Articles

9.3: Cantorova věta a její důsledky

dovednosti rozvíjet

  • vysvětlete Cantorovu větu

jakmile Cantor ukázal, že existují dva typy nekonečna (spočitatelné a nespočetné), následující otázka byla přirozená: „mají všechny nespočetné množiny stejnou kardinálnost?“

stejně jako ne všichni“ ne-psi “ jsou kočky, není důvod se domnívat, že všechny nespočetné sady by měly mít stejnou velikost. Vytváření nespočetných sad různých velikostí však není tak snadné, jak to zní.

například, co úsečka reprezentovaná intervalem \ ( \ ) a čtvercem reprezentovaným množinou \ (×=\{(x, y) / 0 ≤ x, y ≤ 1\}\). Určitě dvourozměrný čtverec musí být větší nekonečná množina než jednorozměrný úsečkový segment. Je pozoruhodné, že Cantor ukázal, že tyto dvě sady byly stejné kardinality. Ve své korespondenci 1877 tohoto výsledku svému příteli a kolegovi matematikovi Richardu Dedekindovi dokonce Cantor poznamenal: „vidím to, ale nevěřím tomu!“

obr. 9.3.1.png

obrázek \(\PageIndex{1}\): Richard Dedekind

následující dává původní představu o Cantorově důkazu. Cantor vymyslel následující funkci \(f : × → \). Nejprve reprezentujeme souřadnice libovolného bodu \((x, y)∈ ×\) jejich desetinnými reprezentacemi \(x = 0.a_1a_2a_3 …\ ) a \(y = 0.b_1b_2b_3….\ ) I zakončení desetinných míst lze zapsat tímto způsobem, jak bychom mohli napsat \(0.5 = 0.5000….\ ) Pak můžeme definovat \(f (x,y)\) podle

\

tato relativně jednoduchá myšlenka má některé technické potíže související s následujícím výsledkem.

cvičení \(\PageIndex{1}\)

zvažte sekvenci \((0.9,0.99,0.999,…)\). Určete, že tato sekvence konverguje a ve skutečnosti konverguje k \(1\). To naznačuje, že \(0.999… = 1\).

podobně máme \(0.04999… = 0.05000…\), atd. Aby byla desetinná reprezentace reálného čísla v \(\) jedinečná, musíme důsledně zvolit zápis zakončujícího desetinného čísla jako ten, který končí nekonečným řetězcem nul nebo nekonečným řetězcem devíti . Bez ohledu na to, jakou volbu uděláme, nikdy bychom tuto funkci nemohli provést. Například \(109/1100 = 0.09909090…\ ) by měl jako svůj předobraz \((0.0999…,0.9000…)\) což by byl mix obou konvencí.

Cantor byl schopen překonat tuto formalitu, aby demonstroval korespondenci jedna ku jedné, ale místo toho si všimneme, že v obou konvencích je funkce jedna ku jedné, takže to říká, že množina \ ( × \ ) je stejná kardinalita jako nějaká (nespočetná) podmnožina \(\mathbb{R}\). Skutečnost, že to má stejnou kardinalitu jako \(\mathbb{R}\), je něco, k čemu se vrátíme. Ale nejprve se pokusíme postavit nespočetnou množinu, která nemá stejnou kardinalitu jako \(\mathbb{R}\). K řešení tohoto problému Cantor v roce 1891 prokázal následující.

Věta \(\PageIndex{1}\): Cantorova věta

Nechť \(s\) je libovolná množina. Pak neexistuje žádná vzájemná korespondence mezi \(S\) A \(P (S)\), množinou všech podmnožin \(s\).

vzhledem k tomu, \(s\) může být uveden do one-to-one korespondence s podmnožinou \(P (S) (A → \ {a\})\), pak to říká, že \(P (S)\) je alespoň tak velký jako \(S\). V konečném případě je \(/P (S)/\) striktně větší než \(/S/\), jak ukazuje následující problém. To také ukazuje, proč \(P (S)\) se nazývá výkonová sada \(s\).

Cvičení \(\PageIndex{2}\)

Prokázat: Pokud \(|S / = n\), pak \(/P| S) / = 2n\)

Nápověda

Nechť \(S = a_1, a_2, …, n\). Zvažte následující korespondenci mezi prvky \(P (S)\) a množinou \(T\) všech \(n\) – n-tic Ano (\(Y\)) nebo ne (\(N\)):

\

kolik prvků je v \(T\)?

cvičení \(\PageIndex{3}\)

Dokažte Kantorovu větu.

Nápověda

