Articles

9.3: Cantor’ s Theorem and Its Consequences

färdigheter att utveckla

  • förklara Cantor ’ s theorem

när Cantor visade att det fanns två typer av oändlighet (räknbar och oräknelig) var följande fråga naturlig, ”har alla otaliga uppsättningar samma kardinalitet?”

precis som inte alla” icke-hundar ” är katter, finns det ingen anledning att tro att alla otaliga uppsättningar ska vara lika stora. Men att bygga otaliga uppsättningar av olika storlekar är inte så lätt som det låter.

till exempel,hur är det med linjesegmentet representerat av intervallet \(\) och torget representerat av uppsättningen \ (POV = \{(x,y)|0 x, x, x 1\}\). Visst måste den tvådimensionella kvadraten vara en större oändlig uppsättning än det endimensionella linjesegmentet. Anmärkningsvärt visade Cantor att dessa två uppsättningar var samma kardinalitet. I sin korrespondens från 1877 av detta resultat till sin vän och matematiker, Richard Dedekind, påpekade även Cantor: ”jag ser det, men jag tror inte på det!”

fig 9.3.1.png

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

följande ger den ursprungliga tanken på Cantors bevis. Cantor utarbetade följande funktion \(f: AC / s \). För det första representerar vi koordinaterna för vilken punkt som helst \((x,y) db\) med deras decimalrepresentationer \(x = 0.a_1a_2a_3 …\ ) och \(y = 0.b_1b_2b_3….\ ) Även avslutande decimaler kan skrivas på detta sätt som vi kunde skriva \(0.5 = 0.5000….\ ) Vi kan sedan definiera \(f (x, y)\) av

\

denna relativt enkla IDE har några tekniska svårigheter i det relaterade till följande resultat.

övning \(\Sidaindex{1}\)

Tänk på sekvensen \((0.9,0.99,0.999,…)\). Bestäm att denna sekvens konvergerar och faktiskt konvergerar till \(1\). Detta tyder på att \(0.999… = 1\).

på samma sätt har vi \(0.04999… = 0.05000…\), osv. För att göra decimalrepresentationen av ett reellt tal i \(\) unikt måste vi göra ett konsekvent val att skriva en avslutande decimal som en som slutar i en oändlig sträng av nollor eller en oändlig sträng av nior . Oavsett vilket val vi gör, vi kunde aldrig göra denna funktion på. Till exempel \(109/1100 = 0,09909090…\ ) skulle ha som sin förbild \((0.0999…,0.9000…)\) vilket skulle vara en blandning av de två konventionerna.

Cantor kunde övervinna denna teknikalitet för att demonstrera en en-till-en-korrespondens, men i stället kommer vi att notera att i endera konventionen är funktionen en-till-en, så det här säger att uppsättningen \ (xhamster\) är samma kardinalitet som någon (oräknelig) delmängd av \(\mathbb{R}\). Det faktum att detta har samma kardinalitet som \(\mathbb{R}\) är något vi kommer tillbaka till. Men först ska vi försöka konstruera en oräknelig uppsättning som inte har samma kardinalitet som \(\mathbb{R}\). För att ta itu med denna fråga bevisade Cantor följande 1891.

Sats \(\PageIndex{1}\): Cantor ’ s Theorem

Låt \(s\) vara vilken uppsättning som helst. Då finns det ingen en-till-en-korrespondens mellan \(S\) och \(P(S)\), uppsättningen av alla delmängder av \(S\).

eftersom \(S\) kan sättas i en-till-en-korrespondens med en delmängd av \(P (s) (a{a\})\), säger detta att\ (P(S)\) är minst lika stor som\ (s\). I det ändliga fallet \(|P (S)|\) är strängt större än \(|S/\) som följande problem visar. Det visar också varför \(P(S)\) kallas effektuppsättningen av \(S\).

Övning \(\Sidaindex{2}\)

Bevisa: Om \(|S | = n\), sedan \(|P(s) / = 2n\)

tips

Låt \(S = a_1, a_2, …, a_n\). Tänk på följande korrespondens mellan elementen i \(P (S)\) och uppsättningen \(T\) av alla \(n\) – tuples av ja (\(Y\)) eller nej (\(N\)):

\

hur många element finns i \(T\)?

övning \(\PageIndex{3}\)

bevisa Cantors Sats.

antydan

