plik

Logika i teoria mnogości/Wykład 5: Para
uporządkowana, iloczyn kartezjański, relacje,
domykanie relacji, relacja równoważności, rozkłady
zbiorów

From Studia Informatyczne

< Logika i teoria mnogości

Spis treści

1  Para uporządkowana
2  Iloczyn kartezjański
3  Relacje

3.1 Operacje na relacjach:

4 Relacje równoważności

4.1 Rozkłady zbiorów
4.2 Domykanie relacji

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.

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:

WIERDZENIE

1.2.

Dla dowolnych zbiorów

zachodzi:

OWÓD

Dowód przeprowadzimy tylko ze strony lewej do prawej, bo w odwrotnym kierunku jest to fakt oczywisty. Niech
zatem dwie pary

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.

Logika i teoria mnogości/Wykład 5: Para uporządkowana, iloczyn kart...

http://wazniak.mimuw.edu.pl/index.php?title=Logika_i_teoria_mnogoś...

1 of 8

2012-03-28 17:45

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

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 .

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łą .

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.

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:

Logika i teoria mnogości/Wykład 5: Para uporządkowana, iloczyn kart...

http://wazniak.mimuw.edu.pl/index.php?title=Logika_i_teoria_mnogoś...

2 of 8

2012-03-28 17:45

WICZENIE

2.3

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

WICZENIE

2.4

Sprawdź, czy dla dowolnych zbiorów

, prawdziwa jest następująca implikacja:

Relacje

EFINICJA

3.1.

Relacją nazywamy każdy podzbiór iloczynu

Operacje na relacjach:

EFINICJA

3.2.

Niech

oraz

WICZENIE

3.3

Niech relacja

oraz

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

WICZENIE

3.4

Niech relacja

oraz

. Pokaż własności:

WICZENIE

3.5

Logika i teoria mnogości/Wykład 5: Para uporządkowana, iloczyn kart...

http://wazniak.mimuw.edu.pl/index.php?title=Logika_i_teoria_mnogoś...

3 of 8

2012-03-28 17:45

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

WICZENIE

3.6

Udowodnij, że zbiór jest relacją wtedy i tylko wtedy, gdy

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ą relacja 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.

EFINICJA

4.1.

Dla zbioru definiujemy relację

jako

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:

EFINICJA

4.4.

Niech będzie relacją równoważności o polu . Klasą równoważności elementu

jest zbiór

EFINICJA

4.5.

Zbiór klas równoważności relacji będący elementem zbioru

oznaczamy przez

WIERDZENIE

4.6.

Niech będzie relacją równoważności o polu . Następujące warunki są równoważne:

Logika i teoria mnogości/Wykład 5: Para uporządkowana, iloczyn kart...

http://wazniak.mimuw.edu.pl/index.php?title=Logika_i_teoria_mnogoś...

4 of 8

2012-03-28 17:45

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

. 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 nastę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.

WIERDZENIE

4.7.

Niech

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

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

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

. 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

EFINICJA

4.8.

Niech

. Rodzinę

nazywamy rozkładem zbioru , gdy:

EMAT

4.9.

Logika i teoria mnogości/Wykład 5: Para uporządkowana, iloczyn kart...

http://wazniak.mimuw.edu.pl/index.php?title=Logika_i_teoria_mnogoś...

5 of 8

2012-03-28 17:45

Dla relacji równoważności o polu zbiór

jest rozkładem .

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.).

EFINICJA

4.10.

Niech będzie rozkładem zbioru . Definiujemy relacje

następująco:

wtw

EMAT

4.11.

Dla rozkładu

relacja

jest:

równoważnością,

1.
2.

OWÓD

Relacja

jest zwrotna, każdy bowiem

musi leżeć w pewnym zbiorze rozkładu . Symetria

nie

wymaga dowodu. Przechodniość

. Niech

. 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

relacją równoważności.

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

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.

Logika i teoria mnogości/Wykład 5: Para uporządkowana, iloczyn kart...

http://wazniak.mimuw.edu.pl/index.php?title=Logika_i_teoria_mnogoś...

6 of 8

2012-03-28 17:45

EFINICJA

4.14.

Niech będzie rodziną relacji o polu , czyli niech

. Rodzina jest zamknięta na przecięcia, gdy:

jeżeli

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

EFINICJA

4.15.

Relacja

jest domknięciem relacji

w klasie (zbiorze) relacji gdy:

1.
2.

dla każdej relacji jeżeli

oraz

EMAT

4.16.

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

OWÓD

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

wzajemnie by się zawierały.

WIERDZENIE

4.17.

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

Klasa relacji jest domknięta na przecięcia.

Każda relacja ma domknięcie w klasie relacji .

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

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.

Pokazać, 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

Logika i teoria mnogości/Wykład 5: Para uporządkowana, iloczyn kart...

http://wazniak.mimuw.edu.pl/index.php?title=Logika_i_teoria_mnogoś...

7 of 8

2012-03-28 17:45

oraz

, da się pokazać, że

WICZENIE

4.19

Dla relacji niech

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

Czy prawdą jest, że:

dla dowolnej relacji relacja

jest relacją równoważności,

dla dowolnej relacji zachodzi

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

Źródło: "http://wazniak.mimuw.edu.pl/index.php?title=Logika_i_teoria_mnogo%C5%9Bci/Wyk%C5
%82ad_5:_Para_uporz%C4%85dkowana%2C_iloczyn_kartezja
%C5%84ski%2C_relacje%2C_domykanie_relacji%2C_relacja_r%C3%B3wnowa%C5%BCno%C5%9Bci%2C_rozk
%C5%82ady_zbior%C3%B3w"

Tę stronę ostatnio zmodyfikowano o 19:48, 16 wrz 2006;

Logika i teoria mnogości/Wykład 5: Para uporządkowana, iloczyn kart...

http://wazniak.mimuw.edu.pl/index.php?title=Logika_i_teoria_mnogoś...

8 of 8

2012-03-28 17:45