Logika i teoria mnogości/Wykład 6: Funkcje, tw. o faktoryzacji, produkt uogólniony, obrazy i przeciwobrazy, tw. Knastera-Tarskiego i lemat Banacha

Wprowadzenie

W poniższym wykładzie wprowadzamy formalnie pojęcie funkcji. Bardzo duży fragment współczesnej matematyki dotyczy właśnie badania własności funkcji. W teorii zbiorów funkcje są relacjami, które spełniają dodatkowy warunek jednoznaczności. Każda funkcja jest więc zbiorem par. W teorii zbiorów, której pojęciem pierwotnym jest należenie do zbioru, reprezentowanie funkcji za pomocą zbiorów jest pewną koniecznością. W praktyce jednak patrzymy na funkcje raczej jako na operacje, działające na elementach pewnych zbiorów. Często do opisu funkcji używamy wzorów, np. $f(a)=a^{2}$. Warto jednak podkreślić różnicę pomiędzy wzorem a funkcją. Przykładowy wzór może opisywać wiele funkcji, w zależności od tego, z jakiego zbioru elementy będziemy podstawiać w miejsce $a$, a nawet od tego, jak będziemy rozumieć podnoszenie do kwadratu (np. przez $a^{2}$ oznaczaliśmy iloczyn kartezjański $a\times a$, ale równocześnie dla liczby naturalnej $n$ przez $n^{2}$ będziemy oznaczać jej kwadrat). W kolejnych wykładach przekonamy się również, że istnieją funkcje, których nie da się opisać żadnym wzorem.

Warto wspomnieć, że rozważa się również teorie, w których pierwotnymi pojęciami są właśnie funkcje i składanie funkcji. Okazuje się, że bardzo wiele twierdzeń klasycznej matematyki (opartej na teorii zbiorów) da się udowodnić na ich gruncie. Takiemu właśnie podejściu poświęcony jest wykład Teoria kategorii dla informatyków.

Funkcja jako relacja

W poprzednim wykładzie wyróżniliśmy pewną grupę relacji (relacje zwrotne, symetryczne i przechodnie), które to relacje nazwaliśmy relacjami równoważności. Podobnie teraz wyróżnimy pewne relacje, które nazwiemy funkcjami. Podkreślmy jeszcze raz, że funkcja jako relacja jest zbiorem, którego elementami są pary.

Definicja 2.1.

Relację $f\subset X\times Y$ nazywamy funkcją ze zbioru $X$ w zbiór $Y$, jeśli ma następujące własności:

1.

$\forall _{x\in X}\forall _{y\in Y}\forall _{z\in Y}((x,y)\in f\wedge (x,z)\in f)\Rightarrow (y=z).\quad {\mbox{(2.1)}}$

2. $f_{L}=X.$

Zbiór wszystkich funkcji ze zbioru $X$ w zbiór $Y$ będziemy oznaczać przez $Y^{X}$.

Czyli funkcja to relacja taka, że do każdego elementu $x$ ze zbioru $X$ można dobrać dokładnie jeden element $y\in Y$ taki, że $(x,y)\in f$. Pierwsza własność mówi dokładnie tyle, że jeśli do jakiegoś elementu $x$ możemy dobrać elementy $y$ i $z$ takie, aby obydwa były w relacji z $x$, to muszą one być sobie równe, a więc do każdego elementu zbioru $X$ można dobrać co najwyżej jeden element będący z nim w relacji $f$. Druga własność mówi, że do każdego elementu ze zbioru $X$ da się dobrać przynjamniej jeden element będący z nim w relacji $f$. Często będziemy używać skrótowego zapisu $f:X\rightarrow Y$, który będzie oznaczał, że $f$ jest funkcją ze zbioru $X$ w zbiór $Y$ (a więc $f_{L}=X$ i $f_{P}\subset Y$). Mówimy też, że funkcja $f$ odwzorowuje zbiór $X$ w zbiór $Y$.

W definicji funkcji konieczne było odwołanie się do zbioru, na którym funkcja jest określona. Zwróćmy uwagę, że dla konkretnej relacji nie możemy powiedzieć, czy jest ona funkcją, czy nie, gdyż zależy to od tego, jaki zbiór przyjmiemy za $X$. Na przykład relacja $r=\{(0,0),(1,1)\}$ jest funkcją ze zbioru $\{0,1\}$ w zbiór $\{0,1\}$, ale nie jest funkcją ze zbioru $N$ w zbiór $\{0,1\}$. Czasem wygodniej jest rozważać funkcje po prostu jako relacje, dlatego wprowadzamy pojęcie funkcji częściowej.

Definicja 2.2.

Relację $f$ nazywamy funkcją częściową, jeśli ma następującą własność:

$\forall _{x}\forall _{y}\forall _{z}((x,y)\in f\wedge (x,z)\in f)\Rightarrow (y=z).\quad {\mbox{(2.1)}}$

Zwróćmy uwagę, że równie dobrze powyższą własność moglibyśmy sformułować następująco:

$\forall _{x\in f_{L}}\forall _{y\in f_{P}}\forall _{z\in f_{P}}((x,y)\in f\wedge (x,z)\in f)\Rightarrow (y=z).$

Sformułowanie to jest równoważne z (patrz definicja 2.2.), gdyż we wszysktich przypadkach, w których poprzednik implikacji jest prawdziwy, mamy $x\in f_{L},y\in f_{P},z\in f_{P}$.

Fakt 2.1.

Każda funkcja częściowa $f$ jest funkcją ze zbioru $f_{L}$ w zbiór $f_{P}$. Dla dowolnych zbiorów $X,Y$ każda relacja, która jest funkcją ze zbioru $X$ w zbiór $Y$, jest funkcją częściową.

Wobec powyższego faktu, w przypadkach, kiedy nie jest istotne, na jakim zbiorze funkcja jest zdefiniowana, będziemy rozważać odpowiadającą jej funkcję częściową. Dla dowolnej funkcji częściowej $f$ wprowadzamy poniższe oznaczenia, których będziemy również używać dla funkcji. Dla dowolnego $x$, jeśli istnieje taki element $y$, dla którego $(x,y)\in f$, to oznaczamy go przez $f(x)$, podobnie fakt $(x,y)\in f$ notujemy jako $f(x)=y$. Mówimy wtedy, że funkcja częściowa $f$ przyporządkowuje elementowi $x$ element $y$. Elementy $f_{L}$ nazywamy argumentami funkcji częściowej $f$, a elementy $f_{P}$ wartościami funkcji częściowej $f$.

Przykład 2.3.

Poniżej przedstawiamy przykłady relacji, które są funkcjami częściowymi:

1. $\emptyset$ (poprzednik implikacji (patrz definicja 2.2.), jest zawsze fałszywy więc implikacja (patrz definicja 2.2.), jest zawsze prawdziwa),

2. $\{(\emptyset ,\emptyset )\}$,

3. $\{(0,0),(1,0),(2,1)\}$,

4. $X\times \{0\}$ dla dowolnego zbioru $X$,

5. $\mathbb {I} _{X}$

oraz relacje, które funkcjami częściowymi nie są:

1. $\{(0,0),(0,1)\}$,

2. $X\times \{0,1\}$, dla dowolnego niepustego zbioru $X$.

Ćwiczenie 2.1

1. Udowodnij, że złożenie funkcji częściowych jest funkcją częściową.

2. Udowodnij, że jeśli $f:X\rightarrow Y$ i $g:Y\rightarrow Z$, to relacja $g\circ f$ jest

funkcją ze zbioru $X$ w zbiór $Z$.

Rozwiązanie 1

Niech $f,g$ będą funkcjami częściowymi. Dla dowodu nie wprost przypuśćmy, że złożenie $g\circ f$ nie jest funkcją częściową. Jest to równoważne faktowi, że istnieją elementy $x,y_{1},y_{2}$ takie, że $(x,y_{1}),(x,y_{2})\in g\circ f$ i $y_{1}\neq y_{2}$. Skoro $(x,y_{1})\in g\circ f$, to z definicji złożenia relacji istnieją pary $(x,z_{1})\in f$ oraz $(z_{1},y_{1})\in g$, dla pewnego elementu $z_{1}$. Podobnie dla $(x,y_{2})\in g\circ f$ istnieją pary $(x,z_{2})\in f$ oraz $(z_{2},y_{2})\in g$, dla pewnego elementu $z_{2}$. Ponieważ $(x,z_{1}),(x,z_{2})\in f$ oraz $f$ jest funkcją częściową, to $z_{1}=z_{2}$, będziemy więc ten element oznaczać przez $z$. Wobec tego mamy $(z,y_{1}),(z,y_{2})\in g$. Skoro jednak $g$ jest funkcją częściową, to $y_{1}=y_{2}$. Jest to sprzeczność z założeniem nie wprost.

Rozwiązanie 2

Z poprzedniego punktu otrzymujemy, że $g\circ f$ jest funkcją częściową. Wystarczy pokazać, że jest określona na wszystkich elementach zbioru $X$. Weźmy dowolny $x\in X$, ponieważ $f:X\rightarrow Y$ to $f_{L}=X$, a więc istnieje $y\in Y$, dla którego $(x,y)\in f$. Podobnie skoro $g:Y\rightarrow Z$, to istnieje $z\in Z$ taki, że $(y,z)\in g$. Z definicji złożenia relacji otrzymujemy $(x,z)\in g\circ f$, a zatem $g\circ f$ jest określona na $x$. Wobec dowolności wyboru $x$ jest określona na całym zbiorze $X$.

Ćwiczenie 2.2

Czy na każdym zbiorze $X$ istnieje relacja równoważności, która jest funkcją z $X$ w $X$?

Rozwiązanie

Dla każdego zbioru $X$ relacja równoważności $\mathbb {I} _{X}$ (identyczność) jest funkcją.

Obrazy i przeciwobrazy

Czasem warto spojrzeć na funkcję z szerszej perspektywy. Rozważmy pewną funkcję $f:X\rightarrow Y$. Funkcja ta w naturalny sposób wyznacza pewną funkcję przekształcającą podzbiory zbioru $X$ w podzbiory zbioru $Y$, przyporządkowując zbiorowi $A\subset X$, zbiór elementów zbioru $Y$, które są wartościami funkcji $f$ dla pewnych argumentów ze zbioru $A$. Funkcję tą formalnie definujemy w poniższy sposób.

Definicja 3.1.

Każda funkcja $f:X\rightarrow Y$ wyznacza pewną funkcję ${\vec {f}}:{\mathcal {P}}(X)\rightarrow {\mathcal {P}}(Y)$ tak, że dla dowolnego zbioru $A\subset X$

${\vec {f}}(A)=\{y\in Y:\exists _{x\in A}f(x)=y\}.$

