Cantor hatványhalmaz-tételével kapcsolatos diszkusszió

Molnár Zoltán blogbejegyzésében említette, hogy Geier János esszéjével (Cantor hatványhalmaz tételének kritikája) valami gond lehet.

Nos, a cikk többek számára olvashatatlan (kizárólag MS termékekkel jeleníthető meg megfelelően), ezért el fogom kérni Geier úrtól a cikk felhasználási jogát, legalábbis a fórum számára.

Addig is a szabad forrásokra hivatkozom (és kérek mindenkit, küldjön ide link formájában anyagokat):
WikiPedia - Cantor-tétel (és bizonyítás)
Csaba Ferenc: Cantor tétele (pdf)

Update: Geier János megküldte RTF formátumban a cikket (ld. a csatolmányt), melyet ezúton is megköszönünk neki.

CsatolásMéret
Cantor_rovid.rtf67.77 KB
 

Hozzászólás megjelenítési lehetőségek

A választott hozzászólás megjelenítési mód a „Beállítás” gombbal rögzíthető.
Varasdi Károly, 2006, május 19 - 19:03

Ez érdekes. Egyébként az indirekt bizonyítás időnként nagyon is trükkös tud lenni...

Simonyi András, 2006, május 13 - 18:16

Varasdi Károly hívta fel a figyelmemet (már elég régen) Wilfrid Hodges, a neves logikus
itt olvasható cikkére, amelyben a szerkesztőként hozzá beküldött Cantor-tétel cáfolatokról számol be, bemutatva a leggyakrabban előforduló gondolatmeneteket. Hodges ugyan a Cantor-tétel speciális, a term. számok halmazára vonatkozó alakjáról ír, de szerintem vannak olyan megjegyzései, melyek G.J. írásához is kapcsolhatók.

Különösen a cikk vége releváns, ahol az indirekt bizonyítások értelmezésének nehézségeiről ír.

Simonyi András, 2006, május 13 - 12:25

átrágtam magam a csatolt anyagon, és nekem úgy tűnik, hogy nem sikerült hibát találnia a bizonyításban a szerzőnek.

Mozó már utalt arra, hogy az írás T létezését cáfoló gondolatmenete problematikus: ha R reláció (tehát halmaz), akkor legalábbis magyarázatra szorul, hogy miként szerepelhet az őt jelölő kifejezés kétargumentumú predikátumként a "diagonálizációs formulában". Ezen felül a diagonalizációs formula hol "meghatároz" egy tulajdonságot, (állítás_1), hol ő maga egy leképezés (állítás_1 bizonyítása) -- az utóbbi viszont legalábbis furcsa, hiszen egy formula minden valószínűség szerint nem lehet halmaz.

A fő probléma azonban nem "T nemlétezésének bizonyításával" van, mert ez a gondolatmenet precízzé tehető, hanem azzal, hogy a szerző nem tisztázza, hogy pontosan milyen formális rendszerben, milyen axiómákból kiinduló bizonyítást kritizál, és -- ez a legnagyobb baj -- mintha tévesen értelmezné az indirekt bizonyítás módszerét.

Az eredeti bizonyítás a következő érvényes érvelési receptet, a Reductio ad absurdumot használja:

"Annak igazolásához, hogy egy G premisszahalmazból következik ~A, elégséges azt igazolni, hogy G és {A} uniójából ellentmondás következik."

Azt hiszem, nem szükséges amellett érvelni, hogy ez egy bevett bizonyítási módszer (az intuicionista logikában is érvényes, és pl. a term. levezetési rendszerekben ez a negációra vonatkozó két legalapvetőbb levezetési szabály egyike, az ún. bevezetési szabály).

Osszuk ki a szerepeket: a klasszikus bizonyításban G a halmazelmélet bizonyos axiómáit tartalmazza, A pedig az az állítás, hogy létezik olyan B és M, melyre teljesül, hogy B bijekció M és M hatványhalmaza között.

A klasszikus bizonyítás így okoskodik: ha A igaz, akkor a részhalmazaxióma-séma miatt léteznie kell M egy olyan T részhalmazának is, melyben pontosan M azon elemei találhatók, amelyek nem elemei B-szerinti képüknek. T létezésének feltételezése viszont ellentmondásra vezet, mivel T B-szerinti ősképe pontosan akkor eleme T-nek, ha nem eleme. Sikerült ellentmondásra jutnunk, tehát igazoltuk, hogy a halmazelmélet G axiómáiból következik ~A.

G.J. bizonyítja, hogy ha A teljesül, akkor nem létezhet a fenti elemeket tartalmazó T, és úgy gondolja hogy a bizonyítás emiatt nem folytatható. Nos egyrészt fölöslegesnek tűnik a bonyolult gondolatmenet T "nemlétéről", mert már az eredeti bizonyítás is igazolja, hogy egy ilyen T létének feltételezése ellentmondásra vezet, másrészt abszurd az az állítás, hogy a bizonyítás nem folytatható, hiszen a reductio ad absurdum-hoz éppen az szükséges, hogy belássuk: egy állítás és az állítás tagadása is következik premisszáinkból és abból az állításból, aminek a negációját igazolni szeretnénk. Márpedig pont ez a helyzet: az indirekt feltevésből és az axiómákból a megfelelő tulajdonságú T nemlétezése következik, hiszen létének feltevése ellentmondásra vezet, de létezése is következik, a részhalmazaxióma-séma miatt.

Van még az írásnak egy másik vonulata is: mintha G.J. nem fogadná el a részhalmazaxióma-séma igazságát (lásd tétel_3). Ennek feltevése nélkül valóban nem következik a tétel, de nem hiszem, hogy bárki az ellenkezőjét állította volna.

Összefoglalva: Szerintem a klasszikus bizonyítás a halmazelmélet szokásos axiómáit felhasználva, általánosan elfogadott, érvényes következtetési szabályoknak megfelelően érvelve konklúzivan igazolja a bizonyítandó állítást, és G.J. írása nem tartalmaz olyasmit, ami ezt kérdésessé teszi.

Molnár Zoltán, 2006, május 10 - 07:11

Először is. G. J. lényegében azt állítja, hogy bár hivatkozhatunk a (cikkben szereplő) T halmazra, de ez mégsem létezik (jelölet nélküli?). Én pont az ellenkezőjére hívnám fel a figyelmet. Miközben levezethető a T létezését állító formula, addig nem biztos, hogy van olyan term, mellyel T-re hivatkozni tudnók (előkerül a ZF nyelvének határozatlan individuumleírásokkal kapcsolatos megnevezési hiányossága, melyet azonban kellő ügyességgel Russell szerint át lehet hidalni). Mindezek azonban nem érintik a Cantor-tétel állításának érvényességét.