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

 

V2.35

második, javított verzió

 

Copyright © Geier János, 2002.05.20- 2004.04.15

http://www.geier.hu

 

Írásom előző verziójára kapott reakciók alapján szükségét éreztem, hogy azon - az alapgondolat megtartása mellett (!) - jelentős formai átalakítást végezzek. .

 

Nézzünk először egy tömör levezetést a Cantor tételre.

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ámlá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

Mindenek előtt azt szeretném megjegyezni, hogy itt nem Rudin a főszereplő: a Cantor tétel bármely más, hasonló logikát követő levezetését választhattunk volna a kritika tárgyául. Valamit azonban kellett választani, és hát éppen erre esett a választás.

 

Először tagoltan ismételjük meg magát a Rudin-féle levezetést.

R1°. A tétel kimondásakor Rudin bevezeti a következő jelölést:

(1)       Jelöljük A-val az összes olyan (véges vagy végtelen) sorozat halmazát, melyek a 0 és 1 számjegyekből állnak.

Azt természetesen ezen a ponton még nem tudjuk, hogy A számossága mekkora, ez itt még függőben van.

R2°. A tétel állítása: Ha az (1) feltétel fennáll, akkor A nem megszámlálható számosságú.

A megszámlálható számosság fogalma alatt nyilván a következőt kell itt érteni: valamely H halmazt akkor nevezünk megszámlálhatónak, ha a természetes számok N halmaza és a H halmaz között létezik kölcsönösen egyértelmű leképezés.

R3°. A bizonyítás első lépéseként egy új jel kerül bevezetésre:

(2)       Jelöljük E-vel az A halmaz egy tetszőleges megszámlálható részhalmazát.

Ez azt jelenti, legyen E olyan részhalmaza A-nak, melyre létezik a természetes számok N halmaza és az E halmaz között egy kölcsönösen egyértelmű leképezés. Más szóval az E elemei megszámozhatók a természetes számok által, azaz sorozatba rendezhetők. Itt nincs kikötve, hogy E valódi részhalmaz legyen, a levezetésnek ezen a pontján még az E=A eset lehetőségét is meg kell engedni. Nem is lenne korrekt dolog az EÌA feltételt előre kikötni (azaz az E=A lehetőséget eleve kizárni), hiszen a további lépésekből látni fogjuk, hogy Rudin bizonyításának fő célja éppen annak kimutatása, hogy E=A lehetetlen.

Nézzük, hogyan is mutatja ezt ki?

R4°. Az E halmazt alkotó sorozatokat s1, s2, s3, ... -vel jelöli, és e jelölések felhasználásával "konstruál" egy s sorozatot a következő "szabály" segítségével:

(3)       Az s sorozat n-edik eleme legyen 1, ha az sn  sorozat n-edik eleme 0, és fordítva.

Azt, hogy ez az s sorozat eleme-e E-nek, vagy sem, ebben a pillanatban még nem tudhatjuk, de Rudin azon nyomban beláttatja velünk, hogy az nem lehet E-ben. Teszi ezt a következőképp.

R5°. Azt állítja, hogy

(4)       A (3) által konstruált s sorozat E minden elemétől különbözik.

Ennek okát ugyan nem részletezi, de egy rövid indirekt bizonyítással könnyen beláthatjuk mi is. Ha ugyanis sÎE lenne, akkor azon feltevés miatt, hogy E megszámlálható, a megszámlálhatóságot bizonyító kölcsönösen egyértelmű hozzárendelés alapján ez az s valamelyik k természetes számhoz lenne hozzárendelve, azaz lenne olyan k természetes szám, melyre s= sk. Azonban ekkor az s (3) szerinti konstrukciója miatt ennek az s= sk -nak a k-adik számjegye nem lehetne azonos sk  -nak a k-adik számjegyével, azaz saját maga k-adik számjegyével. Ez nyilván ellentmondás, tehát Rudin nyomán valóban beláthattuk, hogy a (3) szerint konstruált s nem lehet az E eleme. (Vegyük észre, hogy ez az indirekt gondolatmenet támaszkodik arra a kiinduló feltételre, hogy E megszámlálható.)

R6°. Rudin azt állítja ezek után, hogy viszont a (3) szerint konstruált s, ha nem is eleme E-nek, de A-nak mindenképpen eleme, azaz sÎA. Ezzel eljut a fő konklúzióhoz: "és így E az A egy valódi részhalmaza". Ha az előbbieket végig elfogadjuk, akkor valóban így is van. Az E-nek (2) szerinti definíciója önmagában még nem zárja ki se az  E=A, se a EÌA lehetőséget. Mivel azonban imént láttuk be, hogy s eleme A-nek, de nem eleme E-nek, ezért sÎA\E,  ezért A\E nem üres, azaz E valódi részhalmaza A-nak. Tehát E=A nem lehetséges. Ennek kimutatása volt a bizonyítás fő célja, és ez ezek szerint sikerült is.

