Dalsze zagadnienia

Będę tu prezentował dodatkowe, raczej proste zadania( bo były fajne zadania, które zostawiłem na potem). Będą to raczej proste problemy.

Uzasadnimy najpierw, że dla dwóch rodzin zbiorów [math]\mathbb{X}, \mathbb{Y}[/math] nie zawsze zachodzi równość zbiorów:

[math]\bigcap\left( \mathbb{X} \cap \mathbb{Y}\right)= \bigcap \mathbb{X} \cap \bigcap \mathbb{Y}.[/math]

Jako kontrprzykład dla tej równości połóżmy [math]X=\left\{ 1,2\right\} [/math] [math]Y=\left\{ 2,3\right\}[/math] oraz [math]\mathbb{X}=\left\{ X\right\}, \mathbb{Y}=\left\{ Y\right\}.[/math]

Wtedy [math]\bigcap \mathbb{X}=X[/math], podobnie [math]\bigcap \mathbb{Y}=Y[/math], zatem [math]\bigcap \mathbb{X} \cap \bigcap \mathbb{Y}=X\cap Y=\left\{ 2\right\}.[/math]

Podczas gdy [math]\mathbb{X} \cap \mathbb{Y}=\emptyset[/math], bo zbiory [math]X\neq Y[/math], zatem [math]\bigcap\left( \mathbb{X} \cap \mathbb{Y}\right)=\bigcap\emptyset=\emptyset\neq\left\{ 2\right\}[/math], równość więc nie jest prawdą.

Zastanówmy się nad inkluzjami dla rodziny zbiorów [math]\mathbb{X}[/math]: [math]\bigcup\mathbb{X}\subset \mathbb{X}[/math], oraz [math]\bigcup\mathbb{X}\supset \mathbb{X}.[/math] Otóż, wbrew pozorom, ta ostatnia inkluzja jest o wiele bardziej nietypowa. Pierwsza inkluzja mówi, że elementy [math]\bigcup\mathbb{X}[/math] są elementami [math]\mathbb{X}[/math], czyli elementy elementów [math]\mathbb{X}[/math] (zbiorów rodziny [math]\mathbb{X}[/math]) są elementami [math]\mathbb{X}[/math]- są to tzw. zbiory(rodziny zbiorów) przechodnie. Równoważnie to możemy określić warunkiem [math]\mathbb{X}\subset P\left( \mathbb{X}\right)[/math], bo ten warunek oznacza, że zbiory rodziny [math]\mathbb{X}[/math] są elementami [math]P\left( \mathbb{X}\right)[/math], czyli są podzbiorami [math]\mathbb{X}[/math], w związku z czym ich elementy są elementami [math]\mathbb{X}[/math], czyli to oznacza, że elementy elementów [math]\mathbb{X}[/math] są elementami [math]\mathbb{X}[/math]. O takich zbiorach przechodnich będziemy jeszcze pisać.

Natomiast inkluzja [math]\bigcup\mathbb{X}\supset \mathbb{X}.[/math] jest o wiele dziwniejsza. Mówi ona, że zbiory rodziny [math]\mathbb{X}[/math] są elementami [math]\bigcup\mathbb{X}[/math], a więc elementów tych zbiorów. A to przecież elementy zbiorów rodziny [math]\mathbb{X}[/math] są elementami odpowiednich zbiorów. Jednak taka dziwaczna inkluzja jest możliwa. Niech [math]\mathbb{X}[/math] będzie dowolną rodziną induktywną (tzn. spełniającą aksjomat nieskończoności). Wykażemy, że wtedy [math]\bigcup\mathbb{X}\supset \mathbb{X}.[/math]

Niech [math]A\in\mathbb{X}.[/math] Pokażemy, że [math]A\in\bigcup\mathbb{X}.[/math] Ponieważ [math]\mathbb{X}[/math] jest zbiorem induktywnym, to [math]A'=A\cup\left\{ A\right\}\in\mathbb{X}[/math], ponieważ [math]A\in A\cup\left\{ A\right\}\in\mathbb{X}[/math], to [math]A\in\bigcup\mathbb{X}. \square[/math]

Zastanówmy się teraz uważnie nad pytaniem: Czy istnieje więcej niż jeden zbiór(rodzina zbiorów) [math]\mathbb{X}[/math] taka, że [math]\bigcap \mathbb{X} = \bigcup \mathbb{X}[/math]?

Otóż wiemy, że dla dowolnego zbioru [math]X[/math] mamy [math]\bigcap \left\{X\right\}=X=\bigcup \left\{X\right\},[/math] a więc istnieje przynajmniej jedna taka rodzina zbiorów. Biorąc teraz dwa różne zbiory [math]A,B[/math], zauważamy, że wtedy rodziny zbiorów [math]\left\{A\right\}, \left\{B\right\}[/math] są różne (bo zbiory [math]A,B[/math] są różne). Zgodnie z przytoczonym faktem [math]\bigcap \left\{A\right\}=A=\bigcup \left\{A\right\},[/math] oraz [math]\bigcap \left\{B\right\}=B=\bigcup \left\{B\right\}[/math], wobec czego istnieją co najmniej dwie rodziny zbiorów [math]\mathbb{X}[/math], takie,że iloczyn rodziny [math]\mathbb{X}[/math] jest równy sumie rodziny [math]\mathbb{X}[/math].

Dla dowolnego zbioru [math]X[/math], mamy: [math]\bigcup P\left( X\right)=X.[/math]

Dowód: Aby pokazać, że [math]\bigcup P\left( X\right)=X,[/math] pokazujemy dwa zawierania.

Inkluzja w prawo: Suma rodziny wszystkich podzbiorów [math]X[/math], a więc suma szczególnej rodziny podzbiorów [math]X[/math] musi być podzbiorem [math]X[/math].

Inkluzja w lewo: Wiemy,że suma dowolnej rodziny zbiorów jest nadzbiorem każdego zbioru tej rodziny, więc suma rodziny wszystkich podzbiorów [math]X[/math] jest nadzbiorem [math]X[/math] (bo [math]X \subset X[/math], a więc [math]X\in P\left( X\right)[/math]).

A więc [math]\bigcup P\left( X\right)=X.\square[/math]

