Relacja przechodnia

Relacja przechodnia

Typ	Relacja binarna
Pole	Algebra elementarna
Oświadczenie	Relacja na zbiorze jest przechodnia , jeśli dla wszystkich elementów $a}$$\$$Displaystyle$ , ${\ Displaystyle b}$${\ Displaystyle C}$ w $Displaystyle X} }$ , ilekroć odnosi się ${$ \ displaystyle a} do b {\ displaystyle b} i $b$ \ $b$$do$ { $displaystyle c}$$}$ wtedy odnosi się również ${\$ do $a$ .
Symboliczne stwierdzenie	$\ Displaystyle \ forall a, b, c \ in X: (aRb \ klin bRc) \ Strzałka w prawo aRc}$

W matematyce relacja a R na zbiorze X jest przechodnia , jeśli dla wszystkich elementów a , b , c w X , ilekroć R odnosi się do b i b do c , to R odnosi się również a do c . Każdy rząd częściowy , jak również każda relacja równoważności musi być przechodnia.

Definicja

Przechodnie relacje binarne
Symetryczny antysymetryczny Połączony Dobrze uzasadnione Ma połączenia Spotyka się Zwrotny Bezrefleksyjny Asymetryczny Razem, Semiconnex Antyrefleksyjny _ Relacja równoważności Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Zamówienie w przedsprzedaży (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Zamówienie częściowe ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Całkowita przedsprzedaż ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Całkowite zamówienie ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Wstępne zamawianie ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Cóż, quasi-porządkowanie ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Dobrze uporządkowany ✗ Y Y Y ✗ ✗ Y ✗ ✗ Krata ✗ Y ✗ ✗ Y Y Y ✗ ✗ Semilatyka łączenia ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Meet-semilatice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Ścisły porządek częściowy ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Ściśle słaby porządek ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Ścisły porządek całkowity ✗ Y Y ✗ ✗ ✗ ✗ Y Y Symetryczny antysymetryczny Połączony Dobrze uzasadnione Ma połączenia Spotyka się Zwrotny Bezrefleksyjny Asymetryczny Definicje dla wszystkich ${\ Displaystyle a, b}$ i ${\ Displaystyle S \ neq \ varnothing:}$ $w prawo {}&bRa \ koniec {wyrównane}}}$ $\ Displaystyle {\ rozpocząć {wyrównane} aRb {\ tekst {i}} & bRa \\\ Strzałka w prawo a = {} & b \ koniec {wyrównane}}}$ ${\ Displaystyle {\ rozpocząć {wyrównane} a \ neq {} & b \ Strzałka w prawo \\ aRb {\ tekst {lub}} & bRa \ koniec {wyrównane}}}$ ${\ Displaystyle {\ rozpocząć {wyrównane} \ min S \\ {\ tekst {istnieje}} \ koniec {wyrównane}}}$ ${\ Displaystyle {\ rozpocząć {wyrównane} a \ vee b \\ {\ tekst {istnieje}} \ koniec {wyrównane}}}$ ${\ Displaystyle {\ rozpocząć {wyrównane} a \ klin b \\ {\ tekst {istnieje}} \ koniec {wyrównane}}}$ ${\ displaystyle aRa}$ ${\ Displaystyle {\ tekst {nie}} aRa}$ ${\ Displaystyle {\ rozpocząć {wyrównane} aRb \ Strzałka w prawo \\ {\ tekst {nie}} bRa \ koniec {wyrównane}}}$
Y wskazuje, że właściwość kolumny jest zawsze prawdziwa dla terminu wiersza (po lewej stronie), podczas gdy ✗ wskazuje, że właściwość nie jest ogólnie gwarantowana (może być zachowana lub nie). Na przykład, że każda relacja równoważności jest symetryczna, ale niekoniecznie antysymetryczna, jest wskazana odpowiednio przez Y w kolumnie „Symetryczny” i ✗ w kolumnie „Antysymetryczny”. Wszystkie definicje milcząco wymagają, aby jednorodna relacja była przechodnia : dla wszystkich ${\ Displaystyle a, b, c,}$$jeśli$${\ displaystyle bRc}$ za $\ displaystyle aRb}$ i ${\ displaystyle aRc.}$ następnie Definicja terminu może wymagać dodatkowych właściwości , które nie są wymienione w tej tabeli.

Relacja jednorodna R na zbiorze X jest relacją przechodnią , jeśli

