Articles

9.3: twierdzenie Cantora i jego konsekwencje

umiejętności rozwijania

  • wyjaśnij twierdzenie Cantora

kiedy Cantor pokazał, że istnieją dwa rodzaje nieskończoności (policzalny i niepoliczalny), naturalne było następujące pytanie: „czy wszystkie zbiory niepoliczalne mają tę samą Kardynalność?”

podobnie jak nie wszystkie „Nie-psy” są kotami, nie ma powodu, aby sądzić, że wszystkie niezliczone zestawy powinny być tej samej wielkości. Jednak konstruowanie niezliczonych zestawów o różnych rozmiarach nie jest takie proste, jak się wydaje.

na przykład, co z segmentem linii reprezentowanym przez interwał \ ( \ ) i kwadratem reprezentowanym przez zbiór \ (×=\{(x,y)|0 ≤ x, y ≤ 1\}\). Z pewnością dwuwymiarowy kwadrat musi być większym nieskończonym zbiorem niż jednowymiarowy segment linii. Co ciekawe, Cantor pokazał, że te dwa zestawy były takie same. W swojej korespondencji z 1877 roku o tym wyniku do swojego przyjaciela i kolegi matematyka, Richarda Dedekinda, nawet Cantor zauważył: „widzę to, ale nie wierzę!”

rys. 9.3.1.png

rysunek \(\PageIndex{1}\): Richard Dedekind

poniżej przedstawiono oryginalny pomysł dowodu Cantora. Cantor opracował następującą funkcję \(f : × → \). Po pierwsze, reprezentujemy współrzędne dowolnego punktu \((x, y)∈ ×\) przez ich reprezentacje dziesiętne \(x = 0.a_1a_2a_3 …\ ) i \(y = 0.b_1b_2b_3….\ ) Nawet końcówki dziesiętne mogą być zapisywane w ten sposób, jak możemy zapisać \(0.5 = 0.5000….\ ) Możemy wtedy zdefiniować \(f (x,y)\) przez

\

ten stosunkowo prosty pomysł ma pewne trudności techniczne związane z następującym wynikiem.

ćwiczenia \(\PageIndex{1}\)

rozważ sekwencję \((0.9,0.99,0.999,…)\). Określ, że ta sekwencja zbiega się i, w rzeczywistości, zbiega się do \(1\). Sugeruje to, że \(0.999… = 1\).

podobnie mamy \(0.04999… = 0.05000…\), itp. Aby urzÄ … dzenie dziesiętne liczby rzeczywistej w \(\) byĹ 'o unikalne, musimy dokonaÄ ‡ konsekwentnego wyboru zapisu koĹ” czÄ … cego urzÄ … dzenia dziesiętnego jako takiego, ktĂłre koĹ ” czy siÄ ™ nieskończonym ciÄ … giem zer lub nieskończonym ciÄ … giem dziewiątek . Bez względu na to, jakiego wyboru dokonamy, nigdy nie moglibyśmy wprowadzić tej funkcji. Na przykład \(109/1100 = 0.09909090…\ ) będzie miał jako swój pre-image \((0.0999…,0.9000…)\), która byłaby mieszanką dwóch konwencji.

Cantor był w stanie przezwyciężyć tę technikę, aby zademonstrować korespondencję jeden do jednego, ale zamiast tego zauważymy, że w obu konwencjach funkcja jest jeden do jednego, więc mówi to, że zbiór \(×\) jest taki sam jak jakiś (niezliczalny) podzbiór \(\mathbb{R}\). Fakt, że ma to taką samą Kardynalność jak \(\mathbb{R}\), jest czymś, do czego wrócimy. Ale najpierw spróbujemy skonstruować niezliczalny zbiór, który nie ma takiej samej kardynalności jak \(\mathbb{R}\). Aby rozwiązać ten problem, Cantor udowodnił w 1891 roku, co następuje.

\(\PageIndex{1}\): Twierdzenie cantora

Niech \(s\) będzie dowolnym zbiorem. Wtedy nie ma korespondencji jeden do jednego pomiędzy \(S\) I \(P(S)\), zbiorem wszystkich podzbiorów \(S\).

ponieważ \(S\) można umieścić w korespondencji jeden do jednego z podzbiorem \(P(s) (a → \{a\})\), to mówi, że \(P(S)\) jest co najmniej tak duży jak \(s\). W skończonym przypadku \(|P (S)|\) jest ściśle większa od \(|S/\), Jak pokazuje poniższy problem. Pokazuje również, dlaczego \(P(S)\) nazywa się zbiorem mocy \(S\).

Ćwiczenia \(\PageIndex{2}\)

Udowodnij: If \(/S / = n\), then \(|P(S)| = 2n\)

Hint

Let \(s = a_1, a_2,…, a_n\). Rozważ następującą korespondencję między elementami \(P(S)\) i zestawem \(T\) wszystkich \(n\)-krotek yes (\(Y\)) lub no (\(N\)):

\

ile elementów jest w \(T\)?

ćwiczenia \(\PageIndex{3}\)

udowodnij twierdzenie Cantora.

