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łajace 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 $x$ , 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 przechodznie), 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 \land (x, z) \in f) \Rightarrow (y = z) .

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 \to 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 \land (x, z) \in f) \Rightarrow (y = z) .

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 \land (x, z) \in f) \Rightarrow (y = z) .

Sformułowanie to jest równoważne z 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 Definicja 2.2. jest zawsze fałszywy więc implikacja 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.

𝕀_{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

{{{3}}}

Ćwiczenie 2.2

{{{3}}}

Obrazy i przeciwobrazy

Czasem warto spojrzeć na funkcję z szerszej perspektywy. Rozważmy pewną funkcję $f : X \to 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.

Każda funkcja $f : X \to Y$ wyznacza pewną funkcję $\vec{f} : 𝒫 (X) \to 𝒫 (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$ .

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

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

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

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

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

obrazem zbioru liczb parzystych przez funkcję $f$ jest zbiór liczb

podzielnych przez 4.

ład

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

Każda funkcja $f : X \to Y$ wyznacza pewną funkcję ${\vec{f}}^{- 1} : 𝒫 (Y) \to 𝒫 (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$ .

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

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

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

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

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

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

przeciwobrazem zbioru liczb podzielnych przez 4, przez funkcję $f$ jest

zbiór liczb parzystych,

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

ład

Fakt [Uzupelnij]

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.

{cwicz}{1} {hint}{0} {Ćwiczenie {section}.{cwicz}}

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

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

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

$\vec{f} (X ∖ A_{1}) \supset \vec{f} (X) ∖ \vec{f} (A_{1})$

Solution.

\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} \land f (x) = y]} = \\ = {y \in Y : \exists_{x} [(x \in A_{1} \lor x \in A_{2}) \land f (x) = y]} = \\ = {y \in Y : \exists_{x} [(x \in A_{1} \land f (x) = y) \lor (x \in A_{2} \land f (x) = y)]} = \\ = {y \in Y : [\exists_{x} (x \in A_{1} \land f (x) = y)] \lor [\exists_{x} (x \in A_{2} \land f (x) = y)]} = \\ = {y \in Y : [\exists_{x} (x \in A_{1} \land f (x) = y)]} \cup {y \in Y : [\exists_{x} (x \in A_{2} \land 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}

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.

Weźmy dowolny element $y \in \vec{f} (X) ∖ \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 ∖ A_{1})$ .

{Koniec ćwiczenia {section}.{cwicz}}

{cwicz}{1} {hint}{0} {Ćwiczenie {section}.{cwicz}}

Dla dowolnej funkcji $f : X \to Y$ i dowolnej rodziny $κ$ podzbiorów $X$ (czyli $κ \in 𝒫 (𝒫 (X))$ ) udowodnij następujące fakty:

$\vec{f} (⋃ κ) = ⋃ {\vec{f} (A) : A \in κ}$

$\vec{f} (⋂ κ) \subset ⋂ {\vec{f} (A) : A \in κ}$

Solution.

Niech $A \in κ$ wtedy

$⋃ κ = ⋃ κ \cup A$ . Z poprzedniego ćwiczenia otrzymujemy

\vec{f} (⋃ κ) = \vec{f} (⋃ κ) \cup \vec{f} (A)

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

\vec{f} (⋃ κ) \supset ⋃ {\vec{f} (A) : A \in κ} .

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

\vec{f} (⋃ κ) \subset ⋃ {\vec{f} (A) : A \in κ} .

Niech $A \in κ$ , wtedy $⋃ κ = ⋃ κ \cap A$ . Z poprzedniego ćwiczenia

otrzymujemy

\vec{f} (⋂ κ) = \vec{f} (⋂ κ \cap A) \subset \vec{f} (⋂ κ) \cap \vec{f} (A) .

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

\vec{f} (⋂ κ) \subset ⋂ {\vec{f} (A) : A \in κ}

{Koniec ćwiczenia {section}.{cwicz}}

{cwicz}{1} {hint}{0} {Ćwiczenie {section}.{cwicz}}

Skonstruuj kontrprzykłady dla poniższych inkluzji:

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

$\vec{f} (X ∖ A_{1}) \subset \vec{f} (X) ∖ \vec{f} (A_{1})$

$\vec{f} (⋂ κ) \supset ⋂ {\vec{f} (A) : A \in κ}$

Solution.: Niech $f = {(0, 0), (1, 0)}$ oraz $A_{1} = {0}$ i

$A_{2} = {1}$ , $X = {0, 1}$ i $κ = {A_{1}, A_{2}}$ . Wtedy

$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.

$\vec{f} (X ∖ A_{1}) = \vec{f} ({1}) = {0}$ podczas gdy

$\vec{f} (X) ∖ \vec{f} (A_{1}) = {0} ∖ {0} = \emptyset$ .

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

{Koniec ćwiczenia {section}.{cwicz}}

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

{cwicz}{1} {hint}{0} {Ćwiczenie {section}.{cwicz}}

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

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

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

${\vec{f}}^{- 1} (Y ∖ B_{1}) = {\vec{f}}^{- 1} (Y) ∖ {\vec{f}}^{- 1} (B_{1})$

Solution.

\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} \lor f (x) \in B_{2} \Leftrightarrow \\ \Leftrightarrow x \in {\vec{f}}^{- 1} (B_{1}) \lor x \in {\vec{f}}^{- 1} (B_{2}) \Leftrightarrow \\ \Leftrightarrow x \in {\vec{f}}^{- 1} (B_{1}) \cup {\vec{f}}^{- 1} (B_{2}) \end{array}

