Para uporządkowana

Bardzo często będziemy chcieli mieć do czynienia ze zbiorem, który niesie w sobie informację o dwóch innych zbiorach, informację tak trafnie zakodowaną,
aby można było odzyskać z niej każdą z jego składowych. Do tego celu wprowadzimy zbiór nazywany parą uporządkowaną dwóch innych zbiorów.

D

EFINICJA

1.1.

Niech oraz

będą zbiorami. Przez parę uporządkowaną

rozumiemy zbiór

Parę uporządkowaną można zdefiniować inaczej na wiele sposobów. Chodzi jednak o to, aby ze zbioru, który jest parą, można było odzyskać jednoznacznie
każdą z jego składowych. Tak więc moglibyśmy zaakceptować każdą

inn

ą inną definicję pod warunkiem, że będzie spełnione następujące twierdzenie:

T

WIERDZENIE

1.2.

Dla dowolnych zbiorów

zachodzi:

D

OWÓD

Dowód przeprowadzimy tylko ze

strony

lewej do prawej, bo w odwrotnym kierunku jest to fakt oczywisty. Niech zatem dwie pary

i

będą równe.

Ponieważ

, więc

. Mamy zatem

lub

. W pierwszym przypadku

,

ale

w drugim również jest

tak, mamy bowiem, że

. Pierwszą część twierdzenia mamy za sobą, bo już wiemy, że pierwsze współrzędne równych par są równe.

Następnie przeprowadzamy dowód przez przypadki. Jeżeli jest tak, że

, to

. Zatem

, co daje,

że

, a zatem

. W przeciwnym przypadku, gdy

mamy, że

. Daje to dwie

możliwoś

ci

albo

, co nie może mieć miejsca, bo mielibyśmy, że

albo zaś

. To drugie prowadzi do naszej

tezy

.

Ć

WICZENIE

1.3

Dla każdej pary

udowodnij, że

R

OZWIĄZANIE

Rozważymy dwa przypadki.

1.

Jeśli

, to

i wtedy

.

2.

Jeśli

, to

a więc

skąd otrzymujemy

Ć

WICZENIE

1.4

Udowodnij, że dla dowolnej pary uporządkowanej zbiór

jest pusty, gdy współrzędne par są różne, a w przeciwnym przypadku jest zbiorem jednoelementowym zawierającym współrzędną pary .

R

OZWIĄZANIE

Jeśli jest parą, to istnieją zbiory

takie, że

.

1. Przypuśćmy, że

. Wtedy

i

. Ponieważ

to

, a wtedy

gdyż przecinany zbiór zawiera elementy rozłączne

. Wobec tego również

2. W przypadku, gdy

, otrzymujemy

, a więc

i wtedy

skąd otrzymujemy

Ć

WICZENIE

1.5

Poka

ż, że z każdej pary można otrzymać jej drugą współrzędną, posługując się jedynie parą , mnogościowymi operacjami

oraz

stałą .
W

SKAZÓWKA

1.

Rozważ najpierw pary różnych elementów.

2.

Wykorzystaj zbiór z Ćwiczenia 1.4 (patrz

ćwiczenie 1.4

) .

R

OZWIĄZANIE

Rozważmy najpierw przypadek, gdy para ma różne elementy. Zobaczymy, że dla każdej takiej pary

, mamy

Ponieważ

, to

i wtedy

Zobaczmy teraz, jak proponowany wzór działa na parach o równych współrzędnych. Jeśli

, to

i wtedy

Musimy więc jeszcze trochę popracować. Wykorzystajmy ćwiczenie 1.4 (patrz

ćwiczenie 1.4

), niech nowy wzór będzie postaci

Dla par o różnych elementach dodana część wzoru jest zbiorem pustym, więc ta sytuacja jest analogiczna do 1.1, skąd otrzymujemy, że tak zdefiniowany
zbiór jest równy .

