Articles

9.3: Cantor tétele és következményei

készségek fejlesztése

  • magyarázza Cantor tétele

miután Cantor megmutatta, hogy kétféle végtelen létezik (megszámlálható és megszámlálhatatlan), a következő kérdés természetes volt: “vajon minden megszámlálhatatlan halmaznak ugyanaz a kardinalitása?”

csakúgy, mint nem minden “nem kutya” macska, nincs ok azt hinni, hogy minden megszámlálhatatlan készletnek azonos méretűnek kell lennie. Azonban építése megszámlálhatatlan készletek különböző méretű nem olyan egyszerű, mint amilyennek hangzik.

például mi a helyzet a \(\) intervallum által ábrázolt vonalszegmenssel és a \ (++=\{(x,y)|0 6,y 1\}\) halmaz által képviselt négyzettel. Természetesen a kétdimenziós négyzetnek nagyobb végtelen halmaznak kell lennie, mint az egydimenziós vonalszakasz. Figyelemre méltó, hogy Cantor megmutatta, hogy ez a két készlet ugyanaz a kardinalitás. 1877-es levelezésében ezt az eredményt barátjának és matematikus társának, Richard Dedekindnek, még Cantor is megjegyezte: “látom, de nem hiszem el!”

ábra 9.3.1.png

ábra \(\PageIndex{1}\): Richard Dedekind

az alábbiakban bemutatjuk Cantor bizonyításának eredeti elképzelését. Cantor a következő függvényt dolgozta ki \(F:\). Először a \((x,y)\) pontok koordinátáit ábrázoljuk decimális ábrázolásukkal \(x = 0.a_1a_2a_3 …\ ) és \ (y = 0.b_1b_2b_3….\ ) Még a záró tizedesjegyeket is írhatjuk így, ahogy írhatnánk \(0,5 = 0,5000….\ ) Ezután definiálhatjuk \(f (x,y)\)

\

ennek a viszonylag egyszerű ötletnek vannak technikai nehézségei a következő eredményhez kapcsolódóan.

gyakorlat \(\Oldalindex{1}\)

Tekintsük a sorrendet \((0.9,0.99,0.999,…)\). Határozzuk meg, hogy ez a szekvencia konvergál-e, és valójában \(1\) – re konvergál. Ez arra utal, hogy \(0.999… = 1\).

hasonlóképpen van \(0,04999… = 0.05000…\ ) stb. Ahhoz, hogy egy valós szám decimális ábrázolása \(\) egyedi legyen, következetesen választanunk kell egy végződő decimális írását, amely végtelen nulla vagy végtelen kilences karakterláncban végződik . Nem számít, milyen döntést hozunk, soha nem tudtuk ezt a funkciót rá. Például: \(109/1100 = 0,09909090…\ ) volna, mint a pre-image \((0.0999…,0.9000…)\) ami a két konvenció keveréke lenne.

Cantor képes volt legyőzni ezt a technikát, hogy bemutassa az egy az egyhez levelezést, de ehelyett megjegyezzük, hogy bármelyik Konvencióban a függvény egy az egyhez, tehát ez azt mondja, hogy a halmaz \ ( ^ \ ) ugyanaz a kardinalitás, mint a \(\mathbb{R}\) néhány (megszámlálhatatlan) részhalmaza. Az a tény, hogy ennek ugyanaz a kardinalitása, mint a \(\mathbb{R}\), valami, amire visszatérünk. De először megpróbáljuk építeni egy megszámlálhatatlan halmaz, amely nem ugyanaz a kardinalitás, mint \(\mathbb{R}\). Ennek a kérdésnek a kezelésére Cantor 1891-ben bizonyította a következőket.

Tétel \(\Oldalindex{1}\): Cantor tétele

legyen \(S\) bármilyen halmaz. Ekkor nincs egy az egyhez levelezés \(S\) és \(P(S)\) között, a \(S\) összes részhalmazának halmaza.

mivel \(S\) egy az egyhez levelezésbe helyezhető \(P(S) (a \{a\})\) részhalmazával, akkor ez azt mondja, hogy \(P(S)\) legalább akkora, mint \(S\). Véges esetben a \(|P(S)|\) szigorúan nagyobb, mint \(|S|\), amint azt a következő probléma mutatja. Azt is bemutatja, hogy a \(P(S)\) – t miért nevezzük \(S\) teljesítménykészletnek.

Gyakorlat \(\Oldalindex{2}\)

Bizonyítás: Ha \(/S / = n\), akkor \(/P (S) / = 2n\)

tipp

legyen \(S = a_1, a_2,…, a_n\). Tekintsük a következő megfelelést a \(P(S)\) elemei és az összes \(n\) halmaza között-igen (\(Y\)) vagy nem (\(N\)):

\

hány elem van a \(T\) – ben?

gyakorlat \(\PageIndex{3}\)

Bizonyítsuk be Cantor tételét.

tipp

tegyük fel az ellentmondás, hogy van egy-az-egyhez levelezés \(f: S ++ P (S)\). Fontolja meg \(a = \{X} s|x \nem {}} f (x)\}\). Mivel\ (f\) van rá, akkor van\ (a A\) oly módon, hogy\(A = f (a)\). Van\ (a A\) vagy van \ (a \ nem { \ } a\)?

