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

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

Определение

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

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

${\displaystyle \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 :

${\displaystyle \forall a,b,c\in X\,(b\,R\,a\land c\,R\,a\to b\,R\,c).}$

Характеристики

Схематизированное правое евклидово отношение согласно свойству 10. Ярко окрашенные квадраты обозначают классы эквивалентности R ′ . Бледно окрашенные прямоугольники обозначают возможные отношения элементов в X \ran( R ). В этих прямоугольниках отношения могут иметь место, а могут и не иметь место.

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

Ссылки

1. Fagin, Ronald (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 .
7. Бак, Чарльз (1967), «Альтернативное определение отношений эквивалентности», Учитель математики , 60 : 124–125.
8. Единственное направление if следует из предыдущего абзаца. — Для направления if предположим aRb и aRc , тогда a , b , c являются членами области определения и области определения R , следовательно, bRc по симметрии и транзитивности; левоевклидовость R следует аналогично.
9. Если выполняется xRy ∧ ¬ yRx ∧ yRz ∧ ¬ zRy , то и y, и z находятся в диапазоне R . Поскольку R является эквивалентностью на этом множестве, yRz влечет zRy . Следовательно, антецедент формулы определения квазитранзитивности не может быть удовлетворен.
10. Применим аналогичный аргумент, учитывая, что x , y находятся в области R.
11. Если выполняется xRy ∧ yRz , то y и z находятся в области действия R . Поскольку R связно, выполняется xRz или zRx или x = z . В случае 1 больше ничего не нужно доказывать. В случаях 2 и 3 также x находится в области действия. Следовательно, xRz следует из симметрии и рефлексивности R на его области действия соответственно.
12. Аналогично, используя то, что x , y находятся в области определения R.
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.