Dla dowolnej rodziny zbiorów [math]\mathbb{X}[/math] mamy:

[math]\mathbb{X}\subset P\left( \bigcup \mathbb{X}\right).[/math]

Dowód: Niech [math]A\in\mathbb{X}[/math]. Skoro [math]A[/math] jest zbiorem z rodziny [math]\mathbb{X}[/math], to z własności sumy [math]A[/math] jest podzbiorem sumy tej rodziny, czyli [math]A\subset \bigcup \mathbb{X}.[/math] To z kolei oznacza, że [math]A\in P\left( \bigcup \mathbb{X}\right)[/math], i z dowolności [math]A[/math], otrzymujemy [math]\mathbb{X}\subset P\left( \bigcup \mathbb{X}\right).\square[/math]

Jednak inkluzja w drugą stronę nie zawsze zachodzi. Kontrprzykładem będzie rodzina [math]\mathbb{X}= \{\{\emptyset\}\}.[/math] Wtedy:

[math]\mathcal{P}(\bigcup\{\{\emptyset\}\} \ \ )= \mathcal{P}(\{\emptyset\}) = \{\emptyset,\{\emptyset\}\}\neq \{\{\emptyset\}\}=\mathbb{X},[/math] bo [math]\emptyset\notin \{\{\emptyset\}\}[/math], bo [math]\emptyset\neq \{\emptyset\}.[/math] Zatem tutaj [math]\mathbb{X}\neq P\left( \bigcup \mathbb{X}\right).[/math]

Jeśli mamy funkcję [math]f:X\rightarrow X[/math], to element [math]x\in X[/math] nazywamy punktem stałym funkcji [math]f[/math], gdy [math]f(x)=x.[/math]

Niech [math]X[/math] będzie zbiorem. Rozważmy funkcję [math]f:P\left( P\left( X\right) \right) \rightarrow P\left( P\left( X\right) \right),[/math] określoną jako:

[math]f\left( x\right)=\left\{ \bigcup x, \bigcap x\right\} .[/math]

Czyli funkcja [math]f[/math] dostaje jako argument rodzinę podzbiorów [math]X[/math], i przypisuje jej rodzinę złożoną z dwóch zbiorów- zbioru będącego sumą tej rodziny oraz zbioru będącego iloczynem tej rodziny. Podamy kilka przykładów punktów stałych dla tej funkcji.

Dla dowolnego zbioru [math]A\subset X[/math], mamy [math]f\left( \left\{ A\right\} \right)=\left\{ \bigcup \left\{ A\right\} , \bigcap \left\{ A\right\} \right\}=\left\{ A,A\right\} =\left\{ A\right\} .[/math] A więc rodzina [math]\left\{ A\right\}[/math] jest punktem stałym. Kolejne przykłady:

Dla dowolnego zbioru [math]A \subset X[/math], mamy [math]f\left( \left\{ A,\emptyset \right\} \right)=\left\{ \bigcup\left\{ A,\emptyset \right\}, \bigcap\left\{ A,\emptyset \right\} \right\}=\left\{ A \cup \emptyset, A \cap \emptyset \right\}=\left\{ A,\emptyset \right\}.[/math]

Dla dowolnych zbiorów [math]A,B \subset X[/math], takich, że [math]A \subset B[/math] mamy: [math]f\left( \left\{ A,B\right\} \right)=\left\{ A \cup B, A \cap B\right\}=\left\{ B,A\right\}=\left\{ A,B\right\},[/math] gdzie przedostatnia równość pochodzi z założenia, że [math]A \subset B.[/math]

Zwróćmy uwagę, że istnieją funkcje, które nie mają punktów stałych. Prostym przykładem może być funkcja [math]f:\left\{ 0,1\right\} \rightarrow \left\{ 0,1\right\},[/math] daną jako [math]f=\left\{ \left( 0,1\right),\left( 1,0\right) \right\}.[/math]

Kolejny przykład. Niech [math]X[/math] będzie niepustym zbiorem. Wykażemy, że dla funkcji [math]f:P\left( X\right) \rightarrow P\left( X\right),[/math] określonej jako [math]f\left( A\right)=X \setminus A[/math], nie istnieje punkt stały.

Przypuśćmy, że istnieje punkt stały, nazwijmy go [math]A[/math]. Wtedy [math]f\left( A\right)=A.[/math] Z drugiej strony, z definicji tej funkcji mamy [math]f\left( A\right)=X \setminus A.[/math] Wnioskujemy, że [math]A=X \setminus A.[/math] Ponieważ zbiór [math]X[/math] jest niepusty, więc istnieje element [math]x \in X,[/math] ustalamy taki element. Rozstrzygnijmy problem czy [math]x \in A.[/math] Jeśli tak, to z tej równości wynika, że [math]x \in X \setminus A[/math], a więc z definicji różnicy zbiorów [math]x \notin A[/math]- sprzeczność. Jeśli [math]x\notin A[/math], to [math]x \in X \setminus A,[/math] a więc z tej równości wynika, że [math]x \in A[/math], i również otrzymujemy sprzeczność, co kończy ten prosty dowód.[math]\square[/math]

Dla funkcji [math]f:P\left( X\right) \rightarrow P\left( X\right),[/math] zbiór [math]A \subset X[/math] nazywamy najmniejszym punktem stałym, gdy [math]f\left( A\right)=A,[/math] (czyli [math]A[/math] jest punktem stałym) oraz dla dowolnego zbioru [math]B \subset X[/math] spełniony jest warunek [math]f\left( B\right)=B \rightarrow A \subset B.[/math] Czyli gdy każdy punkt stały [math]B[/math] jest większy pod względem inkluzji od [math]A[/math]- od tego najmniejszego punktu stałego, czyli zbiór [math]B[/math] jest nadzbiorem zbioru [math]A[/math].

Podobnie dla funkcji [math]f:P\left( X\right) \rightarrow P\left( X\right),[/math] zbiór [math]A \subset X[/math] nazwiemy największym punktem stałym, gdy jest punktem stałym, oraz każdy zbiór [math]B \subset X[/math] będący punktem stałym jest podzbiorem [math]A[/math], czyli wtedy zbiór [math]A[/math] jest większy pod względem inkluzji od [math]B[/math].