\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} \land f (x) \in B_{2} \Leftrightarrow \\ \Leftrightarrow x \in {\vec{f}}^{- 1} (B_{1}) \land x \in {\vec{f}}^{- 1} (B_{2}) \Leftrightarrow \\ \Leftrightarrow x \in {\vec{f}}^{- 1} (B_{1}) \cap {\vec{f}}^{- 1} (B_{2}) \end{array}

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

{Koniec ćwiczenia {section}.{cwicz}}

{cwicz}{1} {hint}{0} {Ćwiczenie {section}.{cwicz}}

Dla dowolnej funkcji $f : X \to Y$ i dowolnej rodziny $κ$ podzbiorów $Y$ (czyli $κ \in 𝒫 (𝒫 (Y))$ ) udowodnij następujące fakty:

${\vec{f}}^{- 1} (⋃ κ) = ⋃ {{\vec{f}}^{- 1} (B) : B \in κ}$

${\vec{f}}^{- 1} (⋂ κ) \subset ⋂ {{\vec{f}}^{- 1} (B) : B \in κ}$

Solution.

\begin{array}{l} x \in {\vec{f}}^{- 1} (⋃ κ) \Leftrightarrow \\ \Leftrightarrow f (x) \in ⋃ κ \Leftrightarrow \\ \Leftrightarrow \exists_{B \in κ} f (x) \in B \\ \Leftrightarrow \exists_{B \in κ} x \in {\vec{f}}^{- 1} (B) \Leftrightarrow \\ \Leftrightarrow x \in ⋃ {{\vec{f}}^{- 1} (B) : B \in κ}_{1}) \end{array}

Metoda z poprzedniego punktu podziała i tutaj. Dla urozmaicenia

prezentujemy nieco inne rozwiązanie. Niech $κ^{'} = {Y ∖ B : B \in κ}$ . Wtedy, używając wielokrotnie praw de'Morgana, dostaniemy

\begin{array}{l} {\vec{f}}^{- 1} (⋂ κ) = \\ = {\vec{f}}^{- 1} (Y ∖ ⋃ κ^{'}) = \\ = {\vec{f}}^{- 1} (Y) ∖ {\vec{f}}^{- 1} (⋃ κ^{'}) = \\ = {\vec{f}}^{- 1} (Y) ∖ ⋃ {{\vec{f}}^{- 1} (C) : C \in κ^{'}} = \\ = {\vec{f}}^{- 1} (Y) ∖ ⋃ {{\vec{f}}^{- 1} (Y ∖ B) : B \in κ} = \\ = {\vec{f}}^{- 1} (Y) ∖ ⋃ {{\vec{f}}^{- 1} (Y) ∖ {\vec{f}}^{- 1} (B) : B \in κ} = \\ = ⋂ {{\vec{f}}^{- 1} (Y) ∖ ({\vec{f}}^{- 1} (Y) ∖ {\vec{f}}^{- 1} (B)) : B \in κ} \end{array}

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

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

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

= ⋂ {{\vec{f}}^{- 1} (B) : B \in κ} .

{Koniec ćwiczenia {section}.{cwicz}}

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.

Dla dowolnej funkcji $f : X \to 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ładów wykłady z konstrukcją liczb

{cwicz}{1} {hint}{0} {Ćwiczenie {section}.{cwicz}}

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

Solution.: Przedstawiamy poniżej dwa różne dowody.

Dowód 1

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

Zwrotność. Dla dowolnego elementu $x \in X$ oczywiście jest

spełnione $f (x) = f (x)$ , a więc $(x, x) \in \sim_{f}$ .

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}$ .

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 Uzupelnic ex:przeciwobrazy| 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 \overset{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})}) ∋ 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.

