Russellparadox

De russellparadox, ook antinomie van Russell genoemd, is een paradox in de naïeve verzamelingenleer over verzamelingen waarvan de elementen zelf ook weer verzamelingen zijn. De paradox toonde aan dat bepaalde pogingen om de intuïteve verzamelingenleer, zoals die door Georg Cantor geformuleerd was, te formaliseren, tot een tegenspraak leiden. De paradox veroorzaakte een schok in de wereld van de grondslagen van de wiskunde.

De paradox werd ontdekt door Ernst Zermelo in 1899, maar werd niet gepubliceerd, en werd onafhankelijk van Zermelo door Bertrand Russell ontdekt in 1900.

De paradox

Volgens de intuïteve verzamelingenleer is iedere definieerbare collectie een verzameling. Russell beschouwde verzamelingen waarvan de elementen zelf ook verzamelingen zijn. Hij onderscheidde verzamelingen die zichzelf bevatten en verzamelingen die zichzelf niet bevatten.

Een voorbeeld van een verzameling die zichzelf niet bevat, is de verzameling $BV$, bestaande uit bloemenverzamelingen:

$BV$= {tulpenverzameling, hyacintenverzameling, rozenverzameling, narcissenverzameling, ...}.

Elk element van $BV$ is zelf ook weer een verzameling. Duidelijk is dat $BV\notin BV$. Met andere woorden: $BV$ is zelf geen element van $BV$. Immers, een verzameling bestaande uit bloemenverzamelingen is zelf geen bloemenverzameling. Er zijn dus verzamelingen die zichzelf niet bevatten. Russell definieerde de verzameling $R$, de russellverzameling, van al zulke verzamelingen:

$R=\{V\mid V\notin V\}$

De verzameling $R$ is niet de lege verzameling, want de bovengenoemde verzameling $BV$ bevat zichzelf niet en is dus een element van $R$.

Russell stelde nu de vraag: "bevat $R$ zichzelf?", dus geldt er dat $R\in R\$?

Stel dat het antwoord 'ja' is. In dat geval moet $R$ voldoen aan de eigenschappen die alle elementen van $R$ bezitten en dus geldt dan dat $R\notin R$. Dus een tegenspraak.

Dan is het antwoord dus niet 'ja', maar 'nee': $R$ kan zichzelf niet bevatten: $R\notin R$. Maar dan voldoet $R$ aan de eigenschap die geldt voor de elementen van $R$, dus is $R\in R$. Ook een tegenspraak.

Het blijkt dat

$R\in R\Longleftrightarrow R\notin R$,

dus is geen van beide mogelijkheden $R\in R$ en $R\notin R$ juist.

Voor de russellverzameling is het zowel onmogelijk dat een bepaald object er wel in zit als dat het er niet in zit. Dit is de paradox van Russell.

Formele presentatie

Definieer verzamelingstheorie VT als de theorie van predicatenlogica met een binair predicaat $\in$ en het axioma:

$\exists y\forall x(x\in y\iff P(x))$

voor iedere formule P met een willekeurige variabele.

Substitueer $x\notin x$ voor $P(x)$. Dan is er een $y$ waarvoor geldt:

$y\in y\iff y\notin y$

VT is dus inconsistent.

Verband met Cantor

De paradox van Russell is sterk verbonden met het diagonaalbewijs van Cantor. Daarmee kan aangetoond worden dat de machtsverzameling van een verzameling $V$ een element bevat dat geen element van $V$ is. Neem voor $V$ de verzameling van alle verzamelingen. De machtsverzameling van $V$ is de verzameling van alle verzamelingsverzamelingen. Maar dit is zelf een deelverzameling van de verzameling van alle verzamelingen, wat een paradox is.

Past men het bewijs van Cantor toe om te bewijzen dat die verzameling desondanks groter is, dan is de russellverzameling de verzameling waarvan aangetoond wordt dat die niet in de verzameling van alle verzamelingen zit.

Men kan de moeilijkheid die volgt uit het begrip 'verzameling van alle verzamelingen' vermijden door een onderscheid te maken tussen klassen en verzamelingen. Een klasse wordt in het bijzonder een verzameling genoemd indien ze zelf element kan zijn van een andere klasse. Op deze manier is de 'verzameling van alle verzamelingen ' een klasse en geen verzameling.

Oplossing van de paradox

De paradox van Russell toonde aan dat er iets ernstig mis was met de verzamelingenleer zoals die rond 1900 bekend was. Om de paradox van Russell op te lossen, werden de axioma's veranderd. In het bijzonder werd het volgende axioma, dat tot dan toe werd aangenomen, verworpen:

• Voor elke eigenschap A bestaat de verzameling van alle dingen met eigenschap A

In plaats daarvan kwamen regels zoals:

• Voor elke verzameling V bestaat de verzameling van alle deelverzamelingen van V
• Voor elke verzameling V en elke eigenschap A bestaat de verzameling van alle elementen in V met eigenschap A

Deze regels zijn nu opgesteld zodat alle verzamelingen die in de wiskundige praktijk voorkomen door de axioma's gedefinieerd worden, maar paradoxale verzamelingen zoals de verzameling van alle verzamelingen en de russellverzameling niet.

Men onderscheidt nu predicatenlogica's van verschillende ordes:

• binnen de eerste orde predicatenlogica kan alleen over constanten en variabelen worden geprediceerd,
• binnen de tweede orde predicatenlogica kan ook over eerste-orde-predicaten geprediceerd worden,
• in het algemeen kan in n-de-orde predicatenlogica's over predicaten van orde ten hoogste n-1 worden geprediceerd.

De russellparadox wordt ook vermeden met het regulariteitsaxioma (een van de axioma's van de Zermelo-Fraenkel-verzamelingenleer), dat, in de context van een theorie waarbij elk element van een verzameling zelf een verzameling is, zegt dat een niet-lege verzameling een element heeft dat disjunct is met de verzameling. Toegepast op een willekeurige verzameling volgt hier namelijk uit dat geen verzameling element is van zichzelf, dus dat de verzameling van alle verzamelingen, die ook de verzameling zou zijn van alle verzamelingen die zichzelf niet bevatten, niet bestaat. Daarmee wordt ook de paradox voorkomen dat de machtsverzameling van de verzameling van alle verzamelingen strikt groter zou moeten zijn dan de verzameling van alle verzamelingen.

Varianten van deze paradox

Varianten van de paradox van Russell, die ogenschijnlijk binnen een ander gebied liggen maar in essentie neerkomen op dezelfde paradox, zijn:

• de catalogusparadox
• de paradox van de liegende Kretenzer
• de paradox van Grelling

Voetnoten