Set Theory

Why Sets?

We want to put math on a solid foundation so we know that we are not talking nonsense.

If we can reduce everything down to a few very basic concepts and rules that people can agree upon, then show how to carefully and systematically derive all of mathematics from them, building things up in a way everyone can agree is valid, we can have confidence that mathematics does what it is supposed to do.

For many people, sets are the basic concept.

A set is a carefully constructed collection of objects. In most set theories, sets contain only other sets as elements. Sets all the way down. This gives sets a very minimal feel—great for a foundational concept.

It is kind of surprising that this works, but it does.

History

Many, many histories of the development of Set Theory have been written. Thousands, probably. But the big event that you really need to know was this: Gottlob Frege was working on a project in which the idea of a set as any collection of objects defined by a property was central. Bertrand Russell wrote to him and pointed out that allowing sets for any conceivable property allowed for the self-contradictory set of all sets that do not contain themselves, now known as Russell’s Paradox. A set cannot just be any collection.

So what to do about this? We have to construct, somehow, a rigorous theory of sets that is free of this (and all other, we hope) paradoxes. Different folks have proposed ways to do so, leading to different theories of sets. Some, like ZF and its relatives, make self-containing sets impossible to write. Some, like NF, allow such sets but get around the root problem with stratification. Others, like NBG, distinguish sets and classes.

There are other ways in which set theories differ from each other. Some set theories allow for the existence of items that are not sets, but that can be members of sets. They’re called urelements. ZFC explicitly rejects these because foundations are simpler without them, and they don’t really add any expressive power.

Here are a few theories that are particularly notable:

• ZF and ZFC: Zermelo-Fraenkel Set Theory, with ZFC being the version that includes the Axiom of Choice. The most widely-known and studied set theory, forming, for many people, the standard foundation for much of modern mathematics. Avoids Russell’s Paradox by completely disallowing self-containing sets.
• NBG: Von Neumann–Bernays–Gödel Set Theory. A set theory that extends ZF by distinguishing sets and classes, where classes can be collections of sets that are too large to be sets themselves, avoiding Russell’s paradox. One awesome feature is that it is finitely axiomatizable, unlike ZF, which requires (as we’ll see below) axiom schemas.
• NF and NFU: New Foundations and New Foundations with Urelements. Uses stratification to avoid paradoxes while allowing some self-containing sets. Like NBG, it is finitely axiomatizable. Created by the logician W. V. Quine.
• MK: Morse–Kelley Set Theory. Closely related to NBG, distinguishing sets and classes, but not finitely axiomatizable.
• KP: Kripke–Platek Set Theory. Roughly the predicative part of ZFC and thus much weaker.
• CST: Constructive Set Theory. A version of set theory compatible with constructive mathematics, i.e., mathematics that avoids the law of excluded middle.

ZFC is the Big One

The bulk of these notes will cover ZFC. We may, rarely, if at all, talk about other ones. ZFC is really a standout. It’s the one most people know, and the one most people think of when they think of Set Theory. If we ever talk about a different theory, we’ll be sure to point out that we are doing so.

And oh yeah, ZFC has even been called One of Humankind’s Great Inventions

Basic Notation

Time to get formal.

Surprisingly, all we need is $\in$.

Let’s begin with notation:

• $x \in A$ is defined to mean $x$ is an element of $A$.
• $x \notin A$ sugars $\neg(x \in A)$, and is read “$x$ is not an element of $A$.”
• $A \subseteq B$ sugars $\forall x. x \in A \supset x \in B$, and is read “$A$ is a subset of $B$.”

To define and work with sets, we assume that first-order predicate logic already exists, and build set theory on top of it. The most popular set theory, ZFC, gives us axioms that tell us what sets are and how sets behave. Sets have to be defined carefully: we cannot, as we mentioned above but is worth repeating, define a set by any property whatsoever, as this would allow “the set of all non-self-containing sets” which is self-contradictory nonsense.

There is a lot of notation in Set Theory, so more sugar will be warranted. We’ll be using:

$\begin{array}{lcl} \forall x \in A. P & \textrm{to sugar} & \forall x.\, x \in A \supset P \\ \exists x \in A. P & \textrm{to sugar} & \exists x.\, x \in A \land P \\ \forall x\,y \in A. P & \textrm{to sugar} & \forall x. \forall y.\, x \in A \land y \in A \supset P \\ \exists x\,y \in A. P & \textrm{to sugar} & \exists x. \exists y.\, x \in A \land y \in A \land P \\ \end{array}$

Other notation will be defined as needed.

The Axioms of ZFC

A formal theory needs a syntax, a semantics, and inference rules. Recall (from our notes on logic) that inference rules without premises are called axioms. ZFC is pretty much a formal theory that adds axioms specifically for sets on top of first-order predicate logic.