dla wszystkich a , b , c ∈ X , jeśli a R b i b R c , to a R c .

Lub w kategoriach logiki pierwszego rzędu :

$\ Displaystyle \ forall a, b, c \ in X: (aRb \ klin bRc) \ Strzałka w prawo aRc}$ ,

gdzie a R b jest notacją wrostkową dla ( a , b ) ∈ R .

Przykłady

Jako przykład niematematyczny, relacja „jest przodkiem” jest przechodnia. Na przykład, jeśli Amy jest przodkiem Becky, a Becky jest przodkiem Carrie, to Amy również jest przodkiem Carrie.

Z drugiej strony „jest biologicznym rodzicem” nie jest relacją przechodnią, ponieważ jeśli Alice jest biologicznym rodzicem Brendy, a Brenda jest biologicznym rodzicem Claire, to nie oznacza to, że Alice jest biologicznym rodzicem Claire . Co więcej, jest antyprzechodnie : Alice nigdy nie może być biologiczną matką Claire.

Relacje nieprzechodnie, nieprzechodnie obejmują mecze sportowe, „wie” i „rozmawia z”.

„Jest większe niż”, „jest co najmniej tak duże jak” i „jest równe” ( równość ) to relacje przechodnie na różnych zbiorach, na przykład zbiorze liczb rzeczywistych lub zbiorze liczb naturalnych:

zawsze, gdy x > y i y > z , to także x > z

zawsze, gdy x ≥ y i y ≥ z , wtedy też x ≥ z

zawsze, gdy x = y i y = z , wtedy też x = z .

Więcej przykładów relacji przechodnich:

• „jest podzbiorem ” (włączenie zestawu, relacja na zbiorach)
• „dzieli” ( podzielność , relacja na liczbach naturalnych)
• „implikuje” ( implikacja , symbolizowana przez „⇒”, relacja dotycząca zdań )

Przykłady relacji nieprzechodnich:

• „jest następcą ” (relacja na liczbach naturalnych)
• „jest członkiem zbioru” (symbolizowane jako „∈”)
• „jest prostopadły do” (relacja na liniach w geometrii euklidesowej )

Pusta relacja na dowolnym zbiorze $jest$ przechodnia, ponieważ nie ma elementów ${\ displaystyle aRb}$ że ${\ Displaystyle a, b, c \ in X}$${\ displaystyle bRc}$ i za , a zatem warunek przechodniości jest próżniowo prawdziwy . Relacja R zawierająca tylko jedną uporządkowaną parę $postać$$X$ jeśli uporządkowana ${\ Displaystyle a, b, c \ in X}$ niektórych tylko są ${\ Displaystyle a = b = c = x}$ i rzeczywiście w tym przypadku ${\ Displaystyle aRc}$ , natomiast jeśli uporządkowana para nie ma postaci ${\ Displaystyle (x, x)}$ to nie ma takich elementów ${\ Displaystyle a, b, c \ in X}$ a zatem $przechodnie$ .

Nieruchomości

Właściwości zamknięcia

• Odwrotność (odwrotność) relacji przechodniej jest zawsze przechodnia. Na przykład, wiedząc, że „jest podzbiorem ” jest przechodnie, a „jest nadzbiorem ” jest jego odwrotnością, można wywnioskować, że to drugie jest również przechodnie.
• Przecięcie dwóch relacji przechodnich jest zawsze przechodnie. Na przykład, wiedząc, że „urodził się wcześniej” i „ma to samo imię co” są przechodnie, można wywnioskować, że „urodził się wcześniej i ma to samo imię co” również jest przechodnie.
• Połączenie dwóch relacji przechodnich nie musi być przechodnie. Na przykład „urodził się przed lub ma takie samo imię jak” nie jest relacją przechodnią, ponieważ np. Herbert Hoover jest spokrewniony z Franklinem D. Rooseveltem , który z kolei jest spokrewniony z Franklinem Pierce'em , podczas gdy Hoover nie jest spokrewniony z Franklinem Pierce'em .
• Dopełnienie relacji przechodniej nie musi być przechodnie. Na przykład, podczas gdy „równe do” jest przechodnie, „nie równe” jest przechodnie tylko w zestawach z co najwyżej jednym elementem.

Inne właściwości

Relacja przechodnia jest asymetryczna wtedy i tylko wtedy, gdy jest zwrotna .

