7.3: The Logic of Sets

Russell’s Paradox

Reasoning naively about sets turns out to be risky. In fact, one of the earliest attempts to come up with precise axioms for sets in the late nineteenth century by the logician Gotlob Frege, was shot down by a three line argument known as Russell’s Paradox⁴ which reasons in nearly the same way as the proof of Cantor’s Theorem 7.1.11. This was an astonishing blow to efforts to provide an axiomatic foundation for mathematics:

Russell’s Paradox

Let \(S\) be a variable ranging over all sets, and define

\[\nonumber W ::= \{S \mid S \notin S\}.\]

So by definition,

\[\nonumber S \in W \text{ iff } S \notin S,\]

for every set \(S\). In particular, we can let \(S\) be \(W\), and obtain the contradictory result that

\[\nonumber W \in W \text{ iff } W \notin W.\]

The simplest reasoning about sets crashes mathematics! Russell and his colleague Whitehead spent years trying to develop a set theory that was not contradictory, but would still do the job of serving as a solid logical foundation for all of mathematics.

Actually, a way out of the paradox was clear to Russell and others at the time: it’s unjustified to assume that \(W\) is a set. The step in the proof where we let \(S\) be \(W\) has no justification, because \(S\) ranges over sets, and \(W\) might not be a set. In fact, the paradox implies that \(W\) had better not be a set!

But denying that \(W\) is a set means we must reject the very natural axiom that every mathematically well-defined collection of sets is actually a set. The problem faced by Frege, Russell and their fellow logicians was how to specify which well-defined collections are sets. Russell and his Cambridge University colleague Whitehead immediately went to work on this problem. They spent a dozen years developing a huge new axiom system in an even huger monograph called Principia Mathematica, but for all intents and purposes, their approach failed. It was so cumbersome no one ever used it, and it was subsumed by a much simpler, and now widely accepted, axiomatization of set theory by the logicians Zermelo and Fraenkel.

The ZFC Axioms for Sets

A formula of set theory⁵ is a predicate formula that only uses the predicates “\(x = y\)” and “\(x \in y\).” The domain of discourse is the collection of sets, and “\(x \in y\)” is interpreted to mean that \(x\) and \(y\) are variables that range over sets, and \(x\) is one of the elements in \(y\).

It’s generally agreed that, using some simple logical deduction rules, essentially all of mathematics can be derived from some formulas of set theory called the Axioms of Zermelo-Fraenkel Set Theory with Choice (ZFC).

For example, since \(x\) is a subset of \(y\) iff every element of \(x\) is also an element of \(y\), here’s how we can express \(x\) being a subset of \(y\) with a formula of set theory:

\[\label{7.3.1} (x \subseteq y) ::= \forall z. (z \in x \text{ IMPLIES } z \in y). \]

Now we can express formulas of set theory using “\(x \subseteq y\)” as an abbreviation for formula (\ref{7.3.1}).

We’re not going to be studying the axioms of ZFC in this text, but we thought you might like to see them—and while you’re at it, get some practice reading quantified formulas:

Extensionality. Two sets are equal if they have the same members.

\[\nonumber (\forall z. z \in x \text{ IFF } z \in y) \text{ IMPLIES } x = y.\]

Pairing. For any two sets \(x\) and \(y\), there is a set, \(\{x, y\}\), with \(x\) and \(y\) as its only elements:

\[\nonumber \forall x, y. \exists u. \forall z. [z \in u \text{ iff } (z = x \text{ OR } z = y)]\]

Union. The union, \(u\), of a collection, \(z\), of sets is also a set:

\[\nonumber \forall z. \exists u. \forall x. (\exists y. x \in y \text{ AND } y \in z) \text{ IFF } x \in u.\]

Infinity. There is an infinite set. Specifically, there is a nonempty set, \(x\), such that for any set \(y \in x\), the set \(\{y\}\) is also a member of \(x\).

Subset. Given any set, \(x\), and any definable property of sets, there is a set containing precisely those elements \(y \in x\) that have the property.

\[\nonumber \forall x. \exists z. \forall y. y \in z \text{ IFF } [y \in x \text{ AND } \phi(y)]\]

where \(\phi(y)\) is any assertion about \(y\) definable in the notation of set theory.

Power Set. All the subsets of a set form another set:

\[\nonumber \forall x. \exists p. \forall u. u \subseteq x \text{ IFF } u \in p.\]

Replacement. Suppose a formula, \(\phi\), of set theory defines the graph of a function, that is,

\[\nonumber \forall x, y, z. [\phi(x, y) \text{ IFF } \phi(x, z)] \text{ IMPLIES } y = z.\]

Then the image of any set, \(s\), under that function is also a set, \(t\). Namely,

\[\nonumber \forall s \text{ } \exists t \text{ } \forall y. [\exists x. \phi(x, y) \text{ IFF } y \in t].\]

Foundation. There cannot be an infinite sequence

\[\nonumber \cdots \in x_n \in \cdots x_1 \in x_0\]

of sets each of which is a member of the previous one. This is equivalent to saying every nonempty set has a “member-minimal” element. Namely, define

\[\nonumber \text{member-minimal}(m, x) ::= [m \in x \text{ AND } \forall y \in x.y \notin m].\]

Then the foundation axiom is

\[\nonumber \forall x. x \neq \emptyset \text{ IMPLIES } \exists m. \text{member-minimal}(m, x).\]

Choice. Given a set, \(s\), whose members are nonempty sets no two of which have any element in common, then there is a set, \(c\), consisting of exactly one element from each set in \(s\). The formula is given in Problem 7.28.

Avoiding Russell’s Paradox

These modern ZFC axioms for set theory are much simpler than the system Russell and Whitehead first came up with to avoid paradox. In fact, the ZFC axioms are as simple and intuitive as Frege’s original axioms, with one technical addition: the Foundation axiom. Foundation captures the intuitive idea that sets must be built up from “simpler” sets in certain standard ways. And in particular, Foundation implies that no set is ever a member of itself. So the modern resolution of Russell’s paradox goes as follows: since \(S \notin S\) for all sets \(S\), it follows that \(W\), defined above, contains every set. This means \(W\) can’t be a set—or it would be a member of itself.

 

⁴Bertrand Russell was a mathematician/logician at Cambridge University at the turn of the Twentieth Century. He reported that when he felt too old to do mathematics, he began to study and write about philosophy, and when he was no longer smart enough to do philosophy, he began writing about politics. He was jailed as a conscientious objector during World War I. For his extensive philosophical and political writing, he won a Nobel Prize for Literature.

⁵Technically this is called a first-order predicate formula of set theory