There are many ways to choose the axioms of ZFC. Here we’re listing many that are well-known. They are not all mutually exclusive (i.e., some can be derived from others), but they are internally consistent and cover everything that should be covered, and that’s all that matters.

We haven’t defined functions yet, but thinking in terms of functions makes the axiom a bit easier to understand. We’ll go deeper into this in class to understand how the intuitive notion of a function is captured by the axiom.

Unlike the other axioms, this one is philosophically controversial. It asserts the existence of a choice function without telling you how to construct one—and for infinite (especially uncountable) collections of sets, there may be no way to describe such a function explicitly. You’re just allowed to assume it exists.

Encoding Objects in ZFC

Now we know what sets are. To have Set Theory as a foundation for mathematics, we need to be able to encode every mathematical object as a set. But how? Here are some encodings people have invented:

Object	Encoding in Set Theory
Natural Numbers	$0 = \varnothing$ $1 = \{0\} = \{\varnothing\}$ $2 = \{0, 1\} = \{\varnothing,\{\varnothing\}\}$ $3 = \{0,1,2\} = \{\varnothing,\{\varnothing\},\{\varnothing,\{\varnothing\}\}\}$ $4 = \{0,1,2,3\}$ ... $n = \{0,1,2,\ldots,n-1\}$ ...
Booleans	$\textsf{false} = 0$ $\textsf{true} = 1$
Ordered Pairs	$(a, b) = \{\{a\}, \{a, b\}\}$
Tuples	Ordered pairs that “nest” to the right
Relations	Sets of ordered pairs
Functions	Relations in which each left element is unique
Structures	Custom arrangements of elements often with tags that carry meaning in a given context
Sequences	Functions from $\{0, 1, \ldots, n\}$ to some set, representing an ordered list of elements
Lists	Nested pairs in which the innermost pair has the form $(x, \varnothing)$
Characters	Natural numbers (interpreted as code points)
Strings	Lists of characters
Integers	Sets of all pairs of natural numbers $(a, b)$ with the same difference $a - b$
Rational Numbers	Sets of all pairs of integers $(a, b)$ with $b \neq 0$ with the same quotient $\frac{a}{b}$
Real Numbers	Sets of rational numbers with no lower bound, no greatest element, and for any rational number in the set, contains all rational numbers less than that value

Details will come momentarily. For now, simply appreciate that everything does seem to be encodable with sets, which is why Set Theory has become so effective and popular.

As we go through these encodings, you’ll note that many different kinds of objects have the same structural encodings, but their behaviors may be radically different. The following two exercises should help illustrate this point.

Natural Numbers

The Axiom of Infinity states that a certain infinite set exists, one we call $\mathbb{N}$, We call the elements of this set the natural numbers and denote them $0, 1, 2, 3, \dots$. Formally, $0$ is the empty set $\varnothing$, $1$ is $\{\varnothing\}$, $2$ is $\{\varnothing, \{\varnothing\}\}$, and so on, with each number being the set of all preceding numbers.

This is worth stating again. Any natural number $n$ is encoded as:

$$ \{ 0, 1, 2, \dots, n-1 \} $$

Interesting this works for $0$, which is encoded as $\varnothing$.

Booleans

In ZFC, the value $\textsf{false}$ is encoded as 0, and $\textsf{true}$ is encoded as 1.

We call the set of all boolean values $\mathbb{B}$, so $\mathbb{B} = \{\textsf{false}, \textsf{true}\}$. Note that this is indeed $\{ 0, 1 \}$, which is, you no doubt recalled from just seconds ago, just $2$.

Pairs

A pair is a ordered collection of two elements. Since it is ordered, we cannot just encode $(a,b)$ as $\{a,b\}$, because $\{a,b\} = \{b,a\}$ by the Axiom of Extensionality. So we have to come up with something better.

Kuratowski found a good encoding, which is the most common one used today: the pair $(a,b)$ is represented as the set $\{\{a\}, \{a,b\}\}$.

The encoding works great in practice, but gives off strange vibes if you look too closely.

Relax

Such oddities are a natural result of building everything from sets. One need only worry about encodings when dealing with foundations; in practice, separate all the different kinds of objects into different kinds of things and don’t mix them up. It’s not that hard.

Let’s define something to make our lives easier. The set of all pairs $(a, b)$ whose first element comes from $A$ and the second from $B$ will be denoted $A \times B$. We can define it as:

$$A \times B =_{\small{\textrm{def}}} \{ z \in \mathcal{P}(\mathcal{P}(A \cup B)) \mid \exists a \in A. \exists b \in B. z = (a, b) \}$$

Again, this is just an encoding. You may sometimes see folks write:

However, this is not legal, since (the Axiom of Separation tells us) the left-hand side of the $\mid$ must be an expression of the form $x \in S$ where $S$ is an existing set (of which we are trying to make a subset from), but in this failed definition this set is implicitly...$S$ itself—the set they are trying to define. However, once $A \times B$ is properly defined, it can be used as a set that can be subsetted.