Antag för motsägelse, att det finns en en-till-en korrespondens \(F : S Bisexuell P(S)\). Tänk på \(A = \{x c|x \Inte {C} f (x)\}\). Eftersom \(f\) är på, då finns det \(en pov a\) sådan att \(A = f(A)\). Är \ (a xnumx a\) eller är \(A \inte {xnumx} A\)?

det visar sig faktiskt att \(\mathbb{R}\) och \(P(\mathbb{N})\) har samma kardinalitet. Detta kan ses i en rondell med hjälp av några av ovanstående tankar från övning \(\PageIndex{2}\). Låt \(T\) vara uppsättningen av alla sekvenser av nollor eller sådana (Du kan använda \(Y\)S eller \(N\)s, om du föredrar). Då är det enkelt att se att \(T\) och \(P(\mathbb{N})\) har samma kardinalitet.

om vi betraktar \((0,1]\), som har samma kardinalitet som \(\mathbb{R}\), kan vi se att detta har samma kardinalitet som \(T\) också. Specifikt, om vi tänker på siffrorna i binärt, kan varje reellt tal i \ ( \ ) skrivas som \(\sum_{j=1}^{\infty } \frac{a_j}{2^j} = (a_1, a_2, \cdots)\) där \(a_j brasilian \{0,1\}\). Vi måste redogöra för det faktum att binära representationer som \(0.0111…\ ) och \(0.1000…\ ) representerar samma reella tal (säg att inga representationer kommer att sluta i en oändlig sträng nollor), då kan vi se att \(\) har samma kardinalitet som \(t – U\), där \(U\) är uppsättningen av alla sekvenser som slutar i en oändlig sträng nollor. Det visar sig att \(U\) i sig är en räknbar uppsättning.

övning \(\Sidaindex{4}\)

låt \(U_n = \ {(a_1, a_2, a_3,…) / a_j 6 \ {0,1\}\) och \(a_{n + 1} = a_{n+2} = ··· = 0\}\). Visa att för varje \(n\) är \(U_n\) ändlig och använd detta för att dra slutsatsen att \(U\) är oändligt oändligt.

följande två problem visar att radering av en räknbar uppsättning från en oräknelig uppsättning inte ändrar dess kardinalitet.

övning \(\Sidaindex{5}\)

Låt \(S\) vara en oändlig uppsättning. Bevisa att \(S\) innehåller en countably oändlig delmängd.

övning \(\PageIndex{6}\)

Antag att \(X\) är en oräknelig uppsättning och \(Y 2b X\) är oändligt oändligt. Bevisa att \(X\) och \(X – Y\) har samma kardinalitet.

Tips

Låt \(Y = Y_0\). Om \(X-Y_0\) är en oändlig uppsättning, innehåller den av det föregående problemet en oändligt oändlig uppsättning \(Y_1\). På samma sätt om \(X – (Y_0 Bisexuell Y_1)\) är oändlig innehåller den också en oändlig uppsättning \(Y_2\). Återigen, om \(X – (Y_0 megapixlar Y_1 megapixlar Y_2)\) är en oändlig uppsättning så innehåller den en oändlig uppsättning \(Y_3\), etc. För \(n = 1,2,3,…,\) let \ (f_n: y_{n-1} bisexuell y_n\) vara en en-till-en-korrespondens och definiera \(f: X Bisexuell X-Y\) av

\

visa att \(f\) är en-till-en och på.

ovanstående problem säger att \(R\), \(T – U\), \(T\) och \(P(N)\) alla har samma kardinalitet.

som angivits tidigare hade Cantors arbete med oändliga uppsättningar en djupgående inverkan på matematiken i början av tjugonde århundradet. Till exempel, när han undersökte beviset på Cantors teorem, tänkte den framstående logikern Bertrand Russell sin berömda paradox 1901. Före denna tid, en uppsättning var naivt tänkt som bara en samling av objekt. Genom arbetet med Cantor och andra, uppsättningar blev ett centralt studieobjekt i matematik eftersom många matematiska begrepp omformulerades i termer av uppsättningar. Tanken var att uppsättningsteori skulle vara ett förenande tema för matematik. Denna paradox satte den matematiska världen på örat.

Russells Paradox

Tänk på uppsättningen av alla uppsättningar som inte är delar av sig själva. Vi kallar den här uppsättningen \(D\) och frågar, ”Är \(D Xiaomi D\)?”Symboliskt är denna uppsättning

\

om\ (D IC D\), Sedan per definition, \(D \inte {IC} d\). Om D 6 oc D, då per definition, \(D Oc D D\).

