--- title: "Relacje" lecture_number: 3 has_solutions: true has_exercises: true --- ```{include} ../_includes/sagecell-loader.md ``` # Relacje ## Relacje binarne :::{narration} Niech $X, Y$ będą ustalonymi zbiorami. ::: :::{prf:definition} **Relacją binarną** {index}`relacja` (dwuargumentową) między elementami zbioru $X$ a elementami zbioru $Y$ nazywamy dowolny podzbiór ```{math} R\subseteq X \times Y. ``` Element $x\in X$ jest **w relacji** $R$ z elementem $y\in Y$, gdy ```{math} (x,y) \in R \qquad \text{co zapisujemy jako} \qquad xRy. ``` Jeśli $X=Y$, to mówimy, że relacja $R\subseteq X\times X$ jest {index}`relacja; w zbiorze` **określona w zbiorze** $X .$ ::: :::{prf:example} :label: lec-03-example-01 1. {index}`relacja; pusta`**Relacja pusta** w dowolnym zbiorze $X$: ```{math} \emptyset \ \subseteq\ X \times X. ``` 2. {index}`relacja; pełna`**Relacja pełna** w dowolnym zbiorze $X$: ```{math} F \ = \ X \times X. ``` 3. {index}`relacja; podzielności`**Relacja podzielności** w zbiorze liczb $\nn$: ```{math} \mid \ = \ \Set{(x,y)\in \nn\times \nn : \exists k\in \nn\ \ y=k\cdot x}. ``` 4. Dla ustalonego $n\in \nn$, **relacja przystawania modulo $n$** w zbiorze $\zz$: ```{math} \equiv_n \ = \ \Set{(z_1,z_2)\in \zz\times \zz : n\mid(z_1-z_2)}. ``` 5. **Relacja równoważności formuł** w zbiorze formuł rachunku zdań: ```{math} T \ = \ \Set{(\alpha,\beta)\in X\times X : \alpha \imply\beta \ \text{i}\ \beta \imply\alpha \ \text{są tautologiami}}. ``` 6. {index}`relacja; mniejszości`**Relacja mniejszości** w zbiorze $\rr$: ```{math} \leq \ = \ \Set{(x,y)\in \rr\times \rr : x\leq y}. ``` ::: ## Własności relacji :::{prf:definition} Relację $R \subseteq X \times X$ nazywamy: - {index}`relacja; zwrotna`**zwrotną**, jeśli $\forall x \in X \quad xRx$; - {index}`relacja; symetryczna`**symetryczną**, jeśli $\forall x,y \in X \quad xRy \Rightarrow yRx$; - {index}`relacja; przechodnia`**przechodnią**, jeśli $\forall x,y,z \in X \quad xRy \wedge yRz \Rightarrow xRz$; - {index}`relacja; antysymetryczna`**antysymetryczną**, jeśli $\forall x,y \in X \quad xRy \wedge yRx \Rightarrow x=y .$ ::: :::{prf:example} - Relacje zwrotne: $=,\ \leq,\ \mid,\ \subseteq .$ - Relacje symetryczne: $=$, równoległość prostych na płaszczyźnie. - Relacje przechodnie: $=,\ \leq,\ \subseteq,\ \mid .$ - Relacje antysymetryczne: $\leq,\ \subseteq,\ \mid .$ ::: ::::{exercise} :label: m-lec-03-ex-01 :class: [exercise] Sprawdźmy, które z własności (zwrotność, symetria, przechodniość, antysymetria) ma relacja $R\subseteq \rr\times\rr$ zadana wzorem ```{math} xRy \qlq |x-y|\leq 1. ``` :::: :::{solution-without-reference} :class: [solution] dropdown - Zwrotna: $|x-x|=0\leq 1$ dla każdego $x\in\rr$ -- tak. - Symetryczna: $|x-y|=|y-x|$, więc jeśli $|x-y|\leq 1$ to i $|y-x|\leq 1$ -- tak. - Przechodnia: nie, np. $0R1$ i $1R2$, ale $|0-2|=2 > 1$, więc $\Negation(0R2) .$ - Antysymetryczna: nie, np. $0R1$ i $1R0$, choć $0\neq 1 .$ ::: ## Relacja równoważności :::{prf:definition} Relację $R \subseteq X \times X$ nazywamy {index}`relacja równoważności`**relacją równoważności**, jeśli jest zwrotna, symetryczna i przechodnia. ::: ::::{prf:example} Przykłady relacji równoważności 1. W dowolnym zbiorze $X .$ Relacja pełna $F=X \times X .$ 2. W zbiorze $\zz$, relacja przystawania $\equiv_n$ modulo $n .$ 3. W zbiorze formuł rachunku zdań, relacja $T .$ 4. W dowolnym zbiorze $X .$ Relacja równości $=\ \subseteq X\times X .$ 5. W zbiorze prostych na płaszczyźnie. Relacja równoległości prostych. :::: :::{exercise} :class: [exercise] Sprawdźmy, że relacje $\equiv_n$ i $T$ z {prf:ref}`lec-03-example-01` są relacjami równoważności. ::: :::{solution-without-reference} :class: [solution] dropdown 1. Relacja $\equiv_n \ = \ \Set{(z_1,z_2)\in \zz\times \zz : n\mid(z_1-z_2)}$: - zwrotność: $\forall x \in \zz \quad x-x = 0 = n \cdot 0 \implies n \mid (x-x) \implies x \equiv_n x$ - symetria: $\forall x,y \in \zz \quad x \equiv_n y \implies n \mid (x-y) \implies x-y = nk \implies y-x = n(-k) \implies n \mid (y-x) \implies y \equiv_n x$ - przechodniość: $\forall x,y,z \in \zz \quad (x \equiv_n y \wedge y \equiv_n z) \implies (n \mid (x-y) \wedge n \mid (y-z)) \implies x-z = (x-y)+(y-z) = nk+nm = n(k+m) \implies n \mid (x-z) \implies x \equiv_n z$ 2. Relacja $T \ = \ \Set{(\alpha,\beta)\in X\times X : \alpha \imply\beta \ \text{i}\ \beta \imply\alpha \ \text{są tautologiami}}$: - zwrotność: $\forall \alpha \in X \quad \alpha \imply \alpha$ jest prawem logiki (tautologią), zatem $\alpha T \alpha$ - symetria: $\forall \alpha,\beta \in X \quad \alpha T \beta \implies (\alpha \imply \beta \text{ oraz } \beta \imply \alpha \text{ są taut.}) \implies (\beta \imply \alpha \text{ oraz } \alpha \imply \beta \text{ są taut.}) \implies \beta T \alpha$ - przechodniość: $\forall \alpha,\beta,\gamma \in X \quad (\alpha T \beta \wedge \beta T \gamma) \implies (\alpha \imply \beta, \beta \imply \alpha, \beta \imply \gamma, \gamma \imply \beta \text{ są taut.}) .$ Z przechodniości implikacji $[(p \imply q) \wedge (q \imply r)] \imply (p \imply r)$ wynika, że $\alpha \imply \gamma$ oraz $\gamma \imply \alpha$ są tautologiami, zatem $\alpha T \gamma$ W obu przypadkach zachodzą wszystkie trzy warunki, więc $\equiv_n$ oraz $T$ są relacjami równoważności. ::: ### Klasy abstrakcji i zbiór ilorazowy :::{narration} Niech $R \subseteq X \times X$ będzie relacją równoważności i niech $a\in X .$ ::: :::{prf:definition} Zbiór ```{math} [a]_R = \Set{x \in X : x R a} ``` nazywamy {index}`klasa abstrakcji`**klasą abstrakcji** elementu $a$ (względem relacji $R$). Element $a$ nazywamy wtedy **reprezentantem** {index}`klasa abstrakcji; reprezentant` tej klasy. ::: :::{prf:example} Dla relacji równoważności zdefiniowanych w {prf:ref}`lec-03-example-01`. 1. $[a]_{=} = \Set{x \in X : x=a} = \Set{a} .$ 2. $[a]_F = \Set{x \in X : xFa} = X .$ 3. $[a]_{\equiv_n} = \Set{z \in \zz : z \equiv_n a} = \Set{z \in \zz : n\mid(z-a)}= \Set{a+k n : k \in \zz} .$ 4. $[\alpha\vee \Negation\alpha]_T$ -- klasa dowolnej tautologii $\alpha\vee\Negation\alpha$ względem relacji $T$ z poprzedniego przykładu to zbiór wszystkich tautologii. ::: :::{prf:definition} Zbiór wszystkich klas abstrakcji relacji równoważności $R\subseteq X\times X$ ```{math} X/_R=\Set{[a]_R : a\in X} ``` nazywamy {index}`zbiór ilorazowy`**zbiorem ilorazowym** relacji $R .$ ::: :::{prf:example} - $\zz_n := \zz/_{\equiv_n}=\Set{[0]_{\equiv_n},[1]_{\equiv_n},\ldots,[n-1]_{\equiv_n}} .$ - $X/_F=\Set{[x]_F} = \Set{X}$ (dla relacji pełnej $F$ -- jedna klasa). - $X/_==\Set{\Set{x} : x\in X}$ (dla relacji równości -- klasy jednoelementowe). ::: ::::{exercise} :label: m-lec-03-ex-02 :class: [exercise] Sprawdźmy, że relacja $$ xRy \qlq x^2=y^2 $$ jest relacją równoważności w zbiorze $\rr$, i znajdźmy jej klasy abstrakcji oraz zbiór ilorazowy $\rr/_R .$ :::: :::{answer} :class: [solution] dropdown Zwrotność, symetria i przechodniość wynikają natychmiast z odpowiednich własności równości liczb. Dla $a\in \rr$ mamy ```{math} [a]_R = \Set{x\in \rr : x^2=a^2} = \begin{cases} \Set{-a,a}, & a\neq 0 \\ \Set{0}, & a = 0. \end{cases} ``` Zatem $\rr/_R = \Set{\Set{-a,a} : a\geq 0}$ -- każda klasa (poza $\Set{0}$) ma dokładnie dwóch reprezentantów. ::: :::{prf:theorem} Dla dowolnej relacji równoważności $R\subseteq X\times X$ i dowolnych $a,b\in X$: 1. $a \in [a]_R$; 2. $[a]_R = [b]_R \ \vee\ [a]_R \cap [b]_R = \emptyset$ 3. $\displaystyle\bigcup_{a \in X} [a]_R = X$ 4. $[a]_R = [b]_R \Leftrightarrow a R b .$ ::: ### Podział zbioru :::{prf:definition} **Podziałem** {index}`podział zbioru` zbioru $X$ nazywamy rodzinę $\mathcal{A}=(A_i)_{i\in I}$ podzbiorów zbioru $X$ taką, że: 1. $\forall i \in I \quad A_i \subseteq X$ 2. $\forall i \in I \quad A_i \neq \emptyset$ 3. $\forall i,j \in I \quad i\neq j \Rightarrow A_i \cap A_j = \emptyset$ 4. $\displaystyle\bigcup_{i \in I} A_i = X .$ ::: :::{prf:example} - $L$ -- zbiór ludzi, $A_1\subseteq L$ -- zbiór kobiet, $A_2\subseteq L$ -- zbiór mężczyzn; wówczas $(A_1,A_2)$ jest podziałem $L .$ - $\zz$ -- zbiór liczb całkowitych, $A_i=\Set{3z+i : z \in \zz}$, dla $i\in I=\Set{0,1,2}$; wówczas $(A_i)_{i\in I}$ jest podziałem $\zz .$ - $\mathcal{X}=2^{\Set{1,\ldots,n}}$, $A_k=\Set{Y\in \mathcal{X} : |Y|=k}$, dla $k\in I=\Set{0,\ldots,n}$; wówczas $(A_k)_{k\in I}$ jest podziałem $\mathcal{X} .$ ::: :::{prf:theorem} Niech $X\neq \emptyset .$ 1. Jeżeli $R\subseteq X\times X$ jest relacją równoważności, to zbiór ilorazowy $X/_{R}$ jest podziałem zbioru $X .$ 2. Jeżeli $\mathcal{A}=(A_i)_{i\in I}$ jest podziałem zbioru $X$, to relacja $R_{\mathcal{A}}\subseteq X\times X$ określona warunkiem ```{math} xR_{\mathcal{A}} y \qlq \exists i\in I\ \ x,y\in A_i ``` jest relacją równoważności. ::: :::{narration} Innymi słowy, podziały zbioru $X$ i relacje równoważności na $X$ to -- z dokładnością do powyższego przyporządkowania -- to samo pojęcie. ::: :::{prf:remark} Ta obserwacja pozwala konstruować nowe zbiory liczbowe jako zbiory ilorazowe. Na przykład: - w zbiorze $\nn\times\nn$ relacja $$ (p,q)\sim(k,l) \qlq p+l=q+k $$ jest relacją równoważności, a zbiór ilorazowy $(\nn\times\nn)/_\sim$ utożsamiamy ze zbiorem $\zz$ (klasę pary $(p,q)$ oznaczamy jako różnicę $p-q$) - w zbiorze $\zz\times(\zz\setminus\Set{0})$ relacja $$ (p,q)\,\varrho\,(k,l) \qlq p\cdot l=q\cdot k $$ jest relacją równoważności, a zbiór ilorazowy utożsamiamy ze zbiorem $\qq$ (klasę pary $(p,q)$ oznaczamy jako ułamek $\frac p q$). ::: ## Relacje porządkujące :::{prf:definition} Relację $\preceq \subseteq P \times P$ nazywamy {index}`porządek częściowy`**porządkiem częściowym**, jeśli jest zwrotna, antysymetryczna i przechodnia. Parę $(P,\preceq)$ nazywamy wtedy {index}`zbiór częściowo uporządkowany`**zbiorem częściowo uporządkowanym** (**posetem**). Jeżeli w $(P,\preceq)$, dla elementów $x, y \in P$ $$ x\preceq y, $$ to mówimy, że $x$ jest **mniejszy** od $y$ lub **poprzedza** $y$, a $y$ jest **większy** od $x$ lub **następuje po** $y .$ ::: ::::{prf:example} Przykłady posetów :::{container} columns-3-auto 1. $(\rr, \leq)$ 2. $(2^{X}, \subseteq)$ 3. $(\nn, \mid)$ ::: 4. $(\rr\times\rr,\preceq)$, gdzie $$ (x,y)\preceq (a,b) \qlq x\leq a \wedge y\leq b $$ -- porządek **produktowy**. 5. $(\rr\times\rr,\preceq)$, gdzie $$ (x,y)\preceq (a,b) \qlq x< a \vee (x=a \wedge y\leq b) $$ -- porządek **leksykograficzny**. :::: :::{exercise} :class: [exercise] Sprawdźmy, że relacje $\leq$ i $\mid$ z {prf:ref}`lec-03-example-01` są relacjami częściowego porządku. ::: :::{solution-without-reference} :class: [solution] dropdown 1. Relacja mniejszości $\leq \ = \ \Set{(x,y)\in \mathbb{R} \times \mathbb{R} : x \leq y}$: - zwrotność: $\forall x \in \mathbb{R} \quad x = x \implies x \leq x$ - antysymetria: $\forall x,y \in \mathbb{R} \quad (x \leq y \wedge y \leq x) \implies x = y$ (wynika bezpośrednio z własności porządku liczb rzeczywistych) - przechodniość: $\forall x,y,z \in \mathbb{R} \quad (x \leq y \wedge y \leq z) \implies x \leq z$ 2. Relacja podzielności $\mid \ = \ \Set{(x,y)\in \mathbb{N} \times \mathbb{N} : \exists k\in \mathbb{N} \quad y = k \cdot x}$: - zwrotność: $\forall x \in \mathbb{N} \quad x = 1 \cdot x \wedge 1 \in \mathbb{N} \implies x \mid x$ - antysymetria: $\forall x,y \in \mathbb{N} \quad (x \mid y \wedge y \mid x) \implies (y = kx \wedge x = my) \implies x = m(kx) \implies x = (mk)x \implies mk = 1.$ Ponieważ $m,k \in \mathbb{N}$, to $m=k=1$, zatem $x = y$ - przechodniość: $\forall x,y,z \in \mathbb{N} \quad (x \mid y \wedge y \mid z) \implies (y = kx \wedge z = my) \implies z = m(kx) = (mk)x .$ Ponieważ $mk \in \mathbb{N}$, to $x \mid z$ W obu przypadkach zachodzą warunki zwrotności, antysymetrii i przechodniości, więc $\leq$ oraz $\mid$ są relacjami częściowego porządku. ::: :::{prf:definition} Elementy $x,y\in P$ nazywamy {index}`element; porównywalny`**porównywalnymi** (ozn. $x\sim y$), jeśli $$ x\preceq y \vee y\preceq x. $$ W przeciwnym przypadku nazywamy je **nieporównywalnymi** (ozn. $x\parallel y$). ::: ### Diagram Hassego :::{prf:definition} **Diagramem Hassego** {index}`diagram Hassego` nazywamy graficzną reprezentację zbioru częściowo uporządkowanego $(P,\preceq)$, w której: - wierzchołki grafu odpowiadają elementom zbioru $P$ - jeśli $x\neq y$ i $x \preceq y$, to wierzchołek $x$ rysujemy niżej niż wierzchołek $y$ - dwa wierzchołki $x\neq y$ łączymy krawędzią wtedy i tylko wtedy, gdy $x$ **bezpośrednio poprzedza** $y$, tzn. ```{math} x \preceq y \ \wedge\ \Negation\bigl(\exists z\ \ z\neq x \wedge z\neq y \wedge x \preceq z \preceq y\bigr). ``` ::: :::{prf:example} :label: lec-03-example-08 Poniższy diagram obrazuje pewien poset $\Paren{\Set{1,2,3,4,5,6,7}, \preceq} .$ ```{tikz} \begin{tikzpicture}[scale=3, >=stealth, elem/.style={draw, circle, fill=white, inner sep=0pt, minimum size=14mm, font=\Large}] \path (-0.5,-0.5) rectangle (2.5,3.5); \node[elem] (n1) at (1,0) {1}; \node[elem] (n2) at (2,0) {2}; \node[elem] (n3) at (0,1) {3}; \node[elem] (n4) at (1,1) {4}; \node[elem] (n5) at (2,1) {5}; \node[elem] (n6) at (2,2) {6}; \node[elem] (n7) at (2,3) {7}; \node[elem] (n8) at (0,3) {8}; \draw (n1) -- (n3); \draw (n1) -- (n4); \draw (n1) -- (n5); \draw (n2) -- (n3); \draw (n2) -- (n5); \draw (n3) -- (n7); \draw (n3) -- (n8); \draw (n4) -- (n6); \draw (n5) -- (n6); \draw (n6) -- (n7); \draw (n6) -- (n8); \end{tikzpicture} ``` Wynika z niego na przykład, że: $2 \preceq 3 \preceq 8$, zaś $7$ i $8$ NIE są ze sobą w relacji -- są elementami nieporównywalnymi. ::: ### Elementy wyróżnione :::{narration} Niech $(P,\preceq)$ będzie zbiorem częściowo uporządkowanym. ::: :::{prf:definition} Element $a \in P$ nazywamy: - {index}`element maksymalny`**maksymalnym**, jeśli $\Negation\bigl(\exists x\in P\ \ a\neq x \wedge a\preceq x\bigr)$ - {index}`element minimalny`**minimalnym**, jeśli $\Negation\bigl(\exists x\in P\ \ a\neq x \wedge x\preceq a\bigr)$ - {index}`element największy`**największym**, jeśli $\forall x\in P \ \ x \preceq a$ - {index}`element najmniejszy`**najmniejszym**, jeśli $\forall x\in P \ \ a \preceq x .$ ::: :::{prf:remark} 1. Jeśli w zbiorze $(P,\preceq)$ istnieje element największy (najmniejszy), to jest on jedynym elementem maksymalnym (minimalnym). 2. W zbiorze $(P,\preceq)$ istnieje co najwyżej jeden element największy i co najwyżej jeden element najmniejszy. ::: :::{prf:example} 1. W posecie opisanym diagramem w {prf:ref}`lec-03-example-08`: - elementy minimalne to $1$ i $2$ -- brak elementu najmniejszego (bo $1$ i $2$ są nieporównywalne) - elementy maksymalne to $7$ i $8$ -- brak elementu największego. 2. W posecie $(\nn, \mid)$: - $1$ jest elementem minimalnym i zarazem najmniejszym - nie ma elementów maksymalnych, a zatem największego. 3. W posecie $(\nn_2 = \nn\setminus\Set{1}, \mid)$: - każda liczba pierwsza jest elementem minimalnym, więc nie ma elementu najmniejszego - nie ma elementów maksymalnych, a zatem największego. ::: ### Ograniczenia i kresy :::{narration} Niech $(P,\preceq)$ będzie zbiorem częściowo uporządkowanym i niech $X\subseteq P .$ ::: :::{prf:definition} Element $a\in P$ jest {index}`ograniczenie górne`**ograniczeniem górnym** zbioru $X$, jeśli ```{math} \forall x \in X \quad x \preceq a. ``` Element $b\in P$ jest {index}`ograniczenie dolne`**ograniczeniem dolnym** zbioru $X$, jeśli ```{math} \forall x \in X \quad b \preceq x. ``` Zbiory wszystkich ograniczeń górnych i dolnych $X$ oznaczamy odpowiednio ```{math} \begin{aligned} X^* & = \Set{a \in P : \forall x\in X\ x \preceq a}, \\ X_* & = \Set{a \in P : \forall x\in X\ a \preceq x}. \end{aligned} ``` Element $a\in P$ jest {index}`kres górny`**kresem górnym** zbioru $X$ (ozn. $\sup X$), jeśli jest elementem najmniejszym w zbiorze $(X^*,\preceq) .$ Element $a\in P$ jest {index}`kres dolny`**kresem dolnym** zbioru $X$ (ozn. $\inf X$), jeśli jest elementem największym w zbiorze $(X_*,\preceq) .$ ::: :::{prf:example} 1. W posecie opisanym diagramem w {prf:ref}`lec-03-example-08`: ```{math} \begin{aligned} \Set{3}^* & = \Set{3,7,8}, & \Set{3}_* & = \Set{1,2,3}, \\ \Set{4}^* & = \Set{4,6,7,8}, & \Set{4}_* & = \Set{1,4}. \end{aligned} ``` Dla $X=\Set{3,4}$ mamy $X^* = \Set{3,7,8}\cap\Set{4,6,7,8} = \Set{7,8} .$ Ponieważ $7$ i $8$ są nieporównywalne, zbiór $(X^*,\preceq)$ nie ma elementu najmniejszego, więc **$\sup X$ nie istnieje**. Z drugiej strony $X_* = \Set{1,2,3}\cap\Set{1,4} = \Set{1}$, a więc **$\inf X = 1$**. 2. W posecie $(\nn,\mid)$, dla $X=\Set{6,8,12}$, mamy $\sup X = \mathrm{NWW}(6,8,12)=24$ oraz $\inf X = \NWD(6,8,12)=2 .$ 3. W posecie $(2^{X},\subseteq)$, dla rodziny $\mathcal{C}=\Set{A_i\subseteq X : i\in I}$, mamy ```{math} \sup \mathcal{C}=\bigcup_{i \in I}A_i, \qquad \inf \mathcal{C}=\bigcap_{i \in I}A_i. ``` ::: ::::{exercise} :label: m-lec-03-ex-04 :class: [exercise] Korzystając z diagramu Hassego z poprzedniego punktu, znajdźmy $\Set{4,5}^*$, $\Set{4,5}_*$ oraz -- o ile istnieją -- $\sup\Set{4,5}$ i $\inf\Set{4,5} .$ :::: :::{answer} :class: [solution] dropdown ```{math} \begin{aligned} \Set{4,5}^* & = \Set{4,6,7,8}\cap\Set{5,6,7,8} = \Set{6,7,8}, \\ \Set{4,5}_* & = \Set{1,4}\cap\Set{1,2,5} = \Set{1}. \end{aligned} ``` Ponieważ $6$ jest najmniejszym elementem zbioru $\Set{6,7,8}$ (bo $6\preceq 7$ i $6 \preceq 8$), to $\sup\Set{4,5}=6 .$ Zbiór $\Set{4,5}_*=\Set{1}$ ma jeden element, więc $\inf\Set{4,5}=1 .$ ::: ### Łańcuchy i antyłańcuchy :::{prf:definition} Podzbiór $C \subseteq P$ nazywamy {index}`łańcuch`**łańcuchem**, jeśli ```{math} \forall x,y \in C \quad x\sim y. ``` Podzbiór $D \subseteq P$ nazywamy {index}`antyłańcuch`**antyłańcuchem**, jeśli ```{math} \forall x,y \in D \quad x\parallel y. ``` ::: :::{prf:example} W posecie opisanym diagramem w {prf:ref}`lec-03-example-08`: - ciąg $2\preceq 5\preceq 6 \preceq 7$ tworzy **łańcuch** - zbiór $\Set{3,4,5}$ jest **antyłańcuchem** (elementy $3,4,5$ są parami nieporównywalne). ::: :::{prf:proposition} W skończonym, niepustym zbiorze częściowo uporządkowanym istnieje element maksymalny i element minimalny. ::: :::{narration} To dość oczywiste stwierdzenie przestaje być oczywisty dla zbiorów nieskończonych. Jego uogólnieniem jest poniższy, fundamentalny dla matematyki lemat. ::: :::{prf:theorem} Lemat Kuratowskiego--Zorna :label: lemat-kuratowskiego-zorna Jeżeli $(P,\preceq)$ jest niepustym zbiorem częściowo uporządkowanym, w którym każdy łańcuch $C\subseteq P$ ma ograniczenie górne (tzn. $C^*\neq\emptyset$), to w zbiorze $(P,\preceq)$ istnieje element maksymalny. Analogicznie, jeśli każdy łańcuch ma ograniczenie dolne, to istnieje element minimalny. ::: :::{prf:remark} 1. Lemat Kuratowskiego--Zorna jest **równoważny aksjomatowi wyboru** (a więc sam bywa przyjmowany jako aksjomat teorii mnogości) -- jego dowodu nie da się przeprowadzić bez odwołania się do niego lub równoważnego mu stwierdzenia. 2. Lemat ten jest podstawowym narzędziem dowodzenia istnienia obiektów maksymalnych, których nie potrafimy skonstruować jawnie -- np. istnienia bazy w dowolnej przestrzeni wektorowej (także nieskończenie wymiarowej) czy istnienia ideału maksymalnego w pierścieniu z jedynką. ::: (funkcja-jako-relacja)= ## Funkcja jako relacja :::{prf:remark} Funkcję $f\colon X\to Y$ możemy formalnie utożsamić z relacją $f\subseteq X\times Y$ spełniającą warunek ```{math} \forall x\in X\ \exists! y\in Y \quad (x,y)\in f, ``` czyli relacją **jednoznaczną** (każdemu $x$ odpowiada co najwyżej jeden $y$) i **określoną na całym $X$** (każdemu $x$ odpowiada co najmniej jeden $y$). :::