Dla par o równych elementach pierwsza część zbioru jest zbiorem pustym. W ćwiczeniu 1.4 (patrz

ćwiczenie 1.4

) pokazaliśmy, że w takim przypadku

mamy

, jeśli jest współrzędną pary . Wobec tego

Iloczyn kartezjański

Zanim wprowadzimy definicję zbioru wszystkich par uporządkowanych elementów dwóch zbiorów (zwanego dalej iloczynem kartezjańskim), należy nam się

krótkie wprowadzenie. Otóż niech

oraz

. Łatwo zauważyć, że zarówno

, jak i

są podzbiorami

.

Zatem

oraz

. Więc

, co daje,

że

.

Istnienie i konstrukcja iloczynu kartezjańskiego zostało dokładnie omówione w dodatkowym rozdziale

"Iloczyn kartezjański i aksjomat wyróżniania"

.

Proponuję przestudiowanie dodatkowego rozdziału dopiero po zapoznaniu się z rozdziałami wcześniejszymi, pomimo braku precyzji w następnej definicji.

D

EFINICJA

2.1.

Niech

będą zbiorami. Iloczynem kartezjańskim (produktem)

nazywamy zbiór

Będziemy używać specjalnej notacji

na zbiór

.

Ć

WICZENIE

2.2

Pokaż następujące elementarne własności iloczynu kartezjańskiego:

R

OZWIĄZANIE

[

SCHOWAJ

]

Z definicji iloczynu kartezjańskiego oraz twierdzenia 1.2 (patrz

twierdzenie 1.2.

) w sposób oczywisty wynika

następujący fakt, który wykorzystamy w dowodach. Dla dowolnych zbiorów

zachodzi

1.

Ponieważ

jest zawsze fałszem, to powyższy zbiór jest pusty.

2. Ponieważ obydwa zbiory są zbiorami par, więc wykażemy, że dowolna para należy do jednego

wtedy i tylko wtedy, gdy należy do drugiego. Weźmy dowolną parę

, wtedy

3. A

nalogicznie do poprzedniego punktu, weźmy dowolną parę

, wtedy

4. Analogicznie do poprzednich punktów, weźmy dowolną parę

, wtedy

Ć

WICZENIE

2.3

Produkt kartezjań

ski

jest monotoniczny ze względu na każdą współrzędną osobno, to znaczy:

R

OZWIĄZANIE

[

SCHOWAJ

]

1.

Niech

będą dowolnymi zbiorami takimi, że

. Wtedy dla dowolnej pary

mamy

Stąd

.

1.

Dla dowolnych zbiorów

mamy

. Z poprzedniego

ćwiczenia otrzymujemy

(Metoda z poprzedniego punktu podziała równie dobrze.)

Ć

WICZENIE

2.4

Sprawdź, czy dla dowolnych zbiorów

, prawdziwa jest następująca implikacja:

R

OZWIĄZANIE

[

SCHOWAJ

]

Nie. Na przykład, gdy

, to dla dowolnych zbiorów

mamy

Biorąc różne zbiory

, otrzymamy kon

trprzykład dla badanej implikacji.

Relacje

D

EFINICJA

3.1.

Relacją nazywamy każdy podzbiór iloczynu

.

[

Edytuj

]

Operacje na relacjach:

D

EFINICJA

3.2.

Niech

oraz

.

Ć

WICZENIE

3.3

Niech relacja

oraz

. Pokazać elementarne własności operacji na relacjach:

R

OZWIĄZANIE

[

SCHOWAJ

]

1.

2.

3.

4.

5. Dowód

jest analogiczny do poprzedniego.

6.

Ć

WICZENIE

3.4

Niech relacja

oraz

. Pokaż własności:

R

OZWIĄZANIE

[

SCHOWAJ

]

W poniższych punktach (1-4) pokażemy, że dowolna para należy do zbioru po lewej

