Russell-paradoxon

A Wikipédiából, a szabad lexikonból.

A Russell-paradoxon Bertrand Russell 1901-ben felfedezett halmazelméleti paradoxonja, amely rávilágít, hogy a Cantor és Frege által megalkotott naiv halmazelmélet, illetve formalizált logikai elmélet ellentmondásos.

A paradoxon formális definíciója a következő: legyen R azon halmazok halmaza, amelyek nem tartalmazzák saját magukat:

$R=\{S\mid S\not\in S\}$

A Cantor-féle halmazelméletben R jóldefiniált halmaznak tekinthető. A paradoxon lényegére rávilágító kérdés: eleme-e R önmagának?

Tegyük fel, hogy igen, $R \in R$ . Ekkor R nyilvánvalóan nem olyan halmaz, ami nem tartalmazza saját magát, tehát definíció szerint nem eleme R-nek, azaz önmagának, más szóval $R \not\in R$ , ellentmondásra jutottunk.
Tegyük fel, hogy nem, azaz $R \not\in R$ . Ekkor R nyilvánvalóan olyan halmaz, ami nem tartalmazza saját magát, tehát definíció szerint eleme R-nek, azaz önmagának, más szóval $R \in R$ , ismét ellentmondásra jutottunk.

Látható, hogy mindkét lehetséges feltételezés ellentmondásra vezet.

Russell felfedezése alapjaiban rengette meg a matematikát. Egyszerűen bebizonyítható ugyanis, hogy egy olyan matematikai elméletben, melyben a hagyományos matematikai logika eszközeivel egy ellentmondást le lehet vezetni (tehát legalább egy tétel és annak tagadása is levezethető), minden levezethető tétel tagadása is levezethető, így az elmélet nem ér túl sokat. Azaz „bármi és egyúttal bárminek az ellenkezője is bizonyítható”.

Tartalomjegyzék

1 A Russell-paradoxon közérthető formái
- 1.1 Katalógusok
- 1.2 Színezés
2 Reakciók a Russell-paradoxonra
3 Kapcsolódó paradoxonok
- 3.1 További hasonló paradoxonok
4 Hivatkozások

[szerkesztés] A Russell-paradoxon közérthető formái

Laikusok számára is könnyen megérthető a paradoxon, ha absztrakt matematikai jelölés helyett szemléletesen magyarázzuk el. Erre tesz kísérletet az alábbi két variáció.

[szerkesztés] Katalógusok

Tegyük fel, hogy valakik elkészítik a világon lévő összes könyv összes lehetséges szempont szerinti katalógusait. A katalógusok is könyvek, így maguk is katalogizálhatóak. Egy részük tartalmazza önmagát, úgy értve, hogy a katalógus címe szerepel magában a katalógusban (pl. „A száz betűnél nem hosszabb című könyvek” katalógusába be kell hogy kerüljön maga ez a katalógus is, minthogy olyan könyv, melynek címe száz betűnél nem hosszabb). Megjegyezzük: a katalógusokról nem kell feltennünk, hogy kész, befejezett művek, gondolhatunk például folyamatosan fejlesztett adatbázisokra; melyeket egy-egy csoport állandóan fejleszt; és ha megjelenik egy új könyv, akkor minden fejlesztőcsoport eldönti, hogy szerepelnie kell-e a katalógusban, és ha igen, beleírják (különben russelli értelemben tipizált katalógusokhoz jutnánk, melyek körében az antinómia nem lép fel).

Mármost mit tegyen az a szerkesztőbrigád, amelyik az összes, önmagát nem tartalmazó katalógust listázza, vagyis „Az önmagukat nem tartalmazó katalógusok katalógusát”? Nevezzük ezt a katalógust A-nak. Előbb-utóbb a csoportnak el kell döntenie, magát az A-t beleírja-e az A katalógusba. Ha beleírják, akkor a katalógus tartalmazni fogja önmagát, tehát nem lesz „önmagát nem tartalmazó”, és így törölni kell az A-ból. Ha viszont nem írják bele, a katalógus önmagát nem fogja tartalmazni. Ekkor viszont (mivel minden önmagát nem tartalmazó katalógusnak be kell kerülnie e katalógusba) mégis bele kell írni a katalógusba, és így ott vagyunk, ahol az előbb.

Egyszóval „az önmagát nem tartalmazó” katalógusok katalógusa tartalmazza önmagát, ha nem tartalmazza önmagát; és nem tartalmazza önmagát, ha tartalmazza önmagát. Ez pedig logikai ellentmondás.

[szerkesztés] Színezés

Színezzünk a halmazokat két színnel. Legyenek pirosak a rendes halmazok, amelyek a józan észnek megfelelően nem tartalmazzák saját magukat. Piros halmaz tehát a teásbögrék halmaza, a XIII. kerületi Radnóti Miklós utcai általános iskola III.b osztályának fiú tanulóinak halmaza, a 3 cm-nél rövidebb balmenetes réz facsavarok halmaza stb., mivel maguk a halmazok természetesen nem teásbögrék, fiú tanulók vagy facsavarok.

