Relacja euklidesowa

W matematyce relacje euklidesowe są klasą relacji binarnych , które formalizują „ Aksjomat 1 ” w Elementach Euklidesa : „Wielkości, które są równe tym samym, są sobie równe” .

Definicja

Prawa właściwość euklidesowa: pełne i przerywane strzałki wskazują odpowiednio poprzedniki i następniki.

Relacja binarna R na zbiorze X jest euklidesowa (czasami nazywana prawą euklidesową ), jeśli spełnia następujące warunki: dla każdego a , b , c w X , jeśli a jest powiązane z b i c , to b jest powiązane z c . Aby napisać to w logice predykatów :

${\ Displaystyle \ forall a, b, c \ in X \, (a \, R \, b \ ziemia a \, R \, c \ do b \, R \, c).}$

Podwójnie, relacja R na X jest lewostronnie euklidesowa , jeśli dla każdego a , b , c w X , jeśli b jest powiązane z a i c jest powiązane z a , to b jest powiązane z c :

${\ Displaystyle \ forall a, b, c \ w X \, (b \, R \, a \ ziemia c \, R \, a \ do b \, R \, c).}$

Nieruchomości

Schematyczna relacja euklidesowa prawostronna zgodnie z właściwością 10. Głęboko kolorowe kwadraty wskazują klasy równoważności R ′ . Jasne prostokąty wskazują możliwe relacje elementów w X \ran( R ). W tych prostokątach relacje mogą się utrzymywać lub nie.

1. Ze względu na przemienność ∧ w poprzedniku definicji, aRb ∧ aRc implikuje nawet bRc ∧ cRb , gdy R jest prawym euklidesem. Podobnie bRa ∧ cRa implikuje bRc ∧ cRb , gdy R pozostaje euklidesowy.
2. Właściwość bycia euklidesowym różni się od przechodniości . Na przykład ≤ jest przechodnie, ale nie prawostronnie euklidesowe, podczas gdy xRy zdefiniowane przez 0 ≤ x ≤ y + 1 ≤ 2 nie jest przechodnie, ale prawostronnie euklidesowe na liczbach naturalnych .
3. W przypadku relacji symetrycznych przechodniość, prawostronna euklidesowość i lewa euklidesowość są zbieżne. Jednak również relacja niesymetryczna może być zarówno przechodnia, jak i prawostronna euklidesowa, na przykład xRy zdefiniowana przez y = 0.
4. Relacja, która jest zarówno prawo-euklidesowa, jak i zwrotna, jest również symetryczna, a zatem jest relacją równoważności . Podobnie, każda lewostronna euklidesowa i zwrotna relacja jest równoważnością.
5. Zakres właściwej relacji euklidesowej jest zawsze podzbiorem jej dziedziny . Ograniczenie właściwej relacji euklidesowej do jej zakresu jest zawsze zwrotne, a zatem równoważne . Podobnie dziedzina lewostronnej relacji euklidesowej jest podzbiorem jej zakresu, a ograniczenie lewostronnej relacji euklidesowej do jej domeny jest równoważnością.
6. Relacja R jest zarówno lewy, jak i prawy euklidesowy, wtedy i tylko wtedy, gdy dziedzina i zbiór rozstępów R są zgodne, a R jest relacją równoważności na tym zbiorze.
7. Prawostronna relacja euklidesowa jest zawsze quasi-przechodnia , podobnie jak lewa relacja euklidesowa.
8. Połączona prawostronna relacja euklidesowa jest zawsze przechodnia; podobnie jak połączona lewa relacja euklidesowa.
9. Jeśli X ma co najmniej 3 elementy, spójna prawostronna relacja euklidesowa R na X nie może być antysymetryczna , podobnie jak spójna lewostronna relacja euklidesowa na X . Na zbiorze dwuelementowym X = { 0, 1 } np. relacja xRy określona przez y =1 jest spójna, prawostronna euklidesowa i antysymetryczna, a xRy określona przez x =1 jest spójna, lewostronna euklidesowa i antysymetryczna.
10. Relacja R na zbiorze X jest euklidesowa wtedy i tylko wtedy, gdy ograniczenie R ′ := R | _{ran( R )} jest równoważnością i dla każdego x w X \ran( R ), wszystkie elementy, z którymi x jest powiązane pod R są równoważne pod R ′ . Podobnie, R na X jest lewostronnie euklidesowe wtedy i tylko wtedy, gdy R ′ := R | _{dom( R )} jest równoważnością i dla każdego x w X \dom( R ), wszystkie elementy związane z x pod R są równoważne pod R ′ .
11. Lewostronna relacja euklidesowa jest lewostronnie unikalna wtedy i tylko wtedy, gdy jest antysymetryczna . Podobnie, właściwa relacja euklidesowa jest właściwa tylko wtedy i tylko wtedy, gdy jest antysymetryczna.
12. Relacja lewego euklidesa i lewego unikalnego jest próżniowo przechodnia, podobnie jak prawy euklidesowy i prawy unikalny.
13. Lewa relacja euklidesowa pozostaje quasi-zwrotna . W przypadku relacji unikalnych dla lewicy zachodzi również sytuacja odwrotna. Podwójnie, każda prawicowa relacja euklidesowa jest prawostronnie quasi-zwrotna, a każda właściwa jednoznaczna i właściwa quasi-zwrotna relacja jest prawostronnie euklidesowa.