R7°. A bizonyítás további mondatai már csak a megszámlálható halmaz fogalmát magyarázzák és aktualizálják jelen esetre.

Ez volt tehát a Cantor tételének és a tétel levezetésének Rudin-féle részletes, kritikai megjegyzések nélküli kibontása.

 

Most nézzük meg a levezetést kritikusabb szemmel.

Vegyük sorra az R1° ... R7°  pontokat, az egymásnak megfelelő pontokat most K1°...K7°-tel jelölve. (Az Ri°-beli szöveget nem mindenütt ismétlem meg, adott esetben vissza kell oda lapozni.)

K1°. Az (1) jelölés eleve feltételezi, hogy az ilyen sorozatok halmaza létezik. Rendben, fogadjuk el, hogy a matematikában használt "létezés" fogalommal összhangban létezik az A halmaz, mely elemként tartalmazza az össze 0,1 számjegyekből álló sorozatot, és csak azokat.

K2°. A tétel állítása itt kerül kimondásra. Fogadjuk el, hogy Rudin ennek bizonyítását tűzte ki célul.

K3°. Az E halmaz bevezetésével a bizonyítás új fordulatot vett: mostantól nem az N és A halmaz közötti kölcsönösen egyértelmű megfeleltetés lehetetlenségének közvetlen bizonyítása a cél, hanem e helyett az lesz a cél, hogy belássuk: bárhogyan választjuk is az A halmaz E részhalmazát, ha E megszámlálható, akkor nem lehet azonos A-vel. Tehát a cél: kellő indokot kell találni az E=A lehetőség kizárására. (Ezen a ponton még az E=A lehetőség nincs kizárva!)

K4°. És most érkeztünk el a bizonyítás kritikus pontjára: konstruálás. Rudin "konstruál" egy s sorozatot a (3) "szabály" alapján.

Álljunk itt meg, és tegyük fel a kérdést: mit jelent jelen esetben az a szó, hogy "konstruálás"? Talán egy vadonatúj, eddig még nem létező s sorozatot szándékozik konstruálni? Nyilván nem, hiszen a kiindulás szerint A tartalmazza az összes sorozatot. Bármilyen s sorozatot is szeretne "konstruálni" Rudin, az sikeres esetben azonos lesz egy A-beli elemmel - sikertelen esetben pedig nem fog megnevezni semmit. Az, ami itt konstruálásnak tűnik, valójában csak megnevezés! Pontosabban szólva: megnevezési szándék. Ti. nem biztos, hogy az, amit ilyen formán megnevezni próbál, valóban létezik is.  Az egzisztencia ilyen esetekben mindig bizonyítandó!

Ezért a továbbiakban el kell felejtenünk a "konstruálás" szót, és helyette a helyzetet valójában kifejező "megnevezés" szót kell használnunk. (A megnevezés szó szinonimái: kijelölés, kiválasztás, hivatkozás rá, stb.)

A (3) szabály alapján tehát lehetetlen "új" sorozatot "konstruálni", ezért a következő elnevezést javaslom.

Konvenció_1: A  (3)-mal jelölt mondatot a továbbiakban diagonalizációs feltételnek nevezzük.

Ezt úgy értelmezzük, hogy ha előre (magától a (3) feltételtől független módon!) adva van egy s sorozat, akkor utólag, s ismeretében feltehető a kérdés, hogy ez az s eleget tesz-e a (3) diagonalizációs feltételnek, vagy sem.

K5°. Rudin ezek után itt azt a látszólagos kérdést veti fel, hogy a (3) által megnevezett s sorozat hová tartozik: E-be, vagy A\E-be? Célja annak kimutatása, hogy nem tartozhat E-be. Ez azonban csak látszólagos kérdés, ugyanis itt elsikkad egy nagyon fontos szempont: létezik egyáltalán olyan s sorozat, ami megfelel a (3) kitételnek? A levezetés szövege ezt egyszerűen átlépi, és eleve arról beszél, hogy "az" s sorozat. Ez levezetési hiba.

Ezt a hibát a (4) állítás következő módosításával tehetjük korrektté:

(5)       Ha a (3) által megnevezett s sorozat létezik, akkor s az E minden elemétől különbözik.

