Russellin paradoksi

Russellin paradoksi on Bertrand Russellin vuonna 1901 keksimä paradoksi, joka todistaa Gottlob Fregen ja Georg Cantorin naiivin joukko-opin sisäisesti ristiriitaiseksi.[1]

Formaalisti Russelin paradoksi määritellään seuraavasti: Oletetaan, että joukon M alkioita ovat kaikki sellaiset (normaalit) joukot, jotka eivät kuulu itseensä. Joukko A on siis joukon M alkio vain, jos joukko A ei ole itse oma alkionsa. Paradoksi seuraa kysymyksestä, kuuluuko joukko M tällöin yhtenä alkiona itseensä? Jos kuuluisi, niin ei tulisi M:n oman määritelmän perusteella kuulua; jos taas ei kuulu, niin silloin tulisi saman määritelmän mukaan kuulua.

Matemaattisesti ongelman voi ilmaista seuraavasti: Olkoon M = { x : x∉x }. Tällöin jos M∈M, määritelmän mukaan M∉M. Vastaavasti jos M∉M, määritelmän mukaan M∈M.

Paradoksin idean voi esittää myös konkreettisena esimerkkinä, esimerkiksi kuuluisalla parturin paradoksilla: oletetaan, että kylän parturi ajaa parran niiltä ja vain niiltä kyläläisiltä, jotka eivät aja omaa partaansa. Ajaako hän tällöin oman partansa? Jos parturi ajaa oman partansa, hän ei aja omaa partaansa ja kääntäen.

Russellin paradoksin keksiminen johti aksiomaattisen joukko-opin keksimiseen. Nykyään puhutaankin, että M = { x : x∉x } on luokka eikä joukko. Aksiomaattisen joukko-opin kehittämiseen vaikutti suuresti Kurt Gödel. Hän todisti epätäydellisyyslauseensa todeksi ja todisti samalla, ettei matematiikkaa voi osoittaa sisäisesti täysin ristiriidattomaksi. Myös Alan Turing käytti Gödelin tulosta todistaessaan pysähtymisongelman ratkaisemattomuuden.