Załóżmy, że mamy zestaw czterech różnych kolorów kartek. Możemy oczywiście ułożyć je w cztery stosy tak, iż na każdym z nich znajduje się dokładnie jeden kolor. Innymi słowy, dwie kartki znajdują się na tym samym stosie, jeżeli są tego samego koloru. Oczywiście każda z kartek musi leżeć na jakimś stosie i żadna nie może leżeć na więcej niż jednym. Właśnie zbudowaliśmy relację w zbiorze kartek.
Relacje i relacja równoważności
Podstawowy problem opiera się na poprawnym zdefiniowaniu relacji. Jak wskazuje Kazimierz Trzęsicki (2006), relacją dwuczłonową w iloczynie X×Y, gdzie X i Y są zbiorami, jest każdy podzbiór zbioru X×Y. Tę enigmatyczną definicję ukażemy opierając się na prostym przykładzie. Rozważmy płaszczyznę, czyli iloczyn zbiorów liczb rzeczywistych ℝ×ℝ. Załóżmy, że liczba y jest w relacji z x wtedy, gdy y=x. Zbiorem elementów będących ze sobą w relacji jest zatem prosta o równaniu y=x przedstawiona niżej. Prosta ta jest podzbiorem płaszczyzny. Ogólniej, relacja wyznacza pary liczb (a, b) takie, że a jest w relacji z b i zawsze jest to część lub całość zbioru wszystkich par liczb – tych, które są oraz tych, które nie są ze sobą w relacji. Oznacza to równocześnie, że relację określamy na konkretnym zbiorze. Jak widać, funkcja jest szczególnym rodzajem relacji – takiej, w której pierwszy element jest w relacji z dokładnie jednym elementem.
Rysunek 1. Prosta na płaszczyźnie jako wizualizacja relacji
Relację przedstawia się zazwyczaj w postaci warunku: „x jest w relacji z y, jeżeli…” i jeśli własność ta zachodzi, zapisujemy zwyczajowo xRy. Z perspektywy zastosowania relacji istotne jest określenie pewnych podstawowych własności. Powiemy, że relacja jest zwrotna, jeżeli każdy element jest w relacji sam ze sobą lub inaczej xRx. Cecha podzielności w zbiorze {1,2,3,4} jest relacją zwrotną, bo każda z tych liczb jest podzielna przez samą siebie. Zwrotna jest także na tym zbiorze relacja równości – oczywiście dana liczba jest równa samej sobie. Warunku tego nie spełni natomiast relacja ostrej nierówności – liczba nie może być większa od samej siebie: 3<3 nie jest prawdą.
Drugą istotną własność stanowi symetria: jeżeli element x jest w relacji z y, to y jest w relacji z x, inaczej: xRy ⇒ yRx. Warunek ten pozwala na przestawianie elementów względem relacji bez naruszenia prawdziwości zdania. Określmy w zbiorze liczb całkowitych relację: xRy x-y jest liczbą naturalną. Relacja ta nie jest symetryczna – weźmy liczby 2 i 5. 5-2=3 jest liczbą naturalną, więc zachodzi 5R2, jednak 2-5=-3 i nie jest to liczba naturalna, zatem nie zachodzi 2R5. Symetryczna jest za to relacja: w danej szkole uczeń X jest w relacji z uczniem Y, jeżeli X i Y są w tej samej klasie. Jeżeli X i Y są w tej samej klasie, to wypowiedź z odwróconą kolejnością: Y i X są w tej samej klasie, nie zmienia istoty znaczenia relacji – a więc Y i X są w tej samej klasie. Intuicyjnie zatem rozumiemy, że w szczególności relacja jest symetryczna, gdy sens modyfikowanej wypowiedzi się nie zmienia i nie ma wpływu na prawdziwość zdania.
Przechodniość informuje, iż jeżeli jeden element jest w relacji z drugim, a drugi z trzecim, to również pierwszy z trzecim. Formalny zapis przyjmuje postać: xRy ʌ yRz ⇒ xRz dla dowolnych elementów: x, y, z. Powróćmy ponownie do przykładu klasy. Jeżeli uczeń X i Y są w tej samej klasie oraz Y i Z są w tej samej, to wnioskujemy, iż również X i Z są w tej samej klasie. W zbiorze liczb naturalnych własność tę obserwujemy przy nierówności: jeżeli liczba a jest mniejsza od b, liczba b mniejsza od c, to a jest mniejsza od c. Przykładowo: 3<5, 5<10, a zatem 3<10 – relacja jest przechodnia.
Należy nadmienić, co można pojąć w sposób intuicyjny na podstawie przedstawionych przykładów, że relacja jest określonego typu, jeżeli dany warunek jest spełniony dla wszystkich elementów. Jeżeli znajdziemy chociaż jedną parę, która nie spełnia danego warunku, na przykład zwrotności, to nie możemy wtedy powiedzieć, że relacja jest zwrotna.
Relacja posiadająca trzy wymienione wyżej własności pozwala na dzielenie elementów na pewne grupy, które będziemy nazywać klasami abstrakcji – do danej klasy abstrakcji należą elementy, dla których zachodzi dana relacja. Zbiory te są rozłączne – tworzą zamknięte grupy elementów – każdy jest w relacji z innym z klasy abstrakcji i nie jest w relacji z żadnym z innej. Gwarantują to: zwrotność, symetria oraz przechodniość. Załóżmy, że mamy dwie różne klasy abstrakcji, gdzie jeden element z pierwszej klasy abstrakcji jest w relacji z innym elementem w drugiej klasie abstrakcji. Wtedy jednak z przechodniości wszystkie inne elementy z pierwszej klasy abstrakcji wchodzą w relację z tym elementem, a znowu z własności przechodniości wchodzą zatem w relację ze wszystkimi elementami drugiej klasy abstrakcji, a w związku z tym tworzą jedną klasę abstrakcji – stąd widać, iż elementy z danych klas nie mogą być w relacji. Istotnie relacja dotycząca koloru kartek wspomniana w pierwszym akapicie jest relacją równoważności, gdyż dana kartka jest tego samego koloru jak ona sama. Jeżeli jedna kartka jest tego samego koloru jak druga, to analogicznie druga ma taki sam kolor jak pierwsza. Wreszcie, jeżeli pierwsza kartka ma ten sam kolor jak druga, druga jak trzecia, to pierwsza też ma ten sam kolor co trzecia. Klasy abstrakcji pozwalają zgrupować te kartki w oddzielne zbiory kartek różnego koloru. Układamy więc cztery stosy kartek, w których każda jest tego samego koloru co inne w stosie, ale żadna nie jest tego samego koloru co kartka z innego stosu. Skoro klasy te są rozłączne, to nie potrzebujemy porównywać wszystkich elementów. Decydując, na który stos ułożę kartkę, wystarczy, że porówna się ją z jedną kartką z każdego stosu – innymi słowy nie trzeba wiedzieć, iż wszystkie kartki są zielone, żeby ułożyć gdzieś zieloną kartkę – wystarczy jedna zielona kartka leżąca na górze. Nazwiemy ją reprezentantem, gdyż reprezentuje jedną konkretną klasę abstrakcji. Jeżeli kartka jest w relacji z tą kartką, to jest w relacji ze wszystkimi innymi na tym stosie (w tej klasie abstrakcji), a jeżeli nie jest w relacji – to nie jest w relacji również z żadną inną kartką tego stosu.
Klasy abstrakcji mogą być zarówno skończone jak i nieskończone. Ponownie możemy wrócić do przykładu z uczniami. W istocie relacja: XRY X i Y są w tej samej klasie jest relacją równoważności. Każda klasa stanowi zatem (dosłownie) klasę abstrakcji. Pojedyncza osoba jest tutaj reprezentantem. Załóżmy, że do klasy 1 chodzi Jan Nowak. Jest on osobą w szkole bardzo znaną. Widząc go, inni uczniowie od razu wiedzą, do której chodzi klasy oraz kto jest z nim w tej samej klasie. W ten sposób widać uzasadnienie wyróżnienia pewnego elementu – reprezentanta – jest on charakterystyczny i jednoznaczny (zakładając tutaj oczywiście, że do szkoły nie chodzi dwóch Janów Nowaków – każdego Jana Nowaka traktujemy jako jeden element). Klasy abstrakcji tej relacji są skończone, bowiem do każdej klasy chodzi pewna skończona liczba uczniów.
Wiele przykładów pokazało, iż relacje możemy rozszerzać na różne obiekty, które nie muszą być liczbami: uczniowie czy kartki są takimi przykładami. Rozważmy teraz następującą relację w iloczynie kartezjańskim podzbiorów zbioru liczb rzeczywistych: zbiór A jest w relacji ze zbiorem B, gdy A jest równoliczny z B. Jest to relacja równoważności. Każdy zbiór jest równoliczny z samym sobą, jeżeli jeden zbiór ma tyle samo elementów, ile ma drugi zbiór, to symetrycznie drugi zbiór ma tyle samo elementów, ile ma pierwszy zbiór. I wreszcie, jeżeli zbiór A jest równoliczny z B, B równoliczny z C, to A jest równoliczny z C. Klasy abstrakcji grupują zatem zbiory według tego, ile mają elementów, co przedstawiono na schemacie niżej.
Rysunek 2. Klasy abstrakcji relacji równoliczności zbiorów
Oczywiście nie zostały wypisane wszystkie elementy. Samych zbiorów jednoelementowych zawierających kolejne liczby naturalne jest nieskończenie wiele. Podobnie sytuacja wygląda w przypadku większej liczby elementów. Jedynie klasa abstrakcji zbiorów zeroelementowych jest skończona – należy do niej tylko zbiór pusty. Mamy więc do czynienia z nieskończonymi klasami abstrakcji i to w dwojaki sposób: istnieje nieskończenie wiele klasy abstrakcji i w każdej jest nieskończenie wiele zbiorów (poza zbiorem pustym). Reprezentantem klasy abstrakcji zbiorów dwuelementowych może być przykładowo zbiór {1,2}. Mając ten zbiór, jesteśmy w stanie jednoznacznie zinterpretować, do której klasy abstrakcji on należy – zbiorów dwuelementowych. Wiemy też, jakie elementy są z nim w relacji, np. {1,3}, {1,5} czy {-5,2}.
Relacja porządku częściowego i liniowego
Dla celów dalszej analizy zostanie przedstawiony kolejny typ relacji. Powiemy, że relacja jest antysymetryczna, jeżeli z tego, że element x jest w relacji z y i y jest w relacji z x wynika, że te elementy muszą być równe, co zapisujemy w postaci: xRy ʌ yRx ⇒ x=y. Antysymetryczna jest relacja słabej nierówności w zbiorze liczb rzeczywistych, mianowicie własności x≤y oraz y≤x zachodzą dokładnie wtedy, gdy x=y. Antysymetryczna nie będzie natomiast relacja podzielności w zbiorze liczb całkowitych bez zera. Zauważmy, że liczba 3 jest podzielna przez -3, liczba -3 jest podzielna przez 3, ale -3≠3.
Wykorzystamy teraz warunek antysymetryczności oraz zwrotności i przechodniości poznane wcześniej, aby określić nowy typ relacji nazywanej relacją częściowego porządku. Zgodnie z nazwą, wymienione własności pozwalają na ustalenie pewnego porządku (potocznie: określenie, który element jest mniejszy, a który większy). Częściowość oznacza, iż możemy utworzyć pewne różne od siebie „szeregi” elementów będących ze sobą w relacji (to znaczy wszystkie elementy takiego „szeregu” są ze sobą porównywalne), które nazywać będziemy łańcuchami. Relację częściowego porządku stanowi inkluzja określona na pewnym niepustym zbiorze X. Zauważmy, że dowolny zbiór A zawiera się w A, Jeżeli A zawiera się w B i B zawiera się w A, to zbiory te są równe oraz jeżeli A zawiera się w B, B zawiera się w C, to A zawiera się w C. Zbiory w tej przestrzeni można ustawić w pewnej kolejności – to znaczy kolejności względem zawierania. Rozważmy zbiory w przestrzeni X przedstawionej niżej z relacją inkluzji.
Rysunek 3. Przestrzeń częściowo uporządkowana X
Zauważmy, iż relację zawierania można przedstawić za pomocą prostego schematu:
Rysunek 4. Łańcuchy przestrzeni częściowo uporządkowanej X
Ten uproszczony schemat pozwala na kilka trafnych obserwacji dotyczących relacji częściowego porządku. Przede wszystkim nie wszystkie elementy są porównywalne. Zbiór H nie zawiera się w zbiorze A ani zbiór A nie zawiera się w zbiorze H. Elementy tworzą z tego powodu wiele łańcuchów, przykładowo: zbiór pusty – B – A – X.
W tej przestrzeni względem relacji inkluzji elementem najmniejszym jest zbiór pusty, który zawiera się w każdym zbiorze, a elementem największym jest zbiór X, w którym zawiera się każdy zbiór tej przestrzeni. Elementy najmniejsze i największe nie muszą istnieć, ale jeżeli istnieją, to są wyznaczone jednoznacznie – są jedyne. W tym przypadku istnieją elementy najmniejszy i największy, jednak nie musi tak być. Łańcuchy mogą rozpoczynać się i kończyć na różnych elementach – określamy je wtedy jako odpowiednio elementy minimalne i maksymalne (może ich być wiele). Przyjrzyjmy się następującej hipotetycznej sytuacji:
Rysunek 5. Przykład pewnej relacji elementów w pewnej przestrzeni
W zbiorze tym nie można określić elementu najmniejszego ani największego. Są za to elementy minimalne: Q, W, M oraz elementy maksymalne: R, U, V. Jeżeli istnieje element najmniejszy, to dodatkowo mówimy, iż dana przestrzeń jest dobrze uporządkowana. Podany zbiór X z relacją inkluzji stanowi zatem przykład przestrzeni dobrze uporządkowanej.
W przypadku relacji częściowego porządku wyróżniamy również przestrzeń uporządkowaną w sposób gęsty. Mianowicie jeżeli jeden element jest w relacji z drugim, to zawsze istnieje trzeci element taki, iż pierwszym jest z nim w relacji, a on sam jest w relacji z drugim. Przestrzenią taką jest przykładowo zbiór liczb wymiernych z relacją słabej nierówności. Pomiędzy dwoma liczbami wymiernymi zawsze istnieje pewna liczba wymierna – wystarczy chociażby przyjąć średnią z tych dwóch liczb, która oczywiście będzie również liczbą wymierną i będzie znajdować się między obiema liczbami.
Istnieje typ relacji, w której każde dwa elementy są ze sobą porównywalne. Ta własność jest zapewniona wtedy, gdy relacja jest spójna, to znaczy zawsze jeden element jest w relacji z drugim lub drugim z pierwszym, innymi słowy: xRy v yRx. Jeżeli relacja częściowego porządku jest dodatkowo spójna, to nazywamy ją relacją liniowego porządku, gdyż otrzymujemy wyłącznie jeden łańcuch – w końcu wszystkie elementy możemy porównać i w pewien sposób „uszeregować”.
By lepiej zobrazować istotę spójności, spróbujmy skonstruować łańcuch liczb całkowitych sortując kolejne losowo wybrane elementy. Określmy zatem na zbiorze liczb całkowitych relację słabej nierówności: ≤. Jest to relacja liniowego porządku – jest zwrotna: x≤x, antysymetryczna: x≤y ʌ y≤x ⇒ x=y, przechodnia: x≤y ʌ y≤z ⇒ x≤z oraz spójna: x≤y v y≤x.
Krok 1: weźmy element 0. Od teraz jeżeli element x jest w relacji z elementem y, to kładziemy go po lewej stronie elementu y. Jeżeli to element y jest w relacji z x, to element x kładziemy po prawej stronie. Sytuację, gdy zachodzą obie relacje pomijamy – to zachodzi wtedy, gdy liczby są równe (antysymetria).
Krok 2: Bierzemy losowy element – niech będzie to liczba 5. 5 nie jest w relacji z 0 (to znaczy nieprawda, że 5≤0). Jednak 0 jest w relacji z 5, zatem kładziemy 5 po prawej stronie.
Dalsze kroki: Bierzemy losowy element i powtarzamy procedurę. Niech będą to elementy -3, 2 i 7. -3R0, zatem -3 znajduje się po lewej stronie od 0. Nie musimy już sprawdzać, czy na pewno zachodzi -3R5 i czy -3 jest po lewej stronie od liczby 5 – to wynika bezpośrednio z przechodniości relacji. 0R2 i 0R7, zatem 2 i 7 są po prawej stronie. Teraz 2R5 – 2 jest po lewej stronie od 5, a to oznacza koniec porównań. 5R7, zatem 7 jest po prawej stronie od liczby 5 i ponownie kończą się możliwości porównań.
Oczywiście nie jesteśmy w stanie w ten sposób utworzyć zbioru liczb całkowitych – jest ich w końcu nieskończenie wiele i otrzymujemy nieskończony łańcuch, dodatkowo bez elementu najmniejszego lub największego, nie ma też elementów minimalnych ani maksymalnych. Należy zauważyć jednak, iż każdą liczbę można porównać z inną i dzięki temu „znaleźć jej miejsce w szeregu”. Porządek jest liniowy – istotnie otrzymujemy swego rodzaju linię, pewną kolejność elementów od najmniejszego do największego. Co więcej, gdyby istniały elementy minimalne i maksymalne, to byłyby one jedyne – bo istnieje tylko jeden łańcuch, a zatem byłyby to elementy odpowiednio najmniejszy i największy.
Bibliografia
- Trzęsicki, Elementy logiki i teorii mnogości, 2006, wyd. II, wersja elektroniczna
Autor: Michał Walter, Uniwersytet Jagielloński, Wydział Matematyki i Informatyki
