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: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
Linia 424: Linia 424:
 
\exists_y [(x,y) \in T \wedge ((y,z)\in R \vee (y,z)\in S ))] \Leftrightarrow\\
 
\exists_y [(x,y) \in T \wedge ((y,z)\in R \vee (y,z)\in S ))] \Leftrightarrow\\
 
\exists_y [((x,y) \in T \wedge (y,z)\in R) \vee ((x,y) \in T \wedge (y,z)\in S ))] \Leftrightarrow\\
 
\exists_y [((x,y) \in T \wedge (y,z)\in R) \vee ((x,y) \in T \wedge (y,z)\in S ))] \Leftrightarrow\\
[\exists_y ((x,y) \in T \wedge (y,z)\in R)] \vee [\exists_y ((x,y) \in T \wedge (y,z)\in S )] \Leftrightarrow\\
+
\ [\exists_y ((x,y) \in T \wedge (y,z)\in R)] \vee [\exists_y ((x,y) \in T \wedge (y,z)\in S )] \Leftrightarrow\\
 
(x,z)\in (R \circ T) \vee (x,z)\in (S \circ T) \Leftrightarrow \\
 
(x,z)\in (R \circ T) \vee (x,z)\in (S \circ T) \Leftrightarrow \\
 
(x,z)\in  (R \circ T) \cup (S  \circ T)
 
(x,z)\in  (R \circ T) \cup (S  \circ T)
 
\end{align}</math></center>
 
\end{align}</math></center>
5.  
+
5.
  
 
<center><math>\displaystyle \begin{align} (x,z)\in (R \cap  S ) \circ T  \Leftrightarrow\\
 
<center><math>\displaystyle \begin{align} (x,z)\in (R \cap  S ) \circ T  \Leftrightarrow\\
Linia 434: Linia 434:
 
\exists_y [(x,y) \in T \wedge ((y,z)\in R \wedge (y,z)\in S ))] \Leftrightarrow\\
 
\exists_y [(x,y) \in T \wedge ((y,z)\in R \wedge (y,z)\in S ))] \Leftrightarrow\\
 
\exists_y [((x,y) \in T \wedge (y,z)\in R) \wedge ((x,y) \in T \wedge (y,z)\in S ))] \Rightarrow\\
 
\exists_y [((x,y) \in T \wedge (y,z)\in R) \wedge ((x,y) \in T \wedge (y,z)\in S ))] \Rightarrow\\
[\exists_y ((x,y) \in T \wedge (y,z)\in R)] \wedge [\exists_y ((x,y) \in T \wedge (y,z)\in S )] \Leftrightarrow\\
+
\ [\exists_y ((x,y) \in T \wedge (y,z)\in R)] \wedge [\exists_y ((x,y) \in T \wedge (y,z)\in S )] \Leftrightarrow\\
 
(x,z)\in (R \circ T) \wedge (x,z)\in (S \circ T) \Leftrightarrow \\
 
(x,z)\in (R \circ T) \wedge (x,z)\in (S \circ T) \Leftrightarrow \\
 
(x,z)\in  (R \circ T) \cap (S  \circ T)
 
(x,z)\in  (R \circ T) \cap (S  \circ T)

Aktualna wersja na dzień 13:48, 28 wrz 2020

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.

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 .

End of proof.gif

Ćwiczenie 1.3

Dla każdej pary udowodnij, że

Rozwiązanie

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

Rozwiązanie

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

Wskazówka


Rozwiązanie

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.

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:

Rozwiązanie

Ćwiczenie 2.3

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

Rozwiązanie

Ćwiczenie 2.4

Sprawdź, czy dla dowolnych zbiorów , prawdziwa jest następująca implikacja:

Rozwiązanie

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:

Rozwiązanie

Ćwiczenie 3.4

Niech relacja oraz . Pokaż własności:

Rozwiązanie

Ćwiczenie 3.5

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

Rozwiązanie

Ćwiczenie 3.6

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

Rozwiązanie

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:

  • ,
  • ,
  • .
Rozwiązanie

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

End of proof.gif

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

End of proof.gif

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.

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

End of proof.gif

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ą,

Dowó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 .

End of proof.gif

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

Wskazówka


Rozwiązanie

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

Wskazówka


Rozwiązanie

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.

Definicja 4.14.

Niech będzie rodziną relacji o polu , czyli niech . Rodzina jest zamknięta na przecięcia, gdy:

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

End of proof.gif

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 .

End of proof.gif

Ć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 oraz , da się pokazać, że ).

Rozwiązanie

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

Rozwiązanie