A Note on Russell’s Paradox

A Note on Russell’s Paradox

Topics in mathematics very frequently rely on set theory (I am hard-pressed to quickly think of one that doesn’t). Set theory itself is a very abstract area of study. Even so, mathematicians built it on axioms (self-evident truths taken as fundamental starting points), and, of course, debate continues to this day as to which axioms are the best/most efficient.

As mathematicians delight in doing, one can begin with these axioms and search for boundaries. That is, ask the question, “What can I get away with while still following these rules?” And paradoxes can follow. Here set theory is no exception. But paradoxes aren’t the end of the world; on the contrary, they can be nicely illuminating. Taking just one of the first principles of axiomatic set theory, one can arrive at a substantial fact of mathematics, while in the course of uncovering a well-worn conundrum.

This post, of course, concerns Russell’s Paradox, as covered in Naïve Set Theory by Paul Halmos. I highly recommend the book to readers who enjoy the discussion to follow; it is a wonderfully readable treatment of axiomatic set theory.

A Few Definitions & Notations

Throughout, the word set refers to a general collection of objects; note these objects may themselves be sets. The symbol \in denotes belonging to a set, and will translate x\in A to mean any of the following equivalent expressions in English:

  • x is an element of A;
  • x belongs to A;
  • x is a member of A.

Similarly, \notin denotes not belonging. A set will also be noted with curly braces, e.g., \{all real numbers\}. Sometimes variables are used as well, as in 

\{x\in S\mathrel{:}x>5\},

read as the set of all x belonging to S such that x is greater than 5.

Finally, a contradiction is any mathematical statement which is always false. (Contradictions are not allowed to exist.1) An example of the ‘canonical contradiction’ insists a statement and its negation are true all at once. Take the clause ‘n>8 and n\leq8,’ for instance. These properties cannot simultaneously hold for any number n, otherwise said the statement is false for all numbers n.

Axiomatic Set Theory

As with most branches of mathematics, set theory has been axiomatized, more than once, as mentioned earlier. In order to come to the mathematical understanding I focus on in this post, we only need one of these building blocks.

Axiom (Specification). Given a set A and a property p, there is a set B whose elements are exactly those elements of A for which p is true.

This axiom lays the ground for defining sets in terms of existing ones. All partitioning, categorizing, classifying, and so forth make use of this. As an example, we can speak of the set of all positive integers, \mathbb{N}=\{1,2,3,\ldots\}, and specify a subset like the set of all even positive integers:

\{2,4,6,\ldots\}=\{n\in\mathbb{N}\mathrel{:}n\text{ is even}\}.

Put plainly, given a set, you can create a new one (referred to as a subset) meeting criteria of your choosing. And it’s the choosing that makes set theory so fun. With that, let’s make a choice, and see what we can get away with while following this rule.

Russell’s Paradox

First we suppose a set A is given; here A can be any set you like (odd positive integers, irrational numbers, even the set of your long-term goals).

Next define the property p(x) to mean x\notin x. That is, p(x) is true if, and only if, x\notin x.

Let’s stop for a moment and consider p(x). You might think it nonsensical, but it can be seen to hold even in the physical sense, e.g., a box is not contained in itself, even when it contains several smaller boxes. For a math example, the set of natural numbers is not itself a natural number, so \mathbb{N}\notin\mathbb{N}. (Perhaps less reasonable is the opposite x\in x, but that can be saved for another discussion.

With a touch of grandeur, you may now INVOKE the Axiom of Specification to create a new set

B=\{x\in A\mathrel{:}p(x)\}=\{x\in A\mathrel{:}x\notin x\}.

To clarify, this means that in order for it to be true that y\in B, then it must be the case that y\in A and y\notin y. As you might have guessed, the definition of B is less interesting than what we can do with it. On that note, a query:

Is it possible that B\in A?

This question, relatively easily posed, quickly leads to trouble. Let’s examine.

By specifying the new set B by way of the property p(x), we split membership in A. If y\in A, then either y\in B or y\notin B, by definition.

Now we apply that to B, and investigate both cases. If we suppose B\in A:

  • Case 1. If B\in B, then p(B) is untrue. By definition of p(B), it follows B\notin B, a contradiction.  
  • Case 2. If B\notin B, then p(B) is true. But this means B\in B, a contradiction again.

As all our options yield contradictions, the assumption that B\in A in the first place must have been a faulty one2. That is, it can only be the case that B\notin A.

The arrival at a contradiction under all possible cases above is known as Russell’s Paradox, attributed to its first recorded discoverer, the logician Bertrand Russell.

Conclusion (Why does this matter?)

The abstract nature of set theory makes it somewhat easy to regard Russell’s Paradox as more a minor mathematical curiosity/oddity than, say, The Fundamental Theorem of Calculus. In particular, the discussion above only makes use of nondescript sets and minimally defined elements thereof.

Unlikely as it may seem, the importance lies in leaving the set A arbitrary. Remember, we said let A be any set you like. And still we found something that cannot possibly belong to that arbitrary set. Even leaving almost nothing to specifics, we created something necessarily separate.

What this means is that no set which contains everything can exist. There is no ‘universal’ set in mathematics. A frame of reference cannot be truly complete. Indeed, that speaks even to the axiomatic system by which we derived this very fact!3 No matter how ‘large’ the set, there exists something apart from it. On a further philosophical lean, there is always room to take a grander view and think outside the present mode, to pick up something new.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Footnotes

  1. This itself is taken as an axiom of propositional logic. Useful theory is much harder to come by without it.
  2. The preceding paragraph is essentially a proof by contradiction that A.
  3. Axiomatic systems are not without their limitations, despite strong design and good intentions. In particular, one axiomatization of set theory, called ZFC (for Zermelo-Fraenkel with Axiom of Choice) is proven inadequate for proof or disproof of The Continuum Hypothesis.

One thought on “A Note on Russell’s Paradox

Leave a Reply

Your email address will not be published. Required fields are marked *