Relacje

Niech [math]a,b[/math] będą dowolnymi elementami (zbiorami). Przez parę uporządkowaną [math]\left( a,b\right)[/math] rozumiemy zbiór [math]\left\{ \left\{ a\right\},\left\{ a,b\right\} \right\}.[/math]

Uwaga: [math]\left( a,a\right) =\left\{ \left\{ a\right\},\left\{ a,a\right\} \right\}=\left\{ \left\{ a\right\},\left\{ a \right\}\right\}=\left\{ \left\{ a\right\} \right\}.[/math]

Parę uporządkowaną można też zdefiniować w inny sposób. Chodzi jednak o to, by dla takich par spełniona była własność zapowiedziana w pierwszym rozdziale, która mówi, że jeśli jedna para uporządkowana różni się od drugiej pary, choć na pierwszej czy choć na drugiej współrzędnej, to te pary uporządkowane są różne. A więc pokażemy, że przy naszej definicji pary uporządkowanej, zachodzi:

Twierdzenie 1. Dla dowolnych [math]a,b,c,d[/math], mamy:

[math]\left( a,b\right)=\left( c,d\right) \Longleftrightarrow \left\{ \left\{ a\right\},\left\{ a,b\right\} \right\}=\left\{ \left\{ c\right\},\left\{ c,d\right\} \right\}\Longleftrightarrow a=c \wedge b=d.[/math]

Oczywiście pierwsza równoważność to tylko zastosowanie definicji, interesuje nas druga równoważność, a w zasadzie implikacja [math]\Longrightarrow[/math].

Dowód: Załóżmy zatem, że [math]\left\{ \left\{ a\right\},\left\{ a,b\right\} \right\}=\left\{ \left\{ c\right\},\left\{ c,d\right\} \right\}.[/math]

Mamy [math]\left\{ a\right\} \in \left\{ \left\{ a\right\},\left\{ a,b\right\} \right\}[/math], więc [math]\left\{ a\right\} \in \left\{ \left\{ c\right\},\left\{ c,d\right\} \right\}[/math], a więc [math]\left\{ a\right\}=\left\{ c\right\}[/math] lub [math]\left\{ a\right\}=\left\{ c,d\right\}[/math]. W pierwszym przypadku [math]a=c[/math], ale w drugim również jest tak, mamy bowiem, z zasady równości zbiorów , że [math]c \in \left\{a\right\}[/math], a więc [math]c=a[/math]. Wiemy już, ze pierwsze współrzędne równych par są równe:

[math]\left( a,b\right)=\left( a,d\right)[/math]

Dalej przeprowadzimy dowód przez rozważenie przypadków.

Jeżeli [math]a=b[/math], to [math]\left( a,b\right)=\left( a,a\right)=\left\{ \left\{ a\right\} \right\}[/math], zatem [math]\left( a,d\right)=\left( a,b\right)=\left\{ \left\{ a\right\} \right\}[/math], więc ponieważ [math]\left( a,d\right)=\left\{ \left\{ a\right\},\left\{ a,d\right\} \right\} =\left\{ \left\{ a\right\} \right\}[/math], to z zasady równości zbiorów [math]\left\{ a,d\right\} \in \left\{ \left\{ a\right\} \right\}[/math], a więc [math]\left\{ a,d\right\}=\left\{ a\right\}[/math] , i dalej podobnie [math]d=a=b[/math], czyli [math]d=b[/math], co należało pokazać.

W przeciwnym przypadku, gdy [math]a \neq b[/math], to wtedy [math]\left( a,b\right)=\left\{ \left\{ a\right\},\left\{ a,b\right\} \right\}=\left( a,d\right)=\left\{ \left\{ a\right\},\left\{ a,d\right\} \right\}[/math]. Ponieważ [math]\left\{ a,b\right\} \in \left\{ \left\{ a\right\},\left\{ a,b\right\} \right\}[/math], więc [math]\left\{ a,b\right\} \in \left( a,d\right)=\left\{ \left\{ a\right\},\left\{ a,d\right\} \right\}[/math]. Daje to dwie możliwości: albo [math]\left\{ a,b\right\}=\left\{ a\right\}[/math], co prowadzi do [math]b=a[/math]-sprzeczność. Musi więc zajść drugi przypadek [math]\left\{ a,b\right\} =\left\{ a,d\right\}[/math], co daje [math]b\in \left\{ a,d\right\}[/math], i ponieważ [math]b \neq a[/math] to [math]b=d[/math], co należało pokazać.

