HANDOUT   

(pdf verzió: PDF)

 

Ez az írás a Ruzsa Imre emlékkonferencián 2009.09.18.-án elhangzott 20 perces előadásom (+10 perc hozzászólás), valamint az 5 nappal későbbi Filozófiai Szeminátriumon 2009.09.23.-án elhangzott 1 órás (+fél óra diszkusszió) előadásom alkalmával kiosztott Handout szövegével azonos, eltekintve néhány sajtóhiba javításától.

A teljes cikk itt található

A Filozófiai Szemináriumra beküldött absztraktot itt találod.

 

2010.10.02.: Iránytű az olvasáshoz

Ez az iránytű semmi újat nem állít a cikkben foglaltakhoz képest. Csak felhívja a figyelmet bizonyos dolgokra, melyek félreértelmezhetők, vagy elkerülhetik a felületes olvasó figyelmét.

A szerző az alábbi írásában és a teljes cikkben

- nem azt állítja, hogy a Cantot tétel nem igaz;

- azt sem állítja, hogy Cantort tételt nem lehet bizonyítani.

Azt állítja, és szándéka szerint korrekt matematikai gondolatmenettel be is bizonyította, hogy a tankönyvekben és kézikönyvekben fellelhető, Cantor eredeti gondolamenetével azonos, indirekt gondolamenetben egy "csúsztatás" van; valamit ott nem vettek figyelembe. A hiba (bizonyos formális előfeltevések alapján! - ld. alább) korrigálható, de az már egy másik bizonyítás lesz. Ezen (ti. a formális előfeltevések létjogosultságán) különféle filozófiai vitákat lehet folytatni. De nem matematikait.

A gondolatmenet lényegét a Tétel_2 utáni Következmény_2 mondja ki. Ld. még alul a diszkussziót.

 

Az eredeti handout, kiegészítésekkel:

 

Szemantikai értékrés Cantor édenkertjének égboltján - avagy mi az, amit megmentett Hilbert?

 

C: Geier János, 2009.09.18-24

Ld. még: http://www.geier.hu/Cantor/Cantor_rovid.htm

Az eredeti az kissé kiegészítve és sajtóhibák javítva. 2009.10.06, majd 2010.10.02.

A teljes cikkre mutató linkek betéve: 2010.09.27

 

Minden jog fenntartva. Ez az írás a szerző írásbeli beleegyezése nélkül nem másolható,
nem sokszorosítható, nem terjeszthető, sem részben, sem egészben.
Az oldal linkelhető.
Idézés esetén az irodalmi hivatkozások szabályainak betartása szigorú követelmény.

 

FIGYELEM:  Ez a lap a Microsoft Internet Explorerhez lett optimalizálva. Ha a matematikai - logikai jelek " Û   Ø  Î Ï  nem olvashatók, akkor nézd meg ezt a PDF  fájlt.

 

EZ A HANDOUT CSAK EGY KIEGÉSZÍTÉS VOLT AZ ELŐADÁSON, HISZEN A HALLGATÓSÁGTÓL NEM VÁRHATÓ EL, HOGY EGY RÖVID ELŐADÁSBAN A MATEMATIKAI  LEVEZETÉSEKET AZONNAL NYOMON TUDJA KÖVETNI.

EZ A HANDOUT TEHÁT CSEPPET SEM AZONOS A teljes cikk -KEL!  A teljes cikk  MONDANIVALÓJA JÓVAL BŐVEBB. 

KÉRLEK, OLVASD EL A teljes cikk   -ET IS!

 

A Cantor tétel

Tétel (Cantor hatványhalmaz tétele) Tetszőleges nemüres M halmaz nem ekvivalens a H=2M hatványhalmazával.

Bizonyítás: (a jól ismert tankönyvi verziók rekonstrukciója)

Tegyük fel indirekte, hogy M ekvivalens H-val, azaz, hogy

(1)                                        létezik  B: M ® H  bijektív leképezés.

Tekintsük a H hatványhalmaznak azt a T elemét, melynek pontosan azok az M halmazbeli x elemek elemei, melyekhez rendelt B(x) halmaz nem tartalmazza elemként x-et, azaz  TÎH  tegyen eleget a

(2)                                             "xÎM  [xÎT Û  Ø xÎB(x)]

