Ez a file a HPS szeminárium honlapján lévőnek pontos másolata:

http://hps.elte.hu/seminar/2002/April/Goedel_vita/J_Geier_02_04_12.html

 

 

A Cantor-féle diagonalizáció szóbeli kritikája

"A Gödel-tétel filozófiai következményei" c. "Panel discussion" során kiderült, mi a nézőpontom sarkalatos pontja: a Cantor-féle diagonalizáció és az arról tett kijelentésem, ami sokakban nem annyira matematika, mint inkább érzelmi ellenállást váltott ki.

A vita során kifutottunk az időből, emiatt ennek részletes kifejtésére már nem kerülhetett sor. Ezt pótolom most egy tömör, intuitív gondolatmenettel.

A kritikai gondolatmenetemet egy tankönyből kiemelt példa kapcsán mondom el. Kérem a tisztelt olvasót, ha nem ért egyet a felhasznált példával, írja le, és küldje el nekem a Cantor-féle diagonalizációnak azt a verzióját, amivel egyetért. Az szólhat akár a valós számok nemmegszámlálhatóságáról, akár a hatványhalmaz tételről (a hatványhalmaz számossága mindig nagyobb az alaphalmaz számosságánál).

Továbbá kérem a tisztelt olvasót, hogy amennyiben nem ért egyet az alábbi kritikai elemzésemmel, mutasson rá, hol abban a hiba. (Hol "csúsztatok", amikor azt vezetem le, hogy Cantor "csúsztatott".)

 

Az olvasó iránti őszinte tisztelettel:

Geier János

Budapest, 2002. április 14.

 

************************************************************************

A Cantor-féle diagonalizáció szóbeli kritikája

© Geier János, 2002. április 14.

http://www.geier.hu/

Az alábbi gondolatmenet intuitív matematikai fogalmakat használ, csakúgy, mint magának a Cantor tétel levezetésének tankönyvekből ismert verziói, pl. az alábbi Rudin idézet. A korrekt, formalizált kritika egy másik dolgozatban kerül majd bemutatásra.

Rudin megfogalmazása (Rudin, W.(1978) A matematikai analízis alapjai, Budapest: Műszaki könyvkiadó. 40. oldal, betű szerinti idézet.)

{idézet kezdete}

 2.14. Tétel:  Legyen A az összes olyan sorozat halmaza, melynek elemei a 0 és 1 számjegyek.
Ez az A halmaz nem megszámálható.

Az A elemei olyan sorozatok, mint 1,0,0,1,0,1,1,1, …

Bizonyítás: Legyen E  az  A egy megszámlálható részhalmaza, és álljon E az s1, s2, s3, sorozatokból. A következők szerint konstruáljunk egy s sorozatot. Ha az n-edik számjegy
sn -ben 1, akkor legyen az n-edik számjegy s -ben 0, és fordítva. Ekkor az s sorozat E minden elemétől legalább egy helyen különbözik; ezért sÏE. De világos, hogy sÎA, és így E az A egy valódi részhalmaza.

Ezzel beláttuk, hogy A minden megszámlálható részhalmaza A valódi részhalmaza. Ebből következik, hogy A nemmegszámlálható. (Egyébként önmaga valódi részhalmaza lenne, ami képtelenség.) ÿ

{idézet vége}

Kritikai elemzés

A tétel levezetésének szövegével összhangban most sorozat alatt a tételben szereplő A halmaz elemeit értjük.

Nézzük meg, mit is jelent a levezetésben az a kifejezés, hogy "konstruáljunk". Talán egy vadonatúj, eddig még nem létező s sorozatot szándékozunk konstruálni? Nyilván nem, hiszen a kiindulás szerint A tartalmazza az összes sorozatot. Ezért a "konstruálás" jelen esetben nem egy új elem előállítását, csupán csak egy már korábban is létező A-beli elem "megnevezését" jelenti.

Állapodjunk meg - egyelőre általánosságban, a konkrét átlós módszertől függetlenül -, hogy mit is értsünk ilyen esetben konstrukció alatt. Javaslatom: a jelenlegi esetben konstrukció alatt olyan eljárást (módszert, leírást) értsünk, mely alapján meg tudunk nevezni egy A -beli elemet - feltéve, hogy van ilyen elem. Utóbbi kitételt nyilván hozzá kell tennünk, mert ha tetszőleges megnevezési eljárást megengedünk, akkor lehet, hogy nincs is azt kielégítő A-beli elem. (Pl. az, hogy "konstruáljuk meg azt az s sorozatot, mely egyenlő a saját számjegyeinek invertálásával létrehozott sorozattal", eleve kudarcra van ítélve. Ilyen s nem létezhet, még akkor sem, ha a megfogalmazásban úgy fogalmaztunk: "...azt az s sorozatot...". Ha ezután ezt a "nemlétező s sorozatot" akarnánk felhasználni bármiféle további gondolatmenetben, levezetve belőle különféle állításokat, súlyos logikai hibát vétenénk.)