Relacja przechodnia nie musi być zwrotna . Kiedy tak jest, nazywa się to zamówieniem w przedsprzedaży . Na przykład na zbiorze X = {1,2,3}:

• R = {(1,1), (2,2), (3,3), (1,3), (3,2)} jest zwrotne, ale nie przechodnie, ponieważ para (1,2) jest nieobecna ,
• R = {(1,1), (2,2), (3,3), (1,3) } jest zarówno zwrotne, jak i przechodnie, więc jest to preorder,
• R = { (1,1), (2,2), (3,3) } jest zarówno zwrotne, jak i przechodnie, kolejny preorder.

Rozszerzenia przechodnie i domknięcie przechodnie

Główny artykuł: zamknięcie przechodnie

Niech R będzie relacją binarną na zbiorze X . Przechodnie rozszerzenie R , oznaczone jako R ₁ , jest najmniejszą relacją binarną na X taką, że R ₁ zawiera R , a jeśli ( a , b ) ∈ R i ( b , c ) ∈ R to ( a , c ) ∈ R ₁ . Załóżmy na przykład, że X to zbiór miast, z których niektóre są połączone drogami. Niech R będzie relacją dla miast gdzie ( A , B ) ∈ R jeśli istnieje droga bezpośrednio łącząca miasto A i B . Ta relacja nie musi być przechodnia. Przechodnie rozszerzenie tej relacji może być określone przez ( A , C ) ∈ R ₁ jeśli możesz podróżować między miastami A i C używając co najwyżej dwóch dróg.

Jeśli relacja jest przechodnia, to jej przechodnim rozszerzeniem jest ona sama, to znaczy, jeśli R jest relacją przechodnią, to R ₁ = R .

Przechodnie rozszerzenie R1 _w byłoby oznaczone przez R2 i kontynuując _. ten sposób, generalnie przechodnie _rozszerzenie Ri byłoby Ri _{+ 1} Domknięcie przechodnie R , oznaczone przez R * lub R ^∞ jest sumą zbiorów R , R ₁ , R ₂ , ... .

Przechodnie zamknięcie relacji jest relacją przechodnią.

Relacja „jest biologicznym rodzicem” na zbiorze ludzi nie jest relacją przechodnią. Jednak w biologii często pojawia się potrzeba rozważenia rodzicielstwa biologicznego na dowolnej liczbie pokoleń: relacja „jest biologicznym przodkiem” jest relacją przechodnią i jest przechodnim zamknięciem relacji „jest biologicznym rodzicem”.

Dla powyższego przykładu miast i dróg, ( A , C ) ∈ R * pod warunkiem, że między miastami A i C można podróżować dowolną liczbą dróg.

Typy relacji wymagające przechodniości

• Preorder – relacja zwrotna i przechodnia
• Porządek częściowy – antysymetryczny preorder
• Total preorder – połączona (wcześniej nazywana totalną) przedsprzedaż
• Relacja równoważności – symetryczny preorder
• Ścisłe uporządkowanie słabe - ścisłe uporządkowanie częściowe, w którym nieporównywalność jest relacją równoważności
• Porządkowanie całkowite - relacja spójna (całkowita), antysymetryczna i przechodnia

Liczenie relacji przechodnich

żaden ogólny wzór, który liczy liczbę relacji przechodnich na zbiorze skończonym (sekwencja A006905 w OEIS ). Istnieje jednak wzór na znalezienie liczby relacji, które są jednocześnie zwrotne, symetryczne i przechodnie - innymi słowy, relacje równoważności - (sekwencja A000110 w OEIS ), te, które są symetryczne i przechodnie, te, które są symetryczne, przechodnie i antysymetryczne oraz te, które są całkowite, przechodnie i antysymetryczne. Pfeiffer poczynił pewne postępy w tym kierunku, wyrażając relacje z kombinacjami tych właściwości w odniesieniu do siebie nawzajem, ale obliczenie którejkolwiek z nich jest trudne. Zobacz także Brinkmann i McKay (2005). Mala wykazała, że ​​żaden wielomian ze współczynnikami całkowitymi nie może reprezentować wzoru na liczbę relacji przechodnich w zbiorze i znalazła pewne relacje rekurencyjne, które zapewniają dolne granice tej liczby. Pokazał również, że ta liczba jest wielomianem drugiego stopnia, jeśli zbiór zawiera dokładnie dwie uporządkowane pary .

Liczba n -elementowych relacji binarnych różnych typów