követelménynek (Û  az 'ekvivalencia' logikai műveletet, Ø a 'negáció' logikai műveletet jelöli. Û  Ø  helyett a ’kizáró vagy’ Ñ jelet is használhatjuk itt.)

(*)

Az (1) feltétel  miatt létezik t =B-1(T), azaz

(3)                                                   $tÎM  [B(t) = T].

A (2) és (3) kétszeri felhasználásával kapjuk:

(4)       ha [tÎT] akkor [tÏB(t)] azaz [tÏT], és ha [tÏT] akkor [tÎB(t)] azaz [tÎT].

Ez ellentmondás, amivel

                                      cáfoltuk a kiinduló (1) indirekt feltételezésünket.

QED.

Erre a továbbiakban ’Cantor levezetés’ elnevezéssel hivatkozunk.

* * *

Állítás: Ez a levezetés hibás, nem bizonyítja a konklúziónak szánt állítást, azaz (1) tagadását. A hiba lényege: nem bizonyított, hogy a (2) követelményt kielégítő T halmaz szükségképpen létezik. Sőt ennek fordítottja igaz: amikor a levezetés során eljutunk (2) -ig,  már ott bizonyítható (anélkül, hogy hivatkoznánk a levezetés folytatására!), hogy az (1) feltétel fennállása mellett a (2) követelményt kielégítő TÎH nem létezik. Emiatt a (3) és a (4) -ben lévő kifejezések értelmezhetetlenek, ezért a levezetésben nem lehet eljutni a (4) ellentmondás kimutatásáig.

 

A következőkben’Ña ’kizáró vagy’ logikai művelet jele, ’@a formulahelyettesítés metanyelvi jele.

Definíció:   Legyen U  Í V és R az (U,V)  páron értelmezett reláció. Az R relációból származtatott  diagonalizációs tulajdonságot a következő formulával definiálom: 

 

                                        D(v)  @  "xÎU  [R(x,x) Ñ R(x,v)] ,   vÎV.

 

Tétel (Diagonalizációs tétel):   Legyen U=V. Akkor az R-ből származtatott  diagonalizációs tulajdonság kielégíthetetlen a V halmazon, azaz tetszőleges vÎV-re  D(v) = h, azaz "vÎV [Ø D(v)].

 