om du tittar tillbaka på beviset på Cantors teorem var det i grunden tanken som gav oss motsägelsen. Att ha en sådan motsägelse som inträffade på matematikens mest grundläggande nivå var skandalös. Det tvingade ett antal matematiker och logiker att noggrant utforma axiomerna genom vilka uppsättningar kunde konstrueras. För att vara ärlig, de flesta matematiker fortfarande närmar set teori från en naiv synvinkel som de uppsättningar vi brukar ta itu med faller under kategorin av vad vi skulle kalla ”normala uppsättningar.”I själva verket kallas ett sådant tillvägagångssätt officiellt naiv uppsättningsteori (i motsats till axiomatisk uppsättningsteori). Men försök att sätta uppsättningsteori och logik på solid grund ledde till den moderna studien av symbolisk logik och i slutändan utformningen av dator (maskin) logik.

en annan plats där Cantors arbete hade ett djupt inflytande i modern logik kommer från något vi hänvisade till tidigare. Vi visade tidigare att enhetskvadrat \ (Xiaomi\) hade samma kardinalitet som en oräknelig delmängd av \(\mathbb{R}\). Faktum är att Cantor visade att enhetstorget hade samma kardinalitet som \(\mathbb{R}\) själv och flyttades för att främja följande 1878.

Conjecture (kontinuumhypotesen)

varje otalbar delmängd av \(\mathbb{R}\) har samma kardinalitet som \(\mathbb{R}\).

Cantor kunde inte bevisa eller motbevisa denna gissning (tillsammans med alla andra matematiker). Att bevisa eller motbevisa denna gissning, som kallades kontinuumhypotesen, var faktiskt ett av Hilberts berömda\ (23\) problem som presenterades som en utmaning för matematiker vid International Congress of Mathematicians 1900.

eftersom \(\mathbb{R}\) har samma kardinalitet som \(P (N)\), generaliserades kontinuumhypotesen till:

gissning(den generaliserade kontinuumhypotesen)

givet en oändlig uppsättning \(S\) finns det ingen oändlig uppsättning som har en kardinalitet strikt mellan den av \(S\) och dess effektuppsättning \(P (s)\).

försök att bevisa eller motbevisa detta var förgäves och med goda skäl. År 1940 visade logikern Kurt g Sackaridel att kontinuumhypotesen inte kunde motbevisas från Zermelo-Fraenkel Axiom av setteori 1. 1963 visade Paul Cohen att kontinuumhypotesen inte kunde bevisas med hjälp av Zermelo-Fraenkel Axiom. Med andra ord innehåller Zermelo-Fraenkel-axiomerna inte tillräckligt med information för att bestämma hypotesens sanning.

vi är villiga att satsa på att just nu kan ditt huvud simma lite med osäkerhet. Om så är fallet, vet då att det här är samma känslor som det matematiska samhället upplevde i mitten av det tjugonde århundradet. Tidigare sågs matematik som en modell för logisk säkerhet. Det är oroande att finna att det finns uttalanden som är ”osäkra.”I själva verket bevisade g Xhamster 1931 att ett konsekvent ändligt axiomsystem som innehöll aritmetiska axiomer alltid skulle innehålla obestridliga uttalanden som varken kunde bevisas sanna eller falska med dessa axiomer. Matematisk kunskap skulle alltid vara ofullständig.

 fig 9.3.2.png

Figure \(\PageIndex{2}\): Kurt g Aubbidel

så genom att försöka sätta grunden för kalkylen på fast mark har vi kommit till en punkt där vi aldrig kan få matematisk säkerhet. Betyder det att vi ska kasta upp våra händer och erkänna nederlag? Ska vi bli förlamade av rädsla för att försöka någonting? Absolut inte! Som vi nämnde tidigare gör de flesta matematiker bra genom att ta ett pragmatiskt tillvägagångssätt: använda sin matematik för att lösa problem som de stöter på. I själva verket är det vanligtvis problemen som motiverar matematiken. Det är sant att matematiker tar chanser som inte alltid panorerar ut, men de tar fortfarande dessa chanser, ofta med framgång. Även när framgångarna leder till fler frågor, som de vanligtvis gör, att ta itu med dessa frågor leder vanligtvis till en djupare förståelse. Åtminstone innebär vår ofullständiga förståelse att vi alltid kommer att ha fler frågor att svara på, fler problem att lösa.

vad mer kan en matematiker begära?