Poniższy przykład pokazuje, że dla funkcji może się zdarzyć, że mimo, że istnieją punkty stałe, ale nie istnieje największy punkt stały.

Niech [math]X[/math] będzie niepustym zbiorem. Rozważmy funkcję [math]f:P\left( P\left( X\right) \right) \rightarrow P\left( P\left( X\right) \right)[/math], określoną jako [math]f\left( \mathbb{A}\right)= \left\{ \bigcup \mathbb{A} \right\},[/math] czyli funkcja [math]f[/math] dostaje jako argument rodzinę podzbiorów [math]X[/math], i przypisuje jej zbiór jednoelementowy złożony z sumy tej rodziny. Jeśli [math]\mathbb{A}[/math] jest rodziną podzbiorów [math]X[/math], która jest punktem stałym, to wtedy [math]f\left( \mathbb{A}\right)=\mathbb{A}= \left\{ \bigcup \mathbb{A} \right\}.[/math] Widać więc, że punktami stałymi mogą być tylko rodziny jednozbiorowe (jednoelementowe)- bo zbiór [math]\left\{ \bigcup \mathbb{A} \right\}[/math] jest jednoelementowy. Wykażemy teraz, że każda rodzina jednozbiorowa jest punktem stałym. Niech [math]A \subset X.[/math] Pokazujemy, że [math]\left\{ A\right\}[/math] jest punktem stałym. Z określenia funkcji mamy [math]f\left( \left\{ A\right\} \right)= \left\{ \bigcup \left\{ A\right\} \right\}=\left\{ A\right\}.[/math] Zatem [math]\left\{ A\right\}[/math] jest punktem stałym. Zatem dla tej funkcji punktami stałymi są dokładnie rodziny jednozbiorowe. Ponieważ [math]X[/math] jest niepusty, więc ma co najmniej dwa różne podzbiory [math]A,B[/math] (np. [math]\emptyset[/math] i [math]X[/math]). Ustalmy dwa takie różne podzbiory [math]A,B.[/math] Wtedy rodziny zbiorów [math]\left\{ A\right\},\left\{ B\right\}[/math] są różne ( bo zbiory [math]A,B[/math] są różne). Zgodnie z udowodnioną własnością rodziny zbiorów [math]\left\{ A\right\},\left\{ B\right\}[/math] są punktami stałymi. Gdyby istniał tu największy punkt stały, to musiałby być nadzbiorem [math]\left\{ A\right\}[/math] oraz [math]\left\{ B\right\},[/math] zatem musiałby mieć co najmniej dwa elementy ([math]A,B[/math]). A ponieważ jest to punkt stały, i punktami stałymi są dokładnie rodziny jednozbiorowe otrzymujemy sprzeczność. Wobec czego tu nie istnieje największy punkt stały ( choć istnieją co najmniej dwa punkty stałe).

Jednak każda funkcja [math]f:P\left( X\right) \rightarrow P\left( X\right)[/math], która jest monotoniczna ze względu na inkluzję, posiada najmniejszy punkt stały oraz ma największy punkt stały.

Monotoniczna pod względem inkluzji, tzn. spełnia warunek dla dowolnych zbiorów [math]A,B \subset X[/math]:

[math]A \subset B \rightarrow f\left( A\right) \subset f\left( B\right).[/math]

Warunek ten mówi, że jeśli na argumentach funkcji zachodzi inkluzja (przypominamy,że argumentami i wartościami funkcji są tu podzbiory zbioru [math]X[/math]), to na odpowiadających im wartościach również zachodzi (zgodna) inkluzja. Funkcję monotoniczne ze względu na inkluzję zachowują relację inkluzji pomiędzy przekształcanymi zbiorami.

Ilustracja funkcji za pomocą grafu

Przypomnijmy intuicję ze szkoły, że funkcja pomiędzy dwoma zbiorami, to przyporządkowanie każdemu elementowi pierwszego zbioru dokładnie jednego elementu drugiego zbioru. U nas rolę przyporządkowania w sposób ścisły pełni relacja pomiędzy tymi zbiorami. Każda funkcja jest zatem zbiorem par uporządkowanych. Spróbujemy jednak zilustrować funkcję za pomocą grafu. Wiemy, że funkcja jest zbiorem par, a każdy zbiór jest (sam w sobie) nieuporządkowany. Możemy zatem te pary ustawić w takiej kolejności jak chcemy. Weźmy element dziedziny [math]x \in X[/math], z definicji funkcji jest mu przypisany dokładnie jeden element [math]y\in Y[/math]. Łączymy te elementy, łączymy wszystkie elementy dziedziny którym jest przypisana wartość [math]y[/math] z elementem [math]y[/math]. Bierzemy kolejny inny element dziedziny funkcji [math]x _{1}[/math], przypisany jest mu jeden element [math]y _{1}[/math]. Łączymy te elementy, łączymy wszystkie elementy dziedziny którym jest przypisana wartość [math]y_{1}[/math] z elementem [math]y _{1}[/math]. Bierzemy kolejny inny element dziedziny funkcji [math]x _{2}[/math], robimy ten proces aż się wyczerpią elementy dziedziny(u nas cztery serie- zobacz ilustrację obok).

Jeśli funkcja [math]f:X \rightarrow Y[/math] jest bijekcją, to relacja odwrotna [math]f ^{-1}[/math] jest funkcją bijekcją ze zbioru [math]Y[/math] w zbiór [math]X[/math].

Dowód:

Pokażemy, że [math]\left( f ^{-1}\right) _{L}=Y.[/math] Niech [math]y\in Y.[/math] Ponieważ [math]f[/math] jest bijekcją, to jest 'na' zbiór [math]Y[/math], więc [math]y=f \left( x\right) ,[/math] przy pewnym [math]x\in X[/math]. Inaczej mówiąc [math]\left( x,y\right) \in f[/math]. Wtedy z określenia relacji odwrotnej [math](y,x)\in f^{-1}[/math], a więc [math]y[/math] należy do [math]\left( f ^{-1}\right) _{L}[/math]. Wobec dowolności wyboru [math]y[/math] otrzymujemy [math]\left( f ^{-1}\right) _{L}=Y.[/math]

