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]

Otóż niech [math]X,Y[/math] będą dowolnymi zbiorami, oraz niech [math]x\in X, y \in Y[/math]. Łatwo zauważyć, że zarówno [math] \left\{x,y\right\}[/math], jak i [math] \left\{x\right\}[/math] są podzbiorami [math] X \cup Y[/math]. Zatem [math] \left\{x,y\right\} \in \mathcal{P} (X \cup Y)[/math] oraz [math] \left\{x\right\} \in \mathcal{P} (X \cup Y)[/math]. Więc [math] \left\{\left\{x\right\},\left\{x,y\right\}\right\} \subset \mathcal{P} (X \cup Y)[/math], co daje, że [math]\left\{\left\{x\right\},\left\{x,y\right\}\right\}= (x,y) \in \mathcal{P} (\mathcal{P} (X \cup Y)).[/math]

Zauważmy teraz, że dla dowolnych ustalonych dwóch zbiorów [math]X,Y[/math] istnieje dokładnie jeden zbiór [math]X \cup Y[/math], dla zbioru [math]X \cup Y[/math] istnieje jedyny zbiór [math]P\left( X \cup Y\right)[/math], i znowu dla tego zbioru istnieje jedyny zbiór [math]\mathcal{P} (\mathcal{P} (X \cup Y)).[/math] Nasz dowód pokaże, że jeśli [math]x\in X, y\in Y[/math] to [math]\left\{\left\{x\right\},\left\{x,y\right\}\right\}= (x,y) \in \mathcal{P} (\mathcal{P} (X \cup Y)), [/math] co wobec dowolności [math]x,y[/math] będzie oznaczać, że cały iloczyn kartezjański [math]X\times Y[/math] jest zawarty w tym jedynym zbiorze [math]\mathcal{P} (\mathcal{P} (X \cup Y)).[/math] Pozostaje więc wybrać z tego jedynego zbioru (stosując aksjomat wybierania) ten iloczyn kartezjański, te wszystkie pary. Definiujemy więc:

[math] X \times Y=\left\{a\in\mathcal{P} (\mathcal{P} (X \cup Y)) \Bigl| \ \bigvee \limits_{x\in X}\bigvee \limits_{y\in Y} a=(x,y)=\left\{\left\{x\right\},\left\{x,y\right\}\right\} \right\}.[/math]

Wybraliśmy więc z takiego zbioru pary uporządkowane [math]a=(x,y)[/math], gdzie [math]x[/math] jest pewnym elementem zbioru [math]X[/math], [math]y[/math] jest pewnym elementem zbioru [math]Y[/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]