stronie odpowiedniej równości wtedy i tylko wtedy, gdy należy do prawej. W punkcie 5, pokazujemy jedynie implikację w prawą stronę, gdyż mamy udowodnić
inkluzję.

1.

2. Dowód drugiej równości jest analogiczny do dowodu pierwszej, wystarczy użyć

w miejsce

oraz

w miejsce

.

3.

4.

5.

Ć

WICZENIE

3.5

Podaj przykład relacji, dla których poniższa równość nie jest prawdziwa.

R

OZWIĄZANIE

[

SCHOWAJ

]

Niech

, wtedy

1.

, więc

.

2.

i

, a więc

Ć

WICZENIE

3.6

Udowodnij, że zbiór

jest relacją wtedy i tylko wtedy, gdy

R

OZWIĄZANIE

[

SCHOWAJ

]

Pokażemy najpierw, że dla każdej relacji

mamy

Zaczniemy od inkluzji

. Weźmy dowolny element

, wtedy musi istnieć element

taki, że

. Skoro

,

to musi istnieć para

taka, że

. Wobec tego z definicji pary uporządkowanej

lub

.

Poniew

aż

, to

i wtedy

lub

i wtedy

. Wobec tego

.

Pokażemy teraz prawdziwość inkluzji

w równaniu 3.12. Weźmy dowolny element

wtedy istnieje element

taki, że

,

a więc

. Stąd otrzymujemy

Ponieważ

, to otrzymujemy

, a więc

. Analogiczne rozumow

anie można

przeprowadzić dla elementu

. Zakończyliśmy więc dowód równości 3.12.

W temacie ćwiczenia implikacja w lewą stronę jest oczywista. Jeśli

jest zbiorem, to

jest zbiorem i

jest podzbiorem iloczynu kartezjańskiego

dwóch zbiorów, więc musi być relacją. Dla implikacji w prawą stronę załóżmy, że

jest relacją, wtedy

Relacje równoważności

W tym podrozdziale poznamy ważną klasę (zbiór) relacji zwaną klasą relacji równoważności(w innych podręcznikach mogą się państwo spotkać z nazwą
r

elacja abstrakcji). Relacje takie będą służyły do definiowania pojęć abstrakcyjnych, o czym przekonamy się w wielu miejscach tego i innych wykładów.

Bardzo dobrym ćwiczeniem pokazującym abstrakcyjne metody definiowania pojęć będzie

wykład 8

, w którym zaprzęgniemy relacje abstrakcji do definiowania

liczb.

Rozpoczynamy rozdział od koniecznej definicji.

D

EFINICJA

4.1.

Dla zbioru

definiujemy relację

jako

.

D

EFINICJA

4.2.

Relację

nazywamy relacją równoważnością o polu

, jeżeli:



zawiera relacje

(zwrotność

),



(symetria

),



(przechodniość

).

Ć

WICZENIE

4.3

Pokazać, że definicje zwrotności, symetryczności i przechodniości relacji o polu

są odpowiednio równoważne następującym własnościom:



,



,



.

R

OZWIĄZANIE

[

SCHOWAJ

]

Ćwiczenie jest elementarne.

D

EFINICJA

4.4.

Niech

będzie relacją równoważności o polu

. Klasą równoważności elementu

jest zbiór

D

EFINICJA

4.5.

Zbiór klas równoważności relacji

będący elementem zbioru

oznaczamy przez

.

T

WIERDZENIE

4.6.

Niech

będzie relacją równoważności o polu

. Następujące warunki są równoważne:

1.

,

2.

,

3.

.

D

OWÓD

Pokażemy, że

. Niech wspólny element dwóch klas

oraz

nazywa się . Ze względu na pełną symetrię tezy wystarczy pokazać,

że

. Niech zatem

. Mamy więc

. Z założenia jest również

oraz

. Z symetrii

otrzymujemy

. Zatem

i

i

. Natychmiast z przechodniości otrzymujemy, że

.