Dowód [math]\Longleftarrow[/math] jest oczywisty, teza wynika wprost z założeń i zasady równości zbiorów.[math]\square[/math]

Ćwiczenie 2. Dla każdej pary uporządkowanej [math]x=\left( a,b\right)[/math], udowodnij, że [math]\bigcap\bigcap x=a.[/math]

To ćwiczenie ma bardziej charakter formalny. Przypomnijmy bowiem, że jedynymi przez nas rozważanymi obiektami (bytami) są zbiory. Wobec czego para uporządkowana [math]x=\left( a,b\right)[/math] jest zbiorem ( patrz definicja na początku tego rozdziału), jest to zbiór złożony ze zbiorów, bo elementy zbiorów są również zbiorami, więc możemy utworzyć iloczyn rodziny [math]x=\left( a,b\right)[/math], otrzymując zbiór [math]\bigcap x[/math]- znowu zbiór złożony ze zbiorów, i wtedy iloczyn takiej rodziny zbiorów [math]\bigcap\mathbb{A}[/math], gdzie [math]\mathbb{A}=\bigcap x[/math] ma być równe zbiorowi [math]a[/math] ( współrzędne par uporządkowanych są również zbiorami).

Rozwiązanie: [math]\bigcap \left(x=\left( a,b\right) =\left\{ \left\{ a\right\},\left\{ a,b\right\} \right\}\right)=\bigcap\left\{ \left\{ a\right\},\left\{ a,b\right\} \right\}=\left\{ a\right\} \cap \left\{ a,b\right\}=\left\{ a\right\}.[/math]

Zatem [math]\bigcap\bigcap x=\bigcap\left\{ a\right\}=a.[/math]

Pojęcie pary uporządkowanej jest potrzebne do wprowadzenia iloczynu kartezjańskiego, a potem relacji.

Iloczyn kartezjański

Iloczynem kartezjańskim zbiorów [math]X,Y[/math], to zbiór [math] X\times Y=\left\{\left( x,y\right)\Bigl| \ x\in X, y\in Y\right\}.[/math]

Iloczyn kartezjański

Czyli jest to zbiór wszystkich par uporządkowanych elementów kolejnych zbiorów [math]X,Y[/math]. Np. [math]\left( 1,2\right) ,\left( 2,2\right),\left( 2,1\right) \in \left[ 0,2\right] \times \left[ 1,2\right].[/math] Graficzną ilustracją iloczynu kartezjańskiego jest prostokąt- zobacz ilustracje obok. Na ogół [math]X\times Y\neq Y\times X[/math]- aby się o tym przekonać wyznacz np. [math]\left[ 0,1\right] \times \left[ 0,2\right][/math] i [math]\left[ 0,2\right] \times \left[ 0,1\right].[/math]

Podstawowe własności iloczynu kartezjańskiego:

Twierdzenie 1.1. Dla dowolnych zbiorów [math]X,Y,Z[/math]:

[math]1. \ X\times\left\{ \right\} =\left\{ \right\} =\left\{ \right\} \times X. \\ 2. \ X\times\left( Y\cup Z\right)=\left( X\times Y\right) \cup \left( X\times Z\right), \ \ \left( X\cup Y\right)\times Z=\left( X\times Z\right) \cup \left( Y\times Z\right). \\ 3. \ X\times\left( Y\cap Z\right)=\left( X\times Y\right) \cap \left( X\times Z\right). \\ 4. \ X\times\left( Y\setminus Z\right)=\left( X\times Y\right) \setminus \left( X\times Z\right). [/math]

Dowód:

1. Nie wprost. Gdyby iloczyn kartezjański [math]X\times\left\{ \right\}[/math] byłby niepusty, to istniałaby para [math]\left( x,a\right) \in X\times\left\{ \right\}[/math], a więc wtedy [math]x\in X[/math] i [math]a\in\left\{ \right\}[/math], a zbiór pusty nie posiada elementów, a [math]a[/math] świadczy o tym, że posiada- sprzeczność. Dowód drugiej równości jest analogiczny. [math]\square[/math]

Nim przejdziemy do dalszych dowodów. potrzebny będzie nam następujący prosty fakt: dla dowolnych [math]a,b[/math] oraz dowolnych zbiorów [math]A,B[/math], mamy:

[math]\left( a,b\right) \in A\times B \Longleftrightarrow a\in A \wedge b\in B.[/math]

Wynika to z definicji iloczynu kartezjańskiego. Jedyne, co wymaga krótkiego uzasadnienia, to wynikanie [math]\Longrightarrow.[/math]

Jeżeli [math]\left( a,b\right) \in A\times B [/math], to [math]\left( a,b\right)=\left( c,d\right)[/math], gdzie [math]c\in A, d\in B[/math]. Wtedy jednak z twierdzenia 1, mamy [math]a=c\in A[/math] i [math]b=d\in B[/math], czyli [math]a\in A[/math] i [math]b\in B[/math].

Przechodzimy do dowodu punktu 2.

Ponieważ obydwa zbiory są zbiorami par uporządkowanych, więc wykażemy, że dowolna para należy do jednego zbioru wtedy i tylko wtedy, gdy należy do drugiego. Weźmy dowolną parę [math]\left( a,b\right)[/math], wtedy na podstawie wprowadzonej własności i definicji sumy dwóch zbiorów:

[math] (a,b)\in X \times (Y \cup Z) \Leftrightarrow\\ a \in X \wedge b\in (Y\cup Z) \Leftrightarrow\\ a\in X \wedge (b\in Y \vee b\in Z) \Leftrightarrow\\ (a\in X \wedge b\in Y) \vee (a\in X \wedge b\in Z) \Leftrightarrow\\ (a,b) \in X \times Y \vee (a,b)\in X \times Z \Leftrightarrow\\ (a,b) \in \left( X\times Y\right) \cup \left( X\times Z\right). [/math]

Zatem, (patrz komentarz początek) [math]X\times\left( Y\cup Z\right)=\left( X\times Y\right) \cup \left( X\times Z\right).[/math] Dowód drugiej równości jest analogiczny. [math]\square[/math]

3. Ponieważ obydwa zbiory są zbiorami par uporządkowanych, więc znowu wykażemy, że dowolna para należy do jednego zbioru wtedy i tylko wtedy, gdy należy do drugiego. Weźmy dowolną parę [math](a,b)[/math], wtedy:

[math] (a,b)\in X \times (Y \cap Z) \Leftrightarrow\\ a \in X \wedge b\in (Y\cap Z) \Leftrightarrow\\ a\in X \wedge (b\in Y \wedge b\in Z) \Leftrightarrow\\ (a\in X \wedge b\in Y) \wedge (a\in X \wedge b\in Z) \Leftrightarrow\\ (a,b) \in X \times Y \wedge (a,b)\in X \times Z \Leftrightarrow\\ (a,b) \in \left( X\times Y\right) \cap \left( X\times Z\right),[/math]

co należało otrzymać.

4. Na tej samej zasadzie co poprzednio, weźmy dowolną parę [math](a,b)[/math]. Wtedy:

[math] (a,b) \in (X \times Y) \setminus (X \times Z) \Leftrightarrow (a,b) \in (X \times Y)\wedge (a,b) \notin (X \times Z)\Leftrightarrow \\ a\in X \wedge b\in Y \wedge \neg(a\in X \wedge b\in Z) \Leftrightarrow\\ b\in Y \wedge (a\in X \wedge (a\notin X \vee b\notin Z)) \Leftrightarrow\\ b\in Y \wedge [(a\in X \wedge a\notin X) \vee (a\in X \wedge b\notin Z)] \Leftrightarrow\\ b\in Y \wedge (a\in X \wedge b\notin Z) \Leftrightarrow a\in X \wedge (b\in Y\wedge b\notin Z)\Leftrightarrow\\ a\in X \wedge (b\in Y \setminus Z) \Leftrightarrow (a,b) \in X \times (Y \setminus Z), [/math]

co należało otrzymać. Dowód jest zakończony. [math]\square[/math]

Fakt 1.2. Dla dowolnych zbiorów [math]A,B,C,D[/math], mamy:

[math]A\subset B \wedge C\subset D \Longrightarrow A\times C\subset B\times D.[/math]