(Fogalmazhatnánk így is: A (3) által megnevezett s sorozat E minden elemétől különbözik - feltéve, hogy létezik ilyen, a (3) -nak eleget tévő s. Azonban néhányan félreétették a "feltéve" kifejezést. Tévesen úgy gondolták, hogy ez egy önkényes szándékot fejez ki. Valahogy így gondolták: ha ezt tekintjük az egyik kiinduló feltételnek, akkor természetes, hogy ebből már következik az kérdéses állítás.)

Nyilvánvaló: ha tetszőleges megnevezési leírást tekintünk, akkor egyáltalán nem lehetünk előre biztosak abban, hogy létezik azt kielégítő objektum, jelen esetben 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, melyre már Arisztotelész is felhívta a figyelmet, és így hívott: "a kellő megalapozottság hiánya". A matematika egyéb területein számtalan olyan példa található, ahol ezzel a szófordulattal élünk. Pl. "tekintsük az X valószínűségi változó várható értékét - feltéve, hogy az létezik.")

Már eddig is többször hangsúlyoztuk, hogy amíg E=A lehetetlenségét nem bizonyítottuk, addig a következő két lehetőség áll fenn:

(I)  E=A

(II)  A\E¹Æ .

ahol E az A-nak tetszőleges megszámlálható részhalmaza, EÍA.

(Az (I) lehetőség fennállása azzal ekvivalens, hogy A megszámlálható.)

Nyilvánvaló, hogy bármely adott EÍA esetén e két lehetőség egymást kizárja, ugyanakkor együtt lefedik az összes lehetőséget; harmadik lehetőség nincs. Az eredeti Rudin-féle levezetés célja éppen annak kimutatása lenne, hogy (I) feltételezése a (3) diagonalizáció felhasználásával ellentmondásra vezet. Nézzük meg, hogy az ellentmondás kimutatása a "konstrukció" vs. "megnevezés" fogalmának fenti tisztázása után még mindig lehetséges-e?

Tekintsük a következő két állítást, melyekben (2) -vel összhangban jelöljük E-vel az A egy tetszőleges megszámlálható részhalmazát.

Állítás_1: Nincs olyan sÎE sorozat, mely eleget tesz (3) diagonalizációs  feltételnek.

Bizonyítás_1: Az állítás bizonyításához ismételjük meg az R5°-ben leírt indirekt gondolatmenetet, de itt most a Konvenció_1 alapján ki kell cserélnünk a "konstrukció" szót a "megnevezés" szóra.
Tegyük fel indirekte, hogy létezik a (3) diagonalizációs feltételnek elege tevő sÎE sorozat.
Mivel E megszámlálható, a megszámlálhatóságot bizonyító kölcsönösen egyértelmű hozzárendelés alapján ez az s valamelyik k természetes számhoz lenne hozzárendelve, azaz lenne olyan k természetes szám, melyre s = sk. Azonban az s -ről feltettük, hogy eleget tesz a (3) feltételnek, ezért ennek az s= sk -nak a k-adik számjegye nem lehetne azonos sk -nak a k-adik számjegyével, azaz saját maga k-adik számjegyével. Ez nyilván ellentmondás, tehát nem igaz az az indirekt feltételezés, miszerint létezik a (3) diagonalizációs feltételt kielégítő sÎE sorozat. Ezzel az állítást bebizonyítottuk.

Állítás_2:  Ha E=A,  akkor nincs a (3) diagonalizációs feltételnek eleget tevő sÎA sorozat.

Bizonyítás_2: A kiinduló E=A feltétel miatt nyilvánvaló, hogy s most csak E-beli elem lehet. Ezért a tétel állítása az Állítás_1 közvetlen következménye.

Az Állítás_2-et úgy is fogalmazhatjuk: Ha feltesszük, hogy E=A, akkor a (3) diagonalizációs feltétel nem nevez meg semmit.

Az előbbiekből következik, hogy ahhoz, hogy a (3) diagonalizációs feltételnek eleget tevő s sorozat létezésének egyáltalán a lehetősége fennálljon, előre fel kell tételeznünk, hogy A\E¹Æ . Ha ugyanis az ellenkezőkét tesszük fel, vagyis hogy az E olyan, hogy  A\E=Æ, azaz E=A, akkor az Állítás_2 szerint nincs a (3) diagonalizációs feltételnek eleget tevő s sorozat, ami egy egyértelmű, bizonyított állítás, nem pedig ellentmondás.

K6°. Ezen a ponton tehát az eredeti R6° ponttal ellentétes eredményt kaptunk. Ugyanis R6° azt állítja, hogy a (3) szerint "konstruált" s, ha nem is eleme E-nek, de A-nak mindenképpen eleme.
A Konvenció_1 szerint  a "konstruálás" fogalma helyett a "megnevezés" fogalma, ami itt helyénvaló. E konvenció alapján bizonyított Állítás_2 pedig épp azt mondja ki, hogy az E=A lehetőség elutasítását a diagonalizációra hivatkozás nem indokolja; az E=A feltétel mellett egyszerűen nincs a (3) diagonalizációs feltételnek eleget tevő sÎA sorozat.

