Informatyka MIMUW

Funkcje różnowartościowe. Równoliczność

Niech $\displaystyle f: X\mapsto Y$ będzie dowolną funkcją określoną na zbiorze $\displaystyle X$ o wartościach w zbiorze $\displaystyle Y.$ Przypomnijmy kilka pojęć z teorii mnogości.

DEFINICJA 1.42.

Funkcję $\displaystyle f: X\mapsto Y$ nazywamy iniekcją zbioru $\displaystyle X$ w zbiór $\displaystyle Y$, jeśli jest różnowartościowa, to znaczy, że dla dowolnych elementów $\displaystyle x,y\in X$ z równości $\displaystyle f(x)=f(y)$ wynika, że $\displaystyle x=y.$

DEFINICJA 1.43.

Funkcję $\displaystyle f: X\mapsto Y$ nazywamy suriekcją zbioru $\displaystyle X$ na zbiór $\displaystyle Y$, jeśli każdy element zbioru $\displaystyle Y$ jest wartością funkcji $\displaystyle f,$ to znaczy, że dla dowolnego elementu $\displaystyle y\in Y$ istnieje element $\displaystyle x\in X$ taki, że $\displaystyle y=f(x).$

DEFINICJA 1.44.

Funkcję $\displaystyle f: X\mapsto Y$ nazywamy bijekcją zbioru $\displaystyle X$ na zbiór $\displaystyle Y$, jeśli jest iniekcją i suriekcją.

DEFINICJA 1.45.

Mówimy, że zbiory $\displaystyle X, Y$ są równoliczne, jeśli istnieje bijekcja zbioru $\displaystyle X$ na zbiór $\displaystyle Y$. Mówimy też wtedy, że zbiory $\displaystyle X$, $\displaystyle Y$ są tej samej mocy, co zapisujemy krótko $\displaystyle \text{card}X=\text{card}Y$ lub $\displaystyle \#X=\#Y$. Jeśli zbiór zawiera skończoną liczbę elementów równą $\displaystyle n$ (innymi słowy: jeśli jest równoliczny ze zbiorem $\displaystyle \{1, 2, 3, \ldots , n\}$), to mówimy, że jest zbiorem mocy $\displaystyle n$, co zapisujemy $\displaystyle \text{card}A =n$ lub $\displaystyle \# A =n$.

PRZYKŁAD 1.46.

a) Można wykazać, że zbiór liczb naturalnych jest równoliczny ze zbiorem liczb całkowitych i ze zbiorem liczb wymiernych.
b) Również każdy nieskończony podzbiór zbioru liczb naturalnych (na przykład zbiór liczb parzystych, zbiór liczb nieparzystych, zbiór liczb pierwszych) jest równoliczny z całym zbiorem liczb naturalnych.

DEFINICJA 1.47.

Zbiór $\displaystyle A$ równoliczny ze zbiorem liczb naturalnych nazywamy zbiorem przeliczalnym. Mówimy też, że moc zbioru przeliczalnego $\displaystyle A$ jest równa alef zero, co zapisujemy $\displaystyle card\, A =\aleph_0$ lub $\displaystyle \# A =\aleph_0$.

DEFINICJA 1.48.

Zbiór nieskończony, który nie jest równoliczny ze zbiorem liczb naturalnych, nazywamy zbiorem nieprzeliczalnym.

Twierdzenie 1.49. Zbiór liczb rzeczywistych nie jest równoliczny ze zbiorem liczb naturalnych.

PRZYKŁAD 1.50.

a) Jeśli $\displaystyle a < b$ są dowolnymi elementami zbioru $\displaystyle \overline{\mathbb{R}}$, to każdy z przedziałów $\displaystyle [a,b],(a,b],[a,b),(a,b),$ jest równoliczny ze zbiorem liczb rzeczywistych.
b) Co więcej, można również wykazać, że zbiór punktów płaszczyzny $\displaystyle \mathbb{R}^2=\mathbb{R}\times \mathbb{R}$ jest równoliczny ze zbiorem liczb rzeczywistych.

DEFINICJA 1.51.

Zbiór $\displaystyle A$ równoliczny ze zbiorem liczb rzeczywistych nazywamy zbiorem mocy continuum, co zapisujemy $\displaystyle card\, A =c$ lub $\displaystyle \# A =c.$

PRZYKŁAD 1.52.

Niech

$\displaystyle a \ =\ (0,a_1\ a_2\ a_3 \ \ldots)_3 \ =\ 0+\frac{a_1}{3}+\frac{a_2}{9}+\frac{a_3}{27}+\ldots,$

