Russellin paradoksi

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

Paradoksin voi esittää esimerkkinä: Kylän parturi ajaa parran ainoastaan niiltä miehiltä, jotka eivät aja omaa partaansa. Ajaako parturi oman partansa?

Formaalimmin paradoksi määritellään siten, että joukko M sisältää kaikki joukot, jotka eivät sisällä itseään. Joukko A on siis joukon M jäsen vain, jos joukko A ei ole oma jäsenensä. Paradoksi onkin, kuuluuko joukko M itseensä? 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.

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äydellisyysteoreemansa todeksi ja todisti samalla, ettei matematiikka voi olla sisäisesti täysin ristiriidaton. Myös Alan Turing käytti Gödelin tulosta todistaessaan pysähtymisongelman ratkaisemattomuuden.