Informatyka MIMUW

1. Oczywiste. Identyczność \( \displaystyle 1_A \) jest tego świadkiem.
2. Funkcja odwrotna do bijekcji jest bijekcją.
3. Złożenie bijekcji jest bijekcją.

1. Suma mnogościowa bijekcji działających na zbiorach rozłącznych i mających rozłączne przeciwdziedziny jest bijekcją.
2. Niech \( \displaystyle f:A \rightarrow B \) i \( \displaystyle g: C \rightarrow D \) będą bijekcjami. Rozważ funkcje \( \displaystyle \Phi: A^C \rightarrow B^D \) zadaną następująco: niech \( \displaystyle \alpha \) będzie pewną funkcją z \( \displaystyle A^C \). \( \displaystyle \Phi ( \alpha ) = f \circ \alpha \circ g^{-1} \). Sprawdź, że \( \displaystyle \Phi \) jest bijekcją.
3. Definiujemy funkcje \( \displaystyle \Upsilon : (A^B)^C \rightarrow A^{ B \times C} \). Niech \( \displaystyle x \) będzie dowolną funkcją ze zbioru \( \displaystyle (A^B)^C \) oraz niech \( \displaystyle b\in B \) i \( \displaystyle c\in C \). \( \displaystyle \Upsilon (x) (b,c) = x(c)(b) \). Sprawdź, że \( \displaystyle \Upsilon \) jest bijekcją.
4. Definiujemy funkcje \( \displaystyle \alpha :A^C \times B^C \rightarrow (A \times B)^C \). Niech \( \displaystyle f,g \) będą funkcjami ze zbiorów odpowiednio \( \displaystyle A^C \) i \( \displaystyle B^C \) oraz niech \( \displaystyle c\in C \). Definiujemy \( \displaystyle \alpha (f,g)(c) = (f(c),g(c)) \). Sprawdź, że \( \displaystyle \alpha \) jest bijekcją.
5. Definiujemy funkcje \( \displaystyle \kappa : A^{B \cup C} \rightarrow A^B \times A^C \). Niech \( \displaystyle x \) będzie funkcją ze zbioru \( \displaystyle A^{B \cup C} \). Definiujemy \( \displaystyle \kappa (x) = (x \mid_B , x\mid_C) \), gdzie \( \displaystyle x \mid_B , x\mid_C \) są odpowiednio zawężeniami funkcji \( \displaystyle x \) do zbiorów \( \displaystyle B \) lub \( \displaystyle C \). Sprawdź, że \( \displaystyle \kappa \) jest bijekcją.
6. Zbiorowi \( \displaystyle A \) przyporządkowujemy jego funkcję charakterystyczną.

Dowody poszczególnych punktów

1. Ustalmy zbiory \( \displaystyle A, B, C \) i \( \displaystyle D \) takie, że \( \displaystyle A \sim_m B \) i \( \displaystyle C \sim_m D \) oraz \( \displaystyle A \cap C = B \cap D = \emptyset \). Definicja równoliczności gwarantuje istnienie bijekcji \( \displaystyle f:A \rightarrow B \) i \( \displaystyle g: C \rightarrow D \). Zdefiniujmy relację \( \displaystyle h = f\cup g \). Niewątpliwie \( \displaystyle h\subset (A\cup C)\times (B\cup D) \), a ponieważ \( \displaystyle A \cap C = \emptyset \) wnioskujemy, że \( \displaystyle h \) jest funkcją. Ponieważ \( \displaystyle f \) i \( \displaystyle g \) były surjekcjami, to również \( \displaystyle h \) jest surjekcją na \( \displaystyle B\cup D \). Ponieważ \( \displaystyle B\cap D = \emptyset \) i funkcje \( \displaystyle f \) i \( \displaystyle g \) były iniekcjami, wnioskujemy, że \( \displaystyle h \) jest iniekcją, co kończy dowód.

2. Niech \( \displaystyle f:A \rightarrow B \) i \( \displaystyle g: C \rightarrow D \) będą bijekcjami. Rozważmy funkcję \( \displaystyle \Phi: A^C \rightarrow B^D \) zdefiniowaną, dla dowolnego \( \displaystyle \alpha\in A^C \) jako

\( \displaystyle \Phi ( \alpha ) = f \circ \alpha \circ g^{-1}. \)

Wykażemy, że \( \displaystyle \Phi \) jest bijekcją. Dla surjektywności ustalmy dowolną funkcję \( \displaystyle \beta\in B^D \), wtedy \( \displaystyle f^{-1} \circ \beta \circ g\in A^C \) i oczywiście \( \displaystyle \Phi(f^{-1} \circ \beta \circ g) =f \circ f^{-1} \circ \beta \circ g \circ g^{-1} = \beta \), co należało wykazać. Pozostaje udowodnić, że \( \displaystyle \Phi \) jest iniekcją. Ustalmy \( \displaystyle \alpha \) i \( \displaystyle \alpha' \) w \( \displaystyle A^C \) takie, że \( \displaystyle \Phi(\alpha) = \Phi(\alpha') \). Wtedy \( \displaystyle f \circ \alpha \circ g^{-1} =f \circ \alpha' \circ g^{-1} \) i obkładając obie strony równości przez \( \displaystyle f^{-1} \) z lewej strony i \( \displaystyle g \) z prawej otrzymujemy \( \displaystyle \alpha = \alpha' \), co dowodzi, że \( \displaystyle \Phi \) jest iniekcją. Dowód jest zakończony.