Pokażemy, że relacja [math]f ^{-1}[/math] jest funkcją ze zbioru [math]Y[/math] w zbiór [math]X[/math]. Przypuśćmy dla dowodu nie wprost, że nie jest funkcją. Oznacza to, że istnieje element [math]y\in Y[/math] oraz elementy [math]x_1,x_2\in X[/math] takie, że [math]x_1 \neq x_2, \left( y, x_{1} \right) \in f^{-1}[/math], i [math]\left( y, x_{2} \right) \in f^{-1}.[/math] Wtedy [math]\left( x _{1},y \right) \in f[/math] i [math]\left( x _{2},y \right) \in f[/math] inaczej mówiąc [math]f\left( x _{1} \right)=y= f\left( x _{2}\right),[/math] i ponieważ [math]f[/math] jest bijekcją, więc jest różnowartościowa, więc otrzymujemy sprzeczność wobec tego, że ta funkcja różnym elementom [math]x_{1}, x_{2}[/math] przypisuje tą samą wartość [math]y.[/math]

Pokażemy, że funkcja [math]f ^{-1}[/math] jest funkcją różnowartościową. Weźmy dowolne pary należące do niej [math]\left( y _{1},x\right),\left( y _{2},x\right),[/math] które mają taką samą drugą współrzędną [math]x[/math]. Pokażemy, że [math]y_1=y_2.[/math] Ponieważ [math]\left( y _{1},x\right),\left( y _{2},x\right) \in f^{-1},[/math] to [math]\left(x, y_{1} \right) \in f[/math] i [math]\left(x, y_{2} \right) \in f[/math], wobec czego, i ponieważ [math]f[/math] jest funkcją, otrzymujemy [math]y_1=y_2[/math]. Zatem [math]f ^{-1}[/math] jest funkcją różnowartościową.

Pokażemy, że funkcja [math]f ^{-1}[/math] jest 'na' zbiór [math]X[/math]. Niech [math]x\in X[/math]. Ponieważ [math]f:X \rightarrow Y[/math], to istnieje jedyny element [math]y \in Y[/math], taki, że [math]f\left( x\right)=y.[/math] Inaczej mówiąc [math]\left( x,y\right) \in f[/math], a więc [math]\left( y,x\right) \in f^ {-1}[/math] , inaczej mówiąc [math]f^{-1} \left( y\right)=x[/math], a więc [math]x[/math] jest wartością funkcji [math]f^{-1}.[/math] Wobec dowolności [math]x\in X[/math] ,funkcja [math]f^{-1}[/math] jest 'na' zbiór [math]X.[/math]

Zatem [math]f ^{-1}[/math] jest funkcją bijekcją ze zbioru [math]Y[/math] w zbiór [math]X. \square[/math]

Wykażemy, że jeśli w zbiorze uporządkowanym [math]\left( X, \le \right)[/math] jest element najmniejszy, to jest on supremum zbioru pustego, ( pustego podzbioru [math]X[/math]). Zobacz ilustrację obok.

Niech [math]a[/math] będzie elementem najmniejszym w [math]X[/math]. Pokażemy, że [math]a[/math] spełnia warunki bycia supremum [math]\bigvee \left\{ \right\} .[/math]

1. Należy pokazać, że [math]a[/math] jest ograniczeniem górnym zbioru pustego, czyli [math]b\le a[/math] dla dowolnego [math]b\in\left\{ \right\}[/math], oczywiście jest to (formalnie) prawda.

2. Niech [math]b[/math] będzie ograniczeniem górnym zbioru pustego. Ponieważ [math]a[/math] jest elementem najmniejszym, to natychmiast otrzymujemy, że [math]a \le b[/math]. Wobec dowolności [math]b[/math] oznacza, to że [math]\bigvee \left\{ \right\}=a .\square[/math]

W sposób symetryczny można pokazać, że jeśli w zbiorze uporządkowanym [math]\left( X, \le \right)[/math] jest element największy, to jest on infimum zbioru pustego, ( pustego podzbioru [math]X[/math]).

W zbiorze uporządkowanym jeśli każdy podzbiór ma supremum, to każdy podzbiór ma infimum.

Przedstawmy jedynie piękny szkic dowodu.

Niech [math]\left( X, \le \right)[/math] będzie zbiorem uporządkowanym w którym każdy podzbiór ma supremum. Należy pokazać, że każdy podzbiór ma infimum. Weźmy zbiór [math]A\subset X[/math]. Należy pokazać, że [math]A[/math] ma infimum. Rozważmy zbiór [math]B[/math] na lewo od zbioru [math]A[/math]( czyli zbiór ograniczeń dolnych zbioru [math]A[/math]). Taki zbiór [math]B[/math] jako podzbiór [math]X[/math] ma supremum, i pokazujemy, że to supremum jest infimum zbioru [math]A[/math] na prawo. Zobacz ilustrację obok.

W sposób symetryczny, w zbiorze uporządkowanym, jeśli każdy podzbiór ma infimum, to każdy podzbiór ma supremum.

Symetrycznie- trzeba wziąć zbiór [math]A\subset X[/math], i rozważyć zbiór na prawo od niego. Taki zbiór ma infimum, i pokazujemy, że to infimum jest supremum zbioru na lewo- zbioru [math]A[/math].

Niech [math]X[/math] będzie zbiorem. Wtedy rodzina jego wszystkich podzbiorów [math]P \left( X\right)[/math] jest uporządkowana przez inkluzję, zatem [math]\left( P\left( X\right), \subset \right)[/math] jest zbiorem uporządkowanym. Wtedy mówiliśmy, że dla dowolnej rodziny [math]\mathbb{A} \subset P\left( X\right)[/math], mamy [math]\bigvee \mathbb{A}= \bigcup\mathbb{A},[/math] a jeśli dodatkowo rodzina [math]\mathbb{A}[/math] jest niepusta, to [math]\bigwedge \mathbb{A}= \bigcap\mathbb{A}.[/math] Objaśniając, jeśli weźmiemy rodzinę [math]\mathbb{A}[/math] podzbiorów [math]X[/math], wtedy supremum tej rodziny jest suma tej rodziny, a jeśli dodatkowo rodzina jest niepusta, to jej infimum to iloczyn tej rodziny. Dla pustej rodziny, mamy, jej infimum to element największy( mówiliśmy, że element największy jest infimum zbioru pustego), czyli tutaj cały zbiór [math]X[/math]( jest największym elementem [math]P\left( X\right)[/math] pod względem inkluzji), podczas gdy [math]\bigcap\emptyset=\emptyset.[/math] Równość więc dla niepustego zbioru [math]X[/math] nie ma miejsca.

