Евклидово соотношение

В математике евклидовы отношения представляют собой класс бинарных отношений , которые формализуют « Аксиому 1 » в » Евклида «Началах : «Величины, равные одному и тому же, равны друг другу».

Определение [ править ]

Право-евклидово свойство: сплошная и пунктирная стрелки указывают антецеденты и консеквенты соответственно.

Бинарное отношение R на множестве X является евклидовым (иногда называемым правым евклидовым ), если оно удовлетворяет следующему: для каждых a , b , c в X , если a связано с b и c , то b связано с c . ^[1] Чтобы записать это в логике предикатов :

\forall a,b,c\in X\,(a\,R\,b\land a\,R\,c\to b\,R\,c).

Двойственным образом отношение R на X является левоевклидовым , если для каждых a , b , c в X , если b связано с a , а c связано с a , то b связано с c :

\forall a,b,c\in X\,(b\,R\,a\land c\,R\,a\to b\,R\,c).

Свойства [ править ]

Из-за коммутативности ∧ в антецеденте определения из aRb ∧ aRc даже следует bRc ∧ cRb , когда R правоевклидово. Аналогично, из bRa ∧ cRa следует bRc ∧ cRb, когда R левоевклидово.
Свойство быть евклидовым отличается от транзитивности . Например, ≤ является транзитивным, но не правоевклидовым, ^[2] в то время как xRy, определенный как 0 ≤ x ≤ y + 1 ≤ 2, не является транзитивным, ^[3] но правильный Евклид в отношении натуральных чисел .
Для симметричных отношений транзитивность, правая евклидовость и левая евклидовость совпадают. Однако несимметричное отношение также может быть как транзитивным, так и правоевклидовым, например, xRy, определенное как y =0.
Отношение, которое является одновременно правоевклидовым и рефлексивным, также является симметричным и, следовательно, является отношением эквивалентности . ^[1]^[4] Точно так же каждое левоевклидово и рефлексивное отношение является эквивалентностью.
Диапазон правого евклидова отношения всегда является подмножеством ^[5] своего домена . Ограничение . правого евклидова отношения на его диапазон всегда рефлексивно ^[6] и, следовательно, эквивалентность. Точно так же область определения левого евклидова отношения является подмножеством его диапазона, а ограничение левого евклидова отношения на его область определения является эквивалентностью. Следовательно, правое евклидово отношение на X , которое также является тотальным справа (соответственно левое евклидово отношение на X , которое также является тотальным слева ), является эквивалентностью, поскольку его диапазон (соответственно его область определения) равен X . ^[7]
Отношение R является как левым, так и правосторонним евклидовым тогда и только тогда, когда область определения и множество диапазонов R согласуются, и R является отношением эквивалентности на этом множестве. ^[8]
Правое евклидово отношение всегда квазитранзитивно . ^[9] как и левое евклидово отношение. ^[10]
Связное ; правоевклидово отношение всегда транзитивно ^[11] то же самое относится и к связному левому евклидову отношению. ^[12]
Если X имеет по крайней мере 3 элемента, связное правоевклидово отношение R на X не может быть антисимметричным . ^[13] и связное левоевклидово отношение на X тоже не может . ^[14] На 2-элементном множестве X = {0, 1}, например, отношение xRy, определенное как y =1, связно, правоевклидово и антисимметрично, а отношение xRy, определенное как x =1, связно, левоевклидово и антисимметрично.
Отношение R на множестве X является правоевклидовым тогда и только тогда, когда ограничение R ′ := R | _{ran( R )} является эквивалентностью, и для каждого x в X \ran( R ) все элементы, с которыми x связан относительно R, эквивалентны относительно R ′ . ^[15] Аналогично, R на X является левоевклидовым тогда и только тогда, когда R ′ := R | _{dom( R )} является эквивалентностью, и для каждого x в X \dom( R ) все элементы, связанные с x относительно R, эквивалентны относительно R ′ .
Левое евклидово отношение уникально слева тогда и только тогда, когда оно антисимметрично . Точно так же правое евклидово отношение уникально справа тогда и только тогда, когда оно антисимметрично.
Лево-евклидово и лево-единственное отношение является бессмысленно транзитивным, как и право-евклидово и право-единственное отношение.
Левое евклидово отношение является левым квазирефлексивным . Для уникальных слева отношений справедливо и обратное. Двойственным образом каждое правоевклидово отношение является правоквазирефлексивным, а каждое правое уникальное и правоквазирефлексивное отношение является правоевклидовым. ^[16]

Ссылки [ править ]