3. Definiujemy funkcje \( \displaystyle \Upsilon : (A^B)^C \rightarrow
A^{ B \times C} \). Niech \( \displaystyle x \) będzie dowolną funkcją ze zbioru \( \displaystyle (A^B)^C \). Dla dowolnych \( \displaystyle b\in B \) i \( \displaystyle c\in C \) definiujemy \( \displaystyle \Upsilon (x) (b,c) = x(c)(b) \). Pozostaje wykazać, że \( \displaystyle \Upsilon \) jest bijekcją. Dla wykazania iniektywności wybierzmy dwie dowolne funkcje \( \displaystyle x \) i \( \displaystyle x' \) z \( \displaystyle (A^B)^C \). Wtedy, dla dowolnego \( \displaystyle c\in C \) i \( \displaystyle b\in B \) mamy \( \displaystyle x(c)(b)=x'(c)(b) \), czyli, dla dowolnego \( \displaystyle c\in C \) funkcje \( \displaystyle x(c) \) i \( \displaystyle x'(c) \) są równe. Wnioskujemy, że funkcje \( \displaystyle x \) i \( \displaystyle x' \) są identyczne na każdym z argumentów, czyli \( \displaystyle x=x' \), co należało wykazać. Aby wykazać, że \( \displaystyle \Upsilon \) jest surjekcją, ustalmy dowolny \( \displaystyle y\in A^{ B \times C} \) i zdefiniujmy funkcję \( \displaystyle x \) taką, że \( \displaystyle x(c)(b) = y(b,c) \). Oczywiście \( \displaystyle x\in (A^B)^C \) i \( \displaystyle \Upsilon(x) = y \), co należało wykazać.

4. Definiujemy funkcje \( \displaystyle \alpha :A^C \times B^C \rightarrow (A \times B) ^C \). Niech \( \displaystyle f,g \) będą funkcjami ze zbiorów odpowiednio \( \displaystyle A^C \) i \( \displaystyle B^C \) oraz niech \( \displaystyle c\in C \). Definiujemy \( \displaystyle \alpha (f,g)(c) = (f(c),g(c)) \). Ustalmy dwie pary funkcji \( \displaystyle (f,g) \) oraz \( \displaystyle (f',g') \) z \( \displaystyle A^C\times B^C \) i załóżmy, że \( \displaystyle \alpha(f,g) = \alpha(f',g') \), czyli \( \displaystyle (f(c),g(c)) =(f'(c),g'(c)) \), dla każdego \( \displaystyle c \). To implikuje, że \( \displaystyle f=f' \) oraz \( \displaystyle g=g' \), czyli \( \displaystyle \alpha \) jest iniekcją. Dla wykazania surjektywności ustalmy dowolną funkcję \( \displaystyle h\in(A\times B)^C \) i niech \( \displaystyle h_1: C \rightarrow A \) i \( \displaystyle h_2: C \rightarrow B \) będą funkcjami takimi, że \( \displaystyle h(c) = (h_1(c), h_2(c)) \). Wtedy oczywiście \( \displaystyle \alpha(h_1,h_2) = h \), czyli \( \displaystyle \alpha \) jest surjekcją, czego należało dowieść.

5. Definiujemy funkcje \( \displaystyle \kappa : A^{B \cup C} \rightarrow A^B \times A^C \). Dla dowolnego \( \displaystyle x \) elementu zbioru \( \displaystyle A^{B \cup C} \) definiujemy \( \displaystyle \kappa (x) = (x \mid_B , x\mid_C) \), gdzie \( \displaystyle x \mid_B , x\mid_C \) są odpowiednio zawężeniami funkcji \( \displaystyle x \) do zbiorów \( \displaystyle B \) i \( \displaystyle C \). Załóżmy, niewprost, że \( \displaystyle \kappa \) nie jest iniekcją. Istnieją wtedy dwie różne funkcje \( \displaystyle x \) i \( \displaystyle x' \) elementy \( \displaystyle A^{B \cup C} \) takie, że \( \displaystyle \kappa(x) =\kappa(x') \), czyli \( \displaystyle x \mid_B = x' \mid_B \) oraz \( \displaystyle x \mid_C = x' \mid_C \), co jest oczywistą sprzecznością. Dla dowodu surjektywności ustalmy dwie funkcje \( \displaystyle y_1\in A^B \) i \( \displaystyle y_2\in A^C \), wtedy \( \displaystyle y_1\cup y_2\in {B \cup C}\times A \), a ponieważ \( \displaystyle A\cap B = \emptyset \), wnioskujemy, że \( \displaystyle y_1\cup y_2 \) jest funkcją. Oczywiście \( \displaystyle \kappa(y_1\cup y_2) = (y_1,y_2) \) co dowodzi surjektywności.