Ilustracja relacji zwrotnej

Relacja [math]R[/math] w zbiorze [math]X[/math] jest zwrotna dokładnie wtedy, gdy zawiera relację identyczności na [math]X[/math]. Zilustrujmy to lepiej- zobacz obok.

Relacja [math]R \subset X \times X[/math] jest symetryczna, jeśli spełnia warunek (dla dowolnych [math]x,y \in X[/math])

[math]\left( x,y\right)\in R \rightarrow \left( y,x\right) \in R.[/math]

Czyli jeśli elementy [math]x,y[/math] są ze sobą w relacji [math]R[/math], to symetrycznie [math]y,x[/math] są również w relacji [math]R[/math].

Przykład: Niech [math]X=\left\{ 0,1\right\}.[/math] [math]R=\left\{ \left( 0,1\right), \left(1,0 \right) \right\}[/math] Taka relacja jest symetryczna. Niech [math]S=\left\{ \left( 0,0\right) ,\left( 0,1\right) \right\}[/math] Natomiast relacja [math]S[/math] nie jest symetryczna, bo [math]\left( 0,1\right) \in S[/math], podczas gdy [math]\left( 1,0\right) \notin S.[/math]

Relacja symetryczna jest symetryczna względem przekątnej- zobacz ilustrację obok.

Niech [math]X[/math] będzie zbiorem, a [math]R[/math] relacją w tym zbiorze. Wtedy poniższe warunki są równoważne.

(1) [math]R[/math] jest symetryczna,

(2) [math]R=R ^{-1}.[/math]

Czyli [math]R[/math] jest symetryczna, równoważnie gdy jest równa swojej relacji odwrotnej.

Dowód:

[math](1) \rightarrow (2)[/math] Załóżmy, że [math]R[/math] jest symetryczna. Aby pokazać, że [math]R=R ^{-1},[/math] pokazujemy dwie inkluzję. Inkluzja w prawo: [math]R \subset R ^{-1}.[/math] Niech [math]\left( x,y\right) \in R.[/math] Wtedy ponieważ [math]R[/math] jest symetryczna, więc [math]\left( y,x\right) \in R,[/math] a więc z określenia relacji odwrotnej [math]\left( x,y\right) \in R ^{-1}.[/math] Zatem [math]R \subset R ^{-1}.[/math] Inkluzja w lewo: [math]R \supset R ^{-1}.[/math] Niech [math]\left( x,y\right) \in R ^{-1}.[/math] Wtedy z określenia relacji odwrotnej [math]\left( y,x\right) \in R.[/math] Ponieważ [math]R[/math] jest symetryczna, więc również [math]\left( x,y\right) \in R.[/math] Zatem [math]R \supset R ^{-1},[/math] i [math]R=R ^{-1}.[/math]

[math](2) \rightarrow (1)[/math] Załóżmy, że [math]R=R ^{-1}.[/math] Aby pokazać, że [math]R[/math] jest symetryczna, to niech [math]\left( x,y\right) \in R.[/math] Wtedy z założonej równości [math]\left( x,y\right) \in R ^{-1},[/math] a więc z określenia relacji odwrotnej [math]\left( y,x\right) \in R.[/math] Wnioskujemy, że [math]R[/math] jest symetryczna.[math]\square[/math]

Jako przykład zastosowania tego twierdzenia, wykażemy, że suma dwóch relacji symetrycznych na tym samym zbiorze jest relacją symetryczną.

Niech [math]X[/math] będzie zbiorem, a [math]R,S[/math] relacjami symetrycznymi w zbiorze [math]X[/math]. Wykażemy, że relacja [math]R \cup S[/math] jest relacją symetryczną.

Dowód:

Ponieważ [math]R,S[/math] są relacjami symetrycznymi, więc [math]R= R^{-1}[/math], i [math]S= S^{-1}.[/math] Wobec czego:

[math]\left( R \cup S\right) ^{-1}= R^{-1}\cup S^{-1}=R \cup S,[/math] czyli [math]\left( R \cup S\right) ^{-1}=R \cup S,[/math] a więc relacja [math]R \cup S[/math] jest symetryczna.[math]\square[/math]

Wykażemy, że w każdym niepustym skończonym podzbiorze [math]A\subset X[/math] liniowo uporządkowanego zbioru [math]\left( X,\le\right)[/math] jest element najmniejszy i największy.

Niech [math]\left( X, \le \right)[/math] będzie zbiorem liniowo uporządkowanym, a [math]A \subset X[/math] niepustym skończonym podzbiorem. Wykażemy, że w [math]A[/math] jest element najmniejszy i największy. Dowód poprowadzimy indukcyjnie ze względu na ilość elementów zbioru [math]A[/math].

Jeśli [math]A[/math] jest jednoelementowy, tzn. [math]A=\left\{ a\right\}[/math], to wtedy ten element [math]a[/math] jest jego elementem najmniejszym i największym.

Przypuśćmy, że twierdzenie zachodzi dla zbiorów [math]n[/math]-elementowych ([math]n \ge 1[/math]). Weźmy dowolny ([math]n+1[/math])-elementowy zbiór [math]A \subset X[/math]. Ustalmy [math]a\in A[/math]. Rozważmy [math]A \setminus\left\{ a\right\}[/math] jest to zbiór [math]n[/math]-elementowy, zatem możemy zastosować do niego założenie indukcyjne, i dostać jego element najmniejszy [math]b[/math] i największy [math]B[/math]. Wtedy ponieważ jesteśmy na zbiorze liniowo uporządkowanym, więc elementy [math]b[/math] i [math]a[/math] są porównywalne, i wtedy mniejszy z elementów [math]b[/math] i [math]a[/math] jest elementem najmniejszym [math]A[/math]( bo [math]b[/math] jest najmniejszy w [math]A \setminus\left\{ a\right\}[/math] ). Podobnie, większy z elementów [math]B[/math] i [math]a[/math] jest elementem największym [math]A[/math]. Dowolność zbioru [math]A[/math] kończy dowód kroku indukcyjnego, i cały dowód.[math]\square[/math]

