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 ${\mathcal {P}}(A)$ potentzia-multzoaren kardinala $A$ multzoaren kardinala baino hertsiki handiagoa da.

Multzo finituetarako Cantorren teorema betetzen dela erraz 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 kardinala zenbaki arrunten potentzia-multzoaren berdina dela eta ondorioz, zenbaki arrunten kardinala baino hertsiki handiagoa dela. Zenbaki errealen kardinalari "jarraitasunaren kardinalitatea" esaten zaio.

Georg Cantor matematikari alemaniarraren izena du teoremak. Cantorrek XIX. mendearen amaieran planteatu eta erakutsi zuen lehen aldiz teorema. 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 dagoela (izan ere infinitu), bakoitza aurrekoa baino handiagoa. A priori emaitza hori ez da oso intuitiboa, baina oso garrantzitsua da matematikaren oinarrietan.
• Ez dago $\mathbb {N}$ zenbaki arrunten multzoko azpimultzo guztiak zerrendatzeko modurik.

Frogapena

$A$ multzoaren kardinala $B$ multzoaren kardinala baino hertsiko txikiagoa dela frogatzeko, frogatu behar da badela $g:A\to B$ funtzio injektiboa baina ez dela existitzen bi multzoen arteko funtzio bijektiborik. Beste era batera esanik, ez dela existitzen $B$tik $A$rako funtzio supraiektiborik.

Gure kasura etorriz, har dezagun edozein $f:A\to {\mathcal {P}}(A)$ funtzioa, 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, $A$ren azpimultzo bat topatu behar da (${\mathcal {P}}(A)$ multzoko elementu bat alegia) ez dena $A$ko 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 $A$ko elementu baten irudia izan frogatu zuen. Horretarako absurdo bidezko froga egin zuen honela.

Demagun badela $a\in A:B=f(a)$ elementua. Orain, bi aukera daude, $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. Frogapena amaitzeko, $g:A\to {\mathcal {P}}(A)$ funtzio injektibo bat topatu behar dugu. Kasu honetan erraza da, izan ere ${\displaystyle g(x)=\{x\}}$ identitate-funtzioak, $x$ elementua bera bakarrik biltzen duen $\{x\}$ multzora eramaten duen funtzioa injektiboa baita.

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 ($\varnothing$) 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 definizioz, loturiko multzoan dagoelako; baina horrek $B$ multzoaren definizioa kontrajartzen du. Baldin eta $b\notin B$, orduan ez berekoia da eta definizioz $B$ko kide izan beharko luke. Beraz, ez dago modurik $B$ multzoarekin lotuta dagoen $b$ zenbaki arruntik topatzeko.

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

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. Beste era batera esanda, $n\mapsto \{n\}$ funtzioa bijektiboa da. Beraz, ${\mathcal {P}}(\mathbb {N} )$ren kardinala $\mathbb {N}$rena baino hertsiki handiagoa izatea beste aukerarik ez dago, Cantorren teorema frogatuz.

Kanpo estekak

• Wang, H. (2011). Ehun urte logika matematikoan. Gogoa, 6(1). https://doi.org/10.1387/gogoa.4005 (itzulpena)

• Datuak: Q474881
• Multimedia: Cantor's theorem / Q474881