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ś...
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.
DEFINICJA 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:
TWIERDZENIE 1.2.
Dla dowolnych zbiorów zachodzi:
DOWÓ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.
1 of 8 2012-03-28 17:45
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ś...
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 . A
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.
DEFINICJA 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:
2 of 8 2012-03-28 17:45
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ś...
ĆWICZENIE 2.3
Produkt kartezjański jest monotoniczny ze względu na każdą współrzędną osobno, to znaczy:
ĆWICZENIE 2.4
Sprawdz
, czy dla dowolnych zbiorów , prawdziwa jest następująca implikacja:
Relacje
DEFINICJA 3.1.
Relacją nazywamy każdy podzbiór iloczynu .
Operacje na relacjach:
DEFINICJA 3.2.
Niech oraz .
ĆWICZENIE 3.3
Niech relacja oraz . Pokazać elementarne własności operacji na relacjach:
ĆWICZENIE 3.4
Niech relacja . Pokaż własności:
oraz
ĆWICZENIE 3.5
3 of 8 2012-03-28 17:45
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ś...
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.
DEFINICJA 4.1.
Dla zbioru definiujemy relację .
jako
DEFINICJA 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:
,
,
.
DEFINICJA 4.4.
Niech będzie relacją równoważności o polu . Klasą równoważności elementu jest zbiór
DEFINICJA 4.5.
Zbiór klas równoważności relacji będący elementem zbioru oznaczamy przez .
TWIERDZENIE 4.6.
Niech będzie relacją równoważności o polu . Następujące warunki są równoważne:
1. ,
4 of 8 2012-03-28 17:45
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. ,
3. .
DOWÓ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 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.
TWIERDZENIE 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. .
DOWÓD
Zwrotność jest oczywista, ponieważ zawiera się w każdej relacji rodziny . Symetria. Wez
my
. Dla każdej relacji jest . Z symetrii każdej jest więc , co daje
. Przechodniość. Niech . Dla każdej relacji jest więc
oraz
. Z przechodniości każdej relacji mamy, że , co daje .
i
. Mamy zatem, że , co daje dla każdej relacji . To zaś daje, że
Niech
.
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
DEFINICJA 4.8.
Niech . Rodzinę nazywamy rozkładem zbioru , gdy:
1. ,
2. ,
3. .
LEMAT 4.9.
5 of 8 2012-03-28 17:45
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ś...
Dla relacji równoważności o polu zbiór jest rozkładem .
DOWÓ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.).
DEFINICJA 4.10.
Niech będzie rozkładem zbioru . Definiujemy relacje następująco:
wtw
LEMAT 4.11.
Dla rozkładu
relacja jest:
1. równoważnością,
2.
DOWÓ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
i
takie, że . Przecięcie i jest więc niepuste, zatem , co daje tezę .
oraz
Inkluzja w prawo . Niech . Klasa jest zatem wyznaczona przez pewien element taki, że
. Niech będzie zbiorem rozkładu , do którego należy . A
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 i .
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.
6 of 8 2012-03-28 17:45
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ś...
DEFINICJA 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.
DEFINICJA 4.15.
Relacja jest domknięciem relacji w klasie (zbiorze) relacji gdy:
1.
2.
3. dla każdej relacji jeżeli oraz to
LEMAT 4.16.
Domknięcie relacji (w dowolnej klasie), jeżeli istnieje, to jest jedyne.
DOWÓD
Gdyby istniały dwa domknięcia pewnej relacji, to ze względu na warunek wzajemnie by się zawierały.
TWIERDZENIE 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 .
DOWÓ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.
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
7 of 8 2012-03-28 17:45
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ś...
oraz , da się pokazać, że ).
Ć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.
y
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;
8 of 8 2012-03-28 17:45