Předpokládejme, že pro rozpor existuje individuální korespondence \(f: S → P (s)\). Zvažte \(a = \{x S S / x \ not {}} f (x)\}\). Vzhledem k tomu, \(f\) je onto, pak je \(a ∈ a\) takový, že \(A = f (a)\). Je \(a ∈ a\) nebo je \(a \not {}} a\)?

ve skutečnosti se ukazuje, že \(\mathbb{R}\) a \(P (\mathbb{N})\) mají stejnou kardinalitu. To lze vidět kruhovým objezdem pomocí některých výše uvedených nápadů z cvičení \(\PageIndex{2}\). Konkrétně nechť \(T\) je množina všech sekvencí nul nebo jedniček (můžete použít \(Y\) S nebo \(N\) s, pokud chcete). Pak je jasné, že \(T\) A \(P (\mathbb{N})\) mají stejnou kardinalitu.

pokud vezmeme v úvahu \((0,1]\), které má stejnou kardinalitu jako \(\mathbb{R}\), pak vidíme, že toto má stejnou kardinalitu jako \(T\). Konkrétně, pokud uvažujeme o číslech v binárních číslech, pak každé reálné číslo v \(\) může být zapsáno jako \(\sum_{j=1}^{\infty } \frac{a_j}{2^j} = (a_1, a_2, \cdots)\) kde \(a_j ∈ \{0,1\}\). Musíme vzít v úvahu skutečnost, že binární reprezentace jako \(0.0111…\ ) a \(0.1000…\ ) představují stejné reálné číslo (řekněme, že žádné reprezentace nekončí nekonečným řetězcem nul), pak vidíme, že \ ( \ ) má stejnou kardinalitu jako \(T – U\), kde \(U\) je množina všech sekvencí končících nekonečným řetězcem nul. Ukazuje se, že \(U\) sám o sobě je počitatelná množina.

cvičení \(\PageIndex{4}\)

Let \(U_n = \{(a_1, a_2, a_3,…) / a_j ∈ \{0,1\}\) a \(a_{n+1} = a_{n+2} = ··· = 0\}\). Ukázat, že pro každý \(n\), \(U_n\) je konečný a použít k závěru, že \(U\) je počítatelně nekonečný.

následující dva problémy ukazují, že smazání počitatelné množiny z nespočetné množiny nemění její kardinálnost.

cvičení \(\PageIndex{5}\)

Nechť \(S\) je nekonečná množina. Dokažte, že \(S\) obsahuje početně nekonečnou podmnožinu.

cvičení \(\PageIndex{6}\)

Předpokládejme, že \(X\) je nespočetná Množina A \(Y ⊂ X\) je nekonečně nekonečná. Dokažte, že \(X\) a \(X-Y\) mají stejnou kardinalitu.

Nápověda

Let \(Y = Y_0\). Pokud je \(X-Y_0\) nekonečná množina, pak podle předchozího problému obsahuje početně nekonečnou množinu \(Y_1\). Podobně je-li \(X – (Y_0 ∪ Y_1)\) nekonečný, obsahuje také nekonečnou množinu \(Y_2\). Opět platí, že pokud \(X – (Y_0 ∪ Y_1 y Y_2)\) je nekonečná množina, pak obsahuje nekonečnou množinu \(Y_3\) atd. Pro \(n = 1,2,3,…,\) nechť \(f_n: Y_{n-1} → Y_n\) je korespondence jedna ku jedné a definuje \(f : X → X – Y\) podle

\

ukázat, že \(f\) je one-to-one a onto.

výše uvedené problémy říkají, že \(R\), \(T-U\), \(T\) A \(P (N)\) mají stejnou kardinalitu.

jak bylo uvedeno dříve, Cantorova práce na nekonečných množinách měla na počátku dvacátého století hluboký dopad na matematiku. Například při zkoumání důkazu Kantorovy věty vymyslel významný logik Bertrand Russell svůj slavný paradox v roce 1901. Před touto dobou byla sada naivně považována za pouhou sbírku předmětů. Prostřednictvím práce Cantora a dalších, sady se staly ústředním předmětem studia v matematice, protože mnoho matematických konceptů bylo přeformulováno, pokud jde o sady. Myšlenka byla, že teorie množin měla být sjednocujícím tématem matematiky. Tento paradox nastavil matematický svět na ucho.

Russellův Paradox

zvažte množinu všech množin, které nejsou samy o sobě prvky. Tuto množinu nazýváme \(D\) a ptáme se: „je \(D ∈ D\)?“Symbolicky je tato sada

\

pokud \(D ∈ D\), pak podle definice \(D \ not {}} d\). Pokud D 6∈ D, pak podle definice \(D ∈ D\).