gdzie $\displaystyle a_i \in \{0, \ 1, \ 2 \}$, będzie ciągiem cyfr rozwinięcia w systemie trójkowym (tj. pozycyjnym systemie o podstawie 3) liczby z przedziału $\displaystyle [0,1]$. Rozważmy kolejno zbiory

$\begin{array}{rll} \displaystyle C_0 & = & [0,1] \\ C_1 & = & \{a\in C_0 : a_1 \neq 1\} \\ C_2 & = & \{a\in C_1 : a_2 \neq 1\} \\ C_3 & = & \{a\in C_2 : a_3 \neq 1\} \\ \vdots & = & \vdots \\ C_{n+1} & = & \{a\in C_n : a_{n+1} \neq 1\} \end{array}$

i tak dalej. Zauważmy, że

$\displaystyle C_1 \ =\ \bigg[\frac{0}{3},\frac{1}{3}\bigg]\cup\bigg[\frac{2}{3},\frac{3}{3}\bigg]\subset C_0$

to zbiór liczb z przedziału $\displaystyle [0,1]$, które w rozwinięciu trójkowym nie mają cyfry 1 na pierwszym miejscu po przecinku, zaś

$\displaystyle C_2 \ =\ \bigg[\frac{0}{9},\frac{1}{9}\bigg]\cup\bigg[\frac{2}{9},\frac{3}{9}\bigg] \cup \bigg[\frac{6}{9},\frac{7}{9}\bigg]\cup\bigg[\frac{8}{9},\frac{9}{9}\bigg]\subset C_1$

to zbiór liczb z przedziału $\displaystyle [0,1]$, które w rozwinięciu trójkowym nie mają cyfry 1 ani na pierwszym, ani na drugim miejscu po przecinku, a ogólnie

$\displaystyle C_{n} \ =\ \{a\in C_{n-1} : a_{n} \neq 1\} \ \subset\ C_{n-1},\quad n>1,$

to zbiór liczb z przedziału $\displaystyle [0,1]$, które w rozwinięciu trójkowym nie mają cyfry 1 po przecinku na żadnym z miejsc od pierwszego aż do $\displaystyle n$-tego włącznie.

Zauważmy, że liczbę $\displaystyle \frac{1}{3}$ można zapisać w systemie trójkowym jako $\displaystyle (0,10000\ldots )_{3}$ bądź też bez użycia cyfry $\displaystyle 1$ za pomocą trójkowego ułamka okresowego: $\displaystyle (0,02222\ldots)_{3}$. Podobnie $\displaystyle \frac{1}{9}=0,010000\ldots =(0,0022222\ldots)_{3}$. Stąd liczby $\displaystyle \frac{1}{3}$, $\displaystyle \frac{1}{9}$,... ., należą do zbiorów $\displaystyle C_1, C_2,\ldots$, pomimo że ich ich zapis trójkowy zawiera cyfrę 1. Można je bowiem zapisać również nie używając jedynki.

Z definicji zbiorów $\displaystyle C_i$ wynika, że

$\displaystyle \ldots \subset C_{n+1}\subset C_{n}\subset \ldots \subset C_{2} \subset C_{1} \subset C_{0}.$

Dowodzi się (zob. twierdzenie Cantora o zstępującym ciągu zbiorów domkniętych w przestrzeni zupełnej), że część wspólna $\displaystyle C_0 \cap C_1 \cap C_2 \cap C_3 \cap \ldots$ nieskończenie wielu zbiorów $\displaystyle C_n$ jest zbiorem niepustym. Zbiór ten zawiera tylko te liczby z przedziału $\displaystyle [0,1]$, które można zapisać w systemie trójkowym bez użycia cyfry 1.

DEFINICJA 1.53.

Zbiór

$\displaystyle C \ =\ \{a=(0, a_1\ a_2\ a_3 \ \ldots)_{3}=\frac{a_1}{3}+\frac{a_2}{9}+\frac{a_3}{27}+\ldots , a_i\in \{0,2\} \}$

tych liczb z przedziału $\displaystyle [0,1]$, które w systemie trójkowym da się zapisać bez użycia cyfry 1, nazywamy trójkowym zbiorem Cantora.

Uwaga 1.54.

Zbiór Cantora jest równoliczny ze zbiorem wszystkich nieskończonych ciągów o wyrazach w zbiorze dwuwartościowym: $\displaystyle \{ 0, 2\}$. Jest więc nieprzeliczalny.