Funkcje i elementy teorii mocy
Wstęp 2
1. Funkcje 3
2. Własności funkcji 6
3. Obrazy zbiorów wyznaczane przez funkcje i ich własności 11
4. Przeciwobrazy zbiorów wyznaczone przez funkcje i ich własności 14
5. Elementy teorii mocy. Zbiory przeliczalne i nieprzeliczalne oraz ich własności 16
Bibliografia 23
Wstęp
Funkcje są podstawowymi narzędziami stosowanymi między innymi w informatyce
do opisu (modelowania, charakteryzowania, specyfikacji) własności szeroko pojętych
systemów informacyjnych, a przez to również systemów oprogramowania.
Pokażemy, że znane ze szkoły pojęcie funkcji  definiowane tam jako pewnego
rodzaju przyporządkowanie  można precyzyjnie zdefiniować za pomocą
odpowiednich relacji. Zostaną przedstawione i omówione podstawowe własności
funkcji. Zdefiniujemy także i udowodnimy własności obrazów i przeciwobrazów
zbiorów wyznaczonych przez funkcje.
Istotną częścią tego modułu jest przedstawienie i omówienie podstawowych pojęć
związanych z teorią mocy. Udowodnimy między innymi, że liczb naturalnych jest
 tyle samo , co liczb wymiernych. Zwieńczeniem modułu jest udowodnienie, że