podpowiedź

załóżmy dla sprzeczności, że istnieje korespondencja jeden do jednego \(f : S → P(S)\). Rozważ \(a = \{x ∈ S / x \not { ∈ } f (x)\}\). Ponieważ \(f\) jest onto, to jest \(a ∈ a\) takie, że \(A = f (a)\). Jest \(a ∈ a\) czy jest \(a \not {∈} A\)?

W rzeczywistości okazuje się, że \(\mathbb{R}\) I \(P(\mathbb{N})\) mają tę samą cardinalność. Można to zobaczyć w sposób okrężny, wykorzystując niektóre z powyższych pomysłów z Ćwiczenia \(\PageIndex{2}\). W szczególności, niech \(T\) będzie zbiorem wszystkich sekwencji zer lub jedynek(możesz użyć \(Y\)S lub \(N\)S, jeśli wolisz). Następnie łatwo jest zobaczyć, że \(T\) I \(P (\mathbb{N})\) mają tę samą cardinalność.

jeśli weźmiemy pod uwagę \((0,1]\), która ma taką samą Kardynalność jak \(\mathbb{R}\), to widzimy, że ma ona taką samą Kardynalność jak \(T\). W szczególności, jeśli myślimy o liczbach binarnych, to każda liczba rzeczywista w \ ( \ ) może być zapisana jako \(\sum_{j=1}^{\infty } \ frac{a_j}{2^j} = (a_1, a_2, \cdots )\) gdzie \(a_j ∈ \{0,1\}\). Musimy wziąć pod uwagę fakt, że reprezentacje binarne, takie jak \(0.0111…\) i \(0,1 tys…\ ) reprezentują tę samą liczbę rzeczywistą (powiedzmy, że żadna reprezentacja nie kończy się nieskończonym ciągiem zer), wtedy widzimy, że \ ( \ ) ma taką samą Kardynalność jak \(T – U\), gdzie \(u\) jest zbiorem wszystkich sekwencji kończących się nieskończonym ciągiem zer. Okazuje się, że \(U\) jest zbiorem policzalnym.

ćwiczenia \(\PageIndex{4}\)

Let \(U_n = \{(a_1, a_2, a_3,…) / a_j ∈ \{0,1\}\) i \(a_{n + 1} = a_{n+2} = ··· = 0\}\). Pokaż, że dla każdego \(n\), \(U_n\) jest skończona i użyj tego do wniosku, że \(u\) jest policzalnie nieskończona.

dwa poniższe problemy pokazują, że usunięcie zbioru policzalnego z zbioru niepoliczalnego nie zmienia jego cardinalności.

ćwiczenia \(\PageIndex{5}\)

Niech \(S\) będzie zbiorem nieskończonym. Udowodnij, że \(S\) Zawiera nieskończony podzbiór.

ćwiczenia \(\PageIndex{6}\)

Załóżmy, że \(X\) jest zbiorem niepoliczalnym, a \(Y ⊂ X\) jest nieskończenie nieskończone. Udowodnij, że \(X\) i \(X – Y\) mają tę samą Kardynalność.

Podpowiedź

Let \(Y = Y_0\). Jeśli \(X-Y_0\) jest zbiorem nieskończonym, to przez poprzedni problem zawiera zbiór nieskończony \(Y_1\). Podobnie, jeśli \(X – (Y_0 ∪ Y_1)\) jest nieskończony, zawiera również nieskończony zbiór \(Y_2\). Jeśli \(X – (Y_0 ∪ Y_1 ∪ Y_2)\) jest zbiorem nieskończonym, to zawiera zbiór nieskończony \(Y_3\) itd. For \(n = 1,2,3,…,\) niech \(f_n : Y_{N-1} → Y_n\) będzie korespondencją jeden-do-jednego i zdefiniuje \(f: X → X-Y\) przez

\

Pokaż, że \(f\) jest jeden do jednego i na.

powyższe problemy mówią, że \(R\), \(T – U\), \(T\) I \(P(N)\) wszystkie mają tę samą Kardynalność.

jak wspomniano wcześniej, prace Cantora nad nieskończonymi zbiorami miały głęboki wpływ na matematykę na początku XX wieku. Na przykład, badając dowód twierdzenia Cantora, wybitny Logik Bertrand Russell opracował swój słynny paradoks w 1901 roku. Wcześniej zestaw był naiwnie postrzegany jako zbiór przedmiotów. Dzięki pracy Cantora i innych, zbiory stawały się centralnym obiektem badań w matematyce, ponieważ wiele pojęć matematycznych było przeformułowanych pod względem zbiorów. Chodziło o to, że teoria mnogości miała być jednoczącym tematem matematyki. Paradoks ten wprawił matematyczny świat w osłupienie.

paradoks Russella

rozważmy zbiór wszystkich zbiorów, które nie są elementami samych siebie. Nazywamy ten zbiór \(D\) i pytamy: „Is \(D ∈ D\)?”Symbolicznie ten zestaw jest

\

If \(D ∈ D\), then by definition, \(D \not {∈} d\). Jeśli D 6∈ D, to z definicji \(D ∈ D\).