Here’s more sugar. We can pattern match on the left-hand side tuple pattern writing:

$$\{(a, b) \in A \times B \mid a = b\}$$

for:

$$\{z \in A \times B \mid \exists a. \exists b. z = (a, b) \land a = b\}$$

Pairs are going to come up very often.

Tuples

Objects such as $()$, $(21,F)$, $(a,a,b,a,b,a,b,b)$, or $(do, re, mi, fa, so, la, ti, do)$ are called tuples. The elements of a tuple are ordered. Given a tuple $t$, you access the $i$th element with the notation $\:t\!\downarrow\!i$.

In ZFC, tuples are created from pairs. Here’s how: We will take $\times$ to be right-associative, so $A_1 \times A_2 \times \ldots \times A_n$ means $A_1 \times (A_2 \times (\ldots \times A_n)\ldots)$, and $(a_1, \ldots, a_n)$ sugars $(a_1, (a_2, (\ldots, (a_{n-1}, a_n)\ldots)))$ and is called an $n$-tuple. Its length is $n$.

Note that all tuples have at least $2$ elements. We can loosely talk about $1$-tuples as being an element itself, i.e., $a = (a)$ and the $0$-tuple as being the special value $()$, which we will encode as $\varnothing$.

Tuples can be concatenated. If $t_1$ is an $m$-tuple and $t_2$ is an $n$-tuple then $t_1 • t_2$ is an $(m+n)$-tuple:

$$(a_1, \ldots, a_m) • (b_1, \ldots, b_n) = (a_1, \ldots, a_m, b_1, \ldots, b_n)$$

We will allow the concatenation operator to work with $0$-tuples and $1$-tuples as well, so $(a,b) • c = (a,b,c)$, $a • b = (a,b)$, $a • () = a$, and $() • () = ()$.

Don’t forget that order matters: $(a,(a,a))$ is not the same thing as $((a,a),a)$.

Sets

A set, in practice, is an unordered collection of unique elements.

Sets are encoded in ZFC as...sets!

Relations

A relation is a subset of a cross product. That’s it. That’s the whole definition.

For the relation $R \subseteq A \times B$, we say $A$ is the domain and $B$ is the codomain. If $(a,b) \in R$ we write $aRb$. The inverse $R^{-1} \subseteq B \times A$ is $\{(b,a) \mid aRb\}$.

Here is the definition of the less-than relation on natural numbers in set theory:

Note that because a relation is a subset of $A \times B$, the set of all relations over $A$ and $B$ is $\mathcal{P}(A \times B)$.

Now we can define composition in Set Theory. If $R \subseteq A \times B$ and $S \subseteq B \times C$ then the composition of $R$ and $S$ is $S \circ R$ = $\{(a,c) \mid \exists b. aRb \land bSc\}$.

The symbol $\circ$ can be read as “composed with” but it is much better read as “after”. For example, $S \circ R$ is best read as “$S$ after $R$.”

Even though relations are sets, the superscript notation on relations means something different than it does for regular sets. This seems infuriating until you finally come to terms with the fact that that math notation is very contextual and changes depending on what you are talking about. Anyway, here is what the superscripts mean for relations:

Those definitions imply $R^2 = R \circ R$, $R^3 = R \circ R \circ R$, and so on.

These forms turn out to be very useful in computation theories, as we frequently use relations that represent a single computation step, so the * form of the relation will mean any number of steps.

AMBIGUOUS NOTATION ALERT

The expression $R^2$ is ambiguous: since a relation is a set, $R^2$ could mean $R \times R$, but most people use it to mean $R \circ R$. You really need to supply context when using ambiguous notation.

Functions

In set theory, where everything is a set, even functions, a function $f \subseteq A \times B$ is defined to ba a relation in which every element of $A$ appears exactly once as the first element of a pair in $f$. That’s all it is.

If $f$ is a function and $(a,b) \in f$ we write $f a = b$, or $f(a) = b$, and say $b$ is the value of $f$ at $a$. The range of $f$ is $\{b \mid \exists a. b = f a\}$.

The set of all functions from $A$ to $B$ is denoted $A \rightarrow B$. You might also see $B^A$ used for this set.

Since functions are relations and therefore sets, we often write them in set notation, but you may prefer to use $\lambda$ notation, which shows how inputs are mapped to outputs. Here you provide a logical formula after the dot which provides the output after substituting the input into the formula.

It might go without saying, but because functions are relations, the “after” operation applies to functions. An example:

$$ (\textsf{square} \circ \textsf{inc}) (3) = \textsf{square}(\textsf{inc}(3)) = \textsf{square}(4) = 16 $$ $$ (\textsf{inc} \circ \textsf{square}) (3) = \textsf{inc}(\textsf{square}(3)) = \textsf{inc}(9) = 10 $$

