Russell-paradoxon

A Russell-paradoxon Bertrand Russell 1901-ben felfedezett matematikai logikai, ill. 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 olyan érvelést használ, amelyhez hasonlóak tulajdonképp már több ezer éve ismertek voltak (ld. Epimenidész-paradoxon). Azt, hogy a paradoxonhoz vezető érvelés a halmazelmélet ill. logika matematikai elméletének ellentmondásosságát okozhatja, többen is felfedezték a tizenkilencedik század végén; például Ernst Zermelo matematikus és Bertrand Russell filozófus.

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?

1. 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.
2. 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ó”.

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 tesznek kísérletet az alábbi variációk:

A borbélyparadoxon

Tegyük fel, hogy a laktanya katonai borbélya a szolgálati szabályzatnak megfelelően csak azokat a katonákat borotválja, akik maguk nem borotválkoznak, de nem borotválhatja azokat, akik maguk borotválkoznak. Kérdés: magát megborotválhatja-e? Ha megborotválja magát, akkor olyan katonának számít, aki maga borotválja magát, ergo a szolgálati szabályzat megtiltja, hogy megborotválkozzon. Ha ennek megfelelően, nem borotválkozik, akkor a szolgálati szabályzat értelmében, olyan katonának számít, akit borotválnia kell. Bármit is tesz tehát: akár megborotválja magát, akár nem, vét a szolgálati szabályzat ellen.

Ez valóban tekinthető a Russell-paradoxon átfogalmazásának. Legyen L a laktanya katonáinak halmaza, és jelölje x∈y azt, hogy az y katona borotválja az x katonát (x,y L-beliek). Mármost a b borbély épp azokat a katonákat borotválja, akik nem borotválkoznak maguk, vagyis amelyekre igaz x∉x. Tehát x∈b :⇔ x∉x (hasonlóan, a halmazelméleti modellhez, ahol az R halmaz így is definiálható: x∈R :⇔ x∉x). A „megborotválja-e magát a borbélyt?” kérdés halmazelméleti megfelelője: igaz-e b∈b? A Russell-paradoxonhoz hasonlóan az x∈b :⇔ x∉x -ben x helyére b-t helyettesítve adódik az ellentmondás: b∈b :⇔ b∉b.

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 (például „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 önmagukat 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.

Színezés

Színezzünk a halmazokat két színnel. Legyenek pirosak a rendes halmazok, amelyek 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ű.

1. Tegyük fel, hogy piros, eszerint tehát benne van a könyvben. Ha viszont benne van a könyvben, 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.
2. 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.

Karinthy-paradoxon

Egyik művében Karinthy Frigyes így ír:

„Ohó álljunk csak meg. Ön azt mondja, a rögeszmém, hogy őrült vagyok. De hiszen tényleg az vagyok, az imént mondta. De hiszen akkor ez nem rögeszme, akkor az egy logikus gondolat. Tehát nincs rögeszmém. Tehát mégse vagyok őrült. Tehát csak rögeszme, hogy őrült vagyok, tehát rögeszmém van, tehát őrült vagyok, tehát igazam van, tehát nem vagyok őrült. Mégiscsak gyönyörű dolog a tudomány!”

(Karinthy Frigyes: Őrült sikerem a tébolydában [2])

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élet. 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 matematikusok 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 naiv 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 például 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.

Kapcsolódó paradoxonok

• A hazug paradoxona és az Epimenidész-paradoxon egyaránt ó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
• Mirimanoff-paradoxon

Hivatkozások

A magyar Wikikönyvekben
további információk találhatók

Russell-paradoxon témában.

• A Russell-paradoxon és logikai háttere (angol nyelven, IEP)