Dla dowolnego zbioru $A\subset X$ zbiór ${\vec {f}}(A)$ nazywamy obrazem zbioru $A$ przez funkcję $f$.

Przykład 3.2.

Niech $f:N\rightarrow N$ będzie określona wzorem $f(x)=2\cdot x$. Wtedy

1. ${\vec {f}}(N)$ jest zbiorem liczb parzystych,

2. ${\vec {f}}(\emptyset )=\emptyset$,

3. ${\vec {f}}(\{1\})=\{2\}$,

4. ${\vec {f}}(\{1,2\})=\{2,4\}$,

5. obrazem zbioru liczb parzystych przez funkcję $f$ jest zbiór liczb podzielnych przez 4.

W podobny sposób definiujemy przeciwobrazy zbiorów przez funkcję. Przeciwobrazem zbioru $B\subset Y$ przez funkcję $f:X\rightarrow Y$ nazwiemy zbiór tych elementów zbioru $X$, którym funkcja przypisuje wartości ze zbioru $B$.

Definicja 3.3.

Każda funkcja $f:X\rightarrow Y$ wyznacza pewną funkcję ${\vec {f}}^{-1}:{\mathcal {P}}(Y)\rightarrow {\mathcal {P}}(X)$ w następujący sposób. Dla dowolnego zbioru $B\subset Y$

${\vec {f}}^{-1}(B)=\{x\in X:\exists _{y\in B}f(x)=y\}.$

Dla dowolnego zbioru $B\subset Y$ zbiór ${\vec {f}}^{-1}(B)$ nazywamy przeciwobrazem zbioru $B$ przez funkcję $f$.

Przykład 3.4.

Niech $f:N\rightarrow N$ będzie określona wzorem $f(x)=2\cdot x$. Wtedy

1. ${\vec {f}}^{-1}(N)=N$,

2. ${\vec {f}}^{-1}(\emptyset )=\emptyset$,

3. ${\vec {f}}^{-1}(\{1\})=\emptyset$,

4. ${\vec {f}}^{-1}(\{1,2\})=\{1\}$,

5. przeciwobrazem zbioru liczb nieparzystych przez funkcję $f$ jest zbiór pusty,

6. przeciwobrazem zbioru liczb podzielnych przez 4, przez funkcję $f$ jest zbiór liczb parzystych,

7. przeciwobrazem zbioru liczb parzystych przez funkcję $f$ jest $N$.

Fakt 3.1.

Nietrudno zauważyć, że dla dowolnej funkcji częściowej $f$

${\vec {f}}(\emptyset )=\emptyset ={\vec {f}}^{-1}(\emptyset ).$

W poniższych ćwiczeniach badamy podstawowe własności obrazów i przeciwobrazów dowolnych funkcji.

Ćwiczenie 3.1

Dla dowolnej funkcji $f:X\rightarrow Y$ i dla dowolnych zbiorów $A_{1},A_{2}\subset X$ udowodnij następujące fakty:

1. ${\vec {f}}(A_{1}\cup A_{2})={\vec {f}}(A_{1})\cup {\vec {f}}(A_{2})$,

2. ${\vec {f}}(A_{1}\cap A_{2})\subset {\vec {f}}(A_{1})\cap {\vec {f}}(A_{2})$,

3. ${\vec {f}}(X\setminus A_{1})\supset {\vec {f}}(X)\setminus {\vec {f}}(A_{1})$.

Rozwiązanie 1

${\begin{array}{l}{\vec {f}}(A_{1}\cup A_{2})=\\=\{y\in Y:\exists _{x\in A_{1}\cup A_{2}}f(x)=y\}=\\=\{y\in Y:\exists _{x}[x\in A_{1}\cup A_{2}\wedge f(x)=y]\}=\\=\{y\in Y:\exists _{x}[(x\in A_{1}\vee x\in A_{2})\wedge f(x)=y]\}=\\=\{y\in Y:\exists _{x}[(x\in A_{1}\wedge f(x)=y)\vee (x\in A_{2}\wedge f(x)=y)]\}=\\=\{y\in Y:[\exists _{x}(x\in A_{1}\wedge f(x)=y)]\vee [\exists _{x}(x\in A_{2}\wedge f(x)=y)]\}=\\=\{y\in Y:[\exists _{x}(x\in A_{1}\wedge f(x)=y)]\}\cup \{y\in Y:[\exists _{x}(x\in A_{2}\wedge f(x)=y)]\}=\\=\{y\in Y:[\exists _{x\in A_{1}}f(x)=y]\}\cup \{y\in Y:[\exists _{x\in A_{2}}f(x)=y)]\}=\\={\vec {f}}(A_{1})\cup {\vec {f}}(A_{2})\end{array}}$

Rozwiązanie 2

Weźmy dowolny element $y\in {\vec {f}}(A_{1}\cap A_{2})$. Oznacza to, że istnieje element $x\in A_{1}\cap A_{2}$ taki, że $f(x)=y$. Skoro $x\in A_{1}$, to $y=f(x)\in {\vec {f}}(A_{1})$. Podobnie skoro $x\in A_{2}$, to $y=f(x)\in {\vec {f}}(A_{2})$. Mamy więc $y\in {\vec {f}}(A_{1})$ oraz $y\in {\vec {f}}(A_{2})$, a więc należy także do ich przecięcia.

Rozwiązanie 3

Weźmy dowolny element $y\in {\vec {f}}(X)\setminus {\vec {f}}(A_{1})$. Istnieje wtedy element $x\in X$, dla którego $f(x)=y$ oraz skoro $y\notin {\vec {f}}(A_{1})$, to $x\notin A_{1}$. Wobec tego $y\in {\vec {f}}(X\setminus A_{1})$.

Ćwiczenie 3.2

Dla dowolnej funkcji $f:X\rightarrow Y$ i dowolnej rodziny $\kappa$ podzbiorów $X$ (czyli $\kappa \in {\mathcal {P}}({\mathcal {P}}(X))$) udowodnij następujące fakty:

1. ${\vec {f}}(\bigcup \kappa )=\bigcup \{{\vec {f}}(A):A\in \kappa \}$,

2. ${\vec {f}}(\bigcap \kappa )\subset \bigcap \{{\vec {f}}(A):A\in \kappa \}$.

Rozwiązanie 1

Niech $A\in \kappa$, wtedy $\bigcup \kappa =\bigcup \kappa \cup A$. Z poprzedniego ćwiczenia otrzymujemy

${\vec {f}}(\bigcup \kappa )={\vec {f}}(\bigcup \kappa )\cup {\vec {f}}(A),$

wobec tego dla dowolnego $A\in \kappa$ mamy ${\vec {f}}(\bigcup \kappa )\supset {\vec {f}}(A)$. Więc również

${\vec {f}}(\bigcup \kappa )\supset \bigcup \{{\vec {f}}(A):A\in \kappa \}.$

Dla inkluzji w drugą stronę weźmy dowolny element $y\in {\vec {f}}(\bigcup \kappa )$. Wtedy istnieje $x\in \bigcup \kappa$ taki, że $f(x)=y$. Skoro $x\in \bigcup \kappa$, to istnieje $A_{0}\in \kappa$ taki, że $x\in A_{0}$. Oznacza to, że $y\in {\vec {f}}(A_{0})$, a więc również $y\in \bigcup \{{\vec {f}}(A):A\in \kappa \}$. Wobec tego

${\vec {f}}(\bigcup \kappa )\subset \bigcup \{{\vec {f}}(A):A\in \kappa \}.$

Rozwiązanie 2

Niech $A\in \kappa$, wtedy $\bigcup \kappa =\bigcup \kappa \cap A$. Z poprzedniego ćwiczenia otrzymujemy

${\vec {f}}(\bigcap \kappa )={\vec {f}}(\bigcap \kappa \cap A)\subset {\vec {f}}(\bigcap \kappa )\cap {\vec {f}}(A).$

Wynika stąd, że ${\vec {f}}(\bigcap \kappa )\subset {\vec {f}}(A)$ dla dowolnego $A\in \kappa$, a więc również

${\vec {f}}(\bigcap \kappa )\subset \bigcap \{{\vec {f}}(A):A\in \kappa \}$

Ćwiczenie 3.3

Skonstruuj kontrprzykłady dla poniższych inkluzji:

1. ${\vec {f}}(A_{1}\cap A_{2})\supset {\vec {f}}(A_{1})\cap {\vec {f}}(A_{2})$,

2. ${\vec {f}}(X\setminus A_{1})\subset {\vec {f}}(X)\setminus {\vec {f}}(A_{1})$,

3. ${\vec {f}}(\bigcap \kappa )\supset \bigcap \{{\vec {f}}(A):A\in \kappa \}$.

Rozwiązanie

Niech $f=\{(0,0),(1,0)\}$ oraz $A_{1}=\{0\}$ i $A_{2}=\{1\}$, $X=\{0,1\}$ i $\kappa =\{A_{1},A_{2}\}$. Wtedy

1. $f(A_{1}\cap A_{2})=f(\emptyset )=\emptyset$, podczas gdy ${\vec {f}}(A_{1})\cap {\vec {f}}(A_{2})=\{0\}\cap \{0\}=\{0\}$, a więc zbiór niepusty.

2. ${\vec {f}}(X\setminus A_{1})={\vec {f}}(\{1\})=\{0\}$, podczas gdy ${\vec {f}}(X)\setminus {\vec {f}}(A_{1})=\{0\}\setminus \{0\}=\emptyset$.

3. sytuacja jest dokładnie taka jak w punkcie pierwszym.

Znacznie bardziej regularnie zachowują się przeciwobrazy funkcji. Podstawowe własności są tematem następnych ćwiczeń.

Ćwiczenie 3.4

Dla dowolnej funkcji $f:X\rightarrow Y$ i dla dowolnych zbiorów $B_{1},B_{2}\subset Y$ udowodnij następujące fakty:

1. ${\vec {f}}^{-1}(B_{1}\cup B_{2})={\vec {f}}^{-1}(B_{1})\cup {\vec {f}}^{-1}(B_{2})$,

2. ${\vec {f}}^{-1}(B_{1}\cap B_{2})={\vec {f}}(B_{1})\cap {\vec {f}}(B_{2})$,

3. ${\vec {f}}^{-1}(Y\setminus B_{1})={\vec {f}}^{-1}(Y)\setminus {\vec {f}}^{-1}(B_{1})$.

Rozwiązanie 1