Elementy	Każdy	Przechodni	Zwrotny	Symetryczny	Przed Sprzedaż	Zamówienie częściowe	Całkowita przedsprzedaż	Całkowite zamówienie	Relacja równoważności
0	1	1	1	1	1	1	1	1	1
1	2	2	1	2	1	1	1	1	1
2	16	13	4	8	4	3	3	2	2
3	512	171	64	64	29	19	13	6	5
4	65536	3994	4096	1024	355	219	75	24	15
N	2 n 2		2 n 2 - rz	2 n ( n +1)/2			${\ textstyle \ suma _ {k = 0} ^ {n} k! S (n, k)}$	n !	${\ textstyle \ suma _ {k = 0} ^ {n} S (n, k)}$
OEIS	A002416	A006905	A053763	A006125	A000798	A001035	A000670	A000142	A000110

Zauważ, że S ( n , k ) odnosi się do liczb Stirlinga drugiego rodzaju .

Powiązane właściwości

Kamień –papier–nożyce opiera się na nieprzechodnim i antyprzechodnim związku „ x bije y ”.

Relację R nazywamy nieprzechodnią , jeśli nie jest przechodnia, to znaczy, jeśli xRy i yRz , ale nie xRz , dla pewnych x , y , z . Natomiast relację R nazywamy antyprzechodnią, jeśli xRy i yRz zawsze implikują, że xRz nie zachodzi. Na przykład relacja zdefiniowana przez xRy , jeśli xy jest liczbą parzystą jest nieprzechodni, ale nie antyprzechodni. Relacja zdefiniowana przez xRy , jeśli x jest parzysta, a y nieparzysta , jest zarówno przechodnia, jak i antyprzechodnia. Relacja zdefiniowana przez xRy , jeśli x jest kolejnym numerem y , jest zarówno nieprzechodnia, jak i antyprzechodnia. Nieoczekiwane przykłady nieprzechodniości pojawiają się w sytuacjach takich jak kwestie polityczne lub preferencje grupowe.

Uogólnione do wersji stochastycznych ( stochastyczna przechodniość ), badanie przechodniości znajduje zastosowanie w teorii decyzji , psychometrii i modelach użyteczności .

Innym uogólnieniem jest relacja quasi-przechodnia ; wymagane jest, aby był przechodni tylko w swojej niesymetrycznej części. Relacje takie są wykorzystywane w teorii wyboru społecznego czy mikroekonomii .

Twierdzenie: Jeśli R jest jednowartościowe , to R;R ^T jest przechodnie.

dowód: Załóżmy ${\ Displaystyle xR; R ^ {T} yR; R ^ {T} z.}$ Wtedy są a i b takie, że ${\ Displaystyle xRaR ^ {T} yRbR ^ {T} z.}$ Ponieważ R jest jednowartościowy, yRb i aR ^T y implikują a = b . Zatem x R a R ^T z , stąd x R; R ^T z i R; R ^T jest przechodnie.

Wniosek : Jeśli R jest jednowartościowy, to R; R ^T jest relacją równoważności w dziedzinie R .

dowód: R;R ^T jest symetryczny i zwrotny w swojej dziedzinie. Przy jednowartościowości R spełniony jest warunek przechodni równoważności.

Zobacz też

• Redukcja przechodnia
• Kości nieprzechodnie
• Teoria racjonalnego wyboru
• Sylogizm hipotetyczny — przechodniość warunku materialnego

Notatki

•   Grimaldi, Ralph P. (1994), Matematyka dyskretna i kombinatoryczna (wyd. 3), Addison-Wesley, ISBN 0-201-19912-2
•   Liu, CL (1985), Elementy matematyki dyskretnej , McGraw-Hill, ISBN 0-07-038133-X
•   Gunther Schmidt , 2010. Matematyka relacyjna . Cambridge University Press, ISBN 978-0-521-76268-7 .
•   Smith, Douglas; Eggen, Maurice; St.Andre, Richard (2006), A Transition to Advanced Mathematics (wyd. 6), Brooks / Cole, ISBN 978-0-534-39900-9
• Pfeiffer, G. (2004). Liczenie relacji przechodnich. Dziennik sekwencji liczb całkowitych , 7 (2), 3.

Linki zewnętrzne

• „Przechodniość” , Encyklopedia matematyki , EMS Press , 2001 [1994]
• Przechodniość w działaniu na skróty