So does iteration (since again, functions are just relations):

$$ \begin{array}{l} \textsf{inc}^0 (5) = 5 \\ \textsf{inc}^1 (5) = \textsf{inc}(5) = 6 \\ \text{inc}^2 (5) = (\textsf{inc} \circ \textsf{inc}) (5) = \textsf{inc}(\textsf{inc}(5)) = 7 \\ \textsf{inc}^3 (5) = (\textsf{inc} \circ \textsf{inc} \circ \textsf{inc}) (5) = \textsf{inc}(\textsf{inc}(\textsf{inc}(5))) = 8 \\ \ldots \\ \textsf{inc}^{-1} (5) = 4 \\ \end{array} $$

The -jections

Time for more definitions! For $f:\!A \rightarrow B$ (or $f \in A \rightarrow B$ for you set theorists, since the following works the same in both theories):

• $f$ is a surjection (i.e., $f$ maps $A$ onto $B$) iff $\forall b. \exists a. f a = b$
• $f$ is an injection (i.e., $f$ maps $A$ one-to-one to $B$) iff $\forall a . \forall b. a \neq b \supset f a \neq f b$
• $f$ is a bijection, a.k.a. a one-to-one correspondence iff $f$ is a surjection and an injection

If $f$ is a bijection from $A$ to $B$, then:

• $f^{-1}$ is a bijection from $B$ to $A$
• $\forall a. f^{-1}(f\,a) = a$
• $\forall b . f(f^{-1}\,b) = b$

Partial Functions

We defined a function as a relation where every element of the domain appears exactly once as the first element of a pair. If we relax this to every element of the domain appearing at most once then we have a partial function. Think of a partial function as not being able to compute a value for every element, or one in which the value at some inputs is “undefined.” For emphasis, functions are defined everywhere are called total functions.

The set of all partial functions from $A$ to $B$ is denoted $A \rightharpoonup B$.

If $f \in A \rightharpoonup B$ then:

• $f \in C \rightarrow B$ for some $C \subseteq A$, where $C$ is precisely the set of elements from $A$ at which $f$ is defined.
• $f \in A \rightarrow B \cup \{\bot_B\}$, where $\bot_B$ is a representation of the undefined value in $B$.

The subscript on $\bot_B$ is often omitted in practice and inferred from context.

Partial functions are useful in computer science because they allow us to model programs that might not terminate or might throw an error. However, the modern approach in programming languages is that for functions that may fail, we use total functions whose codomain is a sum or union type combining expected return values and error values. For functions that never terminate, well, partial functions are fine.

Sequences

A sequence is an ordered list of elements indexed by natural numbers, and written $\langle a_0, a_1, a_2, \dots, a_{n-1} \rangle$. The length of the sequence is $n$.

In Set Theory, a sequence is a partial function from the natural numbers $\mathbb{N}$ to some set $A$, where the function is defined for the first $n$ natural numbers and undefined thereafter. To get the element at position $i$ in sequence $s$, we simply evaluate $s(i)$.

Alternatively, a sequence can be encoded as a total function with domain $\{ 0, 1, \ldots, n-1\}.$

Lists

A list is like a sequence, but (in Set Theory) rather than being defined by a function, it is defined inductively like so: The empty list is represented by $\varnothing$, and a non-empty list is represented as an ordered pair whose first element is the head of the list and the second element is the tail (which is itself a list). So the list $[3,8,5]$ would be represented as $(3, (8, (5, \varnothing)))$.

Strings

Strings in set theory are encoded as lists of characters, where a character is an element of a set known as an alphabet. An example of an alphabet is the set $\textsf{Unicode}$. The set theory representation of the string $hi$ is $(\texttt{LATIN SMALL LETTER H}, (\texttt{LATIN SMALL LETTER I}, \varnothing))$, or $(\texttt{U+0068}, (\texttt{U+0069}, \varnothing))$.

The context surrounding strings is so vast, we have a separate page of notes on the topic. It is part of a much larger theory of language and computation, which we will explore in detail later in the course.

Maps

Sometimes it’s convenient to think of partial functions as maps where the inputs are the keys and the outputs are the values. When we do, we tweak the notation a bit. Here’s a partial function, $m \in \textsf{Unicode}^* \rightharpoonup \mathbb{N}$:

$(\lambda s. \bot)[\texttt{a} \mapsto 1][\texttt{b} \mapsto 2][\texttt{c} \mapsto 3]$

The function substitution notation is perfect here, as it says that the value at every input is $\bot$ unless explicitly overwritten. But we said above that functions are just sets. Which set is this? We can say it’s this:

$\{ (\texttt{a}, 1), (\texttt{b}, 2), (\texttt{c}, 3) \} \cup \{ (s, \bot) \mid s \in \textsf{Unicode}^* \setminus \{\texttt{a}, \texttt{b}, \texttt{c}\} \}$

It’s a bit hard to read, though, so in these cases, we do better writing the function in map notation:

$\{ \texttt{a}\!: 1, \texttt{b}\!: 2, \texttt{c}\!: 3 \}$

We will consider the latter just syntactic sugar for the former, rather than defining maps as a primitive type. So for this particular map, we have:

Also, because maps are just functions, the substitution notation works for them too. If $m$ is the map above, we can write things like $m[\texttt{d} \mapsto 4]$ for the map just like $m$ with the additional key-value pair mapping $d$ to $4$, and $m[\texttt{b} \mapsto 0]$ for the map like $m$ except $\texttt{b}$ now maps to $0$.

Numbers

We covered a lot about numbers in our notes on Mathematics Foundations. We skimmed over the important part: how are numbers (other than the natural numbers, which we’ve already seen) encoded in Set Theory?

Naturals, Integers, and Rationals

First, we’ve already seen how to encode the natural numbers:

$$ \begin{array}{lcl} \mathbb{N} & = & \{ \varnothing, \{\varnothing\}, \{\varnothing, \{\varnothing\}\}, \{\varnothing, \{\varnothing\}, \{\varnothing, \{\varnothing\}\}\}, \ldots \} \\ & = & \{0, 1, 2, 3, \dots\} \end{array} $$

The intuitive approach to encoding integers and rational numbers in set theory goes like this:

• An integer is encoded as a set of pairs $(a, b)$ from $\mathbb{N} \times \mathbb{N}$, such that, say, the integer $3$ is encoded as $\{ (3,0), (4,1), (5,2), \dots \}$ and the integer $-2$ is encoded as $\{ (0,2), (1,3), (2,4), \dots \}$. The set of all integers is called $\mathbb{Z}$.
• A rational number is encoded as a set of pairs $(a, b)$ from $\mathbb{Z} \times (\mathbb{Z} \setminus \{0\})$, such that, say, the rational number $\frac{3}{4}$ is encoded as $\{ (3,4), (6,8), (9,12), \dots \}$ and the rational number $-\frac{2}{5}$ is encoded as $\{ (-2,5), (-4,10), (-6,15), \dots \}$. The set of all rational numbers is called $\mathbb{Q}$.

But to make this formal, we need to define what we mean by addition and multiplication for natural numbers within set theory.

Here is the successor function on natural numbers in set theory:

$$ S =_{\small{\textrm{def}}} \{ (x,y) \in \mathbb{N} \times \mathbb{N} \mid y = x \cup \{x\} \} $$

Now addition on natural numbers is the smallest relation that satisfies the properties of addition:

$$ + =_{\small{\textrm{def}}} \bigcap \left\{ R \in \mathcal{P}((\mathbb{N} \times \mathbb{N}) \times \mathbb{N}) \ \middle|\ \begin{array}{l} (\forall m \in \mathbb{N}. \, (m, 0)\,R\, m) \; \land \\ (\forall m, n, k \in \mathbb{N}. \, (m, n)\,R\, k \supset (m, S(n))\,R\, S(k)) \end{array} \right\} $$

Now we can formally define the sets of integers and rational numbers:

Reals

Real Numbers are pretty wild, and require some cleverness to define set-theoretically. The trick is to model a real as a set of all rational numbers less than the number we are defining—more precisely, a bounded, downward-closed (if $x$ is in the set and $y$ is a rational number less than $x$, then $y$ is also in the set) set of rationals that is neither $\varnothing$ or $\mathbb{Q}$ itself, called a Dedekind Cut. Specific examples are:

The set of all real numbers:

Naturally, we’d like to see how to define addition, subtraction, multiplication, division, and exponentiation on the integers, rational numbers, and real numbers, but alas, that’s beyond the scope of these notes, but it easy to find.

Cardinal Numbers

A cardinal number tells us how many of something there are. In particular, it helps us count how many items there are in a set. So these numbers are central to Set Theory.

They also show up in computability theory, since one of the central results of that theory is that there are more functions than programs. That’s interesting. But how do we know this?

The quantity of elements in a set is called the cardinality of the set. The cardinality of set $A$ is denoted $|A|$ and obeys these axioms:

• $|A| = |B|$ iff there exists a bijection between $A$ and $B$. That is, for each element in $A$ there is a matching value in $B$ and vice-versa.
• $|A| \leq |B|$ iff there exists an injection from $A$ to $B$. That is, for each element of $A$ there is a matching element in $B$, but not necessarily vice-versa.
• $|A| \lt |B|$ iff $|A| \leq |B|$ and $|A| \neq |B|$

Did you notice something about bijections? They are important! They tell us when two sets are the same size, without having to count them.

Matching is more fundamental than counting.

Think about this

Matching is more fundamental than counting. Imagine yourself without words for what we now call numbers. You could still come up with ideas of greater than or less than, and allocate resources, and even trade.

Counting is an advanced concept!

If there exists a bijection between a set $A$ and the set $\{1, 2, ... k\}$ for some natural number $k \geq 0$, we say that $A$ is finite and, since the number of elements in $\{1, 2, ... k\}$ is $k$, we have $|A| = k$.

What about $\mathbb{N}$? We can’t find a bijection between that and $\{1, 2, ... k\}$ for any natural number $k$. That set is not finite—it is infinite. So what is its cardinality? Someone once declared it to be $\aleph_0$ and this stuck. $\aleph_0$ a cardinal number. Not a natural number, but definitely a cardinal, because it tells you how many of something there is.

We can make a bijection between the set of even numbers and the set of natural numbers using the function $\lambda n_{\small{\mathbb{N}}}. 2n$. So the set of even numbers has the same cardinality as the set of natural numbers. It too has a cardinality of $\aleph_0$.

An interesting thing about $\mathbb{N}$ is that you can list, enumerate, or count them—yes it would take forever, but you could do it in principle. The is so significant that we have a definition:

A set $A$ is countable (a.k.a. listable) iff $A$ is finite or $|A| = \aleph_0$. $\mathbb{N}$ is countable by definition. We saw that the even natural numbers are countable. So is $\mathbb{Z}$, because $\lambda n.(\textsf{if}\;\textit{even}(n)\;\textsf{then}\;\frac{-n}{2}\;\textsf{else}\;\frac{n+1}{2})$ is a bijection between $\mathbb{N}$ and $\mathbb{Z}$.

$\mathbb{N} \times \mathbb{N}$ is countable, too:

  (0,0)
  (0,1)   (1,0)
  (0,2)   (1,1)   (2,0)
  (0,3)   (1,2)   (2,1)   (3,0)
  (0,4)   (1,3)   (2,2)   (3,1)   (4,0)
  (0,5)   (1,4)   (2,3)   (3,2)   (4,1)   (5,0)
  ...

By a similar argument, $\mathbb{Q}$, $\mathbb{N}^i$, and any countable union of countable sets are all countable.

But the set of real numbers is associated with a bigger infinity. We prove this with a technique known as diagonalization, which basically says that no matter how you try to list all real numbers, you can always construct a new real number that is not on the list.

Here’s a video explanation, together with some additional historical context:

The video shows that there are infinities “larger than” the infinity of the natural numbers. That is, there are cardinal numbers much greater than $\aleph_0$. Such sets are called uncountable. There are infinitely many larger and larger and larger infinities. You can show this by making power sets repeatedly. Why? Because Cantor’s theorem works for both finite (obviously) and infinite sets:

Cantor’s Theorem: For any set $A$, $|A| \lt |\mathcal{P}(A)|$. Proof: Clearly $|A| \leq |\mathcal{P}(A)|$, so we only have to show $|A| \neq |\mathcal{P}(A)|$. Proceed by contradiction. Assume $|A| = |\mathcal{P}(A)|$, which means there is a function $g$ mapping $A$ onto $\mathcal{P}(A)$. Consider $Y = \{x \mid x \in A \land x \notin g(x)\}$. Since $g$ is an onto function, there must exist a value $y \in A$ such that $g(y)=Y$. If we assume $y \in Y$ then by definition means that $y \notin Y$. But if we assume $y \notin Y$, then that means $y \in Y$. This is a contradiction, so the assumption that a surjectve $g$ exist cannot hold. Therefore $|A| \neq |\mathcal{P}(A)|$. Slay.

Diagonalization again

Cantor’s theorem uses the same diagonalization technique as the proof that $|\mathbb{N}| \lt |\mathbb{R}|$.

Similar arguments to this proof of Cantor’s theorem show that the following sets are uncountable:

• $\{x \mid x \in \mathbb{R} \land 0 \lt x \lt 1\}$
• $\mathbb{N} \rightarrow \mathbb{N}$

Fun fact. Okay so $\{x \mid x \in \mathbb{R} \land 0 \lt x \lt 1\}$ is uncountable. But is its cardinality equal to, or strictly less than, $\mathbb{R}$ itself? Turns out it’s equal! The bijection you are looking for is: $\lambda x. \frac{1}{\pi}tan^{-1}x + \frac{1}{2}$ is a bijection to $\langle 0,1 \rangle$.

The continuum is a pretty mind-blowing concept.

The fact that $\mathbb{N}\rightarrow\mathbb{N}$ is uncountable means that there are functions for which no computer program can be written to solve, because programs are strings of symbols from a finite alphabet of characters (e.g., Unicode) and thus there are only a countably infinite number of them. Similarly, the fact that there are real numbers that we cannot describe is true because descriptions are themselves finite strings in some language.