Pokażemy, że

. Ze zwrotności mamy, że

, co z założenia

daje

, a to tłumaczy się na

.

Pokażemy, że

. Wystarczy pokazać, że wspólnym elementem klas

oraz

jest

. Dla pierwszej z nich wynika to z założenia

,

a dla drugiej ze zwrotności

.

W nas

tępnym twierdzeniu zobaczymy, jak rodzina relacji równoważności jest odporna na przecinanie. Pokażemy mianowicie, że przecięcie dowolnej liczby

relacji równoważności jest nadal relacją równoważności.

T

WIERDZENIE

4.7.

Niech

będzie pewną rodziną (zbiorem) relacji równoważności o tym samym polu

. Mamy że:

1.

jest relacją równoważności o polu

,

2.

.

D

OWÓD

Zwrotność

jest oczywista, ponieważ

zawiera się w każdej relacji rodziny . Symetria. Weźmy

. Dla każdej

relacji

jest

. Z symetrii każdej

jest więc

, co daje

. Przechodniość.

Niech

oraz

. Dla każdej relacji

jest więc

i

. Z przechodniości każdej

relacji

mamy, że

, co daje

.

Niech

. Mamy zatem, że

, co daje

dla każdej relacji

. To zaś daje, że

dla

każdej

, co jest równoważne z

.

W szczególności przecięcie wszystkich relacji równoważności o polu

daje

. Jest ona najsilniejszą relacją równoważności. Najsłabszą jest

.

Rozkłady zbiorów

D

EFINICJA

4.8.

Niech

. Rodzinę

nazywamy rozkładem zbioru

, gdy:

1.

,

2.

,

3.

.

L

EMAT

4.9.

Dla

relacji równoważności

o polu

zbiór

jest rozkładem

.

D

OWÓD

Każda klasa jest niepusta, bo zawiera element, który ją wyznacza.

, bo każda klasa jest podzbiorem

. Odwrotnie

każdy

.

Dwie klasy, gdy są różne, muszą być rozłączne co udowodniliśmy w twierdzeniu 4.6 (patrz

twierdzenie 4.6.

).

D

EFINICJA

4.10.

Niech

będzie rozkładem zbioru

. Definiujemy relacje

następująco:

wtw

L

EMAT

4.11.

Dla rozkładu

relacja

jest:

1.

równoważnością,

2.

D

OWÓD

Relacja

jest zwrotna, każdy bowiem

musi leżeć w pewnym zbiorze

rozkładu . Symetria

nie wymaga dowodu.

Przechodniość

. Niech

i

. Istnieją zatem dwa zbiory

i

rozkładu takie, że

oraz

.

Przeci

ęcie

i

jest więc niepuste, zatem

, co daje tezę

.

Inkluzja w prawo

. Niech

. Klasa

jest zatem wyznaczona przez pewien element

taki, że

. Niech

będzie zbiorem rozkładu , do którego należy . Łatwo wykazać, że

. Inkluzja w lewo

. Niech

.

jest niepusty, więc

istnieje

. Klasa

.

Ć

WICZENIE

4.12

Niech

będzie niepustym zbiorem oraz niech

. Zdefiniujemy relację

następująco: dla dowolnych

zbiorów

mamy

(

oznacza różnicę symetryczną zbiorów, czyli

). Udowodnij, że relacja

jest rel

acją równoważności.

W

SKAZÓWKA

[

SCHOWAJ

]

Najtrudniej jest pokazać przechodniość. Udowodnij, że

. Dobrym punktem wyjścia jest naszkicowanie wszystkich

przecięć zbiorów

.

R

OZWIĄZANIE

[

SCHOWAJ

]

Pokażemy po kolei zwrotność, przechodniość i symetryczność.

1.

Dla każdego

mamy

, a więc relacja

jest zwrotna.

2.

Ponieważ dla dowolnych zbiorów

, to

wtedy i tylko wtedy, gdy