valójában kiderül, hogy \(\mathbb{R}\) és \(P(\mathbb{N})\) ugyanaz a kardinalitás. Ez körforgalomban látható a \(\PageIndex{2}\) gyakorlat fenti ötleteinek felhasználásával. Pontosabban, legyen \(T\) a nullák vagy egyes sorozatok halmaza (használhatja \(Y\) s vagy \(N\) s, ha úgy tetszik). Ekkor egyértelmű, hogy \(T\) és \(P(\mathbb{N})\) ugyanaz a kardinalitás.

ha figyelembe vesszük \((0,1]\), amelynek ugyanaz a kardinalitása, mint \(\mathbb{R}\), akkor láthatjuk, hogy ennek is ugyanaz a kardinalitása, mint \(T\). Pontosabban, ha a bináris számokra gondolunk, akkor a \(\) minden valós száma \(\sum_{j=1}^{\infty } \frac{a_j}{2^j} = (a_1, a_2, \cdots )\) ahol \(a_j ++ \{0,1\}\). Figyelembe kell vennünk azt a tényt, hogy a bináris ábrázolások, például a \(0.0111…\ ) és \(0.1000…\ ) ugyanazt a valós számot képviselik (mondjuk, hogy egyetlen reprezentáció sem ér véget végtelen nullasorozatban), akkor láthatjuk, hogy \ ( \ ) ugyanolyan kardinalitással rendelkezik, mint \(T – U\), ahol \(U\) az összes végtelen nullasorozatban végződő szekvencia halmaza. Kiderül, hogy \(U\) maga egy megszámlálható halmaz.

gyakorlat \(\Oldalindex{4}\)

legyen \(U_n = \{(a_1, a_2, a_3,…) / a_j \{0,1\}\) és \(a_{n + 1} = a_{n+2} = ··· = 0\}\). Mutassuk meg, hogy minden \(n\),\ (U_n\) véges, és használjuk ezt arra a következtetésre, hogy\ (U\) megszámlálhatóan végtelen.

A következő két probléma azt mutatja, hogy egy megszámlálható halmaz törlése egy megszámlálhatatlan halmazból nem változtatja meg annak kardinalitását.

gyakorlat \(\Oldalindex{5}\)

legyen\ (S\) végtelen halmaz. Bizonyítsuk be, hogy\ (S\) tartalmaz egy megszámlálhatóan végtelen részhalmazt.

gyakorlat \(\PageIndex{6}\)

tegyük fel, hogy\ (X\) megszámlálhatatlan halmaz, és\ (Y \ X\) megszámlálhatatlanul végtelen. Bizonyítsuk be, hogy \(X\) és \(X – Y\) ugyanaz a kardinalitás.

Tipp

Legyen \(Y = Y_0\). Ha \(X – Y_0\) végtelen halmaz, akkor az előző probléma szerint megszámlálhatóan végtelen halmazt tartalmaz \(Y_1\). Hasonlóképpen, ha \(X – (Y_0 6_1)\) végtelen, akkor tartalmaz egy végtelen halmazt is \(Y_2). Ismét, ha \(X- (Y_0 6_1 Y_2)\) végtelen halmaz, akkor végtelen halmazt tartalmaz \(3) stb. Mert \(n = 1,2,3,…,\) legyen \(f_n : Y_{n-1} dg_n\) egy az egyhez levelezés, és határozza meg \(f : X DG X – Y\)

\

mutassa meg, hogy \(f\) egy az egyhez és rá.

a fenti problémák azt mondják, hogy \(R\), \(T – U\), \(T\) és \(P(N)\) mind azonos kardinalitással rendelkeznek.

mint korábban jeleztük, Cantor végtelen halmazokkal kapcsolatos munkája a huszadik század elején mély hatást gyakorolt a matematikára. Például a Cantor-tétel bizonyításának vizsgálatakor a jeles logikus Bertrand Russell 1901-ben kidolgozta híres paradoxonját. Ez idő előtt egy készletet naivan úgy gondoltak, mint csak tárgyak gyűjteményét. Munkája révén a Cantor és mások, készletek egyre központi tárgya tanulmány a matematikában, mint sok matematikai fogalmakat, hogy újrafogalmazzák szempontjából készletek. Az ötlet az volt, hogy a halmazelméletnek a matematika egyesítő témájának kell lennie. Ez a paradoxon a fülébe helyezte a matematikai világot.

Russell-paradoxon

Tekintsük az összes halmaz halmazát, amelyek nem önmaguk elemei. Ezt a halmazt \(D\) – nek hívjuk, és megkérdezzük: “\(D\D\)?”Szimbolikusan ez a készlet

\

ha \(D\ D\), akkor definíció szerint \(D \ nem {\D} D\). Ha D 6 .. D, akkor definíció szerint \(D .. D\).