Legyenek kékek a rendetlen halmazok, amelyek tartalmazzák saját magukat. Erre már nehezebb példát találni, de nem lehetetlen, gondoljunk például a fenti, „Száz betűnél nem hosszabb című könyvek” katalógusára, vagy a Műszaki és Természettudományi Egyesületek Szövetségére, a MTESZ-re [1], amely maga is műszaki és természettudományi egyesület lévén tagja (vagy tagja lehetne) önmagának.

Ha ez eddig világos, akkor képzeljük el, hogy valaki összegyűjti az összes piros halmazt (a fenti három példával együtt) egy nagy könyvbe. Ez a könyv persze nagyon vastag lesz (tkp. végtelenül vastag), de ezzel most ne foglalkozzunk. A nagy kérdés, hogy a könyv által felsorolt halmazok halmaza milyen színű.

Tegyük fel, hogy piros, eszerint tehát benne van a könyvben. Ha viszont benne van a könyben, akkor benne van a könyvben felsorolt halmazok halmazában is, azaz önmagában. Ha viszont tartalmazza önmagát, akkor kéknek kell lennie. Ellentmondás.
Tegyük fel, hogy kék, tehát tartalmazza saját magát, azaz eleme a könyv által felsorolt halmazok halmazának (saját magának). Ebből következik, hogy benne van a könyvben, akkor viszont kénytelen piros lenni, mert a könyvben csak piros halmazok vannak leírva. Ismét ellentmondás.

[szerkesztés] Reakciók a Russell-paradoxonra

Miután Russell felfedezte paradoxonját, minden matematikus számára világos lett, hogy a halmazelmélet abban az intuitív formában, ahogy Cantor megalkotta, nem tartható, hiszen ebben az elméletben bármilyen bizonyítható tétel tagadása is bizonyítható.

Az első választ a paradoxonra maga Russell adta. Munkatársával, Alfred North Whitehead segítségével kidolgoztak egy alternatív halmazelméletet a Principia Mathematica című munkájukban (amely nevét Isaac Newton hasonló című munkájáról, a Philosophiae Naturalis Principia Mathematica-tól kölcsönözte), ez a tipizált halmazelmélet, vagy típuselméletet. Ez lehetővé teszi az összes addig ismert halmazelméleti és matematikai eredmény levezetését, de elkerüli a paradoxonból következő ellentmondást. Ennek ellenére különféle okok miatt nem vált különösebben népszerűvé matematikusi körökben. A matematikusnak nehézkesnek és mesterkéltnek tartották az elméletet, és sokkal egyszerűbb utat találtak a halmazelmélet megreformálására

Egy másik irányzat volt a Cantor-féle naív halmazelmélet megreformálása, amelynek eredménye a modern axiomatikus halmazelmélet lett. Ez a típuselmélethez hasonlóan, nem engedi meg tetszőleges halmazok létrehozását, és így elkerüli a Russell-féle és a hozzá hasonló problémákat, ugyanakkor a típuselméletnél rugalmasabb.

Az axiomatikus halmazelméletnek több változata alakult ki, elsőként a Zermelo-Fraenkel axiómarendszer. Az axiomatikus halmazelmélet alapja az üres halmaz ({}) és néhány axióma, és csak azok a halmazok szabályosak, amelyek felépíthetők az üres halmazból az axiómák által definiált halmazműveletek (mint pl. tartalmazás, unió, metszet) használatával. A regularitási axióma, amely kizárja bizonyos önmagukat tartalmazó halmazok megkonstruálását, biztosítja, hogy nem lép fel a Russell-paradoxon. Ez az elmélet meglehetősen korlátozónak tűnhet, mégis (ha az axiómarendszert a kiválasztási axiómával is bővítjük) az addig ismert matematika egésze újra felépíthető belőle.

Egy másik elmélet, melyet (elsősorban) Neumann János dolgozott ki, a Neumann-Bernays-Gödel-axiómarendszer, a halmaz fogalmának általánosítására, az osztályéra alapoz. Eszerint az elmélet szerint R nem halmaz, hanem osztály. Ez a kis különbség szintén biztosítja, hogy nem lép fel a Russell-paradoxon.

Az elmúlt században e két halmazelmélet mellett számos más, kevésbé neves alternatív halmazelméletet is kidolgoztak, bár ezek legtöbbje nincs összefüggésben a Russell-paradoxonnal.

[szerkesztés] Kapcsolódó paradoxonok

A borbélyparadoxon, amely nagyon hasonló a Russell-paradoxonhoz.

[szerkesztés] További hasonló paradoxonok

A hazug paradoxona és az Epimenidész-paradoxon, mindkettő ókori eredetű. A hazug paradoxona nagyon alapvető, a 20. században kétszer is fontos szerepet játszott a matematikában. Először Kurt Gödel használta fel egy formalizált változatát nemteljességi tételének igazolásához. Másodszor Alan Turing bizonyította a megállási probléma eldönthetetlenségét a paradoxon segítségével
Grelling-Nelson paradoxon
Curry paradoxonja, amely a Russell-paradoxontól eltérően nem használ negációt.
Boethius-paradoxon
Cantor-paradoxon
Burali-Forti-paradoxon
Richard-paradoxon