. Wobec tego

relacja

jest symetryczna.

3.

Weźmy zbiory

, takie

że

. Wtedy

Ponieważ z definicji relacji

mamy

oraz

, to ich suma też jest podzbiorem

i w konsekwencji

również

. Oznacza to, że

, a więc relacja

jest przechodnia.

Ć

WICZENIE

4.13

Udowodnij, że dla relacji równoważności

na zbiorze

, relacja

jest relacją równoważności wtedy i tylko wtedy, gdy

Podaj przykłady relacji równoważności

takich, że

jest relacją równoważności oraz

i

.

W

SKAZÓWKA

[

SCHOWAJ

]

Przyjrzyj się dokładnie rodzinie zbiorów

.

R

OZWI

ĄZANIE

[

SCHOWAJ

]

Zaczniemy od pokazania, że formuła 4.1 implikuje, iż relacja

jest relacją równoważności. Pokażemy, że

rodzina

tworzy rozkład zbioru

. Oczywiście, dla każdego elementu

mamy

oraz

. Wystarczy

więc pokazać, że zbiory w rodzinie

są rozłączne. Weźmy dowolne dwa elementy rodziny

i przypuśćmy, że

ich przecięcie jest niepuste. Niech to będą zbiory odpowiadające elementom

, a więc

oraz

. Skoro te zbiory

mają niepuste przecięcie, to istnieje

.

Ponieważ

, to

,

co jest równoważne

. Podobne rozumowanie dla

daje

. Wobec czego

dostajemy

, ponieważ jednak zgodnie z formułą 4.1 jedna z tych klas jest nadzbiorem drugiej, to

lub

. W przypadku, gdy

, dostajemy również z 4.1.

oraz

, wobec

czego otrzymujemy

. Drugi przypadek jest analogiczny. Wobec czego rodzina

jest rozkładem

zbioru

. Wystarczy teraz przekonać się, że

wtedy i tylko wtedy, gdy

, aby udowodnić, że jest to rzeczywiście

rozkład generowany przez relację

. Weźmy dowolne

, wtedy

Pokażemy teraz, że jeśli

jest relacją równoważności, to musi być spełniona formuła 4.1. Dla dowodu niewprost przypuśćmy, że nie jest spełniona.

Oznacza to, że istnieje element

, dla którego

oraz

. Wobec tego istnieje

oraz

. Oznacza to, że

oraz

. Skoro

jest relacją równoważności,

to

. Przypuśćmy, że

. Wtedy

, wobec czego

, co jest sprzeczne z tym,

że

, ponieważ relacja

jest symetryczna. Analogiczną sprzeczność otrzymujemy dla

. Obie możliwości prowadzą do

sprzeczności, a więc formuła 4.1 musi być spełniona.

Na koniec podajemy przykład relacji równoważności, równoważności

takich, że

jest relacją równoważności oraz

i

.

Polem relacji będzie zbiór

. Relacje

określimy poprzez wyznaczane przez nie rozkłady odpowiednio

:

Łatwo sprawdzić, że

i

, gdyż

oraz

. Z rozkładów

w prosty sposób wynika, że formuła

4.1 jest prawdziwa dla tych relacji, wobec czego

jest relacją równoważności. Wyznaczany przez nią rozkład to

.

Domykanie relacji

W praktyce matematycznej często potrzebne jest rozważanie domknięć relacji ze względu na wiele przeróżnych własności. W podrozdziale tym dokonamy
charakteryzacji domknięć. Pokażemy między innymi, kiedy takie domykanie jest możliwe.

D

EFINICJA

4.14.

Niech

będzie rodziną relacji o polu

, czyli niech

. Rodzina

jest zamknięta na przecięcia, gdy:

1.

2.

jeżeli

to

Poniżej podamy definicję domknięcia relacji w pewnej klasie (zbiorze) relacji. Definiujemy intuicyjnie najmniejszą relację zawierającą daną należącą do klasy.

