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

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 s₁, s₂, s₃, … sorozatokból. A következők szerint konstruáljunk egy s sorozatot. Ha az n-edik számjegy
s_n-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 s_n-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.