Relacje binarne na zbiorze

Przez relację binarną na zbiorze rozumiemy relację binarną zdefiniowaną między dwoma identycznymi zbiorami.

Przykłady

Relacja binarna na zbiorze jest specjalnym typem relacji binarnej, w której dwa wspierające zbiory są takie same. Zatem sesja binarna na zbiorze to sesja R taka, że R ⊆ M × M.

Sesja "większa niż" jest sesją binarną na zbiorze, ponieważ pracujemy z liczbami po obu stronach. Tak więc, > ⊆ ℝ × ℝ. Sesja "ojciec - liczba dzieci" nie jest sesją binarną na zbiorze, ponieważ wybieramy ojca ze zbioru wszystkich ludzi, podczas gdy wybieramy liczbę dzieci z pewnego zbioru liczbowego.

Właściwości

Sesja binarna R na zbiorze M może mieć kilka interesujących właściwości. Mówimy, że sesja R jest...

• refleksyjna, jeśli dla wszystkich a ∈ M zachodzi, że [a, a] ∈ R.
• symetryczna, jeśli dla wszystkich a, b ∈ M zachodzi, że jeśli [a, b] ∈ R, to [b, a] ∈ R.
• antysymetryczny, jeśli dla wszystkich a, b ∈ M zachodzi, że jeśli [a, b] ∈ R jest również [b, a] ∈ R, to a = b.
• przechodni, jeśli dla wszystkich a, b, c ∈ M zachodzi, że jeśli [a, b] ∈ R i również [b, c] ∈ R, to również [a, c] jest w R.

Przykłady refleksyjności

Refleksyjność oznacza, że element jest w relacji do samego siebie. Typowym przykładem jest równość. Jeśli zdefiniowaliśmy równość na liczbach naturalnych, to z pewnością zachodzi ona dla dowolnego elementu a: a = a. Innym przykładem może być podzielność. W tym przypadku liczba a jest podzielna przez samą siebie, więc para [a, a] jest w relacji podzielności (siedem dzieli siedem).

Jednak relacja mniej niż nie jest już refleksyjna, ponieważ nie jest prawdą, że a < a. Nie jest to możliwe, siedem nie może być mniejsze niż siedem. Podobnie relacja bycia ojcem mojego dziecka - nie mogę być swoim własnym ojcem. Taka relacja nie jest refleksyjna.

Chodzi o to, że refleksyjność musi istnieć dla wszystkich elementów, nie wystarczy znaleźć tylko niektóre. Na przykład relacja "lubić kogoś". Z jednej strony mogę kogoś lubić, na przykład korektora, ale mogę też lubić siebie. Z pewnością istnieje osoba, która lubi siebie. Ale jest też osoba, która siebie nie lubi. Taka relacja nie jest wtedy refleksyjna - wszyscy ludzie musieliby lubić samych siebie.

Przykłady symetrii

W relacji symetrycznej, jeśli istnieje para w relacji, to istnieje odwrotna para w relacji. Na przykład relacja bycia rodzeństwem. Jeśli Honza jest rodzeństwem Jany, to Jana jest również rodzeństwem Honzy. Z relacji liczbowych może to być relacja "bycia liczbą przeciwną". Rozumiem przez to parę 2 i −2 lub −7 i 7. Są to dwie liczby, które sumują się do zera. Taka sesja jest symetryczna, ponieważ kolejność po prostu nie ma znaczenia: [2, −2] i [−2, 2] są nadal liczbami przeciwnymi do siebie i sumują się do zera.

Sesja, która nie jest symetryczna, jest mniejsza niż (nad liczbami rzeczywistymi). Nie ma elementu symetrycznego, ponieważ a < b nigdy nie może być ważne, a b < a. Jeśli 5 < 15, to 15 < 5 nie może być ważne. Co więcej, relacja "bycia ojcem swojego syna" nie jest symetryczna. Możesz być ojcem swojego syna, ale wtedy syn nie może być ojcem swojego ojca.

Ponownie, ta własność musi zachodzić dla wszystkich przypadków. Jeśli relacja "lubienia kogoś" (na zbiorze wszystkich ludzi) ma być symetryczna, to jeśli lubię Agatę Hanychovą, to Agus musiałaby lubić mnie w tym samym czasie. A skoro ona mnie nawet nie zna, to nie mogę powiedzieć, że mnie lubi, a szkoda i relacja nie jest symetryczna. Co również jest przykre.

Przykłady antysymetrii

Klasycznym przykładem sesji antysymetrycznej jest sesja mniejsza lub równa. Antysymetria mówi nam, że jeśli elementy [a, b] i [b, a] są w sesji, to jedynym sposobem, w jaki mogą być równe, jest to, że są równe, a = b. Sesja mniejsza lub równa spełnia to. Kiedy a ≤ b i b ≤ a mają zastosowanie w tym samym czasie? Tylko wtedy, gdy a = b. Gdy dodamy: czy 3 ≤ 5 i jednocześnie 5 ≤ 3 mają zastosowanie? Nie. Ale 4 ≤ 4 i 4 ≤ 4 mają zastosowanie w tym samym czasie.

Przykładem sesji, która nie jest antysymetryczna, mogą być pary słów o tej samej długości, na przykład [sobota, sekera]. Taka sesja nie jest antysymetryczna, ponieważ znajdujemy parę słów, które są w sesji, ich element odwrotny jest również w sesji, a jednak te dwa słowa są różne. Tak więc wspomniany element [sobota, sekera] i jego odwrotność: [sekera, sobota]. Oba są oczywiście w naszej sesji, ale jednocześnie sobota ≠ sekera, więc sesja nie jest antysymetryczna.

Przykład przechodniości

Przechodniość jest relacją mniej-więcej. Przechodniość mówi nam, że jeśli 3 < 4 i 4 < 5, to 3 < 5 musi z pewnością również zachodzić. Jest to dość naturalna właściwość dla wielu relacji. Podobnie dla przykładu z tą samą długością słowa. Jeśli [sekera, sobota] i [sobota, poleno] należą do jednej sesji, to słowa [sekera, poleno] również należą do jednej sesji.

Transitive nie jest sesją bycia ojcem syna. Jeśli Tonda jest ojcem Franta, a Franta jest ojcem Mirko, to Tonda nie jest ojcem Mirko, tylko jego dziadkiem. Podobnie, lubienie kogoś nie jest relacją przechodnią. Jeśli lubię Agatę, a Agata lubi swojego męża, nie oznacza to, że lubię męża Agaty.

O przechodniości mówimy także w klasycznej grze w kości. Przypuśćmy, że sesja z kostką A jest lepsza od sesji z kostką B, jeśli prawdopodobieństwo wyrzucenia przez kostkę A większej liczby oczek jest większe niż prawdopodobieństwo wyrzucenia przez kostkę B. Czy taka sesja jest przechodnia? Odpowiedź na to pytanie znajduje się w artykule o nieprzechodnich kostkach.

Równoważność i porządkowanie

Niektóre specjalne typy sesji binarnych mają swoje nazwy:

• Równoważność to sesja, która jest refleksyjna, symetryczna i przechodnia.
• Uporządkowanie to relacja, która jest zwrotna, antysymetryczna i przechodnia.