# 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. | Symbol | Name | Description / typical elements | |--------|------|-------------------------------| | $\mathbb{N}$ | Natural numbers | $\{1, 2, 3, 4, \dots\}$ — the counting numbers | | $\mathbb{Z}$ | Integers | $\{\dots, -3, -2, -1, 0, 1, 2, 3, \dots\}$ | | $\mathbb{Q}$ | Rational numbers | fractions $\tfrac{p}{q}$ with $p,q \in \mathbb{Z}$, $q \ne 0$, e.g. $\tfrac{4}{2}, \tfrac{1}{2}, \tfrac{4}{10}$ | | — | Irrational numbers | reals that are *not* rational, e.g. $\sqrt{2}, \pi, e$ | | $\mathbb{R}$ | Real numbers | all rationals **and** all irrationals together | | $I$ | Imaginary numbers | $\{\,bi \mid b \in \mathbb{R}\,\}$ where $i^2 = -1$ | | $\mathbb{C}$ | Complex numbers | $\{\,a + bi \mid a, b \in \mathbb{R}\,\}$ | 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$). ![The numeric sets nested inside one another: ℕ ⊂ ℤ ⊂ ℚ ⊂ ℝ ⊂ ℂ](img/l01_hierarchy.png) **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 **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. ![Venn diagram of A ⊆ B: circle A sits entirely inside circle B](img/l01_subset.png) **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. ![A recursive definition generating strings as a tree from basis, rule, and closure](img/l01_recursive.png) ### 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). ![ℕ pairs one-to-one with ℤ (countable), while ℝ defeats any listing by diagonalization (uncountable)](img/l01_countability.png) > **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). ![The power set \mathcal{P}({a,b,c}) as a lattice of all 2³ = 8 subsets ordered by inclusion](img/l01_powerset.png) **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$. > **Common pitfall.** $|\mathcal{P}(\varnothing)| = 1$, not $0$: the empty set has exactly one > subset, namely itself. Similarly $\varnothing \in \mathcal{P}(A)$ for every $A$, so $\mathcal{P}(A)$ > is never empty even when $A$ is. ### 10.2 The size of the power set The grouping in Example 1.37 (with row sums $1,4,6,4,1$ — the binomial coefficients $\binom{4}{k}$) points to the central theorem. We give **two** independent proofs, because each teaches a reusable technique. > **Theorem 1.38.** If $A$ is finite with $|A| = n$, then $|\mathcal{P}(A)| = 2^{n}$. #### Proof 1 — by a bijection with bit-strings *Proof.* List the elements as $A = \{a_1, a_2, \dots, a_n\}$. Let $\{0,1\}^{n}$ be the set of length-$n$ **bit-strings** (ordered $n$-tuples of $0$s and $1$s). Define $\varphi : \mathcal{P}(A) \to \{0,1\}^{n}$ by sending each subset $S$ to its **characteristic vector** $$ \varphi(S) = (b_1, b_2, \dots, b_n), \qquad b_i = \begin{cases} 1 & \text{if } a_i \in S,\\ 0 & \text{if } a_i \notin S.\end{cases} $$ We show $\varphi$ is a bijection. - **Injective.** Suppose $\varphi(S) = \varphi(T)$. Then for each $i$, $a_i \in S \iff b_i = 1 \iff a_i \in T$. So $S$ and $T$ contain exactly the same $a_i$, i.e. $S = T$. - **Surjective.** Given any bit-string $(b_1,\dots,b_n) \in \{0,1\}^{n}$, form $S = \{\, a_i \mid b_i = 1 \,\} \subseteq A$. Then $\varphi(S) = (b_1,\dots,b_n)$. So every bit-string is hit. Hence $\varphi$ is a bijection, and $|\mathcal{P}(A)| = |\{0,1\}^{n}|$. Finally $|\{0,1\}^{n}| = 2^{n}$: a length-$n$ bit-string is built by choosing each of the $n$ coordinates independently from $2$ options, so by the product rule (Lecture 13's combinatorics) there are $2 \cdot 2 \cdots 2 = 2^{n}$ of them. Therefore $|\mathcal{P}(A)| = 2^{n}$. ∎ This bijection is not merely a counting device — it *is* how sets are stored in computers (§1.11.4 / §1.13): a subset of an $n$-element universe is a single $n$-bit word. #### Proof 2 — by induction on $n$ *Proof.* We induct on $n = |A|$. *Base case* ($n = 0$). The only set with $0$ elements is $\varnothing$, and $\mathcal{P}(\varnothing) = \{\varnothing\}$, so $|\mathcal{P}(\varnothing)| = 1 = 2^{0}$. ✓ *Inductive step.* Assume (induction hypothesis) that **every** set with $k$ elements has exactly $2^{k}$ subsets. Let $A$ be any set with $|A| = k+1$. Fix an element $a \in A$ and put $A' = A \setminus \{a\}$, so $|A'| = k$. Split the subsets of $A$ into two classes according to whether they contain $a$: - **Subsets not containing $a$.** These are precisely the subsets of $A'$. By the induction hypothesis there are $2^{k}$ of them. - **Subsets containing $a$.** Each has the form $S \cup \{a\}$ for a unique $S \subseteq A'$, and conversely each $S \subseteq A'$ yields one such subset. This pairing is a bijection with the subsets of $A'$, so again there are $2^{k}$. The two classes are disjoint (a set either contains $a$ or not) and together exhaust $\mathcal{P}(A)$. By the sum rule, $$ |\mathcal{P}(A)| = 2^{k} + 2^{k} = 2 \cdot 2^{k} = 2^{k+1}. $$ This completes the inductive step. By the principle of mathematical induction, $|\mathcal{P}(A)| = 2^{n}$ for all $n \ge 0$. ∎ > **Remark (why prove it twice).** The bijective proof gives *insight* — subsets > "are" bit-strings — and generalizes to a formula-free count. The inductive proof > models the standard "fix one element, split into two cases" strategy that recurs > across combinatorics. Meeting both now prepares you for the combinatorics of Lecture 13. > **Corollary 1.39 (a binomial identity).** For every $n \ge 0$, > $$ \sum_{k=0}^{n} \binom{n}{k} = 2^{n}. $$ > *Proof.* Classify the subsets of an $n$-set by their size $k$. The number of > $k$-element subsets is $\binom{n}{k}$ (this is the definition of the binomial > coefficient, established in the combinatorics of Lecture 13). Summing over all possible > sizes $k = 0, 1, \dots, n$ counts *every* subset exactly once, which by > Theorem 1.38 totals $2^{n}$. ∎ For $n = 4$ this reads > $1+4+6+4+1 = 16$, matching Example 1.37 exactly. > **Remark (the notation $2^{A}$).** The alternative symbol $2^{A}$ for the power > set is deliberate: writing $2 = \{0,1\}$, the set $2^{A}$ of all functions > $A \to \{0,1\}$ *is* (via characteristic functions) the set of subsets of $A$, > and its size $2^{|A|}$ matches. This viewpoint also gives meaning to $|\mathcal{P}(A)|$ for > *infinite* $A$: $|\mathcal{P}(\mathbb N)| = 2^{\aleph_0}$, the continuum of §1.9. --- ### 10.3 The power set and the set operations The power set interacts cleanly with the operations of Lecture 2. For all sets $A,B$: - $\mathcal{P}(A\cap B)=\mathcal{P}(A)\cap\mathcal{P}(B)$ — a set is a subset of **both** $A$ and $B$ exactly when it is a subset of $A\cap B$; - $\mathcal{P}(A)\cup\mathcal{P}(B)\subseteq\mathcal{P}(A\cup B)$, and the inclusion is usually **strict**: $\{a,b\}\in\mathcal{P}(\{a\}\cup\{b\})$ but lies in neither $\mathcal{P}(\{a\})$ nor $\mathcal{P}(\{b\})$; - $\mathcal{P}(A)\subseteq\mathcal{P}(B)\iff A\subseteq B$ — **monotonicity**, since $A\in\mathcal{P}(A)$ then forces $A\in\mathcal{P}(B)$, i.e. $A\subseteq B$. Each is a one-line element-chase: rewrite "$X\in\mathcal{P}(\cdot)$" as "$X\subseteq\cdot$" and unfold the definitions of $\cap,\cup,\subseteq$. ## 1.11 Ordered pairs, tuples, and the Cartesian product ### 11.1 When order matters Sets deliberately forget order, but a great deal of mathematics and computing needs to *remember* it: the point $(3,5)$ in the plane is not $(5,3)$; the database row `("Ada", 1815)` pairs a name with a year in a fixed layout; a function's input $\to$ output pairing is directional. For this we use ordered pairs. > **Definition (ordered pair).** An **ordered pair** **$(a, b)$** records a *first > component* $a$ and a *second component* $b$. Its defining property is that order > is significant: > $$ (a, b) = (c, d) \;\iff\; a = c \ \text{and}\ b = d. $$ In particular $(1, 2) \ne (2, 1)$, whereas the sets $\{1,2\}$ and $\{2,1\}$ are equal. Repetition is allowed in a pair: $(1,1)$ is perfectly valid, though $\{1,1\} = \{1\}$ as a set. > **Remark (pairs are secretly sets — Kuratowski).** Ordered pairs need not be a new > primitive; they can be *encoded* as sets. Kuratowski's definition is > $$ (a,b) := \{\, \{a\},\ \{a,b\} \,\}. $$ > One can prove from this that $(a,b) = (c,d) \iff a=c \wedge b=d$, recovering > exactly the defining property. This is a recurring theme: with enough ingenuity, > *every* discrete structure (pairs, numbers, functions, relations) can be built > out of plain sets and the single relation $\in$. We will use pairs as if > primitive and never unfold the encoding. > **Definition ($n$-tuple).** For $n \ge 1$, an **$n$-tuple** **$(a_1, a_2, \dots, a_n)$** is an ordered list of $n$ components. Two $n$-tuples are equal iff they > agree in *every* coordinate: > $$ (a_1,\dots,a_n) = (b_1,\dots,b_n) \iff a_i = b_i \text{ for all } i. $$ Ordered pairs are the case $n = 2$; a $3$-tuple $(x,y,z)$ locates a point in space. ### 11.2 The Cartesian product > **Definition (Cartesian product).** The **Cartesian product** of sets $A$ and > $B$ is the set of *all* ordered pairs with first component from $A$ and second > from $B$: > $$ A \times B = \{\, (a, b) \mid a \in A,\ b \in B \,\}. $$ > More generally, $A_1 \times A_2 \times \cdots \times A_n = \{\,(a_1,\dots,a_n) \mid a_i \in A_i\,\}$, and $A^{n}$ abbreviates > $A \times A \times \cdots \times A$ ($n$ factors). The name honors René Descartes, whose coordinate geometry identifies the plane with $\mathbb R \times \mathbb R = \mathbb{R}^{2}$ and space with $\mathbb R^{3}$. ![The Cartesian product A × B as a grid of ordered pairs, with |A × B| = |A|·|B|](img/l01_cartesian.png) **Example 1.40.** With $A = \{1, 2, 3, 4\}$ and $B = \{1, 2, 3, 4\}$, a typical element of $A \times B$ is $(1, 2)$, and $(1,2) \ne (2,1)$ even though both pairs live in $A \times B$. Here $|A \times B| = 16$ (Proposition 1.42). **Example 1.41 (product need not be square).** With $A = \{a,b\}$ and $B = \{1,2,3\}$, $$ A \times B = \{(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)\}, $$ so $|A \times B| = 2 \cdot 3 = 6$. Note $A \times B \ne B \times A$ in general (their elements are pairs in opposite orders), so the Cartesian product is **not commutative** — one of several algebraic facts developed in Lecture 2. ### 11.3 Counting the product > **Proposition 1.42.** For finite sets, $|A \times B| = |A| \cdot |B|$. > > *Proof.* Let $A = \{a_1,\dots,a_m\}$ with $|A| = m$ and $|B| = n$. Partition > $A \times B$ according to the first coordinate: > $$ A \times B = (\{a_1\}\times B) \,\cup\, (\{a_2\}\times B) \,\cup\, \cdots \,\cup\, (\{a_m\}\times B). $$ > These $m$ blocks are pairwise disjoint (pairs with different first coordinates are > different), and each block $\{a_i\}\times B = \{(a_i, b) \mid b \in B\}$ is in > bijection with $B$ via $(a_i,b) \mapsto b$, so each has exactly $n$ elements. By > the sum rule, $|A \times B| = \underbrace{n + n + \cdots + n}_{m} = m \cdot n = |A|\cdot|B|$. ∎ By induction this extends to $|A_1 \times \cdots \times A_n| = |A_1|\cdot|A_2|\cdots|A_n|$; in particular $|A^{n}| = |A|^{n}$. For instance $|\{0,1\}^{n}| = 2^{n}$, recovering the bit-string count used in Theorem 1.38. > **Remark (cross-reference).** The Cartesian product is the *stage* on which > relations and functions are defined: in Lecture 3, a **relation** from $A$ to $B$ > is *any subset* $R \subseteq A \times B$, and a **function** is a relation in > which each $a \in A$ appears as a first coordinate exactly once. Thus everything > in this section is prerequisite machinery for the two lectures that follow. ### 11.4 A first glimpse of applications The three constructions of this chapter map cleanly onto everyday computing objects: - a **subset** of a fixed finite universe ⟷ a **bit-set / bitmask** (§1.13.1); - a **tuple** ⟷ a **record / struct / row** (§1.13.2); - a **Cartesian product** ⟷ the **type of all such rows** (§1.13.2–13.3). §1.13 develops these. --- ## 1.12 Russell's paradox and a note on axioms ### 12.1 The paradox The naive rule we have used informally — "any property $P$ determines the set $\{x \mid P(x)\}$ of all objects with that property" — is called **unrestricted comprehension**. In 1901 Bertrand Russell noticed it is *self-contradictory*. Some sets are members of themselves and some are not — under naive comprehension, at least; e.g. "the set of all sets" would contain itself. Consider the property "$x$ is *not* a member of itself," and form the set it supposedly determines: $$ R = \{\, x \mid x \notin x \,\}. $$ Now ask the fatal question: **is $R \in R$?** - If $R \in R$, then $R$ satisfies the defining property, i.e. $R \notin R$. - If $R \notin R$, then $R$ satisfies the defining property, so $R \in R$. Either way we reach $R \in R \iff R \notin R$, an outright contradiction. So no such set $R$ can exist, and unrestricted comprehension is untenable. (The kinship with Cantor's diagonal set $D$ in Theorem 1.35 is exact: both hinge on an object asked whether it belongs to a set defined by *not* belonging.) > **A homelier version — the barber.** In a certain village the barber shaves > exactly those men who do not shave themselves. Does the barber shave himself? If > he does, he shouldn't; if he doesn't, he must. The "barber" cannot exist — just as > the set $R$ cannot. ### 12.2 The resolution The fix is to forbid conjuring sets out of properties alone. Modern set theory (the **Zermelo–Fraenkel** axioms, ZF/ZFC) replaces unrestricted comprehension with the **axiom schema of separation**: from an *already existing* set $U$ you may carve $$ \{\, x \in U \mid P(x) \,\}, $$ but you may **not** form $\{x \mid P(x)\}$ over the whole universe. Because the paradoxical $R$ needs to range over *all* objects, it is never constructed, and the contradiction disappears. There is also, provably, **no set of all sets** in ZFC — which is why §1.2 insisted the universal set $U$ is always a concrete set fixed by context, never "everything." This is exactly why, throughout this course, we write set-builder expressions with a domain: $\{x \in \mathbb Z \mid \dots\}$, $\{x \in U \mid \dots\}$. The habit is not pedantry — it is the discipline that keeps set theory consistent. > **Historical note.** Russell communicated the paradox to Gottlob Frege in 1902, > just as the second volume of Frege's *Grundgesetze der Arithmetik* — which sought > to found all of arithmetic on unrestricted comprehension — was in press. Frege's > stricken reply conceded the foundation had collapsed. The repair by Ernst Zermelo > (1908) and Abraham Fraenkel (1920s) produced the ZFC axioms on which essentially > all of contemporary mathematics is now built. --- ## 1.13 Applications in computer science Sets are not just notation; the constructions above are implemented directly in hardware, databases, and programming languages. ### 13.1 Bit-sets (bitmasks) Fix a universe of $n$ items indexed $0, 1, \dots, n-1$. By the characteristic-vector bijection of Theorem 1.38, every subset $S$ corresponds to a length-$n$ bit-string, which fits in a machine integer (an $n$-bit word). Set operations become single hardware instructions on that word: | Set concept | Bit operation | Cost | |-------------|---------------|------| | $i \in S$ | test bit $i$: `(w >> i) & 1` | $O(1)$ | | $A \cup B$ | bitwise OR `a \| b` | $O(1)$ per word | | $A \cap B$ | bitwise AND `a & b` | $O(1)$ per word | | $\overline{A}$ (complement in $U$) | bitwise NOT `~a` | $O(1)$ per word | | $A \setminus B$ | `a & ~b` | $O(1)$ per word | | $|A|$ (cardinality) | population count `popcount(a)` | $O(1)$ hardware | This is why a $64$-element universe is a natural unit: one subset per `uint64`. Bit-sets power register allocators, graph reachability, chess engines ("bitboards"), and the fast set operations behind search engines. Every identity we prove about $\cup, \cap, \overline{(\cdot)}$ in Lecture 2 is simultaneously a theorem about these bit operations (the shared abstraction is **Boolean algebra**). ### 13.2 Relational databases A database **table** with columns of types $T_1, T_2, \dots, T_n$ has rows that are $n$-tuples in the Cartesian product $T_1 \times T_2 \times \cdots \times T_n$. The table itself is a **finite subset** of that product — i.e. exactly a **relation** (Lecture 3): $$ \texttt{Students} \;\subseteq\; \texttt{Name} \times \texttt{ID} \times \texttt{Year}. $$ Because rows form a *set*, duplicate rows collapse (extensionality) and row order is irrelevant — matching SQL's `SELECT DISTINCT` and the fact that query results are unordered unless you add `ORDER BY`. The operations of *relational algebra* — union, intersection, difference, projection, selection, join — are set operations on these subsets of Cartesian products, so this lecture and Lecture 2 are the direct mathematical foundation of SQL. ### 13.3 Type systems and algebraic data types In a typed programming language a **type** can be understood as the *set of its values*, and the type constructors mirror set constructions — the reason they are called **algebraic data types**: | Type construct | Set analogue | Cardinality | |----------------|--------------|-------------| | product / struct / record / tuple `(A, B)` | $A \times B$ | $\lvert A\rvert \cdot \lvert B\rvert$ | | sum / variant / `enum` / tagged union `A + B` | disjoint union $A \sqcup B$ | $\lvert A\rvert + \lvert B\rvert$ | | function type `A -> B` | set of functions $B^{A}$ | $\lvert B\rvert^{\lvert A\rvert}$ | | unit type `()` | singleton $\{\ast\}$ | $1$ | | empty / `Void` type | $\varnothing$ | $0$ | For example, the type `Bool = {true, false}` has cardinality $2$; a pair `(Bool, Bool)` has $2\cdot 2 = 4$ values; and `Bool -> Bool` has $2^{2} = 4$ functions — precisely $|B|^{|A|}$. Counting a type's inhabitants (its cardinality) tells you, for instance, how many cases a `switch` must handle to be exhaustive, and the isomorphisms of this algebra (e.g. $A \times 1 \cong A$, $A + 0 \cong A$) justify refactorings compilers perform automatically. ### 13.4 Formal languages (preview) By Example 1.27 the set $\Sigma^{*}$ of strings over an alphabet is recursively defined, and a **language** is any subset $L \subseteq \Sigma^{*}$. Since $\Sigma^*$ is countably infinite, it has *uncountably* many subsets (Theorem 1.35), so there are uncountably many languages — but only countably many finite descriptions (programs/grammars). By a counting argument, **most languages have no finite description**: an early hint, grounded entirely in this chapter, that uncomputable and undecidable problems must exist. This thread is picked up in the lectures on regular languages, automata, and computability. --- ## Chapter summary Set theory supplies the vocabulary for the entire course. A **set** is an unordered collection of distinct elements, fully determined by its members (extensionality), so order and repetition inside braces are invisible. Membership $x \in A$ is the single primitive relation. Two sets among all others are singled out: the empty set $\varnothing$, which we proved is unique and is a subset of every set (by vacuous truth), and a context-dependent universe $U$ — never "everything," lest Russell's paradox strike. We compare sets with **inclusion** $\subseteq$, a partial order (reflexive, transitive, antisymmetric), and we prove two sets **equal** by the **double-inclusion method** — showing each contains the other — which is the template for every set identity to come. Sets are described three ways: by roster, by set-builder predicate (always over a stated domain, to stay safe), and by recursive definitions with a basis, a rule, and a closure clause — the last being how computer science defines strings, expressions, and data structures, and the natural partner of proof by (structural) induction. We **measure** sets by cardinality $|A|$, comparing sizes via bijections. This idea scales to the infinite, where Cantor's results overturn intuition: $\mathbb Z$ and $\mathbb Q$ are countable, but $\mathbb R$ is uncountable by the **diagonal argument**, and $|A| < |\mathcal{P}(A)|$ for every set. The **power set** $\mathcal{P}(A)$ of all subsets satisfies $|\mathcal{P}(A)| = 2^{n}$ when $|A| = n$, which we proved twice — bijectively (subsets $\leftrightarrow$ bit-strings) and by induction. Finally, **ordered pairs**, **tuples**, and the **Cartesian product** $A \times B$ (with $|A \times B| = |A|\,|B|$) restore the notion of order and set the stage for relations and functions. The same three constructions reappear as bit-sets, database tables, and program types. **Key facts.** - Extensionality: $A = B \iff (\forall x)(x \in A \iff x \in B)$; order and repetition are irrelevant. - $\varnothing$ is unique, $|\varnothing| = 0$, and $\varnothing \subseteq A$ for every $A$ (vacuous truth); but $\varnothing \ne \{\varnothing\}$ and $|\mathcal{P}(\varnothing)| = 1$. - Numeric hierarchy: $\mathbb N \subset \mathbb Z \subset \mathbb Q \subset \mathbb R \subset \mathbb C$, each inclusion proper; $\sqrt 2 \notin \mathbb Q$. - $A \subseteq B \iff (\forall x)(x \in A \Rightarrow x \in B)$; $\subseteq$ is reflexive, transitive, antisymmetric. - Equality by **double inclusion**: $A = B \iff (A \subseteq B \wedge B \subseteq A)$. - Descriptions: roster, set-builder $\{x \in U \mid P(x)\}$, recursive (basis + rule + closure). - $|\mathcal{P}(A)| = 2^{|A|}$; $\sum_{k=0}^{n}\binom nk = 2^{n}$. - Countable: $\mathbb N, \mathbb Z, \mathbb Q$. Uncountable: $\mathbb R$, $\mathcal{P}(\mathbb N)$. Always $|A| < |\mathcal{P}(A)|$ (Cantor). - $(a,b) = (c,d) \iff a=c \wedge b=d$; $|A \times B| = |A|\cdot|B|$; product is not commutative. - Never form $\{x \mid P(x)\}$ without a domain (Russell's paradox). --- ## Exercises ### Warm-up **1.** State the two principles (order, repetition) that make $\{2,1,2\}$, $\{1,2\}$, and $\{2,1\}$ all denote the same set. What single axiom underlies both? **2.** Explain the difference between $\varnothing$, $\{\varnothing\}$, and $\{0\}$. Give the cardinality of each. **3.** Place each of $-3,\ 0.75,\ \sqrt5,\ 4,\ 3-2i$ into the *smallest* customary numeric set ($\mathbb N, \mathbb Z, \mathbb Q, \mathbb R, \mathbb C$) that contains it. **4.** For $A = \{1, \{2\}, \{1,2\}\}$, decide each of: $1 \in A$; $2 \in A$; $\{2\} \in A$; $\{2\} \subseteq A$; $\{1,2\} \in A$; $\{1,2\} \subseteq A$; $\varnothing \subseteq A$. **5.** Is $\{1,2\}$ a proper subset of $\{1,2\}$? Is it a subset? Justify both answers. **6.** Compute $|\mathcal{P}(A)|$ for $A = \{a,b,c\}$ and list all $8$ of its elements grouped by size. **7.** Why is $(2,5) \ne (5,2)$ while $\{2,5\} = \{5,2\}$? How many elements does $A \times B$ have when $|A| = 3$ and $|B| = 4$? ### Standard **8.** Prove by double inclusion that $\{\, x \in \mathbb Z \mid x^2 = 4 \,\} = \{-2, 2\}$. **9.** Rewrite $\{3, 6, 9, 12, 15\}$ in set-builder notation, and give a recursive definition (basis + rule) of the set of *all* positive multiples of $3$. **10.** Let $A = \{n \in \mathbb Z \mid n = 4k+2 \text{ for some } k \in \mathbb Z\}$ and $B = \{n \in \mathbb Z \mid n \equiv 2 \pmod 4\}$. Prove $A = B$. **11.** Prove that for all sets, $A \subseteq B$ and $B \subseteq C$ imply $A \subseteq C$ (transitivity), taking arbitrary elements explicitly. **12.** List all elements of $\{a, b\} \times \{1, 2, 3\}$, and separately of $\{1,2,3\} \times \{a,b\}$. Are the two products equal? What does this show about commutativity of $\times$? **13.** Using the recursive definition of the Dyck language (Example 1.28), list all balanced-parenthesis strings of length $\le 4$, and state how many there are of length exactly $6$. **14.** A byte is a bit-string of length $8$. Using the characteristic-vector idea, explain why there are exactly $256$ subsets of an $8$-element universe, and describe which byte represents the subset $\{a_0, a_3, a_7\}$ of $\{a_0, \dots, a_7\}$. ### Challenge **15.** Prove that $\sqrt 3$ is irrational. Where exactly does the proof use that $3$ is prime (equivalently, not a perfect square)? **16.** Prove **carefully** that $\varnothing \subseteq A$ for every set $A$ *by contradiction*, writing out the negation of "$\varnothing \subseteq A$" explicitly before deriving the contradiction. **17.** Give the two proofs that $|\mathcal{P}(A)| = 2^{n}$ (bijection with bit-strings; and induction on $n$) in your own words. In the inductive step, identify precisely where the induction hypothesis is used. **18.** Prove that the set $\mathbb N \times \mathbb N$ is countable by describing an explicit listing (e.g. by anti-diagonals). Then explain in one or two sentences why the same *style* of argument fails to list the reals in $(0,1)$. **19.** (Cantor's theorem, hands-on.) Let $A = \{1,2,3\}$ and let $f : A \to \mathcal{P}(A)$ be $f(1) = \{2\},\ f(2) = \{1,2,3\},\ f(3) = \varnothing$. Compute the diagonal set $D = \{x \in A \mid x \notin f(x)\}$ and verify explicitly that $D \ne f(x)$ for every $x \in A$. **20.** Explain why the set $R = \{x \mid x \notin x\}$ cannot exist. Then explain in one sentence how the ZFC *separation* axiom ($\{x \in U \mid P(x)\}$, with $U$ a set) blocks the paradox. --- ## Selected answers & hints **2.** $|\varnothing| = 0$ (no elements); $|\{\varnothing\}| = 1$ (one element, namely $\varnothing$); $|\{0\}| = 1$ (one element, the number $0$). All three are *different* objects: an empty box, a box holding an empty box, and a box holding the number zero. **4.** True: $1 \in A$, $\{2\} \in A$, $\{1,2\} \in A$, $\varnothing \subseteq A$. False: $2 \in A$ (the object $2$ is not an element of $A$; it only appears *inside* elements), $\{2\} \subseteq A$ (this would need $2 \in A$, which is false), $\{1,2\} \subseteq A$ (needs $2 \in A$). Moral: distinguish $\in$ from $\subseteq$, and do not "see through" braces. **5.** $\{1,2\} \subseteq \{1,2\}$ is **true** (reflexivity, Prop. 4.2: every element of the left is in the right). It is **not** a *proper* subset, because properness requires the two sets to differ, and here they are equal. **6.** $|\mathcal{P}(A)| = 2^3 = 8$: $\varnothing$; $\{a\},\{b\},\{c\}$; $\{a,b\},\{a,c\},\{b,c\}$; $\{a,b,c\}$ — grouped $1 + 3 + 3 + 1 = 8$. **8.** ($\subseteq$) If $x \in \mathbb Z$ and $x^2 = 4$ then $(x-2)(x+2)=0$, so $x = 2$ or $x = -2$; either way $x \in \{-2,2\}$. ($\supseteq$) $2^2 = 4$ and $(-2)^2 = 4$ with $2, -2 \in \mathbb Z$, so both belong to the left set. Hence equality by double inclusion. **9.** $\{3, 6, 9, 12, 15\} = \{\,3k \mid k \in \mathbb N,\ k \le 5\,\}$. Recursive definition of all positive multiples of $3$: *basis* $3 \in S$; *rule* if $n \in S$ then $n + 3 \in S$; (closure). **12.** $\{a,b\}\times\{1,2,3\} = \{(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)\}$; $\{1,2,3\}\times\{a,b\} = \{(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)\}$. Both have $6$ elements, but the products are **not equal** (e.g. $(a,1)$ is in the first, not the second), so $\times$ is not commutative. **13.** Length $0$: $\varepsilon$. Length $2$: `()`. Length $4$: `(())`, `()()` — two of them. (Odd lengths are impossible.) The count of balanced strings of length $2n$ is the Catalan number $C_n$; for length $6$ ($n=3$), $C_3 = 5$. **14.** Each of the $8$ elements is independently in or out, giving $2^8 = 256$ characteristic vectors, hence $256$ subsets. With bit $i$ meaning "$a_i \in S$," the subset $\{a_0, a_3, a_7\}$ is the byte $10001001$ (bit $7$ leftmost) — equivalently value $2^0 + 2^3 + 2^7 = 137$. **15.** Mimic Theorem 1.7: assume $\sqrt3 = p/q$ in lowest terms, get $p^2 = 3q^2$, so $3 \mid p^2$. Primality of $3$ gives $3 \mid p$ (a prime dividing a product divides a factor — Euclid's lemma; this is the step that *needs* $3$ prime). Write $p = 3k$, deduce $3 \mid q$, contradicting lowest terms. (For a non-square like $3$, $6$, $\dots$ the argument works; for a perfect square like $4$ it correctly *fails*, since $\sqrt4 = 2$ is rational.) **16.** Negation of $\varnothing \subseteq A$: "$\exists x\,(x \in \varnothing \wedge x \notin A)$." Such an $x$ satisfies $x \in \varnothing$, impossible. The existence assumption is therefore false, so $\varnothing \subseteq A$. **18.** List $\mathbb N \times \mathbb N$ by anti-diagonals: $(1,1);\ (1,2),(2,1);\ (1,3),(2,2),(3,1);\ \dots$, i.e. group pairs by the constant sum $i + j$; each group is finite, so concatenating them enumerates all pairs — a bijection with $\mathbb N$. It fails for $(0,1)$ because a real is an *infinite* sequence of digits, not a finite pair of indices; the diagonal argument (Thm 9.3) shows any purported list is incomplete. **19.** $1 \notin f(1) = \{2\}$, so $1 \in D$; $2 \in f(2) = \{1,2,3\}$, so $2 \notin D$; $3 \notin f(3) = \varnothing$, so $3 \in D$. Thus $D = \{1,3\}$. Checking: $f(1) = \{2\}$, $f(2) = \{1,2,3\}$, $f(3) = \varnothing$ — none equals $\{1,3\}$, so $D$ is outside the image of $f$, confirming $f$ is not surjective. **20.** If $R$ existed, then $R \in R \iff R \notin R$ (substitute $R$ into the defining property), a contradiction; so $R$ cannot exist. Separation only lets you form $\{x \in U \mid x \notin x\}$ for an already-existing set $U$; the result is a subset of $U$ and one shows it simply *is not an element of $U$*, producing no contradiction — the self-swallowing "set of all sets" is never available. --- ## Further reading - Kenneth H. Rosen, *Discrete Mathematics and Its Applications* — Chapter 2 (Basic Structures: Sets, Functions, Sequences, Sums, and Matrices) covers sets, the power set, and Cartesian products, and §1.2.5 treats cardinality and Cantor's diagonal argument. - Susanna S. Epp, *Discrete Mathematics with Applications* — Chapter 6 (Set Theory) develops the element method for proving subset and equality relations in careful detail, closely matching the double-inclusion technique of §1.5. - For the axiomatic and historical background (extensionality, separation, Russell's paradox, ZFC), Paul Halmos's *Naive Set Theory* is a classic short treatment. These texts use $\mathbb N = \{0,1,2,\dots\}$ in places; recall (§1.3) that our course convention is $\mathbb N = \{1,2,3,\dots\}$.