Lankide:Iirigoien/Cantorren teorema

{x, y, z} multzoaren kardinala edo kardinalitatea hiru da, eta bere potentzia-multzoan zortzi elementu daude (3 < 2³ = 8).

Cantor-en teorema, Georg Cantorrena, Zermo-Fränkel-en multzoen teorian formalizagarria den emaitza da:

Edozein A multzoren P(A) potentzia-multzoaren kardinala A multzoaren kardinala baino hertsiki handiagoa da.

Multzo finituetarako Cantorren teorema betezen dela ikus daiteke azpimultzo kopurua kontatuz. Multzo hutsa azpimultzo gisa hartuta, $n$ elementu dituen multzoak $2^{n}$azpimultzo ditu eta beraz, teoremak dioena egiazkoa da, $2^{n}>n$ delako zenbaki arruntetarako.

Cantorren teorema ordea askoz esanguratsuagoa bilakatzen da edozein multzori aplika dakiokeela erreparatuz, bai eta multzo infinituei ere. Cantorrek frogatu zuen zenbaki errealen multzoaren kardinalitatea zenbaki arrunten potentzia-multzoaren berdina dela eta ondorioz, zenbaki arrunten kardinalitatea baino hertsiki handiagoa dela. Zenbaki errealen kardinalitateari "jarraitasunaren kardinalitatea" esaten zaio.

Teoremak Georg Cantor matematikari alemaniarraren izena du, XIX. mendearen amaieran planteatu eta erakutsi zuen lehen aldiz. Cantorren teoremak berehala ondorio garrantzitsuak izan zituen matematikaren filosofian. Adibidez, multzo infinitu baten potentzia-multzoa modu iteratiboan hartuz eta Cantorren teorema aplikatuz, kardinal infinituen hierarkia infinitu bat lortzen dugu, kardinal bakoitza aurrekoa baino hertsiki handiagoa delarik. Honela, kardinal handiena ez dela existitzen ondorioztatzen da (azkar esanda, "ez dago handiena den infiniturik").

Eztabaida

Multzo finituetarako berehalakoa da Cantorren teorema: multzo finitu batek n elementu baditu, multzo horren potentzia multzoak 2ⁿ elementu ditu eta nabaria da 2ⁿ > n dela, teoremak dion bezala. Multzo infinituetarako ere egiazkoa izatea ez da guztiz intuitiboa. Cantorrek multzo infinituen kardinalari trasfinitua deitu zien eta multzo hauetarako zenbait emaitza interesgarri ezartzeko aukera ematen du teoremak.

• Kardinal transfinitu ugari dago, eta horrek esan nahi du, berez, infinitu mota asko daudela (izan ere infinito), bakoitza aurrekoa baino handiagoa. A priori emaitza hori ez da oso intuitiboa, baina oso garrantzitsua da matematikaren oinarrietan.
• Ez dago $\mathbb {N}$ zenbaki arrunten multzokoazpimultzo guztiak zerrendatzeko modurik.

Frogapena

Har dezagun edozein $f:A\to {\mathcal {P}}(A)$ funtzio, non ${\mathcal {P}}(A)$ A-ren parteen-multzoa edo potentzia-multzoa den. Cantorren teoremak potentzia-multzoaren kardinala jatorrizko multzoarena baino hertsiki handiagoa dela dio, beste era batera esanda f ez dela supraiektiboa.

F ez dela supraiektiboa frogatzeko, Aren azpimultzo bat topatu behar da (${\mathcal {P}}(A)$ multzoko elementua alegia) ez dena Aren elementu baten irudia f funtziorako. Horretarako Cantorrek B azpimultzo partikular bat hartu zuen, honela definitua:

$B=\left\{\,x\in A:x\not \in f(x)\,\right\}.$

Azpimultzo hori ezin dela Ako elementu baten irudia izan frogatu zuen. Horretarako absurdo bidezko froga egin zuen.

Demagun badela $a\in A:B=f(a)$ elementua. Orain, bi egoera gerta daitezke, $a\in B$ ala $a\notin B$:

1. Baldin eta $a\in B$ bada, orduan, B definitu den moduagatik $a\notin B$ behar du eta beraz, kontraesanera iritsi gara.
2. Baldin eta $a\notin B$ bada, orduan, B definitu den moduagatik $a\in B$ eta berriro ere kontraesanera iritsi gara.

Hau da, edonola ere kontraesan batera iritsi garenez, ez da existitzen $a\in A$ elementua, B multzoaren aurreirudia dena. Eta beraz, f funtzioa ez dela supraiektiboa frogatuta da.

Aren kardinala infinitu zenbakigarria denean

Azter dezagun nolako den egin berri dugun frogapena $A$ multzoa infinitu zenbakigarria denean. Orokortasunik galdu gabe, $A=\mathbb {N} =\{1,2,3,\dots \}$ zenbaki arrunten multzoa har daiteke.

${\mathcal {P}}(\mathbb {N} )$ potentzia-multzoak zenbaki arruntekin osatutako infinitu azpimultzo biltzen ditu. Bertan dago adibidez zenbaki bikoitien multzoa ({2, 4, 6,...}) baita multzo hutsa ere. Bere itxura honelako zerbait izango da:

${\mathcal {P}}(\mathbb {N} )=\{\varnothing ,\{1,2\},\{1,2,3\},\{4\},\{1,5\},\{3,4,6\},\{2,4,6,\dots \},\dots \}.$

Aurreko frogapenari helduz, demagun $\mathbb {N}$ eta bere potentzia-multzoa ${\mathcal {P}}(\mathbb {N} )$ multzo ekipotenteak direla onartzen dugula une batez, berriro ere absurdo bidezko froga egiteko.

Saia gaitezen $\mathbb {N}$ko elementu bakoitza ${\mathcal {P}}(\mathbb {N} )$ko beste elementu batekin lotzen. Bi multzoak ekipotenteak badira, multzo bakoitzeko elementu bakoitza beste multzoko elementu bakarrarekin lotu ahalko dugu. Adibidez, honelako zerbait:

$\mathbb {N} {\begin{Bmatrix}1&\longleftrightarrow &\{4,5\}\\2&\longleftrightarrow &\{1,2,3\}\\3&\longleftrightarrow &\{4,5,6\}\\4&\longleftrightarrow &\{1,3,5\}\\\vdots &\vdots &\vdots \end{Bmatrix}}{\mathcal {P}}(\mathbb {N} ).$

Ezarritako lotura horietan zenbaki arrunt batzuk zenbakia bera barneratzen duten azpimultzoekin lotuta daudela ikus daiteke. Adibidez, 2 zenbaki arrunta bera barneratzen duen {1, 2, 3} azpimultzoarekin lotuta dago. Dei diezaiegun zenbaki horiei berekoi. Beste zenbaki arrunt batzuk, bera barneratzen ez duten azpimultzoekin lotuta daude. Adibidez 1 zenbakia {4, 5} azpimultzoarekin lotuta dago eta azpimultzo horrek ez du 1 zenbakia barneratzen. Zenbaki horiei ez berekoi deituko diegu. Era berean, 3 eta 4 zenbakiak ez dira berekoiak.

Ideia horiek erabiliko ditugu absurdo bidezko froga honetan kontraesana emango digun multzoa definitzeko. Izan bedi B multzoa, zenbaki ez berekoi guztiez osatuta dagoena. Definizioz, ${\mathcal {P}}(\mathbb {N} )$ potentzia-multzoak zenbaki arrunten multzo guztiak ditu, eta, beraz, B multzo hori ere badu elementu gisa. $\mathbb {N}$ eta ${\mathcal {P}}(\mathbb {N} )$ren artean ezarritako lotura funtzioa bijektiboa bada, B zenbaki arrunt batekin lotu ahalko da, adibidez b zenbakiarekin. Baina horrek arazo bat sortzen du: baldin eta $b\in B$ badago, orduan b berekoia da definizioa, loturiko multzoan dagoelako; baina horrek, eta horrek B multzoaren definizioa kontrajartzen du. Baldin eta $b\notin B$, orduan ez berekoia da eta definizioz Bko kide izan beharko luke. Beraz, ez dago modurik B multzoarekin lotuta dagoen b zenbaki arruntik topatzeko.

Brekin lotuta dagoen zenbaki arruntik ez dagoenez, $\mathbb {N}$ eta ${\mathcal {P}}(\mathbb {N} )$ren artean bijekzio bat bazenaren gure hasierako usteak kontraesanara garamatza.

Kontraesanera iritsi gara B multzoan elementuak bazeudela pentsatu dugulako, B multzoa ordea hutsik egon daiteke. Horrela balitz, x zenbaki arrunt bakoitza, bera barneratzen duen zenbaki arrunten azpimultzo batekin lotuko litzateke. Orduan, zenbaki arrunt bakoitza hutsik ez dagoen azpimultzo bati lotuko litzaioke eta horrek $\varnothing \in {\mathcal {P}}(\mathbb {N} )$ multzo hutsari lotzeko zenbaki arruntik gabe utziko gintuzke, berriro ere ${\mathcal {P}}(\mathbb {N} )$ko elementu guztiak estaltzeko lotura bijektiborik ez dela posible erakutsiz.

Absurduaren bidezko froga honekin $\mathbb {N}$ eta ${\mathcal {P}}(\mathbb {N} )$ren kardinalak ezin direla berdinak izan frogatu dugu. Gainera, $\mathbb {N}$ren kardinala ezin da ${\mathcal {P}}(\mathbb {N} )$rena baino txikiagoa izan ale bakarreko multzo guztiak barneratzen dituelako, nolabait $\mathbb {N}$ren kopia bat ${\mathcal {P}}(\mathbb {N} )$ multzoan txertatuz. Beraz, ${\mathcal {P}}(\mathbb {N} )$ren kardinala $\mathbb {N}$rena baino hertsiki handiagoa izatea beste aukerarik ez dago, Cantorren teorema frogatuz.

• Cantor-Bernstein-Schröder-en teorema
• Zermiomo-Fraenkel axiomak