Cantor-paradoxon

A Wikipédiából, a szabad enciklopédiából

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[szerkesztés | forrásszöveg szerkesztése]

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, amit 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[szerkesztés | forrásszöveg szerkesztése]

Modern bizonyítás[szerkesztés | forrásszöveg szerkesztése]

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})|\le |\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[szerkesztés | forrásszöveg szerkesztése]

Az eredeti Cantor-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 f1, 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, f1, .
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. [1]
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 megfeletethető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, … ω0, ω0+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 fogalalja, 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 abc utolsó betüje a ת jelöli az összes alephek rendszerét.
Ugyannak 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 γ0, és egy γ1 amelyik nincs benne a Z(c)-ben, így
γ0γγ1
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 ω0 a legkisebb transzfinit szám és a neki megfelelő aleph pedig 0
0=|ω0|
0 a legkisebb aleph és a
Z(א0) = Ω0
számosság osztályt határozza meg.
A Z(ℵ0) α számainak elégséges és szükséges feltétele, hogy teljesítsék
ω0αω1
feltételt,ahol ω1 a legkisebb transzfinit szám amelyiknek a kardinális száma nem azonos az 0-lal.
|ω1| = 1
nem csak különbözik az 0-tól, de egyben nagyságrend szerinti rákövetkezője. Ezzel hozzájutunk az
Ω1 = Z(ℵ1)
számosság osztályhoz. Ebbe a számosság osztályba tartoznak azok a β számok, amelyek kielégítik a
ω1βω2
feltételt, ahol ω2 a legkisebb transzfinit szám amelyiknek a kardinális száma nem azonos az 0-val sem az 1-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ágrendszerint 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ágyaztható 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.[2]

Az ellentmondás kiküszöbölése[szerkesztés | forrásszöveg szerkesztése]

Zermelo–Fraenkel-halmazelméletben[szerkesztés | forrásszöveg szerkesztése]

„…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[3]

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.[4]

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

Neumann–Bernays–Gödel-halmazelméletben[szerkesztés | forrásszöveg szerkesztése]

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

  1. Ruzsa Imre jegyzete, Georg Cantor: Végtelenség a matematikában és a filozófiában: válogatott szemelvények. Filozófiai Figyelő 1988/4-ben
  2. Ernst Zermelo: Untersuchungen über die Grundlagen der Mengenlehre I. Mathematische Annalen 65(1908), 261-281.o.
  3. Zermelo [1908b], 202. old.
  4. Stanford Encyclopedia of Philosophy:Set Theory -- by Thomas Jech

Források[szerkesztés | forrásszöveg szerkesztése]

  • 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.