Cantor-paradoxon

A Cantor-paradoxon egy ellentmondás a naiv halmazelméletben, amely abból származik, hogy megengedett a legnagyobb számosságú (vagy kardinális számú) halmaz (például az univerzális halmaz) létezése. Az ellentmondás abban áll, hogy a legnagyobb számosságú halmaznak több részhalmaza van, mint eleme, így nem is lehet legnagyobb számosságú.

Történeti áttekintés

A paradoxon felbukkanását az a cantori elv okozta, hogy a „jól definiált objektumok bármely összessége halmazt alkot”; de általában a felfedezését is Georg Cantornak tulajdonítják, mivel 1899. július 28-án Dedekindhez írt levelében ő említette először. A levélben arról ír, hogy meg kell különböztetni kétféle sokaságot: „inkonzisztens” és „konzisztens” sokaságokat. A különbség köztük az, hogy az inkonzisztens sokaságok „nem lehetnek elemei semmiféle sokaságnak”. Az inkonzisztens sokaságokat „abszolút végtelennek” is nevezi; ezek állnak a számossági hierarchia csúcsán. A levélben „az összes számok Ω rendszeréről” mutatja meg, hogy „inkonzisztens”, jólrendezett, illetve „abszolút végtelen”; és ennek belátásához használja fel azt az ellentmondást, amelyet azóta Cantor-paradoxonnak hívunk.

A későbbi osztályrealista halmazelméletekben a cantori inkonzisztens sokaságokat valódi osztályoknak hívják, a konzisztens sokaságokat pedig halmazoknak. A Zermelo-Fraenkel halmazelmélet és rokonai csak konzisztens sokaságokat engednek meg változóik értékei között.

A naiv halmazelmélet két másik fontos ellentmondását, a Burali-Forti-paradoxont és a Russell-paradoxont 1897-ben, illetve 1901-ben fedezték fel névadóik.

Az ellentmondás bizonyításai

Modern bizonyítás

Az ellentmondás belátásához két tételre van szükség. Az egyik a (Cantor–) Schröder–Bernstein-tétel, amely szerint ha A és B tetszőleges halmazok között kölcsönösen létezik injektív leképezés, akkor bijektív leképezés is van köztük, vagyis A és B ekvivalens egymással. A másik szükséges tétel a Cantor-tétel, amely azt állítja, hogy ha $\scriptstyle {H}$ halmaz, akkor

$|H|<|{\mathcal {P}}(H)|$

– ahol $\scriptstyle {{\mathcal {P}}(H)}$ a $\scriptstyle {H}$ halmaz hatványhalmaza, $\scriptstyle {|H|}$ pedig a számossága.

Legyen $\scriptstyle {\mathrm {V} }$ az összes halmazok halmaza. Ekkor Cantor tétele szerint

$|\mathrm {V} |<|{\mathcal {P}}(\mathrm {V} )|$

(vagyis létezik $\scriptstyle {\mathrm {V} \rightarrow {\mathcal {P}}(\mathrm {V} )}$ injekció). Mivel $\scriptstyle {{\mathcal {P}}(\mathrm {V} )}$ maga és minden eleme is halmaz, ebből következik, hogy $\scriptstyle {{\mathcal {P}}(\mathrm {V} )\subseteq \mathrm {V} }$, vagyis hogy $\scriptstyle {|{\mathcal {P}}(\mathrm {V} )|\leq |\mathrm {V} |}$ (tehát $\scriptstyle {{\mathcal {P}}(\mathrm {V} )\rightarrow \mathrm {V} }$ is injektív leképezés, így a Schröder–Bernstein-tétel szerint ekvivalens egymással a halmaz és hatványhalmaza). Ez ellentmondás. ■

Eredeti bizonyítás

Az eredeti Cantor-féle bizonyításhoz szükséges néhány definíció és tétel a jólrendezett halmazokról.

a) Két ekvivalens sokaság vagy egyaránt “halmaz”, vagy egyaránt inkonzisztens sokaság.

b) Halmaz minden részsokasága is halmaz.

c) Jólrendezettnek mondjuk az egyszerűen rendezett F halmazt, ha elemei a legkisebb f₁, elemtől kezdve egy meghatározott rákövetkezés szerint növekednek, mely eleget tesz a következő két feltételnek:

I. Van F-nek egy rangban legalacsonyabb eleme, f₁, .

II. Ha F’ részhalmaza F-nek, és F-nek van egy vagy több olyan eleme, melyek rangja magasabb, mint F’ bármely eleméé, akkor létezik F-nek olyan f’ eleme, amely az F’ összességét közvetlenül követi, azaz nincs F-nek olyan eleme, amelyiknek a rangja F’ és f’ közé esne.

c') Egy szemléletesebb, de az eredetivel ekvivalens definíció: Egy halmaz lineáris –vagy egyszerű- rendezését (olyan rendezés, amely alaptulajdonságaiban megegyezik a számegyenes számainak nagyság szerinti rendezésével) jólrendezésnek mondjuk, ha a halmaz bármely nemüres részében van első (legalacsonyabb rangú) elem. Cantor “sorozatnak” nevezi az ilyen sokaságokat.

d) “Sorozat” minden része is “sorozat”.

e) Ha egy lineárisan rendezett sokaság ‘halmaz’, akkor a ‘típusa’ az az általános fogalom, amely alá csak ez a halmaz és a hozzá hasonlóan rendezett halmazok tartoznak. (Két lineárisan rendezett halmaz hasonló, ha kölcsönösen egyértelműen megfeleltethetőek egymásnak úgy, hogy a megfeleltetett elemek rangviszonya a két halmazban mindig ugyanaz.)

Cantor rendszámoknak hívja a jólrendezett halmazok típusait

Állítás: „Az összes számok Ω rendszere inkonzisztens, abszolút végtelen sokaság.”

Bizonyítás: Egy korábbi bizonyítás szerint, két különböző α és β szám közül az egyik mindig kisebb és a másik mindig nagyobb, valamint hogy három szám esetében, ha α<β, és β<γ, akkor α<γ is teljesül. Tehát Ω lineárisan rendezett rendszer.

És mivel számok tetszőleges sokasága, tehát Ω bármely része tartalmaz legkisebb számot; az Ω rendszer a természetes nagyság szerinti rendezéssel „sorozatot” alkot.

Kapcsoljuk ehhez a sokasághoz még a 0 elemet, mégpedig helyezzük az első helyre; így jutunk az Ω’ sorozathoz.

0, 1, 2, 3, … ω₀, ω₀+1, …, γ, …

Az itt előforduló bármely γ szám az őt megelőző elemek (a 0-t is beleértve) sorozatának típusa.

Ω’ nem lehet konzisztens sokaság (és ezért Ω sem): Ha Ω’ konzisztens lenne, akkor, mint jólrendezett halmazhoz egy δ számot rendelhetnénk hozzá, mely nagyobb lenne, mint az összes Ω-ban előforduló szám. Az Ω rendszerben azonban, tekintve, hogy ez az összes számot magába foglalja, a δ szám is előfordul. Tehát δ nagyobb lenne, mint δ, ami ellentmondás.

Mivel jól rendezett halmazok hasonlósága egyben az ekvivalenciájukat is jelenti, minden γ számhoz tartozik egy א(γ)=|γ| kardinális szám; összes olyan jól rendezett halmaz kardinális száma, amelynek típusa γ.

Az „aleph”ek azok a kardinális számok, amelyek ebben az értelemben az Ω rendszer transzfinit számainak felelnek meg, és a héber ábécé utolsó betűje a ת jelöli az összes alephek rendszerét.

Ugyanannak a c kardinális számnak megfelelő összes γ számok rendszerét hívjuk Z(c) „számosság osztálynak”. Nyilvánvaló, hogy minden számosság osztályban létezik egy legkisebb szám γ₀ és egy γ₁, amelyik nincs benne a Z(c)-ben, így

γ₀≤γ∠γ₁

ekvivalens azzal, hogy a γ szám a Z(c) számosság osztályba tartozik. Mivel minden szám összességnek, így Ω minden részsokaságának van egy legkisebb eleme, minden számosság osztály valójában az Ω sorozat egy része.

Az Ω rendszerbeli egyes számok önmagukban alkotnak egy számosság osztályt; ezek a véges számok 1, 2, 3, …., v, …, amelyek |1|, |2|, |3|, …, |v|, … véges kardinális számoknak felelnek meg.

Legyen a ω₀ a legkisebb transzfinit szám és a neki megfelelő aleph pedig ℵ₀

ℵ₀=|ω₀|

ℵ₀ a legkisebb aleph és a

Z(א₀) = Ω₀

számosság osztályt határozza meg.

A Z(ℵ₀) α számainak elégséges és szükséges feltétele, hogy teljesítsék

ω₀ ≤ α ∠ ω₁

feltételt, ahol ω₁ a legkisebb transzfinit szám amelyiknek a kardinális száma nem azonos az ℵ₀-lal.

|ω₁| = ℵ₁

nem csak különbözik az ℵ₀-tól, de egyben nagyságrend szerinti rákövetkezője. Ezzel hozzájutunk az Ω₁ = Z(ℵ₁)

számosság osztályhoz. Ebbe a számosság osztályba tartoznak azok a β számok, amelyek kielégítik a

ω₁ ≤ β ∠ ω₂

feltételt, ahol ω₂ a legkisebb transzfinit szám amelyiknek a kardinális száma nem azonos az ℵ₀-val sem az ℵ₁-gyel, és így tovább.

Az omega rendszer transzfinit számai közül, amelyeknek egyetlen ℵ_v (ahol v véges) sem felel meg megint van egy legkisebb, ω_ω0 , és ezzel egy új alephhez jutunk.

ℵ_ω0 = |ω_ω0|

És ez, az összes ℵ_v után következő legkisebb kardinális szám.

Nyilvánvaló, hogy ily módon az alephek és a nekik megfelelő Ω rendszerbeli számosság osztályok formálásának a folyamata teljesen határtalan.

Az alephek ת rendszere, nagyságrend szerint rendezve az Ω rendszerhez hasonló sorozatot, így az Ω rendszerhez hasonlóan inkonzisztens vagy abszolút végtelen sokaságot alkot.

Állítás: A ת rendszer tartalmazza az összes transzfinit kardinális számot.

Bizonyítás: Ha veszünk egy V sokaságot és feltesszük, hogy egyetlen aleph sem az ő kardinális száma, ezzel ahhoz jutunk el, hogy V inkonzisztens. Mivel ezzel azt tételezzük fel, hogy az egész Ω rendszer beágyazható a V sokaságba, vagyis van a V-nek olyan részsokasága V’ amelyik ekvivalens az Ω rendszerrel.

Mivel omega inkonzisztens V’ is az, és mivel V’ inkonzisztens a V is az.

Tehát minden transzfinit konzisztens sokaságnak, vagyis minden transzfinit halmaznak kardinális száma kell, hogy legyen egy határozott aleph szám. ■

A paradoxonok időben korai és egymáshoz közeli felfedezése rövid távon rontotta a cantori halmazelmélet helyzetét és megítélését, és a matematika második megalapozási válságához vezetett. Ennek ellenére hosszú távon erősítette a halmazelméletet és a matematika megalapozását; többek között azáltal, hogy Ernst Zermelo 1908-ban a halmazelmélet axiomatizálásával küszöbölte ki a paradoxonokat.

Az ellentmondás kiküszöbölése

Zermelo–Fraenkel-halmazelméletben

„…ezen axióma révén már nem lehet halmazokat önállóan definiálni, hanem adott halmazok részhalmazaiként kell őket elkülöníteni; így ki vannak zárva az olyan ellentmondásos fogalmak, mint ‘összes halmazok halmaza’, ‘összes számosságok halmaza’, és ezekkel együtt – Hessenberg szavaival élve – az »ultrafinit paradoxonok«.” -- Ernst Zermelo

Mivel az ellentmondásokat Cantor eredeti halmaz definíciója okozta, Ernst Zermelo a részhalmaz-axiómával (vagy elkülönítési-axiómával) korlátozta ’sokaságok’ halmazba való rendezését.

Részhalmaz axióma vagy elkülönítési axióma: Ha adott egy Φ formula és egy u halmaz; létezik egy v halmaz, melynek elemei pontosan azok az elemei u-nak, melyek eleget tesznek a Φ formulának.

Adott Φ formulára; ∀b∃a∀x[x∈a↔(x∈b&Φ(x))]

Források

• Georg Cantor: Végtelenség a matematikában és a filozófiában: válogatott szemelvények. Filozófiai Figyelő 1988/4.
• Justin T. Miller, An Historical Account of Set-Theoretic Antinomies Caused by the Axiom of Abstraction
• Michael Hallett: Cantorian set theory and limitation of size. Clarendon Press, Oxford, 1984.
• Ernst Zermelo: Investigations in the foundations of set theory, in: Jean van Heijenoort (szerk.): From Frege to Gödel, Harvard University Press, Cambridge (Massachusetts), 1967.