{Koniec ćwiczenia {section}.{cwicz}}

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.

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 \land 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.

ład Następujące funkcje częściowe są iniekcjami

$\emptyset$ ,

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

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

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

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

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

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

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

liczbę parzystą nie większą od niej

ład

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

{cwicz}{1} {hint}{0} {Ćwiczenie {section}.{cwicz}}

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

Solution.: 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ęściowa.

Przypuśćmy, że $f : X \to 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ą.

{Koniec ćwiczenia {section}.{cwicz}}

{cwicz}{1} {hint}{0} {Ćwiczenie {section}.{cwicz}}

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

Solution.: 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 = 𝕀_{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 𝕀_{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 𝕀_{X}$ .

Dla dowodu implikcaji w drugą stronę załóżmy, że istnieje funkcja częściowa $g$ taka, że $g \circ f = 𝕀_{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 = 𝕀_{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ą.

{Koniec ćwiczenia {section}.{cwicz}}

{cwicz}{1} {hint}{0} {Ćwiczenie {section}.{cwicz}}

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

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

{Koniec ćwiczenia {section}.{cwicz}}

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.

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 \to Y$ określenie, że $f$ jest suriekcją, będzie oznaczało, że $f$ jest suriekcją na zbiór $Y$ .

ład

$\emptyset$ jest suriekcją na $\emptyset$ , ale nie jest suriekcją na

żaden inny zbiór,

${(\emptyset, \emptyset)}$ jest suriekcją na zbiór ${\emptyset}$

i nie jest suriekcją na ${{\emptyset}, \emptyset}$ ,

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

${1, 0}$ ,

funkcja $f : N \to 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$ .

ład

Fakt [Uzupelnij]

Funkcja $f : X \to Y$ jest suriekcją wtedy i tylko wtedy, gdy istnieje funkcja $g : Y \to X$ taka, że $f \circ g = 𝕀_{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.

{cwicz}{1} {hint}{0} {Ćwiczenie {section}.{cwicz}}

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

Solution.: 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 ∖ {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 ∖ B$ lub $y_{2} \in B ∖ 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ą.

{Koniec ćwiczenia {section}.{cwicz}}

{cwicz}{1} {hint}{0} {Ćwiczenie {section}.{cwicz}}

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

Solution.: 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))$ .

Parser nie mógł rozpoznać (nieznana funkcja „\alignedA”): {\displaystyle \alignedA & = & \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\}) \\ \endaligned}

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 niespusty, 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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned\vec{f}^{-1}(\vec{f}(A)) & = & (\bigcup \{\{a\}:a\in A\}) \\ \vec{f}^{-1}(\vec{f}(A)) & = & A. \endaligned}

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 $𝒫 (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 zbióró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ą.

{Koniec ćwiczenia {section}.{cwicz}}

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$ .

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

$f : X \to Y$ ,

$f$ jest iniekcją,

$f$ jest suriekcją na $Y$ .

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

Twierdzenie [Uzupelnij]

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 [Uzupelnij]

Z cwiczenia Uzupelnic ex:injekcjaCzesciowaOdwracanie| 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 \to 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 [Uzupelnij]

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

Dowód [Uzupelnij]

Jeśli funkcja częściowe $g \circ f$ jest pusta to jest iniekcją. W przeciwnym razie weźmy dwie dowolne (niekoniecznie różne) pary należace 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ą.

{cwicz}{1} {hint}{0} {Ćwiczenie {section}.{cwicz}}

Udowodnij że w twierdzeniu Uzupelnic thm:iniekcjeZlozenie| implikacja w przeciwną stronę nie jest prawdziwa.

Solution.: Rozważmy funkcje częściowe $f = {(0, 0)}$ oraz

$g = {(0, 1), (1, 1)}$ . Wtedy $g \circ f = {(0, 1)}$ a więc jest iniekcją, podczas gdy funkcja $g$ iniekcją nie jest.

{Koniec ćwiczenia {section}.{cwicz}}

Twierdzenie [Uzupelnij]

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

Dowód [Uzupelnij]

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ą.

{cwicz}{1} {hint}{0} {Ćwiczenie {section}.{cwicz}}

Udowodnij że w twierdzeniu Uzupelnic thm:suriekcjeZlozenie| implikacja w przeciwną stronę nie jest prawdziwa.

Solution.: 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}$ .

{Koniec ćwiczenia {section}.{cwicz}}

{cwicz}{1} {hint}{0} {Ćwiczenie {section}.{cwicz}}

W cwiczeniu Uzupelnic ex:ObrazyKontr| pokazaliśmy, że poniższe równości nie są prawdziwe dla wszystkich funkcji. Udowodnij, że

dla funkcji $f : X \to 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ą

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

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

Solution.

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

\vec{f} (A_{1} \cap A_{2}) ⊊ \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} ∖ A_{2}$ oraz $x_{2} \in A_{2} ∖ 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ą.

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 ∖ {x_{1}}$ . Wtedy