The continuum is a pretty mind-blowing concept.

Alternate Definitions

Rather than defining finite sets as those can have a bijection with $\{1, 2, \ldots k\}$ for natural number $k$ and infinite sets as sets that are not finite, others prefer these definitions:

A set is infinite iff there is a bijection between it and a proper subset of itself. A set is finite iff it is not infinite.

Ordinal Numbers

It’s important to distinguish cardinals from ordinals. An ordinal number gives the position of something in an ordered sequence. While cardinal numbers are called, in English, zero, one, two, three, and so on, ordinal numbers are called first, second, third, and so on.

This video has great visuals for both kind of numbers. You may have encountered it in the Foundations of Mathematics notes. If you haven’t, watch it now:

Recall Practice

Here are some questions useful for your spaced repetition learning. Many of the answers are not found on this page. Some will have popped up in lecture. Others will require you to do your own research.

1. What are three theories that claim to be able to formalize “all of mathematics”?
   Set Theory;
   Type Theory;
   Category Theory.
2. What is the characteristic notations of set theory?
   $x \in A$
3. What is a set?
   A collection of distinct objects, carefully constructed to avoid nonsensical or paradoxical situations.
4. What are some of the foundational mathematical objects?
   Booleans, numbers, tuples, characters, strings, sequences, relations, functions, sets, vectors, matrices, tensors, maps, graphs.
5. What does the expression $A \subseteq B$ sugar?
   It is syntactic sugar for $\forall x (x \in A \rightarrow x \in B)$.
6. What is the most popular set theory called?
   ZFC, for Zermelo-Fraenkel-Choice.
7. Name some Axioms of ZFC set theory.
   Empty Set, Extensionality, Regularity, Pairing, Union, Power Set, Infinity, Separation, Replacement, Choice.
8. How is the natural number 1 represented in set theory?
   $\{ \emptyset \}$.
9. Why are sets so effective at formalizing mathematics?
   A set expresses the very fundamental notion of an object having a property.
10. What does a tuple look like?
    $(a, b, c)$
11. What is $(10, 20, 30)\downarrow 1$?
    $20$
12. What kind of a type do tuples belong to?
    A product type.
13. What is $(2, 8, 3) \bullet (5, 1)$?
    $(2, 8, 3, 5, 1)$
14. How do sets differ from tuples?
    Sets are unordered and do not contain duplicates.
15. What is the difference between a crisp set and a fuzzy set?
    A crisp set is a set where an element is either in the set or not. A fuzzy set is a set where an element can be partially in the set.
16. How do we denote that $x$ is a member of the set $A$?
    $x \in A$
17. Why isn’t $\{ x \mid x \not\in x \}$ considered a set?
    Considering it a set ruins everything because if it were a set, assuming it was a member of itself would imply it was not and assuming it was not a member of itself would imply that it was.
18. How is set subtraction $A \setminus B$ defined?
    $\{x \in A \mid x \notin B\}$
19. What is the difference between $A-B$ and $A \setminus B$?
    Nothing, they are the same.
20. What is the difference between $A \setminus B$ and $A \vartriangle B$?
    The first is the set of all elements in $A$ but not in $B$. The second, the symmetric difference, is the set of elements that are in exactly one of $A$ or $B$.
21. What is $\mathcal{P}(\{a,b,c\})$?
    $\{\varnothing, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\} \}$
22. What is $\varnothing \times \varnothing$?
    $\varnothing$
23. What is $\{1,2\}^*$ (assuming this set is not an alphabet or language)?
    $\{(), (1), (2), (1,1), (1,2), (2,1), (2,2), (1,1,1), (1,1,2), (1,2,1), (1,2,2), (2,1,1), \ldots \}$
24. What is $\{1, 2\}^0$?
    $\{ () \}$
25. What are the distinct partitions of $\{ a, b \}$?
    • $\{ \{a\}, \{b\} \}$
    • $\{ \{a,b\} \}$
26. What are the distinct partitions of $\{ a, b, c \}$?
    • $\{ \{a\}, \{b\}, \{c\} \}$
    • $\{ \{a,b\}, \{c\} \}$
    • $\{ \{a,c\}, \{b\} \}$
    • $\{ \{b,c\}, \{a\} \}$
    • $\{ \{a,b,c\} \}$
27. Are the set of all even integers and the set of all prime numbers disjoint?
    No, they share the number $2$.
28. Given a relation $R$ defined as a subset of $A \times B$, what are $A$ and $B$ called?
    The domain and codomain of $R$.
29. How do we denote the set of all relations over $A$ and $B$?
    $\mathcal{P}(A \times B)$
30. What is the inverse of the relation $\{(1, 2), (3, 4)\}$?
    $\{(2, 1), (4, 3)\}$