D

EFINICJA

4.15.

Relacja

jest domknięciem relacji

w klasie (zbiorze) relacji

gdy:

1.

2.

3.

dla każdej relacji

jeżeli

oraz

to

L

EMAT

4.16.

Domknięcie relacji (w dowolnej klasie), jeżeli istnieje, to jest jedyne.

D

OWÓD

Gdyby istniały dwa domknięcia pewnej relacji, to ze względu na warunek

wzajemnie by się zawierały.

T

WIERDZENIE

4.17.

Następujące warunki są równoważne:

1.

Klasa relacji

jest domknięta na przecięcia.

2.

Każda relacja ma domknięcie w klasie relacji

.

D

OWÓD

. Niech

będzie relacją. Utwórzmy zbiór relacji

jako

. Takie

nie jest puste, bowiem

relacja totalna

należy do

. Pokażmy, że

jest domknięciem

w

. Istotnie

. Z założenia mamy też

.

Minimalność

stwierdzamy przez: niech

takie że

. Takie

musi leżeć w zbiorze

, jest więc

.

. Po pierwsze

leży w zbiorze

, bo wystarczy domknąć

. Niech

będzie niepustym podzbiorem

. Niech

będzie

domknięciem

w

. Wiemy, że dla dowolnej relacji

, o ile

i

to

. Połóżmy za

dowolny element z

.

Założenia implikacji pozostają automatycznie spełnione, jest więc tak, że

dla dowolnej

wyjętej z

. W takim razie

.

Ponieważ mamy też

, bo

było domknięciem, jest więc

, a to oznacza, że

.

Ć

WICZENIE

4.18

Pokazać jak wyglądają domknięcia w klasie relacji, zwrotnych, symetrycznych i przechodnich.

Pokaz

ać, stosując twierdzenie 4.17 (patrz

twierdzenie 4.17.

), że nie istnieje domknięcie spójne ani antysymetryczne. (Relacja

jest spójna,

gdy

. Relacja

jest antysymetryczna, gdy z faktu, że

oraz

, da się pokazać,

że

).

R

OZWIĄZANIE

[

SCHOWAJ

]

1. Pokażemy, że dla każdej relacji

jej domknięcie w klasie relacji zwrotnych na

to

. Pokażemy po kolei, że spełnia warunki

domknięcia:

(a)

(b)

, a więc jest zwrotna,

(c) weźmy dowolną zwrotną relację

. Ponieważ

jest zwrotna to

, a więc

.

2. Pokażemy, że dla każdej relacji

jej domknięcie w klasie relacji symetrycznych na

to

. Pokażemy po kolei, że spełnia

warunki domknięcia:

(a)

(b)

, a więc jest symetryczna ,

(c) weźmy dowolną symetryczną relację

. Ponieważ

jest symetryczna to

. Skoro

to

.

Ponieważ

, to

.

3 Posługując się intuicyjnym pojęciem liczb naturalnych, przedstawimy szkic konstrukcji przechodniego domknięcia, pomimo że konstrukcja ta wyprzedza

prezentowany mate

riał. Dla dowolnej liczby

przez

będziemy oznaczać

-

krotne złożenie relacji

z sobą (czyli

oraz

dla

). Zdefiniujmy rodzinę

jako zbiór wszystkich skończonych wielokrotnych złożeń relacji

z sobą,

czyli

. Do formalnego zdefiniowania rodziny

p

otrzebne są pojęcia liczb naturalnych,

funkcji oraz definiowania przez indukcje, które zostaną przedstawione w następnych rozdziałach. Pokażemy teraz, że domknięcie relacji

w klasie relacji

przechodnich na

to relacja

. Pokażemy po kolei, że spełnia warunki domknięcia:

(a)

(b) Aby pokazać, że relacja

jest przechodnia, weźmy dowolne dwie pary

. Wtedy muszą istnieć