ha visszatekintünk a Cantor-tétel bizonyítására, alapvetően ez volt az ötlet, amely ellentmondást adott nekünk. Botrányos volt egy ilyen ellentmondás a matematika legalapvetőbb szintjén. Számos matematikust és logikust kényszerített arra, hogy gondosan dolgozzák ki azokat az axiómákat, amelyekkel a halmazokat meg lehet építeni. Őszintén szólva, a legtöbb matematikus még mindig naiv szempontból közelíti meg a halmazelméletet, mivel azok a halmazok, amelyekkel általában foglalkozunk, a “normál halmazoknak” nevezett kategóriába tartoznak.”Valójában egy ilyen megközelítést hivatalosan naiv Halmazelméletnek hívnak (szemben az axiomatikus halmazelmélettel). A halmazelmélet és a logika szilárd alapokra helyezésére tett kísérletek azonban a szimbolikus logika modern tanulmányozásához és végső soron a számítógépes (gépi) logika tervezéséhez vezettek.

egy másik hely, ahol Cantor munkája mély hatást gyakorolt a modern logikára, valamiből származik, amire korábban utaltunk. Korábban megmutattuk, hogy az egység négyzet \ ( \ ) ugyanolyan kardinalitással rendelkezik, mint a \(\mathbb{R}\) megszámlálhatatlan részhalmaza. Tény, hogy Cantor kimutatta, hogy az egység négyzet volt ugyanaz a kardinalitás, mint \(\mathbb{R}\) magát, és költözött, hogy előre a következő 1878-ban.

sejtés (a Kontinuumhipotézis)

a \(\mathbb{R}\) minden megszámlálhatatlan részhalmaza ugyanolyan kardinalitással rendelkezik, mint a \(\mathbb{R}\).

Cantor nem tudta bizonyítani vagy megcáfolni ezt a sejtést (minden más matematikussal együtt). Tény, hogy bizonyítani vagy cáfolni ezt a sejtést, amely nevezte a kontinuum hipotézis volt az egyik Hilbert híres \(23\) problémák bemutatott kihívás, hogy a matematikusok a Nemzetközi Matematikai Kongresszus 1900-ban.

mivel \(\mathbb{R}\) ugyanolyan kardinalitással rendelkezik, mint \(P (N)\), akkor a kontinuum hipotézist általánosítottuk a:

sejtés (az általánosított Kontinuumhipotézis)

adott végtelen halmaz \(S\), nincs olyan végtelen halmaz, amelynek kardinalitása szigorúan \(S\) és \(P(S)\) hatványhalmaza között van.

ennek bizonyítására vagy megcáfolására tett erőfeszítések hiábavalók voltak és jó okkal. 1940-ben a logikus Kurt G. D. D. D. kimutatta, hogy a kontinuum hipotézist nem lehet megcáfolni a Zermelo-Fraenkel axiómák halmazelmélet 1. 1963-ban Paul Cohen megmutatta, hogy a kontinuum hipotézist nem lehet bizonyítani a Zermelo-Fraenkel axiómák. Más szavakkal, a Zermelo-Fraenkel axiómák nem tartalmaznak elegendő információt a hipotézis igazságának eldöntéséhez.

hajlandóak vagyunk fogadni, hogy ezen a ponton a fejed kissé bizonytalanságban úszhat. Ha igen, akkor tudd, hogy ezek ugyanazok az érzések, amelyeket a matematikai közösség a huszadik század közepén tapasztalt. A múltban a matematikát a logikai bizonyosság modelljének tekintették. Nyugtalanító, hogy vannak olyan állítások, amelyek “eldönthetetlenek.”Tény, hogy G. D. D. D. 1931-ben bebizonyította, hogy egy konzisztens véges axióma rendszer, amely tartalmazza a számtani axiómákat, mindig tartalmaz eldönthetetlen állításokat, amelyek sem igaznak, sem hamisnak nem bizonyulhatnak ezekkel az axiómákkal. A matematikai ismeretek mindig hiányosak lennének.

 9.3.2.ábra.png

ábra \(\PageIndex{2}\): Kurt G Xhamdel

tehát azzal, hogy megpróbáljuk szilárd alapokra helyezni a számítás alapjait, eljutottunk arra a pontra, ahol soha nem nyerhetünk matematikai bizonyosságot. Ez azt jelenti, hogy fel kell dobnunk a kezünket, és el kell ismernünk a vereséget? Meg kell bénulnunk attól a félelemtől, hogy bármit megpróbálunk? Természetesen nem! Mint korábban említettük, a legtöbb matematikus pragmatikus megközelítéssel jár jól: matematikájával megoldja a felmerülő problémákat. Valójában általában a problémák motiválják a matematikát. Igaz, hogy a matematikusok olyan esélyeket vállalnak, amelyek nem mindig sikerülnek, de mégis vállalják ezeket az esélyeket, gyakran sikerrel. Még akkor is, ha a sikerek több kérdéshez vezetnek, mint általában, ezeknek a kérdéseknek a kezelése általában mélyebb megértéshez vezet. Legalábbis a hiányos megértésünk azt jelenti, hogy mindig több kérdésre kell válaszolnunk, több problémát kell megoldanunk.

mi mást kérhetne egy matematikus?