jeśli spojrzeć wstecz na dowód twierdzenia Cantora, to był w zasadzie pomysł, który dał nam sprzeczność. Zaistnienie takiej sprzeczności na najbardziej podstawowym poziomie matematyki było skandaliczne. Zmusiło to wielu matematyków i logików do starannego opracowania aksjomatów, dzięki którym zbiory mogą być konstruowane. Szczerze mówiąc, większość matematyków nadal podchodzi do teorii zbiorów z naiwnego punktu widzenia, ponieważ zbiory, którymi zwykle się zajmujemy, należą do kategorii „zbiorów normalnych”.”W rzeczywistości takie podejście jest oficjalnie nazywane naiwną teorią zbiorów (w przeciwieństwie do aksjomatycznej teorii zbiorów). Jednak próby postawienia teorii zbiorów i logiki na solidnych podstawach doprowadziły do współczesnych badań nad logiką symboliczną i ostatecznie do projektowania logiki komputerowej (maszynowej).

kolejne miejsce, w którym twórczość Cantora wywarła głęboki wpływ na współczesną logikę, pochodzi z czegoś, do czego wcześniej nawiązywaliśmy. Pokazaliśmy wcześniej, że kwadrat jednostki \ ( × \ ) ma taką samą cardinalność jak niepoliczalny podzbiór \(\mathbb{R}\). W rzeczywistości Cantor wykazał, że kwadrat jednostkowy ma taką samą cardinalność jak \(\mathbb{R}\) i został przesunięty w 1878 roku, aby przejść dalej.

domysły (hipoteza Continuum)

każdy niepoliczalny podzbiór \(\mathbb{R}\) ma taką samą Kardynalność jak \(\mathbb{R}\).

Cantor nie był w stanie udowodnić lub obalić tego przypuszczenia (podobnie jak każdy inny matematyk). W rzeczywistości udowodnienie lub obalenie tej hipotezy, która została nazwana hipotezą Continuum, było jednym ze słynnych problemów Hilberta \(23\) przedstawionych jako wyzwanie dla matematyków na Międzynarodowym Kongresie matematyków w 1900 roku.

ponieważ \(\mathbb{R}\) ma taką samą Kardynalność jak \(P(N)\), wtedy hipoteza Continuum została uogólniona do:

domysły (uogólniona hipoteza Continuum)

biorąc pod uwagę nieskończony zbiór \(S\), nie ma nieskończonego zbioru, który ma Kardynalność ściśle między tym z \(s\) i jego zbiór mocy \(P (S)\).

próby udowodnienia lub obalenia tego były daremne i nie bez powodu. W 1940 roku Logik Kurt Gödel wykazał, że hipotezy Continuum nie można obalić z aksjomatów Zermelo-Fraenkela teorii mnogości 1. W 1963 Paul Cohen wykazał, że hipotezy Continuum nie można udowodnić za pomocą aksjomatów Zermelo-Fraenkela. Innymi słowy, aksjomaty Zermelo-Fraenkela nie zawierają wystarczającej ilości informacji, aby zdecydować o prawdziwości hipotezy.

jesteśmy gotowi założyć się, że w tym momencie Twoja głowa może pływać trochę z niepewnością. Jeśli tak, to wiedz, że są to te same uczucia, których społeczność matematyczna doświadczyła w połowie XX wieku. W przeszłości matematyka była postrzegana jako model logicznej pewności. Niepokojące jest stwierdzenie, że istnieją stwierdzenia, które są „nierozstrzygalne.”W rzeczywistości Gödel udowodnił w 1931 roku, że spójny skończony system aksjomatów, który zawierał aksjomaty arytmetyki, zawsze będzie zawierał stwierdzenia nierozstrzygalne, które nie mogą być ani udowodnione, ani fałszywe z tymi aksjomatami. Wiedza matematyczna zawsze byłaby niepełna.

rys. 9.3.2.png

rysunek \(\PageIndex{2}\): Kurt Gödel

starając się postawić fundamenty rachunku na solidnym podłożu, doszliśmy do punktu, w którym nigdy nie możemy uzyskać matematycznej pewności. Czy to oznacza, że powinniśmy podnieść ręce i przyznać się do porażki? Czy powinniśmy być sparaliżowani strachem przed próbowaniem czegokolwiek? Na pewno nie! Jak już wspomnieliśmy, większość matematyków radzi sobie dobrze, przyjmując pragmatyczne podejście: używając swojej matematyki do rozwiązywania problemów, które napotykają. W rzeczywistości to właśnie problemy motywują matematykę. To prawda, że matematycy ryzykują, które nie zawsze się sprawdzają, ale nadal podejmują te szanse, często z sukcesem. Nawet jeśli sukcesy prowadzą do większej liczby pytań, jak zwykle, rozwiązywanie tych pytań zwykle prowadzi do głębszego zrozumienia. Przynajmniej nasze niepełne zrozumienie oznacza, że zawsze będziemy mieli więcej pytań do odpowiedzi, więcej problemów do rozwiązania.

o co jeszcze może prosić matematyk?