Contents / Discrete Mathematics / Sets and Functions

Chapter 2

Sets and Functions

Set operations and the double-inclusion method used throughout; distributive and De Morgan laws by element chasing; inclusion-exclusion for two and three sets; functions, images and preimages; injectivity and surjectivity characterised by left and right inverses; bijections and composition; power sets with the count 2 to the n; and Cantor's theorem proved by the diagonal set.

Introduction

Mathematics needs a single language in which every other object can be described, and since the end of the nineteenth century that language has been sets. A number, a list, a graph, a program's state space, a relation, a function — each of them can be presented as a set, or as a set equipped with a little extra structure. That is not a philosophical flourish; it is a practical economy. Prove something about sets once and it holds everywhere, because everything else is built on top.

Two ideas carry this chapter. The first is that a set is determined by its members and by nothing else — not by how it was described, not by the order in which you list them, not by how many times you mention an element. The second is that a function is the right notion of "comparison" between sets, and that three properties of functions — injectivity, surjectivity, and their conjunction, bijectivity — turn into three ways of comparing sizes: at most as big, at least as big, exactly as big. Once sizes are compared by functions rather than by counting, the comparison keeps working for infinite sets, and the last theorem in this chapter is the startling thing that happens when it does.

The technique to master here is not a formula but a habit: to prove two sets equal, prove each is a subset of the other. We prove that this is legitimate at the start of the chapter and then use it constantly — for the distributive laws, for De Morgan's laws, for every identity of set algebra. Take an arbitrary element of the left side, walk it across to the right side, then walk an arbitrary element back. The argument is always the same shape, and a reader who has internalised that shape has learned most of what set algebra has to teach.

We also count. Counting subsets, functions, injections, surjections and bijections is where discrete mathematics starts to earn its keep, and inclusion–exclusion — the correction term $- ∣ A \cap B ∣$ that stops double counting — is the first genuinely useful counting theorem most people meet. The chapter ends with Cantor's theorem: for every set $A$ , no function $A \to P (A)$ can be onto. Its proof is four lines long, uses nothing but the material of this chapter, and shows that there is no largest set and no single "infinity".

A word on scope. Sets are also the subject of a foundational theory with axioms, ordinals, cardinal arithmetic and independence results; that belongs to the separate subject Set Theory and is not developed here. In this chapter a set is a collection of things, and the only care we take with "collection" is to note, in one remark, where naive use of the word goes wrong.

2.1Sets, membership, and the double-inclusion method

A set is specified by saying what belongs to it. Everything else in this section follows from taking that sentence literally.

Definition 2.1 (Set and membership). A set is a collection of distinct objects, called its elements or members. We write $a \in S$ for " $a$ is an element of $S$ " and $a \in / S$ for its negation. A finite set may be given by roster notation, listing its elements between braces, as in $S = {2, 3, 5, 7}$ .

Because a set is fixed by its membership, the roster carries no information beyond which objects appear in it. Order is not part of the data, and repetition adds nothing:

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

Both sides have exactly the elements $1$ , $2$ and $3$ , so they are the same set. If you need order, use a sequence or a tuple; if you need repetition, use a multiset. A set is the structure that has thrown both away, and that is precisely what makes it the simplest one.

Definition 2.2 (Set-builder notation). For a property $P$ , we write

{x \in U : P (x)}

for the set of those elements of an already-given set $U$ that satisfy $P$ . Read the colon as "such that". For example ${n \in Z : n = 2 k for some k \in Z}$ is the set of even integers.

Notation. Throughout, $N = {0, 1, 2, \dots}$ , $Z$ is the integers, $Q$ the rationals and $R$ the reals. For a positive integer $n$ we write

[n] = {1, 2, \dots, n},

the standard $n$ -element set. Almost every counting argument below is phrased with $[n]$ in the background.

Remark. Set-builder notation as written above carves a subset out of a set $U$ that is already in hand, and that restriction is not decoration. Allowing ${x : P (x)}$ for an arbitrary property, with no ambient set, produces Russell's paradox: let $R = {x : x \in / x}$ and ask whether $R \in R$ ; either answer contradicts the other. Repairing this is the business of Set Theory and its axioms. For this chapter, the discipline of always drawing elements from a stated set is enough to keep us out of trouble.

Definition 2.3 (Empty set). The empty set, written $\emptyset$ , is the set with no elements: $x \in / \emptyset$ for every $x$ .

Definition 2.4 (Subset and proper subset). A set $A$ is a subset of a set $B$ , written $A \subseteq B$ , if every element of $A$ is an element of $B$ ; that is, if the implication

x \in A ⟹ x \in B

holds for all $x$ . If $A \subseteq B$ and $A \neq = B$ , then $A$ is a proper subset, written $A ⊊ B$ .

Pitfall. $\in$ and $\subseteq$ are different relations between different kinds of thing. For $A = {1, 2}$ we have $1 \in A$ and ${1} \subseteq A$ , but $1 \subseteq A$ is a type error and ${1} \in A$ is false. An element of $A$ is a member; a subset of $A$ is a set of members. The distinction matters most in the section on power sets, where the elements of $P (A)$ are exactly the subsets of $A$ .

Set equality is now definable, and the definition is the engine of the whole chapter.

Definition 2.5 (Equality of sets). Two sets are equal, $A = B$ , if they have exactly the same elements: for every $x$ , $x \in A$ if and only if $x \in B$ . This principle is called extensionality.

Proposition 2.6 (Set equality by double inclusion). For all sets $A$ and $B$ ,

A = B if and only if A \subseteq B and B \subseteq A .

Proof. Suppose $A = B$ . Let $x \in A$ . By extensionality $x \in A$ if and only if $x \in B$ , so $x \in B$ . As $x$ was arbitrary, $A \subseteq B$ ; the same argument with the roles exchanged gives $B \subseteq A$ .

Conversely suppose $A \subseteq B$ and $B \subseteq A$ , and let $x$ be arbitrary. If $x \in A$ then $x \in B$ , because $A \subseteq B$ . If $x \in B$ then $x \in A$ , because $B \subseteq A$ . So $x \in A$ if and only if $x \in B$ , and extensionality gives $A = B$ .∎

This innocuous-looking proposition is a method, and it is the method this chapter uses more than any other. To prove an identity between two set expressions:

Take an arbitrary $x$ in the left-hand set. Unfold the definitions until you have a logical statement about $x$ .
Reason with that statement — using the ordinary rules for "and", "or" and "not" — until you reach the statement defining the right-hand set. Conclude $x$ lies in the right-hand set, hence $LHS \subseteq RHS$ .
Repeat starting from an arbitrary $x$ in the right-hand set.

Step 3 is not optional in general, though it is often unnecessary in practice: when every step in part 2 is an if and only if rather than a one-way implication, the same chain read backwards is the reverse inclusion, and it is honest to say so instead of writing it out. We will do exactly that once the reader has seen the long form several times.

Proposition 2.7 (The empty set is a subset of every set). For every set $A$ , $\emptyset \subseteq A$ .

Proof. We must show that $x \in \emptyset ⟹ x \in A$ holds for every $x$ . Fix an $x$ . By the definition of $\emptyset$ the hypothesis $x \in \emptyset$ is false, and an implication with a false hypothesis is true. Hence the implication holds for every $x$ , which is the definition of $\emptyset \subseteq A$ .∎

Intuition. The argument feels like a trick the first time, so it is worth naming the reason it is not. To refute $\emptyset \subseteq A$ you would have to exhibit an element of $\emptyset$ that is missing from $A$ . There are no elements of $\emptyset$ at all, so no such counterexample can be produced, and a claim with no possible counterexample is true. A statement true this way is called vacuously true. Nothing has been smuggled in: "all my unicorns are purple" is true for the same reason, and would become informative only if I owned a unicorn.

Proposition 2.8 (Uniqueness of the empty set). There is exactly one set with no elements.

