Lecture 1. Set theory #

Overview #

Set theory is the foundational language of discrete mathematics. Almost every object we study later in this course — relations, functions, Boolean algebras, graphs, probability spaces, and the state sets of automata — is built on top of sets. When we say “a graph is a pair $(V, E)$ where $E$ is a set of pairs of vertices,” or “a relation from $A$ to $B$ is a subset of $A \times B$,” or “an event is a subset of the sample space,” we are speaking set theory. Learning to read and write in this language fluently now pays dividends in every subsequent lecture.

This chapter introduces the primitive notion of a set and the membership relation, catalogues the special and numeric sets we will reuse constantly, and develops the vocabulary for comparing sets (subset, equality), describing them (roster, set-builder, recursive), and measuring them (cardinality, power set, countability). Along the way we prove the standard structural facts — $\varnothing \subseteq A$, the double-inclusion criterion for equality, $|\mathcal{P}(A)| = 2^{n}$ — rigorously rather than merely asserting them, because a large part of the value of a discrete-mathematics course is learning how to prove statements about discrete structures. We close with ordered pairs, tuples, and the Cartesian product, which lead directly into relations, and with a cautionary historical note on Russell’s paradox and applications to computer science.

Set operations (union, intersection, difference, complement), Venn diagrams, and the algebraic identities that govern them are the subject of Lecture 2; here we build the ground they stand on. Relations, which are defined as subsets of Cartesian products, follow in Lecture 3.

A note on rigor. Several results below are stated as theorems or propositions and come with a proof, delimited by Proof. … ∎. Read the proofs actively: at each step ask “why is this step allowed?” The proof techniques on display here — direct proof, proof by contradiction, proof by cases, proof by induction, and proof by exhibiting a bijection — are exactly the techniques you will reuse throughout the course.

1.1 Sets and membership #

1.1 Motivation #

Collections are everywhere. The students enrolled in a course, the files in a directory, the primes below $100$, the reachable states of a program, the pixels of an image, the rows of a database table — each is a collection of objects regarded as a single entity. Mathematics needs one clean, uniform notion that captures “a collection considered as a whole” while ignoring incidental details such as the order in which we happen to list the objects or how many times we mention each one. That notion is the set.

1.2 The primitive notions #

We take two notions as primitive (undefined, understood intuitively): set and membership.

Definition (set). A set is an unordered collection of distinct objects considered as a whole. The objects are called the elements (or members) of the set. A set is completely determined by which objects it contains — not by any order among them, and not by any repetition.

Definition (membership). We write $x \in A$ to mean “$x$ is an element of $A$” (read “$x$ belongs to $A$”), and $x \notin A$ to mean “$x$ is not an element of $A$.” For every object $x$ and set $A$, exactly one of $x \in A$, $x \notin A$ holds.

Sets are conventionally named with capital letters ($A, B, C, \dots$) and their elements with lowercase letters, though this is only a convention: an element of a set may itself be a set (indeed, in the standard axiomatic development every element is a set).

Two structural principles follow immediately from “a set is determined by its members”:

• Order is irrelevant: $\{1,2,3\} = \{3,1,2\}$.
• Repetition is irrelevant: $\{1,2,2,3\} = \{1,2,3\}$.

An element either is or is not in a set; there is no notion of “how many times” or “in what position.” (Structures that do track multiplicity are called multisets, and structures that track order are sequences or tuples; both are built on top of sets and appear later.)

Example 1.1. Let $A = \{a, e, i, o, u\}$ be the set of vowels of the English alphabet. Then $e \in A$, but $b \notin A$. The set $A$ has exactly five members, and $\{u, a, o, i, e\}$ denotes the very same set.

Example 1.2. $\{x\}$, a set with exactly one element $x$, is called a singleton. Thus $\{7\}$, $\{a\}$, and $\{\varnothing\}$ are singletons. Note carefully that $7$ and $\{7\}$ are different objects: the first is a number, the second is a set whose one element is that number.

Example 1.3 (sets of sets). Elements may themselves be sets. In $B = \{\, 1,\ \{1\},\ \{1,2\} \,\}$ we have $1 \in B$ and $\{1\} \in B$, and these are three distinct elements, so $|B| = 3$. But $2 \notin B$: although $2$ appears inside the element $\{1,2\}$, it is not itself an element of $B$. Membership does not “see through” the braces.

Remark (well-definedness). For a description to name a set, membership must be definite: given any object, it must be determinate whether it belongs. “The set of large numbers” is not well-defined (how large is large?), whereas “the set of integers greater than $10^{6}$” is. Vagueness, not infinitude, is the problem; infinite sets like $\mathbb{N}$ are perfectly well-defined.

Common pitfall (element vs. set). Beginners routinely confuse an object $x$ with the singleton $\{x\}$, and confuse membership $\in$ with the subset relation $\subseteq$ (§1.4). Keep them apart: $x \in A$ relates an object to a set; $\{x\} \subseteq A$ relates a set to a set. Both can be true at once, and they say the same thing here — $x \in A \iff \{x\}\subseteq A$ — but they are grammatically different statements, and the confusion becomes a real error once the elements are themselves sets (Example 1.3).

1.2 Special sets: the empty set and the universe #

Two sets play a distinguished structural role and deserve names.

Definition (empty set). The empty set (or null set), written $\varnothing$ (also $\{\,\}$), is the unique set that has no elements at all. For every object $x$ we have $x \notin \varnothing$.

The empty set is the additive “zero” of set theory: small, but indispensable. It is the base case of countless recursive definitions and the value returned when a search finds nothing.

Beware the following distinction, which trips up almost everyone once:

$$\varnothing \ne \{\varnothing\}.$$

The left-hand side contains nothing ($|\varnothing| = 0$). The right-hand side is a singleton whose one element happens to be the empty set ($|\{\varnothing\}| = 1$). By analogy: an empty box and a box that contains one empty box are not the same box. We will prove below (Proposition 1.5) that there is genuinely only one empty set.

Definition (universal set). In any particular discussion we fix a universal set (or universe), often written $U$, consisting of all objects relevant to that discussion. Every set under consideration is understood to be a subset of $U$.

The universe is a matter of context, chosen for convenience: when discussing integers, $U = \mathbb{Z}$; when discussing letters, $U$ is the alphabet; in a dice problem, $U = \{1,2,3,4,5,6\}$. The universe becomes essential in Lecture 2, where the complement $\overline{A}$ of a set is defined as $U \setminus A$ and therefore depends on which $U$ we chose.

Common pitfall (no “set of everything”). It is tempting to take $U$ to be “the set of absolutely all objects.” §1.12 (Russell’s paradox) shows that an unrestricted universal set leads to contradiction. In practice $U$ is always some concrete, safely-sized set fixed by the problem, never “everything.”

Example 1.4. If the universe is $U = \{1,2,3,4,5,6\}$ (one throw of a die), then in probabilistic language the “impossible outcome” corresponds to $\varnothing$ and the “certain outcome” corresponds to $U$ itself. There is exactly one empty set, whatever the context.

Proposition 1.5 (uniqueness of the empty set). There is exactly one set with no elements.

Proof. Suppose $E_1$ and $E_2$ are both sets with no elements. We show $E_1 = E_2$ using the equality criterion of §1.5 (double inclusion). To show $E_1 \subseteq E_2$ we must verify $x \in E_1 \implies x \in E_2$ for every $x$; but $x \in E_1$ is false for every $x$ (as $E_1$ has no elements), so the implication holds vacuously (§1.4.2). Hence $E_1 \subseteq E_2$. By the identical argument with the roles swapped, $E_2 \subseteq E_1$. By double inclusion, $E_1 = E_2$. Since any two empty sets coincide, the empty set is unique. ∎

Because it is unique, we are entitled to speak of the empty set and to give it its own symbol $\varnothing$.

1.3 Numeric sets #

Certain infinite sets of numbers recur so often that they have reserved blackboard-bold symbols. Memorize this hierarchy; we will use it in every lecture.

A few clarifications:

• Following the course deck, we take $\mathbb{N} = \{1, 2, 3, \dots\}$ (starting at $1$). Many authors (and most computer scientists) include $0$ and write $\mathbb{N} = \{0,1,2,\dots\}$ or $\mathbb{N}_0$. Neither convention is more correct; watch for which one each text uses, because it changes statements like “$0 \in \mathbb{N}$.”
• Rational numbers are exactly those expressible as a ratio of two integers. A rational has a decimal expansion that either terminates ($\tfrac{1}{2} = 0.5$) or is eventually periodic ($\tfrac{1}{3} = 0.\overline{3}$, $\tfrac{1}{7} = 0.\overline{142857}$).
• Irrational numbers have non-terminating, non-repeating decimal expansions; $\sqrt{2} = 1.41421\dots$ and $\pi = 3.14159\dots$ cannot be written as a ratio of integers (Theorem 1.7 proves this for $\sqrt 2$).
• The imaginary unit $i$ satisfies $i^2 = -1$, and a complex number combines a real part $a$ and an imaginary part $b$ as $a + bi$.

These sets nest inside one another:

$$\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}.$$

Every natural number is an integer, every integer is rational (e.g. $-3 = \tfrac{-3}{1}$), every rational is real, and every real is complex (with imaginary part $0$). Each inclusion is proper — there are integers that are not natural ($-1$), rationals that are not integers ($\tfrac12$), reals that are not rational ($\sqrt2$), and complexes that are not real ($i$).

Example 1.6 (classification). Classify $-7,\ \tfrac{3}{4},\ \sqrt{2},\ 5,\ 2i$.

• $5 \in \mathbb{N}$ (and hence also in $\mathbb{Z}, \mathbb{Q}, \mathbb{R}, \mathbb{C}$).
• $-7 \in \mathbb{Z}$ but $-7 \notin \mathbb{N}$.
• $\tfrac{3}{4} \in \mathbb{Q}$ but $\tfrac{3}{4} \notin \mathbb{Z}$.
• $\sqrt{2} \in \mathbb{R}$ (irrational) but $\sqrt{2} \notin \mathbb{Q}$.
• $2i \in \mathbb{C}$ (in fact $2i \in I$) but $2i \notin \mathbb{R}$.

The blackboard-bold letters denote the smallest customary system; each number also lives in every larger system in the chain.

Intervals of $\mathbb{R}$ #

Subsets of the real line are named by interval notation. For $a<b$: the closed interval $[a,b]=\{x:a\le x\le b\}$ includes both endpoints; the open interval $(a,b)=\{x:a<x<b\}$ excludes both; the half-open $[a,b)$ and $(a,b]$ include exactly one; and the rays $[a,\infty)=\{x:x\ge a\}$, $(-\infty,b)=\{x:x<b\}$ (and their variants) are unbounded. A square bracket means the endpoint is in the set, a round bracket that it is not; $\pm\infty$ always takes a round bracket. This notation is used throughout the course — e.g. $(0,1)$ for a probability, $[a,b]$ for a function’s domain.

3.1 A worked proof: $\sqrt 2$ is irrational #

That the chain $\mathbb{Q} \subset \mathbb{R}$ is proper is not obvious — one must produce a real number and prove it is not a ratio of integers. The classic example is $\sqrt 2$. The proof, known to the Pythagoreans around 500 BCE, is a model of the technique proof by contradiction.

Theorem 1.7. $\sqrt{2}$ is irrational; that is, there are no integers $p, q$ with $q \ne 0$ and $\left(\tfrac{p}{q}\right)^2 = 2$.

Proof. Suppose, for contradiction, that $\sqrt 2$ is rational. Then we may write $\sqrt 2 = \tfrac{p}{q}$ with $p, q \in \mathbb{Z}$, $q \ne 0$, and the fraction in lowest terms, i.e. $\gcd(p,q) = 1$ (any fraction can be reduced to lowest terms by cancelling common factors). Squaring gives $2 = \dfrac{p^2}{q^2}$, hence

$$p^2 = 2q^2. \tag{$\ast$}$$

Equation $(\ast)$ says $p^2$ is even. Now $p^2$ even forces $p$ even: for if $p$ were odd, say $p = 2m+1$, then $p^2 = 4m^2 + 4m + 1 = 2(2m^2+2m)+1$ would be odd. So $p$ is even; write $p = 2k$. Substituting into $(\ast)$:

$$(2k)^2 = 2q^2 \;\Longrightarrow\; 4k^2 = 2q^2 \;\Longrightarrow\; q^2 = 2k^2.$$

By the same reasoning $q^2$ is even, so $q$ is even. But now $2 \mid p$ and $2 \mid q$, contradicting $\gcd(p,q) = 1$. The assumption that $\sqrt 2$ is rational is therefore untenable, and $\sqrt 2$ is irrational. ∎

Remark. The same argument shows $\sqrt{n}$ is irrational whenever $n$ is a natural number that is not a perfect square. The proofs that $\pi$ and $e$ are irrational are far harder and belong to analysis; we cite them but do not prove them here.

Historical note. The discovery that the diagonal of a unit square (length $\sqrt 2$) is incommensurable with its side shattered the Pythagorean belief that all magnitudes are ratios of whole numbers. It is one of the earliest known proofs by contradiction and one of the first genuine theorems about the structure of the number line.

1.4 Subsets and inclusion #

4.1 The definition #

Definition (subset). $A$ is a subset of $B$, written $A \subseteq B$, when every element of $A$ is also an element of $B$:

$$A \subseteq B \;\iff\; (\forall x)\,(x \in A \implies x \in B).$$

If in addition $A \ne B$ — i.e. $B$ has at least one element not in $A$ — we call $A$ a proper subset of $B$ and write $A \subset B$ (some texts write $A \subsetneq B$ to stress properness).

Intuitively $A \subseteq B$ says “$A$ fits inside $B$.” The definition is a universally quantified conditional, and that logical shape dictates how we prove inclusions: to prove $A \subseteq B$, take an arbitrary $x \in A$ and derive $x \in B$. This “take an arbitrary element” move is the single most common opening line in set-theoretic proofs.

Example 1.8. Let $A = \{1, 2\}$ and $B = \{1, 2, 3, 4\}$. Every element of $A$ ($1$ and $2$) lies in $B$, so $A \subseteq B$; and since $3 \in B$ but $3 \notin A$, the inclusion is proper: $A \subset B$. By contrast, $\{1, 5\} \not\subseteq B$ because $5 \notin B$ — a single “witness” element outside $B$ suffices to refute an inclusion.

Common pitfall ($\in$ vs. $\subseteq$). These are different relations. With $A = \{1, 2\}$: $1 \in A$ (true), $\{1\} \subseteq A$ (true), but $1 \subseteq A$ is a type error ($1$ is not a set) and $\{1\} \in A$ is false ($A$’s elements are $1$ and $2$, not the set $\{1\}$). The traps get sharper with nested sets: for $A = \{1, \{2\}\}$ we have $\{2\} \in A$ and $\{\{2\}\} \subseteq A$, but $2 \notin A$ and $\{2\} \not\subseteq A$.

4.2 The empty set is a subset of everything (vacuous truth) #

Our first structural theorem is one students often find surprising, because it seems to say “nothing is inside everything.” The resolution is the logical principle of vacuous truth: a conditional $P \implies Q$ whose hypothesis $P$ is false is counted as true, regardless of $Q$. (Compare an unfulfillable promise: “if you finish a marathon in $1$ hour, I’ll pay you 1000 dollars” is never broken if no such marathon is ever run.) Vacuous truth is developed fully in the propositional-logic material; here we use it.

Proposition 1.9. For every set $A$, $\;\varnothing \subseteq A$.

Proof. By definition we must show $(\forall x)\,(x \in \varnothing \implies x \in A)$. Let $x$ be arbitrary. The hypothesis “$x \in \varnothing$” is false, because the empty set has no elements. A conditional with a false hypothesis is true (vacuous truth). Hence $x \in \varnothing \implies x \in A$ holds for this — and therefore every — $x$. Thus $\varnothing \subseteq A$. ∎

Alternative proof (by contradiction). Suppose $\varnothing \not\subseteq A$. By the definition of $\subseteq$, this failure means there exists an element $x$ with $x \in \varnothing$ and $x \notin A$. But $x \in \varnothing$ is impossible. This contradiction shows $\varnothing \subseteq A$. ∎

The second proof is worth studying: it shows how to negate a subset claim. The negation of “$\forall x\,(x\in A \Rightarrow x \in B)$” is “$\exists x\,(x \in A \wedge x \notin B)$.” To disprove $A\subseteq B$ you exhibit one such witness $x$; to prove it you rule all witnesses out.

4.3 Reflexivity and transitivity of $\subseteq$ #

Proposition 1.10 (reflexivity). For every set $A$, $\;A \subseteq A$.

Proof. For every $x$, the conditional $x \in A \implies x \in A$ is true (a statement implies itself). Hence $A \subseteq A$. ∎

Proposition 1.11 (transitivity). If $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$.

Proof. Let $x$ be an arbitrary element of $A$. Since $A \subseteq B$, from $x \in A$ we get $x \in B$. Since $B \subseteq C$, from $x \in B$ we get $x \in C$. Thus every element of $A$ is an element of $C$, i.e. $A \subseteq C$. ∎

Remark (a preview of order theory). Propositions 1.10, 1.11 and Theorem 1.13 (antisymmetry) together say that $\subseteq$ is a partial order on any collection of sets: reflexive, antisymmetric, and transitive. Partial orders are studied systematically in the lecture on relations (Lecture 3); the power set $\mathcal{P}(A)$ ordered by $\subseteq$ is the prototypical example and reappears in the lecture on Boolean algebras and lattices.

Example 1.12. $\{1\} \subseteq \{1,2\} \subseteq \{1,2,3\}$, so by transitivity $\{1\}\subseteq\{1,2,3\}$ — as is directly visible. Transitivity earns its keep in proofs where the intermediate set $B$ is not something you would want to compute element-by-element.

1.5 Set equality and the double-inclusion method #

5.1 Extensionality #

When are two sets equal? The guiding principle, called the axiom of extensionality, is that a set is nothing more than its members:

Definition / Axiom (extensionality). Two sets are equal, $A = B$, exactly when they have the same elements:

$$A = B \;\iff\; (\forall x)\,(x \in A \iff x \in B).$$

Extensionality is why order and repetition inside braces do not matter (§1.1): $\{1,2,2,3\}$ and $\{3,1,2\}$ have the same members, hence are equal. It also means sets described in totally different ways can turn out equal — and proving such equalities is a core skill.

5.2 The double-inclusion criterion #

The biconditional “$x \in A \iff x \in B$” splits into two conditionals, and those two conditionals are precisely two subset statements. This yields the workhorse theorem of the whole chapter.

Theorem 1.13 (equality via double inclusion; antisymmetry of $\subseteq$). For all sets $A, B$,

$$A = B \;\iff\; \big(A \subseteq B \ \text{and}\ B \subseteq A\big).$$

Proof. ($\Rightarrow$) Suppose $A = B$. By extensionality, for every $x$ we have $x \in A \iff x \in B$. In particular $x \in A \implies x \in B$ (so $A \subseteq B$) and $x \in B \implies x \in A$ (so $B \subseteq A$).

($\Leftarrow$) Suppose $A \subseteq B$ and $B \subseteq A$. Let $x$ be arbitrary. From $A \subseteq B$ we have $x \in A \implies x \in B$; from $B \subseteq A$ we have $x \in B \implies x \in A$. Combining the two conditionals, $x \in A \iff x \in B$. As $x$ was arbitrary, $A$ and $B$ have the same elements, so by extensionality $A = B$. ∎

The double-inclusion proof template. To prove two sets $A$ and $B$ are equal:

1. ($\subseteq$) Assume $x \in A$; through valid steps deduce $x \in B$. Conclude $A \subseteq B$.
2. ($\supseteq$) Assume $x \in B$; through valid steps deduce $x \in A$. Conclude $B \subseteq A$.
3. By Theorem 1.13, $A = B$. ∎

This template appears constantly in Lecture 2, where every set identity (De Morgan’s laws, distributivity, absorption, …) is proved this way.

5.3 Worked examples of set equality #

Example 1.14 (order and repetition). $\{1, 2, 3\} = \{3, 2, 1\} = \{1, 1, 2, 3\}$. All three descriptions list exactly the members $1, 2, 3$; by extensionality they denote one set.

Example 1.15 (double inclusion, roster vs. set-builder). Let $A = \{\, x \in \mathbb{Z} \mid x^2 = 1 \,\}$ and $B = \{-1, 1\}$. We claim $A = B$.

Proof. ($\subseteq$) Let $x \in A$. Then $x \in \mathbb Z$ and $x^2 = 1$, so $x^2 - 1 = 0$, i.e. $(x-1)(x+1) = 0$; hence $x = 1$ or $x = -1$. In either case $x \in B$. Thus $A \subseteq B$. ($\supseteq$) $1 \in \mathbb Z$ and $1^2 = 1$, so $1 \in A$; likewise $(-1)^2 = 1$, so $-1 \in A$. Hence $B \subseteq A$. By double inclusion, $A = B$. ∎

Example 1.16 (two set-builder descriptions). Let

$$E = \{\, 2k \mid k \in \mathbb{Z} \,\}, \qquad F = \{\, n \in \mathbb{Z} \mid n^2 \text{ is even} \,\}.$$

We claim $E = F$ (both are “the even integers”).