Możemy podać oczywisty przykład zbioru uporządkowanego w którym każdy łańcuch posiada supremum.

Oczywistym przykładem jest dowolny skończony zbiór uporządkowany [math]\left( X, \le \right)[/math] w którym jest element najmniejszy [math]a[/math]. Pokażemy, że w zbiorze[math]X[/math] każdy łańcuch posiada supremum. Ustalmy dowolny łańcuch [math]A[/math]. Jeśli [math]A=\emptyset[/math], to ponieważ [math]a[/math] jest elementem najmniejszym w całym [math]X[/math], więc jest to supremum pustego łańcucha. Jeśli łańcuch [math]A[/math] jest niepusty, to ponieważ jest podzbiorem zbioru [math]X[/math]-zbioru skończonego, więc jest skończony. A w skończonym zbiorze niepustym liniowo uporządkowanym (bo jest to łańcuch, więc jest on liniowo uporządkowany przez dany porządek [math]\le[/math] ograniczony do elementów tego łańcucha) jest element największy. Ponieważ jest elementem największym łańcucha [math]A[/math], to tym bardziej jest jego supremum. [math]\square[/math]

W zbiorze uporządkowanym [math]\left( X, \le \right)[/math] zbiór [math]A \subset X[/math] nazywamy ograniczonym z góry, jeśli ma on w [math]X[/math] ograniczenie górne.

Podobnie zbiór [math]A \subset X[/math] nazwiemy ograniczonym z dołu, jeśli ma on ograniczenie dolne.

Wykażemy, że jeśli w zbiorze uporządkowanym [math]\left( X, \le \right)[/math] każdy niepusty podzbiór ograniczony z góry ma supremum, to każdy niepusty podzbiór ograniczony z dołu ma infimum.

Dowód( szkic):

Niech [math]\left( X, \le \right)[/math] będzie zbiorem uporządkowanym, w którym każdy niepusty podzbiór ograniczony z góry ma supremum. Pokażemy, że również każdy niepusty podzbiór ograniczony z dołu ma infimum. Niech [math]A \subset X[/math] będzie niepustym podzbiorem ograniczonym z dołu. Chcemy pokazać, że ma infimum. Rozważmy zbiór [math]B[/math] wszystkich ograniczeń dolnych [math]A[/math] (czyli zbiór na lewo od [math]A[/math]). Ponieważ [math]A[/math] jest ograniczony z dołu, więc ma ograniczenie dolne, stąd zbiór [math]B[/math] jest niepusty. Zbiór [math]B[/math] jest podzbiorem [math]X[/math] ograniczonym z góry przez elementy [math]A \neq \left\{ \right\}.[/math] Zatem, z założenia, [math]B[/math] ma supremum, i pokazujemy, że to supremum jest infimum zbioru [math]A[/math] (na prawo).[math]\square[/math] (Ilustracja taka sama jak przedtem).

Niech [math]X[/math] będzie zbiorem. Rozważmy rodzinę [math]\mathbb{B}[/math] wszystkich liniowych porządków na jakichkolwiek podzbiorach zbioru [math]X[/math], wraz z inkluzją. Ponieważ są to liniowe porządki na pewnych zbiorach [math]Y \subset X[/math], więc w szczególności relacje w tych zbiorach [math]Y \subset X[/math], więc łatwo się przekonać, że te relacje są podzbiorami [math]X \times X[/math] (więc są również relacjami w zbiorze [math]X[/math]), więc są podzbiorami ustalonego zbioru, więc inkluzja na takiej rodzinie zbiorów jest relacją porządku, stąd [math]\left( \mathbb{B}, \subset\right)[/math] jest zborem uporządkowanym. Liniowy porządek jest większy od danego gdy jest jego nadzbiorem, lub inaczej mówiąc gdy jest jego rozszerzeniem. Łatwo więc będzie pokazać, że również w [math]\left( \mathbb{B}, \subset\right)[/math] każdy niepusty łańcuch posiada supremum.

Niech [math]\mathbb{D} \subset \mathbb{B}[/math] będzie niepustym łańcuchem. Wtedy jeśli mamy dwa elementy [math]\mathbb{D}[/math], to są one liniowymi porządkami, i są porównywalne względem [math]\subset[/math] , a wiec jeden z nich jest rozszerzeniem drugiego, więc w myśl twierdzenia o sumie liniowych porządków( Zbiory uporządkowane pod koniec) relacja [math]\bigcup \mathbb{D}[/math] jest liniowym porządkiem na swoim polu, czyli na podzbiorze zbioru [math]X[/math]. Zatem [math]\bigcup \mathbb{D} \in \mathbb{B}[/math] Z własności sumy [math]\bigcup \mathbb{D}[/math] jest supremum względem inkluzji dla [math]\mathbb{D}.\square[/math] Zobacz ilustrację obok.

Niech [math]X[/math] będzie niepustym zbiorem. Rodzinę [math]\mathbb{B}[/math] podzbiorów [math]X[/math] nazywamy rozkładem (podziałem) zbioru [math]X[/math], gdy:

[math]1. \ A \neq \left\{ \right\} ,[/math] dla dowolnego [math]A \in \mathbb{B}. [/math]

[math]2. \ \bigcup \mathbb{B}=X,[/math]

[math]3. \ (A\in\mathbb{B}\wedge B\in\mathbb{B} \wedge A \neq B )\Longrightarrow A\cap B =\left\{ \right\}.[/math]

Czyli jest to rodzina zbiorów niepustych, których suma wynosi [math]X[/math], i tak, że każde dwa różne zbiory tej rodziny są rozłączne, (czyli wtedy [math]A\cap B =\left\{ \right\}[/math]- ich przekrój jest zbiorem pustym). Intuicyjnie jest to dowolne pokrojenie zbioru [math]X[/math] na kawałki- zobacz ilustracje obok.

