Na tym wykładzie przechodzimy do podstaw teorii mocy. Zdefiniujemy relację równoliczności zbiorów, moc zbiorów, następnie powiemy co to znaczy, że zbiór jest skończony, przeliczalny, oraz wykażemy pewne twierdzenia o zbiorach przeliczalnych.
Uwaga 162.
W powyższej sytuacji piszemy \(\# A=n\) albo \(\text {card}A=n\), albo \(|A|=n\), albo \(\bar {\bar A}=n\) oraz mówimy, że moc zbioru \(A\) jest równa \(n\).
Uwaga 163. Zauważmy, że powyższa definicja wymaga znajomości zbioru liczb naturalnych. Formalna konstrukcja tego zbioru będzie przedstawiona na ostatnim wykładzie. Można jednak zdefiniować pojęcie zbioru skończonego bez używania liczb naturalnych – otóż mówimy, że zbiór jest skończony, gdy nie jest równoliczny z żadnym swoim podzbiorem właściwym (ta definicja pochodzi od Richarda Dedekinda1). Jeśli wśród aksjomatów Teorii Mnogości mamy Pewnik Wyboru, to te definicje są równoważne. Więcej na temat różnych definicji zbiorów skończonych można przeczytać w [3].
Przykład 164. \(\{1,2,3,4\}\sim \{a,b,c,d\}\sim \{5,7,-11,3\}\), wszystkie te zbiory są skończone i mają cztery elementy, piszemy np. \(\# \{5,7,-11,3\}=4\).
Wykażemy teraz kilka, intuicyjnie dość oczywistych, faktów o zbiorach skończonych. W dowodach posłużymy się zasadą indukcji w wersji znanej ze szkoły. Więcej o zasadzie indukcji w Wykładzie 15.
Dowód. Dowód prowadzimy indukcją ze względu na \(n=\# B\).
1. Jeśli \(n=0\) to \(\# B=0\) czyli \(B=\emptyset \), skąd, skoro \(A\subset B\) to \(A=\emptyset \), czyli \(\# A= 0=n\).
2. Niech \(n> 0\) i załóżmy, że nasze twierdzenie zachodzi dla zbiorów \(B\) takich, że \(\# B\leq n\). Weźmy teraz zbiór \(B\) taki, że \(\# B=n+1\).
Jeśli \(A= B\) to wtedy \(\# A=n+1\).
Jeśli \(A\neq B\) (ale z założenia \(A\subset B\)) to mamy \(A \subsetneq B\), zatem istnieje \(b\in B: b\notin A\). Stąd \(A\subset B\setminus \{b\}.\) Wystarczy teraz wykazać poniższy lemat.
Faktycznie, jeśli wykażemy lemat, to skoro \(A\subset B\setminus \{b\}\), to z założenia indukcyjnego mamy \(\# A\leq n\) (i przy okazji \(\# A< \# B\)).
Dowód Lematu 166. Mamy wykazać, że jeśli \(f: B\bij \{1,2,\dots ,n+1\}\) to dla dowolnego \(b\in B\) istnieje bijekcja \(g: B\setminus \{b\}\bij \{1,2,\dots ,n\}\).
1. Niech \(b\) będzie takie, że \(f(b)=n+1\). Wówczas \(g\) definiujemy jako \(f|_{B\setminus \{b\}}\).
2. Niech dla \(b\in \{1,2,\dots ,n\}\) będzie \(f(b)=a\in \{1,2,\dots ,n\}\). Niech \(f^{-1}(n+1)=c\) (zauważmy, że \(c\neq a\)). Definiujemy \(g\) następująco:
\[ g(x)=\begin {cases} f(x), \ x\neq c\\ a, \ x=c. \end {cases} \]
Łatwo sprawdzić, że tak zdefiniowana funkcja \(g\) jest bijekcją. □
Dowód. (\(\Longleftarrow \)). Jeśli \(m=n\) to istnieją bijekcje \(f\) i \(g\) takie, że
\[F: A\bij \{1,2,\dots ,n\} \text { i } g: B\bij \{1,2,\dots ,n\}, \]
a zatem \(g^{-1}\circ f\) jest bijekcją \(A\) na \(B\), zatem \(A\sim B\).
(\(\Longrightarrow \)). Mamy następujące bijekcje: \(f: A\bij \{1,2,\dots ,n\}, g: A\bij B, h: B\bij \{1,2,\dots ,m\} \), a zatem mamy bijekcję
\[h\circ g\circ f^{-1}: \{1,2,\dots ,n\} \bij \{1,2,\dots ,m\},\]
zatem \(\{1,2,\dots ,n\} \subset \{1,2,\dots ,m\}\) i \(\{1,2,\dots ,m\} \subset \{1,2,\dots ,n\}\). Stąd, na podstawie Stwierdzenia 165 mamy \(n\leq m\) i \(m\leq n\), czyli \(m=n\). □
Jako wniosek z poprzednich stwierdzeń dostajemy:
Dowód. Faktycznie, skoro \(A\subset B\) i \(B\bij \{1,\dots ,n\}\) to \(\# A=k\leq n\). □
Kolejnym wnioskiem jest następująca uwaga.
Uwaga 169. Zbiór liczb naturalnych nie jest zbiorem skończonym.
Dowód. Gdyby zbiór liczb naturalnych był zbiorem skończonym, to dla pewnego \(n\in \N \) mielibyśmy
\[\N \sim \{1,\dots ,n\}.\]
Zarazem jednak
\[\{1,\dots ,n,n+1\}\subset \N ,\]
a zatem, ze Stwierdzenia 165 mielibyśmy \(n+1\leq n\), sprzeczność.
□
Zbiór nazwiemy przeliczalnym jeśli jest równoliczny ze zbiorem liczb naturalnych.
Definicja 170. Zbiór \(A\) nazywamy zbiorem przeliczalnym, jeśli
\[A\sim \N .\]
Uwaga 171. O zbiorach przeliczalnych mówimy, że mają moc \(\aleph _0\) (czytamyalef-zero).
Uwaga 172. W niektórych podręcznikach zbiorami przeliczalnymi nazywa się zbiory, które są równoliczne ze zbiorem skończonym lub równoliczne z \(\N \), warto się upewnić jaką definicję stosuje autor. W tych wykładach przyjmujemy, że zbiór przeliczalny jest zbiorem nieskończonym, równolicznym z \(\N \). Zbiór, który jest skończony lub przeliczalny nazywamy zbiorem co najwyżej przeliczalnym.
\(\bullet \) Zbiór liczb parzystych \(2\N \) jest przeliczalny. Faktycznie, \(f: \N \to 2\N \), dana wzorem \(f(k)=2k\) jest bijekcją pomiędzy zbiorem liczb naturalnych a zbiorem liczb parzystych.
\(\bullet \) Zbiór liczb całkowitych \(\Z \) jest zbiorem przeliczalnym. Faktycznie, nietrudno sprawdzić, że funkcja dana wzorem \(f(k)=(-1)^k\lceil \frac {k}{2}\rceil \) jest bijekcją \(\N \) na \(\Z \).
Przy dowodzeniu przeliczalności zbiorów będziemy posługiwać się często następującym faktem.
Uwaga 174. Można powiedzieć, że zbiór nieskończony \(A\) jest przeliczalny wtedy i tylko wtedy gdy jego wyrazy można ustawić w ciąg. Faktycznie, jeśli zbiór \(A\) jest przeliczalny, to istnieje bijekcja \(f: \N \bij A\). Ustawiamy wtedy wyrazy zbioru \(A\) w ciąg następująco:
\[a_1=f(1), a_2=f(2),\ldots \]
I na odwrót, jeśli wyrazy zbioru \(A\) są ustawione w ciąg (nieskończony i różnowartościowy) \(a_1,a_2,a_3,\ldots \) to bijekcję \(f: \N \bij A\) definiujemy przez \(f(k)=a_k,\ k\in \N \).
Poniższe stwierdzenie charakteryzuje podzbiory zbioru przeliczalnego.
Dowód. Niech \(A\) będzie zbiorem przeliczalnym a \(B\) jego podzbiorem. Jeśli \(B\) jest zbiorem skończonym, lub jeśli \(B=A\) to \(B\) spełnia tezę stwierdzenia. Przypuśćmy zatem, że \(B\neq A\) i \(B\) jest zbiorem nieskończonym. Niech \(f\) będzie bijekcją \(f: \N \bij A\). Definiujemy bijekcję \(g: \N \bij B\) następująco. Niech \(k_1\) będzie najmniejszą z liczb \(k\) takich, że \(f(k)\in B\). Bierzemy \(g(1):=f(k_1)\). (Formalnie stosujemy tu tzw. zasadę minimum, zob. Wykład 15). Następnie niech \(k_2\) będzie najmniejszą z liczb \(k\), różnych od \(k_1\) takich, że \(f(k)\in B \). Bierzemy \(g(2):=f(k_2)\), ogólnie definiujemy
\[g(n)=f(k_n),\]
gdzie
\[k_n=\min \{k:k\notin \{k_1,\dots , k_{n-1}\}\wedge f(k)\in B \}.\]
□
Dowód. Skoro zbiór \(A\) jest przeliczalny to istnieje bijekcja
\[h: \N \bij A.\]
Weźmy \(B'=B\setminus A\). Jeśli \(B'\) jest pusty, twierdzenie jest oczywiście prawdziwe. Jeśli \(B'\) jest niepusty ale skończony, czyli \(f:\{1,\dots ,k\}\bij B'\) dla pewnego \(k\in \N \), to definiujemy bijekcję z \(A\cup B=A\cup B'\) w \(\N \) wzorem
\[g(m)=\begin {cases} f(m), \ m\leq k\\ h(m-k), \ m\geq k+1. \end {cases}\]
Z takiego określenia \(g\) od razu wynika, że \(g\) jest bijekcją.
Przypuśćmy teraz, że zbiór \(B'\) jest nieskończony. Zatem, jest nieskończonym podzbiorem zbioru przeliczalnego, czyli, na podstawie Stwierdzenia 175 jest zbiorem przeliczalnym. Istnieje zatem bijekcja
\[f:\N \bij B'.\]
Definiujemy bijekcję \(\N \bij A\cup B'=A\cup B\) następująco:
\[g(m)=\begin {cases} h(k), \text { dla } m=2k-1\\ f(k), \text { dla } m=2k,\\ \end {cases}\]
gdzie \(k=1,2,\dots \)
□
Uwaga 177. Powyższy dowód możemy bardziej obrazowo zapisać tak. Zbiór \(A\cup B\) ustawiamy w ciąg
\[b_1,\ldots ,b_k,a_1,a_2,\ldots \]
gdy zbiór \(B'\) jest skończony i ma \(k\) elementów, oraz w ciąg
\[a_1,b_1,a_2,b_2,\ldots \]
\(a_i\in A, b_i\in B'\), gdy zbiór \(B'\) jest nieskończony.
Jako prosty wniosek (ćwiczenie!) z powyższego mamy następujące stwierdzenie.
Kolejne stwierdzenie mówi o przeliczalności iloczynu kartezjańskiego zbiorów przeliczalnych.
Dowód. Wykażemy najpierw, że zbiór \(\N \times \N \) jest zbiorem przeliczalnym. Faktycznie, jeśli \((k,m)\in \N \times \N \) to funkcja \(f: \N \times \N \to \N \) zdefiniowana wzorem
\[f(k,m)=\frac {(k+m+1)(k+m)}{2}+m\]
jest bijekcją (proszę to sprawdzić jako proste ćwiczenie).
Jeśli teraz weźmiemy bijekcje \(g_1: A\bij \N \) i \(g_2:B\bij \N \) to zestawienie \(f\circ (g_1,g_2)\) jest bijekcją \(A\times B\) na \(\N \times \N \). □
Kolejny lemat dotyczy sumowania zbiorów skończonych.
Dowód.
1. Zauważmy, że sumę \(\bigcup _{n\in N} A_n\) możemy zamienić na sumę zbiorów rozłącznych. Niech \(A_1'=A_1\), niech \(A_2'=A_2\setminus A_1', A_3'=A_3\setminus (A_1'\cup A_2')\dots \) itd. Zbiory \(A_i'\) są parami rozłączne i możemy założyć bez zmniejszenia ogólności, że są one są niepuste (puste pomijamy). Niepustych zbiorów \(A_i'\) może być skończenie lub przeliczalnie wiele.
2. Zakładamy zatem, że mamy zbiory \(A_i\), rozłączne i niepuste, gdzie albo \(i\) należy do zbioru skończonego \(\{1,2,\dots ,n\}\), albo \(i\in \N \). Skoro zbiory \(A_i\) są skończone, to każdy z tych zbiorów jest równoliczny ze zbiorem \(\{1,2,\dots ,k_i\}\), czyli \(A_{i}=\{a_{i1},\dots , a_{ik_i}\}\). Wtedy, jeśli \(i\in \{1,2,\dots ,n\}\) to elementy sumy \(\bigcup _{i} A_i\) są następujące
\[a_{11},a_{12},\ldots , a_{1k_1},a_{21},\ldots , a_{2k_2},\ldots a_{n1},\ldots , a_{nk_n}\]
i suma ta jest zbiorem skończonym. Jeśli \(i\in \N \) to elementy sumy \(\bigcup _{i\in N} A_i\) ustawiamy w ciąg (nieskończony)
\[a_{11},a_{12},\ldots , a_{1k_1},a_{21},\ldots , a_{2k_2},a_{31},\ldots , a_{3k_3},\ldots \]
co kończy dowód. □
Podobnie jak przeliczalności iloczynu kartezjańskiego zbiorów przeliczalnych dowodzimy przeliczalności przeliczalnej sumy zbiorów przeliczalnych.
Dowód. Postępując jak w dowodzie powyżej możemy zmienić \(\bigcup _{n\in N} A_n\) na sumę zbiorów rozłącznych \(A_n'\). Każdy ze zbiorów \(A_n'\) jest podzbiorem zbioru \(A_n\), zatem jest zbiorem skończonym lub przeliczalnym. Oznaczmy przeliczalne \(A_i'\) przez \(B_i\) a skończone przez \(C_i\). Jeśli zbiorów \(B_i\) jest skończenie wiele, to korzystając ze Stwierdzenia 178 mamy przeliczalność \(\bigcup _{i} B_i\) a z Lematu 180 wnioskujemy, że zbiór \(\bigcup _{j} C_j\) jest skończony lub przeliczalny. Zatem \(\bigcup _{n} A_n=\bigcup _{i} B_i\cup \bigcup _{j} C_j\) jest (ze Stwierdzenia 178) zbiorem przeliczalnym.
Jeśli zbiorów \(B_i\) jest nieskończenie wiele, to znaczy, że możemy ustawić je w ciąg \(B_1,B_2,\dots \). Elementy sumy tych zbiorów (rozłącznych) możemy zatem ustawić w taki ciąg:
\[b_{11}, b_{12},b_{21},b_{13},b_{22},b_{31},b_{14},b_{23},b_{32},b_{41}\dots ,\]
gdzie \(B_i=\{b_{i1},\dots ,b_{ij},\dots \}\), a zatem suma ta jest zbiorem przeliczalnym.
Dodając do sumy \(\bigcup _{i} B_i=:B\), która jest zbiorem przeliczalnym sumę \(\bigcup _{j} C_j=:C\), która jest zbiorem skończonym lub przeliczalnym, dostajemy, na podstawie poprzednich wyników, że \(\bigcup _{n\in N} A_n=B\cup C\) jest zbiorem przeliczalnym. □
Uwaga 182. Powyższy dowód możemy zobrazować następująco. Przypuśćmy, że zbiory \(A_i\) są przeliczalne i rozłączne. Ustawmy elementy \(A_1\) w ciąg \(a_{11},a_{12},a_{13}\dots \), elementy \(A_2\) w ciąg \(a_{21},a_{22},a_{23}\dots \) itd., następnie elementy sumy zbiorów \(A_i\) ustawmy w taką tablicę jak poniżej.
\[\begin {array}{cccccc} a_{11} & a_{12} & a_{13} & a_{14} &a_{15}&\dots \\ a_{21} & a_{22} & a_{23} & a_{24} &a_{25}&\dots \\ a_{31} & a_{32} & a_{33} & a_{34} &a_{35}&\dots \\ a_{41} & a_{42} & a_{43} & a_{44} &a_{45}&\dots \\ \dots &&&& \end {array}\]
Wówczas elementy sumy możemy ustawić w ciąg „idąc cygańską ścieżką”, Rysunek 9.1:
Rysunek 9.1:
Zauważmy, że analogiczną „rysunkową” metodę możemy zastosować dla dowodu, że \(\N \times \N \) jest zbiorem przeliczalnym.
Użyjemy teraz powyższych rezultatów by wykazać przeliczalność pewnych zbiorów. Zacznijmy od \(\mathbb {Q}\).
Dowód. Wiemy już, że \(\Z \) i \(\Z \times \N ^*\) są zbiorami przeliczalnymi. (Stwierdzenie 179 i Przykład 173.) Przypomnijmy, że zbiór liczb wymiernych możemy utożsamiać ze zbiorem ilorazów \(\frac {p}{q}\), gdzie \(p\in \Z \), \(q\in \N ^*\) oraz \(p\) i \(q\) są względnie pierwsze. \(\Q \) możemy zatem bijektywnie utożsamiać ze zbiorem par \(A=\{(p,q)\in \Z \times \N ^* \mid \text {NWD}(p,q)=1\}\subset \Z \times \N ^*\). Zbiór \(A\) jest oczywiście nieskończony (zawiera liczby całkowite, czyli pary \((p,1)\), oraz jest podzbiorem zbioru przeliczalnego. Zatem \(\Q \) jest zbiorem przeliczalnym. □
Przypomnijmy teraz oznaczenie: \(\Z [x]\) to wielomiany jednej zmiennej \(x\) o współczynnikach ze zbioru \(\Z \), czyli funkcje \(f:\mathbb {R}\to \R \) postaci \(a_0+a_1x+\dots a_nx^n\), gdzie \(a_i\in \Z \) a jeśli \(a_n\neq 0\) to \(n\) nazywamy stopniem wielomianu \(f\).(Stopień wielomianu zerowego przyjmuje się jako równy \(-\infty \).) Przez \(Z_n[x]\) będziemy oznaczać zbiór wielomianów stopnia co najwyżej \(n\).
Analogicznie definiujemy \(\Q [x]\), jako wielomiany jednej zmiennej \(x\) o współczynnikach ze zbioru \(\Q \).
Dowód. Wielomiany o współczynnikach całkowitych możemy zapisać jako sumę:
\[\Z _n[x]=\sum _{n=0}^{\infty }Z_n[x].\]
Każdy ze zbiorów \(Z_n[x]\) możemy utożsamić ze zbiorem \(\Z \times \Z \cdots \times \Z =\Z ^{n+1}\) przyporządkowując wielomianowi ciąg współczynników, \(a_0+a_1x+\dots a_nx^n\to (a_0,a_1\dots ,a_n)\). Każdy ze zbiorów \(Z_n[x]\) jest zatem przeliczalny, a więc \(\Z [x]\) jest zbiorem przeliczalnym jako suma przeliczalnej ilości zbiorów przeliczalnych. □
Uwaga 185. Analogicznie dowodzimy, że \(\Q [x]\) jest zbiorem przeliczalnym.
Uwaga 187. Nie wszystkie liczby rzeczywiste są algebraiczne. Liczby, które nie są algebraiczne nazywamy niealgebraicznymi lub przestępnymi. Liczbą przestępną jest na przykład \(\pi \), dowód tego faktu jest nietrywialny, [2].
Okazuje się, że liczb algebraicznych jest przeliczalnie wiele.
Dowód. Niech \(A\) oznacza zbiór liczb algebraicznych. \(A\) możemy zapisać jako sumę
\[A=\bigcup _{w\in \Z [x]^*}A_w,\]
gdzie \(A_w\) to zbiór pierwiastków danego wielomianu \(w\). Skoro wielomian \(w\) jest niezerowy, to ma stopień równy \(n\), zatem zbiór \(A_w\) ma co najwyżej \(n\) elementów. Zbiór \(\Z [x]^*\) jest zbiorem przeliczalnym, zatem \(A\) jest przeliczalną sumą zbiorów skończonych, czyli z Lematu 180, jest zbiorem przeliczalnym. □
1 Richarda Dedekind (1831–1916), niemiecki matematyk.