6. Ustalmy dowolny zbiór \( \displaystyle A \). Zdefiniujmy funkcję \( \displaystyle \alpha:2^A \rightarrow \mathcal{P}(A) \), kładąc \( \displaystyle \alpha(f) = \overrightarrow{f}^{-1} (1) \). Wtedy, jeśli \( \displaystyle \alpha(f) = \alpha(f') \), to \( \displaystyle \overrightarrow{f}^{-1} (1) =\overrightarrow{f'}^{-1} (1) \) i, co za tym idzie, \( \displaystyle \overrightarrow{f}^{-1} (0)=A\setminus\overrightarrow{f}^{-1} (1) = A\setminus\overrightarrow{f'}^{-1} (1)=\overrightarrow{f'}^{-1} (0) \), czyli \( \displaystyle f=f' \), co dowodzi iniektywności. Dla dowodu surjektywności ustalmy dowolny zbiór \( \displaystyle B\subset A \) i zdefiniujmy jego funkcję charakterystyczną jako \( \displaystyle f \) takie, że \( \displaystyle f(x)=1 \), jeśli \( \displaystyle x\in B \) i \( \displaystyle f(x)=0 \), jeśli \( \displaystyle x\notin B \). Otrzymujemy \( \displaystyle \alpha(f) = B \), co dowodzi surjektywności.

Pokaż indukcją na \( \displaystyle n \) prawdziwość następującego zdania: każdy podzbiór zbioru \( \displaystyle n \) jest skończony. Pokaż indukcją na \( \displaystyle n \) prawdziwość następującego zdania: obraz każdego podzbioru \( \displaystyle n \) jest skończony.

Wykażemy przez indukcję, że każdy podzbiór liczby naturalnej jest bijektywny z jakąś liczbą naturalną. Indukcja przebiega ze względu na zmienną \( \displaystyle n \).

• Jeśli \( \displaystyle n=0=\emptyset \), to jedynym podzbiorem zbioru pustego jest on sam. Zbiór pusty jest równoliczny ze sobą samym poprzez funkcję pustą.
• Załóżmy, że każdy podzbiór \( \displaystyle n \) jest równoliczny z jakąś liczbą naturalną. Rozważmy \( \displaystyle n+1 \) i dowolne \( \displaystyle B\subset n+1 \). Jeśli \( \displaystyle n\notin B \), to \( \displaystyle B \) jest równoliczny z jakąś liczbą naturalną na mocy założenia indukcyjnego. Jeśli \( \displaystyle n\in B \), rozważmy \( \displaystyle B\setminus\{n\} \) -- jest to zbiór, do którego można zastosować założenie indukcyjne i otrzymać liczbę naturalną \( \displaystyle m \) oraz bijekcję \( \displaystyle f \) pomiędzy \( \displaystyle B\setminus\{n\} \) a \( \displaystyle m \). Wtedy zbiór \( \displaystyle B \) jest równoliczny z \( \displaystyle m+1 \) poprzez bijekcję:

\( \displaystyle f'(x) = \begin{cases} f(x), & \mbox{ jeśli } x\neq n, \\ m, & \mbox{ jeśli } x = n.\end{cases} \) Istnienie tej bijekcji dowodzi prawdziwości kroku indukcyjnego.

Pierwsza część ćwiczenia została dowiedziona.

Wykażemy teraz, że obraz zbioru skończonego poprzez funkcję jest skończony. Ustalmy w tym celu dowolny zbiór skończony \( \displaystyle A \) i funkcję \( \displaystyle f:A \rightarrow B \). Ponieważ \( \displaystyle A \) jest skończony, istnieje liczba naturalna \( \displaystyle n \) i bijekcja \( \displaystyle g \) pomiędzy \( \displaystyle n \) i \( \displaystyle A \). Możemy założyć, że \( \displaystyle \overrightarrow{f} (A)=B \). Definiujemy funkcję \( \displaystyle h:B \rightarrow A \) jako \( \displaystyle h(b) =\bigcap \overrightarrow{(f\circ g)}^{-1} (\{b\}) \) -- funkcję, która dla dowolnego elementu \( \displaystyle b\in B \) zwraca najmniejszą liczbę naturalną w \( \displaystyle n \), która jest przekształcana przez \( \displaystyle g \) w \( \displaystyle \overrightarrow{f}^{-1} (\{b\}) \). Otrzymaliśmy bijekcję pomiędzy \( \displaystyle B \) a pewnym podzbiorem liczby naturalnej. Korzystając z poprzedniego punktu i z przechodniości relacji równoliczności, wnioskujemy, że \( \displaystyle B \) jest skończony.