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

Tartalomjegyzék 1 Történeti áttekintés 2 Az ellentmondás bizonyításai 2.1 Modern bizonyítás 2.2 Eredeti bizonyítás 3 Az ellentmondás kiküszöbölése 3.1 Zermelo–Fraenkel-halmazelméletben 3.2 Neumann–Bernays–Gödel-halmazelméletben 4 Hivatkozások 5 Források

[szerkesztés] Történeti áttekintés

A paradoxon felbukkanását az a cantori elv okozta, hogy „jóldefiniált objektumok bármely összessége halmazt alkot”; de áltálában a felfedezését is Georg Cantornak tulajdonítják, mivel 1899. július 28-án Dedekindhez írt levelében került először említésre. 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.

[szerkesztés] Az ellentmondás bizonyításai

[szerkesztés] 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 halmaz, akkor

– ahol a halmaz hatványhalmaza, pedig a számossága.

Legyen az összes halmazok halmaza. Ekkor Cantor tétele szerint

(vagyis létezik injekció). Mivel maga és minden eleme is halmaz, ebből következik, hogy , vagyis hogy (tehát 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. ■

[szerkesztés] Eredeti bizonyítás

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 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. ^[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, ... ω₀, , ω₀₊₁, , ..., γ, ...

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”. Nyílvá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.

Nyílvá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]

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

[szerkesztés] 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[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))]

[szerkesztés] Neumann–Bernays–Gödel-halmazelméletben

[szerkesztés] Hivatkozások

[szerkesztés] 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.