Połączona relacja - Connected relation

W matematyce relację na zbiorze nazywamy połączoną lub całkowitą, jeśli odnosi się (lub „porównuje”) wszystkie odrębne pary elementów zbioru w jednym lub drugim kierunku, podczas gdy nazywa się ją silnie połączoną, jeśli odnosi się do wszystkich par elementów. Jak opisano w sekcji terminologii poniżej , terminologia tych właściwości nie jest jednolita. Tego pojęcia „totalność” nie należy mylić z pojęciem relacji totalnej w tym sensie, że dla wszystkich istnieje tak, że (patrz relacja szeregowa ). ${\ Displaystyle x \ w X}$${\ Displaystyle y \ w X}$${\ Displaystyle x \ mathrel {R} y}$

Powiązanie zajmuje ważne miejsce w definicji ładów całkowitych : porządek całkowity (lub liniowy) jest porządkiem częściowym, w którym dowolne dwa elementy są porównywalne; to znaczy, że relacja porządku jest połączona. Podobnie ścisły porządek częściowy, który jest połączony, jest ścisłym porządkiem całkowitym. Relacja jest porządkiem całkowitym wtedy i tylko wtedy, gdy jest zarówno porządkiem częściowym, jak i silnie powiązanym. Relacja jest ścisłym porządkiem całkowitym wtedy i tylko wtedy, gdy jest ścisłym porządkiem częściowym i jest po prostu połączony. Ścisłe zamówienie całkowite nigdy nie może być silnie połączone (z wyjątkiem pustej domeny).

Formalna definicja

Relacja na zbiorze nazywa się${\ Displaystyle R}$${\ Displaystyle X}$ podłączony, kiedy dla wszystkich${\displaystyle x,y\wX}$

lub równoważnie, kiedy dla wszystkich ${\displaystyle x,y\wX}$

Związek z majątkiem, który dla wszystkich ${\displaystyle x,y\wX}$

nazywa się silnie połączone .

Terminologia

Główne zastosowanie pojęcia powiązanej relacji występuje w kontekście porządków, gdzie używa się go do definiowania całkowitych lub liniowych porządków. W tym kontekście właściwość często nie jest konkretnie nazwana. Porządki całkowite są raczej definiowane jako porządki częściowe, w których dowolne dwa elementy są porównywalne. Zatem,suma jest używana ogólniej dla relacji, które są ze sobą powiązane lub silnie powiązane. Należy jednak odróżnić to pojęcie „całkowitej relacji” od własnościszeregowości, którą nazywamy również totalnością. Podobnie powiązane relacje są czasami nazywanezupełny , chociaż to również może prowadzić do zamieszania:uniwersalna relacjajest również nazywana zupełnym, a „zupełny” ma kilka innych znaczeń wteorii porządku. Powiązane relacje są również nazywaneconnex lub powiedział, że spełniatrichotomię(chociaż bardziej powszechna definicjatrichotomiijest silniejsza w tym,żemusispełnićdokładnie jednąz trzech opcji). ${\ Displaystyle x \ mathrel {R} r, y \ mathrel {R} x, x = y}$

Kiedy rozważane relacje nie są porządkami, bycie połączonym i bycie silnie powiązanym to ważne różne właściwości. Źródła, które definiują oba, następnie używają par terminów, takich jaksłabo połączone ipołączone,zupełneisilnie zupełne,zupełneizupełne,semiconnex iconnexlubconnexiściśle connex , odpowiednio, jako alternatywne nazwy dla pojęć związanych i silnie związanych, jak zdefiniowano powyżej.

Charakterystyki

Niech będzie relacja jednorodna. Poniższe są równoważne: ${\ Displaystyle R}$

• ${\ Displaystyle R}$ jest silnie powiązany;
• ${\ Displaystyle U \ subseteq R \ puchar R ^ {\ top}}$;
• ${\ Displaystyle {\ overline {R}} \ podseteq R ^ {\ top}}$;
• ${\displaystyle {\overline {R}}}$jest asymetryczna ,

gdzie jest uniwersalny relacja i jest odwrotna zależność od${\ Displaystyle U}$${\ Displaystyle R ^ {\ top}}$${\ Displaystyle R.}$

Poniższe są równoważne:

• ${\ Displaystyle R}$ jest połączone;
• ${\ Displaystyle {\ overline {I}} \ subseteq R \ filiżanka R ^ {\ top}}$;
• ${\ Displaystyle {\ overline {R}} \ subseteq R ^ {\ top} \ filiżanka I}$;
• ${\displaystyle {\overline {R}}}$jest antysymetryczna ,

gdzie jest komplementarny związek o stosunku tożsamości i jest odwrotna zależność od${\displaystyle {\overline {I}}}$ ${\ Displaystyle I}$${\ Displaystyle R ^ {\ top}}$${\ Displaystyle R.}$

Wprowadzając progresje, Russell przywołał aksjomat połączenia:

Ilekroć szereg jest pierwotnie dany przez przechodnią relację asymetryczną, możemy wyrazić połączenie przez warunek, że dowolne dwa wyrazy naszego szeregu mają mieć relację generującą .

—  Bertrand Russell , Zasady matematyki, strona 239

Nieruchomości

• Brzeg relacji z turnieju wykresu jest zawsze połączony zależność od zestawu " s wierzchołków.${\ Displaystyle E}$${\ Displaystyle G}$${\ Displaystyle G}$
• Jeśli silnie powiązana relacja jest symetryczna , jest to relacja uniwersalna .
• Relacja jest silnie powiązana wtedy i tylko wtedy, gdy jest połączona i zwrotna.
• Połączona relacja na zbiorze nie może być antyprzechodnia pod warunkiem, że ma co najmniej 4 elementy. Na przykład w zestawie 3-elementowym relacja ma obie właściwości.${\ Displaystyle X}$${\ Displaystyle X}$${\displaystyle \{a,b,c\},}$${\ Displaystyle \ {(a, b), (b, c), (c, a) \}}$
• Jeżeli jest podłączony związek w to wszystkie, lub wszystkie oprócz jednego, elementy znajdują się w zakresie od Podobnie, wszystkie, lub wszystkie oprócz jednego elementy znajdują się w domenie${\ Displaystyle R}$${\displaystyle X,}$${\ Displaystyle X}$${\ Displaystyle R.}$${\ Displaystyle X}$${\ Displaystyle R.}$

Uwagi

Dowody

Bibliografia