Proof. ($\subseteq$) Let $n \in E$, so $n = 2k$ for some $k \in \mathbb Z$. Then $n^2 = 4k^2 = 2(2k^2)$ is even, so $n \in F$. ($\supseteq$) Let $n \in F$, so $n^2$ is even. If $n$ were odd, then $n^2$ would be odd (§1.3.1); since $n^2$ is even, $n$ must be even, i.e. $n = 2k$ for some $k \in \mathbb Z$, so $n \in E$. Hence $F \subseteq E$, and $E = F$. ∎

Example 1.17 (unequal sets — refute one inclusion). $\{1, 2, 3\} \ne \{1, 2\}$, because $3$ belongs to the first set but not the second, so the inclusion $\{1,2,3\} \subseteq \{1,2\}$ fails. To show inequality it is enough to break one of the two inclusions.

Example 1.18 (element vs. singleton, revisited). $2 \ne \{2\}$: the left side is a number, the right side is a set. Likewise $\{2\} \ne \{\{2\}\}$: the left side’s element is $2$, the right side’s element is $\{2\}$, and $2 \ne \{2\}$.

Common pitfall (proving equality with only one inclusion). A frequent error is to prove $A \subseteq B$ and stop, concluding $A = B$. One inclusion gives only “$A$ is part of $B$,” which is consistent with $A \ne B$. Both directions are needed. Conversely, when the two directions have identical-looking steps, say so explicitly (“by the symmetric argument”) rather than omitting a direction.

1.6 Ways to describe a set #

There are three standard ways to specify which elements a set contains.

6.1 Roster (list) notation #

List the elements explicitly between braces, e.g. $A = \{2, 4, 6, 8\}$. For a clear, unambiguous pattern an ellipsis is permitted: $\mathbb{N} = \{1, 2, 3, \dots\}$ or $\{2, 4, 6, \dots, 100\}$. Roster notation is only practical when the set is small or its pattern is obvious.

6.2 Set-builder (predicate) notation #

Describe the elements by a property (predicate) $P(x)$ they must satisfy:

$$A = \{\, x \mid P(x) \,\} \qquad (\text{read: "all } x \text{ such that } P(x)").$$

Almost always a domain $U$ is supplied to keep the definition safe and definite (§1.12 explains why this matters):

$$A = \{\, x \in U \mid P(x) \,\}.$$

This separation form carves out of $U$ exactly the elements satisfying $P$.

Notation. The bar $\mid$ is read “such that.” Some texts — and a few later sections here — write a colon instead, $\{\, x : P(x) \,\}$; the two are interchangeable.

A second, closely related form specifies elements by an expression ranging over a domain — the image or replacement form:

$$\{\, f(x) \mid x \in D \,\}, \qquad\text{e.g.}\qquad \{\, n^2 \mid n \in \mathbb{N} \,\} = \{1, 4, 9, 16, \dots\}.$$

Here the bar separates a rule for producing elements (left) from the range of the input (right).

Example 1.19. The roster $\{2, 4, 6, 8, 10\}$ equals the set-builder description $\{\, x \in \mathbb{N} \mid x \text{ is even and } x \le 10 \,\}$.

Example 1.20 (roster impossible). $\{\, x \in \mathbb{R} \mid x^2 < 9 \,\}$ is the open interval $(-3, 3)$. Roster notation cannot express it (uncountably many elements — §1.9), so set-builder notation is essential, not merely convenient.

Example 1.21 (empty via unsatisfiable predicate). $\{\, x \in \mathbb{R} \mid x^2 = -1 \,\} = \varnothing$, since no real number squares to a negative value. A set-builder description names $\varnothing$ precisely when its predicate is unsatisfiable over the domain.

Example 1.22 (congruences). $\{\, x \in \mathbb{Z} \mid x \equiv 1 \pmod 3 \,\} = \{\dots, -5, -2, 1, 4, 7, \dots\}$, the integers leaving remainder $1$ on division by $3$. Such sets (residue classes) reappear in the number-theory and modular-arithmetic material.

Example 1.23 (a set of pairs). $\{\, (x,y) \in \mathbb{R}^2 \mid x^2 + y^2 = 1 \,\}$ is the unit circle in the plane. Set-builder notation ranges naturally over tuples (§1.11), which is how curves, relations, and graphs get defined.

Example 1.24 (the rationals). $\mathbb{Q} = \{\, \tfrac{p}{q} \mid p, q \in \mathbb{Z},\ q \ne 0 \,\}$. Note this uses the image form; many different pairs $(p,q)$ name the same rational ($\tfrac12 = \tfrac24$), which is fine — extensionality collapses the duplicates.

Common pitfall (unrestricted comprehension). Writing $\{\,x \mid P(x)\,\}$ with no domain — quantifying over “all objects whatsoever” — is dangerous. Taking $P(x)$ to be “$x \notin x$” produces Russell’s paradoxical set (§1.12). Modern set theory only permits the separation form $\{\,x \in U \mid P(x)\,\}$, carving from a set $U$ already known to exist. In this course, always give the domain.

6.3 Recursive (inductive) definition #

Give base elements and rules that generate new elements from old ones. This third style is important enough — and central enough to computer science — to get its own section.

1.7 Recursive (inductive) definitions #

7.1 Motivation and the three parts #

How do you define an infinite set precisely, using only finitely many words, without a closed formula? You bootstrap: declare a few elements outright, then give rules that manufacture new elements from ones you already have. This is exactly how programmers define linked lists (“a list is empty, or a head followed by a list”), how compilers define the syntax of expressions, and how logicians define formulas.

Definition (recursive/inductive definition). A recursive definition of a set $S$ has three parts:

• a base case (basis) — one or more elements declared to be in $S$ outright;
• a recursive rule (induction step) — how to build new elements of $S$ from elements already known to be in $S$;
• a closure clause — $S$ contains nothing except what the basis and rules force (usually left implicit).

The closure clause matters: without it, “the set containing $2$ and closed under $+2$” could be $\{2,4,6,\dots\}$ or all of $\mathbb Z$ or all of $\mathbb R$. Closure makes $S$ the smallest set satisfying the basis and rule.

7.2 Examples #

Example 1.25 (positive even numbers). Define $E$ by basis $2 \in E$; rule if $n \in E$ then $n+2 \in E$. Applying the rule repeatedly gives $2, 4, 6, 8, \dots$, so $E = \{\, 2k \mid k \in \mathbb{N} \,\}$.

Example 1.26 (powers of two). Basis $1 \in S$; rule if $x \in S$ then $2x \in S$. This generates $S = \{1, 2, 4, 8, 16, \dots\} = \{\,2^{k} \mid k \in \mathbb{N}_0\,\}$.

Example 1.27 (strings over an alphabet). Fix a finite alphabet $\Sigma$ (e.g. $\Sigma = \{0,1\}$). The set $\Sigma^{*}$ of all finite strings is defined by basis the empty string $\varepsilon \in \Sigma^{*}$; rule if $w \in \Sigma^{*}$ and $a \in \Sigma$ then the concatenation $wa \in \Sigma^{*}$. This is the founding definition of formal-language theory (used heavily in the lectures on regular languages and automata): a language is then simply a subset of $\Sigma^{*}$.

Example 1.28 (balanced parentheses / the Dyck language). Over $\Sigma = \{\,(\,,\,)\,\}$, define $D$ by: basis $\varepsilon \in D$; rules if $w \in D$ then $(w) \in D$, and if $w_1, w_2 \in D$ then $w_1 w_2 \in D$. Then $D$ is exactly the set of correctly-nested parenthesis strings: $\varepsilon$, (), (()), ()(), (()()), … Recursively-defined languages like this are what parsers recognize.

Example 1.29 (arithmetic expressions). Over operands $\{a, b, c\}$ and operators $\{+, \times\}$: basis each of $a, b, c$ is an expression; rule if $E_1$ and $E_2$ are expressions then so are $(E_1 + E_2)$ and $(E_1 \times E_2)$. This generates all fully-parenthesized expressions such as $((a+b)\times c)$ — the abstract syntax that every compiler builds.

Example 1.30 (binary trees). Basis the empty tree $\bullet$ is a binary tree; rule if $L$ and $R$ are binary trees then the ordered triple $\langle L,\, r,\, R\rangle$ (left subtree, root, right subtree) is a binary tree. Data structures are recursively-defined sets; this is why they pair so naturally with recursion and induction in code.

Remark (structural induction). Every recursively-defined set comes with a matching proof method: to show every element of $S$ has a property $Q$, prove $Q$ holds for the basis elements and is preserved by each rule. This is structural induction, the generalization of ordinary induction on $\mathbb N$, developed in the lecture on mathematical induction. For instance, one proves “every string in the Dyck language $D$ has equally many ( and )” by structural induction on the definition in Example 1.28.

Remark (the natural numbers are themselves recursive). Even $\mathbb N$ can be built recursively. In the von Neumann construction one sets $0 = \varnothing$ and $n + 1 = n \cup \{n\}$, so

$$0 = \varnothing,\quad 1 = \{\varnothing\},\quad 2 = \{\varnothing,\{\varnothing\}\},\quad 3 = \{\varnothing,\{\varnothing\},\{\varnothing,\{\varnothing\}\}\}, \dots$$

Each number is the set of all smaller numbers, so $|n| = n$. This shows sets are expressive enough to encode the counting numbers themselves — the whole of mathematics can, in principle, be founded on the single relation $\in$.

1.8 Cardinality — the “power” of a set #

8.1 Counting elements #

Definition (cardinality). The cardinality of a set $A$, denoted $|A|$, is the number of elements it contains. A set is finite if $|A| = n$ for some $n \in \{0, 1, 2, \dots\}$, and infinite otherwise.

(In older texts and the course deck, cardinality is called the power of a set — Cantor’s original German term was Mächtigkeit. The unrelated “power set” of §1.10 borrows the same word.)

• $|\varnothing| = 0$.
• $|\{a, b, c\}| = 3$.
• $|\{1, 1, 2\}| = 2$ — duplicates are not counted twice (extensionality).
• $|\{\varnothing, \{\varnothing\}\}| = 2$ — two distinct elements.

Example 1.31. For $A = \{a, e, i, o, u\}$ we have $|A| = 5$. For $B = \{\, x \in \mathbb{Z} \mid -2 \le x \le 2 \,\} = \{-2,-1,0,1,2\}$ we have $|B| = 5$ as well. So $|A| = |B|$ even though $A \ne B$: cardinality measures how many, not which.

8.2 Equinumerosity: comparing sizes with bijections #

Example 1.31 hints at the deep idea that drives the rest of this chapter: two sets have the “same size” when their elements can be matched up one-to-one, with none left over on either side. This matching idea — not counting — is what generalizes to infinite sets.

Definition (equinumerous). Sets $A$ and $B$ are equinumerous, written $|A| = |B|$, if there is a bijection $f : A \to B$ (a function that is both injective — no two inputs share an output — and surjective — every output is hit). We write $|A| \le |B|$ if there is an injection $A \to B$.

For finite sets this agrees with ordinary counting. Its power is that it needs no notion of “number” at all, so it applies to infinite sets, where it produces genuinely surprising results (§1.9). Functions, injectivity, surjectivity, and bijectivity are defined here as we need them, as counting tools; functions in their own right appear as a special kind of relation in Lecture 3 (§3.12).

Remark. Exhibiting a bijection is the gold-standard way to prove two sets have equal size — you will see it used to prove $|\mathcal{P}(A)| = 2^{n}$ in §1.10 and $|A \times B| = |A|\,|B|$ in §1.11, and it underlies the combinatorial “bijective proofs” in the combinatorics of Lecture 13.

1.9 Countable and uncountable sets #

9.1 Are all infinities the same size? #

Here is one of the most beautiful discoveries in mathematics, due to Georg Cantor (1870s–1880s): there are different sizes of infinity. The infinite set $\mathbb{N}$ can be matched one-to-one with $\mathbb Z$ and even with $\mathbb Q$, but cannot be matched with $\mathbb R$ — the reals are strictly more numerous. We sketch why. These facts are not needed arithmetically in the rest of the course, but the distinction between countable and uncountable is genuinely used: e.g. the set of all programs is countable while the set of all functions $\mathbb N \to \{0,1\}$ is uncountable, which is the seed of the existence of uncomputable functions (a theme of the computability material).

Definition (countable / uncountable). A set $A$ is countably infinite if $|A| = |\mathbb{N}|$, i.e. there is a bijection $\mathbb{N} \to A$ — equivalently, $A$’s elements can be arranged in an infinite list $a_1, a_2, a_3, \dots$ with each element appearing exactly once. A set is countable if it is finite or countably infinite, and uncountable otherwise. The cardinality of $\mathbb N$ is written $\aleph_0$ (“aleph-null”).

9.2 $\mathbb{Z}$ and $\mathbb{Q}$ are countable #

Theorem 1.32. $\mathbb{Z}$ is countably infinite.

Proof. We exhibit a bijection $f : \mathbb{N} \to \mathbb{Z}$ by listing the integers so that each appears exactly once:

$$0,\ 1,\ -1,\ 2,\ -2,\ 3,\ -3,\ \dots$$

Explicitly, $f(n) = \dfrac{n}{2}$ if $n$ is even, and $f(n) = \dfrac{1-n}{2}$ if $n$ is odd (recall $\mathbb N = \{1,2,3,\dots\}$). Then $f(1)=0,\ f(2)=1,\ f(3)=-1,\ f(4)=2,\ f(5)=-2,\dots$ Every integer appears exactly once — the non-positive integers at odd inputs, the positive integers at even inputs — so $f$ is a bijection. Hence $|\mathbb Z| = |\mathbb N| = \aleph_0$. ∎

The lesson is counterintuitive: $\mathbb Z$ “looks twice as big” as $\mathbb N$, yet the two are equinumerous. With infinite sets, a proper subset can have the same cardinality as the whole (indeed this is a characterization of infinity).

Theorem 1.33 (Cantor). $\mathbb{Q}$ is countably infinite.

Proof sketch. Arrange the positive rationals $\tfrac{p}{q}$ ($p, q \in \mathbb{N}$) in an infinite grid, row $p$ and column $q$:

$$\begin{array}{ccccc} \tfrac11 & \tfrac12 & \tfrac13 & \tfrac14 & \cdots\\ \tfrac21 & \tfrac22 & \tfrac23 & \tfrac24 & \cdots\\ \tfrac31 & \tfrac32 & \tfrac33 & \tfrac34 & \cdots\\ \vdots & \vdots & \vdots & \vdots & \ddots \end{array}$$

Traverse the grid along successive anti-diagonals ($\tfrac11;\ \tfrac21,\tfrac12;\ \tfrac31,\tfrac22,\tfrac13;\ \dots$), skipping any fraction not in lowest terms (so each rational is counted once). This lists every positive rational: $\mathbb Q^{+}$ is countable. Now interleave with $0$ and the negatives — $0, q_1, -q_1, q_2, -q_2, \dots$ — to list all of $\mathbb Q$. Hence $\mathbb Q$ is countably infinite. ∎

The same anti-diagonal “dovetailing” shows that a countable union of countable sets is countable, and that $\mathbb N \times \mathbb N$ is countable — facts reused throughout computer science (e.g. enumerating all pairs, all strings, all programs).

9.3 $\mathbb{R}$ is uncountable: Cantor’s diagonal argument #

Now the punchline: no list can exhaust the reals.

Theorem 1.34 (Cantor, 1891). The interval $(0,1) \subseteq \mathbb{R}$ is uncountable. Consequently $\mathbb{R}$ is uncountable.

Proof (diagonalization). Suppose, for contradiction, that $(0,1)$ is countable. Then its elements can be listed as a sequence $x_1, x_2, x_3, \dots$ containing every number in $(0,1)$. Write each in decimal:

$$\begin{array}{lcl} x_1 &=& 0.\,\mathbf{d_{11}}\,d_{12}\,d_{13}\,d_{14}\cdots\\ x_2 &=& 0.\,d_{21}\,\mathbf{d_{22}}\,d_{23}\,d_{24}\cdots\\ x_3 &=& 0.\,d_{31}\,d_{32}\,\mathbf{d_{33}}\,d_{34}\cdots\\ x_4 &=& 0.\,d_{41}\,d_{42}\,d_{43}\,\mathbf{d_{44}}\cdots\\ &\vdots& \end{array}$$

where $d_{ij} \in \{0,1,\dots,9\}$ is the $j$-th decimal digit of $x_i$. Now construct a new number $y = 0.\,e_1 e_2 e_3 \cdots$ by altering the diagonal digits $d_{ii}$ (shown in bold):

$$e_i \;=\; \begin{cases} 5 & \text{if } d_{ii} \ne 5,\\[2pt] 6 & \text{if } d_{ii} = 5.\end{cases}$$

By construction $y \in (0,1)$, and $e_i \ne d_{ii}$ for every $i$. Therefore $y$ differs from $x_i$ in the $i$-th decimal place, for every $i$, so $y \ne x_i$ for all $i$. But the list was supposed to contain every element of $(0,1)$, and $y \in (0,1)$ — contradiction. Hence $(0,1)$ cannot be listed: it is uncountable. Since $(0,1) \subseteq \mathbb R$, the larger set $\mathbb R$ is uncountable as well. ∎

Remark (why the digits $5$ and $6$). A real number can have two decimal expansions only when one ends in all $9$s and the other in all $0$s (e.g. $0.4999\ldots = 0.5000\ldots$). We chose $e_i \in \{5,6\}$ precisely so that $y$ uses no $0$s or $9$s; hence $y$ has a unique decimal expansion, and the guarantee “$y$ differs from $x_i$ at digit $i$” cannot be voided by an alternate expansion of $x_i$. This care is what makes the argument airtight rather than merely suggestive.

Remark (the continuum). Cantor’s argument shows $|\mathbb N| < |\mathbb R|$: the reals form a strictly larger infinity, the continuum. So the “gap” between $\mathbb Q$ and $\mathbb R$ that Theorem 1.7 opened for the single number $\sqrt 2$ is in fact enormous — the irrationals are uncountable, while the rationals we can list are, in this precise sense, negligibly few.

9.4 Cantor’s theorem: the power set is always bigger #

Diagonalization is not a trick special to decimals; it is a general phenomenon.

Theorem 1.35 (Cantor’s theorem). For every set $A$, there is no surjection $f : A \to \mathcal{P}(A)$. Consequently $|A| < |\mathcal{P}(A)|$ — a set always has strictly fewer elements than its power set, even when $A$ is infinite.

Proof. Let $f : A \to \mathcal{P}(A)$ be any function; we show $f$ misses some subset. Define the “diagonal” set

$$D = \{\, x \in A \mid x \notin f(x) \,\} \subseteq A, \quad\text{so } D \in \mathcal{P}(A).$$

Suppose $D$ were in the image of $f$, say $D = f(a)$ for some $a \in A$. Ask whether $a \in D$. By the definition of $D$,

$$a \in D \iff a \notin f(a) \iff a \notin D,$$

since $f(a) = D$. Thus “$a \in D$” holds iff it fails — a contradiction. So no such $a$ exists, $D$ is not in the image of $f$, and $f$ is not surjective. As no surjection $A \to \mathcal{P}(A)$ exists (while $x \mapsto \{x\}$ is an injection $A \to \mathcal{P}(A)$), we conclude $|A| < |\mathcal{P}(A)|$. ∎

Taking $A = \mathbb N$ yields $|\mathbb N| < |\mathcal{P}(\mathbb N)|$, so $\mathcal{P}(\mathbb N)$ is uncountable (in fact $|\mathcal{P}(\mathbb N)| = |\mathbb R|$). Iterating, $|A| < |\mathcal{P}(A)| < |\mathcal{P}(\mathcal{P}(A))| < \cdots$: there is no largest infinity. Notice, too, how the diagonal set $D$ in this proof is the very same self-referential construction that produces Russell’s paradox in §1.12 — the two are the same idea wearing different clothes.

Historical note. Cantor’s creation of set theory and his hierarchy of infinities were revolutionary and, at first, fiercely resisted. Today his diagonal method is a cornerstone not only of set theory but of computability (the undecidability of the halting problem is a diagonal argument) and of logic (Gödel’s incompleteness theorems).

1.10 The power set #

10.1 Definition and examples #

Since subsets of a set $A$ are themselves objects, we may collect all of them into a new set.

Definition (power set). The power set of $A$, written $\mathcal{P}(A)$ (also $P(A)$ or $2^{A}$), is the set of all subsets of $A$:

$$\mathcal{P}(A) = \{\, S \mid S \subseteq A \,\}.$$

Its elements are themselves sets. Both $\varnothing$ and $A$ always belong to $\mathcal{P}(A)$ (by Proposition 1.9 and 4.2).

Example 1.36. $\mathcal{P}(\varnothing) = \{\varnothing\}$ — one element (not zero!), so $|\mathcal{P}(\varnothing)| = 1$. And $\mathcal{P}(\{a\}) = \{\varnothing, \{a\}\}$, with $|\mathcal{P}(\{a\})| = 2$. And $\mathcal{P}(\{a,b\}) = \{\varnothing, \{a\}, \{b\}, \{a,b\}\}$, with $|\mathcal{P}(\{a,b\})| = 4$.

Example 1.37 (from the deck). For $A = \{1, 2, 3, 4\}$, the power set has $16$ members:

$$\mathcal{P}(A) = \Big\{\ \varnothing,\ \{1\},\{2\},\{3\},\{4\},\ \{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\},$$

$$\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\},\ \{1,2,3,4\}\ \Big\}.$$

Grouped by size: one subset of size $0$, four of size $1$, six of size $2$, four of size $3$, and one of size $4$ — a total of $1+4+6+4+1 = 16$.