Dla dowolnego niepustego zbioru [math]X[/math] przykładem jego rozkładu może być rodzina [math]\left\{ \left\{ x\right\}\Bigl| \ \ x\in X \right\}[/math] wszystkich zbiorów jednoelementowych( co łatwo sprawdzić). Jest to "najdrobniejszy" rozkład zbioru [math]X[/math]. Przy okazji zauważmy (prawdziwy) fakt, że dla dowolnego rozkładu [math]\mathbb{B}[/math] zbioru [math]X[/math] jego moc (ilość elementów [math]\mathbb{B}[/math]) jest co najwyżej taka jak moc zbioru [math]X[/math].

Niech [math]X[/math] będzie zbiorem. Relację [math]R[/math] w zbiorze [math]X[/math] nazywamy relacją równoważności, gdy jest zwrotna, symetryczna i przechodnia. Przypomnę, przechodniość oznacza, że jeśli [math](x,y)\in R [/math] oraz [math](y,z)\in R [/math], to [math](x,z)\in R.[/math]

Dobrym przykładem relacji równoważności na [math]X[/math] jest relacja równości, tzn. identyczność [math]I_X.[/math]

Jest zwrotna, bo zawsze [math](x,x)\in I_X [/math], gdyż zawsze [math]x=x.[/math]

Jest symetryczna, gdyż jeśli [math](x,y)\in I_X,[/math] to [math]x=y[/math], wtedy niewątpliwie [math]y=x[/math], a więc [math](y,x)\in I_X,[/math] a więc jest symetryczna.

Jest też przechodnia, gdyż jeśli [math](x,y)\in I_X [/math] oraz [math](y,z)\in I_X, [/math] to [math]x=y[/math], drugie założenie daje podobnie [math]y=z[/math], zatem [math]x=z[/math], a więc [math](x,z)\in I_X.[/math] A więc jest tez przechodnia, więc [math]I_X[/math] jest relacją równoważności.

Relacją równoważności na [math]X[/math] jest również [math]X\times X[/math] (rozpatrywane pary należą zawsze do [math]X\times X[/math]).

Niech [math]X,Y[/math] będą zbiorami. Wykażemy, że istnieje dokładnie jeden zbiór, który jest zbiorem wszystkich relacji między [math]X[/math] a [math]Y[/math]. Mamy dwa zbiory: [math]X[/math] i [math]Y[/math]. Możemy utworzyć ich iloczyn kartezjański- dokładnie jeden zbiór. Dla tego zbioru [math]X\times Y[/math] możemy utworzyć zbiór jego wszystkich podzbiorów [math]P \left( X\times Y\right)[/math]- dokładnie jeden zbiór. A zbiór wszystkich podzbiorów [math]X\times Y[/math], to zbiór wszystkich relacji między [math]X[/math] a [math]Y[/math] (z definicji relacji między dwoma zbiorami). Wykazaliśmy zatem, że dla dowolnych dwóch zbiorów istnieje dokładnie jeden zbiór- zbiór wszystkich relacji z pierwszego zbioru w drugi. W szczególności możemy mówić (gdy [math]X=Y[/math]) dla zbioru [math]X[/math], o zbiorze wszystkich relacji w zbiorze [math]X[/math]. Będzie do tego nawiązywało poniższe zadanie.

Niech [math]X[/math] będzie zbiorem. Zadajmy ciekawe pytania:

1. Czym jest zbiór wszystkich relacji równoważności na [math]X[/math], które są równocześnie relacjami porządku na [math]X[/math]?

2. Czym jest zbiór wszystkich relacji równoważności na [math]X[/math], które są równocześnie funkcjami z [math]X[/math] do [math]X[/math]?

3. Czym jest zbiór wszystkich relacji porządku na [math]X[/math], które są równocześnie funkcjami z [math]X[/math] do [math]X[/math]?

Odpowiedzią na każde z trzech pytań jest: jest to zbiór jednoelementowy złożony z relacji identyczności [math]I_X.[/math]

Jak wykazaliśmy relacja [math]I_X[/math] jest relacją równoważności, jest też relacją porządku, jest też funkcją z [math]X[/math] do [math]X[/math]. Pozostaje wykazać, że nie ma innych takich relacji( na każde z trzech pytań odpowiemy oddzielnie).

1. Przypuśćmy, że istnieje relacja równoważności [math]R\neq I_X[/math] na [math]X[/math], będąca relacją porządku na [math]X[/math]. Ponieważ [math]R[/math] nie jest relacją identyczności, więc ma w sobie parę [math](x,y)[/math], gdzie [math]x\neq y[/math]. Relacja ta, jako relacja równoważności, jest symetryczna, a więc [math](y,x)\in R.[/math] Jednak ponieważ jest relacją porządku, więc jest też antysymetryczna, więc ponieważ [math](x,y)\in R [/math] i [math](y,x)\in R [/math], więc [math]x=y[/math]- sprzeczność.

2. Przypuśćmy, że istnieje relacja równoważności [math]R\neq I_X[/math] na [math]X[/math], będąca funkcją z [math]X[/math] do [math]X[/math]. Ponieważ [math]R[/math] nie jest relacją identyczności, więc ma w sobie parę [math](x,y)[/math], gdzie [math]x\neq y[/math]. Jako relacja równoważności jest zwrotna, a więc [math](x,x)\in R.[/math] Ponieważ jest to funkcja, a [math](x,x)\in R,[/math] i [math](x,y)\in R,[/math] więc [math]x=y[/math]-sprzeczność.

3. Przypuśćmy, że istnieje relacja porządku [math]R\neq I_X[/math] na [math]X[/math], będąca funkcją z [math]X[/math] do [math]X[/math]. Ponieważ [math]R[/math] nie jest relacją identyczności, więc ma w sobie parę [math](x,y)[/math], gdzie [math]x\neq y[/math]. [math]R[/math] jako relacja porządku jest zwrotna, więc [math](x,x)\in R.[/math]. Ponieważ jest to funkcja, a [math](x,x)\in R,[/math] i [math](x,y)\in R,[/math] więc [math]x=y[/math]-sprzeczność.