^ Jump up to: ^а ^б Феджин, Рональд (2003), Рассуждения о знаниях , MIT Press, стр. 60, ISBN 978-0-262-56200-3 .
^ например, 0 ≤ 2 и 0 ≤ 1, но не 2 ≤ 1
^ например, 2 R 1 и 1 R 0, но не 2 R 0
^ xRy и xRx подразумевают yRx .
^ Равенство домена и диапазона не является обязательным: отношение xRy, определенное как y =min{ x ,2}, является правоевклидовым для натуральных чисел, а его диапазон {0,1,2} является правильным подмножеством его область натуральных чисел.
^ Если y находится в диапазоне R , то xRy ∧ xRy подразумевает yRy для некоторого подходящего x . Это также доказывает, что y находится в области определения R .
^ Бак, Чарльз (1967), «Альтернативное определение отношений эквивалентности» , Учитель математики , 60 : 124–125 .
^ Единственное , если направление следует из предыдущего абзаца. — Для направления if предположим aRb и aRc , тогда a , b , c являются членами области и диапазона R , следовательно, bRc в силу симметрии и транзитивности; левая евклидовость R. Аналогично следует
^ Если выполняется xRy ∧ ¬ yRx ∧ yRz ∧ ¬ zRy , то и y , и z находятся в диапазоне R . Поскольку R является эквивалентностью на этом множестве, из yRz следует zRy . Следовательно, антецедент формулы определения квазитранзитивности не может быть удовлетворен.
^ Аналогичный аргумент применим, учитывая, что , y находятся в области R. x
^ Если выполняется xRy ∧ yRz , то y и z находятся в диапазоне R . Поскольку R связен, выполняется xRz или zRx или x = z . В случае 1 ничего не остается показывать. В случаях 2 и 3 x также находится в диапазоне. Следовательно, xRz следует из симметрии и рефлексивности R на его образе соответственно.
^ Аналогично, используя то, что , y находятся в области R. x
^ Поскольку R связен, по крайней мере два различных элемента x , y находятся в его диапазоне , и выполняется xRy ∨ yRx . Поскольку R симметричен в своем диапазоне, выполняется даже xRy ∧ yRx . Это противоречит свойству антисимметрии.
^ По аналогичному аргументу, используя область определения R .
^ Только если: R ′ является эквивалентностью, как показано выше. Если x ∈ X \ran( R ) и xR ′ y ₁ и xR ′ y ₂ , то y ₁ Ry ₂ в силу правоевклидовости, следовательно, y ₁ R ′ y ₂ . — Если : если выполнено xRy ∧ xRz , то y , z ∈ran( R ). В случае, когда x ∈ran( R ), имеет место даже xR ′ y ∧ xR ′ z , следовательно, yR ′ z в силу симметрии и транзитивности R ′ , следовательно, yRz . В случае x ∈ X \ran( R ), элементы y и z должны быть эквивалентны относительно R ′ по предположению, а значит, и yRz .
^ Йохен Бургхардт (ноябрь 2018 г.). Простые законы о невыявленных свойствах бинарных отношений (технический отчет). arXiv : 1806.05036v2 . Лемма 44–46.

[fagin-1] Jump up to: ^а ^б Феджин, Рональд (2003), Рассуждения о знаниях , MIT Press, стр. 60, ISBN 978-0-262-56200-3 .

[2] например, 0 ≤ 2 и 0 ≤ 1, но не 2 ≤ 1

[3] например, 2 R 1 и 1 R 0, но не 2 R 0

[4] xRy и xRx подразумевают yRx .

[5] Равенство домена и диапазона не является обязательным: отношение xRy, определенное как y =min{ x ,2}, является правоевклидовым для натуральных чисел, а его диапазон {0,1,2} является правильным подмножеством его область натуральных чисел.

[6] Если y находится в диапазоне R , то xRy ∧ xRy подразумевает yRy для некоторого подходящего x . Это также доказывает, что y находится в области определения R .

[buck-7] Бак, Чарльз (1967), «Альтернативное определение отношений эквивалентности» , Учитель математики , 60 : 124–125 .

[8] Единственное , если направление следует из предыдущего абзаца. — Для направления if предположим aRb и aRc , тогда a , b , c являются членами области и диапазона R , следовательно, bRc в силу симметрии и транзитивности; левая евклидовость R. Аналогично следует

[9] Если выполняется xRy ∧ ¬ yRx ∧ yRz ∧ ¬ zRy , то и y , и z находятся в диапазоне R . Поскольку R является эквивалентностью на этом множестве, из yRz следует zRy . Следовательно, антецедент формулы определения квазитранзитивности не может быть удовлетворен.

[10] Аналогичный аргумент применим, учитывая, что , y находятся в области R. x

[11] Если выполняется xRy ∧ yRz , то y и z находятся в диапазоне R . Поскольку R связен, выполняется xRz или zRx или x = z . В случае 1 ничего не остается показывать. В случаях 2 и 3 x также находится в диапазоне. Следовательно, xRz следует из симметрии и рефлексивности R на его образе соответственно.

[12] Аналогично, используя то, что , y находятся в области R. x

[13] Поскольку R связен, по крайней мере два различных элемента x , y находятся в его диапазоне , и выполняется xRy ∨ yRx . Поскольку R симметричен в своем диапазоне, выполняется даже xRy ∧ yRx . Это противоречит свойству антисимметрии.

[14] По аналогичному аргументу, используя область определения R .

[15] Только если: R ′ является эквивалентностью, как показано выше. Если x ∈ X \ran( R ) и xR ′ y ₁ и xR ′ y ₂ , то y ₁ Ry ₂ в силу правоевклидовости, следовательно, y ₁ R ′ y ₂ . — Если : если выполнено xRy ∧ xRz , то y , z ∈ran( R ). В случае, когда x ∈ran( R ), имеет место даже xR ′ y ∧ xR ′ z , следовательно, yR ′ z в силу симметрии и транзитивности R ′ , следовательно, yRz . В случае x ∈ X \ran( R ), элементы y и z должны быть эквивалентны относительно R ′ по предположению, а значит, и yRz .

[16] Йохен Бургхардт (ноябрь 2018 г.). Простые законы о невыявленных свойствах бинарных отношений (технический отчет). arXiv : 1806.05036v2 . Лемма 44–46.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]