Russell's paradox

The powerset for a universe of three elements consists of eight possible sets. For readers who have studied combinations and/or Pascal's triangle: There is $\textstyle {\binom {3}{3}}=1$ way place all three elements in a subset (i.e., select 3 elements from a universe of three elements.) There are $\textstyle {\binom {3}{2}}=3$ ways to select 2 elements, $\textstyle {\binom {3}{1}}=3$ ways to select 1 element, and $\textstyle {\binom {3}{0}}=1$ one way to create the null set (i.e., select zero objects.) ${\displaystyle }$

• See also Russell's paradox and Paradoxes of set theory on Wikipedia

Russell's paradox resembles Pinocchio paradox in that it involves self-referencing. Pinocchio's words are in conflict with his nose: If his words are true, his nose would not grow. But since his nose is growing, we know his words are false. In short:

• His words are false if his words are true.
• His words are true if his words are false.

With Russell's paradox, the self-referencing conflict is between a set's definition and the items that are in the set. The paradox is important when sets are allowed be contain sets as members, as is the case with the pair of sets used to define surreal numbers.

In naive set theory, the universe is a collection that contains all the entities under consideration for membership in a set. The figure to the right corresponds to a universe that consists of three elements: $a$, $b$, and $c.$ The powerset consists of all sets that one can construct from these three elements (including the null set, $\Phi \equiv \{\;\},$ and the universe, $U\equiv \{a,b,c\}.$

When set theory gets complicated

We begin with a simple (naive) version of set theory based on the integers $1$ and $2$. For a universe $U$ with only two elements, the powerset contains four elements: $P(U)=\{\Phi ,A,B,U\}.$

$\Phi =\{\,\},\;$$\,\;A=\{1\},\;$ $\;B=\{2\},\;$ and $\;U=\{1,2\}=\{2,1\}.$

Great complexity results from what will turn out to be a failed attempt to define an alternate "universe" that we shall call $U^{*},$ that includes not only $1$ and $2,$ but all sets associated with this pair of integers. It is obvious that $U^{*}$ contains an infinite number of elements. For example, consider $A_{1}=\{A\}=\{\{1\}\},$ $A_{2}=\{A_{1}\}=\{\{\{1\}\}\},$ and $A_{3}=\{\{\{\{1\}\}\}\}.$This brings us to a collection of entities that can be defined recursively

$$A_{n+1}=\{A_{n}\}.$$

Letting $n$ go to $\infty$ yields:

$$A_{\infty }=\lim _{n\to \infty }A_{n}=\{\{\{\ldots \{\{\{\,1\,\}\}\}\ldots \}\}\}$$

This set contains itself, in that $A_{\infty }$ is an element of $A_{\infty }.$ Another set that contains itself is,

$$b=\{2,b\}=\{2,\{2,b\}\}=\{2,\{2,\{2,b\}\}\}=\ldots .$$

Curiously, Russell's paradox involves not sets that contain themselves as members (e.g., $a$ and $b,$) but sets where no member of the set in question is that set. This collection of sets that do not contain themselves includes not only the aforementioned power set $(\{1\},\{2\},\{1,2\},\{\,\}),\,$ but an infinite number of other sets that do not contain themselves. For example,

$$c=\{2,\{2\},b\}$$

does not contain itself, despite the fact that the third member of $c$ does contain itself.

Defining R as the set of all sets that do not contain themselves

Given the original elements 1 and 2, permitting sets to be elements greatly expands the "universe". Russell's paradox involves the set we shall call $R,$ which is the set of all sets that do not contain themselves as members.

The paradoxical question is whether $R$ is a member of $R.$ In other words: Is$R\in R?$ Or is $R\not \in R?$ Both statements violate the definition of $R.$

In symbols:

${\text{Let }}R=\{x\mid x\not \in x\}{\text{, then }}R\in R\iff R\not \in R$