liczby

takie, że

oraz

. Wobec tego

. Z łączności składania relacji

wynika, że

. Wobec tego

.

(c) Weźmy dowolną przechodnią relację

taką, że

, pokażemy indukcyjnie, że dla każdego

mamy

.

i. Baza indukcji. Dla

mamy

, a więc z założenia

.

ii. Krok indukcyjny. Weźmy dowolne

i przypuśćmy, że dla każdego

zachodzi

. Weźmy

dowolną parę

. Ponieważ

, to

. Oznacza to, że istnieje element

taki,

że

oraz

. Z założenia indukcyjnego wynika, że

oraz

. Ponieważ

jest

przechodnia to

. Wobec dowolności wyboru pary

otrzymujemy

.

Skoro dla każdego

mamy

, to również

.

Pokażemy teraz, że istnieje zbiór

taki, że klasa relacji spójnych na zbiorze

i

klasa relacji symetrycznych na zbiorze

nie są domknięte na przecięcia. W obliczu Twierdzenia 4.17 (patrz

Twierdzenie 4.17.

) będzie to oznaczało, że nie

wszystkie relacje mają domknięcia w tych klasach. Niech

.

1.

Relacje

są spójne na

, a ich przecięcie, czyli

zbiór

, nie jest.

2.

Relacja

nie jest antysymetryczna, a więc klasa relacji antysymetrycznych na

nie jest domknięta na przecięcia.

Ć

WICZENIE

4.19

Dla relacji

niech

,

,

oznaczają odpowiednio zwrotne, symetryczne, przechodnie domknięcie relacji

. Czy prawdą jest, że:

1.

dla dowolnej relacji

relacja

jest relacją równoważności,

2.

dla dowolnej relacji

zachodzi

W każdym z powyższych przypadków proszę podać dowód lub kontrprzykład.

R

OZ

WIĄZANIE

[

SCHOWAJ

]

1. Zaczniemy od pokazania, że dowolne domknięcie relacji zwrotnej jest zwrotne. Rozważamy relacje na zbiorze

. Z definicji zwrotności mamy,

jest

zwrotna wtedy i tylko wtedy gdy

. W definicji do

mknięcia 4.15 (patrz

Definicja 4.15.

) punkt pierwszy mówi, że jeśli

jest domknięciem

to

. Wobec tego konieczne jest, aby

. Zwróćmy uwagę, że powyższy argument działa dla dowolnych klas rodzin relacji domkniętych na

przecięcia. Stąd otrzymujemy, że symetryczne domknięcie relacji zwrotnej jest zwrotne, i przechodnie domknięcie relacji zwrotnej jest zwrotne. Ponieważ

relacja

jest zwrotna, to również zwrotna musi być

. Pokażemy teraz, że przechodnie domknięcie relacji symetrycznej jest symetryczne.

Wykorzystamy charakteryzację domknięcia przechodniego z ćwiczenia 4.18 (patrz

ćwiczenie 4.18.

). Można łatwo pokazać indukcyjnie, że dla

dowolnego

mamy

. Dla relacji symetrycznych dostajemy więc

. Wobec tego mamy:

a więc przechodnie domknięcie relacji symetrycznej jest symetryczne. Oznacza to, że relacja

jest symetryczna. Wcześniej pokazaliśmy, że

jest zwrotna. Ponieważ jest przechodnim domknięciem, to jest też przechodnia. Wobec tego jest relacją równoważności. 2. Pokażemy relację

, dla której

relacja

nie jest przechodnia. Ponieważ relacja

jest przechodnia, będzie to oznaczało, że te relacje są różne.

Niech

oraz

. Relacja

jest przechodnia, więc

; jej symetryczne domknięcie

to

. I po zwr

otnym domknięciu

otrzymujemy

. Łatwo zauważyć, że otrzymana relacja nie jest

przechodnia, gdyż

, podczas gdy

.