A pontos elemzés tehát azt mutatta ki, hogy a diagonalizációs feltételre hivatkozva nem találtunk alapot az E=A lehetőség kizárására - ami pedig az eredeti bizonyítás fő célja lett volna.

K7°. A végkonklúzió ellentétes az eredeti R7°-tel. Azt kaptuk ugyanis, hogy A megszámlálhatóságának feltételezése nem vezet ellentmondásra. Tehát ahhoz, hogy az A nemmegszámlálhatóságának bizonyításához egyáltalán hozzá lehessen kezdeni, előtte fel kell tételeznünk, hogy A nemmegszámlálható - és ekkor valóban sikeres is lesz a "bizonyítás". Ez nonszensz.

 

Következmény: A Cantor-féle diagonalizációra hivatkozással - a kimutatott levezetési hiba korrekciója után - nem lehet bizonyítani az A halmaz nemmegszámlálhatóságát.

 

É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észetű 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 (3) diagonalizációs feltételnek eleget tévő")

A kritikai elemzés K1° ... K7° pontjai ki is mutatták, hogy ha a "konstruálás" fogalmát felcseréljük az itt helyénvaló "megnevezés" fogalmával, akkor kapjuk az Állítás_1 és Állítás_2 -t, ami felfedi e rejtett előfeltételt.

A csúsztatás

A csúsztatás hátterében az is feltűnik, hogy Cantor-féle levezetés "ügyesen" váltogatja az aktuá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ó sorozatról (potenciális végtelen). Azzal, hogy a (3) diagonalizációs feltételt nem konstrukciónak, hanem megnevezésnek tekintjük, ezt a fogalmi keveredést letisztáztuk, aminek eredménye a fenti következmény.

Miért nehéz észrevenni?

Végül még meg kell vizsgálni, mi lehet az oka annak, hogy mégis sokan elfogadják a Cantor tétel szokásos, konstrukción alapuló levezetéseit? Ennek vélhető oka, hogy a "konstrukció" fogalma a matematikában mindennapos, hétköznapi fogalom, ezért aki a Cantor tétel levezetését olvassa, könnyen átsiklik afelett, hogy itt nem véges konstrukcióról van szó. Valamilyen nem teljesen tisztázott módon az olvasó úgy véli, el tudja képzelni azt az s sorozatot, amit a (3) leírás "megkonstruál". Ha jobban belegondolunk, kiderül: a (3) leírást bizonyos értelemben valóban lehet konstrukciónak tekinteni, hiszen rögzített n esetén, elölről kezdve, egyesével lehet konstruálni egy  0,1 számjegyekből álló, n hosszúságú véges sorozatot. Ez azonban nem ugyanaz, mintha egy végtelen sorozatot "konstruálnánk". Ez téveszti meg az olvasót!

Miután pedig az olvasó átsiklik ezen a nüansznyi logikai résen, tévesen úgy véli, hogy eszerint (3) egy végtelen hosszú s sorozat "konstruálását" írja le - és nem firtatja, mit is kell érteni ilyen esetben konstruálás alatt. Ezért az R5°-ben kifejtett indirekt gondolatmenetben nem azt a feltételt veti el, hogy s létezik (ez a kérdés fel sem merül benne), hanem azt, hogy az E=A előfeltétel, azaz a fenti (I) lehetőség vezetett ellentmondásra, tehát azt kell elutasítani.

Ami már van, zt nem lehet újból létrehozni - csak megnevezni

Végül azt is vegyük észre, hogy az A halmaz a Tétel0 kiinduló feltétele miatt eleve tartalmazza az összes 0,1 számjegyekből álló sorozatot, ezért "új" sorozat "konstrukciójának" lehetősége egyszerűen nem áll fenn. Hiába akarna valaki "új" sorozatot konstruálni,  nem fog sikerülni: bármit is mond, jó esetben csupáncsak megnevez egy olyat, ami már ezelőtt is létezett. (Rossz esetben pedig a semmit nevezi meg, azaz nemlétező dologról akar valamit állítani.)

 

Összefoglalás: A Cantor tétel levezetéseinek szokásos gondolatmenteiben hallgatólagosan eleve feltételezik, hogy a diagonalizációs feltételnek eleget tévő s sorozat létezik - holott ez nem triviális.  Ez bizonyításra szorul, de e bizonyítás hiányzik.

 

 

Copyright © Geier János

www.geier.hu