${\begin{array}{l}x\in {\vec {f}}^{-1}(B_{1}\cup B_{2})\Leftrightarrow \\\Leftrightarrow f(x)\in B_{1}\cup B_{2}\Leftrightarrow \\\Leftrightarrow f(x)\in B_{1}\vee f(x)\in B_{2}\Leftrightarrow \\\Leftrightarrow x\in {\vec {f}}^{-1}(B_{1})\vee x\in {\vec {f}}^{-1}(B_{2})\Leftrightarrow \\\Leftrightarrow x\in {\vec {f}}^{-1}(B_{1})\cup {\vec {f}}^{-1}(B_{2})\end{array}}$

Rozwiązanie 2

${\begin{array}{l}x\in {\vec {f}}^{-1}(B_{1}\cap B_{2})\Leftrightarrow \\\Leftrightarrow f(x)\in B_{1}\cap B_{2}\Leftrightarrow \\\Leftrightarrow f(x)\in B_{1}\wedge f(x)\in B_{2}\Leftrightarrow \\\Leftrightarrow x\in {\vec {f}}^{-1}(B_{1})\wedge x\in {\vec {f}}^{-1}(B_{2})\Leftrightarrow \\\Leftrightarrow x\in {\vec {f}}^{-1}(B_{1})\cap {\vec {f}}^{-1}(B_{2})\end{array}}$

Rozwiązanie 3

${\begin{array}{l}x\in {\vec {f}}^{-1}(Y\setminus B_{1})\Leftrightarrow \\\Leftrightarrow f(x)\in Y\setminus B_{1}\Leftrightarrow \\\Leftrightarrow f(x)\in Y\wedge \neg (f(x)\in B_{1})\Leftrightarrow \\\Leftrightarrow x\in {\vec {f}}^{-1}(Y)\wedge \neg (x\in {\vec {f}}^{-1}(B_{1}))\Leftrightarrow \\\Leftrightarrow x\in {\vec {f}}^{-1}(Y)\setminus {\vec {f}}^{-1}(B_{1})\end{array}}$

Ćwiczenie 3.5

Dla dowolnej funkcji $f:X\rightarrow Y$ i dowolnej rodziny $\kappa$ podzbiorów $Y$ (czyli $\kappa \in {\mathcal {P}}({\mathcal {P}}(Y))$) udowodnij następujące fakty:

1. ${\vec {f}}^{-1}(\bigcup \kappa )=\bigcup \{{\vec {f}}^{-1}(B):B\in \kappa \}$,

2. ${\vec {f}}^{-1}(\bigcap \kappa )\subset \bigcap \{{\vec {f}}^{-1}(B):B\in \kappa \}$.

Rozwiązanie 1

${\begin{array}{l}x\in {\vec {f}}^{-1}(\bigcup \kappa )\Leftrightarrow \\\Leftrightarrow f(x)\in \bigcup \kappa \Leftrightarrow \\\Leftrightarrow \exists _{B\in \kappa }f(x)\in B\\\Leftrightarrow \exists _{B\in \kappa }x\in {\vec {f}}^{-1}(B)\Leftrightarrow \\\Leftrightarrow x\in \bigcup \{{\vec {f}}^{-1}(B):B\in \kappa \}_{1})\end{array}}$

Rozwiązanie 2

Metoda z poprzedniego punktu podziała i tutaj. Dla urozmaicenia prezentujemy nieco inne rozwiązanie. Niech $\kappa '=\{Y\setminus B:B\in \kappa \}$. Wtedy, używając wielokrotnie praw de'Morgana, dostaniemy