Proof. Suppose $E$ and $E^{'}$ both have no elements. By the proposition The empty set is a subset of every set, applied with $E$ in the role of the empty set, $E \subseteq E^{'}$ ; applied with $E^{'}$ in that role, $E^{'} \subseteq E$ . By Set equality by double inclusion, $E = E^{'}$ .∎

Proposition 2.9 (Inclusion is reflexive and transitive). For all sets $A$ , $B$ , $C$ : $A \subseteq A$ ; and if $A \subseteq B$ and $B \subseteq C$ then $A \subseteq C$ .

Proof. Reflexivity is the implication $x \in A ⟹ x \in A$ , which holds for every $x$ .

For transitivity, let $x \in A$ . Since $A \subseteq B$ we get $x \in B$ , and since $B \subseteq C$ we get $x \in C$ . As $x$ was arbitrary, $A \subseteq C$ .∎

Together with antisymmetry — which is exactly Set equality by double inclusion — this says $\subseteq$ is a partial order, a notion taken up in the chapter on relations. It is only partial: two sets may be incomparable, as ${1, 2}$ and ${2, 3}$ are, neither containing the other.

Example 2.10 (Deciding inclusions). Let $A = {1, 2}$ , $B = {1, 2, 3}$ and $C = {{1}, 1, 2}$ . Decide each of $A \subseteq B$ , $A \in C$ , ${1} \in C$ , ${1} \subseteq C$ , $\emptyset \subseteq C$ , $\emptyset \in C$ .

Solution.

$A \subseteq B$ : true — both $1$ and $2$ lie in $B$ .
$A \in C$ : false. The elements of $C$ are ${1}$ , $1$ and $2$ ; the set ${1, 2}$ is not among them.
${1} \in C$ : true. The set ${1}$ is listed as an element of $C$ .
${1} \subseteq C$ : true, but for a different reason — its only element $1$ belongs to $C$ . Note that items 3 and 4 are both true here by coincidence of this example, not in general.
$\emptyset \subseteq C$ : true, by The empty set is a subset of every set.
$\emptyset \in C$ : false. No element of $C$ is the empty set.

□

Example 2.11 (A first double-inclusion proof). Let $A = {n \in Z : n = 6 k for some k \in Z}$ and $B = {n \in Z : n is even and 3 ∣ n}$ . Prove $A = B$ .

Solution.

( $A \subseteq B$ .) Let $n \in A$ , so $n = 6 k$ for some integer $k$ . Then $n = 2 (3 k)$ is even and $n = 3 (2 k)$ is a multiple of $3$ , so $n \in B$ .
( $B \subseteq A$ .) Let $n \in B$ . Being even, $n = 2 m$ for some integer $m$ . Since $3 ∣ n$ and $3 ∤ 2$ , and $3$ is prime, $3 ∣ m$ — this is Euclid's lemma from number theory. Write $m = 3 j$ ; then $n = 6 j$ , so $n \in A$ .
Both inclusions hold, so by Set equality by double inclusion, $A = B$ .

□

Pitfall. The second inclusion above needed a real idea, while the first was routine. That asymmetry is typical, and it is the reason you must actually write both halves rather than assert "similarly". "Even and divisible by $3$ " implying "divisible by $6$ " is false for the analogous claim with $4$ and $6$ : $12$ is a multiple of $4$ and of $6$ , but ${n : 4 ∣ n and 6 ∣ n}$ is the multiples of $12$ , not of $24$ .

Exercises for §2.1 →

2.2Operations on sets and the algebra they obey

Set operations are defined by the logical connectives: union is "or", intersection is "and", complement is "not". Every identity in this section is therefore a fact of propositional logic in disguise, and element chasing is the translation.

Definition 2.12 (Union, intersection, difference, complement). Let $A$ and $B$ be subsets of a universal set $U$ fixed by context. Then

A \cup B = {x \in U : x \in A or x \in B}, A \cap B = {x \in U : x \in A and x \in B},

A ∖ B = {x \in U : x \in A and x \in / B}, A^{c} = U ∖ A .

The "or" in the union is inclusive: $x$ may lie in both. Sets with $A \cap B = \emptyset$ are called disjoint.

Definition 2.13 (Symmetric difference). The symmetric difference of $A$ and $B$ is

A △ B = (A ∖ B) \cup (B ∖ A),

the elements lying in exactly one of the two sets.

Definition 2.14 (Cartesian product). The Cartesian product of $A$ and $B$ is the set of ordered pairs

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

where $(a, b) = (a^{'}, b^{'})$ means $a = a^{'}$ and $b = b^{'}$ . Write $A^{2}$ for $A \times A$ , and more generally $A^{n}$ for the set of $n$ -tuples from $A$ .

Unlike union and intersection, the Cartesian product is neither commutative nor associative in the strict sense: $(1, 2) \neq = (2, 1)$ , so $A \times B \neq = B \times A$ unless $A = B$ or one of them is empty. The product is where order re-enters a theory built on unordered collections, and it is what makes relations and functions expressible in the language of sets at all.

Figure 2.15. The three-circle Venn diagram. Three sets cut the universe into eight regions, one for each of the eight answers to "in

A

? in

B

? in

C

? " — and the eighth is the region outside all three.

The picture is a proof aid, not a proof. It is reliable for two or three sets — three circles in general position really do produce all eight combinations — and unreliable beyond that, since four circles cannot cut the plane into the sixteen regions four sets require. Element chasing has no such limit, which is why the arguments below are written in symbols even where a diagram would convince you.

Theorem 2.16 (Distributive laws). For all sets $A$ , $B$ , $C$ ,

A \cap (B \cup C) = (A \cap B) \cup (A \cap C), A \cup (B \cap C) = (A \cup B) \cap (A \cup C) .

Proof. We prove the first law by double inclusion.

( $\subseteq$ .) Let $x \in A \cap (B \cup C)$ . Then $x \in A$ , and $x \in B \cup C$ , so $x \in B$ or $x \in C$ . In the first case $x \in A$ and $x \in B$ , so $x \in A \cap B$ . In the second case $x \in A$ and $x \in C$ , so $x \in A \cap C$ . Either way $x \in (A \cap B) \cup (A \cap C)$ .

( $\supseteq$ .) Let $x \in (A \cap B) \cup (A \cap C)$ . Then $x \in A \cap B$ or $x \in A \cap C$ . In the first case $x \in A$ and $x \in B$ ; in the second $x \in A$ and $x \in C$ . In both cases $x \in A$ , and in both cases $x$ lies in $B$ or in $C$ , hence in $B \cup C$ . Therefore $x \in A \cap (B \cup C)$ .

Both inclusions hold, so the sets are equal by Set equality by double inclusion.

The second law is the same argument with "and" and "or" exchanged throughout: $x \in A \cup (B \cap C)$ says $x \in A$ , or else $x$ lies in both $B$ and $C$ ; and $x \in (A \cup B) \cap (A \cup C)$ says $x$ lies in $A$ or $B$ , and in $A$ or $C$ . If $x \in A$ both hold. If $x \in / A$ , the first says $x \in B$ and $x \in C$ , and the second says exactly the same, so the two statements agree in every case.∎

Intuition. The two laws are the set-theoretic reading of the two distributive laws of logic. Arithmetic has only one such law — multiplication distributes over addition, but addition does not distribute over multiplication — so the symmetry here is genuinely new. Do not import the arithmetic instinct that one operation is "stronger"; with $\cap$ and $\cup$ neither is.

Theorem 2.17 (De Morgan's laws for sets). For all subsets $A$ , $B$ of a universal set $U$ ,

(A \cup B)^{c} = A^{c} \cap B^{c}, (A \cap B)^{c} = A^{c} \cup B^{c} .

Proof. Take the first. For $x \in U$ , the following statements are equivalent, each line following from the previous by the definition named beside it:

$x \in (A \cup B)^{c}$ ; $x \in / A \cup B$ (definition of complement); it is not the case that ( $x \in A$ or $x \in B$ ) (definition of union); $x \in / A$ and $x \in / B$ (De Morgan's law of logic); $x \in A^{c}$ and $x \in B^{c}$ ; $x \in A^{c} \cap B^{c}$ .

Every step is an equivalence, so reading the chain downwards gives $(A \cup B)^{c} \subseteq A^{c} \cap B^{c}$ and reading it upwards gives the reverse inclusion. By Set equality by double inclusion the two sets are equal.

For the second law, apply the first to the sets $A^{c}$ and $B^{c}$ : it gives $(A^{c} \cup B^{c})^{c} = A^{cc} \cap B^{cc} = A \cap B$ , using $A^{cc} = A$ . Taking complements of both sides yields $A^{c} \cup B^{c} = (A \cap B)^{c}$ .∎

Remark. The pattern to remember is: a complement turns a union into an intersection and an intersection into a union. It reappears verbatim for logical connectives ( $\neg (p \lor q) \equiv \neg p \land \neg q$ ), for quantifiers ( $\neg\forall x P \equiv \exists x \neg P$ ), and in Boolean circuit design, where it is the rule that lets any circuit be rebuilt from NAND gates alone.

Proposition 2.18 (Difference as intersection with a complement). For all subsets $A$ , $B$ of $U$ : $A ∖ B = A \cap B^{c}$ .

Proof. For $x \in U$ , $x \in A ∖ B$ means $x \in A$ and $x \in / B$ , which is exactly $x \in A$ and $x \in B^{c}$ , which is $x \in A \cap B^{c}$ . Each step is an equivalence, so both inclusions hold at once.∎

That proposition is a labour-saving device: it removes $∖$ from any expression, leaving only $\cup$ , $\cap$ and $^{c}$ , on which the distributive and De Morgan laws can be used directly. The next example shows the technique.

Example 2.19 (Simplifying a set expression). Simplify $(A ∖ B) \cup (A \cap B)$ .

Solution.

By Difference as intersection with a complement, $(A ∖ B) \cup (A \cap B) = (A \cap B^{c}) \cup (A \cap B)$ .
By the Distributive laws read right to left, this is $A \cap (B^{c} \cup B)$ .
$B^{c} \cup B = U$ , since every $x \in U$ either lies in $B$ or does not.
$A \cap U = A$ , because $A \subseteq U$ . Final answer: $A$ .

□

Example 2.20 (Proving an identity by element chasing). Prove $A ∖ (B \cup C) = (A ∖ B) \cap (A ∖ C)$ .

Solution.

Let $x \in A ∖ (B \cup C)$ . Then $x \in A$ and $x \in / B \cup C$ .
By De Morgan's laws for sets (or directly), $x \in / B \cup C$ means $x \in / B$ and $x \in / C$ .
So $x \in A$ and $x \in / B$ , giving $x \in A ∖ B$ ; and $x \in A$ and $x \in / C$ , giving $x \in A ∖ C$ . Hence $x$ lies in the intersection.
Conversely, if $x \in (A ∖ B) \cap (A ∖ C)$ then $x \in A$ , $x \in / B$ and $x \in / C$ , so $x \in A$ and $x \in / B \cup C$ , that is $x \in A ∖ (B \cup C)$ .
Both inclusions hold, so the sets are equal.

□

Proposition 2.21 (Three readings of inclusion). For all sets $A$ and $B$ the following are equivalent:

$A \subseteq B$ ;
$A \cup B = B$ ;
$A \cap B = A$ .

Proof. (1 $\Rightarrow$ 2.) Certainly $B \subseteq A \cup B$ . For the other inclusion, let $x \in A \cup B$ ; then $x \in A$ , in which case $x \in B$ by hypothesis, or $x \in B$ already. So $A \cup B \subseteq B$ , and the two are equal.

(2 $\Rightarrow$ 3.) Assume $A \cup B = B$ . Then $A \cap B = A \cap (A \cup B)$ , and every $x \in A$ lies in $A \cup B$ , so $A \cap (A \cup B) = A$ .

(3 $\Rightarrow$ 1.) Assume $A \cap B = A$ and let $x \in A$ . Then $x \in A \cap B$ , so in particular $x \in B$ . Hence $A \subseteq B$ .

The three implications close a cycle, so the three statements are equivalent.∎

Now to counting. If $A$ is finite we write $∣ A ∣$ for the number of its elements, its cardinality. The union of two sets is the first place where naive counting goes wrong, and the fix is the most reused idea in combinatorics.

Theorem 2.22 (Inclusion–exclusion for two sets). For finite sets $A$ and $B$ ,

∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣.

Proof. Split $A \cup B$ into the three pairwise disjoint pieces $A ∖ B$ , $A \cap B$ and $B ∖ A$ ; every element of $A \cup B$ lies in exactly one of them, according to whether it lies in $A$ only, in both, or in $B$ only. Counting a disjoint union adds the counts, so

∣ A \cup B ∣ = ∣ A ∖ B ∣ + ∣ A \cap B ∣ + ∣ B ∖ A ∣.

Similarly $A$ is the disjoint union of $A ∖ B$ and $A \cap B$ , so $∣ A ∖ B ∣ = ∣ A ∣ - ∣ A \cap B ∣$ , and likewise $∣ B ∖ A ∣ = ∣ B ∣ - ∣ A \cap B ∣$ . Substituting,

∣ A \cup B ∣ = (∣ A ∣ - ∣ A \cap B ∣) + ∣ A \cap B ∣ + (∣ B ∣ - ∣ A \cap B ∣) = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣.

∎

Intuition. Adding $∣ A ∣$ and $∣ B ∣$ counts everything in the overlap twice, once from each set. Subtracting $∣ A \cap B ∣$ removes exactly one of those two counts, leaving every element counted once. The whole of inclusion–exclusion, at every size, is this bookkeeping carried out systematically.

Theorem 2.23 (Inclusion–exclusion for three sets). For finite sets $A$ , $B$ , $C$ ,

∣ A \cup B \cup C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ - ∣ A \cap B ∣ - ∣ A \cap C ∣ - ∣ B \cap C ∣ + ∣ A \cap B \cap C ∣.

Proof. Apply Inclusion–exclusion for two sets to the pair $A \cup B$ and $C$ :

∣ A \cup B \cup C ∣ = ∣ A \cup B ∣ + ∣ C ∣ - ∣ (A \cup B) \cap C ∣.

Expand $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣$ by the same theorem. For the last term, the Distributive laws give $(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$ , and a third application of the two-set formula gives

∣ (A \cap C) \cup (B \cap C) ∣ = ∣ A \cap C ∣ + ∣ B \cap C ∣ - ∣ (A \cap C) \cap (B \cap C) ∣.

Finally $(A \cap C) \cap (B \cap C) = A \cap B \cap C$ , since intersection is idempotent and commutative. Substituting the three expansions and collecting signs gives the stated formula.∎

Intuition. Count each element by which of $A$ , $B$ , $C$ it belongs to. An element in exactly one set is counted once, by one positive term, and by nothing else. An element in exactly two, say $A$ and $B$ , is counted $+ 1 + 1 - 1 = 1$ time. An element in all three is counted $+ 3 - 3 + 1 = 1$ time. Every element is counted exactly once, which is what the theorem asserts.

Example 2.24 (A survey count). Of $120$ students, $65$ study Python, $52$ study C, $43$ study Haskell; $28$ study both Python and C, $21$ Python and Haskell, $18$ C and Haskell, and $10$ study all three. How many study at least one of the languages, and how many study none?

Solution.

By Inclusion–exclusion for three sets, the number studying at least one is $65 + 52 + 43 - 28 - 21 - 18 + 10$ .
The positive terms give $160$ ; the pairwise terms subtract $67$ ; adding back $10$ gives $160 - 67 + 10 = 103$ .
Those studying none are the complement inside the $120$ students: $120 - 103 = 17$ . Final answer: $103$ study at least one, $17$ study none.

□

Example 2.25 (Recovering an unknown intersection). Two finite sets satisfy $∣ A ∣ = 31$ , $∣ B ∣ = 24$ and $∣ A \cup B ∣ = 40$ . Find $∣ A \cap B ∣$ and $∣ A △ B ∣$ .

Solution.

Rearranging Inclusion–exclusion for two sets, $∣ A \cap B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cup B ∣ = 31 + 24 - 40 = 15$ .
The symmetric difference is everything in the union but not the intersection, so $∣ A △ B ∣ = ∣ A \cup B ∣ - ∣ A \cap B ∣ = 40 - 15 = 25$ . Final answer: $15$ and $25$ .

□

Proposition 2.26 (Cardinality of a Cartesian product). For finite sets $A$ and $B$ , $∣ A \times B ∣ = ∣ A ∣ ∣ B ∣$ .

Proof. Write $A = {a_{1}, \dots, a_{m}}$ with $m = ∣ A ∣$ . Every pair in $A \times B$ has exactly one first coordinate, so $A \times B$ is the disjoint union of the $m$ sets $S_{i} = {(a_{i}, b) : b \in B}$ . For each $i$ the assignment $b \mapsto (a_{i}, b)$ matches the elements of $B$ with those of $S_{i}$ one for one, so $∣ S_{i} ∣ = ∣ B ∣$ . Summing over the disjoint pieces, $∣ A \times B ∣ = m ∣ B ∣ = ∣ A ∣∣ B ∣$ .∎

Corollary 2.27 (Tuples from one set). For a finite set $A$ and $n \geq 1$ , $∣ A^{n} ∣ = ∣ A ∣^{n}$ .

Proof. Induct on $n$ . For $n = 1$ the claim is $∣ A ∣ = ∣ A ∣$ . If $∣ A^{n} ∣ = ∣ A ∣^{n}$ , then identifying $A^{n + 1}$ with $A^{n} \times A$ and applying Cardinality of a Cartesian product gives $∣ A^{n + 1} ∣ = ∣ A ∣^{n} \cdot ∣ A ∣ = ∣ A ∣^{n + 1}$ .∎

Example 2.28 (Counting strings). How many binary strings of length $8$ are there, and how many of them start with $1$ and end with $0$ ?

Solution.

A binary string of length $8$ is an element of ${0, 1}^{8}$ , so by Tuples from one set there are $2^{8} = 256$ .
Fixing the first and last symbols leaves the six middle positions free, giving $2^{6} = 64$ . Final answer: $256$ and $64$ .

□

Exercises for §2.2 →

2.3Functions: the definition that removes the ambiguity

Informally a function is a rule. That description is too loose to prove anything with — two different rules can compute the same function, and some "rules" fail to define a function at all — so the working definition names the data instead: a domain, a codomain, and an assignment that is total and single-valued.

Definition 2.29 (Function). A function $f$ from a set $A$ to a set $B$ , written $f : A \to B$ , assigns to each element $a \in A$ exactly one element $f (a) \in B$ . The set $A$ is the domain, $B$ the codomain, and $f (a)$ the value or image of $a$ .

Formally, $f$ is a subset $Γ_{f} \subseteq A \times B$ — its graph — such that for every $a \in A$ there is exactly one $b \in B$ with $(a, b) \in Γ_{f}$ .

The two conditions packed into "exactly one" are worth separating. At least one makes $f$ total: no element of the domain may be left without a value, so $f (x) = 1/ x$ is not a function $R \to R$ , though it is one on $R ∖ {0}$ . At most one makes $f$ well defined: no element may receive two values, so the "rule" $\pm x$ does not define a function $[0, \infty) \to R$ .

Definition 2.30 (Image and preimage). For $f : A \to B$ , $S \subseteq A$ and $T \subseteq B$ , define

f (S) = {f (a) : a \in S} \subseteq B, f^{- 1} (T) = {a \in A : f (a) \in T} \subseteq A .

The set $f (A)$ is the image (or range) of $f$ . The notation $f^{- 1} (T)$ is the preimage of $T$ and is defined for every $f$ , whether or not $f$ has an inverse function.

Pitfall. Codomain and image are different sets, and a function carries its codomain as part of its data. The squaring maps $R \to R$ and $R \to [0, \infty)$ have the same rule and the same graph read as a set of pairs, but the second is surjective and the first is not. Any statement about surjectivity is a statement about the chosen codomain.

Definition 2.31 (Equality of functions). Two functions $f, g : A \to B$ are equal if $f (a) = g (a)$ for every $a \in A$ . Functions with different domains or different codomains are never equal.

Definition 2.32 (Composition and identity). For $f : A \to B$ and $g : B \to C$ , the composite $g \circ f : A \to C$ is defined by $(g \circ f) (a) = g (f (a))$ . The identity function $id_{A} : A \to A$ is given by $id_{A} (a) = a$ .

Proposition 2.33 (Composition is associative, with identities). For $f : A \to B$ , $g : B \to C$ and $h : C \to D$ ,

h \circ (g \circ f) = (h \circ g) \circ f, f \circ id_{A} = f = id_{B} \circ f .

Proof. All four composites in the first identity are functions $A \to D$ , so by Equality of functions it suffices to check them at an arbitrary $a \in A$ :

(h \circ (g \circ f)) (a) = h ((g \circ f) (a)) = h (g (f (a))) = (h \circ g) (f (a)) = ((h \circ g) \circ f) (a) .

For the second, $(f \circ id_{A}) (a) = f (id_{A} (a)) = f (a)$ and $(id_{B} \circ f) (a) = id_{B} (f (a)) = f (a)$ .∎

Associativity is what licenses writing $h \circ g \circ f$ with no brackets, and it is used silently in every inverse argument later. Note that composition is emphatically not commutative: with $f (x) = x + 1$ and $g (x) = x^{2}$ on $R$ , $(g \circ f) (x) = (x + 1)^{2}$ while $(f \circ g) (x) = x^{2} + 1$ .

Theorem 2.34 (Counting functions). Let $A$ and $B$ be finite with $∣ A ∣ = n$ and $∣ B ∣ = m$ . The number of functions $A \to B$ is $m^{n}$ .

Proof. List the domain as $A = {a_{1}, \dots, a_{n}}$ . A function $f : A \to B$ is determined by the tuple of its values $(f (a_{1}), \dots, f (a_{n})) \in B^{n}$ , since knowing every value is knowing $f$ by Equality of functions. Conversely every tuple $(b_{1}, \dots, b_{n}) \in B^{n}$ arises from exactly one function, namely the one sending $a_{i} \mapsto b_{i}$ — this assignment is total and single valued because each $a_{i}$ appears once in the list. So the functions $A \to B$ correspond one for one with the elements of $B^{n}$ , and by Tuples from one set there are $m^{n}$ of them.∎

Intuition. Choosing a function is filling in a table with one row per element of the domain. Each row is filled independently, from $m$ options, and there are $n$ rows: $m \cdot m \dots m = m^{n}$ . The notation $B^{A}$ for the set of functions $A \to B$ is chosen so that this count reads $∣ B^{A} ∣ = ∣ B ∣^{∣ A ∣}$ .

Example 2.35 (Counting assignments). How many ways can $5$ distinct jobs be assigned to $3$ machines, if every job goes to exactly one machine and machines may sit idle?

Solution.

An assignment is a function from the $5$ -element set of jobs to the $3$ -element set of machines.
By Counting functions there are $3^{5} = 243$ of them. Final answer: $243$ .

□

Proposition 2.36 (Images and unions, preimages and everything). Let $f : A \to B$ , let $S_{1}, S_{2} \subseteq A$ and $T_{1}, T_{2} \subseteq B$ . Then

f (S_{1} \cup S_{2}) = f (S_{1}) \cup f (S_{2}), f (S_{1} \cap S_{2}) \subseteq f (S_{1}) \cap f (S_{2}),

f^{- 1} (T_{1} \cup T_{2}) = f^{- 1} (T_{1}) \cup f^{- 1} (T_{2}), f^{- 1} (T_{1} \cap T_{2}) = f^{- 1} (T_{1}) \cap f^{- 1} (T_{2}) .

The inclusion for images can be strict.

Proof. For the first identity: $b \in f (S_{1} \cup S_{2})$ means $b = f (a)$ for some $a \in S_{1} \cup S_{2}$ , that is for some $a \in S_{1}$ or some $a \in S_{2}$ , which says $b \in f (S_{1})$ or $b \in f (S_{2})$ . Every step is an equivalence, so the sets are equal.

For the inclusion: if $b \in f (S_{1} \cap S_{2})$ then $b = f (a)$ with $a$ in both $S_{1}$ and $S_{2}$ , so $b \in f (S_{1})$ and $b \in f (S_{2})$ . The reverse fails because the element of $S_{1}$ witnessing $b \in f (S_{1})$ need not be the element of $S_{2}$ witnessing $b \in f (S_{2})$ . Concretely, take $f : {1, 2} \to {0}$ with $S_{1} = {1}$ and $S_{2} = {2}$ : then $S_{1} \cap S_{2} = \emptyset$ , so the left side is $\emptyset$ , while both images are ${0}$ and the right side is ${0}$ .

For the preimages: $a \in f^{- 1} (T_{1} \cup T_{2})$ means $f (a) \in T_{1} \cup T_{2}$ , that is $f (a) \in T_{1}$ or $f (a) \in T_{2}$ , that is $a \in f^{- 1} (T_{1})$ or $a \in f^{- 1} (T_{2})$ . Replacing "or" by "and" throughout proves the intersection case, and the argument works because $f (a)$ is a single element, so asking which sets it lies in commutes with the connectives.∎

Remark. This is the reason preimages are the better-behaved notion. Preimage respects unions, intersections and complements; image respects only unions. A great deal of later mathematics — continuity in topology, measurability in probability — is defined using $f^{- 1}$ rather than $f$ for exactly this reason.

Example 2.37 (Images and preimages of a concrete map). Let $f : Z \to Z$ be $f (n) = n^{2}$ . Compute $f ({- 2, - 1, 0, 1, 2})$ , $f^{- 1} ({4})$ , $f^{- 1} ({2})$ and $f^{- 1} ({0, 1, 4, 9})$ .

Solution.

$f ({- 2, - 1, 0, 1, 2}) = {4, 1, 0, 1, 4} = {0, 1, 4}$ , a set of size $3$ — images can shrink.
$f^{- 1} ({4}) = {- 2, 2}$ , since those are the integers squaring to $4$ .
$f^{- 1} ({2}) = \emptyset$ : no integer squares to $2$ . A preimage may be empty; that is not an error.
$f^{- 1} ({0, 1, 4, 9}) = {0, \pm 1, \pm 2, \pm 3}$ , which has $7$ elements.

□

Exercises for §2.3 →

2.4Injections and surjections

Two questions can be asked of a function $f : A \to B$ , and they are independent of each other. Does $f$ ever collide, sending two inputs to one output? Does $f$ reach everything in $B$ ? The answers name the two classes that organise the rest of the chapter.

Definition 2.38 (Injective, surjective, bijective). A function $f : A \to B$ is

injective (one-to-one) if $f (a_{1}) = f (a_{2})$ implies $a_{1} = a_{2}$ , for all $a_{1}, a_{2} \in A$ ;
surjective (onto) if for every $b \in B$ there exists $a \in A$ with $f (a) = b$ , that is $f (A) = B$ ;
bijective if it is both.

The contrapositive of injectivity is often the more usable form: $a_{1} \neq = a_{2} ⟹ f (a_{1}) \neq = f (a_{2})$ , "distinct inputs give distinct outputs". In practice one proves injectivity by assuming $f (a_{1}) = f (a_{2})$ and deducing $a_{1} = a_{2}$ algebraically; one proves surjectivity by taking an arbitrary $b \in B$ and constructing an $a$ that maps to it.

Figure 2.39. Three functions from a four-element to a three-element set and back. Left: injective, no two arrows land together, so the target must be at least as large. Middle: surjective, every target is hit. Right: bijective, a perfect pairing.

Example 2.40 (Deciding the two properties). For each function decide injectivity and surjectivity: (a) $f : Z \to Z$ , $f (n) = 2 n$ ; (b) $g : Z \to Z$ , $g (n) = n + 7$ ; (c) $h : R \to R$ , $h (x) = x^{2}$ ; (d) $k : Z \to N$ , $k (n) = ∣ n ∣$ .

Solution.

(a) Injective: $2 n_{1} = 2 n_{2}$ gives $n_{1} = n_{2}$ . Not surjective: no integer maps to $1$ , since $2 n = 1$ has no integer solution.
(b) Injective, as $n_{1} + 7 = n_{2} + 7$ forces $n_{1} = n_{2}$ ; and surjective, since $m = g (m - 7)$ for every $m \in Z$ . So $g$ is bijective.
(c) Not injective, since $h (- 1) = h (1) = 1$ . Not surjective, since $x^{2} \geq 0$ never equals $- 1$ .
(d) Not injective ( $k (- 3) = k (3)$ ), but surjective, since every $m \in N$ satisfies $m = k (m)$ .

□

The next two theorems recast the definitions in terms of inverses, and they are the reason these particular properties matter: injectivity means the function can be undone from the left, surjectivity means it can be undone from the right.

Definition 2.41 (Left and right inverses). Let $f : A \to B$ . A function $g : B \to A$ is a left inverse of $f$ if $g \circ f = id_{A}$ , and a right inverse if $f \circ g = id_{B}$ .

Theorem 2.42 (Injective iff a left inverse exists). Let $f : A \to B$ with $A \neq = \emptyset$ . Then $f$ is injective if and only if there is a function $g : B \to A$ with $g \circ f = id_{A}$ .

Proof. ( $\Leftarrow$ ) Suppose such a $g$ exists and $f (a_{1}) = f (a_{2})$ . Applying $g$ to both sides, $g (f (a_{1})) = g (f (a_{2}))$ , that is $a_{1} = a_{2}$ since $g \circ f = id_{A}$ . So $f$ is injective.

( $\Rightarrow$ ) Suppose $f$ is injective. Since $A$ is nonempty, fix some $a_{0} \in A$ . Define $g : B \to A$ by

g (b) = {the unique a \in A with f (a) = b, a_{0}, b \in f (A), b \in / f (A) .

The first clause is legitimate precisely because $f$ is injective: for $b \in f (A)$ at least one such $a$ exists by definition of the image, and at most one exists by injectivity, so the value is well defined. The second clause makes $g$ total. For any $a \in A$ we have $f (a) \in f (A)$ , and the unique preimage of $f (a)$ is $a$ itself, so $g (f (a)) = a$ . Hence $g \circ f = id_{A}$ .∎

Remark. The hypothesis $A \neq = \emptyset$ is needed only to have somewhere to send the unreached elements of $B$ . The empty function $\emptyset \to B$ is injective but admits no left inverse when $B \neq = \emptyset$ , since there is no function $B \to \emptyset$ at all.

Theorem 2.43 (Surjective iff a right inverse exists). Let $f : A \to B$ . Then $f$ is surjective if and only if there is a function $g : B \to A$ with $f \circ g = id_{B}$ .

Proof. ( $\Leftarrow$ ) Suppose $f \circ g = id_{B}$ and let $b \in B$ . Then $f (g (b)) = b$ , so $b$ is in the image of $f$ . As $b$ was arbitrary, $f$ is surjective.

( $\Rightarrow$ ) Suppose $f$ is surjective. For each $b \in B$ the set $f^{- 1} ({b})$ is nonempty. Choose one element from each of these sets and call it $g (b)$ ; this defines a function $g : B \to A$ , and $f (g (b)) = b$ holds for every $b$ by construction, so $f \circ g = id_{B}$ .∎

Remark. The phrase "choose one element from each" in the last proof is the axiom of choice when $B$ is infinite: making infinitely many independent choices at once is not something the other axioms provide. For finite $B$ no axiom is needed — repeated use of "the set is nonempty, so pick an element" suffices. We use choice silently from here on, as every introductory treatment does; what it costs and what it buys is the business of Set Theory.

Example 2.44 (Building the two one-sided inverses). Let $f : Z \to Z$ be $f (n) = 2 n$ and let $q : Z \to Z$ be $q (n) = ⌊ n /2 ⌋$ . Verify that $q$ is a left inverse of $f$ , and show $f$ has no right inverse.

Solution.

$q (f (n)) = ⌊ 2 n /2 ⌋ = n$ for every integer $n$ , so $q \circ f = id_{Z}$ and $q$ is a left inverse — consistent with $f$ being injective.
If $g$ were a right inverse then $f (g (1)) = 1$ , that is $2 g (1) = 1$ , which has no integer solution. So no right inverse exists, consistent with $f$ not being surjective by Surjective iff a right inverse exists.
Note $f (q (1)) = f (0) = 0 \neq = 1$ : a left inverse need not be a right inverse.

□

Theorem 2.45 (Composition preserves both properties). Let $f : A \to B$ and $g : B \to C$ .

If $f$ and $g$ are injective, so is $g \circ f$ .
If $f$ and $g$ are surjective, so is $g \circ f$ .

Proof. (1) Suppose $(g \circ f) (a_{1}) = (g \circ f) (a_{2})$ , that is $g (f (a_{1})) = g (f (a_{2}))$ . Injectivity of $g$ gives $f (a_{1}) = f (a_{2})$ , and injectivity of $f$ gives $a_{1} = a_{2}$ .

(2) Let $c \in C$ . Since $g$ is surjective there is $b \in B$ with $g (b) = c$ ; since $f$ is surjective there is $a \in A$ with $f (a) = b$ . Then $(g \circ f) (a) = g (f (a)) = g (b) = c$ , so $c$ lies in the image of $g \circ f$ .∎

Theorem 2.46 (Partial converses for a composite). Let $f : A \to B$ and $g : B \to C$ .

If $g \circ f$ is injective, then $f$ is injective.
If $g \circ f$ is surjective, then $g$ is surjective.

Neither conclusion can be strengthened: $g \circ f$ injective does not force $g$ injective, and $g \circ f$ surjective does not force $f$ surjective.

Proof. (1) Suppose $f (a_{1}) = f (a_{2})$ . Applying $g$ gives $g (f (a_{1})) = g (f (a_{2}))$ , that is $(g \circ f) (a_{1}) = (g \circ f) (a_{2})$ ; since $g \circ f$ is injective, $a_{1} = a_{2}$ .

(2) Let $c \in C$ . Since $g \circ f$ is surjective there is $a \in A$ with $g (f (a)) = c$ . Then $b = f (a)$ is an element of $B$ with $g (b) = c$ , so $g$ is surjective.

For the counterexamples, take $A = {1}$ , $B = {1, 2}$ , $C = {1}$ with $f (1) = 1$ and $g (1) = g (2) = 1$ . Then $g \circ f$ is the identity on $A$ , hence both injective and surjective, while $g$ is not injective (it collapses $1$ and $2$ ) and $f$ is not surjective (it misses $2$ ).∎

Intuition. Read the arrows. In $A f B g C$ , information can only be destroyed as you move right, so if nothing was lost overall then nothing was lost in the first step — that is (1). Dually, everything in $C$ must be reached by the last step, so if the composite reaches all of $C$ then so does $g$ — that is (2). The two halves that fail are the ones about the far end of the chain, where the other map can hide the defect.

Example 2.47 (Using the partial converses). Let $f : N \to Z$ be $f (n) = n$ and $g : Z \to Z$ be $g (n) = n^{2}$ . Is $g \circ f$ injective? Is $g$ injective? What does Partial converses for a composite let you conclude?

Solution.

$(g \circ f) (n) = n^{2}$ on $N$ , and $n_{1}^{2} = n_{2}^{2}$ with $n_{1}, n_{2} \geq 0$ forces $n_{1} = n_{2}$ , so $g \circ f$ is injective.
$g$ itself is not injective on $Z$ , since $g (- 1) = g (1)$ .
The theorem concludes only that $f$ is injective, which it is. This is exactly the case showing the missing half — an injective composite with a non-injective outer map — is genuinely possible.

□

Theorem 2.48 (Counting injections). Let $∣ A ∣ = n$ and $∣ B ∣ = m$ . The number of injections $A \to B$ is the falling factorial

m^{\underline{n}} = m (m - 1) (m - 2) \dots (m - n + 1) = \frac{m !}{( m - n )!}

when $n \leq m$ , and $0$ when $n > m$ .

Proof. List $A = {a_{1}, \dots, a_{n}}$ and build an injection by choosing values in order. The value $f (a_{1})$ may be any of the $m$ elements of $B$ . Given the first $i$ values, all distinct, the value $f (a_{i + 1})$ must avoid them and may be anything else, so there are $m - i$ choices. Each sequence of choices yields a distinct injection and every injection arises from exactly one such sequence, namely the sequence of its own values. Multiplying the independent counts gives $m (m - 1) \dots (m - n + 1)$ .

If $n > m$ the process stalls: after $m$ steps every element of $B$ has been used and the factor $m - m = 0$ appears, so the product is $0$ . That no injection exists in this case is the content of the next theorem.∎

Theorem 2.49 (Pigeonhole principle, in function form). Let $A$ and $B$ be finite with $∣ A ∣ > ∣ B ∣$ . Then no function $f : A \to B$ is injective; equivalently, some $b \in B$ has $∣ f^{- 1} ({b}) ∣ \geq 2$ .

Proof. Let $∣ B ∣ = m$ and let $f : A \to B$ be any function. The sets $f^{- 1} ({b})$ for $b \in B$ are pairwise disjoint — an element $a$ lies in the one indexed by $b = f (a)$ and no other — and their union is $A$ , because $f$ is total. Hence

∣ A ∣ = b \in B \sum ∣ f^{- 1} ({b}) ∣.

If every term were at most $1$ the sum would be at most $m = ∣ B ∣ < ∣ A ∣$ , a contradiction. So some term is at least $2$ , meaning two distinct elements of $A$ share an image, and $f$ is not injective.∎

Intuition. Put $∣ A ∣$ pigeons into $∣ B ∣$ holes with more pigeons than holes and some hole holds two. The argument above is just that statement with the holes named $f^{- 1} ({b})$ . Its power comes from choosing the function well: to show that among any $13$ people two share a birth month, take $f$ from people to months.

Example 2.50 (A pigeonhole argument). Show that any set of $6$ distinct integers chosen from ${1, 2, \dots, 10}$ contains two whose difference is $5$ , or explain why it can fail.

Solution.

Pair the numbers by remainder-style blocks: ${1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}$ — five pairs, each with difference $5$ .
Define $f$ from the chosen $6$ integers to these $5$ pairs by sending each integer to the pair containing it. This is a function from a $6$ -element set to a $5$ -element set.
By the Pigeonhole principle, in function form, $f$ is not injective, so two chosen integers lie in the same pair. Those two differ by exactly $5$ .

□

Exercises for §2.4 →

2.5Bijections and the comparison of sizes

A bijection pairs the elements of two sets with nothing left over on either side. That is what "same size" ought to mean, and taking it as the definition of same size is what lets the notion survive the passage to infinite sets.

Theorem 2.51 (Bijective iff a two-sided inverse exists). Let $f : A \to B$ . Then $f$ is bijective if and only if there is a function $f^{- 1} : B \to A$ with

f^{- 1} \circ f = id_{A} and f \circ f^{- 1} = id_{B} .

Moreover such a function is unique.

Proof. ( $\Leftarrow$ ) If such a function exists it is in particular a left inverse and a right inverse, so $f$ is injective by Injective iff a left inverse exists and surjective by Surjective iff a right inverse exists.

( $\Rightarrow$ ) Suppose $f$ is bijective. For each $b \in B$ , surjectivity provides an $a \in A$ with $f (a) = b$ and injectivity makes it unique; define $f^{- 1} (b)$ to be that $a$ . This is a total, single-valued assignment, hence a function $B \to A$ . By construction $f (f^{- 1} (b)) = b$ for all $b$ , and for $a \in A$ the unique preimage of $f (a)$ is $a$ , so $f^{- 1} (f (a)) = a$ .

For uniqueness, suppose $g$ and $h$ both satisfy the two identities. Then, using associativity from Composition is associative, with identities,

g = g \circ id_{B} = g \circ (f \circ h) = (g \circ f) \circ h = id_{A} \circ h = h .

∎

Definition 2.52 (Inverse function). For a bijection $f : A \to B$ , the unique function $f^{- 1} : B \to A$ of the preceding theorem is the inverse of $f$ .

Pitfall. The symbol $f^{- 1}$ is overloaded. Applied to a set it means the preimage and always makes sense; applied to an element it means the inverse function and makes sense only when $f$ is bijective. Context disambiguates, but write $f^{- 1} ({b})$ rather than $f^{- 1} (b)$ whenever $f$ is not known to be a bijection.

Theorem 2.53 (The inverse of a bijection is a bijection). If $f : A \to B$ is a bijection then $f^{- 1} : B \to A$ is a bijection, and $(f^{- 1})^{- 1} = f$ .

Proof. The two identities characterising $f^{- 1}$ read, from the point of view of $f^{- 1}$ , as: $f$ is a left inverse of $f^{- 1}$ (since $f \circ f^{- 1} = id_{B}$ ) and a right inverse of $f^{- 1}$ (since $f^{- 1} \circ f = id_{A}$ ). So $f^{- 1}$ has a two-sided inverse, namely $f$ , and by Bijective iff a two-sided inverse exists it is a bijection with inverse $f$ .∎

Proposition 2.54 (Composites of bijections). If $f : A \to B$ and $g : B \to C$ are bijections, then $g \circ f$ is a bijection and

(g \circ f)^{- 1} = f^{- 1} \circ g^{- 1} .

Proof. That $g \circ f$ is bijective follows from Composition preserves both properties applied twice. For the formula, compute both composites using associativity:

(f^{- 1} \circ g^{- 1}) \circ (g \circ f) = f^{- 1} \circ (g^{- 1} \circ g) \circ f = f^{- 1} \circ id_{B} \circ f = f^{- 1} \circ f = id_{A},

and symmetrically $(g \circ f) \circ (f^{- 1} \circ g^{- 1}) = id_{C}$ . By the uniqueness clause of Bijective iff a two-sided inverse exists, $f^{- 1} \circ g^{- 1}$ is the inverse of $g \circ f$ .∎

Intuition. Undoing "socks then shoes" is "shoes off then socks off": the order reverses. That is the whole content of $(g \circ f)^{- 1} = f^{- 1} \circ g^{- 1}$ , and the same reversal appears for matrix inverses and for group inverses, because it depends only on associativity and identities.

Theorem 2.55 (Counting bijections). If $∣ A ∣ = ∣ B ∣ = n$ , the number of bijections $A \to B$ is $n!$ .

Proof. A bijection between two $n$ -element sets is in particular an injection, and by Counting injections with $m = n$ there are $n (n - 1) \dots 1 = n!$ injections $A \to B$ . Conversely every injection here is already a bijection: its image is a subset of $B$ with $n$ distinct elements, and a subset of an $n$ -element set having $n$ elements is the whole set. So bijections and injections coincide in this case, and there are $n!$ of them.∎

Definition 2.56 (Equinumerosity). Sets $A$ and $B$ are equinumerous, written $∣ A ∣ = ∣ B ∣$ , if some bijection $A \to B$ exists. A set is finite if it is equinumerous with $[n]$ for some $n \in N$ , countably infinite if it is equinumerous with $N$ , and uncountable otherwise.

Proposition 2.57 (Equinumerosity behaves like an equality). For all sets $A$ , $B$ , $C$ : $∣ A ∣ = ∣ A ∣$ ; if $∣ A ∣ = ∣ B ∣$ then $∣ B ∣ = ∣ A ∣$ ; and if $∣ A ∣ = ∣ B ∣$ and $∣ B ∣ = ∣ C ∣$ then $∣ A ∣ = ∣ C ∣$ .

Proof. For the first, $id_{A}$ is a bijection $A \to A$ , since it is its own two-sided inverse. For the second, a bijection $f : A \to B$ yields the bijection $f^{- 1} : B \to A$ by The inverse of a bijection is a bijection. For the third, bijections $f : A \to B$ and $g : B \to C$ compose to the bijection $g \circ f : A \to C$ by Composites of bijections.∎

Example 2.58 (An infinite set equinumerous with a proper subset). Exhibit a bijection from $N$ to the set $E$ of even natural numbers, and say what it shows.

Solution.

Define $f : N \to E$ by $f (n) = 2 n$ .
Injective: $2 n_{1} = 2 n_{2}$ gives $n_{1} = n_{2}$ . Surjective: any even $m \in E$ is $2 (m /2)$ with $m /2 \in N$ .
So $∣ N ∣ = ∣ E ∣$ , even though $E ⊊ N$ . For infinite sets a proper subset may have the same size — a phenomenon impossible for finite sets, where Pigeonhole principle, in function form forbids it. This is Hilbert's hotel, and it is a theorem, not a paradox.

□

Theorem 2.59 (Counting surjections). The number of surjections from an $n$ -element set onto an $m$ -element set is

S (n, m) = k = 0 \sum m (- 1)^{k} (k m) (m - k)^{n} .

Proof. Let $B = {b_{1}, \dots, b_{m}}$ and for each $i$ let $M_{i}$ be the set of functions $A \to B$ that miss $b_{i}$ . A function fails to be surjective exactly when it lies in $M_{1} \cup \dots \cup M_{m}$ , so the surjections number $m^{n} - ∣ M_{1} \cup \dots \cup M_{m} ∣$ by Counting functions.

For a set $I$ of $k$ indices, the functions missing every $b_{i}$ with $i \in I$ are precisely the functions from $A$ into the remaining $m - k$ elements, of which there are $(m - k)^{n}$ ; and there are $(k m)$ such index sets. The inclusion–exclusion principle — the pattern proved above for two and three sets, extended to $m$ sets by the same alternating bookkeeping — therefore gives

∣ M_{1} \cup \dots \cup M_{m} ∣ = k = 1 \sum m (- 1)^{k + 1} (k m) (m - k)^{n} .

Subtracting from $m^{n}$ and absorbing $m^{n}$ as the $k = 0$ term of the alternating sum yields the stated formula.∎

Example 2.60 (Surjections onto a three-element set). How many functions from a $4$ -element set onto a $3$ -element set are there?

Solution.

By Counting surjections with $n = 4$ , $m = 3$ : $(0 3) 3^{4} - (1 3) 2^{4} + (2 3) 1^{4} - (3 3) 0^{4}$ .
That is $81 - 3 \cdot 16 + 3 \cdot 1 - 0 = 81 - 48 + 3 = 36$ .
Check against the structure: a surjection $[4] \to [3]$ collapses exactly one pair of inputs, and there are $(2 4) = 6$ pairs and $3! = 6$ ways to assign the resulting three blocks to the three targets, giving $6 \cdot 6 = 36$ . Final answer: $36$ .

□

Exercises for §2.5 →

2.6Power sets, and a set that outruns every function into it

The power set is the first construction that takes a set to a strictly bigger one, and the argument that it does so is the deepest thing in this chapter.

Definition 2.61 (Power set). The power set of a set $A$ is the set of all subsets of $A$ :

P (A) = {S : S \subseteq A} .

The elements of $P (A)$ are sets. For $A = {1, 2}$ ,

P (A) = {\emptyset, {1}, {2}, {1, 2}},

a four-element set, and note that $\emptyset \in P (A)$ and $A \in P (A)$ always, by The empty set is a subset of every set and reflexivity of inclusion. In particular $P (\emptyset) = {\emptyset}$ has one element, not none: the empty set has exactly one subset, itself.

Theorem 2.62 (The size of a power set). If $∣ A ∣ = n$ is finite, then $∣ P (A) ∣ = 2^{n}$ .

Proof. Write $A = {a_{1}, \dots, a_{n}}$ and define $χ : P (A) \to {0, 1}^{n}$ by sending a subset $S$ to its indicator string

χ (S) = (s_{1}, \dots, s_{n}), s_{i} = {1, 0, a_{i} \in S, a_{i} \in / S .

This is a function: each subset determines each bit unambiguously.

$χ$ is injective. If $χ (S) = χ (T)$ then for every $i$ we have $a_{i} \in S$ if and only if $s_{i} = 1$ if and only if $a_{i} \in T$ . Since every element of $A$ is some $a_{i}$ , the sets $S$ and $T$ have the same elements, so $S = T$ by extensionality.

$χ$ is surjective. Given a string $(s_{1}, \dots, s_{n}) \in {0, 1}^{n}$ , put $S = {a_{i} : s_{i} = 1}$ . Then $S \subseteq A$ and $χ (S)$ is the given string.

So $χ$ is a bijection, and by Tuples from one set the codomain has $2^{n}$ elements. Hence $∣ P (A) ∣ = 2^{n}$ .∎

Intuition. Building a subset is walking down the list of elements answering one yes/no question each: in or out? The record of your answers is a binary string of length $n$ , every string is a possible record, and different records give different subsets. So subsets and strings are the same objects wearing different clothes — which is why a set data type is often implemented as a bit vector.

Corollary 2.63 (Subsets by size). For $∣ A ∣ = n$ and $0 \leq k \leq n$ , the number of subsets of $A$ with exactly $k$ elements is $(k n)$ , and consequently

k = 0 \sum n (k n) = 2^{n} .

Proof. Under the bijection $χ$ of The size of a power set, a subset of size $k$ corresponds to a binary string with exactly $k$ ones, and the number of such strings is the number of ways to choose which $k$ of the $n$ positions carry a one, namely $(k n)$ . Every subset has exactly one size, so classifying $P (A)$ by size partitions it into the $n + 1$ disjoint pieces counted by $(0 n), \dots, (n n)$ , whose total is $∣ P (A) ∣ = 2^{n}$ .∎

Example 2.64 (Power sets of small sets). Compute $∣ P (A) ∣$ and $∣ P (P (A)) ∣$ for $∣ A ∣ = 3$ , and list $P ({a, b})$ .

Solution.

$∣ P (A) ∣ = 2^{3} = 8$ by The size of a power set.
Applying the theorem again to the $8$ -element set $P (A)$ : $∣ P (P (A)) ∣ = 2^{8} = 256$ .
$P ({a, b}) = {\emptyset, {a}, {b}, {a, b}}$ , four elements, as $2^{2} = 4$ predicts. Final answer: $8$ and $256$ .

□

Example 2.65 (Counting subsets with a constraint). How many subsets of ${1, 2, \dots, 10}$ contain the element $3$ but not the element $7$ ?

Solution.

Membership of $3$ is forced to "in" and membership of $7$ is forced to "out", so two of the ten yes/no decisions are made for us.
The remaining $8$ elements are unconstrained, giving $2^{8} = 256$ subsets by the indicator-string argument of The size of a power set. Final answer: $256$ .

□

Everything so far has been finite bookkeeping. The final theorem is not, and it is the reason this chapter ends here rather than with a summary of counting formulas. Cantor's question is: can a set be listed by its own elements? Can we index every subset of $A$ by an element of $A$ ?

Figure 2.66. Cantor's diagonal for

A = {a_{1}, \dots, a_{5}}

. Row

i

records the membership string of

f (a_{i})

; the marked diagonal entries are

[a_{i} \in f (a_{i})]

. The diagonal set

D

flips every diagonal entry, so its row differs from row

i

in column

i

for every

i

— and therefore equals no row at all.

Theorem 2.67 (Cantor's theorem). For every set $A$ , there is no surjection $f : A \to P (A)$ . Consequently $∣ A ∣ \neq = ∣ P (A) ∣$ .

Proof. Let $f : A \to P (A)$ be any function. Define the diagonal set

D = {a \in A : a \in / f (a)} .

This is a legitimate subset of $A$ : it is carved out of $A$ by the property " $a \in / f (a)$ ", which is a well-formed statement about $a$ , since $f (a)$ is a subset of $A$ and membership in it is a yes-or-no question. So $D \in P (A)$ .

We claim $D$ is not in the image of $f$ . Suppose, for contradiction, that $D = f (a_{0})$ for some $a_{0} \in A$ , and ask whether $a_{0} \in D$ .

If $a_{0} \in D$ , then by the defining property of $D$ we have $a_{0} \in / f (a_{0}) = D$ , a contradiction.
If $a_{0} \in / D$ , then $a_{0}$ fails the defining property, so $a_{0} \in f (a_{0}) = D$ , again a contradiction.

Both cases are impossible, yet one of them must hold, so no such $a_{0}$ exists. Hence $D \in P (A)$ is missed by $f$ , and $f$ is not surjective.

Since $f$ was arbitrary, no surjection $A \to P (A)$ exists. A bijection is in particular a surjection, so no bijection exists either, and $∣ A ∣ \neq = ∣ P (A) ∣$ .∎

Intuition. Read $f$ as a table with one row per element of $A$ , row $a$ holding the membership string of the subset $f (a)$ , as in the figure. The set $D$ is built by walking down the main diagonal and writing the opposite of what you find. The resulting string cannot be row $1$ , because it differs there in column $1$ ; it cannot be row $2$ , because it differs in column $2$ ; and so on for every row. The table lists some subsets and $D$ is not among them, no matter how the table was filled in.

Remark. Note what the proof does not need: $A$ may be finite, countable or anything else, and no counting is performed. For finite $A$ the conclusion is the familiar $n < 2^{n}$ ; for $A = N$ it says $P (N)$ is uncountable, which is the standard proof that the reals cannot be listed. Iterating gives $N, P (N), P (P (N)), \dots$ , an unending ladder of strictly increasing infinities, so there is no largest set and no single "infinity". Where exactly the reals sit on that ladder is the continuum hypothesis, and the answer — that the usual axioms settle neither yes nor no — belongs to Set Theory.

Remark. The map $a \mapsto {a}$ is an injection $A \to P (A)$ , so $P (A)$ is at least as large as $A$ ; Cantor's theorem says it is never exactly as large. The two together are what justify calling the power set strictly bigger.

Example 2.68 (The diagonal set for a small map). Let $A = {1, 2, 3}$ and let $f (1) = {1, 2}$ , $f (2) = \emptyset$ , $f (3) = {1, 3}$ . Compute $D$ and verify it is missed by $f$ .

Solution.

Test each element: $1 \in f (1) = {1, 2}$ , so $1 \in / D$ . $2 \in / f (2) = \emptyset$ , so $2 \in D$ . $3 \in f (3) = {1, 3}$ , so $3 \in / D$ .
Hence $D = {2}$ .
The image of $f$ is ${{1, 2}, \emptyset, {1, 3}}$ , and ${2}$ is not among its three members, exactly as Cantor's theorem predicts. Indeed $f$ misses $2^{3} - 3 = 5$ subsets in all; the theorem's contribution is to name one that is missed for every $f$ at once.

□

Summary. The chapter's spine: extensionality gives Set equality by double inclusion, which is the proof technique for every identity of set algebra — the Distributive laws, De Morgan's laws for sets, and the rest. Counting starts with Inclusion–exclusion for two sets and its three-set version, and with $∣ A \times B ∣ = ∣ A ∣∣ B ∣$ , from which Counting functions gives $m^{n}$ , Counting injections gives the falling factorial, Counting bijections gives $n!$ and Counting surjections gives an alternating sum. Injectivity and surjectivity are characterised by one-sided inverses and bijectivity by a two-sided one; composition preserves both properties, and the partial converses hold only at the near and far ends of the chain. Finally $∣ P (A) ∣ = 2^{∣ A ∣}$ by the indicator-string bijection, and Cantor's theorem shows that no function from $A$ can reach every subset of $A$ .

Exercises for §2.6 →

Common Mistakes

Confusing $\in$ with $\subseteq$ . For $A = {1, 2}$ : $1 \in A$ and ${1} \subseteq A$ are true; $1 \subseteq A$ and ${1} \in A$ are not. The confusion is fatal in $P (A)$ , whose elements are sets.
Believing $\emptyset = {\emptyset}$ . The first has no elements; the second has one. Hence $∣ P (\emptyset) ∣ = 1$ , not $0$ .
Proving only one inclusion. " $\subseteq$ " is half of an equality. If your steps are genuine equivalences, say so and cite that the chain reads both ways; otherwise write the second half out, because it may need a different idea — as in the $6 ∣ n$ example.
Distrusting a vacuous argument. $\emptyset \subseteq A$ is true because no element of $\emptyset$ can witness a failure. This is not a loophole; it is what "for all" means over an empty range.
Adding cardinalities of overlapping sets. $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣$ needs $A \cap B = \emptyset$ . Otherwise subtract the overlap, and for three sets remember to add $∣ A \cap B \cap C ∣$ back.
Confusing codomain with image. $f (x) = x^{2}$ as a map $R \to R$ is not surjective; the same rule as a map $R \to [0, \infty)$ is. Surjectivity is never a property of the rule alone.
Checking injectivity with one example. Showing $f (1) \neq = f (2)$ proves nothing. Assume $f (a_{1}) = f (a_{2})$ and derive $a_{1} = a_{2}$ for arbitrary $a_{1}, a_{2}$ ; a single collision, on the other hand, does disprove it.
Assuming a left inverse is a right inverse. $⌊ n /2 ⌋$ undoes doubling from the left but not from the right. Only a bijection has a two-sided inverse.
Over-reading the partial converses. $g \circ f$ injective gives only that $f$ is injective, and $g \circ f$ surjective only that $g$ is. The other halves are false, with a two-line counterexample.
Counting functions as $n^{m}$ instead of $m^{n}$ . With $∣ A ∣ = n$ and $∣ B ∣ = m$ , the count of $f : A \to B$ is $∣ B ∣^{∣ A ∣} = m^{n}$ : one independent choice per element of the domain.
Writing $f^{- 1}$ for a non-invertible $f$ and then treating it as a function. $f^{- 1} (T)$ is always a preimage set; $f^{- 1} (b)$ as an element requires bijectivity.
Claiming Cantor's proof needs infinity. It needs nothing but the definition of $D$ , and it applies verbatim to a three-element set. Infinity is where the conclusion becomes surprising, not where the proof lives.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

Practice this chapter