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 Filozófiai Szemináriumra beküldött absztraktot itt találod

 

Teljes levelezés Máté Andrással: Máté Andrással a cikk visszautasítása kapcsán folytatott levelezés itt található: MAlevelezes.htm

A kérdéses cikk: Mekis Péter felkérésére beadott, majd Máté András által visszautasított teljes cikk: itt található

Teljes levelezés Mekis Péterrel:  Mekis Péterrel a cikk visszautasítása kapcsán folytatott levelezés itt található: MekisLevelezes.htm

 

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 korrigálható, de az már egy másik bizonyítás lesz. Ezen különféle filozófiai vitákat lehet folytatni. De nem matematikait.

 

Az írás lényegét a Tétel_2 utáni Következmény_2 mondja ki.

Ld. még alul a diszkussziót.

 

Ha valaki nem ért egyet azzal, hogy a szokásos Cantor levezetés hibás és a (*) pontnál elakad, az legyen szíves, mutasson rá a hiba kimutatását célzó alábbi gondolatmenet  hibájára. Szerinte mi a hiba, hol és miért: Diagonalizációs tétel?, Tétel_2?, Következmény_2? Elkezdeni másról beszélni ehelyett, felesleges.

 

Új megjegyzések még a szövegben és a szöveg alján

 

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.

 

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)ÎT  Ñ  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. Kellő hivatkozási alap esetén 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 Î T  Û   (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 Î T  Û  (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 Î T  Û   Ø  (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.: A ZF-ben (vagy ZFC-ben) 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ére á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 nem ez a lényeg itt, az ezen való rágódás félre visz. Az egész gondolatsor fő állítása a Következmény_2.

 

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

 

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. Ezt az elvet, ha nem is ilyen explicit formában kimondva, az ELE TTK matematikus szakán az 1970 es években oktatták, sőt épp a valószínűségszámítás tantárgyban számon is kérték. 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.)

 

Kedves korlátozási szabályt nem elfogadó olvasó!

Ha nem fogadod el a korlátozási szabályt, akkor nincs miről tovább beszélnünk. Ugyanis az azt jelenti, hogy merőben mások a matematikával kapcsolatos tapasztalataink és a matematikai gondolkodásmódról alkotott fogalmaink. Közös alap nélkül sose fogjuk megérteni egymást - de a világ elég tág.

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