{y} = \vec{f} (X ∖ A_{1})

a więc $y \in \vec{f} (X ∖ 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) ∖ \vec{f} (A_{1})$ . Wynika stąd, że zbiory $y \notin \vec{f} (X) ∖ \vec{f} (A_{1})$ i $\vec{f} (X ∖ 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 ∖ 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) ∖ \vec{f} (A_{1}) = \vec{f} (A_{2}) = \vec{f} (X ∖ A_{1})

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

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 ∖ 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ą.

{Koniec ćwiczenia {section}.{cwicz}}

{cwicz}{1} {hint}{0} {Ćwiczenie {section}.{cwicz}}

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

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

jest iniekcją.

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

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}$ .

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 pierwszym równość ta implikuje $x_{1} = x_{2}$ oraz $y_{1} = y_{2}$ . A więc funkcja $f$ jest iniekcją.

{Koniec ćwiczenia {section}.{cwicz}}

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.

Twierdzenie [Uzupelnij]

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

Dowód [Uzupelnij]

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 𝒫 (X) : x \in X \land 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 𝒫 (X) \times Y : \exists_{x \in X} k = [x]_{\sim_{f}} \land f (x) = y} .

Zauważmy, że $h$ rzeczywiście jest funkcją, gdyż, zgodnie 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$ .

{cwicz}{1} {hint}{0} {Ćwiczenie {section}.{cwicz}}

Dla poniższych funkcji podaj przykład funkcji $g, h$ oraz zbioru $Z$ z twierdzenia o faktoryzacji Uzupelnic thm:faktoryzacja|

Niech $K$ będzie zbiorem okręgów na płaszczyźnie, funkcja

$f : K \to R$ niech przypisuje okręgom długości ich średnic

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

Solution.

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.

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.

{Koniec ćwiczenia {section}.{cwicz}}

Produkt uogólniony

W wykładzie (Relacje) 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.

Produktem uogólnionym zbioru $X$ nazwiemy zbiór $ℙ X$ zdefiniowany następująco

ℙ X \overset{def}{\equiv} {f \in 𝒫 (X \times ⋃ X) : (f : X \to ⋃ X) \land \forall_{x \in X} f (x) \in x} .

Czyli zbiór $ℙ 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 Wyklad4, aksjomat wyboru 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 [Uzupelnij]

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

Dowód [Uzupelnij]

