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
szerkesztésA 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
szerkesztésModern bizonyítás
szerkesztésAz 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. ■
Eredeti bizonyítás
szerkesztésAz 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 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 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.
- 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 γ0 és egy γ1, 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 ω0 a legkisebb transzfinit szám és a neki megfelelő aleph pedig ℵ0
- ℵ0 a legkisebb aleph és a
- 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
- feltételt, ahol ω1 a legkisebb transzfinit szám amelyiknek a kardinális száma nem azonos az ℵ0-lal.
- 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
- 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.
- É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.[2]
Az ellentmondás kiküszöbölése
szerkesztésZermelo–Fraenkel-halmazelméletben
szerkesztés„…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))]
Hivatkozások
szerkesztés- ↑ 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
- ↑ Ernst Zermelo: Untersuchungen über die Grundlagen der Mengenlehre I. Mathematische Annalen 65(1908), 261-281. o.
- ↑ Zermelo [1908b], 202. old.
- ↑ Stanford Encyclopedia of Philosophy:Set Theory -- by Thomas Jech
Források
szerkesztés- 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.