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 set. 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 set with a property so interesting that we shall label it with a lower case letter:

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

To simplify our understanding of Russell's paradox, we consider only positive integers (1,2,3...) and sets that "involve" positive integers. Like any discipline in mathematics, requires careful attention to definitions.

Exploring our "universe" of sets, U^*

First, we need to discuss what kinds of sets we wish to consider. In the language of set theory, we need to define our "universe". We begin with the obvious sets associated with positive integers, namely, sets that contain one or more positive integers. Three such sets are shown below:

{2}, {4,2} and {1,2,6} 

It is understood that {4,2} and {2,4} are the same set, and that this set contains two integers. Two other sets immediately come to mind:

{1,2,3,4,...} and {}

The first of the two sets shown above is the set of all positive integers, while the other set is called the empty set because it contains no elements. It is convenient to give the empty set a symbol:

∅ ≡ {}

Why have we allowed ∅ to be in our "universe"? It's a matter of how we decide to define U^*. One might argue that ∅ somehow "involves" a positive integer in that it excludes positive integers. But ultimately, the argument is not one of semantics but free will. How does the author or reader wish to define the universe? In this essay, the ∅ was introduced primarily in order to highlight the use of symbols, or "labels" in discussions of set theory. It would be nearly impossible to explain Russell's paradox without being able to "label" or "name" sets.

Next, we introduce the idea that a set can contain a set by expanding our "universe" to include other types of sets that involve positive integers. Consider:

 X = {2, {2}, {2,7} },

where we have chosen to use the ubiquitous "X" of elementary algebra to represent a set that contains three elements: 2, the set that contains 2, and the set the contains both 2 and 7. Now we introduce the concept of a set that contains itself as a member.

 Y = {2,Y} = {2,  {2, {2,...} } }

Or carrying the iteration (...) one step further:

Y = { 2, Y } =  {2,  {2,  {2, {2,...}  }  }  }

The set Y contains only two elements. And, it is an example of self referencing.

• See also: Wikipedia:Wikipedia's shortest article on self-referencing

For our purposes, the "universe", U^*, contains only sets involving positive integers. We shall include sets like X and Y in our universe.

Divide our "universe" into two sets

Though this seems like a simple definition, our definition of U^* leads to a bewildering collection of sets. For example, {2}, {{2}}, and {{{2}}} are all distinctly different sets in of U^* that involve only the integer "2". Following Wikipedia's informal presentation of Russell's paradox, we define the set of all sets that do not contain themselves as elements, and call this the normal set, R. The set X described above is an element of R because X is not an element of X. But Y={2,Y} is an element of Y, and therefore, Y is not a "normal" set, or not an element of R.

X = {2, {2}, {2,7} } ∈ R
Y = {2,Y} ∉ R

Here, the symbol ∈ is introduced to denote "is in", while ∉ denotes "is not in".

Common notions

In the 19th century, mathematicians began to appreciate the complexities associated with declaring ideas to be common notions. We shall nevertheless adopt the point of view that every set either is, or is not, an element of R. And it is reasonable to include R in our universe, U^*, because R does involve positive integers.

The paradox: Is R ∈ R or is R ∉ R?

To put it bluntly,

If R is in R, then it does not contain itself, and therefore R is not in R.

But,

If R is not in R, then it is a normal set, and therefore R is in R.