Fordítsuk figyelmünket most a tétel levezetésében leírt "konstrukcióra".  Azaz tekintsük azt az s sorozatot - feltéve, hogy van ilyen -, mely a következő diagonalizációs feltételnek tesz eleget: "Ha az n-edik számjegy sn -ben 1, akkor legyen az n-edik számjegy s -ben 0, és fordítva."  Bontsuk két részre a lehetőségeket:

(1)   A\E = Æ 
(2)   A\E ¹ Æ

E két lehetőség egymást kizárja, ugyanakkor együtt lefedik az összes lehetőséget; harmadik lehetőség nincs.

Mind az (1), mind a (2) eset további két lehetőségre bomlik:

(i)   nincs olyan s sorozat, mely a diagonalizációs feltételeknek eleget tesz;
(ii)  van ilyen s sorozat.

Ezek egyrészt szintén kizárják egymást, másrészt lefedik az összes lehetőséget.

Vegyük sorra mind a 4 lehetőséget:

(1i)   A\E=Æ és nincs ilyen s sorozat
(1ii)  A\E=Æ és van ilyen s sorozat  
(2i)   A\E¹Æ és nincs ilyen s sorozat
(2ii)  A\E¹Æ és van ilyen s sorozat

A rövidebb írásmód érdekében, ha valamely s eleget tesz a diagonalizációs feltételnek, azt jelöljük így: D(s)=igaz, ha nem tesz eleget, azt így: D(s)=hamis. Akkor e 4 lehetőséget a következő táblázattal szemléltethetjük:

 

(1)
A\E=Æ

(2)
A\E ¹Æ

(i) Ø$s D(s)

a

b

(ii)   $s D(s)

c

d

 ahol a,b,c,d  az igaz vagy a hamis logikai értékek valamelyikét jelöli. Ezt a táblázatot kell kitöltenünk annak érdekében, hogy eldönthessük, a fenti 4 lehetőség közül melyik áll fenn, és melyik nem.

A fentiek alapján nyilvánvaló, hogy mindkét sorban és mindkét oszlopban pontosan egy igaz és pontosan egy hamis logikai érték lehet; tehát az a,b,c,d elemekből álló mátrix egyik átlója csupa igaz, másik átlója csupa hamis logikai értékből áll.

A tétel bizonyításának megfelelő részlete alapján nyilvánvaló, hogy c=hamis, amiből már egyértelműen adódik, hogy a főátlóban lesznek az igaz, a mellékátlóban pedig a hamis értékek. Tehát a kitöltött táblázat a következő:

 

(1)
A\E=Æ

(2)
A\E ¹Æ

(i) Ø$s D(s)

igaz

hamis

(ii)   $s D(s)

hamis

igaz

És most figyeljük meg, közvetlenül a táblázat alapján mit kaptunk:

Ha  feltesszük, hogy A\E=Æ,  akkor nincs a diagonalizációs feltételnek eleget tevő sorozat; ha  feltesszük, hogy A\E¹Æ, akkor pedig van. Ellentmondás egyik esetben sincs.

De ugyanezt, szintén közvetlenül a táblázat alapján, fordítva is megkapjuk:

Ha feltesszük, hogy nincs a diagonalizációs feltételnek eleget tevő sorozat, akkor A\E=Æ,  ha feltesszük, hogy van, akkor pedig A\E¹Æ. Ellentmondás egyik esetben sincs.

Következmény: A tétel levezetése szerinti Cantor-féle diagonalizációs eljárással se azt nem bizonyítottuk, hogy az A halmaz megszámlálható, se azt, hogy nemmegszámlálható.

Q.E.D.

Értelmezés

Az eredeti levezetésben rejlő "csúsztatás" most már nyilvánvaló: rejtett módon megelőlegezi egy olyan sorozat - nevezetesen a diagonalizációs feltételnek eleget tévő sorozat - létezését, amelynek éppen a létezését kívánja bizonyítani. Ezt egy nyelvi természertű aspektus is elősegíti: "Ekkor az s sorozat E minden ..."(idézet a tétel levezetéséből). Az fel sem merül, hogy ilyen s talán nincs is? ("ilyen"  = "a diagonalizációs feltételnek eleget tévő")

A csúsztatás hátterében az is feltűnik, hogy Cantor-féle levezetés "ügyesen" váltogatja az akutális végtelen és a potenciális végtelen fogalmát. (ld. Ruzsa Imre (1966) A matematika néhány filozófia problémájáról, Budapest: Tankönyvkiadó, 16-17. oldal.) Amikor az A és az E halmazról beszél, azokat egyszer s mindenkorra kész halmazoknak tekinti (aktuális végtelen), amikor "konstrukcióról", akkor pedig egy konstruálási, bővítési folyamat alatt álló halmazról (potenciális végtelen). Azzal, hogy világosan elkülönítjük az s sorozatról tett kijelentéseket a D(s) diagonalizációs tulajdonság megfogalmazásától, ezt a fogalmi keveredést letisztáztuk.

Megjegyzés: A kritikai gondolatmenetnek a Következmény a fő állítása, nem pedig az, amit a Értelmezésben fejtettem ki. Utóbbi már csak ráadás, nem ebben kell keresni az esetleges hibát.

Copyright © Geier János

www.geier.hu