31. Give an example of a relation over $\{a, b, c\}$ that is neither reflexive nor irreflexive.
    $\{(a, a), (b, c)\}$ is not reflexive because it does not contain $(b, b)$, and it is not irreflexive because it does contain $(a, a)$.
32. What is the difference between “asymmetric” and “antisymmetric”?
    An asymmetric relation can never have a member of the form $(x,x)$, but an antisymmetric relation can.
33. What three properties characterize a partial order?
    Reflexivity, antisymmetry, transitivity.
34. Let $R_1 = \{(3,1),(9,8),(2,5)\}$ and $R_2 = \{(8,8),(10,2),(1,7)\}$. What is $R_1 \circ R_2$?
    $\{ (10,5) \}$
35. Let $R = \{ (3, 5), (5, 8), (1, 2), (8, 1) \}$. What are $R^2$ and $R^3$?
    $R^2 = \{ (3, 8), (5, 1), (8, 2) \}$
    $R^3 = \{ (3, 1), (5, 2) \}$
36. How do we denote the set of all functions from $A$ to $B$?
    $A \rightarrow B$
37. The set $\mathbb{Z} \times \{ 0 \}$ is a function. Write it in lambda notation.
    $\lambda x_{\small \textsf{int}}. 0$
38. The set $\{ (x, y) \mid x \in \mathbb{N} \land \textrm{x is even} \land y = \frac{x}{2} \} \cup \{ (x, y) \mid x \in \mathbb{N} \land \textrm{x is odd} \land y = \frac{3x+1}{2} \}$ is a function. Write it in lambda notation, using an if expression.
    $\lambda x_{\small \textsf{nat}}. \textsf{if}\;\textit{even}(x)\;\textsf{then}\;\frac{x}{2}\;\textsf{else}\;\frac{3x+1}{2}$
39. How do you write the function that maps "x" to 21, "y" to 8, "z" to 55, and every other input to 0, in both lambda notation and as a map?
    $(\lambda x. 0)[21/\texttt{"x"}][8/\texttt{"y"}][55/\texttt{"z"}]$
    $\{ \texttt{"x"}\!: 21, \texttt{"y"}\!: 8, \texttt{"z"}\!: 55 \}$
40. What is an injection?
    A function that maps distinct inputs to distinct outputs. Also known as a one-to-one function.
41. What is a surjection?
    A function that maps to every element in the codomain. Also known as an onto function.
42. What is the difference between a function and a partial function?
    A function maps every element of the domain to an element of the codomain. A partial function maps every element of the domain to either zero or one element of the codomain.
43. How do we denote the set of all functions from $A$ to $B$? All partial functions from $A$ to $B$?
    $A \rightarrow B$; $A \rightharpoonup B$
44. If a partial function $f$ has no value at $x$, what do we say $f(x)$ is?
    $\bot$
45. In Set Theory, how is the list $[a, b, c]$ represented?
    As the set $\{ a, (b, (c, \varnothing)) \}$.
46. If A was the alphabet $\{a, b, c\}$, what is $A^2$?
    $A^2$ is the set of all 2-letter words that can be formed from $A$, i.e., $\{aa, ab, ac, ba, bb, bc, ca, cb, cc\}$.
47. How to we write the partial function mapping the vowels of the English alphabet to their 1-based position in the alphabet in map-notation?
    $\{ \texttt{a}\!: 1, \texttt{e}\!: 5, \texttt{i}\!: 9, \texttt{o}\!: 15, \texttt{u}\!: 21 \}$
48. What is cardinal number?
    A number that tells you how many of something there is.
49. ________________ is more fundamental than counting.
    Matching
50. What are the cardinalities of $\varnothing$, $\{a, b, c\}$, and $\mathbb{Z}$?
    0, 3, $\aleph_0$
51. What is an infinite set?
    A set for which there exists a bijection between it and a proper subset of itself.
52. What is a countable set?
    A set for which there exists a bijection between it and $\mathbb{N}$.
53. Which of the following sets are countable and which are not: $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$?
    $\mathbb{N}$, $\mathbb{Z}$, and $\mathbb{Q}$ are countable. $\mathbb{R}$ and $\mathbb{C}$ are uncountable.
54. What does Cantor’s Theorem say?
    For any set $A$, $|A| \lt |\mathcal{P}(A)|$.
55. How are ordinal numbers different from cardinal numbers?
    Ordinal numbers describe the position of an element in a sequence, while cardinal numbers describe the size of a set.
56. Who is the guy that made that freaking amazing set of web pages on big numbers?
    Robert P. Munafo
57. What is a trotillion?
    $10^{(3 \times 10^{(3 \times 10^{900})} + 3)}$

Summary

We’ve covered:

• What sets are
• History
• Basic notions of different set theories
• Basic Notation
• The Axioms of ZFC
• Encoding Objects in ZFC
• Cardinals and Ordinals