Wykład dziesiąty

Temat XI

Teoria mnogości

Teoria liczb kardynalnych

Przez `zbiór' rozumiemy każde zebranie w jedną całość M określonych, dobrze odróżnionych przedmiotów m naszej naoczności albo naszego myślenia (które są nazywane `elementarni'[zbioru] M).

Każdemu zbiorowi przysługuje pewna określona `moc', którą nazywamy też `liczbą kardynalną' . `Mocą' albo `liczbą kardynalną' [zbioru] M nazywamy pojęcie ogólne, które z pomocą naszej aktywnej zdolności myślenia bierze swój początek ze zbioru M w ten sposób, że abstrahuje się od własności jego różnych elementów m i od porządku, w jakim są dane. Wynik tego podwójnego aktu abstrakcji,liczbę kardynalną albo moc [zbioru] M, oznaczamy przez
.

Dwa zbiory M i N nazywamy równolicznymi i oznaczamy to jako M ~ N lub: N ~ M, jeśli można między tymi zbiorami ustanowić taką relację, że każdemu elementowi jednego z nich odpowiada jeden i tylko jeden element drugiego. [G. Cantor (1932, ss. 282 - 283)].

Zasada abstrakcji -zastosowanie do teorii mnogości

Zastosowanie zasady abstrakcji w teorii mnogości prowadzi do bardzo „płod­nych” konstrukcji. Jedną z konstrukcji sugerowanych przez tę zasadę jest rozsze­rzenie „skończonej intuicji” posiadania przez zbiory tej samej ilości elementów na zbiory nieskończone i określenie liczby kardynalnej zbioru jako jego charakterystyki „ilościowej”.

G. Malinowski Logika ogólna, s. 174

Pojęcie równoliczności

Następnie wprowadzamy pojęcie równoliczności. Równoliczne są dwa zbiory, gdy mają tę samą ilość elementów. Ponieważ jednak celem rozważań jest określenie pojęcia ilości, przeto równoliczność mu­simy zdefiniować inaczej, w sposób bardziej bezpośredni. Oprzemy się o następujące intuicje. Zbiór palców ręki lewej jest równoliczny ze zbiorem palców ręki prawej, ponieważ można tak zetknąć dwie ręce, że każdy palec ręki lewej będzie się stykał z jednym i tylko jednym palcem ręki prawej. Zetknięcie to wyznacza wzajemnie jednoznaczne przyporządkowanie między elementami obu zbiorów.

Zgodnie z tą definicją postępują np. dwaj chłopcy, którzy chcąc się po­dzielić sprawiedliwie pewną ilością kasztanów; bez rachowania, siadają po dwóch stronach zbioru przeznaczonego do podziału i równocześnie biorą po jednym kasztanie. Jeden kładzie swój kasztan na swoją stronę, drugi kładzie swój na swoją, po czym znów równocześnie sięgają po na­stępną parę. Jeśli postępując w ten sposób wyczerpią wszystkie kasztany, wówczas mają pewność, że każdy z nich ma tyle samo, co drugi. Odwzorowanie wzajemnie jednoznaczne stanowi tu funkcja przyporządkowująca kasztanowi odłożonemu przez jednego chłopca kasztan równo­cześnie odłożony przez drugiego chłopca. Przy tym sposobie dzielenia obywamy się bez pomocy pojęcia liczby.

Grzegorczyk Zarys logiki matematycznej, ss. 7 - 27

Zbiory równoliczne

Definicja: Dwa zbiory A i B nazywamy równolicznymi, jeżeli istnieje różnowartościowe przekształcenie (odwzorowanie) zbioru A na zbiór B.

Między zbiorami A i B zachodzi relacja równoliczności (A ~ B) gdy są one równoliczne.

Relacja równoliczności jest relacją równoważności, tzn. jest zwrotna, symetryczna i przechodnia:

1) A ~ A

2) jeżeli A ~ B, to B ~ A

3) jeżeli A ~ B i B ~ C, to A ~ C.

Zbiory skończone i nieskończone

Definicje

Zbiór A jest zbiorem skończonym, jeśli liczba jego elementów jest skończona.

Przeliczaniem zbioru nazywamy takie jego uporządkowanie, dzięki któremu wszystkie jego elementy można ustawić w ciąg ({a_i}, i = 1, 2 …) w taki sposób, że każdy z elementów pojawia się w nim tylko jeden raz.

Zbiorem przeliczalnym jest zbiór, który da się przeliczyć.

Zbiór N (= {1, 2, 3 … }) wszystkich liczb naturalnych jest zbiorem przeliczalnym; przy czym elementy tego ciągu można ułożyć według ich wielkości: 1 < 2 < 3 …

Ponadto, zbiór N jest zbiorem nieskończonym przeliczalnym.

Zbiór W wszystkich liczb wymiernych (m/n) jest zbiorem przeliczalnym, tzn. istnieje ciąg {a_i}, i = 1, 2 → ∞; który składa się ze wszystkich liczb wymiernych. Przy czym, mimo, że zbiór liczb wymiernych jest przeliczalny, to nie da się ułożyć w ciąg (rosnący) według ich wielkości. Pomiędzy dwiema danymi liczbami wymiernymi istnieje jeszcze nieskończenie wiele liczb wymiernych i dlatego dla danej liczby wymiernej nie ma liczby wymiernej bezpośrednio od niej większej.

Definicja. Zbiór A nazywamy zbiorem nieskończonym przeliczalnym, jeśli jest on równej mocy (równoliczny) ze zbiorem wszystkich liczb naturalnych (N).

„I całe jest większe od części” ( piąty aksjomat, tzw. myśli wspólne koinai ennoiai w Elementach Euklidesa).

Twierdzenie (paradoks Galileusza)

Jeśli A jest zbiorem nieskończonym przeliczalnym, to jest on równej mocy (równoliczny) ze swoim podzbiorem właściwym.

Dowód:

Istnieje taki ciąg {a_i}_, i = 1, 2 → ∞, że A = {a₁, a₂, a₃, … }, z zał. Wówczas wystarczy podać następującą funkcję różnowartościową f: A
B; gdzie B = {a₂, a₃, … }:

f (a_i) = a _i+1, zachodzi przy tym B
A.

Twierdzenie Dedekinda-Peirce'a

Zbiór A jest zbiorem nieskończonym przeliczalnym wtedy i tylko wtedy, gdy jest on równej mocy (równoliczny) ze swoim podzbiorem właściwym.

Przykład.

Dla N = {1, 2, 3 … } - zbioru wszystkich liczb naturalnych i M = {2, 4, 6, … } - zbioru wszystkich liczb parzystych odwzorowaniem różnowartościowym jest f (n) = 2n,

F: N
M; przy tym M
N.

Odwzorowanie ustalające równoliczność:

1, 2, 3, 4 , …

2, 4, 6, 8, …

Liczby kardynalne

Oznaczenia:

a, b, c, … k, m, n … - liczby kardynalne

a - moc zbioru liczb naturalnych (N)

c - moc („continuum”) zbioru liczb rzeczywistych (R)

Inne notacje:

|A| - liczba kardynalna (moc) zbioru A

₀א - moc zbioru liczb naturalnych, czyt. alef zero

₁א - moc liczb rzeczywistych, czyt. alef jeden

Nc (numerus cardinalis) - zbiór liczb kardynalnych

Definicja: Liczbą kardynalną (mocą) zbioru A nazywamy jego liczebność rozumianą tak, że dwa różne zbiory mają tę samą liczbę kardynalną wtedy i tylko wtedy, gdy są równoliczne.

Liczby kardynalne są klasami abstrakcji relacji równoliczności zbiorów.

Liczbą kardynalną zbioru skończonego jest liczba (skończona) jego elementów.

Relacje i działania na liczbach kardynalnych

Między liczbami kardynalnymi zachodzą relacje:

≤

<

Dla liczb kardynalnych określa się także działania: dodawania +, mnożenia ·

i potęgowania.

Relacje między liczbami kardynalnymi

Relację równości dwóch liczb kardynalnych m i n jest określona przez równoliczność zbiorów:

m = n ≡ A ~ B,

gdzie m = moc A, n = moc B

Definicja: Dwie liczby kardynalne są równe wtedy i tylko wtedy, gdy są mocami zbiorów równolicznych.

Dla zbiorów skończonych pojęcie równej mocy pokrywa się z pojęciem jednakowej ilości elementów.

Zachodzą następujące zależności:

|N| = |C|

|C| = |W|

|N| = |W|

< 0, 1 > - odcinek otwarty 0, 1

[0, 1] - odcinek domknięty 0, 1

< 0, 1 >
R

Zachodzi także:

|< 0, 1 >| = |[0, 1]| = ||R| = c

Prosta (continuum liczbowe) jest takiej samej mocy jak odcinek prostej: < 0, 1 > .

Definicja

Dwie liczby kardynalne są różne (nie są równe) wtedy i tylko wtedy, gdy nie są mocami zbiorów równolicznych.

m ≠ n ≡ ∼ (A ~ B)

gdzie m = moc A, n = moc B

Relację nierówności (różności) dwóch liczb kardynalnych m i n otrzymujemy przez zanegowanie relacji ich równości.

Relacja słabej nierówności dwóch liczb kardynalnych m i n jest określona następująco:

Definicja

Liczba kardynalna m jest mniejsza lub równa liczbie kardynalnej n wtedy i tylko wtedy, gdy m jest mocą zbioru równolicznego z pewnym podzbiorem zbioru o mocy n.

Inaczej, moc m zbioru A jest mniejsza lub równa mocy n zbioru B tylko wtedy, gdy zbiór A jest równoliczny z pewnym podzbiorem C zbioru B:

m ≤ n ≡ ∃_C (C ⊂ B ∧ A ~ C)

gdzie m = moc A, n = moc B

Przykład.

Liczba kardynalna zbioru A = {a, b, c} - 3

Liczba kardynalna zbioru B = {a, b, c, d, e} - 5

Zachodzi relacja słabej nierówności między liczbami kardynalnymi zbiorów A i B: 3 ≤ 5, gdyż zbiór 3-elementowy jest równoliczny z pewnym podzbiorem właściwym zbioru

5-elementowego, np. z podzbiorem C = {b, c, d}.

Relacja ostrej nierówności dwóch liczb kardynalnych m i n; m < n jest określona następująco:

Definicja. Moc m zbioru A jest mniejsza od mocy n zbioru B wtedy i tylko wtedy, gdy zbiór A jest równoliczny z pewnym podzbiorem zbioru B, ale zbiór B nie jest równoliczny z żadnym podzbiorem zbioru A.

Definicja ta oznacza, że moc m zbioru A jest mniejsza od mocy n zbioru B wtedy i tylko wtedy, gdy zbiór A jest równoliczny z pewnym podzbiorem zbioru B i gdy zbiory A oraz B nie są równoliczne.

Przykład.

Liczba kardynalna 3 jest mniejsza od liczby kardynalnej 5, gdyż zbiór 3-elementowy jest równoliczny z pewnym podzbiorem zbioru 5-elementowego, ale oba zbiory nie są równoliczne.

Moc dowolnego zbioru skończonego (n) jest mniejsza od mocy zbioru wszystkich liczb naturalnych (a): n < a.

Twierdzenie (Cantora)

Zbiór wszystkich liczb rzeczywistych (R) jest nieprzeliczalny.

Dowód niewprost (metodą przekątniową)

Załóżmy, że tak nie jest, tzn. że zbiór R da się przeliczyć. Da się zatem wszystkie liczby rzeczywiste ustawić w ciągu: x₁, x₂, x₃ …

Ciąg ten można przedstawić w postaci następującej tablicy kwadratowej:

x₁ = N₁ a₁a₂ a₃a₄ …

x₂ = N₂ b₁b₂ b₃b₄ …

x₃ = N₃ c₁c₂ c₃ c₄ …

x₄ = N₄ d₁d₂ d₃d₄ …

……………………..

Poszczególne wiersze są zapisem kolejnych wyrazów ciągu: x₁, x₂, x₃ … pod postacią liczb i ułamków dziesiętnych; N oznacza część całkowita danej liczby, a małe litery a, b, c - cyfry po przecinku .

Utwórzmy teraz z cyfr położonych na przekątnej tej tablicy (taka metoda nazywa się przekątniową), liczbę rzeczywistą b w następujący sposób:

b = 0 a b c d …, gdzie:

a ≠ a₁

b ≠ b₂

c ≠ c₃

d ≠ d₄

Dla uniknięcia dwuznaczności dobieramy a, b, c, d różne od 0 i 1.

Liczba b jest różna od każdej z liczb ciągu x₁, x₂, x₃ … ; od x₁ różni się pierwszą cyfra po przecinku, od x₂ drugą cyfra po przecinku itd.

Ciąg x₁, x₂, x₃ … nie jest więc przeliczalny, co kończy dowód.

Wniosek z twierdzenia Cantora: a ≠ c, wobec przeliczalności N.

Twierdzenie

Moc zbioru wszystkich liczb naturalnych (a) jest mniejsza od mocy zbioru liczb rzeczywistych (c): a < c

Zbiór liczb rzeczywistych R przedstawia inny, „wyższy” rodzaj nieskończoności od zbioru

liczb naturalnych N oraz od zbioru liczb wymiernych W. Oznacza to, że istnieją przynajmniej dwa różne typy nieskończoności:

- przeliczalna nieskończoność liczb naturalnych (a), oraz

- nieprzeliczalna nieskończoność continuum (c)

Porównywalność liczb kardynalnych

Twierdzenie (wzór) Cantora-Bernsteina

Dla dowolnych m oraz n; jeśli m ≤ n i m ≤ n, i to m = n.

Twierdzenie (prawo trychotomii dla liczb kardynalnych)

∀ m, n ∈ Nc: (m < n) ∨ (m = n) ∨ (n < m)

Prawo trychotomii oznacza porównywalność dowolnych dla liczb kardynalnych.

Dowód tego twierdzenia przeprowadza się w oparciu o aksjomat wyboru. Aksjomat wyboru wyklucza możliwość (która w teorii mnogości nie jest pustą możliwością), że zbiór A nie jest równoliczny a żadnym podzbiorem zbioru B, a zarazem zbiór B nie jest równoliczny a żadnym podzbiorem zbioru A.

Działania na liczbach kardynalnych (materiał nadobowiązkowy)

Definicja dodawania liczb kardynalnych opiera się na pojęciu mocy sumy dwóch zbiorów rozłącznych:

k = m + n, gdzie

m - liczba kardynalna (moc) zbioru A

n - moc zbioru B

k - moc zbioru A ∪ B, przy czym A i B rozłączne

Prawa dodawania liczb kardynalnych

n + a = a

a + a = a

Definicja mnożenia liczb kardynalnych opiera się na pojęciu mocy iloczynu kartezjańskiego

dwóch zbiorów:

k = m · n, gdzie

m - liczba kardynalna (moc) zbioru A

n - moc zbioru B

k - moc zbioru A x B

Prawa mnożenia liczb kardynalnych

n · a = a

a · a = a

Definicja potęgowania liczb kardynalnych opiera się na pojęciu funkcji (odwzorowania) dwóch zbiorów A i B.

Oznaczenia:

A, B -zbiory

m - moc zbioru A

n - moc zbioru B

B^A - zbiór wszystkich funkcji f:A → B, tj. takich, których argumenty przebiegają zbiór A, a wartości należą do zbioru B

n^m - moc zbioru B^A, tj. zbiory wszystkich funkcji, których argumenty przebiegają zbiór A, a wartości należą do zbioru B.

Definicja (potęgowania liczb kardynalnych)

Moc zbioru B podniesiona do potęgi równej mocy zbioru A (n^m) jest to moc k zbioru B^A, tj. moc zbioru wszystkich odwzorowań zbioru A w B, tj. wszystkich funkcji, których argumenty przebiegają zbiór A, a wartości należą do zbioru B, n^m = k.

Inaczej, dla liczb kardynalnych m (mocy zbioru A) i n (mocy zbioru B) potęgę n^m określany jako liczbę kardynalną, która jest mocą zbioru wszystkich odwzorowań zbioru A w B

(wszystkich funkcji o argumentach w A i wartościach w B).

Prawa potęgowania liczb kardynalnych

(mⁿ )^p = m^{n ·p}

mⁿ ·m^p = m^n+p

(m·n)^p = m^p· n^p

Dalsze prawa relacji i działań na liczbach kardynalnych

n - dowolna liczba naturalna

a, c - liczby kardynalne

m, n, p - dowolne liczby kardynalne

A) Własności liczb a i c:

1) a jest najmniejszą liczbą kardynalna nieskończoną

2) a + 1 = a + 2 = a + n = a

3) 1 · a = 2 · a = n · a = a

4) 2^a = c, inny zapis: 2₁א = ^0א

5) n^a = c, dla 2 ≤ n

6) a^a = c

(6) oznacza, że zbiór wszystkich ciągów nieskończonych przeliczalnych o wyrazach (indeksach) naturalnych jest mocy continuum.

7) c + n = n · c = a + c = c + c = c

8) a · c = c · c = cⁿ = c^a = c (!)

Zachodzi ogólnie, nie tylko dla a i c: suma oraz iloczyn dowolnych dwóch liczb kardynalnych równa się większej z tych liczb.

9) 2^c = a^c = c^c

B) Dla dowolnych m, n i p zachodzi:

1) Jeśli m ≤ n i m ≤ p, to m ≤ p

2) Jeśli m ≤ n, to m + p ≤ n +p

3) Jeśli m ≤ n, to m·p ≤ n·p

4) Jeśli m ≤ n, to m^p ≤ n^p

5) Jeśli m ≤ n, to p^m ≤ pⁿ

6) m + 1 = m + 2 = m + n = m

7) 1 · m = 2 · m = n · m = m

Komentarz do relacji i działań na liczbach kardynalnych

Równość c² = c oznacza, że zachodzi następujące twierdzenie.

Twierdzenie. Moc zbioru punktów kwadratu jest taka sama jak moc zbioru punktów odcinka.

Dowód:

Niech < x, y > jest punktem kwadratu jednostkowego, tj. elementem iloczynu kartezjańskiego

< 0, 1 > x < 0, 1 >. Można więc składowe tej pary zapisać w postaci dziesiętnej jako:

x = 0, a₁ a₂ a₃ …

y = 0, b₁ b₂ b₃ …

Określamy funkcję f:( < 0, 1 > x < 0, 1 >) < 0, 1 > następująco:

f (< x, y >) = z, gdzie z = 0, a₁ b₁ a₂ b₂ a₃ b₃ …

Funkcja ta jest różnowartościowa: różnym punktom < x₁, y₁ > i < x₂, y₂ > kwadratu odpowiadać będą różne punkty z₁ i z₂ odcinka.

Podobnie można wykazać, że moc zbioru punktów sześcianu jest taka sama jak moc zbioru punktów odcinka. Ogólnie zachodzi:

Moc płaszczyzny (ilość punktów na płaszczyźnie) jest taka sama jak moc prostej (c · c = c).

Moc przestrzeni 3-wymiarowej i moc płaszczyzny są takie same jak moc prostej (c³ = c).

Uwaga: Powyższe wyniki podważają intuicyjne pojęcie wymiaru przestrzeni i wydają się być z nią sprzeczne.

Jednak bardziej precyzyjna analiza tego pojęcia pokazuje, że wymiar zbioru punktów zależy nie tylko od mocy zbioru, ale też od sposobu lokalizacji (rozłożenia) tych punktów w przestrzeni. W istocie wymiar każdego zbioru punktów jest cechą topologiczną tego zbioru.

Twierdzenia o równej mocy zbioru punktów odcinka, kwadratu i sześcianu nie są twierdzeniami topologicznym, gdyż nie spełniają warunku przekształcenia ciągłego przestrzeni topologicznych.

Topologiczne twierdzenie o niezmienności wymiaru głosi bowiem, że

dowolne dwie figury o różnych wymiarach nie mogą być topologicznie równoważne.

Twierdzenia o liczbach kardynalnych

Definicja: Funkcja charakterystyczna zbioru A (f_A) jest określona następująco:

f_A (x)= 1 dla x ∈A,

f_A (x)= 0 dla x∉A (x ∈A')

Funkcja charakterystyczna danego zbioru to funkcja, która jego elementom przyporządkowuje liczbę 1, a elementom nie należącym do tego zbioru liczbę 0.

Jeśli dla każdego z podzbiorów pewnego zbioru B została określona funkcja charakterystyczna, to dla każdego x ∈B mamy: dla każdego A, A ⊂ B:

albo x ∈A, wtedy f_A (x)= 1

albo x∉A, wtedy f_A (x)= 0

Oznaczenia:

A - zbiór

2^A - zbiór wszystkich podzbiorów zbioru A

|A| = m

{0,1}^A - zbiór funkcji określonych na zbiorze A, które przybierają tylko dwie wartości: 0, 1.

Twierdzenie

Zbiór wszystkich podzbiorów zbioru A (2^A) jest równej mocy ze zbiorem {0,1}^A, tj. zbiorem wszystkich funkcji f: A → {0,1}; inaczej, ze zbiorem wszystkich funkcji charakterystycznych podzbiorów zbioru A.

Dowód:

Określmy funkcję F: 2^A → {0, 1}^A następująco:

F(B) = f_B, gdzie B - dowolny podzbiór A, tj. B ⊂ A.

Funkcja ta każdemu podzbiorowi zbioru A przypisuje funkcję charakterystyczną tego podzbioru. Należy dowieść, że jest ona różnowartościowa.

Weźmy dwa różne argumenty tej funkcji, tj. dwa różne podzbiory B i C zbioru A, takie, że B ≠ C. Niech a ∈ B \ C. Dla a, zgodnie z definicją funkcji charakterystycznej, mamy:

f_B(a) = 1, f_C(a) = 0, a więc f_B ≠ f_C, tzn. że wartości tej funkcji są także różne.

Zatem, zbiory 2^A oraz {0, 1}^A są równoliczne, co wobec definicja zbiorów równolicznych (p. wyżej) kończy dowód.

Z powyższego twierdzenia na podstawie definicji: liczby kardynalnej i potęgowania liczb kardynalnych (p. wyżej) wynika następujący wniosek.

Twierdzenie

Moc wszystkich podzbiorów dowolnego zbioru A o mocy m wynosi 2^m .

Przykłady:

1) Moc wszystkich podzbiorów zbioru skończonego.

A = {a, b, c}

Podzbiory A:

B = {a}, C = {b}, D = {c}, E = {a, b}, F = {b, c}, G = {a, c}, H = {a, b, c}, I = ∅

Moc zbioru wszystkich podzbiorów zbioru {a, b, c} = 8.

Funkcje charakterystyczne podzbiorów zbioru A, f _{( )}: A → {0, 1}

f_B; f_B(a) = 1, f_B(b) = 0, f_B(c) = 0

f_C; f_C(a) = 0, f_C(b) = 1, f_C(a) = 0

f_D; f_D(a) = 0, f_D(b) = 0, f_D(c) = 1

f_E; f_E(a) = 1, f_E(b) = 1, f_E(c) = 0

f_F; f_F(a) = 0, f_F(b) = 1, f_F(c) = 1

f_G; f_G(a) = 1, f_G(b) = 0, f_G(a) = 1

f_H; f_H(a) = 1, f_H(b) = 1, f_H(c) = 1

f_I; f_H(a) = 0, f_H(b) = 0, f_H(c) = 0

Moc zbioru wszystkich funkcji charakterystycznych podzbiorów zbioru {a, b, c} = 8.

W tym przypadku funkcja F wygląda następująco: F(B) = f_B, F(C) = f_C … F(I) = f_I.

Można ją też zapisać następująco:

F: 2^A → {0, 1}^A

F: {a} → (1, 0, 0)

F: {b}→ (0, 1, 0)

F: {c}→ (0, 0, 1)

F: {a, b}→ (1, 1, 0)

F: {b, c} → ( 0, 1, 1)

F: {a, c}→ (1, 0, 1)

F: {a, b, c}→ (1, 1, 1)

F: ∅→ (0, 0, 0)

Moc wszystkich podzbiorów zbioru skończonego A = {a, b, c}o mocy 3 wynosi 2³ = 8 .

2) Moc wszystkich podzbiorów zbioru liczb naturalnych (N) o mocy a wynosi 2^a .

3) Moc wszystkich podzbiorów zbioru liczb rzeczywistych (R) o mocy c wynosi 2^c .

Oznaczenia:

A - zbiór

f: A → 2^A, f(x) = y; x ∈A, y ⊂ A

Z ⊂ A

Twierdzenie o przekątni

Dla każdej funkcji f: A → 2^A, której argumentami są elementy zbioru A, a wartościami podzbiory tego zbioru, istnieje taki zbiór Z, który nie jest wartością tej funkcji.

Dowód (niewprost):

Określamy zbiór Z następująco:

(1) Z = {x: x ∉f(x)}

Zbiór Z (podzbiór A) jest zbiorem tych x-ów (elementów zbioru A), które nie należą do zbioru f(x). Należy dowieść, że dla każdego x ∈A, zachodzi Z ≠ f(x); inaczej, że nie ma takiego x-a, dla którego zachodziłoby f(x) = Z.

Przypuśćmy, że taki x istnieje (założenie dowodu niewprost), oznaczmy go x_0. Zakładamy więc, że dla x₀ zbiór Z jest wartością funkcji f, czyli, że:

(2) f(x₀) = Z

Na podstawie definicji (1) zbioru Z i prawa eliminacji operatora abstrakcji mamy:

x ∈Z ≡ x ∉ f(x), gdy w tej równoważności podstawimy x = x_0, otrzymamy:

x₀ ∈Z ≡ x₀ ∉f(x₀). Na podstawie negacji zasady ekstensjonalności oznacza to, że

(3) Z ≠ f(x₀).

Wobec sprzeczności (2) i (3) dowód jest zakończony.

Twierdzenie Cantora i wnioski z tego twierdzenia

Twierdzenie Cantora

Żaden zbiór nie jest równej mocy z rodziną wszystkich swoich podzbiorów.

Dowód niewprost:

Załóżmy, że jakiś zbiór (A) jest równej mocy z rodziną wszystkich swoich podzbiorów.

Wówczas na mocy równoliczności zbiorów istniałaby funkcja różnowartościowa f: A → 2^A, tzn. taka funkcja, której argumenty przebiegałyby cały zbiór A, a której wartościami byłyby wszystkie podzbiory zbioru A. Jednak taka funkcja, na mocy twierdzenia o przekątni, nie istnieje.

Twierdzenie Cantora można symbolicznie zapisać następująco:

m ≠ 2^m

gdzie m - moc zbioru A

2^m - moc wszystkich podzbiorów zbioru A (na podstawie twierdzenia o mocy

wszystkich podzbiorów dowolnego zbioru (p. wyżej)

Wniosek 1

Rodzina wszystkich podzbiorów zbioru A nie jest równej mocy z żadnym podzbiorem tego zbioru (osłabienie tezy).

Wniosek 2

Twierdzenie (dotyczące zbioru wszystkich zbiorów)

Nie istnieje zbiór wszystkich zbiorów.

Dowód 1-wszy (niewprost)

Załóżmy, że istnieje zbiór wszystkich zbiorów (ozn. U). Wówczas rodzina wszystkich jego podzbiorów (2^U), będąc zbiorem, na mocy tego założenia byłaby jego podzbiorem; zachodziłoby więc: 2^U ⊂ U. Wobec tego rodzina wszystkich podzbiorów zbioru U (jako jego podzbiór) nie mogłaby być równej mocy z rodziną wszystkich podzbiorów zbioru U (na mocy Wniosku 1), czyli ze sobą.

Dowód 2-gi (niewprost)

Załóżmy, jak poprzednio, że istnieje zbiór U wszystkich zbiorów. Określmy funkcję

f: U → 2^U następująco: f(x) = x

Takie określenie funkcji f jest przy powyższym założeniu poprawne, gdyż każdy podzbiór zbioru U jest także jego elementem, jako zbioru wszystkich zbiorów. Argumentami funkcji f byłyby wszystkie elementy zbioru W, a wartościami wszystkie jego podzbiory (wobec utożsamienia: podzbiór element). To jednak, zgodnie z twierdzeniem o przekątni, nie jest możliwe.

Wniosek 3

Moc dowolnego zbioru jest mniejsza od mocy wszystkich jego podzbiorów.

m < 2^m

Wniosek 4

Powyższa nierówność oznacza też, że dla każdej nieskończonej (pozaskończonej) liczby kardynalnej istnieje liczba kardynalna od niej większa. Tak więc,

istnieje nieskończenie wiele liczba kardynalnych nieskończonych

symbolicznie: a ≤ moc Nc, inaczej:

moc Nc zbioru liczb kardynalnych jest nie mniejsza niż zbioru liczb naturalnych.

Istnieje więc ciąg nieskończony C liczb kardynalnych: C = {a_i}, gdzie i = 1, 2, … → ∞

C = { a₁ , a₂ , a₃ , a₄ , …, a_i , a_i+1 …}

gdzie: a₁ = ₀א

a₂ = ₁א

…

a_i = _kא

a_i+1 = _1+kא

przy czym:

₁א = 2 ^0א

_1+kא = 2^kא itd.

W myśl twierdzenie Cantora w ciągu C każdy jego następny wyraz jest liczbą kardynalną większą od liczby kardynalnej, która jest poprzednim wyrazem tego ciągu.

Addenda

Moc zbioru (pojęcie arytmetyczne) jako rodzina zbiorów (pojęcie teoriomnogościowe)

Jeśli rozpatrujemy równoliczność wśród podzbiorów pewnego usta­lonego zbioru A, wówczas, jak łatwo można pokazać, równoliczność daje się wyróżnić jako pewien zbiór par zbiorów, czyli relacja w mnogościo­wym sensie.

Ilość elementów zbioru X jest to taka cecha zbioru X, która przysługuje zbiorowi X i wszystkim zbiorom z nim równolicznym. Zamiast mówić o cesze zbiorów, możemy posłużyć się pojęciem rodziny zbiorów, czyli zbioru zbiorów, a więc pojęciem nie wykraczającym poza teorię mnogości. Moc zbioru X (symbolicznie |X|) jest to więc

taka rodzina zbiorów, do której należy zbiór X oraz należą wszystkie zbiory równoliczne ze zbiorem X.

Arytmetyka - częścią teorii mnogości

Za pomocą równoliczności możemy już określić ogólne pojęcie ilości, czyli mocy zbioru lub liczby kardynalnej zbioru.

Ograniczając się do podzbiorów zbioru A, rodzinę |X| wyróżniamy symbolicznie następująco:

(1) Y
|X| ≡ Y
2^A ∧ X rl Y

Relacja rl jest oczywiście samozwrotna (każdy zbiór jest równoliczny z samym sobą, funkcją wykazującą równoliczność jest identyczność). Stąd i z (1) wynika, że

X
|X|. Relacja rl jest też symetryczna i prze­chodnia. Symetryczna, bo jeśli X rl_f Y, to

Y rl_f-1 X ; przechodnia, bowiem jeśli X rl_f Y i Y rl_g Z, to X rl_h Z, gdzie h jest superpozycją funkcji g i f: h (x) = g(f (x)) dla x
X. Relacja rl jest więc równoważnością. Stąd i z (1) wynika, że jeśli X
|Y| i Z
|Y|, to X rl Z.

Liczbami kardynalnymi lub mocami zbiorów (LC) nazywamy liczby kardynalne pewnych zbiorów, czyli moce pewnych zbiorów. Rodzinę liczb kardynalnych znów łatwo wyróżnić, jeśli ograniczymy się do roz­patrywania mocy podzbiorów zbioru A:

(2) a
LC ≡ a
2^2A ∧
(Y
2^A ∧ a
|Y|)

Słownie: a jest liczbą kardynalną, gdy a jest identyczne z mocą pewnego podzbioru Y zbioru A.

Definicję LC - rodziny liczb kardynalnych zbioru A można także zapisać za pomocą operatora abstrakcji:

LC
{a: a
2^2A ∧
(Y
2^A ∧ a
|Y|)}

Lub też, stosując (1) oraz aksjomat ekstensjonalności, definicję rodziny liczb kardynalnych możemy rozpisać następująco:

(3) a
LC ≡ a
2^2A ∧
{

a ≡ X rlY)}

Wzór (2) możemy wykorzystać do definicji zbioru liczb naturalnych w ramach teorii mnogości. Mianowicie liczby naturalne będą to liczby kardynalne zbiorów skoń­czonych (Fin).

Definicja liczby naturalnej

(4) a
N ≡ a
2^2A ∧
Fin ∧ a
|Y|)

Działania na liczbach natu­ralnych również można określić odwołując się do zbiorów. Jeśli utworzymy sumę X
Y dwóch zbiorów rozłącznych X i Y takich, że a
|X|) i b
|Y|, to

|X
Y|
b. Rodzinę
b można określić tak, że wyróżnione w ten sposób działanie dodawania nie wyprowadza poza rodzinę liczb naturalnych. Łatwo można bowiem dowieść, że

Jeśli a, b
N, to
b
N

Mnożenie liczb naturalnych można opisać następująco. Jeśli mnożymy przez siebie liczby 3 i 5, to możemy wziąć rodzinę X złożoną z 3 zbiorów rozłącznych, z których każdy ma 5 elementów; wówczas suma rodziny X będzie miała 3
5 elementów. Ogólnie, liczbę

a
b elementów ma suma każdej takiej rodziny X zbiorów rozłącznych, dla której |X|
a

i dla każdego U, jeśli U
X, to |U|
b.

Ponieważ suma skończonej ilości zbiorów skończonych jest zbiorem skończonym, przeto zbiór a
b jest rodziną wszystkich zbiorów równolicznych ze zbiorem skończonym
, a więc jest on liczbą naturalną w sensie wzoru (4). Działanie mnożenia nie wyprowadzi więc poza liczby naturalne, czyli spełnia wzór

Jeśli a, b
N, to
N

Układ < N,
,
> jest pewną dziedziną matematyczną zwaną półpierścieniem liczb naturalnych. Łatwo sprawdzić, że wszystkie podstawowe prawa arytmetyki liczb naturalnych dają się wyprowadzić z aksjomatów teorii mnogości.

A. Grzegorczyk Zarys logiki matematycznej, ss. 43 - 45

1

---