Zatem na każde z trzech pytań odpowiedź jest taka sama: jest to [math]\left\{I_X \right\}.[/math]

Relację [math] f\subset X×Y[/math] nazywamy funkcją częściową ze zbioru [math] X[/math] w zbiór [math] Y[/math] , gdy dla dowolnych [math] x\in X, y_1,y_2\in Y[/math] zachodzi:

[math](x,y_1)\in f\wedge (x,y_2)\in f \Longrightarrow y_1=y_2.[/math]

Czyli jest to funkcja na dowolnym podzbiorze zbioru [math] X [/math]. Częściowość oznacza, że nie koniecznie cały zbiór [math] X [/math] musi być jej dziedziną, może być nią dowolny podzbiór zbioru [math] X.[/math]

Każda funkcja częściowa z [math] X[/math] do [math] Y[/math] jest funkcją że zbioru [math]f_L [/math] w zbiór [math] Y[/math]( co wynika wprost z definicji funkcji między zbiorami), czy nawet jest funkcją że zbioru [math] f_L[/math] w zbiór [math] f_P[/math]. Dla dowolnych zbiorów [math] X,Y[/math] każda relacja, która jest funkcją że zbioru [math] X[/math] w zbiór [math] Y[/math] jest funkcją częściową z [math] X[/math] do [math] Y[/math] (nieistotną,uzasadnienie wynika wprost z definicji funkcji między zbiorami, i definicji funkcji częściowej między dwoma zbiorami).

Przykłady: Niech [math](X,\le) [/math] będzie zbiorem uporządkowanym. Wtedy relacja [math] f[/math] z [math] P(X)[/math] w [math]X [/math]:

[math] A(f)a\Longleftrightarrow a [/math] jest elementem najmniejszym [math] A[/math] względem [math]\le,[/math]

jest funkcją częściową (przypisuje bowiem podzbiorowi [math] X[/math] jego element najmniejszy, a wiemy, że zawsze istnieje co najwyżej jeden element najmniejszy). Jeśli bowiem, [math] (A,a), (A,b)\in f[/math], to [math]a [/math] jest elementem najmniejszym [math] A[/math], i podobnie [math] b[/math] jest elementem najmniejszym [math] A[/math], zatem [math]a=b.[/math] Zatem jest to funkcja częściowa.

Jeszcze jeden podobny przykład. Niech [math] (X,\le)[/math] będzie zbiorem uporządkowanym. Niech [math]\mathbb{B}[/math] będzie rodziną wszystkich łańcuchów w [math] X[/math]. Rozważmy relację [math] f[/math] z [math]\mathbb{B}[/math] do [math]X:[/math]

[math](A,x)\in f \Longleftrightarrow[/math] gdy element [math] x[/math] jest supremum łańcucha [math] A[/math].

Czyli łańcuchowi przypisujemy jego supremum.

Jest to funkcja częściowa, gdyż supremum jest zawsze jedyne( gdyż jest to pewnego rodzaju element najmniejszy ). A jeśli w [math](X,\le) [/math] każdy łańcuch posiada supremum(mamy na to przykłady), to wtedy [math] f[/math] jest nawet funkcją z [math]\mathbb {B} [/math] do [math] X.[/math]

Niech [math]X,Y[/math] będą zbiorami. Niech [math]S[/math] będzie zbiorem złożonym z funkcji częściowych z [math] X[/math] do [math] Y[/math] takim, że dla dowolnych dwóch funkcji częściowych w [math] S[/math] jedna jest rozszerzeniem drugiej (czyli funkcje na tych samych argumentach przyjmują zawsze te same wartości ). Wtedy [math] \bigcup S[/math] jest funkcją częściową z [math] X [/math] do [math] Y[/math].

Dowód: Oczywiście, suma funkcji częściowych, a więc suma relacji z [math] X[/math] do [math] Y[/math] jest relacją z [math]X [/math] do [math] Y[/math]. Aby pokazać, że jest to funkcja częściowa, to niech [math](x,y_1),(x,y_2)\in\bigcup S.[/math] Pokażemy, że [math] y_1=y_2.[/math] Ponieważ [math] (x,y_1)\in\bigcup S,[/math] więc [math](x,y_1)\in f_1[/math] dla pewnej relacji [math]f_1\in S.[/math] Podobnie, [math] (x,y_2)\in f_2,[/math] dla pewnej relacji [math] f_2\in S.[/math] Relacje [math] f_1,f_2[/math] są funkcjami częściowymi, i jedna z nich jest rozszerzeniem drugiej, więc na tych samych argumentach przyjmują te same wartości, więc ponieważ [math] f_1(x)=y_1, f_2(x)=y_2,[/math] a więc [math] y_1=y_2.\square[/math]

Przykłady użycia tego faktu podamy później. Kolejny prosty fakt:

Funkcja różnowartościowa a funkcja częściowa

Dla dowolnych zbiorów [math] X,Y[/math] oraz funkcji [math] f:X\rightarrow Y[/math] mamy, że [math]f[/math] jest różnowartościowa, wtedy i tylko wtedy, gdy relacja odwrotna [math] f^{-1}[/math] jest funkcją częściową z [math]Y[/math] do [math] X.[/math] Zobacz ilustrację obok.

Dowód:

Niech [math] f:X\rightarrow Y.[/math] Dowiedziemy równoważne twierdzenie, że [math] f[/math] nie jest różnowartościowa, wtedy i tylko wtedy, gdy relacja odwrotna [math]f^{-1}[/math] nie jest funkcją częściową z [math]Y[/math] do [math] X.[/math]

Przypuśćmy, że [math]f[/math] nie jest różnowartościowa. Jest to równoważne temu, że istnieją różne elementy [math] x_1,x_2\in X[/math] oraz element [math]y\in Y[/math] takie, ze [math](x_1,y)\in f[/math] i [math] (x_2,y)\in f.[/math] Co jest równoważne temu (z określenia relacji odwrotnej), że [math] (y,x_1)\in f^{-1}[/math] i [math] (y,x_2)\in f^{-1},[/math] co wobec różności elementów [math]x_1,x_2[/math] jest równoważne temu, że [math] f^{-1}[/math] nie jest funkcją częściową z [math]Y[/math] do [math]X.\square [/math]