pokud se podíváte zpět na důkaz Cantorovy věty, byla to v podstatě myšlenka, která nám dala rozpor. Mít takový rozpor na nejzákladnější úrovni matematiky bylo skandální. To přinutilo řadu matematiků a logiků, aby pečlivě vymysleli axiomy, kterými by mohly být množiny konstruovány. Být upřímný, většina matematiků stále přistupuje k teorii množin z naivního hlediska, protože množiny, se kterými se obvykle zabýváme, spadají do kategorie toho, co bychom nazvali „normálními množinami“.“Ve skutečnosti se takový přístup oficiálně nazývá naivní teorie množin (na rozdíl od axiomatické teorie množin). Pokusy postavit teorii množin a logiku na pevné základy však vedly k modernímu studiu symbolické logiky a nakonec k návrhu počítačové (strojové) logiky.

další místo, kde kantorova práce měla hluboký vliv v moderní logice, pochází z něčeho, o čem jsme se zmínili dříve. Předtím jsme ukázali, že čtverec jednotky \ ( × \ ) má stejnou kardinalitu jako nespočetná podmnožina \(\mathbb{R}\). Ve skutečnosti Cantor ukázal, že jednotka čtverec měl stejnou kardinálnost jako \(\mathbb{R}\) sám a byl přesunut k postupu následující v roce 1878.

domněnka (hypotéza kontinua)

každá nespočetná podmnožina \(\mathbb{R}\) má stejnou kardinalitu jako \(\mathbb{R}\).

Cantor nebyl schopen dokázat nebo vyvrátit tuto domněnku (spolu s každým jiným matematikem). Ve skutečnosti prokázání nebo vyvrácení této domněnky, která byla nazvána hypotéza kontinua, byl jedním z Hilbertových slavných \(23\) problémů prezentovaných jako výzva matematikům na Mezinárodním kongresu matematiků v roce 1900.

protože \(\mathbb{R}\) má stejnou kardinalitu jako \(P (N)\), pak byla hypotéza kontinua zobecněna na:

domněnka (zobecněná hypotéza kontinua)

vzhledem k nekonečné množině \(s\) neexistuje žádná nekonečná množina, která by měla kardinalitu striktně mezi množinou \(S\) a její mocninou \(P(S)\).

snahy toto dokázat nebo vyvrátit byly marné a s dobrým důvodem. V roce 1940 logik Kurt Gödel ukázal, že hypotézu kontinua nelze vyvrátit z Zermelo-Fraenkelových axiomů teorie množin 1. V roce 1963 Paul Cohen ukázal, že hypotéza kontinua nemohla být prokázána pomocí axiomů Zermelo-Fraenkel. Jinými slovy, axiomy Zermelo-Fraenkel neobsahují dostatek informací k rozhodnutí o pravdivosti hypotézy.

jsme ochotni se vsadit, že v tomto okamžiku může vaše hlava trochu plavat s nejistotou. Pokud ano, pak vězte, že se jedná o stejné pocity, jaké matematická komunita zažila v polovině dvacátého století. V minulosti byla matematika považována za model logické jistoty. Je znepokojující zjistit, že existují prohlášení ,která jsou „nerozhodnutelná“.“Ve skutečnosti Gödel v roce 1931 dokázal, že konzistentní konečný axiomový systém, který obsahoval axiomy aritmetiky, by vždy obsahoval nerozhodnutelné výroky, které by s těmito axiomy nemohly být ani pravdivé, ani nepravdivé. Matematické znalosti by byly vždy neúplné.

 obr. 9.3.2.png

obrázek \(\PageIndex{2}\): Kurt Gödel

takže pokusem položit základy počtu na pevnou zem jsme se dostali do bodu, kdy nikdy nemůžeme získat matematickou jistotu. Znamená to, že bychom měli zvracet ruce a připustit porážku? Měli bychom být paralyzováni strachem, že se o něco pokusíme? Určitě ne! Jak jsme již zmínili, většina matematiků si vede dobře pragmatickým přístupem: pomocí své matematiky řeší problémy, se kterými se setkávají. Ve skutečnosti jsou to obvykle problémy, které motivují matematiku. Je pravda, že matematici riskují, že ne vždy se dostanou ven, ale stále tyto šance využívají, často s úspěchem. I když úspěchy vedou k dalším otázkám, jak to obvykle dělají, řešení těchto otázek obvykle vede k hlubšímu porozumění. Přinejmenším naše neúplné porozumění znamená, že budeme mít vždy více otázek k zodpovězení, více problémů k vyřešení.

co jiného by matematik mohl požádat?