Jeśli liczba elementów w zbiorze wynosi n, gdzie n jest liczba naturalną, to mówimy, że jest to zbiór skończony. O dwóch zbiorach skończonych powiemy, że są równoliczne, gdy mają tyle samo elementów.

Pojęcie "tyle samo elementów" przestaje jednak być intuicyjne, gdy dotyczy zbiorów nieskończonych. Na przykład zbiór liczb naturalnych i zbiór liczb naturalnych, z którego wyrzuciliśmy pierwszych 100 elementów. Czy te zbiory mają, czy nie mają "tyle samo elementów"? Przecież z tego drugiego usunęliśmy niemało!

Jeśli zbiory skończone mają tyle samo elementów, to możemy określić funkcję wzajemnie jednoznacznie przekształcającą jeden ze zbiorów na drugi. Taką funkcję możemy otrzymać, np. numerując kolejnymi liczbami naturalnymi elementy zbiorów, tzn. tworząc ciąg elementów pierwszego zbioru, następnie tworząc ciąg elementów drugiego zbioru, i na koniec przypisując i-temu elementowi pierwszego zbioru i-ty element drugiego zbioru (por. wykład IV). Istnienie wzajemnie jednoznacznej funkcji przekształcającej jeden zbiór na drugi oddaje dobrze intuicje równoliczności tych zbiorów: przecież przy pomocy tej wzajemnie jednoznacznej funkcji ustawiliśmy pary, w których poprzednik należy do jednego zbioru, a następnik do drugiego, i w których żaden element nie powtarza się, a każdy występuje tylko raz.

Rys. 10.1.1 (a) Funkcja ustalająca równoliczność zbioru kółeczek i kwadracików. (b) Funkcja ustalająca równoliczność zbioru liczb parzystych i zbioru liczb naturalnych.

Przykład 10.1.1

1. Na rysunku 10.1.1 przedstawiliśmy dwa proste przykłady zbiorów równolicznych. Zbiory kółeczek i kwadracików przedstawione na rysunku 10.1.1(a) mają tyle samo elementów, co łatwo sprawdzić, bo są skończone. Funkcja, zaznaczona na rysunku strzałkami jest jednym z wielu odwzorowań wzajemnie jednoznacznych jednego zbioru na drugi. Gdyby jeden ze zbiorów miał 3 elementy a drugi 5 elementów, to żadne takie odwzorowanie nie byłoby możliwe. Takie zbiory nie są równoliczne. Pojecie równoliczności, w przypadku zbiorów skończonych, jest identyczne z pojęciem posiadania takiej samej liczby elementów.
2. Zbiory na rysunku 10.1.1(b) są nieskończone. Oczywiście zbiór liczb parzystych jest właściciwym podzbiorem zbioru liczb naturalnych N. Mimo to, funkcja f(x) = x div 2 jest wzajemnie jednoznacznym odwzorowaniem zbioru liczb parzystych P na zbiór liczb naturalnych. Funkcja ta ustala więc równoliczność tych zbiorów.
3. Dowolne dwa przedziały zbioru liczb rzeczywistych są równoliczne. Na rysunku 10.1.2(a) przedstawiliśmy funkcję liniową f(x) = (x-a)(d-c)/(b-a)+ c, która jest bijekcją odwzorowującą przedział [a, b] na przedział [c, d].

Rys. 10.1.2 (a) Funkcja ustalająca równoliczność przedziałów [a,b] i [c,d]. (b) Funkcja tangens ustalająca równoliczność zbioru liczb rzeczywistych i przedziału otwartego (-pi/2, pi/2).

Zadanie 10.1.1 Podać funkcję ustalającą równoliczność zbioru N i zbioru N\{0,1,2,3,...,100}.(Wpisz najprostszą możliwą funkcję)

Rozwiązanie: f(x) = x +101.

Dowód.

Ad(1) Jeśli A ~ B, to istnieje funkcja różnowartościowa odwzorowująca A na B. Na mocy definicji 4.3.2 funkcja odwrotna do niej istnieje i jest różnowartościowym odwzorowaniem B na A, czyli B ~ A.

Ad(2) Na mocy pierwszego założenia (A ~ B), istnieje bijekcja f : A ® B. Na mocy drugiego założenia istnieje bijekcja g: B ® C. Ponieważ złożenie tych funkcji f ° g jest też bijekcją i odwzorowuje zbiór A na C (por. lemat 4.3.2) zatem A ~ C. J

Korzystając z lematu 10.1.1 udowodnimy teraz dość zaskakujące twierdzenie, że wszystkie liczby rzeczywiste "zmieszczą się" w dowolnie małym przedziale liczb rzeczywistych.

Dowód.

Posłużymy się najpierw rysunkiem 10.1.2. Po pierwsze funkcja tangens, przedstawiona na rysunku 10.1.2(b) jest wzajemnie jednoznacznym przekształceniem przedziału otwartego (-pi/2, pi/2) na R. Czyli (- pi/2, pi/2) ~ R. Co więcej, funkcja liniowa opisana na rysunku 10.1.2(a) pozwala odwzorować dowolny przedział otwarty np. (a, b), gdzie a < b, na przedział (-pi/2, pi/2). Czyli (a, b) ~ (- pi/2, pi/2). Stąd, na mocy lematu 10.1.1, zbiory (a,b) i R są równoliczne. J

Pytanie 10.1.1: Czy zbiory X = { xÎ N: 0 £ x<10 }i Y={ x² : x Î N i x jest liczbą parzystą <20} są równoliczne?

« poprzedni punkt

następny punkt »