Евклидово отношение - Euclidean relation

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

Определение

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

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

${displaystyle forall a,b,cin X,(a,R,bland a,R,c o b,R,c).}$

Двойственно отношение р на Икс является левый евклидов если для каждого а, б, c в Икс, если б относится к а и c относится к а, тогда б относится к c:

${displaystyle forall a,b,cin X,(b,R,aland c,R,a o b,R,c).}$

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

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

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

Рекомендации

1. Феджин, Рональд (2003), Рассуждения о знаниях, MIT Press, стр. 60, ISBN  978-0-262-56200-3.
2. например 0 ≤ 2 и 0 ≤ 1, но не 2 ≤ 1
3. например 2р1 и 1р0, но не 2р0
4. xRy и xRx подразумевает yRx.
5. Равенство домена и диапазона не обязательно: отношение xRy определяется у= min {Икс, 2} является правым евклидовым элементом на натуральных числах, а его диапазон, {0,1,2}, является собственным подмножеством его области определения, ℕ.
6. Если у находится в диапазоне р, тогда xRy ∧ xRy подразумевает год, для некоторых подходящих Икс. Это также доказывает, что у находится в сфере р.
7. В только если направление следует из предыдущего абзаца. - Для если направление, предполагать aRb и АРК, тогда а,б,c являются членами домена и диапазона р, следовательно bRc симметрией и транзитивностью; левый евклидовость р следует аналогично.
8. Если xRy ∧ ¬yRx ∧ yRz ∧ ¬zRy держит, то оба у и z находятся в диапазоне р. С р эквивалентность на этом множестве, yRz подразумевает zRy. Следовательно, антецедент формулы определения квазитранзитивности не может быть выполнен.
9. Аналогичный аргумент применим, если учесть, что Икс,у находятся в сфере р.
10. Если xRy ∧ yRz держит, то у и z находятся в диапазоне р. С р полуконнекс, xRz или же zRx или же Икс=z держит. В случае 1 ничего не нужно показывать. В случаях 2 и 3 также Икс находится в диапазоне. Следовательно, xRz следует из симметрии и рефлексивности р по своему ассортименту соответственно.
11. Аналогично, используя это Икс, у находятся в сфере р.
12. С р является полусоединением, по крайней мере, два различных элемента Икс,у находятся в его классифицировать, и xRy ∨ yRx держит. С р симметричен в своем диапазоне, даже xRy ∧ yRx держит. Это противоречит свойству антисимметрии.
13. По аналогичному аргументу, используя домен р.
14. Только если: р’Является эквивалентом, показанным выше. Если Икс∈Иксан (р) и xR’y₁ и xR’y₂, тогда у₁Ry₂ по праву евклидовости, следовательно у₁Ри₂. — Если: если xRy ∧ xRz держит, то у,z∈ran (р). В случае также Икс∈ran (р), четное xR’y ∧ xR’z имеет место, следовательно yR’z симметрией и транзитивностью Р', следовательно yRz. В случае Икс∈Иксан (р), элементы у и z должен быть эквивалентен Р' по предположению, следовательно, и yRz.
15. Йохен Бургхардт (ноябрь 2018 г.). Простые законы о невыразительных свойствах бинарных отношений (Технический отчет). arXiv:1806.05036v2. Лемма 44-46.