Jeśli któryś ze zbiorów $A, B$ jest pusty to $ℙ {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 : ℙ {A, B} \to A \times B$ . Dla dowolnej funkcji $h \in ℙ {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 $ℙ {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 ℙ {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 ℙ {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ą.

{cwicz}{1} {hint}{0} {Ćwiczenie {section}.{cwicz}}

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

Solution.: Niech $A = B = {0, 1}$ . Wtedy $A \times B = {(0, 0), (0, 1), (1, 0), (1, 1)}$ oraz

$ℙ {A, B} = ℙ {A} = {(A, 0), (A, 1)}$ . Ponieważ obraz każdej funkcji ze zbioru $ℙ {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ą.

{Koniec ćwiczenia {section}.{cwicz}}

Twierdzenie Knastra-Tarskiego (patrz Bronisław Knaster i Alfred Tarski

W tym rozdziale przedstawimy podstawową wersję twierdzenia Knastra-Tarskiego o punktach stałych funkcji monotonicznych oraz kilka przykładów zastosowań. Ogólną wersję tego twierdzenia udowodnimy w rozdziale Wyklad 12. Dobre porzadki.

Funkcję $f : 𝒫 (X) \to 𝒫 (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.

{cwicz}{1} {hint}{0} {Ćwiczenie {section}.{cwicz}}

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

Solution.: 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$ .

{Koniec ćwiczenia {section}.{cwicz}}

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

f (x) = x .

{cwicz}{1} {hint}{0} {Ćwiczenie {section}.{cwicz}}

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

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

$f : 𝒫 (𝒫 (X)) \to 𝒫 (𝒫 (X))$ jest określona wzorem $f (x) = {⋃ x, ⋂ x}$ ,

$f : 𝒫 (X^{2}) \to 𝒫 (X^{2})$ jest określona wzorem $f (r) = r^{- 1}$ ,

Solution.

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

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

1. dla dowolnego $x \in X$ mamy $f ({x}) = {⋃ {x}, ⋂ {x}} = {x, x} = {x}$ ,

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

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

$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 $𝕀_{X}$ .

{Koniec ćwiczenia {section}.{cwicz}}

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)}$ .

{cwicz}{1} {hint}{0} {Ćwiczenie {section}.{cwicz}}

Niech $X$ będzie niepustym zbiorem. Udowodnij, że dla funkcji $f : 𝒫 (X) \to 𝒫 (X)$ zdefiniowanej wzorem $f (A) = X ∖ A$ nie istnieje punkt stały.

Solution.: 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 ∖ F$ , a więc mamy

F = X ∖ F

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

{Koniec ćwiczenia {section}.{cwicz}}

Punkt $x_{0} \subset X$ jest najmniejszym punktem stałym funkcji $f : 𝒫 (X) \to 𝒫 (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.

Punkt $x_{0} \subset X$ jest największym punktem stałym funkcji $f : 𝒫 (X) \to 𝒫 (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. ład Dla funkcji $f : 𝒫 (𝒫 (X)) \to 𝒫 (𝒫 (X))$ określonej wzorem $f (A) = {⋂ 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$ . ład

Twierdzenie [Uzupelnij]

[Knaster-Tarski]

Każda monotoniczna funkcja $f : 𝒫 (X) \to 𝒫 (X)$ posiada najmniejszy i największy punkty stałe.

Dowód [Uzupelnij]

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

f (⋃ L) \supset f (x) \supset x .

Wobec tego również

f (⋃ L) \supset ⋃ L

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

f (f (⋃ L)) \supset f (⋃ L) .

Wobec czego również $f (⋃ L) \in L$ . Ponieważ każdy element $L$ jest podzbiorem $⋃ L$ , to również $f (⋃ L) \subset ⋃ L$ . Stąd i z równania Uzupelnic eq:fixpointInclusion1| otrzymujemy

f (⋃ L) = ⋃ L

a więc $⋃ 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 $⋃ L$ , co oznacza dokładnie, że $⋃ 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 $⋂ U$ jest najmniejszym punktem stałym. Z monotoniczności $f$ mamy dla każdego $x \in U$

f (⋂ U) \subset f (x) \subset x

skąd otrzymujemy

f (⋂ U) \subset ⋂ U

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

f (f (⋂ U)) \subset f (⋂ U)

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

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

f (A) \overset{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 Uzupelnic thm:KnasterTarski| 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 $ω$ . Jest to najmniejszy zbiór induktywny będący podzbiorem $X$ . W rozdziale Rozdział o liczbach naturalnych pokażemy, że zbiór $ω$ jest również podzbiorem każdego innego zbioru induktywnego (dociekliwi mogą spróbować udowodnić to już teraz). ład

{cwicz}{1} {hint}{0} {Ćwiczenie {section}.{cwicz}}

Niech $X$ będzie ustalonym zbiorem i $R \subset X^{2}$ będzie dowolną relacją. Zdefiniujmy funkcję $f : 𝒫 (X^{2}) \to X^{2}$ następująco $f (S) = (S \circ S) \cup R$ . Udowodnij, że funkcja $f$ jest monotoniczna. Co jest najmniejszym, a co największym punktem stałym funkcji $f$ ?

Solution.: Monotoniczność wynika z podstawowych własności złożenia relacji. Weźmy dowolne zbiory $A \subset B \subset X^{2}$ .

Wtedy

f (B) = (B \circ B) \cup R \supset (A \circ A) \cup R = f (A) .

Łatwo sprawdzić, że największy punkt stały to $X^{2}$ .

Z definicji funkcji wynika, że każdy punkt stały jest nadzbiorem $R$ . Przypuśćmy, że $S$ jest punktem stałym wtedy $S = S \circ S \cup R$ , a więc $S \supset S \circ S$ . Wynika stąd, że $S$ musi być relacją przechodnią. Podsumowując, każdy punkt stały funkcji $f$ jest relacją przechodnią będącą nadzbiorem $R$ . Niech $\bar{R}$ będzie przechodnim domknięciem relacji $R$ . Wiemy, że jest to najmniejsza relacja przechodnia będąca nadzbiorem $R$ . Jest więc mniejsza od wszystkich punktów stałych funkcji $f$ . Pokażemy, że jest ona punktem stałym. Wiemy, że

f (\bar{R}) = (\bar{R} \circ \bar{R}) \cup R \subset \bar{R} .

W dowodzie twierdzenia Uzupelnic thm:KnasterTarski| Knastra-Tarskiego pokazujemy, że najmniejszy punkt stały jest równy $⋂ U$ , gdzie $U = {x : f (x) \subset x}$ . W rozważanym przypadku pokazaliśmy, ze relacja $\bar{R} \in U$ oraz, że wszystkie punkty stałe są od niej większe. Wynika stąd, że $\bar{R}$ jest najmniejszym punktem stałym funkcji $f$ .

{Koniec ćwiczenia {section}.{cwicz}}

{cwicz}{1} {hint}{0} {Ćwiczenie {section}.{cwicz}}

Niech $f : 𝒫 (𝒫 (N)) \to 𝒫 (𝒫 (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?

Solution.: Najpierw pokażemy monotoniczność. Weźmy dowolne zbiory $A \subset B \subset 𝒫 (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 indukcje ze względu na liczbę elementów zbioru. Niech $S$ będzie punktem stałym funkcji $f$ .

Baza indukcji. Z definicji funkcji $f$ wynika, że dla dowolnego zbioru

$A \subset 𝒫 (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.

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 ∖ {a} \in S$ . Z bazy indukcji otrzymujemy, że ${a} \in S$ . Z definicji funkcji $f$ wynika, że $(A ∖ {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 pierwszysm 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$ .

{Koniec ćwiczenia {section}.{cwicz}}

Lemat Banacha patrz (Stefan Banach)

Twierdzenie Knastra-Tarskiego posłuży nam do udowodnienia lematu Banacha, który z kolei wykorzystamy w wykładzie dotyczącym teorii mocy Wyklad teoria mocy

Twierdzenie [Uzupelnij]

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

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

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

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

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

(RYSUNEK 6.2)

Dowód [Uzupelnij]

Rozważmy funkcję $F : 𝒫 (X) \to 𝒫 (X)$ zdefiniowaną następująco. Dla dowolnego $A \subset X$ niech

F (A) = X ∖ \vec{g} (Y ∖ \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 ∖ \vec{f} (C_{1}) \supset Y ∖ \vec{f} (C_{2})

\vec{g} (Y ∖ \vec{f} (C_{1})) \supset \vec{g} (Y ∖ \vec{f} (C_{2}))

X ∖ \vec{g} (Y ∖ \vec{f} (C_{1})) \subset X ∖ \vec{g} (Y ∖ \vec{f} (C_{2}))

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

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

A_{2} \overset{def}{\equiv} X ∖ A_{1},

B_{1} \overset{def}{\equiv} \vec{f} (A_{1}),

B_{2} \overset{def}{\equiv} Y ∖ 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} \overset{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 ∖ \vec{g} (Y ∖ \vec{f} (A_{1})) .

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

A_{1} = X ∖ \vec{g} (Y ∖ B_{1}),

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

Odejmując obie strony od $X$ otrzymamy

X ∖ 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.

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

Spis treści

Wprowadzenie

Funkcja jako relacja

Obrazy i przeciwobrazy

Iniekcja i suriekcja

Twierdzenie o faktoryzacji

Produkt uogólniony

Twierdzenie Knastra-Tarskiego (patrz Bronisław Knaster i Alfred Tarski

Lemat Banacha patrz (Stefan Banach)

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia