« poprzedni punkt   następny punkt »


10.2. Zbiory przeliczalne

Definicja 10.2.1

Każdy zbiór równoliczny ze zbiorem liczb naturalnych nazywamy przeliczalnym. Zbiory skończone lub przeliczalne nazywa się co najwyżej przeliczalnymi.

Uwaga. Wprost z definicji wynika, że zbiór jest co najwyżej przeliczalny, jeżeli wszystkie jego elementy można ustawić w ciąg, w którym każdy element występuje tylko raz.

Przykład 10.2.1

(1) Zbiór liczb parzystych P jest przeliczalny, por. Rys. 10.1.1(b)

(2) Zbiór liczb nieparzystych NP jest przeliczalny, bo np. funkcja f(x) = 2x+1 jest bijekcją odwzorowującą zbiór liczb naturalnych N na zbiór liczb nieparzystych.

(3) Zbiór liczb całkowitych jest przeliczalny, bo funkcja f określona warunkowo jako f(x) = 2x-1 dla x>0 i f(x) = -2x dla x £ 0 jest odwzorowaniem różnowartościowym zbioru liczb całkowitych na zbiór liczb naturalnych (przekształca liczby całkowite dodatnie na liczby nieparzyste, a liczby całkowite ujemne i zero na liczby naturalne parzyste).

Lemat 10.2.1

Podzbiór zbioru co najwyżej przeliczalnego jest co najwyżej przeliczalny.

Dowód.

Ponieważ podzbiór zbioru skończonego jest skończony, zatem lemat jest oczywisty dla zbiorów skończonych. Niech X będzie zbiorem przeliczalnym, f - bijekcją taką, że f: N ® X i A -nieskończonym podzbiorem X. Funkcja f pozwala ustawić elementy zbioru X w ciąg (f(i))iÎN. Wykreślając z tego ciągu te elementy, które nie należą do A otrzymamy nieskończony ciąg elementów zbioru A.

Zdefiniujemy funkcję g : N ® A w taki sposób, by kolejnym liczbom naturalnym przyporządkowywała kolejne, jeszcze nie wykorzystane, elementy zbioru A (por. Rys. 10.2.1).

g(0) = f(k0), gdzie k0 = min{i : f(i) Î A}

g(1) = f(k1), gdzie k1 = min{i : f(i)Î A\ {g(0)}}

g(2) = f(k2) ), gdzie k2 = min{i : f(i) Î A\ {g(0), g(1)}} itd.

g(j) = f(kj) ), gdzie kj = min{i : f(i) Î A\{g(0), g(1),...,g(j-1)}}

Zbiór {i : f(i) Î A\{g(0), g(1),...,g(j-1)}} jest niepusty dla każdego j, gdyż w przeciwnym razie zbiór A musiałby być skończony. Co więcej, w tym zbiorze zawsze istnieje element najmniejszy, jako, że zbiór liczb naturalnych i jego podzbiory są dobrze ufundowane (por. punkt 6.6 ). Wynika stąd, że definicja funkcji g jest poprawna. Funkcja g jest odwzorowaniem 'na' A, ponieważ każdy element zbioru A występuje na pewnej pozycji, np, j-tej, w ciągu (f(i))iÎN. Jeśli tak, to po j krokach zostanie on wybrany jako wartość funkcji g. Z konstrukcji funkcji g wynika, że jest różnowartościowa, zatem g ustala równoliczność zbioru A i zbioru N. J

Rys. 10.2.1 Odwzorowanie zbioru liczb naturalnych na nieskończony podzbiór A pewnego zbioru X. Elementy zbioru A odpowiadają zaznaczonym na rysunku kratkom.

Wniosek Przecięcie zbiorów co najwyżej przeliczalnych jest zbiorem co najwyżej przeliczalnym.

Pytanie 10.2.1: Przecięcie zbioru skończonego i przeliczalnego jest skończone, czy przeliczalne?

Lemat 10.2.2

  1. Suma dwóch zbiorów co najwyżej przeliczalnych jest zbiorem co najwyżej przeliczalnym.
  2. Suma przeliczalnej rodziny zbiorów co najwyżej przeliczalnych jest zbiorem co najwyżej przeliczalnym.

Dowód.

Ad 1. Niech zbiory X i Y będą nieskończone, przeliczalne. Zatem elementy tych zbiorów możemy ustawić w ciąg. Przyjmijmy, że X = (xi)iÎN oraz Y = (yi) iÎN. Niech f będzie funkcją, która odwzorowuje N na X È Y w taki sposób, że liczbom parzystym przypiszemy elementy zbioru X, a liczbom nieparzystym elementy zbioru Y. Utworzymy w ten sposób ciąg nieskończony wszystkich elementów zbioru X È Y. Jeśli przecięcie zbiorów X i Y nie jest puste, to niektóre elementy występują w naszym ciągu dwukrotnie. Wykreślając po jednym z powtarzających się elementów i ewentualnie dokonując przenumerowania pozostałych, skonstruujemy funkcję wzajemnie jednoznacznie odwzorowującą N na X È Y. Zatem suma X È Y jest zbiorem przeliczalnym (por. Rys. 10.2.2).

Gdyby oba zbiory X i Y były skończone, to ich suma teorio-mnogościowa też byłaby zbiorem skończonym. Gdyby jeden ze zbiorów, np. X, był skończony, a drugi nie, to elementy zbioru X można dopisać na początku ciągu, odpowiadającego zbiorowi Y. Utworzymy w ten sposób ciąg jest złożony ze wszystkich elementów obu zbiorów.

Ad 2. Niech będzie dana indeksowana rodzina zbiorów X= (Xi)iÎN i niech każdy ze zbiorów Xi będzie przeliczalny. Załóżmy ponadto dla uproszczenia, że zbiory tej rodziny są parami rozłączne (Czytelnik zechce zastosować lemat 10.2.1 i samodzielnie przedyskutować pozostałe przypadki). Wynika stąd, że każdy ze zbiorów rodziny możemy przedstawić w postaci ciągu nieskończonego. Przyjmijmy:

Xi = (xi0, xi1, xi2, xi3, xi4, ...) dla iÎN.

Numerując kolejnymi liczbami naturalnymi najpierw elementy, dla których suma indeksów wynosi 0, potem te dla których suma indeksów wynosi 1, itd. por. Rys. 10.2.3(a), otrzymamy ciąg,

x00, x01, x10, x02, x11, x20, x03, x12, x21, x30, ...

w którym występują wszystkie elementy wszystkich zbiorów rodziny. Zatem suma uogólniona î þ iÎN Xi jest zbiorem przeliczalnym.J

Rys. 10.2.2 Suma nieskończonych zbiorów przeliczalnych jest nieskończonym zbiorem przeliczalnym.

Lemat 10.2.3

Produkt kartezjański dwóch zbiorów przeliczalnych jest zbiorem przeliczalnym.

Dowód.

Niech X i Y będą nieskończonymi zbiorami przeliczalnymi. Niech f i g będą funkcjami ustalającymi równoliczność tych zbiorów i zbioru liczb naturalnych, f : N ® X i g : N ® Y . Oznaczmy f(i) = xi, g(i) = yi,

X= (xi)iÎN oraz Y = (yi) iÎN.

Zbudujmy tablicę nieskończoną odpowiadającą produktowi X ´ Y, tak jak przedstawiono na rysunku 10.2.3(b). Kratka znajdująca się w wierszu i-tym i kolumnie j-tej odpowiada elementowi (xi, yj). Teraz wystarczy elementy tej tablicy ustawić w ciąg. Można to zrobić stosując jak w poprzednim lemacie funkcję pary. Kolejność numerowania elementów została zaznaczona na rysunku 10.2.3(b). J

Rys. 10.2.3 (a) W kolejnych wierszach nieskończonej tablicy umieszczono elementy zbiorów X0 = (x0i)iÎN, X1 =(x1i)iÎN itd. Zaznaczona strzałkami linia opisuje kolejność numerowania elementów sumy uogólnionej zbiorów (Xi)iÎN .

(b) Wiersze tablicy są ponumerowane elementami zbioru X =(xi)iÎN, a kolumny elementami zbioru Y=(yi)iÎN. Zaznaczona linia opisuje kolejność numeracji elementów produktu kartezjańskiego X ´ Y.

Wniosek Zbiór liczb wymiernych jest przeliczalny.

Pytanie 10.2.2 Czy produkt kartezjański dowolnej skończonej rodziny zbiorów przeliczalnych jest zbiorem przeliczalnym?

Zadanie 10.2.1 Udowodnić, że zbiór słów nad alfabetem skończonym jest zbiorem przeliczalnym.

Rozwiązanie.

Niech S oznacza dowolny niepusty, alfabet skończony. Zbiór słów nad tym alfabetem S* jest, jak wiadomo (por. punkt 1.6), sumą uogólnioną zbiorów {l }, S, S2, S3 ... Ponieważ każdy z tych zbiorów jest skończony, jest więc też zbiorem co najwyżej przeliczalnym. Zatem na mocy lematu 10.2.2, zbiór S* jest zbiorem co najwyżej przeliczalnym. Ponieważ nieskończony zbiór słów {a,aa, aaa, aaaa,...}, dla dowolnego znaku a z alfabetu, jest podzbiorem S*, zatem jest to zbiór nieskończony, przeliczalny.


« poprzedni punkt   następny punkt »