${\begin{array}{l}{\vec {f}}^{-1}(\bigcap \kappa )=\\={\vec {f}}^{-1}(Y\setminus \bigcup \kappa ')=\\={\vec {f}}^{-1}(Y)\setminus {\vec {f}}^{-1}(\bigcup \kappa ')=\\={\vec {f}}^{-1}(Y)\setminus \bigcup \{{\vec {f}}^{-1}(C):C\in \kappa '\}=\\={\vec {f}}^{-1}(Y)\setminus \bigcup \{{\vec {f}}^{-1}(Y\setminus B):B\in \kappa \}=\\={\vec {f}}^{-1}(Y)\setminus \bigcup \{{\vec {f}}^{-1}(Y)\setminus {\vec {f}}^{-1}(B):B\in \kappa \}=\\=\bigcap \{{\vec {f}}^{-1}(Y)\setminus ({\vec {f}}^{-1}(Y)\setminus {\vec {f}}^{-1}(B)):B\in \kappa \},\end{array}}$

ponieważ ${\vec {f}}^{-1}(Y)\supset {\vec {f}}^{-1}(B)$, to

${\vec {f}}^{-1}(Y)\setminus ({\vec {f}}^{-1}(Y)\setminus {\vec {f}}^{-1}(B))={\vec {f}}^{-1}(B))$

więc kontynuując powyższe równości, dostajemy

$=\bigcap \{{\vec {f}}^{-1}(B):B\in \kappa \}.$

Istnieje ścisły związek pomiędzy funkcjami a relacjami równoważności. Każda funkcja wyznacza pewną relację binarną w poniższy sposób.

Definicja 3.5.

Dla dowolnej funkcji $f:X\rightarrow Y$ definujemy relację binarną $\sim _{f}\subset X^{2}$ następująco:

$(x_{1},x_{2})\in \sim _{f}\Leftrightarrow f(x_{1})=f(x_{2}).$

W myśl powyższej definicji elementy $x_{1},x_{2}\in X$ są w relacji $\sim _{f}$, jeśli funkcja $f$ na tych elementach przyjmuje te same wartości. W poniższym ćwiczeniu dowodzimy, że relacja ta jest relacją równoważności na zbiorze $X$. Relacja ta pełni ważną rolę w podstawowych konstrukcjach liczb, które będą tematem Wykładu 8.

Ćwiczenie 3.6

Udowodnij, że dla dowolnej funkcji $f:X\rightarrow Y$ relacja $\sim _{f}$ jest relacją równoważności na zbiorze $X$.

Rozwiązanie

Przedstawiamy poniżej dwa różne dowody.

Dowód 1

Pokażemy, że relacja jest zwrotna przechodnia i symetryczna.

1. Zwrotność. Dla dowolnego elementu $x\in X$ oczywiście jest spełnione $f(x)=f(x)$, a więc $(x,x)\in \sim _{f}$.

2. Symetryczność. Weźmy dowolne elementy $x,y\in X$ takie, że $(x,y)\in \sim _{f}$. Wynika stąd, że $f(x)=f(y)$, a więc również $f(y)=f(x)$, co jest równoważne $(y,x)\in \sim _{f}$.

3. Przechodniość. Weźmy dowolne elementy $x,y,z\in X$ takie, że $(x,y),(y,z)\in \sim _{f}$. Wtedy $f(x)=f(y)$ i $f(y)=f(z)$, a więc również $f(x)=f(z)$, co oznacza, że $(x,z)\in \sim _{f}$.

Dowód 2

W Ćwiczeniu 3 pokazaliśmy, że ${\vec {f}}^{-1}(A\cap B)={\vec {f}}^{-1}(A)\cap {\vec {f}}^{-1}(B)$. Wynika stąd, że przeciwobrazy rozłącznych zbiorów są rozłączne. Rozważmy rodzinę zbiorów $F{\stackrel {\textrm {def}}{\equiv }}\{{\vec {f}}^{-1}(\{y\}):y\in {\vec {f}}(X)\}$ tworzy podział zbioru $X$. Elementy tej rodziny są rozłączne, bo są przeciwobrazami rozłącznych zbiorów. Każdy element $x\in X$ należy do ${\vec {f}}^{-1}(\{f(x)\})$, a więc należy do pewnego elementu tej rodziny. Wobec tego rodzina $F$ jest podziałem zbioru $X$. Pokażemy teraz, że dowolne dwa elementy $x_{1},x_{2}\in X$ są w relacji $\sim _{f}$ wtedy i tylko wtedy, gdy należą do tego samego zbioru rodziny $F$.

Przypuśćmy, że $f(x_{1})\neq f(x_{2})$. Wtedy z definicji elementy te nie są w relacji $\sim _{f}$. Z drugiej strony $x_{1}\in {\vec {f}}^{-1}(\{f(x_{1})\}$ oraz $x_{2}\in {\vec {f}}^{-1}(\{f(x_{2})\}$. Skoro $f(x_{1})\neq f(x_{2})$, to zbiory $\{f(x_{1})\},\{f(x_{2})\}$ są rozłączne, a więc ich przeciwobrazy również. Otrzymujemy stąd, że elementy $x_{1},x_{2}$ należą do różnych zbiorów rodziny $F$.

Przypuśćmy, że $f(x_{1})=f(x_{2})$, oznaczmy tę wartość przez $y$. Wtedy z definicji $(x_{1},x_{2})\in \sim _{f}$. Z drugiej strony $x_{1}\in {\vec {f}}^{-1}(\{f(x_{1})\}={\vec {f}}^{-1}(\{y\})={\vec {f}}^{-1}(\{f(x_{2})\})\ni x_{2}$, a więc elementy $x_{1},x_{2}$ należą do tego samego zbioru rodziny $F$.

Wynika stąd, że relacja $\sim _{f}$ jest dokładnie relacją wyznaczoną przez rodzinę zbiorów $F$. Skoro rodzina ta jest podziałem zbioru $X$, to relacja $\sim _{f}$ jest relacją równoważności.

Iniekcja i suriekcja

Istotną własnością funkcji jest to, czy różnym elementom może ona przypisać tę samą wartość. Na przykład, w przypadku szyfrowania używamy takich funkcji, które dają się odszyfrować, a więc generują różne kody dla różnych wiadomości. Takie funkcje, których wartości są różne na różnych argumentach nazywamy iniekcjami. Ponieważ ta własność nie zależy od zbioru, na którym funkcja jest zdefiniowana, zdefiniujemy ją dla wszystkich funkcji częściowych.

Definicja 4.1.

Funkcję częściową $f$ nazywamy iniekcją, jeśli różnym elementom przyporządkowuje różne wartości. Formalnie, jeśli spełnia następujący warunek:

$\forall _{y\in f_{P}}\forall _{x_{1},x_{2}\in f_{L}}(f(x_{1})=y\wedge f(x_{2})=y)\Rightarrow x_{1}=x_{2}$

Powyższy warunek mówi dokładnie tyle, że jeśli elementom $x_{1},x_{2}$ funkcja przypisuje tę samą wartość $y$, to te elementy muszą być równe.

Przykład 4.2.

Następujące funkcje częściowe są iniekcjami:

1. $\emptyset$,

2. $\{(\emptyset ,\emptyset )\}$,

3. $\{(0,1),(1,0)\}$,

4. funkcja, która każdej liczbie naturalnej przypisuje liczbę dwukrotnie większą.

Przykłady funkcji częściowych, które nie są iniekcjami:

1. $\{(\emptyset ,\emptyset ),(\{\emptyset \},\emptyset )\}$,

2. $\{(0,0),(1,0)\}$,

3. funkcja, która każdej liczbie naturalnej przypisuje największą

liczbę parzystą nie większą od niej.

W poniższym ćwiczeniu pokazujemy, że jeśli funkcja częściowa nie "zlepia" ze sobą dwóch różnych argumentów, to jest "odwracalna".

Ćwiczenie 4.1.

Udowodnij, że funkcja częściowa $f$ jest iniekcją wtedy i tylko wtedy, gdy $f^{-1}$ jest funkcją częściową.

Rozwiązanie

Dowiedziemy równoważne twierdzenie, które mówi, że funkcja częściowa $f$ nie jest iniekcją wtedy i tylko wtedy, gdy $f^{-1}$ nie jest funkcją częściową.

Przypuśćmy, że $f:X\rightarrow Y$ nie jest iniekcją. Jest to równoważne temu, że istnieją różne elementy $x_{1},x_{2}\in X$ takie, że istnieje $y\in Y$, dla którego $(x_{1},y)\in f$ oraz $(x_{2},y)\in f$. Co jest z kolei równoważne temu, że $(y,x_{1})\in f^{-1}$ oraz $(y,x_{2})\in f^{-1}$, co wobec różności elementów $x_{1},x_{2}$ jest równoważne z tym, że $f^{-1}$ nie jest funkcją częściową.

Ćwiczenie 4.2.

Udowodnij, że funkcja $f:X\rightarrow Y$ jest iniekcją wtedy i tylko wtedy, gdy istnieje funkcja częściowa $g$ taka, że $g\circ f=\mathbb {I} _{X}$.

Rozwiązanie

Zacznijmy od dowodu implikacji w prawo. W poprzednim ćwiczeniu pokazaliśmy, że jeśli $f$ jest iniekcją to, $f^{-1}$ jest funkcją. Załóżmy, że $f$ jest iniekcją i niech $g=f^{-1}$, pokażemy, że $g\circ f=\mathbb {I} _{X}$. Weźmy dowolną parę $(x_{1},x_{2})\in g\circ f$, wtedy musi istnieć element $y\in Y$ taki, że $(x_{1},y)\in f$ oraz $(y,x_{2})\in g$. Skoro $g$ jest odwrotnością $f$, to $(x_{2},y)\in f$. Ponieważ $f$ jest iniekcją to, $x_{1}=x_{2}$. Wynika stąd, że $g\circ f\subset \mathbb {I} _{X}$. Weźmy dowolny element $x\in X$, niech $y\in Y$ będzie elementem takim, że $(x,y)\in f$, wtedy $(y,x)\in g$, a więc $(x,x)\in g\circ f$. Otrzymujemy stąd, że $g\circ f\supset \mathbb {I} _{X}$.

Dla dowodu implikcaji w drugą stronę załóżmy, że istnieje funkcja częściowa $g$ taka, że $g\circ f=\mathbb {I} _{X}$. Weźmy dowolne dwa elementy $x_{1},x_{2}$ takie, że $f(x_{1})=f(x_{2})$. Wtedy $g(f(x_{1}))=g(f(x_{2}))$, ale skoro $g\circ f=\mathbb {I} _{X}$, to $g(f(x_{1}))=x_{1}$ oraz $g(f(x_{2}))=x_{2}$. Wynika stąd, że $x_{1}=x_{2}$. A więc funkcja częściowa $f$ jest iniekcją.

Ćwiczenie 4.3

Czy funkcja częściowa stała może być iniekcją? (funkcja częściowa jest stała, jeśli ma jednoelementowy zbiór wartości).

Rozwiązanie

Funkcja częściowa $\{(\emptyset ,\emptyset )\}$ jest stała i jest iniekcją.

W praktyce często posługujemy się elementami pewnego ustalonego zbioru (np. liczb naturalnych, rzeczywistych itp.) i funkcjami operującymi na tych elementach. W takich przypadkach przydatna okazuje się poniższa definicja funkcji suriektywnej.

Definicja 4.3.

Funkcję częściową $f$ nazywamy suriekcją na zbiór $Y$, jeśli $f_{P}=Y$. Możemy to zapisać jako

$\forall _{y\in Y}\exists _{x\in f_{L}}f(x)=y.$

Zauważmy, że nie ma sensu nazywanie funkcji częściowej suriekcją bez odniesienia się do zbioru $Y$. Dla każdej funkcji możemy dobrać zbiór $Y$ tak, aby była, i tak, aby nie była suriekcją. W przypadku funkcji $f:X\rightarrow Y$ określenie, że $f$ jest suriekcją, będzie oznaczało, że $f$ jest suriekcją na zbiór $Y$.

Przykład 4.4.

1. $\emptyset$ jest suriekcją na $\emptyset$, ale nie jest suriekcją na żaden inny zbiór,

2. $\{(\emptyset ,\emptyset )\}$ jest suriekcją na zbiór $\{\emptyset \}$ i nie jest suriekcją na $\{\{\emptyset \},\emptyset \}$,

3. $\{(0,0)\}$ jest suriekcją na zbiór $\{0\}$ i nie jest suriekcją na $\{1,0\}$,

4. funkcja $f:N\rightarrow N$ taka, że $f(x)=x+1$ jest suriekcją na zbiór liczb naturalnych silnie większych od 0 (czasem oznaczany przez $N_{+}$), ale nie jest suriekcją na $N$.

Fakt 4.1.

Funkcja $f:X\rightarrow Y$ jest suriekcją wtedy i tylko wtedy, gdy istnieje funkcja $g:Y\rightarrow X$ taka, że $f\circ g=\mathbb {I} _{Y}$.

Do udowodnienia powyższego faktu konieczne jest użycie aksjomatu wyboru. Jego dowód (nietrudny) odłożymy więc do wykładu, który jest poświęcony temu aksjomatowi oraz jego równoważnikom.

Ćwiczenie 4.4

Udowodnij, że dla dowolnej funkcji $f:X\rightarrow Y$, $f$ jest suriekcją na $Y$ wtedy i tylko wtedy, gdy funkcja ${\vec {f}}^{-1}$ jest iniekcją na ${\mathcal {P}}(X)$.

Rozwiązanie

Przypuśćmy, że $f$ nie jest suriekcją na $Y$, istnieje wtedy $y\in Y$, dla którego ${\vec {f}}^{-1}(\{y\})=\emptyset$. Wobec tego dla dowolnego $B\subset Y\setminus \{y\}$ mamy

${\vec {f}}^{-1}(B)={\vec {f}}^{-1}(B)\cup {\vec {f}}^{-1}(\{y\})={\vec {f}}^{-1}(B\cup \{y\}),$

a więc funkcja ${\vec {f}}^{-1}$ nie jest iniekcją.

Przypuśćmy teraz, że $f$ jest suriekcją na $Y$. Weźmy dwa różne zbiory $A,B\subset Y$. Skoro są różne, to istnieje element $y_{1}\in A\setminus B$ lub $y_{2}\in B\setminus A$. Zajmiemy się pierwszym przypadkiem, drugi jest symetryczny. Skoro $y_{1}\notin B$, to ${\vec {f}}^{-1}(\{y_{1}\})\cap {\vec {f}}^{-1}(B)=\emptyset$. Ponieważ, $f$ jest suriekcją, to ${\vec {f}}^{-1}(\{y_{1}\})\neq \emptyset$, więc istnieje element $x\in {\vec {f}}^{-1}(\{y_{1}\})$. Mamy więc element $x$ taki, że $x\in {\vec {f}}^{-1}(\{y_{1}\})\subset {\vec {f}}^{-1}(A)$ oraz $x\notin {\vec {f}}^{-1}(B)$, więc zbiory ${\vec {f}}^{-1}(A)$ i ${\vec {f}}^{-1}(B)$ są różne. Wobec tego funkcja ${\vec {f}}^{-1}$ jest iniekcją.

Ćwiczenie 4.5

Udowodnij, że dla dowolnej funkcji $f:X\rightarrow Y$, $f$ jest iniekcją wtedy i tylko wtedy, gdy funkcja ${\vec {f}}^{-1}$ jest suriekcją na ${\mathcal {P}}(X)$.

Rozwiązanie

Zauważmy, że jeśli $f$ jest iniekcją, to przeciwobrazy singletonów są singletonami lub są puste. Przypuśćmy, że $f$ jest iniekcją, weźmy dowolny zbiór $A\subset X$, pokażemy, że $A={\vec {f}}^{-1}({\vec {f}}(A))$.

${\begin{array}{rll}A&=&\bigcup \{\{a\}:a\in A\}\\{\vec {f}}(A)&=&\bigcup \{{\vec {f}}(\{a\}):a\in A\}\\{\vec {f}}(A)&=&\bigcup \{\{f(a)\}:a\in A\}\\{\vec {f}}^{-1}({\vec {f}}(A))&=&{\vec {f}}^{-1}(\bigcup \{\{f(a)\}:a\in A\})\\{\vec {f}}^{-1}({\vec {f}}(A))&=&(\bigcup \{{\vec {f}}^{-1}(\{f(a)\}):a\in A\})\end{array}}$

Skorzystamy teraz z faktu, że przeciwobrazy singletonów są puste lub są sigletonami. Wiemy, że $a\in {\vec {f}}^{-1}(\{f(a)\})$, wobec czego zbiór ${\vec {f}}^{-1}(\{f(a)\})$ jest niepusty, a więc jest singletonem. W takim wypadku jego jedynym elementem może być $a$. Otrzymujemy więc ${\vec {f}}^{-1}(\{f(a)\})=\{a\}$. Wtedy

${\begin{array}{rll}{\vec {f}}^{-1}({\vec {f}}(A))&=&(\bigcup \{\{a\}:a\in A\})\\{\vec {f}}^{-1}({\vec {f}}(A))&=&A\end{array}}$.

Wobec tego dowolny zbiór $A\subset X$ jest przeciwobrazem zbioru ${\vec {f}}(A)$ przez funkcję $f$, a więc funkcja ${\vec {f}}^{-1}$ jest suriekcją.

Przypuśćmy teraz, że funkcja $f$ nie jest iniekcją. Istnieją wtedy różne elementy $x_{1},x_{2}\in X$ oraz element $y\in Y$ takie, że $(x_{1},y),(x_{2},y)\in f$. Pokażemy, że zbiór $\{x_{1}\}$ nie należy do obrazu zbioru ${\mathcal {P}}(Y)$ przez funkcję ${\vec {f}}^{-1}$. Dla dowodu nie wprost przypuśćmy, że istnieje zbiór $B\subset Y$ taki, że ${\vec {f}}^{-1}(B)=\{x_{1}\}$. Rozważmy zbiór ${\vec {f}}^{-1}(\{y\})$, oznaczmy go przez $A$. Z całą pewnością $x_{1},x_{2}\in A$. Ponieważ przeciwobrazy zbiorów rozłącznych są rozłączne, a $x_{1}$ należy zarówno do zbioru $A$, jak i do zbioru ${\vec {f}}^{-1}(B)$, to zbiory $\{y\}$ oraz $B$ nie mogą być rozłączne. Oznacza to, że $y\in B$. Ale w takim wypadku $\{y\}\subset B$ i w konsekwencji

$\{x_{1},x_{2}\}\subset {\vec {f}}^{-1}(\{y\})\subset {\vec {f}}^{-1}(B).$

Ponieważ $x_{1}\neq x_{2}$, to zbiór ${\vec {f}}^{-1}(B)$ nie może być singletonem. Wobec tego nie istnieje zbiór $B$, dla którego ${\vec {f}}^{-1}(B)=\{x_{1}\}$. W efekcie czego funkcja ${\vec {f}}^{-1}$ nie jest suriekcją.

Funkcję nazywamy bijekcją pomiędzy zbiorami $X$ i $Y$, jeśli każdemu elementowi zbioru $X$ przypisuje dokładnie jeden element zbioru $Y$, i w dodatku każdy element zbioru $Y$ występuje w jakimś przypisaniu. Oznacza to dokładnie, że funkcja ta jest zarówno iniekcją jak i suriekcją na zbiór $Y$.

Definicja 4.5.

Funkcję częściową $f$ nazywamy bijekcją ze zbioru $X$ w zbiór $Y$, jeśli są spełnione poniższe warunki:

1. $f:X\rightarrow Y$,

2. $f$ jest iniekcją,

3. $f$ jest suriekcją na $Y$.

Każda funkcja bijektywna pomiędzy zbiorem $X$ a $Y$ dobiera elementy tych zbiorów w pary.

Twierdzenie 4.6.

Funkcja $f$ jest bijekcją ze zbioru $X$ w zbiór $Y$ wtedy i tylko wtedy, gdy $f^{-1}$ jest bijekcją (a więc także funkcją) ze zbioru $Y$ w zbiór $X$.

Dowód

Z ćwiczenia 4 wynika, że relacja $f^{-1}$ jest iniekcją (bo $f$ jest iniekcją). Z własności przeciwobrazów wynika, że ${\vec {f}}^{-1}(Y)=X$. Pozostaje pokazać, że funkcja częściowa $f^{-1}$ jest określona na całym $Y$. Weźmy dowolny element $y\in Y$. Ponieważ $f$ jest suriekcją, to istnieje $x\in X$, dla którego $(x,y)\in f$. Wtedy $(y,x)\in f^{y}$, a więc $y$ należy do dziedziny $f^{-1}$. Wobec dowolności wyboru $y$ dziedziną $f^{-1}$ jest cały zbiór $Y$. Podsumowując, $f^{-1}:Y\rightarrow Y$ jest iniekcją oraz ${\vec {f}}^{-1}(Y)=X$, a więc $f^{-1}$ jest bijekcją ze zbioru $Y$ w zbiór $X$. Implikacja w drugą stronę wynika z faktu, że $f=(f^{-1})^{-1}$.

Twierdzenie 4.7.

Jeśli funkcje częściowe $f,g$ są iniekcjami, to ich złożenie jest iniekcją.

Dowód

Jeśli funkcja częściowa $g\circ f$ jest pusta to jest iniekcją. W przeciwnym razie weźmy dwie dowolne (niekoniecznie różne) pary należące do niej, które mają taką samą drugą współrzędną $(x_{1},y),(x_{2},y)\in g\circ f$. Skoro należą one do złożenia $f$ z $g$, to istnieją elementy $z_{1},z_{2}$ w dziedzinie relacji $f$ takie, że $(x_{1},z_{1}),(x_{2},z_{2})\in f$ oraz $(z_{1},y),(z_{2},y)\in g$. Z iniektywności funkcji częściowej $g$ otrzymujemy, że $z_{1}=z_{2}$, oznaczmy ten element przez $z$. Mamy więc $(x_{1},z),(x_{2},z)\in f$. Z iniektywności funkcji częściowej $f$ dostajemy $x_{1}=x_{2}$, co dowodzi, że funkcja częściowa $g\circ f$ jest iniekcją.

Ćwiczenie 4.6

{{{3}}}

Twierdzenie 4.8.

Dla dowolnych funkcji $f:X\rightarrow Y,g:Y\rightarrow Z$, jeśli $f$ jest suriekcją na $Y$ i $g$ jest suriekcją na $Z$, to $g\circ f$ jest suriekcją na $Z$.

Dowód

Weźmy dowolny $z\in Z$. Ponieważ funkcja $g$ jest suriekcją na $Z$, to istnieje element $y\in Y$ taki, że $(y,z)\in g$. Skoro funkcja $f$ jest suriekcją na $Y$, to istnieje $x\in X$ taki, że $(x,y)\in f$. Z faktów $(x,y)\in f$ oraz $(y,z)\in g$ otrzymujemy $(x,z)\in g\circ f$. Dobraliśmy więc do $z$ element $x\in X$, z którym jest on w relacji $g\circ f$. Wobec dowolności wyboru $z$ funkcja $g\circ f$ jest suriekcją.

Ćwiczenie 4.7

Udowodnij, że w twierdzeniu 4.8. implikacja w przeciwną stronę nie jest prawdziwa.

Rozwiązanie

Weźmy $X=Z=\{0\}$, $Y=\{0,1\}$ oraz $f=\{(0,1)\},g=\{(0,0),(1,0)\}$. Wtedy $f$ jest funkcją ze zbioru $X$ w zbiór $Y$, $g$ jest funkcją ze zbioru $Y$ w zbiór $Z$ oraz $g\circ f=\{(0,0)\}$ jest suriekcją na $\{0\}$, podczas gdy $f$ nie jest suriekcją na $\{0,1\}$.

Ćwiczenie 4.8

W ćwiczeniu 3 pokazaliśmy, że poniższe równości nie są prawdziwe dla wszystkich funkcji. Udowodnij, że:

1.dla funkcji $f:X\rightarrow Y$ równość ${\vec {f}}(A_{1}\cap A_{2})={\vec {f}}(A_{1})\cap {\vec {f}}(A_{2})$ jest prawdą dla dowolnych zbiorów $A_{1},A_{2}$ wtedy i tylko wtedy, gdy $f$ jest iniekcją,

2. dla funkcji $f:X\rightarrow Y$ równość ${\vec {f}}(X\setminus A_{1})={\vec {f}}(X)\setminus {\vec {f}}(A_{1})$ jest prawdą dla dowolnego zbioru $A_{1}$ wtedy i tylko wtedy, gdy $f$ jest iniekcją,

3. dla funkcji $f:X\rightarrow Y$ równość ${\vec {f}}(X\setminus A_{1})=Y\setminus {\vec {f}}(A_{1})$ jest prawdą dla dowolnego zbioru $A_{1}$ wtedy i tylko wtedy, gdy $f$ jest bijekcją.

Rozwiązanie 1

Implikacja w lewo. Przypuśćmy że zbiory te są różne. Wobec tego musi zachodzić

${\vec {f}}(A_{1}\cap A_{2})\subsetneq {\vec {f}}(A_{1})\cap {\vec {f}}(A_{2}),$

to znaczy, że istnieje element $y\in Y$ taki, że $y\in {\vec {f}}(A_{1})\cap {\vec {f}}(A_{2})$ oraz $y\notin {\vec {f}}(A_{1}\cap A_{2})$. Czyli istnieją $x_{1}\in A_{1}\setminus A_{2}$ oraz $x_{2}\in A_{2}\setminus A_{1}$ takie, że $f(x_{1})=f(x_{2})=y$. Ponieważ $x_{1},x_{2}$ należą do rozłącznych zbiorów, to muszą być różne, więc funkcja $f$ nie jest iniekcją.

Implikacja w prawo. Jeśli równość zachodzi dla wszystkich zbiorów, to dla dowolnych różnych elementów $x_{1},x_{2}\in X$ mamy

$\{f(x_{1})\}\cap \{f(x_{2})\}={\vec {f}}(\{x_{1}\})\cap {\vec {f}}(\{x_{2}\})={\vec {f}}(\{x_{1}\}\cap \{x_{2}\})={\vec {f}}(\emptyset )=\emptyset ,$

skąd otrzymujemy $f(x_{1})\neq f(x_{2})$, a więc funkcja $f$ jest iniekcją.

Rozwiązanie 2

Implikacja w prawo. Przypuśćmy, że $f$ nie jest iniekcją. Weźmy $x_{1},x_{2}\in X$ oraz $y\in Y$ takie, że $y=f(x_{1})=f(x_{2})$ oraz $x_{1}\neq x_{2}$. Niech $A_{1}=X\setminus \{x_{1}\}$. Wtedy

$\{y\}={\vec {f}}(X\setminus A_{1}),$

a więc $y\in {\vec {f}}(X\setminus A_{1})$. Równocześnie, ponieważ $x_{2}\in A_{1}$, to $y\in {\vec {f}}(A_{1})$, a więc $y\notin {\vec {f}}(X)\setminus {\vec {f}}(A_{1})$. Wynika stąd, że zbiory $y\notin {\vec {f}}(X)\setminus {\vec {f}}(A_{1})$ i ${\vec {f}}(X\setminus A_{1})$ są różne.

Implikacja w lewo. Przypuśćmy teraz, że $f$ jest iniekcją. Wtedy z punktu pierwszego otrzymamy, że obrazy rozłącznych zbiorów są rozłączne. Weźmy dowolny zbiór $A_{1}\subset X$. Niech $A_{2}=X\setminus A_{1}$. Wtedy

${\vec {f}}(X)={\vec {f}}(A_{1}\cup A_{2})={\vec {f}}(A_{1})\cup {\vec {f}}(A_{2}).$

Ponieważ ${\vec {f}}(A_{1})\cap {\vec {f}}(A_{2})=\emptyset$, to

${\vec {f}}(X)\setminus {\vec {f}}(A_{1})={\vec {f}}(A_{2})={\vec {f}}(X\setminus A_{1}),$

a więc postulowana równość jest prawdziwa.

Rozwiązanie 3

Implikacja w lewo. Jeśli funkcja jest bijekcją, to ${\vec {f}}(X)=Y$ i jest iniekcją, więc z poprzedniego punktu wynika, że badana równość jest prawdziwa.

Implikacja w prawo. Przypuśćmy teraz, że badana równość jest prawdziwa. Pokażemy, że $f$ jest suriekcją na $Y$. Weźmy dowolny element $y\in Y$. Jeśli $y\in {\vec {f}}(A_{1})$, to tym bardziej $y\in {\vec {f}}(X)$. W przeciwnym przypadku z założonej równości wynika, że to $y\in {\vec {f}}(X\setminus A_{1})$, więc również $y\in {\vec {f}}(X)$. Wobec tego każdy $y\in Y$ należy do obrazu zbioru $X$ przez funkcję $f$, a więc $f$ jest suriekcją. Skoro tak, to ${\vec {f}}(X)=Y$ i z założonej równości oraz poprzedniego punktu otrzymujemy, że $f$ jest iniekcją.

Ćwiczenie 4.9

Udowodnij, że funkcja $f:N^{2}\rightarrow N$ określona w następujący sposób

$f(x,y)={\frac {(x+y+1)\cdot (x+y)}{2}}+x$

jest iniekcją.

Rozwiązanie

Weźmy dowolne $(x_{1},y_{1}),(x_{2},y_{2})\in N^{2}$. Rozważymy dwa przypadki.

1. Przypuśćmy, że $x_{1}+y_{1}=x_{2}+y_{2}$. Wtedy niech $z=x_{1}+y_{1}$. Jeśli $f(x_{1},y_{1})=f(x_{2},y_{2})$, to

${\frac {(x_{1}+y_{1}+1)\cdot (x_{1}+y_{1})}{2}}+x_{1}={\frac {(x_{2}+y_{2}+1)\cdot (x_{2}+y_{2})}{2}}+x_{2},$

ponieważ jednak

${\frac {(x_{1}+y_{1}+1)\cdot (x_{1}+y_{1})}{2}}={\frac {(z+1)\cdot (z)}{2}}={\frac {(x_{2}+y_{2}+1)\cdot (x_{2}+y_{2})}{2}},$

to $x_{1}=x_{2}$ i skoro $x_{1}+y_{1}=x_{2}+y_{2}$, to również $y_{1}=y_{2}$.

2. W pozostałym przypadku mamy $x_{1}+y_{1}\neq x_{2}+y_{2}$. Możemy, bez straty ogólności założyć, że $x_{1}+y_{1}<x_{2}+y_{2}$. Niech $z=x_{1}+y_{1}$ oraz $c$ niech będzie takie, że $z+c=x_{2}+y_{2}$. Wtedy

$f(x_{1},y_{1})={\frac {(x_{1}+y_{1}+1)\cdot (x_{1}+y_{1})}{2}}+x_{1}\leq {\frac {(z+1)\cdot (z)}{2}}+z$

oraz

$f(x_{2},y_{2})={\frac {(x_{2}+y_{2}+1)\cdot (x_{2}+y_{2})}{2}}+x_{2}\geq {\frac {(z+c+1)\cdot (z+c)}{2}}\geq {\frac {(z+2)\cdot (z+1)}{2}}.$

Ostatnia nierówność wynika z faktu, że $c\geq 1$. Łatwo zauważyć, że

${\frac {(z+1)\cdot (z)}{2}}+z={\frac {z^{2}+3\cdot z}{2}}<{\frac {z^{2}+3\cdot z+1}{2}}={\frac {(z+2)\cdot (z+1)}{2}},$

co dowodzi, że $f(x_{1},y_{1})<f(x_{2},y_{2})$.

Przypuśćmy teraz, że $f(x_{1},y_{1})=f(x_{2},y_{2})$, wtedy przypadek drugi nie może się zdarzyć, gdyż doszlibyśmy do sprzeczności. W pozostałym (pierwszym) przypadku równość ta implikuje $x_{1}=x_{2}$ oraz $y_{1}=y_{2}$. A więc funkcja $f$ jest iniekcją.

Twierdzenie o faktoryzacji

W tym rozdziale udowodnimy ważne twierdzenie dobrze ilustrujące rolę, którą spełniają iniekcje i suriekcje wśród wszystkich funkcji.

<flash>file=Logika-6.1.swf|width=120|height=120</flash>

<div.thumbcaption>Rysunek 6.1.

Twierdzenie 5.1.

Dla każdej funkcji $f:X\rightarrow Y$ istnieje zbiór $Z$ oraz funkcje $g:X\rightarrow Z,h:Z\rightarrow Y$ takie, że $f=h\circ g$, $g$ jest suriekcją i $h$ jest iniekcją.

Dowód

Niech $Z$ będzie zbiorem klas abstrakcji relacji $\sim _{f}$. Wtedy definujemy $g$ jako funkcję, która każdemu elementowi zbioru $x$ przypisuje jego klasę abstrakcji względem relacji $\sim _{f}$, czyli

$g=\{(x,k)\in X\times {\mathcal {P}}(X):x\in X\wedge k=[x]_{\sim _{f}}\}.$

Zauważmy, że tak zdefiniowana funkcja $g$ jest suriekcją na zbiór $Z$, gdyż klasy abstrakcji nie mogą być puste. Funkcję $h$ defniujemy jako funkcję przypisującą klasom abstrakcji relacji $\sim _{f}$ wartość funkcji na dowolnym elemencie tej klasy, czyli

$h=\{(k,y)\in {\mathcal {P}}(X)\times Y:\exists _{x\in X}k=[x]_{\sim _{f}}\wedge f(x)=y\}.$

Zauważmy, że $h$ rzeczywiście jest funkcją, gdyż, zgodnie z definicją relacji $\sim _{f}$, funkcja $f$ przypisuje wszystkim elementom danej klasy te same wartości.

Pokażemy teraz, że $h$ jest iniekcją. Weźmy dowolne dwie klasy $k_{1},k_{2}\in Z$ i przypuśćmy, że $h(k_{1})=h(k_{2})$. Niech $x_{1},x_{2}\in X$ będą takimi elementami, że $[x_{1}]_{\sim _{f}}=k_{1}$ oraz $[x_{2}]_{\sim _{f}}=k_{2}$. Zgodnie z definicją $h$ mamy $h(k_{1})=f(x_{1})$ oraz $h(k_{2})=f(x_{2})$. Założyliśmy, że $h(k_{1})=h(k_{2})$, więc również $f(x_{1})=f(x_{2})$. Wynika stąd, że $x_{1}\sim _{f}x_{2}$, a więc $[x_{1}]_{\sim _{f}}=[x_{2}]_{\sim _{f}}$, co oznacza dokładnie, że $k_{1}=k_{2}$. Pokazaliśmy więc, że $h$ jest iniekcją.

Pozostaje pokazać, że $f=h\circ g$. Dla dowolnego elementu $x\in X$ mamy

$g(x)=[x]_{\sim _{f}}$

oraz

$h([x]_{\sim _{f}})=f(x).$

Wobec czego otrzymujemy

$h(g(x))=f(x).$

Skoro własność ta zachodzi dla każdego $x\in X$, otrzymujemy $f=h\circ g$.

Ćwiczenie 5.1

Dla poniższych funkcji podaj przykład funkcji $g,h$ oraz zbioru $Z$ z twierdzenia 5.1 o faktoryzacji (patrz twierdzenie 5.1.)

1. Niech $K$ będzie zbiorem okręgów na płaszczyźnie, funkcja $f:K\rightarrow R$ niech przypisuje okręgom długości ich średnic,

2. $f:N^{2}\rightarrow R$ w taki sposób, że $f(x,y)={\frac {x}{y}}$.

Rozwiązanie

1.Zgodnie z konstrukcją w dowodzie twierdzenia zbiór $Z$ będzie podziałem zbioru $K$ na zbiory okręgów o średnicach równej długości. $g$ będzie funkcją, która okręgowi $k\in K$ przypisuje zbiór okręgów o średnicach tej samej długości co średnica $k$. $h$ będzie funkcją, która rodzinom okręgów o tych samych długościach średnic przypisuje liczbę rzeczywistą będącą długością tych średnic.

2. Zgodnie z konstrukcją w dowodzie twierdzenia zbiór $Z$ będzie podziałem $N^{2}$ na zbiory par liczb o równych ilorazach. Funkcja $g$ każdej parze liczb naturalnych $(x,y)$ przypisze zbiór par liczb naturalnych, których iloraz jest równy ${\frac {x}{y}}$.

Funkcja $h$ przypisze każdemu zbiorowi par o równych ilorazach liczbę rzeczywistą będącą wartością tych ilorazów.

Produkt uogólniony

W wykładzie dotyczącym relacji zdefiniowaliśmy iloczyn kartezjański skończonej liczby zbiorów. Poniższa definicja uogólnia tamte rozważania, definiując produkt dowolnej (nawet nieskończonej) rodziny zbiorów.

Definicja 6.1.

Produktem uogólnionym zbioru $X$ nazwiemy zbiór $\mathbb {P} X$ zdefiniowany następująco:

$\mathbb {P} X{\stackrel {\textrm {def}}{\equiv }}\{f\in {\mathcal {P}}(X\times \bigcup X):(f:X\rightarrow \bigcup X)\wedge \forall _{x\in X}f(x)\in x\}.$

Czyli zbiór $\mathbb {P} X$ to zbiór wszystkich tych funkcji, które zbiorom z rodziny $X$ przypisują ich elementy.

Zauważmy, że istnienie produktu uogólnionego dla każdego zbioru $X$ wynika z aksjomatu wyróżniania. Znacznie ważniejszą własnością jednak jest niepustość produktu uogólnionego. Z aksjomatu wyboru w Wykładzie 4 wynika, że produkt uogólniony dowolnej niepustej rodziny niepustych zbiorów jest zawsze niepusty. W konkretnych przypadkach można wykazać niepustość, nie odwołując się do aksjomatu wyboru (np. $\{\{0\}\}$).

W poniższym twierdzeniu pokazujemy, że produkt uogólniony jest w dużej mierze zgodny ze zdefiniowanym wcześniej iloczynem kartezjańskim. Jest to przy okazji pierwszy przykład konstrukcji funkcji bijektywnej, która pozwala "tłumaczyć" elementy jednego zbioru na drugi, co z kolei usprawiedliwia wymienne posługiwanie się nimi.

Twierdzenie 6.2.

Dla dowolnych różnych zbiorów $A,B$ istnieje bijekcja pomiędzy zbiorami $\mathbb {P} \{A,B\}$ a zbiorem $A\times B$.

Dowód

Jeśli któryś ze zbiorów $A,B$ jest pusty, to $\mathbb {P} \{A,B\}=A\times B=\emptyset$, a więc istnieje pomiędzy nimi bijekcja (ćwiczenie: jaka?). Poniżej rozważamy przypadek, gdy oba zbiory są niepuste.

Zdefiniujemy funkcję $F:\mathbb {P} \{A,B\}\rightarrow A\times B$. Dla dowolnej funkcji $h\in \mathbb {P} \{A,B\}$ niech $F(h)=(h(A),h(B))$. Zauważmy najpierw, że para $(h(A),h(B))$ jest rzeczywiście elementem zbioru $A\times B$, ponieważ z definicji zbioru $\mathbb {P} \{A,B\}$ mamy $h(A)\in A$ oraz $h(B)\in B$.

Pokażemy, że funkcja $F$ jest iniekcją. Weźmy dowolne funkcje $g,h\in \mathbb {P} \{A,B\}$, dla których $F(g)=F(h)$. Z definicji funkcji $F$ otrzymujemy $(g(A),g(B))=(h(A),h(B))$, a to jest spełnione tylko wtedy, gdy $g(A)=h(A)$ i $g(B)=h(B)$. Przypomnijmy, że dziedziną funkcji $g$ i $h$ jest zbiór $\{A,B\}$. Skoro przyjmują te same wartości na elementach dziedziny, to są sobie równe, a to wobec dowolności wyboru $g$ i $h$ oznacza, że $F$ jest iniekcją.

Pozostało pokazać, że $F$ jest suriekcją. Weźmy dowolną parę $(a,b)\in A\times B$ i rozważmy funkcję $g=\{(A,a),(B,b)\}$. Ponieważ zbiory $A$ i $B$ są różne, to $g$ jest funkcją określoną na zbiorze $\{A,B\}$. Dodatkowo $g$ spełnia warunek $g(A)\in A$ i $g(B)\in B$, a więc $g\in \mathbb {P} \{A,B\}$. Zauważmy, że $F(g)=(g(A),g(B))=(a,b)$. Wskazaliśmy więc element dziedziny funkcji $F$, dla którego wartością jest właśnie $(a,b)$. Wobec dowolności wyboru $(a,b)\in A\times B$ dowiedliśmy, że $F$ jest suriekcją.

Ćwiczenie 6.1

Udowodnij, że założenie o różności zbiorów $A$ i $B$ w powyższym twierdzeniu jest konieczne.

Rozwiązanie

Niech $A=B=\{0,1\}$. Wtedy $A\times B=\{(0,0),(0,1),(1,0),(1,1)\}$ oraz $\mathbb {P} \{A,B\}=\mathbb {P} \{A\}=\{(A,0),(A,1)\}$. Ponieważ obraz każdej funkcji ze zbioru $\mathbb {P} \{A\}$ w zbiór $A\times B$ jest co najwyżej dwuelementowy, to żadna taka funkcja nie może być suriekcją, a więc również nie może być bijekcją.

Twierdzenie Knastra-Tarskiego

Bronisław Knaster (1893-1980)
Zobacz biografię

W tym rozdziale przedstawimy podstawową wersję twierdzenia

Knastra-Tarskiego o punktach stałych funkcji monotonicznych oraz kilka przykładów zastosowań.

Definicja 7.1.

Funkcję $f:{\mathcal {P}}(X)\rightarrow {\mathcal {P}}(X)$ nazwiemy monotoniczną ze względu na inkluzję, jeśli

$\forall _{x\subset X}\forall _{y\subset X}(x\subset y\Rightarrow f(x)\subset f(y)).$

Funkcje monotoniczne ze względu na inkluzję zachowują relację inkluzji pomiędzy przekształcanymi zbiorami. Nie oznacza to jednak wcale, że argument funkcji musi byc podzbiorem wartości funkcji na tym argumencie.

Ćwiczenie 7.1

Podaj przykład funkcji monotonicznej $f:{\mathcal {P}}(X)\rightarrow {\mathcal {P}}(X)$, dla której nieprawdą jest, że dla każdego zbioru $A\subset X$, zachodzi $f(A)\supset A$.

Rozwiązanie

Dla dowolnego niepustego zbioru $X$ funkcja stale równa $\emptyset$ spełnia żądane założenia. Jest monotoniczna, gdyż prawa strona implikacji w definicji monotoniczności jest zawsze spełniona
($\emptyset \subset \emptyset$). Dla zbioru $X$ mamy $f(X)=\emptyset$, a więc nieprawdą jest, że $f(X)\supset X$.

Definicja 7.2.

Element $x\in X$ jest punktem stałym funkcji $f:X\rightarrow X$, jeśli

$f(x)=x.$

Ćwiczenie 7.2

Podaj przykłady punktów stałych następujących funkcji:

1. $f:R\rightarrow R$ jest określona wzorem $f(x)={\frac {x}{2}}$,

2. $f:{\mathcal {P}}({\mathcal {P}}(X))\rightarrow {\mathcal {P}}({\mathcal {P}}(X))$ jest określona wzorem $f(x)=\{\bigcup x,\bigcap x\}$,

3. $f:{\mathcal {P}}(X^{2})\rightarrow {\mathcal {P}}(X^{2})$ jest określona wzorem $f(r)=r^{-1}$.

Rozwiązanie 1

1. 0 jest jedynym punktem stałym funkcji $f$, $0={\frac {0}{2}}$.

Rozwiązanie 2

Kilka przykładów punktów stałych

(a) dla dowolnego $x\in X$ mamy $f(\{x\})=\{\bigcup \{x\},\bigcap \{x\}\}=\{x,x\}=\{x\}$,

(b) dla dowolnego $A\subset X$ mamy $f(\{A,\emptyset \})=\{(A\cup \emptyset ),(A\cap \emptyset )\}=\{A,\emptyset \}$,

(c)dla dowolnych zbiorów $A\subset B\subset X$ mamy $f(\{A,B\})=\{(A\cup B),(A\cap B)\}=\{B,A\}$.

Rozwiązanie 3

$r\subset X^{2}$ jest punktem stałym funkcji $f$ wtedy i tylko wtedy, gdy $r=r^{-1}$. Wynika stąd, że punktami stałymi są relacje symetryczne będące podzbiorami $X^{2}$. Jedną z takich relacji jest $\mathbb {I} _{X}$.

Zwróćmy uwagę, że istnieją funkcje, które nie mają punktów stałych. Prostym przykładem może być funkcja $\{(0,1),(1,0)\}$.

Ćwiczenie 7.3

Niech $X$ będzie niepustym zbiorem. Udowodnij, że dla funkcji $f:{\mathcal {P}}(X)\rightarrow {\mathcal {P}}(X)$ zdefiniowanej wzorem $f(A)=X\setminus A$ nie istnieje punkt stały.

Rozwiązanie

Dla dowodu niewprost przypuścmy, że istnieje punkt stały $F$ dla funkcji $f$. Oznacza to, że $f(F)=F$. Z definicji $f$ wynika, że $f(F)=X\setminus F$, a więc mamy

$F=X\setminus F,$

co prowadzi do sprzeczności, gdyż zbiór $X$ jest niepusty.

Definicja 7.3.

Punkt $x_{0}\subset X$ jest najmniejszym punktem stałym funkcji $f:{\mathcal {P}}(X)\rightarrow {\mathcal {P}}(X)$, jeśli $f(x_{0})=x_{0}$ oraz

$\forall _{x_{1}\subset X}f(x_{1})=x_{1}\Rightarrow x_{0}\subset x_{1}.$

Czyli wtedy, kiedy każdy inny punkt stały jest jego nadzbiorem.

Definicja 7.4.

Punkt $x_{0}\subset X$ jest największym punktem stałym funkcji $f:{\mathcal {P}}(X)\rightarrow {\mathcal {P}}(X)$, jeśli $f(x_{0})=x_{0}$ oraz

$\forall _{x_{1}\subset X}f(x_{1})=x_{1}\Rightarrow x_{0}\supset x_{1}.$

Czyli wtedy, kiedy każdy inny punkt stały jest jego podzbiorem.

Poniższy przykład ilustruje, że istnienie najmniejszego i największego punktu stałego wcale nie jest oczywiste.

Przykład 7.5.

Dla funkcji $f:{\mathcal {P}}({\mathcal {P}}(X))\rightarrow {\mathcal {P}}({\mathcal {P}}(X))$ określonej wzorem $f(A)=\{\bigcap A\}$ punktami stałymi są $\emptyset$ oraz singletony zawierające podzbiory zbioru $X$ (czyli zbiory postaci $\{A\}$ dla $A\subset X$). Jeśli $X$ jest niepusty, to istnieją przynajmniej dwa różne punkty stałe będące singletonami. Nie istnieje wtedy punkt stały będący ich nadzbiorem, gdyż musiałby zawierać przynajmniej dwa elementy. Wobec tego nie istnieje największy punkt stały funkcji $f$.

Alfred Tarski (1901-1983)
Zobacz biografię

Twierdzenie 7.6. [Knaster-Tarski]

Każda monotoniczna funkcja $f:{\mathcal {P}}(X)\rightarrow {\mathcal {P}}(X)$ posiada najmniejszy i największy punkt stały.

Dowód

Niech $L=\{x\subset X:f(x)\supset x\}$. Pokażemy, że $\bigcup L$ jest największym punktem stałym funkcji $f$. Zauważmy, że dla każdego $x\in L$ z monotoniczności $f$ otrzymujemy

$f(\bigcup L)\supset f(x)\supset x.$

Wobec tego również

$f(\bigcup L)\supset \bigcup L,\quad {\mbox{(7.1)}}$

skąd otrzymujemy, że $\bigcup L\in L$. Przekształcając obie strony poprzedniego równania przez $f$ dzięki monotoniczności tej funkcji, otrzymamy

$f(f(\bigcup L))\supset f(\bigcup L).$

Wobec czego również $f(\bigcup L)\in L$. Ponieważ każdy element $L$ jest podzbiorem $\bigcup L$, to również $f(\bigcup L)\subset \bigcup L$. Stąd i z równania 7.1 otrzymujemy

$f(\bigcup L)=\bigcup L,$

a więc $\bigcup L$ jest punktem stałym funkcji $f$. Co więcej, wszystkie punkty stałe należą do zbioru $L$, wobec czego każdy z nich jest podzbiorem $\bigcup L$, co oznacza dokładnie, że $\bigcup L$ jest największym punktem stałym.

Analogicznie wykażemy istnienie najmniejszego punktu stałego. Niech $U=\{x\subset X:f(x)\subset x\}$. Pokażemy, że $\bigcap U$ jest najmniejszym punktem stałym. Z monotoniczności $f$ mamy dla każdego $x\in U$

$f(\bigcap U)\subset f(x)\subset x,$

skąd otrzymujemy

$f(\bigcap U)\subset \bigcap U,\quad {\mbox{(7.2)}}$

wobec czego $\bigcap U\in U$. Przekształcając obie strony ostatniego równania przez $f$, dzięki monotoniczności tej fukcji, otrzymamy

$f(f(\bigcap U))\subset f(\bigcap U),$

skąd wynika, że $f(\bigcap U)\in U$. Ponieważ $\bigcap U$ jest podzbiorem każdego elementu $U$, więc również $\bigcap U\subset f(\bigcap U)$. Stąd i z równania 7.2 otrzymujemy $f(\bigcap U)=\bigcap U$. Oznacza to, że $\bigcap U$ jest punktem stałym funkcji $f$. Ponieważ wszystkie punkty stałe należą do zbioru $U$, to $\bigcap U$ jest najmniejszym punktem stałym.

Przykład 7.7.

Niech $X$ będzie zbiorem induktywnym (czyli takim, którego istnienie jest gwarantowane przez aksjomat nieskończoności). Zdefiniujmy funkcję $f:{\mathcal {P}}(X)\rightarrow {\mathcal {P}}(X)$ w następujący sposób. Dla dowolnego $A\subset X$ niech

$f(A){\stackrel {\textrm {def}}{\equiv }}A\cup \{x\cup \{x\}:x\in A\}\cup \{\emptyset \}.$

Zwróćmy uwagę, że $f(A)\subset X$ dzięki temu, że zbiór $X$ jest induktywny. Z definicji łatwo wynika, że funkcja $f$ jest monotoniczna. Wobec tego z twierdzenia 7.6 (patrz twiedzenie 7.6.) wynika, że ma najmniejszy i największy punkt stały. Zauważmy, że z definicji funkcji $f$ wynika, że każdy punkt stały tej funkcji jest zbiorem induktywnym. Największy punkt stały łatwo wskazać, gdyż jest to cały zbiór $X$. Znacznie ciekawszy jest najmniejszy punkt stały, nazwijmy go $\omega$. Jest to najmniejszy zbiór induktywny będący podzbiorem $X$. W wykładzie 7 dotyczącym liczb naturalnych pokażemy, że zbiór $\omega$ jest również podzbiorem każdego innego zbioru induktywnego (dociekliwi mogą spróbować udowodnić to już teraz).

Ćwiczenie 7.4

{{{3}}}

Ćwiczenie 7.5

Niech $f:{\mathcal {P}}({\mathcal {P}}(N))\rightarrow {\mathcal {P}}({\mathcal {P}}(N))$ będzie zdefiniowana tak, że dla każdego $A\subset N$

$f(A)=\{x\cup y:x,y\in A\}\cup \{\{n\}:n\in N\}.$

Czyli funkcja $f$ przekształca rodziny zbiorów liczb w rodziny zbiorów liczb. Udowodnij, że funkcja $f$ jest monotoniczna. Co jest najmniejszym punktem stałym funkcji $f$? Czy $\emptyset$ jest elementem tego punktu stałego?

Rozwiązanie

Najpierw pokażemy monotoniczność. Weźmy dowolne zbiory $A\subset B\subset {\mathcal {P}}(N)$. Weźmy dowolny zbiór $x\in f(A)$. Z definicji funkcji $f$ wynika, że $x$ jest postaci $\{n\}$ dla pewnej liczby $n\in N$ lub $x$ jest postaci $a\cup b$ dla pewnych $a,b\in A$. W pierwszym przypadku $x\in f(B)$ dlatego, że z definicji $f(B)\supset \{\{n\}:n\in N\}$. W drugim przypadku $x\in f(B)$ dlatego, że $B\supset A$, a więc $a,b\in B$ i z definicji $f(B)$ otrzymujemy $a\cup b\in f(B)$.

Pokażemy teraz, że każdy punkt stały funkcji $f$ zawiera wszystkie niepuste skończone podzbiory $N$. Dowód przeprowadzimy przez indukcję ze względu na liczbę elementów zbioru. Niech $S$ będzie punktem stałym funkcji $f$.

1. Baza indukcji. Z definicji funkcji $f$ wynika, że dla dowolnego zbioru $A\subset {\mathcal {P}}(N)$ rodzina $f(A)$ zawiera wszystkie zbiory jednoelementowe. Skoro $S$ jest punktem stałym, to $S=f(S)$, a więc musi zawierać wszystkie zbiory jednoelementowe.

2. Krok indukcji. Dla dowolnego $n\in N$ takiego, że $n\geq 1$ pokażemy, że jeśli $S$ zawiera wszystkie $n$-elementowe podzbiory $N$, to zawiera również wszystkie $n+1$-elementowe podzbiory $N$. Weźmy dowolne $n\in N$ takie, że $n\geq 1$ i załóżmy, że $S$ zawiera wszystkie $n$-elementowe podzbiory $N$. Pokażemy, że $S$ zawiera wszystkie $n+1$-elementowe podzbiory $N$. Weźmy dowolny $n+1$-elementowy podzbiór $N$ i nazwijmy go $A$. Niech $a\in A$ (zbiór $A$ jest niepusty). Wtedy z założenia indukcyjnego $A\setminus \{a\}\in S$. Z bazy indukcji otrzymujemy, że $\{a\}\in S$. Z definicji funkcji $f$ wynika, że $(A\setminus \{a\})\cup \{a\}\in f(S)$, czyli $A\in f(S)$. Skoro jednak $S$ jest punktem stałym (czyli $f(S)=S$), to $A\in S$. Wobec dowolności wyboru $A$ krok indukcyjny jest udowodniony.

Wystarczy teraz pokazać, że zbiór niepustych skończonych podzbiorów $N$ jest punktem stałym funkcji $f$. Niech $F$ będzie tym zbiorem. Zauważmy, że $f(F)\supset F$, ponieważ dla każdego $x\in F$ możemy dobrać element $x\cup x\in f(F)$. Wystarczy więc pokazać, że wszystkie zbiory z $f(F)$ są skończone. Weźmy dowolny $y\in f(F)$. Zgodnie z definicją funkcji $f$ zbiór $y$ jest postaci $\{n\}$ dla pewnego $n\in N$ lub postaci $a\cup b$ dla pewnych $a,b\in F$. W pierwszym przypadku $y$ jest jednoelementowy, a więc skończony. W drugim przypadku jest sumą dwóch zbiorów skończonych, a więc również jest skończony. Pokazaliśmy więc, że $f(F)=F$.

$F$ jest punktem stałym i każdy punkt stały funkcji $f$ jest nadzbiorem $F$, więc $F$ jest najmniejszym punktem stałym.

Zauważmy na koniec, że $\emptyset \notin F$. Łatwo pokazać, że $F\cup \{\emptyset \}$ jest również punktem stałym funkcji $f$.

Lemat Banacha

Stefan Banach (1892-1945)
Zobacz biografię

Twierdzenie Knastra-Tarskiego posłuży nam do udowodnienia lematu

Banacha, który z kolei wykorzystamy w wykładzie 9 dotyczącym teorii mocy.

Twierdzenie 7.8.

Dla dowolnych zbiorów $X,Y$ oraz funkcji $f:X\rightarrow Y$ i $g:Y\rightarrow X$ istnieją zbiory $A_{1},A_{2}\subset X$ oraz $B_{1},B_{2}\subset Y$ takie, że:

1. $\{A_{1},A_{2}\}$ jest podziałem zbioru $X$,

2. $\{B_{1},B_{2}\}$ jest podziałem zbioru $Y$,

3. ${\vec {f}}(A_{1})=B_{1}$,

4. ${\vec {g}}(B_{2})=A_{2}$.

<flash>file=Logika-6.2.swf|width=250|height=150</flash>

<div.thumbcaption>Rysunek 6.2.

Dowód

Rozważmy funkcję $F:{\mathcal {P}}(X)\rightarrow {\mathcal {P}}(X)$ zdefiniowaną następująco. Dla dowolnego $A\subset X$ niech

$F(A)=X\setminus {\vec {g}}(Y\setminus {\vec {f}}(A)).$

Pokażemy najpierw, że $F$ jest monotoniczna. Weźmy dowolne zbiory $C_{1},C_{2}\subset X$ takie, że $C_{1}\subset C_{2}$. Wtedy

${\vec {f}}(C_{1})\subset {\vec {f}}(C_{2}),$

więc

$Y\setminus {\vec {f}}(C_{1})\supset Y\setminus {\vec {f}}(C_{2})$ ${\vec {g}}(Y\setminus {\vec {f}}(C_{1}))\supset {\vec {g}}(Y\setminus {\vec {f}}(C_{2}))$ $X\setminus {\vec {g}}(Y\setminus {\vec {f}}(C_{1}))\subset X\setminus {\vec {g}}(Y\setminus {\vec {f}}(C_{2})),$

a więc $F(C_{1})\subset F(C_{2})$.

Skoro $F$ jest monotoniczna, to na mocy twierdzenia 7.6 (patrz twierdzenie 7.6.) Knastra-Tarskiego posiada najmniejszy punkt stały. Oznaczmy go przez $A_{1}$. Zdefiniujemy teraz pozostałe zbiory z tezy twierdzenia. Niech:

$A_{2}{\stackrel {\textrm {def}}{\equiv }}X\setminus A_{1},$ $B_{1}{\stackrel {\textrm {def}}{\equiv }}{\vec {f}}(A_{1}),$ $B_{2}{\stackrel {\textrm {def}}{\equiv }}Y\setminus B_{1}.$

Z definicji zbiorów $A_{1},A_{2},B_{1},B_{2}$ natychmiast wynika, że zbiory $\{A_{1},A_{2}\}$ oraz $\{B_{1},B_{2}\}$ tworzą odpowiednio podziały zbiorów $X$ i $Y$. Również z definicji spełniony jest punkt trzeci tezy (czyli $B_{1}{\stackrel {\textrm {def}}{\equiv }}{\vec {f}}(A_{1})$). Pozostaje pokazać, że zachodzi punkt czwarty. Skoro $A_{1}$ jest punktem stałym funkcji $F$, to

$A_{1}=X\setminus {\vec {g}}(Y\setminus {\vec {f}}(A_{1})).$

Podstawiając kolejno w powyższym wzorze zdefiniowane zbiory, otrzymujemy:

$A_{1}=X\setminus {\vec {g}}(Y\setminus B_{1}),$ $A_{1}=X\setminus {\vec {g}}(B_{2}).$

Odejmując obie strony od $X$, otrzymamy:

$X\setminus A_{1}={\vec {g}}(B_{2}).$

Ponieważ jednak lewa strona w powyższej równości jest z definicji równa $A_{2}$, to otrzymujemy:

$A_{2}={\vec {g}}(B_{2}).$

Wobec tego zdefiniowane zbiory spełniają wszystkie własności postulowane w tezie twierdzenia.