Biz: Legyen  eÎV  tetszőleges rögzített elem. A Fe(x) @ [R(x,x) Ñ R(x,e)] kifejezésben elvégezve a x = e helyettesítést, a ’kizáró vagy’ logikai művelet igazságtáblázata alapján kapjuk, hogy   Fe(e) = h. Tehát létezik olyan xÎV, melyre Fe(x)=h, ezért hamis (h) az az állítás, hogy Fe(x) minden xÎV-re i, azaz  ["xÎV  Fe(x) ] = h, azaz D(e) = h.

Mivel e-t tetszőlegesen választottuk, ezzel a tételt bebizonyítottuk. QED.

Megjegyzés: Ez nem indirekt bizonyítás.

 

Tétel_2: A

 

(1’)                                   [ létezik  B: M ® H  bijektív leképezés ]

 

feltétel fennállásakor nem létezik a (2) követelménynek eleget tévő  T Î H
azaz nem létezik olyan T
ÎH , melyre

 

(2’)                                                "x ÎM  [xÎT Ñ  xÎB(x)]

 

Bizonyítás:

Egyelőre használjunk ki annyit, hogy B injektív és jelöljük B képterét K -val, K ÍH.

Bevezetve a  X=B(x)  jelölést  (ahol xÎM), (2) ezzel ekvivalens:

 

(5)                                     " XÎK [B-1(X)ÎÑ  B-1 (X)ÎX]; TÎH .

 

Definiáljuk az R(X,Y) relációt így:

 

(6)                                   R(X,Y) @ [B-1 (X) Î Y];    X Î K, Y Î H.

 

Ezt felhasználva (5) ezzel ekvivalens:

 

(7)                                      " XÎK [R(X,T) Ñ R(X,X)];   T Î H.

 

Látható, hogy (7) nem más, mint a (6)-ban definiált R relációból származtatott D(T) diagonalizációs tulajdonság  és ez  ekvivalens (2) –vel.

 

Az (1) feltétel azzal ekvivalens, hogy létezik olyan injektív B: M ® H leképezés, mely egyben szürjektív is, azaz K=H. Ez megfelel a Diagonalizációs tétel  U=V feltételének, így a Diagonalizációs tétel alkalmazásával kapjuk, hogy minden TÎH -ra D(T) = h.

Tehát (1) fennállásakor nem létezik a (2) követelménynek eleget tévő TÎH.  QED.

 

Következmény_2: A Cantor levezetése elakad a (2) után a (*) pontnál, mivel azon túl egy addigra bizonyítottan nem létező T objektumra hivatkozik. Azt, hogy ilyen T nincs, a kiinduló indirekt feltételekre támaszkodva, de a (2) ponton túli folytatástól független, önálló gondolatmenettel vezettem le. Mivel a Cantor levezetés az ellentmondás kimutatása előtt elakad, ezért ez egy hibás levezetés.

(2010.10.02.: Az már egy más kérdés, hogy helyette, épp a Diagonalizációs tételre és a Tétel2 -re hivatkozva, lehet-e egy másik bizonyítást konstruálni. Ha találunk kellő  hivatkozási alapot, akkor lehet (ld. alább).  De  akár megvan ez a hivatkozási alap, akár nincs, ettől függetlenül igaz, hogy az eredeti bizonyítás hibás, amint azt a fenti matematikai gondolatmenet bizonyítja.)

 

Kapcsolat a ZF(C) részhalmaz axióma sémájával. Wolfram szerint (eredeti betűjelek kissé átalakítva):

                                      "M "p $T "x ( x Î Û   (x Î M  &  j (x;p)))

azaz:  ha j  egy tulajdonság (p paraméterrel), akkor tetszőleges M halmaz és  p paraméter esetén létezik az a  T = {x Î M | j(x;p) } halmaz, mely az M halmaznak pontosan azokat az x elemeit tartalmazza, melyeknek rendelkeznek a j tulajdonsággal.

 

Alkalmazás a Cantor levezetésre. Legyen: p @ B, (B az (1) szerinti) és  j (x;p)  @  Ø (x Î B(x))

akkor                        "M "B $T "x ( x Î Û  (x Î M  &  Ø (x Î B(x)))

Azaz e konkrét axióma azt állítja, hogy tetszőleges M halmaz és bijektív B: M ® H leképezés esetén létezik a H hatványhalmaznak az a T eleme, melyre  

(**)                                             "xÎM (x Î Û   Ø  (x Î B(x))).

 

A (**) azonos a (2) követelménnyel. Tehát  a ZF(C) részhalmaz axióma sémája alapján egy olyan konkrét axiómát állítottunk elő, mely pontosan az ellenkezőjét állítja annak, amit a Diagonalizációs tétel alkalmazása állít a Cantor levezetésre (ld. Tétel_2).  Ez ellentmondás, amiből úgy (is) ki lehet kerülni, hogy tagadjuk a B bijektivitását. Ezzel a formális segédlettel tehát a Cantor hatványhalmaz tétel a ZF(C)-ben bizonyítható. Ez elgondolkodtató!  

 

2010.10.02.: Ha elfogadjuk a ZF (vagy ZFC) axiómarendszert, akkor formális értelemben (de csakis úgy!) megvan a kellő hivatkozási alap ahhoz, hogy a Cantort tételt az eredeti hibás gondolatmenettől eltérő módon, épp a Diagonalizációs tételre hivatkozva bizonyítsuk, hiszen ott kimondatott egy ezt biztosító axióma. Ezek után hosszasan lehet filozófálni azon, hogy vajon a "naív halmazelméletben"  szintén rendelkezésre állt-e egy ilyen hivatkozási alap. Van, aki úgy gondolja, hogy egy ki nem mondott, hallgatólagos feltételezés is lehet hivatkozási alap, és erről még egy blogot/fórumot is indít. Lelke rajta. Én mindenesetre úgy gondolom, hogy kimondatlanul nem lehet hivatkozni semmire sem. Ha hivatkozok, akkor kimondtam, ha nem mondtam ki, akkor meg nem hivatkoztam. De az ezen való rágódás itt most félre vinne. (ld. még alább)

 

 

DISZKUSSZIÓ (utólag hozzátéve, 2010.10.03-04)

 

A gondolatmenet sarokpontja a Következmény_2. 

Ha csak annyi lenne itt a hivatkozási alap, hogy "T azért nem létezik a (*) pontnál, mert majd az indirekt Cantor bizonyítás végén kiderül az ellentmondás", akkor az hiba lenne, hiszen bizonyítások során - akár direkt, akár indirekt - csak a sorrendben korábbi lépésekre szabad támaszkodni.

A fenti gondolatment azonban nem sérti meg ezt a "sorrendiségi szabályt", amit a következő okfejtés mutat meg.

Azt, hogy a T nem létezik a kiinduló feltételek mellett, egy általános tételre (Diagonalizációs tétel =DT) alapozva a Tétel_2 mondja ki. A DT  tetszőleges R relációról szól. A DT-nek a konkrét helyzetre történő alkalmazása a Tétel_2, amikor is tekintjük a (6) -ban megadott konkrét R -t. A DT bizonyítása független a Cantor bizonyítás (*) -on túli folytatásától, hiszen az egy általános tétel. A Tétel_2 bizonyítása is független a (*) ponton túli folytatástól, hiszen az egy alkalmazása a DT-nek, a kiinduló feltételekre (azaz (*) -nál korábbi állításokra) támaszkodva.. Tehát: a gondolatmenet úgy mutatja ki a (*) pontnál a T -nek az adott feltételek melletti nemlétezését, hogy nem fut előre. Így tehát szó sincs az indirekt bizonyítás félreértelmezéséről.

 

Megjegyzés

 

Itt egy, a matematikai levezetések során lépten nyomon tetten érhető elvet alkalmaztam, amit a teljes cikkben "korlátozási szabálynak" neveztem. Ez alatt azt értem, hogy egy levezetés (legyen az akár direkt, akár indirekt) során nemcsak lehet támaszkodni a premisszákra (közvetlenül vagy közvetve), hanem minden lépésben kötelező is figyelembe venni a premisszák általi esetleges korlátozást. (Ennek kifejtését ld. a cikkben. és a Filozófiai Szeminátriumon)

 

A korlátozási szabály (és a másik kettő) kimondásával semmi újat nem szándékoztam mondani, csak ismerve a félreértelmezési alternatívákat, azokat előre ki akartam védeni azzal, hogy bizonyos jól ismert és általánosan elfogadott elveket explicite lerögzítek. (Ld. a cikkben a 3 szabályt.)

 

(A teljes cikkben a 0 -val való osztást hoztam fel példának, de akár valószínűségelméleti példa is hozható. Például, egy egyszerű tétel így szól: X és Y  valószínűségi változók várható értékeinek összege egyenlő az összegük várható értékével, feltéve, hogy X és Y  várható értékei léteznek és végesek. Ha ezek után egy bonyolultabb tételbizonyításba kezdünk, és annak egy adott pontján akarjuk alkalmazni ezt az összegtételt, nyilván meg kell állnunk egy pillanatra, és megkérdezni: a kiinduló feltételeink mellett léteznek és végesek ezek a várható értékek? Ha nem, akkor nem mehetünk tovább úgy,  mintha léteznének. Ez akkor is így van, ha történetesen egy indirekt bizonyításban vagyunk éppen benne. Az elv egyébként teljesen nyilvánvaló, alapvető logikai elv. Egy matematikus a bizonyítások során automatikusan figyelembe veszi anélkül, hogy különösebben ez tudatosodna nála.)

 

Mellesleg (2010.11.10):

Egyébként az is nagyon fontos kérdés, hogy milyen alapon általánosítjuk végtelenre azt a véges tapasztalatunkat, hogy amennyiben adott egy H halmaz valamely h elemének valamely lokálisan megállapítható P tulajdonsága, akkor kell létezzen a H halmaz azon részhalmaza, mely pontosan az ilyen P tulajdonságú elemeket tartalmazza. (Van, aki ezt nevezi a lokális tulajdonság kollektivizálhatóságának.) Ez a legtöbb esetben természetes. Pl. ha látok egy páros számot (ezt lokálisan állapítom meg, ti. 2 -vel elosztva 0 a maradék), akkor joggal gondolom, hogy létezik a természetes számok halmazának az a részhalmaza, mely a párosakat és csak azokat tartalmazza (ehhez persze el kell fogadnunk a természetes számok halmazának létét, mint aktuális végtelent). De miért kéne gond nélkül elfogadnunk e szabály olyan mértékű általánosítását, hogy végtelen M halmaz esetén (ld. a fenti Cantor hatványhalmaz tétel jelöléseit) is eleve léteznie kellene a (2) követelményt kielégítő  T-nek?  Ahogy mondogatni szokták:  a "végtelenben" (értsd: az aktuális végtelent elfogadó elméletekben) sok minden másképp van, mint végesnél. Pl. ott nem igaz, hogy a rész feltétlenül kisebb az egésznél, hiszen egy végtelen halmaz bizonyos saját valódi részhalmazaival is tud ekvivalens lenni. Akit ez nem zavar, annak vajon miért nehéz elfogadni, hogy a Cantor hatványhalmaz tétel indirekt bizonyításának kiinduló feltételei mellett a lokálisan megállapítható xÏB(x) azaz  [x nem eleme B(x)] tulajdonság nem kollektivizálható ( - egyébként ez a Tétel_2 állítása).

 

Íme a lenyelendő béka: van olyan lokálisan megállapítható tulajdonság, ami nem kollektivizálható. Sokan nem tudják ezt lenyelni. Az ő vágyálmuk: szeretnék, hogy minden lokálisan megállapítható tulajdonság kollektivizálható legyen. Azonban ezt a vágyálmot semmi mással nem tudják alátámasztani, mint hogy úgymond "posztulálják", ami pl. a részhalmaz axiómaséma lefektetésében nyilvánul meg. Ezt az axióma-sémát elfogadva, formális értelemben valóban bizonyítható a Cantor tétel, hiszen ekkor a (*) pont előtt a fent tárgyalt, Tétel_2 -vel kapcsolatos ellentmondásra jutunk (ld. ZF(C)-s fejezet). A Cantor hatványhalmaz tétel tehát e vágyálomra hivatkozva (és a Diagonalizációs tételt felhasználva!) valóban bizonyítható.

 

Megjegyzem még: a történelem során ilyen nem-kollektivizálható tulajdonságokkal Cantor előtt nem találkozhattunk; tapasztalhatjuk, hogy az ilyen tulajdonságok mindegyike kizárólag a Cantor féle diagonalizációnál bukkan fel. Felbukkanásuk viszont ez esetben nem is csoda, hiszen a Cantor féle diagonalizáció - önhivatkozás. Pontosabban: U=V esetén az. Az önhivatkozás megsérti a sorrendiségi szabályt. De hiszen erről szól a cikkem ... Érdemes végignézni: a diagonalizációs trükkön alapul a Cantor hatványhalmaz tétel, a valós számok "megszámlálhatatlanságának" Cantor féle tétele, a Gödel tétel, a Turing tétel, . ..és mind az összes többi végtelenről szóló tételt. És ugyanez mondható el a kapcsolódó antinómiákról: Russel-, borbély-, Richard-, a Berry- stb antinómiák. Az úgynevezett matematika-filozófia mást sem tesz 120 év óta, mint a diagonalizációs trükkből adódó problémákon rágódik.

 

Végül megjegyzem még: a halmazelmélet axiómáinak indoklása alapvetően eltér a matematika többi axiómarendszerének indoklásától. Utóbbiaknál mindig arról van szó, hogy hogyan modellezzük a valóság egy jelenségkörét (pl. a tapasztalati tér geometriai viszonyait), azaz mi legyen e jelenségkör matematikai modellje. Ehhez a tapasztalatból absztraháljuk az alapfogalmakat és az axiómákat. (Euklidész V, párhuzamossági posztulátuma épp azért volt problémás, mert a végtelenre hivatkozott, amiről nincs tapasztalat.) Ezekre azután felépítjük az elméletet, és megnézzük, mi jön ki belőle - és nem utolsó sorban: ismét visszatérünk a tapasztalathoz, és megnézzük, elméleti modellünk jól jósolja-e a tapasztalatot. A halmazelméleti axiómarendszereknél ellenben homlokegyenest másról volt szó: ott a cél szentesítette az eszközt. Ti. az ilyen axiómarendszerek megalkotói előre kijelölték, mit szeretnének "megmenteni" ( ld. még a teljes cikkben a Hilbertnek tulajdonított megfogalmazásokat, hivatkozva Ruzsára, Wittgensteinre, Neumannra és másokra), és ehhez igazították az axiómákat. Cseppet sem zavarta őket az, ami a geométereket 2ezer éven át zavarta. Ez így valóban nem több, mint egy öncélú játék az axiómákkal.

Utolsó módosítás: 2010.11.10.