liczb rzeczywistych nie jest  tyle samo , co liczb naturalnych oraz faktu, że istnieje
nieskończenie wiele rodzajów nieskończoności.
2
1. Funkcje
X Y X
Przypomn3
my szkolną definicję funkcji. Funkcją odwzorowującą zbiór X w zbiór
Y nazywamy takie przyporządkowanie, które każdemu elementowi ze zbioru X
przyporządkowuje dokładnie jeden element ze zbioru Y.
Przykład 1
Bez trudu można zauważyć, że przyporządkowanie na rysunku 1a jest funkcją
(ponieważ spełnia podaną wyżej definicję), zaś przyporządkowanie dane na rysunku
1b nie jest funkcją. W zbiorze X istnieją bowiem takie elementy, którym nie są
przyporządkowane żadne elementy zbioru Y oraz są w zbiorze X takie elementy,
którym przyporządkowano więcej niż jeden element ze zbioru Y.
a b
Rysunek 1
Jeżeli funkcja f odwzorowuje zbiór X w zbiór Y, to zbiór X nazywamy zwyczajowo
dziedziną funkcji f, zaś zbiór Y przeciwdziedziną. Zbiór tych elementów przeciwdziedziny,
które są wartościami funkcji dla pewnych argumentów, nazywamy zbiorem wartości
funkcji. Zbiór wartości funkcji f : X Y oznaczać będziemy przez f(X). Zwyczajowo
również elementy dziedziny funkcji (zbioru X) nazywamy argumentami funkcji, zaś
przyporządkowane tym argumentom elementy zbioru Y nazywamy wartościami
funkcji (jeżeli x jest argumentem, to zapis f(x) zwyczajowo oznacza wartość funkcji f
dla argumentu x).
Zauważmy, że funkcję możemy charakteryzować za pomocą odpowiedniego zbioru
par uporządkowanych typu (x, f(x)), będących elementami iloczynu kartezjańskiego
X × Y. Funkcje zatem możemy definiować jako podzbiory iloczynów kartezjaÅ„skich,
a przez to jako relacje.
RelacjÄ™ f Ä…" X × Y nazywamy funkcjÄ… odwzorowujÄ…cÄ… zbiór X w zbiór Y, jeżeli speÅ‚nia
ona dwa następujące warunki:
(a) " " [(x, y) " f '" (x, z) " f Ò! y = z],
x"X y,z"Y
(b) " " (x, y) " f.
x"X y"Y
Przy czym  jeżeli relacja f spełnia tylko warunek (a)  to nazywamy ją funkcją
częściową (warunek ten nazywany jest warunkiem prawostronnej jednoznaczności).
Jeżeli spełnione są oba warunki, to funkcję f nazywamy czasem także funkcją totalną.
3
X Y
f
f(X)
Oczywiście widać, że podana wyżej definicja funkcji jako relacji pewnego typu
odpowiada definicji szkolnej. Warunek (b) stwierdza bowiem, że każdemu elementowi
ze zbioru X ma być przyporządkowany element ze zbioru Y. Warunek (a) determinuje,
że przyporządkowanie możliwe jest tylko na jeden sposób.
Zauważmy, że zgodnie z powyższą definicją zbiór wartości funkcji jest podzbiorem
przeciwdziedziny. Zauważmy również, że zbiór wartości nie musi być całą
przeciwdziedziną. Intuicję zbioru wartości funkcji przedstawia rysunek 2.
Rysunek 2
Przykład 2
Rozważmy relacjÄ™ f Ä…" R × R, danÄ… zależnoÅ›ciÄ… " [(x, y) " f Ô! x 2 + y = 4].
x,y"R
Pokażemy, że relacja ta jest funkcją.
Wez
my dowolne liczby rzeczywiste x, y, z, spełniające warunek:
(x, y) " f '" (x, z) " f.
KorzystajÄ…c z definicji relacji f, mamy:
x2 + y = 4 '" x2 + z = 4,
czyli:
x2 = 4  y '" x2 = 4  z,
stÄ…d:
y = z.
Spełniony jest zatem warunek prawostronnej jednoznaczności. Prawdziwy jest
również drugi z warunków funkcyjnych, mamy bowiem:
" " (x, y) " f Ô! " " (y = 4  x2).
x"R y"R x"R y"R
Sprawdzenie tego warunku sprowadza się do próby wyznaczenia wartości y
z warunku definiującego relację f i sprawdzenia, czy tak wyznaczona wartość y
należy do przeciwdziedziny.
Przykład 3
Rozważmy relacjÄ™ f Ä…" R × R, danÄ… zależnoÅ›ciÄ… " [(x, y) " f Ô! x2 + y2 = 5 ].
x,y"R
Zauważmy, że relacja ta nie jest funkcją częściową. Mamy bowiem: (1, 2) " f oraz
(1,  2) " f. Istnieją zatem dwie różne liczby przyporządkowane liczbie 1.
4
Jeżeli relacja jest funkcją (spełnia oba warunki funkcyjne), to możemy zmienić formę
zapisu i stosować poniższą notację:
(a) zamiast f Ä…" X × Y, piszemy f : X Y  czytamy: funkcja f odwzorowuje zbiór
X w zbiór Y,
(b) zamiast (x, y) " f piszemy f(x) = y  czytamy: element y jest wartością funkcji f
dla argumentu x.
5
2. Własności funkcji
Przedstawimy teraz definicje i przykłady podstawowych typów funkcji, a mianowicie
funkcji różnowartościowych i funkcji  na .
Jeżeli dla dowolnych różnych argumentów funkcja f : X Y przyjmuje różne
wartości, to funkcję taką nazywamy funkcją różnowartościową (lub iniekcją).
Symbolicznie funkcję nazywamy różnowartościową, jeżeli spełniony jest warunek:
(*) " [x1 `" x2 Ò! f(x1) `" f(x2)]1.
x1,x2"X
Zauważmy, że na mocy prawa kontrapozycji2 warunek ten jest równoważny
warunkowi:
(**) " [f(x1) = f(x2) Ò! x1 = x2]3.
x1,x2"X
Przykład 4
Funkcja liniowa f : R R, dana wzorem f(x) = 2x + 1, jest funkcjÄ…
różnowartościową.
Dla uzasadnienia powyższego skorzystajmy z warunku (**).
Załóżmy, że x1 oraz x2 są dwiema dowolnymi liczbami rzeczywistymi. Załóżmy
dodatkowo, że spełniona jest równość f(x1) = f(x2). Mamy teraz:
2x1 + 1 = 2x2 + 1,
stÄ…d:
x1 = x2.
Przykład 5
Funkcja cos : R R nie jest różnowartościowa, gdyż cos(0) = 1 oraz cos(2Ą) = 1.
Istnieją zatem dwa różne argumenty mające przyporządkowaną tę samą wartość.
Przykład 6
Sprawdz
my, czy funkcja f : (2, +") R, dana wzorem f(x) = x2  4x + 1, jest
różnowartościowa. Skorzystajmy z warunku (**).
Załóżmy, że x1 oraz x2 są dwiema dowolnymi liczbami rzeczywistymi większymi od
2 (x1, x2 " (2, +")). Załóżmy dodatkowo, że spełniona jest równość f(x1) = f(x2).
Mamy teraz:
x12  4x1 + 1 = x2 2  4x2 + 1.
1
Warunek ten mówi, że różnym argumentom są przyporządkowane różne wartości, stąd
nazwa  różnowartościowa .
2
(Ä… Ò! ²) Ô! (Ź² Ò! Źą).
3
Warunek mówi, że jeżeli wartości funkcji są równe, to równe również muszą być argumenty
wyznaczające te wartości.
6
Przekształcając kolejno, otrzymujemy:
x12  x22  4x1 + 4x2 + 1  1 = 0,
(x1  x2)Å"(x1 + x2)  4(x1  x2) = 0,
(x1  x2)Å"[(x1 + x2)  4] = 0,
(x1  x2) = 0 lub (x1 + x2)  4 = 0,
(x1  x2) = 0 lub (x1 + x2) = 4.
Oczywiście, drugi składnik alternatywy jest fałszywy, bo suma dwóch liczb większych
od 2 nie może być równa 4 (przypomn3
my, że x1, x2 " (2, +")). Zatem prawdziwy
musi być pierwszy składnik alternatywy, czyli:
(x1  x2) = 0,
x1 = x2.
Funkcje f : X Y, takie, że f(X) = Y nazywamy funkcjami  na (inaczej surjekcjami).
Inaczej powiemy, że funkcja f : X Y jest surjekcją, jeżeli spełniony jest poniższy
warunek:
" " f(x) = y.
y"Y x"X
Przykład 7
Funkcja f : (2, +") (3, +"), dana wzorem f(x) = x + 1, jest surjekcjÄ…. Mamy
bowiem:
X Y
" " (f(x) = y) Ô! " " (x = y  1).
y"(3, +") x" (2, +") y"(3, +") x" (2, +")
Oczywiście, łatwo można zauważyć, że prawa strona równoważności jest
prawdziwa.
Przykład 8
Funkcja cos : R R nie jest surjekcją, gdyż dla żadnego argumentu nie otrzymamy
wartości 10. Możemy napisać:
Ź " (cos(x) = 10).
x"R
Funkcje równocześnie będące różnowartościowe i  na nazywamy b3
ekcjami lub
odwzorowaniami wzajemnie jednoznacznymi.
Graf przykładowej b3
ekcji  dobrze prezentujący intuicję tego pojęcia
 przedstawiamy na rysunku 3.
Rysunek 3
7
X Y X
f f -1 Y
Twierdzenie 1
Jeżeli funkcja f : X Y jest b3
ekcją, to istnieje funkcja g : Y X, o własnościach:
" [g(f(x)) = x] oraz " [f(g(y)) = y].
x"X y"Y
FunkcjÄ™ g nazywamy funkcjÄ… odwrotnÄ… do f i oznaczamy zwyczajowo symbolem f 1.
Intuicję pojęcia funkcji odwrotnej prezentuje rysunek 4.
Rysunek 4
Twierdzenie 2
Jeżeli f : X Y jest b3
ekcją, to f 1 : Y X jest również b3
ekcjÄ….
Przykład 9
Rozważmy funkcję f : R+ R, daną wzorem4 f(x) = ln(x). Jest ona oczywiście
b3
ekcją (dla różnych liczb rzeczywistych dodatnich istnieją różne wartości logarytmu
naturalnego oraz każda liczba rzeczywista jest logarytmem naturalnym pewnej liczby
rzeczywistej dodatniej).
Funkcją odwrotną do funkcji f określonej wzorem f(x) = ln(x) jest funkcja g : R R+
dana wzorem g(x) = ex.
Mamy bowiem dla dowolnych liczb rzeczywistych x " R+ oraz y " R:
g(f(x)) = eln(x) = x oraz f(g(y)) = ln(ey) = y.
Przykład 10
Dla funkcji f : R , danej wzorem f(x) = arctg(x), funkcjÄ… odwrotnÄ… jest
funkcja f 1: R, dana wzorem f 1(x) = tg(x).
Rozważmy funkcje f : X Y oraz g : Z T, spełniające zależność f(X) ą" Z5. Funkcję
h : X T, spełniającą zależność h(x) = g(f(x)), nazywamy złożeniem funkcji f oraz g
i oznaczamy symbolicznie g ż f 6. Intuicję graficzną złożenia funkcji dla przypadku,
gdy Y = Z przedstawia rysunek 5.
4
ln  funkcja logarytmu naturalnego.
5
Zbiór wartości funkcji f jest zawarty w dziedzinie funkcji g.
6
Zwróćmy uwagę na odwrotną kolejność zapisu, podobnie jak przy złożeniu relacji.
8
Rysunek 5
Przykład 11
Rozważmy funkcję f : R+ R, daną wzorem f(x) = ln(x), oraz funkcję g : R R, daną
wzorem g(x) = arctg(x). Przypomn3
my, że zbiór wartości funkcji f(R+) jest równy
R, zatem jest spełniony odpowiedni warunek wystarczający na istnienie złożenia
X f Y g T
funkcji g ż f (zbiór wartości pierwszej funkcji musi być zawarty w dziedzinie drugiej
funkcji).
f(X)
Złożenie to wyraża się zależnością:
(g ż f)(x) = g(f(x)) = g(ln(x)) = arctg(ln(x)).
A
atwo zauważyć, że dla powyższych funkcji nie istnieje złożenie f ż g, bowiem zbiór
wartości funkcji g (przedział ) nie zawiera się w dziedzinie funkcji f.
Zachodzą następujące własności złożenia funkcji.
Twierdzenie 3
Dla dowolnych funkcji f, g, h spełnione są następujące warunki:
X g f T
(a) g ż (f ż h) = (g ż f) ż h,
(b) jeżeli f i g są różnowartościowe i istnieje złożenie g ż f, to funkcja g ż f jest
również różnowartościowa,
(c) jeżeli funkcje f : X Y oraz g : Y Z są b3
ekcjami, to złożenie g ż f jest
również b3
ekcjÄ….
9
Dowód (a)
Wynika bezpośrednio z własności łączności składania relacji.
Dowód (b)
Wez
my dowolne funkcje f i g, spełniające warunki f : X Y , g : Z T, f(X) ą" Z.
Istnieje wtedy złożenie funkcji g ż f. Załóżmy ponadto, że funkcje f i g są
różnowartościowe.
Spełnione są zatem poniższe warunki:
(*) " [f(x1) = f(x2) Ò! x1 = x2],
x1,x2"X
(**) " [g(z1) = g(z2) Ò! z1 = z2].
z1,z2"Z
Aby udowodnić różnowartościowość funkcji g ż f, należy wykazać, że:
" [(g ż f)(x1) = (g ż f)(x2) Ò! x1 = x ].
x1,x2"X 2
Wez
my zatem dowolne dwa argumenty ze zbioru X oraz załóżmy, że
(g ż f)(x1) = (g ż f)(x2).
Mamy wtedy:
g(f(x1)) = g(f(x2)).
Zauważmy teraz, że f(x1) oraz f(x2) jako wartości funkcji f należą do zbioru f(X) i przez
to7 do zbioru Z. Wiedząc, że funkcja g jest różnowartościowa na podstawie warunku
(**), otrzymujemy:
f(x1) = f(x2),
Z kolei korzystajÄ…c z warunku (*), mamy:
x1 = x2.
Rozważmy funkcję f : X Y i pewien podzbiór dziedziny A (A ą" X). Funkcję
h : A Y spełniającą warunek " h(x) = f(x) nazywamy reduktem (obcięciem)
x"A
funkcji f do zbioru A i oznaczamy zwyczajowo przez fćłA.
Ilustracja graficzna reduktu funkcji przedstawiona jest na rysunku 6.
Y
Y
Rysunek 6
7
Przypomn3
my warunek konieczny na istnienie złożenia funkcji: f(X) ą" Z.
10
X f T A f T
A
3. Obrazy zbiorów wyznaczane
przez funkcje i ich własności
Rozważmy funkcję f : X Y i pewien podzbiór A dziedziny X (A ą" X). Rozważmy
także redukt fćłA, Obrazem zbioru A przez funkcję f nazywamy zbiór wartości reduktu
fćłA (rysunek 7). Obraz ten oznaczamy przez f(A).
Rysunek 7
Pojęcie obrazu zbioru wyznaczanego przez funkcję może więc być definiowane
następująco.
Niech A będzie podzbiorem dziedziny pewnej funkcji f : X Y (A ą" X). Wtedy:
X f Y
f(A) =df.{y " Y : " y = f(x)},
x"A
lub jeszcze inaczej:A
f(A)
f(A) = df.{f(x) : x " A}.
Uwaga: Jak widać z powyższych definicji, obraz zbioru A wyznaczany przez funkcję f
to zbiór wszystkich wartości funkcji wyznaczanych przez argumenty ze zbioru A.
Przykład 12
Rozważmy funkcję f : R R daną wzorem f(x) = x + 1. Wez
my też dwa różne
podzbiory jej dziedziny A = {1, 5, 7} oraz B = (2, +"). W przypadku zbioru
skończonego łatwo jest wyznaczyć obraz zbioru przez funkcję f(A). Wystarczy
bowiem wyznaczyć po kolei wartości funkcji dla poszczególnych elementów
zbioru. Mamy oczywiście f(A) = {2, 6, 8}. Również drugi przypadek jest nietrudny.
A
atwo zauważyć, że wszystkie i tylko te wartości funkcji dla argumentów ze zbioru
A znajdujÄ… siÄ™ w przedziale (3, +").
W dowodach własności obrazów przydatne okazują się też poniższe zależności,
wynikające bezpośrednio z powyższych definicji:
11
(i) y " f(A) Ô! " y = f(x)8,
x"A
(ii) x " A Ò! f(x) " f(A)9.
Implikacja odwrotna do warunku (ii) zachodzi tylko w szczególnym przypadku:
Twierdzenie 4
Dla dowolnej funkcji f : X Y i dowolnego podzbioru jej dziedziny A (A Ä…" X)
prawdziwa jest następująca równoważność:
f jest różnowartoÅ›ciowa Ô! " [f(x) " f(A) Ò! x " A].
x"A
Wniosek
Jeżeli funkcja f : X Y jest różnowartościowa, to zachodzi następująca
równoważność:
x " A Ô! f(x) " f(A).
Prawdziwe są także następujące własności obrazów zbiorów przez funkcje związane
z działaniami teoriomnogościowymi.
Twierdzenie 5
Dla dowolnej funkcji f : X Y i dowolnych podzbiorów A oraz B jej dziedziny
(A, B ą" X) zachodzą następujące warunki:
(a) f(A *" B) = f(A) *" f(B)10,
(b) f(A )" B) Ä…" f(A) )" f(B)11,
(c) jeżeli funkcja f jest różnowartościowa, to f(A )" B) = f(A) )" f(B).
Dowód (b)
Aby wykazać, że f(A )" B) ą" f(A) )" f(B), należy  zgodnie z definicją inkluzji zbiorów
 udowodnić następujący warunek:
" [y " f(A )" B) Ò! y " f(A) )" f(B)].
y
Wez
my zatem dowolny element y:
1. y " f(A )" B) (założenie dowodu).
2. " y = f(x) (1, warunek (i)).
x"A)"B
3. x0 " A )" B oraz y = f(x0) dla pewnego x0 (2).
4. x0 " A )" B (3).
5. y = f(x0) (3).
6. x0 " A (4).
7. x0 " B (4).
8. f(x0) " f(A) (6, warunek (ii)).
9. f(x0) " f(B) (7, warunek (ii)).
10. f(x0) " f(A) )" f(B) (8, 9).
11. y " f(A) )" f(B) (5, 10).
8
Element y należy do obrazu zbioru A wtw, gdy istnieje argument x " A, dla którego y jest wartością.
9
Jeżeli argument należy do pewnego podzbioru dziedziny, to jego wartość należy do obrazu tego
podzbioru.
10
Warunek ten czytamy: obraz sumy zbiorów jest równy sumie obrazów tych zbiorów.
11
Obraz iloczynu zbiorów jest zawarty w iloczynie obrazów tych zbiorów.
12
Dowód (c)
Aby wykazać, że z założenia różnowartościowości funkcji wynika równość
f(A )" B) = f(A) )" f(B), należy  zgodnie z definicją równości zbiorów  przy
odpowiednim założeniu, udowodnić następujący warunek:
" [y " f(A )" B) Ô! y " f(A) )" f(B)].
y
Załóżmy więc, że funkcja f jest różnowartościowa i wez
my dowolny element y.
Implikacja w prawo została wcześniej udowodniona w ogólnym przypadku, zostaje
zatem do udowodnienia implikacja w lewo. Mamy:
1. y " f(A) )" f(B) (założenie dowodu).
2. y " f(A) oraz y " f(B) (1).
3. y " f(A) (2).
4. y " f(B) (2).
5. " y = f(x) (3, warunek (i)).
x"A
6. " y = f(x) (4, warunek (i)).
x"B
7. x1 " A oraz y = f(x1) dla pewnego x1 (5).
8. x2 " B oraz y = f(x2) dla pewnego x2 (6).12
9. x1 " A (7).
10. y = f(x1) (7).
11. x2 " B (8).
12. y = f(x2) (8).
13. f(x1) = f(x2) (10, 12).
14. x1 = x2 (13, różnowartościowość funkcji f).
15. x1 " B (11, 14).
16. x1 " A )" B (9, 15).
17. f(x1) " f(A )" B) (16, warunek (ii)).
18. y " f(A )" B) (10, 17).
12
Zauważmy, że nie musi to być ten sam element x.
13
4. Przeciwobrazy zbiorów
wyznaczone przez funkcje
i ich własności
Rozważmy funkcję f : X Y i pewien zbiór S (S ą" Y). Przeciwobrazem zbioru S przez
funkcję f nazywamy zbiór wszystkich tych argumentów należących do dziedziny,
których wartości należą do zbioru S (rysunek 8). Przeciwobraz ten oznaczamy przez
f 1(S).
Rysunek 8
Pojęcie przeciwobrazu zbioru przez funkcję może być definiowane następująco:
Niech f : X Y będzie dowolną funkcją oraz niech S będzie podzbiorem zbioru
Y (S Ä…" Y).
X f Y
Wtedy:
f 1(S) S
f 1(S) =df {x " X : " y = f(x)}
y"S
lub inaczej:
f 1(S) =df {x " X : f(x) " S}.
Uwaga: Jak widać z powyższych definicji, przeciwobraz zbioru S wyznaczony przez
funkcję f to zbiór tych wszystkich argumentów, których wartość należy do zbioru S.
Rozważmy funkcję f : R R daną wzorem f(x) = 2x + 1. Wez
my też dwa różne
podzbiory zbioru liczb rzeczywistych S = {3, 5, 7} oraz Z = (3, +").
W pierwszym przypadku nietrudno obliczyć, że wartości ze zbioru S odpowiadają
kolejno argumentom 1, 2, 3. W drugim przypadku interesuje nas, które argumenty
dają wartości większe od 3. Możemy zatem zapisać poniższą nierówność:
f(x) > 3,
14
czyli:
2x + 1 > 3.
Oczywiście zbiorem rozwiązań tej nierówności jest przedział (1, +").
Mamy zatem:
f 1(S) = f 1(3, +") = (1, +").
Także w przypadku przeciwobrazów można zapisać  wynikające wprost z definicji
 przydatne w dowodach własności:
(iii) x " f  1(S) Ô! " y = f(x)13,
y"S
(iv) x " f  1(S) Ô! f(x) " S14.
Prawdziwe są następujące własności przeciwobrazów zbiorów.
Twierdzenie 6
Dla dowolnej funkcji f : X Y i dowolnych podzbiorów jej przeciwdziedziny S oraz
Z (S, Z ą" Y) zachodzą następujące warunki:
(a) f 1(S *" Z) = f 1(S) *" f 1(Z)15,
(b) f 1(S )" Z) = f 1(S) )" f 1(Z)16.
Interesujące są własności mieszane obrazów i przeciwobrazów zbiorów. Mamy bowiem
dla dowolnej funkcji f i odpowiednich zbiorów A i S następujące własności:
Twierdzenie 7
(a) A Ä…" f 1(f(A))17,
(b) f(f 1(S)) Ä…" S18.
Inkluzje odwrotne są prawdziwe tylko w szczególnych przypadkach:
Twierdzenie 8
Funkcja f jest różnowartościowa wtedy i tylko wtedy, gdy dla dowolnego podzbioru
jej dziedziny A spełniona jest równość A = f  1(f(A)).
Twierdzenie 9
Funkcja f jest surjekcjÄ… wtedy i tylko wtedy, gdy dla dowolnego podzbioru jej
przeciwdziedziny S spełniona jest równość f (f  1(S)) = S.
13
Argument x należy do przeciwobrazu zbioru S wtw, gdy istnieje element y " S, będący
wartością dla x.
14
Argument x należy do przeciwobrazu zbioru S wtw, gdy jego wartość należy do S.
15
Przeciwobraz sumy zbiorów jest równy sumie przeciwobrazów tych zbiorów.
16
Przeciwobraz iloczynu zbiorów jest równy iloczynowi przeciwobrazów tych zbiorów.
Zwróćmy uwagę, że tutaj zachodzi równość w ogólnym przypadku, dla dowolnych
funkcji.
17
Dowolny zbiór jest zawarty w przeciwobrazie swojego obrazu.
18
Obraz przeciwobrazu danego zbioru jest zawarty w tym zbiorze.
15
5. Elementy teorii mocy.
Zbiory przeliczalne i nieprzeliczalne
oraz ich własności
W temacie tym omówimy podstawowe pojęcia teorii mocy: relację równoliczności,
pojęcie zbioru przeliczalnego i nieprzeliczalnego i ich elementarne własności. Na
koniec podamy  wraz ze szkicem dowodu  twierdzenie Cantora, z którego
wynika, że istnieje nieskończenie wiele rodzajów nieskończoności.
Problem ustalania liczności (liczby elementów) zbioru frapował filozofów
i matematyków od dawna. Dla zbiorów skończonych nie jest to trudne, wystarczy
bowiem policzyć elementy. Gorzej jest z ustalaniem liczności zbiorów nieskończonych.
Jeżeli będziemy zastanawiać się nad licznością zbioru liczb naturalnych oraz nad
licznością zbioru liczb naturalnych parzystych, można rozumować co najmniej na
dwa sposoby. Pierwszy mówi, że oba zbiory są nieskończone, zatem mają tę samą
liczność. Można jednak również stwierdzić, że liczb naturalnych parzystych jest dwa
razy mniej niż wszystkich liczb naturalnych. Liczności tych zbiorów nie mogą być
zatem takie same. Okazuje się, że oba te uzasadnienia nie są poprawne.
Podstawowym pojęciem teorii mocy jest relacja równoliczności. Ustala ona, które
ze zbiorów będziemy nazywali równolicznymi (o tej samej liczności, mocy). Intuicja
definicji tej relacji jest bardzo prosta. Jeżeli zastanowimy się, w jaki sposób człowiek
z epoki żelaza (a więc nieumiejący liczyć) mógł stwierdzić, czy ma tyle samo
palców u obu dłoni, szybko dojdziemy do wniosku, że wystarczyło, aby połączył
odpowiednie palce obu dłoni i w ten sposób pokazał, że jest ich tyle samo. Zauważmy,
że połączenie takie to swoiste przyporządkowanie, a zatem funkcja. Zauważmy też,
że jest to przyporządkowanie wzajemnie jednoznaczne, a zatem b3
ekcja. Naturalna
wydaje się być zatem podana poniżej definicja relacji równoliczności.
Powiemy, że dwa zbiory są równoliczne (relację równoliczności oznaczamy symbolem
 ~ ), jeżeli istnieje między nimi odwzorowanie wzajemnie jednoznaczne (b3
ekcja).
Symbolicznie:
A ~ B Ô!df. "f [ (f : A B) '" f jest b3
ekcjÄ…]
Ilustracja graficzna przedstawiona jest na rysunku 9.
Rysunek 9
16
A B
Korzystając z własności b3
ekcji, łatwo uzasadnić następujące własności relacji
równoliczności:
Twierdzenie 10
Dla dowolnych zbiorów A, B, C prawdziwe są następujące warunki:
(a) A ~ A  każdy zbiór jest równoliczny ze samym sobą (zwrotność),
(b) A ~ B Ò! B ~ A  jeżeli zbiór A jest równoliczny ze zbiorem B, to zbiór B jest
także równoliczny ze zbiorem A (symetria),
(c) (A ~ B '" B ~ C) Ò! A ~ C (przechodniość).
Dowód (a)
Równoliczność dowolnego zbioru A ze sobą ustala funkcja tożsamościowa (b3
ekcja)
f : A A, " f(x) = x.
x"A
Dowód (b)
Załóżmy, że A ~ B  wtedy istnieje b3
ekcja f :A B, równoliczność B ~ A ustala
funkcja odwrotna do f, f  1 : B A (przypomn3
my, że funkcja odwrotna do b3
ekcji
jest również b3
ekcjÄ…).
Dowód (c) (szkic)
Równoliczność zbiorów A i C ustala złożenie odpowiednich funkcji ustalających
równoliczność A ~ B oraz B ~ C.
Przykład 13
Poniżej przedstawiamy przykłady zbiorów równolicznych wraz z funkcjami
wzajemnie jednoznacznymi, ustalającymi te równoliczności:
(a) zachodzi równoliczność N ~ Par (zbiór liczb naturalnych jest równoliczny ze
zbiorem liczb naturalnych parzystych). Istnieje bowiem b3
ekcja f : N Par
dana wzorem f(n) = 2n;
(b) zachodzi równoliczność N ~ NPar (zbiór liczb naturalnych jest równoliczny
ze zbiorem liczb naturalnych nieparzystych). Istnieje bowiem b3
ekcja
f : N NPar dana wzorem f(n) = 2n + 1;
(c) zachodzi równoliczność N ~ {100, 101, 102, 103, ...} (zbiór liczb naturalnych
jest równoliczny ze zbiorem kolejnych naturalnych potęg liczby 10). Istnieje
bowiem b3
ekcja f : N {100, 101, 102, 103, ...} dana wzorem f(n) = 10n;
(d) zachodzi równoliczność R ~ R+ (zbiór liczb rzeczywistych jest równoliczny ze
zbiorem liczb rzeczywistych dodatnich). Istnieje bowiem b3
ekcja f : R R+
dana wzorem f(x) = ex;
(e) zachodzi równoliczność (0, Ą) ~ R (liczb rzeczywistych z przedziału (0, Ą)
jest tyle samo, co wszystkich liczb rzeczywistych). Istnieje bowiem b3
ekcja
f : (0, Ä„) R dana wzorem f(x) = ctg(x).
Zachodzi również następujące twierdzenie, dotyczące równoliczności iloczynów
kartezjańskich i zbiorów potęgowych:
17
Twierdzenie 11
Dla dowolnych zbiorów A, B, C, D jest:
(a) (A ~ B '" C ~ D) Ò! (A × C) ~ (B × D),
(b) A ~ B Ò! P(A) ~ P(B).
Dowód (a) (szkic)
Niech f i g będą b3
ekcjami takimi, że f : A B oraz g : C D.
Zdefiniujmy nowÄ… funkcjÄ™ h : A × C B × D, w sposób nastÄ™pujÄ…cy:
" " [h(x, y) = (f(x), g(y)].
x"A y"C
Tak określona funkcja h jest również b3
ekcją, zatem funkcja ustala równoliczność
zbioru A × C ze zbiorem B × D.
Zbiór nazywamy przeliczalnym, jeżeli jest skończony lub równoliczny ze zbiorem
liczb naturalnych.
Uwaga: A
atwo z powyższej definicji wywnioskować fakt, że nieskończony zbiór jest
przeliczalny wtw, gdy jest równoliczny ze zbiorem liczb naturalnych.
Przykład 14
Zbiorami przeliczalnymi sÄ…:
(a) " (jako zbiór skończony),
(b) {a, b, c, d} (jako zbiór skończony),
(c) N (jest bowiem równoliczny z samym sobą),
(d) Par (jest równoliczny z N),
(e) NPar (jest równoliczny z N).
Okaże się poniżej, że wiele innych zbiorów również jest przeliczalnych. Do
dowodzenia tych własności bardzo użyteczne są dwa następujące twierdzenia:
Twierdzenie 12
Niepusty zbiór A jest zbiorem przeliczalnym wtw, gdy jego wszystkie elementy dają
się ustawić w ciąg różnowartościowy19.
Dowód
Ò!
Niech A będzie niepustym zbiorem przeliczalnym. Zachodzą dwa poniższe
przypadki:
(i) A jest zbiorem skończonym (A = {a1, a2, a3, a4, ..., a }). Tworzymy wtedy ciąg:
n
(a1, a2, a3, a4, ..., a )  jest to różnowartościowy ciąg wszystkich elementów
n
zbioru A.
(ii) A jest zbiorem nieskończonym, zatem jako nieskończony zbiór przeliczalny jest
równoliczny z N. Istnieje b3
ekcja f : N A. Wtedy odpowiedni ciąg wartości
funkcji (f(0), f(1), f(2), f(3), ...) jest różnowartościowym20 ciągiem wszystkich21
elementów zbioru A.
19
W rozważaniach dopuszczamy pojęcie ciągu o skończonej liczbie elementów.
20
Korzystamy z własności różnowartościowości funkcji f.
21
Własność  na funkcji f.
18
Ð!
Niech A będzie zbiorem, gdzie (a0, a1, a2, a3, ...) jest różnowartościowym ciągiem
jego wszystkich elementów. Zachodzą dwa przypadki:
(i) ciąg jest skończony, zatem zbiór jest skończony, czyli przeliczalny;
(ii) ciąg jest nieskończony. Wtedy budujemy funkcję f : N A w sposób
następujący:
Niech f(0) = a0, f(1) = a1, f(2) = a2, ...
Tak określona funkcja f jest różnowartościowa (różnowartościowość ciągu) oraz  na ,
zatem A jest równoliczny ze zbiorem liczb naturalnych N, czyli A jest przeliczalny.
Twierdzenie 13
Niepusty zbiór A jest zbiorem przeliczalnym wtw, gdy jego wszystkie elementy
można ustawić w ciąg22.
Dowód (szkic)
Ò!
Oczywiste na podstawie poprzedniego twierdzenia.
Ð!
Jeżeli ciąg nie jest różnowartościowy, to można z niego wybrać jego różnowartościowy
podciąg wszystkich elementów zbioru A.
Korzystając z ostatniego twierdzenia, można udowodnić ciekawą własność zbioru
liczb całkowitych.
Twierdzenie 14
Zbiór liczb całkowitych Z jest równoliczny ze zbiorem liczb naturalnych N.
Dowód
Wystarczy zauważyć, że wszystkie elementy zbioru liczb całkowitych można ustawić
w ciąg, mamy bowiem Z = {0, 1,  1, 2,  2, 3,  3, ...}. Zatem zbiór Z jest przeliczalny.
Skoro jest również nieskończony, musi być równoliczny ze zbiorem liczb naturalnych.
Możemy więc zapisać: Z ~ N.
Za pomocą powyższych twierdzeń można już udowodnić inne interesujące własności
zbiorów przeliczalnych.
Twierdzenie 15
Niech A, B będą dowolnymi zbiorami przeliczalnymi, zachodzą wtedy następujące własności:
(a) jeżeli C ą" A, to zbiór C jest przeliczalny (podzbiór zbioru przeliczalnego jest
przeliczalny),
(b) iloczyn A )" B zbiorów przeliczalnych jest zbiorem przeliczalnym,
(c) suma A *" B zbiorów przeliczalnych jest zbiorem przeliczalnym,
(d) iloczyn kartezjaÅ„ski A × B dwóch zbiorów przeliczalnych jest zbiorem
przeliczalnym,
22
Różnica  w porównaniu z poprzednim twierdzeniem  jest taka, że teraz ciąg nie musi
być różnowartościowy, może być dowolny.
19
(e) jeżeli f jest funkcją taką, że A jest jej dziedziną, to f(A) (funkcyjny obraz zbioru
przeliczalnego) jest przeliczalny.
Dowód (a)
Jeżeli A jest zbiorem pustym, to dowód oczywisty. Jeżeli A nie jest zbiorem pustym, to
elementy A da się ustawić w ciąg. Dowolny podciąg tego ciągu wyznacza przeliczalny
podzbiór zbioru A.
Dowód (b)
Wystarczy zauważyć, że A )" B ą" A (iloczyn jest podzbiorem każdego z czynników
tego iloczynu).
Dowód (c)
Niech A i B będą zbiorami przeliczalnymi. Niech też A = {a0, a1, a2, a3, ...} oraz
B = {b0, b1, b2, b3, ... }. Wtedy sumę można przedstawić jako:
A *" B = {a0, b0, a1, b1, a2, b2, ...}, czyli A *" B jest zbiorem przeliczalnym (elementy
sumy można ustawić w ciąg).
Dowód (d)
Niech A i B będą zbiorami przeliczalnymi. Niech też A = {a0, a1, a2, a3, ...} oraz
B = {b0, b1, b2, b3, ... }. Wtedy iloczyn kartezjaÅ„ski A × B można przedstawić w postaci
nieskończonej tablicy:
Elementy zbioru A × B można wiÄ™c ustawić w ciÄ…g {(a0, b0), (a1, b0), (a0, b1), (a2, b0), ....}
(sposób doboru elementów wskazany strzałkami).
{(a ,b ), (a ,b ), (a ,b ) ............................................
0 0 0 1 0 2
Twierdzenie 16
(a ,b ), (a ,b ), (a ,b ) ............................................
1 0 1 1 1 2
Zbiór liczb wymiernych Q jest równoliczny ze zbiorem liczb naturalnych.
(a ,b ), (a ,b ), (a ,b ) ............................................
2 0 2 1 2 2
(a ,b ), (a ,b ), (a ,b ) ............................................
3 0 3 1 3 2
Dowód (szkic)
..................................................................................}
Rozważmy funkcjÄ™ f : Z × N+ Q, danÄ… wzorem " " [f(x, y) = ]. Tak
x"Z y"N+
zdefiniowana funkcja jest surjekcją (choć nie jest różnowartościowa). Zatem jej
przeciwdziedzina Q jest obrazem dziedziny Z × N+ (zbiorem wartoÅ›ci), która to
dziedzina na mocy poprzednich twierdzeń jest zbiorem przeliczalnym. Zbiór Q dał się
20
więc przedstawić jako funkcyjny obraz zbioru przeliczalnego, zatem Q jest zbiorem
przeliczalnym. Skoro jest również nieskończony, jest równoliczny ze zbiorem liczb
naturalnych.
Pokazaliśmy wyżej, że zbiory liczb całkowitych i wymiernych są równoliczne
ze zbiorem liczb naturalnych. Nie wszystkie jednak zbiory nieskończone mają tę
własność. Aby to wykazać, uzasadnimy najpierw następujące twierdzenie.
Twierdzenie 17
Przedział (0, 1) jest równoliczny z R (zbiorem liczb rzeczywistych).
Dowód (szkic)
Wystarczy zauważyć, że przedział (0, 1) jest równoliczny z przedziałem (0, Ą).
Równoliczność wyznacza tu redukt fćł(0,1) funkcji f : R R, danej wzorem "
x"R
[f(x) = Ąx]. Teraz  jeżeli wiemy również, że przedział (0, Ą) jest równoliczny z R
(funkcja ctg)  na mocy przechodniości mamy (0, 1) <" R.
Twierdzenie 18
Przedział (0, 1) nie jest równoliczny z N (nie jest przeliczalny).
Dowód
Załóżmy nie wprost, że przedział (0, 1) jest równoliczny z N. Gdyby tak było, wtedy
wszystkie elementy tego przedziału dałoby się ustawić w ciąg23:
x = 0, a a a a ......
1 11 12 13 14
x = 0, a a a a ......
2 21 22 23 24
x = 0, a a a a ......
3 31 32 33 34
x = 0, a a a a ......
4 41 42 43 44
................................... , gdzie a " {0, 1, 2, ..., 9}.
3

Niech y = 0, b1b2b3b4...... będzie liczbą taką, że bj `" ajj (liczba y różni się od wszystkich
liczb z powyższego ciągu).
Oczywiście, y " (0, 1), ale nie ma jej w ciągu  wszystkich liczb z tego przedziału.
Otrzymujemy sprzeczność.
Twierdzenie 19
Zbiór liczb rzeczywistych R nie jest równoliczny ze zbiorem liczb naturalnych.
23
Zapis x1 = 0,a11a12a13a14...... reprezentuje dowolną liczbę rzeczywistą z przedziału (0,
1), np. liczbÄ™ 0,1252286.... .
21
Dowód
Wystarczy skorzystać z wcześniejszego twierdzenia, które mówi, że (0, 1) ~ R. Gdyby
było także R ~ N, mielibyśmy (0, 1) ~ N z przechodniości relacji równoliczności,
a tak nie jest. Otrzymujemy sprzeczność.
Twierdzenie 20
Żaden zbiór A nie jest równoliczny ze swoim zbiorem potęgowym P(A).
Dowód
Załóżmy nie wprost, że dla pewnego A jest A ~ P(A). Wtedy istniałaby b3
ekcja f
taka, że f : A P(A). Zauważmy, że dla każdego x " A jest f(x) " P(A) (f(x) ą" A).
Oznaczmy przez Z = {x " A : x " f(x)}. Zauważmy, że Z ą" A, czyli Z " P(A).
Ponieważ funkcja f jest  na , musiałby istnieć element x0 o własności: f(x0) = Z.
Możliwe są dwa następujące przypadki:
(i) x0 " Z, ale wtedy x0 " f(x0), czyli x0 " Z, otrzymujemy sprzeczność.
(ii) x0 " Z, ale wtedy x0 " f(x0), czyli x0 " Z, również otrzymujemy sprzeczność.
W każdym przypadku mamy sprzeczność.
Wniosek
Istnieje nieskończenie wiele rodzajów nieskończoności.
22
Bibliografia
1. Gubareni N., 2001: Logika dla studentów, Wydawnictwo Politechniki
Częstochowskiej.
2. Kuratowski K., 2004: Wstęp do teorii mnogości i topologii, PWN, Warszawa.
3. Kuratowski K., Mostowski A., 1978: Teoria mnogości, PWN, Warszawa.
4. Marek W., Onyszkiewicz J., 2003: Elementy logiki i teorii mnogości
w zadaniach, PWN, Warszawa.
5. Rasiowa H., 2004: Wstęp do matematyki współczesnej, PWN, Warszawa.
6. Słupecki J., Hałkowska K., Piróg-Rzepecka K., 1994: Logika i teoria mnogości,
Warszawa.
Bibliografia stron WWW
7. Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego.
Witryna internetowa. hżÿp://www.mimuw.edu.pl/~tiuryn/skrypt-98.ps.gz, stan
z 21.09.2005 (J. Tiuryn, Wstęp do teorii mnogości i logiki).
23