Czyli jeden iloczyn kartezjański [math]A\times C[/math] będzie się zawierać w drugim iloczynie kartezjańskim [math]B\times D[/math], jeśli tylko ten mniejszy (pod względem inkluzji) iloczyn kartezjański ma mniejsze odpowiednie składowe- czyli gdy zbiór [math]A[/math] mniejszy jest od [math]B[/math], i [math]C[/math] mniejszy jest od [math]D[/math]- to wtedy iloczyn kartezjański mniejszych zbiorów jest mniejszy od odpowiedniego mu iloczynu kartezjańskiego większych zbiorów (mniejszy,większy należy rozumieć jako słabo mniejszy,słabo większy- dopuszczamy równość zbiorów).

Dowód: Zakładamy, że [math]A\subset B[/math] i [math]C\subset D[/math], chcemy pokazać, że [math]A\times C\subset B\times D.[/math] Niech [math]\left( x,y\right)\in A\times C.[/math] Zatem [math]x[/math] należy do zbioru [math]A[/math], [math]y[/math] należy do [math]C[/math]. Ponieważ z założenia [math]A\subset B[/math], to [math]x[/math] należy do [math]B[/math]. Podobnie, ponieważ [math]C\subset D[/math], to [math]y[/math] należy do [math]D[/math]. Z tych dwóch ostatnich wniosków otrzymujemy, że [math]\left( x,y\right)\in B\times D.[/math] Zatem [math]A\times C\subset B\times D.\square[/math]

Szczególnym przypadkiem powyższego twierdzenia, jest fakt, że dla dowolnych zbiorów [math]A,B,C[/math], mamy:

[math]A\subset B \Longrightarrow A\times C\subset B\times C.[/math]

Aby to udowodnić, weźmy dowolne zbiory [math]A,B,C[/math], takie, że [math]A\subset B[/math]. Stosujemy ten Fakt 1.2. do tych samych zbiorów, i zbioru [math]D=C[/math]. Ponieważ mamy, że [math]A\subset B[/math], i [math]C\subset D=C[/math], to stosując ten fakt dostajemy, że [math]A\times C\subset B\times C.\square[/math]

Podobnie szczególnym przypadkiem tego Faktu 1.2., jest fakt, że dla dowolnych zbiorów [math]A,B,C[/math], mamy:

[math]A\subset B \Longrightarrow C\times A\subset C\times B.[/math]

Dokładana konstrukcja iloczynu kartezjańskiego została omówiona w dodatku dla dociekliwych Dla dociekliwych, gdzie została przedstawiona konstrukcja zgodna z aksjomatem wycinania.

Nim przejdziemy dalej do tematu relacji odnotujmy jeszcze zapomniane dwa proste fakty. Pierwszy mówi, że dla dowolnych zbiorów [math]A,B.C,D,[/math] mamy:

[math]A\subset B \wedge C\subset D \Longrightarrow A\cup C\subset B\cup D.[/math]

Czyli, że suma większych zbiorów (pod względem inkluzji) jest większa. Prosty dowód (trzeba tylko rozważyć dwa przypadki ze względu na przynależność do sumy) pozostawiamy czytelnikowi.

Drugi prosty fakt jest podobny- dotyczy tylko iloczynu. Dla dowolnych zbiorów [math]A,B.C,D,[/math] mamy:

[math]A\subset B \wedge C\subset D \Longrightarrow A\cap C\subset B\cap D.[/math]

Czyli iloczyn większych zbiorów jest większy. Dowód czytelnikowi nie nastręczy trudności.

Relacje

Podstawowym pojęciem (i fundamentalnym) teorii mnogości jest pojęcie relacji.

Niech [math]X,Y[/math] będą zbiorami. Relacją między zbiorami [math]X[/math] a [math]Y[/math], nazywamy każdy podzbiór [math]R\subset X\times Y.[/math]

Ilustracja relacji

Czyli tworzymy najpierw iloczyn kartezjański [math]X\times Y[/math], każdy podzbiór tego zbioru to przykład relacji między [math]X[/math] a [math]Y[/math]. Zobacz ilustrację obok.

Ważne relacje:

[math]\emptyset-[/math] relacja pusta( zbiór pusty jest podzbiorem każdego zbioru).

[math]X\times Y[/math]- relacja pełna (każdy zbiór jest podzbiorem swoim własnym, więc również spełnia to iloczyn [math]X\times Y[/math]).

Relacją w zbiorze [math]X[/math] , nazywamy każdy podzbiór [math]R\subset X\times X.[/math]

Przykładem znowu może być relacja pusta, relacja totalna [math]X\times X[/math], ale również:

[math]I_{X}=\left\{ \left( x,y\right) \in X\times X\Bigl| \ \ x=y\right\}.[/math] Relacja identyczności- dwa elementy są w relacji gdy są identyczne, równe.

Gdy [math]\left( x,y\right) \in R[/math], gdzie [math]x\in X, y\in Y[/math], to mówimy, że elementy [math]x,y[/math] są ze sobą w relacji [math]R[/math]. Zapisujemy to też jako: [math]x(R)y[/math]. Też dla innych oznaczeń relacji- jeśli oznaczymy relację przez np. [math]\sim[/math], to fakt, że elementy [math]x,y[/math] są ze sobą w relacji [math]\sim[/math], zapiszemy jako: [math]x\sim y[/math].

Suma, iloczyn i różnica relacji

Na relacjach można wykonywać działania mnogościowe. I tak, dla relacji [math]R,S\subset X\times Y,[/math] relacja [math]R\cup S[/math], to taka relacja, że dwa elementy [math]x,y[/math] są ze sobą w relacji [math]R\cup S[/math], jeśli tylko są ze sobą w relacji [math]R[/math], oraz wtedy, jeśli tylko są ze sobą w relacji [math]S[/math]. Czyli [math]\left( x,y\right) \in R\cup S\Longleftrightarrow \left( x,y\right) \in R\vee \left( x,y\right) \in S[/math].

Podobnie, dla relacji [math]R,S\subset X\times Y,[/math] relacja [math]R\cap S[/math], to taka relacja, że dwa elementy [math]x,y[/math] są ze sobą w relacji [math]R\cap S[/math], jeśli są ze sobą w relacji [math]R[/math], oraz równocześnie są ze sobą w relacji [math]S[/math]. Czyli [math]\left( x,y\right) \in R\cap S\Longleftrightarrow \left( x,y\right) \in R\wedge \left( x,y\right) \in S.[/math]

Podobnie, różnica relacji [math]R,S[/math]- relacja [math]R\setminus S[/math], to taka relacja, że dwa elementy są ze sobą w relacji [math]R\setminus S[/math], gdy są ze sobą w relacji [math]R[/math] i nie są ze sobą w relacji [math]S[/math], tzn. [math]\left( x,y\right) \in R\setminus S\Longleftrightarrow \left( x,y\right) \in R\wedge \left( x,y\right) \not\in S.[/math]

Ilustracja tych operacji jest podobna do ilustracji działań mnogościowych na zbiorach- zobacz ilustrację obok. Różnica polega na tym, że mamy wprowadzoną strukturę iloczynu kartezjańskiego, i na punkty patrzymy nie na jako zwykłe elementy, tylko jak na pary uporządkowane.

Co więcej, niech [math]\mathbb{A}[/math] będzie pewną rodziną relacji z [math]X[/math] do [math]Y[/math]. Wtedy [math]\bigcup \mathbb{A}[/math]- suma rodziny relacji z [math]X[/math] do [math]Y[/math], a więc suma rodziny podzbiorów [math]X\times Y[/math] jest podzbiorem [math]X\times Y[/math], a więc jest relacją z [math]X[/math] do [math]Y[/math]. Stąd mamy ważne:

Twierdzenie 2.1. Suma dowolnej rodziny relacji z [math]X[/math] do [math]Y[/math] jest relacją z [math]X[/math] do [math]Y[/math].

Dla takiej relacji, mamy: [math]\left( x,y\right) \in \bigcup \mathbb{A}\Longleftrightarrow \left( x,y\right) \in R[/math], dla pewnej relacji [math]R\in\mathbb{A}.[/math]

Tzn. dwa elementy są ze sobą w relacji [math]\bigcup \mathbb{A}[/math], gdy są z sobą w relacji [math]R[/math], dla pewnej relacji [math]R[/math] z rodziny relacji [math]\mathbb{A}.[/math]

Podobnie możemy określić iloczyn rodziny relacji. Dla niepustej rodziny [math]\mathbb{A}[/math] relacji z [math]X[/math] do [math]Y[/math], relacja [math]\bigcap \mathbb{A}[/math], to taka relacja, że dwa elementy są ze sobą w relacji [math]\bigcap \mathbb{A}[/math], gdy są z sobą w relacji [math]R[/math], dla każdej relacji [math]R\in\mathbb{A}.[/math]