Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

The Book of
Foundational Mathematics

Detailed Contents

Propositional Logic
  1. Propositions
  2. Modeling Logic with Truth Tables
  3. Logical Equivalence
  4. The Laws of Logic
  5. Application: Switching Networks
  6. Logical Implications
  7. Propositions with Variables
  8. Quantifiers
  9. Logic with Quantified Statements
  10. Nested Quantifiers
  11. Application: Logic Puzzles
  12. A Primer on Fuzzy Logic
  1. Mathematical Logic with Maple
  2. Defining Propositions with Maple
Arguments and Proof
  1. The Structure of Basic Arguments
  2. Rules of Inference
  3. Using the Rules of Inference
  4. Logically Equivalent Arguments
  5. Invalid Arguments
  6. Universal Specification
  7. Universal Generalization
  8. Axioms, Definitions, Theorems, and Proofs
  9. Proof Technique: Direct Proofs
  10. Proof Technique: Indirect Proofs
  11. Proof Technique: Contradiction
  12. Mistakes in Proofs
  13. Proof Technique: Equivalence
  1. Verifying Mathematical Arguments in Maple
Set Theory
  1. Sets
  2. Subsets
  3. Proof Technique: Element Arguments
  4. A Set of Operations on Sets
  5. The Laws of Set Theory
  6. Proof Technique: Exhaustion
  7. Russell’s Paradox and a Formal Resolution
  1. Set Theory in Maple

Russell’s Paradox and a Formal Resolution

Sets are a powerful abstraction that allows us to collect a wide variety of objects into one structure. Typically, all objects within the set share some common characteristic other than mere inclusion in the set. They may be points on the plane, equilateral triangles, even numbers, or even fruits.

As powerful as sets are, we have not given a formal definition of what a set is. We have been relying on an intuitive definition, and though it works well enough for our purposes, sooner or later the cracks start to show. Sometime around 1901, a mathematician named Bertrand Russell formulated his now infamous paradox that seemed to dismantle the entire theory of sets. The scary thing about the paradox is that a lot of mathematical research and important results rested on the foundations of Set Theory. If Set Theory is wrong, are all results depending on sets wrong as well?

In this section, we’ll eek out what this paradox is, and hint at a solution that solves the problem.

Sets That Are Members of Other Sets

Over the course of this chapter, we’ve defined sets that mostly have numbers, though we’ve constructed other more intricate sets. Sometimes, we’ve constructed sets that contain other sets.

Example 3.7.1

Let’s consider two different sets:

A={ 1, 2, 3 }
B={ 1, 2, 3, {1, 2, 3} }

Here, we can see that B contains the set {1, 2, 3} as an element, which is something we’ve seen before, but we’re going to rewrite set B to make it more obvious that it contains a different set:

B = { 1, 2, 3, A }.

We’ve got a handle on this situation, but let’s ask a more interesting question:

Can a Set Contain Itself?

What would it look like for a set to contain itself? Let’s see if we can make such a set.

Example 3.7.2

Let’s consider the set

☒ = {1}.

Does ☒ contain the set {1} as an element? Of course not! We see that right now, ☒ only contains a single element, which is a number.

Let’s redefine ☒ to contain the set {1} as well:

☒ = { 1, {1} }.

Does ☒ contain itself now? Not quite, because now ☒ contains two elements, one of which is a number, and the other one being a set. Instead the set

{ 1, {1}, {1, {1}} }

contains 1, {1}, and ☒, but this set is not the same thing as

{ 1, {1} }

which is what we’ve defined ☒ to be.

Let’s try again, this time including the set { 1, {1} }:

☒ = { 1, {1}, {1, {1}} }.

Of course, we run into the same problem. The sets

{ 1, {1}, {1, {1}} }{ 1, {1}, {1, {1}}, { 1, {1}, {1, {1}} } }

are not the same. We see that the set on the right could be written as {1, {1}, {1, {1}}, ☒}.

It seems that no matter how many iterations we perform, we never quite get a set that contains itself. The only thing we may be able to do is to think about what would happen if we continue this process indefinitely:

☒ = { 1, {1}, {1, {1}}, {1, {1}, {1, {1}}}, … }.

Does this version of ☒ contain itself as a member? This is a harder question to ask because we are now dealing with an infinite set.

Determining if a set is contained in another set when both sets contain infinitely many elements takes some care, and so we will sidestep that issue by considering the following set:

☒ = { S | S is a set ∧ S ∉ S }.

What kind of set is ☒? It’s a set whose elements are sets. But these are special sets. In Example 3.7.2, we were concerned with what a set that contains itself would look like. Here, we don’t scrutinize whether a given set contains itself. Instead we are just assuming that we’ve somehow curated every set, and are only including sets that do not contain themselves.

Now consider the following question: is ☒ contained within ☒? Remember that for propositions such as

☒ ∈ ☒

there are only two possibilities: either

☒ ∈ ☒ = 0☒ ∈ ☒ = 1

Let’s consider both possibilities.

Case 1: ☒ ∈ ☒ = 0

Here, we are considering the possibility where ☒ does not contain itself.

Well, since ☒ ∉ ☒, we know that

☒ ∉ ☒⟹¬(☒ is a set ∧ ☒ ∉ ☒)
⟹¬(☒ is a set) ∨ ¬(☒ ∉ ☒)
⟹☒ is not a set ∨ ☒ ∈ ☒

However, notice what the logical implications are if ☒ ∉ ☒: either ☒ is not a set (it is, so this would be a contradiction) or ☒ ∈ ☒ (which contradicts the supposition that ☒ ∉ ☒.) Either way, the proposition ☒ ∉ ☒ yields contradictions. As such, we may suspect that ☒ ∈ ☒ = 1. Let’s check.

Case 2: ☒ ∈ ☒ = 1

Suppose we somehow knew that ☒ ∈ ☒.

☒ ∈ ☒⟹☒ is a set ∧ ☒ ∉ ☒
⟹☒ ∉ ☒

So, by assuming ☒ ∈ ☒, the logical implication is that ☒ ∉ ☒? This is a clear contradiction

At this point, both cases yield contradictions. This could be a problem, but solutions do exist.

Resolving the Paradox

How come we’ve not had this problem dealing with any of the previously defined sets in this chapter? It has to do with the fact that we were constructing sets with particular objects. Even numbers are easy to grasp, quadrilaterals are easy to grasp, but abstract set requirements are not so easy to grasp. We even had trouble trying to come up with a set that contained itself in Example 3.7.1.

While not a resolution to the paradox, defining sets using easy-to-grasp elements does at least avoid the issue.

Perhaps the most commonly used formal system of Set Theory is ZFC Set Theory. ZFC is short for

Zermelo – Fraenkel – Choice

where Zarmelo and Fraenkel are the two mathematicians who formulated this type of Set Theory, and the word choice refers to the Axiom of Choice, which is something that will be examined later in this book.

ZFC Set Theory came around in the early 20th century, and is free of paradoxes like Russell’s Paradox. ZFC Set Theory is an intricate system, and requires some more advanced mathematics to understand. While not discussed in this book, you can find more information on ZFC Set Theory from Brilliant. While more difficult to parse through, this Wikipedia article contains a very thorough overview and history of ZFC Set Theory.

This Wikipedia article offers a lot of detail on the history of Russell’s Paradox, and how it inspired the search for more axiomatic systems of Set Theory.