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

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

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

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

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

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

Двойственно, отношение R на X является левым евклидовым , если для каждого в , б , с в X , если б связан с и с связано с , то Ь связано с :

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

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

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

Из-за коммутативности ∧ в антецеденте определения, 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] и , следовательно , эквивалентность. Точно так же область левого евклидова отношения является подмножеством его диапазона, а ограничение левого евклидова отношения его областью является эквивалентностью.
Отношение R является левым и правым евклидовым, если и только если область и диапазон значений R совпадают, и R является отношением эквивалентности на этом множестве. ^[7]
Право евклидового отношения всегда quasitransitive , ^[8] и поэтому является левым евклидовым отношением. ^[9]
Пол-Connex права евклидового отношение всегда транзитивный; ^[10], а значит, и левое евклидово отношение полусвязки. ^[11]
Если X не имеет по крайней мере 3 элемента, пол-Connex правого евклидово отношение R на X не может быть антисимметричными , ^[12] , и ни один может пол-Connex оставил евклидово отношения на X . ^[13] На двухэлементном множестве X = {0, 1}, например, отношение xRy, определенное посредством y = 1, является полусвязным, правым евклидовым и антисимметричным, а xRy, определенным посредством x = 1, является полусвязным, левым Евклидово и антисимметрично.
Отношение R на множестве X является правым евклидовым тогда и только тогда, когда ограничение R ' : = R | _{ran ( R )} является эквивалентностью, и для каждого x в X \ ran ( R ) все элементы, с которыми x связан под R , эквивалентны под R ' . ^[14] Аналогично, R на X остается евклидовым тогда и только тогда, когда R ' : = R | _{dom ( R )} - эквивалентность, и для каждого x в X\ dom ( R ), все элементы, связанные с x под R , эквивалентны под R ' .
Левое евклидово отношение уникально слева тогда и только тогда, когда оно антисимметрично . Точно так же правое евклидово отношение уникально справа тогда и только тогда, когда оно антисимметрично.
Левое евклидово и левое единственное отношение вакуумно транзитивно, так же как и правое евклидово и правое единственное отношение.
Левое евклидово отношение квазирефлексивно слева . Для однозначных слева отношений верно и обратное. Соответственно, каждое правое евклидово отношение является правым квазирефлексивным, а каждое правое уникальное и правое квазирефлексивное отношение является правым евклидовым. ^[15]

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

^ ^a ^b Феджин, Рональд (2003), « Рассуждения о знаниях» , MIT Press, стр. 60, ISBN 978-0-262-56200-3 CS1 maint: обескураженный параметр ( ссылка ).
^ например, 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 . Это также доказываетчто у находится в области R .
^ Только если направление вытекает из предыдущего пункта. - Длянаправления if предположим, что aRb и aRc , тогда a , b , c являются членами области и диапазона R , следовательно, bRc по симметрии и транзитивности; Аналогично следуетевклидовость R слева.
^ Если хКа ∧ ¬ угх ∧ yRz ∧ ¬ ZRY имеет место, то и у и г находятся в диапазоне R . Поскольку R эквивалентность на этом множестве, yRz влечет zRy . Следовательно, антецедент формулы определения квазитранзитивности не может быть выполнен.
^ Аналогичное рассуждение применимо, заметивчто х , у находятся в области R .
^ Если хКу ∧ yRz выполнено, то у и г находятся в диапазоне R . Поскольку R является полусвязным, выполняется xRz,или zRx, или x = z . В случае 1 ничего не нужно показывать. В случаях 2 и 3 также x находится в диапазоне. Следовательно, xRz следует из симметрии и рефлексивности R на его пробеге соответственно.
^ Аналогично,помощью этого х , у в области R .
^ Поскольку 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] Феджин, Рональд (2003), « Рассуждения о знаниях» , MIT Press, стр. 60, ISBN 978-0-262-56200-3 CS1 maint: обескураженный параметр ( ссылка ).

[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 . Это также доказываетчто у находится в области R .

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

[8] Если хКа ∧ ¬ угх ∧ yRz ∧ ¬ ZRY имеет место, то и у и г находятся в диапазоне R . Поскольку R эквивалентность на этом множестве, yRz влечет zRy . Следовательно, антецедент формулы определения квазитранзитивности не может быть выполнен.

[9] Аналогичное рассуждение применимо, заметивчто х , у находятся в области R .

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

[11] Аналогично,помощью этого х , у в области R .

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

[13] Аналогичными рассуждениями, используя домен R .

[14] Только если: 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 .

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

[1]