0.3 Sets, functions, and counting infinity

Sets and functions are the language everything else is written in. A perfect matching (a bijection) is how we compare sizes, and it shows that the integers and the rationals are as small as the counting numbers while the real numbers are strictly larger.

Two questions drive this chapter. What are the basic objects that all of mathematics is built from, and how do you decide whether two collections have “the same number of elements” when neither can be counted to the end? The answers are sets and functions. A set is a collection, a function is a rule, and a perfect pairing between two collections is what “same size” turns out to mean. With that one idea the whole numbers, the integers and the fractions all turn out to be the same size, and the real numbers do not.

Before you start

0.1 for reading and negating statements, and 0.2 for the shapes of proofs (direct, contradiction, cases, induction, well-ordering). Three quick checks.

Quick checkWhat is the negation of 'the number

x

is in

A

and in

B

Quick checkTo prove 'for every

x

, if

P(x)

then

Q(x)

' directly, how do you begin?

Quick checkEvery non-empty set of positive integers has a smallest element. Is the same true for the set of all positive rational numbers?

The picture

Take $A = \{1, 2, 3, 4\}$ and $B = \{3, 4, 5\}$ , inside the universe $U = \{1, 2, 3, 4, 5, 6\}$ . Everything in this chapter’s first half is a question about which numbers land where.

Set	Elements	In words
$A \cup B$	$\{1, 2, 3, 4, 5\}$	in $A$ , or in $B$ , or both
$A \cap B$	$\{3, 4\}$	in both
$A \setminus B$	$\{1, 2\}$	in $A$ but not in $B$
$A^c$	$\{5, 6\}$	in the universe but not in $A$

For the second half, picture two cinema halls with a seat for each person and no empty seats. You can tell that they hold the same number of people without counting anyone: send each person of one group to the seat of their partner. If everyone has a seat, and no seat is shared, and no seat is empty, the groups match. That matching is what mathematicians call a bijection, and it works equally well when the groups are infinite.

Here is the surprise to look for. The counting numbers $1, 2, 3, \dots$ can be matched with the even numbers $2, 4, 6, \dots$ by $n \mapsto 2n$ . The evens are only some of the counting numbers, and yet the matching leaves nobody out. For infinite sets “a part can be as big as the whole”.

The idea, in words

A set is a collection of things, and a function is a rule that sends each thing in one set to exactly one thing in another. Almost every object in mathematics is one of these: a sequence is a function on the counting numbers, a vector space is a set with extra rules, a probability is a function on a set of events.

Why· Why a perfect matching is the right idea of 'same size'

For finite sets, “same size” means that you get the same number when you count. But counting is a matching: you pair the objects with $1, 2, 3, \dots$ and stop. Strip away the numbers and what remains is a pairing with no one left over on either side. That makes sense for any pair of sets, finite or not. Comparing sizes without counting is also how a shepherd checks that no sheep is missing: one pebble per sheep.

Each phrase in “no one left out and no seat shared” becomes a word below. “No one on the left is unpaired” is that the rule is a function. “No seat is shared” is injective. “No seat is empty” is surjective. Both together is bijective.

Where this came from· Before Cantor: Galileo noticed it, and gave up

In his Two New Sciences (1638), Galileo pointed out that each counting number has a square, so the squares $1, 4, 9, 16, \dots$ match up with all the counting numbers. Yet most counting numbers are not squares. His conclusion was that “equal”, “less” and “greater” make no sense for infinite collections. Bernard Bolzano took the problem up again in a book published after his death (1851). He accepted that an infinite set can be matched with a part of itself, but he still held that the part must be smaller than the whole, so a matching alone did not make two sets equal in size for him. Georg Cantor, in the 1870s, did the opposite: he made the matching the definition of “same size” and gave up the idea that a part is always smaller. He then discovered that infinite sets come in different sizes after all. The rest of this chapter follows his road.

Definitions and theorems

Sets

Definition B

Set

A set is a collection of objects, called its elements. We write $x \in A$ for ” $x$ is an element of $A$ ”, and $x \notin A$ for ” $x \in A$ is false”. Two ways to describe a set:

Roster: list the elements, as in $\{2, 3, 5, 7\}$ . Order and repeats do not matter: $\{1, 2, 2\} = \{2, 1\}$ .
Set-builder: $\{x \in D : P(x)\}$ , read “the set of all $x$ in $D$ such that $P(x)$ ”. The colon means “such that” (CS 240 uses a colon, because the bar is also used for absolute value and divisibility).

The empty set $\varnothing$ has no elements. The standard number sets are $\mathbb N = \{1, 2, 3, \dots\}$ , $\mathbb Z$ (all integers), $\mathbb Q = \{ z / b : z \in \mathbb Z,\ b \in \mathbb N \}$ (the rationals) and $\mathbb R$ (the reals). CS 240 puts $0$ in $\mathbb N$ . Here $\mathbb N$ starts at $1$ because we will use its elements as positions in a list: first, second, third.

In one lineA collection of objects, called its elements; what matters is only which objects are in it.

Why it existsSets are the raw material: numbers, functions, vectors and events are all described by saying which objects belong to a set.

The statement $x \notin A$ is the negation of $x \in A$ . That is why the negation rules from 0.1 will do all the work in this section.

Definition B

Subset

$A$ is a subset of $B$ , written $A \subseteq B$ , if $\forall x\ (x \in A \Rightarrow x \in B)$ . We write $A \subsetneq B$ when also $A \ne B$ (a proper subset; CS 240 writes this $A \subset B$ , and some books use $\subset$ for plain subset, so check each book).

In one line $A \subseteq B$ means every element of $A$ is also an element of $B$ .

Why it existsIt is the tool for comparing sets, and for proving two sets are equal.

To prove $A \subseteq B$ you use the recipe from 0.2 for a statement of the shape “for every $x$ , if … then …”.

Write “Let $x \in A$ be arbitrary.”
Derive " $x \in B$ " using the definition of $A$ .

Two things follow from reading the definition exactly. First, $\varnothing \subseteq A$ for every set $A$ : the statement " $x \in \varnothing \Rightarrow x \in A$ " has a false hypothesis for every $x$ , so it is true (vacuous truth, as in 0.1). Second, $A \not\subseteq B$ (read ” $A$ is not a subset of $B$ ”) means, by the negation rules, $\exists x\ (x \in A \land x \notin B)$ . To disprove a subset claim, name one such $x$ .

Theorem B

Double inclusion

For sets $A$ and $B$ : $A = B$ if and only if $A \subseteq B$ and $B \subseteq A$ .

In one line $A = B$ exactly when $A \subseteq B$ and $B \subseteq A$ .

Why it is trueTwo sets are equal when they have the same elements, and 'same elements' is two one-way statements.

ProofHammack 8.3

The idea: Equal sets have the same elements. Write that as an if-and-only-if for every x, and split it into its two directions.

A = B

means

\forall x\ (x \in A \Leftrightarrow x \in B)

This is the definition of equality of sets: they are the same exactly when they have the same elements.

That is

\forall x\ (x \in A \Rightarrow x \in B)

and

\forall x\ (x \in B \Rightarrow x \in A)

An if-and-only-if is two implications (0.1). The quantifier

\forall x

can be applied to each implication separately.

A = B

if and only if

A \subseteq B

and

B \subseteq A

The first is the definition of

A \subseteq B

and the second is the definition of

B \subseteq A

This theorem is the standard way to prove two sets equal: show each is inside the other, by taking an arbitrary element of one and chasing it into the other. We call that element-chasing.

Worked example Hammack 8.1

Show that if

A \subseteq B

and

B \subseteq C

, then

A \subseteq C

Solution.

Set up the goal. We must show $\forall x\ (x \in A \Rightarrow x \in C)$ . So let $x \in A$ be arbitrary. The recipe for a subset proof: an arbitrary element of the smaller set.
Use the first hypothesis. $A \subseteq B$ and $x \in A$ , so $x \in B$ . That is the definition of $A \subseteq B$ , applied to our $x$ .
Use the second hypothesis. $B \subseteq C$ and $x \in B$ , so $x \in C$ . The definition again, applied to the same $x$ .

Answer. Our arbitrary $x \in A$ lies in $C$ , so $A \subseteq C$ .

Union, intersection, complement

Definition B

Union

$A \cup B = \{x : x \in A \lor x \in B\}$ .

In one line $A \cup B$ is the set of everything that is in $A$ or in $B$ (or both).

Why it existsIt is the set-version of 'or': it collects everything that satisfies at least one of two conditions.

Definition B

Intersection

$A \cap B = \{x : x \in A \land x \in B\}$ . Sets with $A \cap B = \varnothing$ are called disjoint.

In one line $A \cap B$ is the set of everything that is in both $A$ and $B$ .

Why it existsIt is the set-version of 'and': it collects everything that satisfies both conditions at once.

Definition B

Complement

Fix a universe $U$ , the set that all elements under discussion belong to. The complement of $A$ is $A^c = \{x \in U : x \notin A\}$ . The related difference is $A \setminus B = \{x : x \in A \land x \notin B\}$ , so $A^c = U \setminus A$ . The Cartesian product is $A \times B = \{(a, b) : a \in A,\ b \in B\}$ , the set of ordered pairs. Order matters: $(1, 2) \ne (2, 1)$ . If $A$ has 3 elements and $B$ has 2, then $A \times B$ has $3 \cdot 2 = 6$ .

In one line $A^c$ is everything in the universe $U$ that is not in $A$ .

Why it existsIt is the set-version of 'not'. It only makes sense relative to a universe, the big set that all our elements come from.

Notice that each definition rewrites ” $x$ belongs to the new set” as a statement built from " $x \in A$ " with and, or, not. That is the whole secret of proofs about sets: membership in $A \cup B$ is, by definition, a logical sentence, so logic from 0.1 applies.

The rules for ‘not in’

A question you asked: what are the rules on “doesn’t belong to”? There is nothing new to memorize. “Not in” is the negation of “in”, so the negation rules of 0.1 apply to the definitions.

Fact B

Rules for not in

For $x \in U$ and sets $A, B$ :

$x \notin A \cap B$ if and only if $x \notin A$ or $x \notin B$ .
$x \notin A \cup B$ if and only if $x \notin A$ and $x \notin B$ .
$x \notin A^c$ if and only if $x \in A$ .
$x \notin A \setminus B$ if and only if $x \notin A$ or $x \in B$ .
$(x, y) \notin A \times B$ if and only if $x \notin A$ or $y \notin B$ .
$x \notin \{y : P(y)\}$ if and only if $P(x)$ is false.

In one lineNot in an intersection means missing from at least one; not in a union means missing from both; not in a complement means in the original set.

Why it is trueEach rule is a negation rule of 0.1 applied to the definition of the set operation.

Proofstandard

The idea: Write what membership means, put 'not' in front, and push the 'not' inward with the rules of 0.1.

Rule 1:

\neg(x \in A \land x \in B)

x \notin A \lor x \notin B

By the definition of intersection,

x \in A \cap B

means

x \in A \land x \in B

. Negate it with De Morgan (rule 1 of 0.1).

Rule 2:

\neg(x \in A \lor x \in B)

x \notin A \land x \notin B

By the definition of union,

x \in A \cup B

means

x \in A \lor x \in B

. Rule 2 of 0.1.

Rule 3:

\neg(x \notin A)

x \in A

By definition,

x \in A^c

means

x \notin A

(for

x \in U

). Negating a negation gives back the original.

Rule 4:

\neg(x \in A \land x \notin B)

x \notin A \lor x \in B

x \in A \setminus B

means

x \in A \land x \notin B

. De Morgan, then

\neg(x \notin B)

x \in B

Rule 5:

\neg(x \in A \land y \in B)

x \notin A \lor y \notin B

(x, y) \in A \times B

means

x \in A \land y \in B

, since a pair is in the product exactly when each coordinate is in its set. De Morgan again.

Rule 6:

x \in \{y : P(y)\}

means

P(x)

, so its negation is that

P(x)

is false.

Membership in a set-builder set is, by its definition, the truth of the condition.

In practice you rarely quote the rules by number. You write what membership means, then negate with the rules of 0.1, and the word “or” appears whenever an “and” was negated.

Quick checkWhich statement is equivalent to

x \notin A \setminus B

Quick checkTo prove that

A \not\subseteq B

(that

A

is NOT a subset of

B

), what must you do?

Worked example

(A \cup B) \setminus B = A

true for all sets

A

and

B

? Prove it or disprove it.

Solution.

Try to prove it by element-chasing. $x \in (A \cup B) \setminus B$ means $x \in A \cup B$ and $x \notin B$ , that is ( $x \in A$ or $x \in B$ ) and $x \notin B$ . Unpack the definitions of difference and union, as in the proofs above.
See where it stops. Since $x \notin B$ , the part " $x \in B$ " is false, so $x \in A$ must hold. That gives $x \in A$ and $x \notin B$ , which is the set $A \setminus B$ , not $A$ . The two sets agree only if $x \in A$ already forces $x \notin B$ .
Build a counterexample. Take $A = \{1, 2\}$ and $B = \{2, 3\}$ . We need an element of $A$ that is also in $B$ , so that it is removed on the left. The element $2$ does that.
Compute both sides. $(A \cup B) \setminus B = \{1, 2, 3\} \setminus \{2, 3\} = \{1\}$ , but $A = \{1, 2\}$ . The element $2$ is in $A$ but not in the left side, so the two sets differ.

Answer. False in general. The left side equals $A \setminus B$ , so the identity holds exactly when $A$ and $B$ are disjoint. To disprove a statement “for all sets”, one specific example is enough.

Worked example

Let

U = \{1, \dots, 6\}

A = \{1, 2, 3, 4\}

B = \{3, 4, 5\}

C = \{4, 6\}

. Describe the elements that are NOT in

(A \cap B) \cup C

, and check with the list.

Solution.

Negate the outer operation first. $x \notin (A \cap B) \cup C$ means $x \notin A \cap B$ and $x \notin C$ . The outermost operation is a union, so use rule 2: not in a union means not in either part.
Negate the inner operation. $x \notin A \cap B$ means $x \notin A$ or $x \notin B$ . So the condition is: $(x \notin A \text{ or } x \notin B)$ and $x \notin C$ . Rule 1: not in an intersection means missing from at least one.
Test each element of $U$ . For $x = 1$ : $1 \notin B$ (true) and $1 \notin C$ (true), so $1$ qualifies. For $x = 2$ : $2 \notin B$ and $2 \notin C$ , so $2$ qualifies. For $x = 3$ : $3 \in A$ and $3 \in B$ , so the first bracket fails. For $x = 4$ : $4 \in C$ , so it fails. For $x = 5$ : $5 \notin A$ and $5 \notin C$ , so $5$ qualifies. For $x = 6$ : $6 \in C$ , so it fails. The condition is a sentence about one element, so we check it element by element.
Check against the direct computation. $A \cap B = \{3, 4\}$ , so $(A \cap B) \cup C = \{3, 4, 6\}$ , whose complement in $U$ is $\{1, 2, 5\}$ . The two methods must agree.

Answer. The elements not in the set are $1, 2, 5$ .

De Morgan’s laws for sets

Another question you asked: if De Morgan’s laws are not given on a CS 240 exam, how can you use them for sets? The answer is that you do not need them as a given fact. You prove them from the definitions, and the proof is short, because the set statement is the logic statement in disguise.

Theorem B

De Morgan's laws for sets

For sets $A, B$ inside a universe $U$ :

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

In one line $(A \cup B)^c = A^c \cap B^c$ and $(A \cap B)^c = A^c \cup B^c$ .

Why it is trueMembership in each side is a statement built from 'in', 'and', 'or', 'not', and the two sides are De Morgan's laws of logic.

ProofCS 240; Hammack 8.4

The idea: Take an arbitrary x in the universe. Turn 'x is in the left side' into a statement about x in A and x in B, apply a negation rule, and turn it back into 'x is in the right side'. Every line is an if-and-only-if, so one chain proves both inclusions at once.

Let

x \in U

. We show

x \in (A \cup B)^c \Leftrightarrow x \in A^c \cap B^c

This is the form of the goal that element-chasing needs:

x \in U

is arbitrary, and we will show the two memberships are equivalent.

x \in (A \cup B)^c \Leftrightarrow x \notin A \cup B

Definition of complement:

x \in U

, so

x \in (A \cup B)^c

means

x \notin A \cup B

\Leftrightarrow\ x \notin A \text{ and } x \notin B

Rule 2 of 'not in': the negation of 'in

A

or in

B

' is 'not in

A

and not in

B

'. This is De Morgan from 0.1.

\Leftrightarrow\ x \in A^c \text{ and } x \in B^c

Definition of complement, applied to

A

and to

B

separately (

x \in U

\Leftrightarrow\ x \in A^c \cap B^c

. So the first law holds, because every element of the universe is in one side exactly when it is in the other.

Definition of intersection.

The second law has the same proof.

The same chain, with 'union' and 'intersection' swapped, using rule 1 of 'not in' instead of rule 2:

x \in (A \cap B)^c \Leftrightarrow x \notin A \cap B \Leftrightarrow (x \notin A \text{ or } x \notin B) \Leftrightarrow (x \in A^c \text{ or } x \in B^c) \Leftrightarrow x \in A^c \cup B^c

This is the answer to “how can I use De Morgan if it is not given”: you write the chain above, with the justification beside each line, whenever a proof needs it. A proof that wants an identity as a step should either quote a theorem it is allowed to cite or reprove it like this. In CS 240 the justification column reads “definition of complement”, “De Morgan’s law (logic)”, and “definition of intersection”.

Worked example CS 240 practice

Prove

A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)

for all sets

A, B, C

Solution. The plan: take an arbitrary $x$ and turn each side into a statement about $x \in A$ , $x \in B$ , $x \in C$ .

Unpack the left side. $x \in A \setminus (B \cup C)$ means $x \in A$ and $x \notin B \cup C$ . Definition of difference.
Negate the union. That is $x \in A$ and ( $x \notin B$ and $x \notin C$ ). Rule 2 of ‘not in’.
Repeat the common part. That is equivalent to ( $x \in A$ and $x \notin B$ ) and ( $x \in A$ and $x \notin C$ ). Saying ” $P$ and ( $Q$ and $R$ )” is the same as saying ”( $P$ and $Q$ ) and ( $P$ and $R$ )”, because $P$ and $P$ is just $P$ (the idempotent law of CS 240).
Repack as set operations. $x \in A \setminus B$ and $x \in A \setminus C$ , which means $x \in (A \setminus B) \cap (A \setminus C)$ . Definitions of difference and intersection, read backwards.

Answer. Every line was an if-and-only-if, so an element is in the left side exactly when it is in the right side. The sets are equal.

Quick checkWhich is the complement of

A \cap B \cap C

(all inside

U

Functions

Definition B

Function

A function $f: A \to B$ assigns to every $a \in A$ exactly one element $f(a) \in B$ . The set $A$ is the domain, $B$ is the codomain, and $f(a)$ is the image of $a$ . The range (or image) of $f$ is $f(A) = \{f(a) : a \in A\}$ , the outputs actually used, which may be smaller than the codomain. Two functions are equal when they have the same domain, the same codomain, and the same output for every input. For $T \subseteq B$ the preimage is $f^{-1}(T) = \{a \in A : f(a) \in T\}$ (this notation does not need an inverse function to exist).

In one lineA rule $f: A \to B$ that assigns to every input in $A$ exactly one output in $B$ .

Why it existsFunctions describe how one quantity depends on another, and let us compare sets by matching them.

“Exactly one” contains two promises: every input has an output, and no input has two. So $x \mapsto \pm\sqrt x$ is not a function, and neither is " $x \mapsto 1/x$ " on $\mathbb R$ , which has no output at $x = 0$ . Chapter 0.4 returns to this point, because defining a function on fractions requires checking that the output does not depend on how you write the fraction.

There are two further properties, and each says half of a perfect matching. Apostol and chapter 2.3 call them one-to-one and onto.

Definition B

Injective

$f: A \to B$ is injective (also one-to-one) if for all $x, y \in A$ : $f(x) = f(y) \Rightarrow x = y$ . By the contrapositive of 0.1, this is the same as: $x \ne y \Rightarrow f(x) \ne f(y)$ .

In one line $f$ is injective (one-to-one) if different inputs always give different outputs: $f(x) = f(y)$ forces $x = y$ .

Why it existsIt says no two inputs are sent to the same place, so no information is lost and the output determines the input.

Definition B

Surjective

$f: A \to B$ is surjective (also onto) if $\forall b \in B\ \exists a \in A:\ f(a) = b$ .

In one line $f$ is surjective (onto) if every element of the codomain is an output: the range is the whole codomain.

Why it existsIt says nothing in the target is unreachable, so every equation $f(x) = b$ has a solution.

Definition B

Bijective

$f: A \to B$ is bijective if it is injective and surjective. Then every $b \in B$ has exactly one $a \in A$ with $f(a) = b$ (at least one from surjective, at most one from injective).

In one line $f$ is bijective if it is both injective and surjective: every element of the codomain is hit by exactly one input.

Why it existsA bijection is a perfect matching between two sets, which is what 'same size' means.

Read the quantifiers as in 0.1. Surjective is $\forall \exists$ : you pick $b$ first, and the proof must then produce an $a$ , which may depend on $b$ . Injective is a statement about every pair of inputs. This gives two templates.

To prove injective: “Suppose $f(x) = f(y)$ .” Then work until you get $x = y$ .
To prove surjective: “Let $b \in B$ be arbitrary.” Solve $f(a) = b$ for $a$ , write the answer as a formula in $b$ , and check that your $a$ lies in the domain $A$ .
To disprove either: exhibit two different inputs with the same output (not injective), or one target nobody reaches (not surjective).

Worked example

f: \mathbb R \to \mathbb R

f(x) = 3x + 2

injective? Surjective? Find the inverse.

Solution.

Injective. Suppose $f(x) = f(y)$ , that is $3x + 2 = 3y + 2$ . Subtract $2$ and divide by $3$ to get $x = y$ . The template for injective: assume equal outputs, derive equal inputs.
Surjective. Let $b \in \mathbb R$ be arbitrary. Solving $3a + 2 = b$ gives $a = (b - 2)/3$ , which is a real number, so it is in the domain. Check: $f(a) = 3 \cdot \tfrac{b - 2}{3} + 2 = b$ . The template for surjective: solve for the input, make sure it is in the domain, and check that it works.
Read off the inverse. The formula from step 2 undoes $f$ : $f^{-1}(b) = (b - 2)/3$ . The solution of $f(a) = b$ is exactly the inverse rule (see the theorem on inverses below).

Answer. $f$ is bijective, with inverse $f^{-1}(x) = (x - 2)/3$ .

Worked example

Classify

g: \mathbb Z \to \mathbb Z

g(n) = n^2

, and

h: \mathbb N \to \mathbb N

h(n) = n^2

Solution.

$g$ is not injective. $g(2) = 4 = g(-2)$ but $2 \ne -2$ . One pair of different inputs with the same output disproves injective.
$g$ is not surjective. The target $2$ is not a square: if $\lvert n \rvert \le 1$ then $n^2 \le 1$ , and if $\lvert n \rvert \ge 2$ then $n^2 \ge 4$ , so $n^2 = 2$ is impossible. To show a target is missed, we must rule out every input, not just try a few.
$h$ is injective. For positive $x, y$ , if $x^2 = y^2$ then $(x - y)(x + y) = 0$ , and $x + y > 0$ , so $x = y$ . Positivity removes the $-2$ that spoiled $g$ . The domain matters.
$h$ is not surjective. The target $2$ is again not a square. Same argument as step 2.

Answer. $g$ is neither. $h$ is injective but not surjective. The formula alone does not decide the answer; the domain and codomain are part of the function.

Worked example

Prove that

f: \mathbb R \setminus \{2\} \to \mathbb R \setminus \{1\}

f(x) = \dfrac{x + 1}{x - 2}

is a bijection, and find its inverse.

Solution.

Check that $f$ lands in the codomain. $f(x) = 1 + \dfrac{3}{x - 2}$ , and $\dfrac{3}{x-2}$ is never $0$ , so $f(x) \ne 1$ . A function must send every input into the stated codomain. Here the codomain leaves out $1$ for exactly this reason.
Injective. Suppose $\dfrac{x + 1}{x - 2} = \dfrac{y + 1}{y - 2}$ . Cross-multiplying (both denominators are non-zero) gives $(x + 1)(y - 2) = (y + 1)(x - 2)$ , that is $xy - 2x + y - 2 = xy - 2y + x - 2$ . This simplifies to $3y = 3x$ , so $x = y$ . The template for injective: assume equal outputs, derive equal inputs.
Surjective. Let $b \ne 1$ be arbitrary. Solve $\dfrac{a + 1}{a - 2} = b$ : $a + 1 = ab - 2b$ , so $a(1 - b) = -2b - 1$ , so $a = \dfrac{2b + 1}{b - 1}$ . This is defined because $b \ne 1$ . The template for surjective: solve for the input as a formula in $b$ .
Check that this $a$ is in the domain. If $a = 2$ then $2b + 1 = 2b - 2$ , which is impossible, so $a \ne 2$ . Check: $a - 2 = \dfrac{3}{b-1}$ and $a + 1 = \dfrac{3b}{b-1}$ , so $f(a) = b$ . The solution must be a legal input, and it must really work. Skipping this check is the usual slip.

Answer. $f$ is a bijection with inverse $f^{-1}(x) = \dfrac{2x + 1}{x - 1}$ . Spot check: $f(3) = 4$ and $f^{-1}(4) = 9/3 = 3$ .

Watch out· In JEE you wrote 'one-one onto', and the codomain was quietly part of the question

JEE asks “is $f$ one-one? onto?” for rules like $e^x$ on $\mathbb R$ . The honest answer depends on the codomain: $e^x: \mathbb R \to \mathbb R$ is injective but not onto (it never reaches $0$ or negative numbers), while $e^x: \mathbb R \to (0, \infty)$ is bijective, with inverse $\ln$ . Restricting the codomain to the range is always allowed and always makes a function surjective. That is why “the inverse of $e^x$ is $\ln x$ ” needs the codomain $(0, \infty)$ .

Quick check

f: \mathbb Z \to \mathbb Z

f(n) = 2n

. Which is true?

Composition. If $f: A \to B$ and $g: B \to C$ , the composition $g \circ f: A \to C$ is the function $(g \circ f)(a) = g(f(a))$ : first $f$ , then $g$ . The identity function on a set $A$ is $\mathrm{id}_A(a) = a$ .

Proposition B

Composition of injections and surjections

Let $f: A \to B$ and $g: B \to C$ .

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

In one lineIf $f$ and $g$ are injective, so is $g \circ f$ ; if both are surjective, so is $g \circ f$ ; hence a composition of bijections is a bijection.

Why it is trueFollow the chain of equalities (injective) or the chain of pre-images (surjective) one function at a time.

ProofHammack 12.2

The idea: Injective: peel off g, then peel off f. Surjective: given a target in C, find where g came from, then where f came from.

(1) Suppose

(g \circ f)(x) = (g \circ f)(y)

, that is

g(f(x)) = g(f(y))

Template for injective: assume equal outputs.

Then

f(x) = f(y)

g

is injective, so equal outputs of

g

come from equal inputs.

Then

x = y

. So

g \circ f

is injective.

f

is injective.

(2) Let

c \in C

Template for surjective: take an arbitrary target in the final codomain.

Pick

b \in B

with

g(b) = c

g

is surjective, so something in

B

is sent to

c

Pick

a \in A

with

f(a) = b

f

is surjective, so something in

A

is sent to

b

c

is an output of

g \circ f

, and

g \circ f

is surjective.

Substitute:

(g \circ f)(a) = g(f(a)) = g(b) = c

Theorem B

Bijections and inverses

A function $f: A \to B$ is bijective if and only if there is a function $g: B \to A$ with $g(f(a)) = a$ for every $a \in A$ and $f(g(b)) = b$ for every $b \in B$ . This $g$ is called the inverse of $f$ and written $f^{-1}$ . In particular, $f^{-1}$ is also bijective.

In one line $f: A \to B$ is bijective exactly when there is a function $g: B \to A$ that undoes it in both orders; this $g$ is the inverse $f^{-1}$ .

Why it is trueA bijection pairs each target with exactly one source, and reading the pairing backwards is the inverse.

ProofHammack 12.3

The idea: (Forward) Define g by 'the one input that lands on b', which exists because f is onto and is unique because f is one-to-one. (Backward) Use g to show f is injective and surjective.

(Bijective implies inverse.) Let

b \in B

. There is exactly one

a \in A

with

f(a) = b

. Define

g(b) = a

Surjective gives at least one input for each target; injective gives at most one. So 'the' input is well defined.This is the first time the two halves of 'bijective' are both used. Surjective makes g defined everywhere; injective makes g single-valued.

Then

f(g(b)) = b

for every

b

By the definition of

g

, the input chosen for

b

is sent by

f

b

And

g(f(a)) = a

for every

a

For

a \in A

, put

b = f(a)

. The unique input sent to

b

a

itself, so

g(b) = a

(Inverse implies bijective.) If

f(x) = f(y)

, then

x = g(f(x)) = g(f(y)) = y

. So

f

is injective.

Apply

g

to both sides of

f(x) = f(y)

and use

g(f(\cdot)) = \mathrm{id}

For

b \in B

f(g(b)) = b

, so

b

is an output of

f

. So

f

is surjective.

Given

b

, the input

g(b)

is sent by

f

b

Finally

f

is an inverse of

g

, so

g

is bijective too.

The conditions in the theorem are symmetric: they also say that

f

is an inverse of

g

. Apply the theorem to

g

Quick check

f: A \to B

and

g: B \to C

are functions, and

g \circ f

is injective. What must be true?

Size without counting

Definition B

Finite set

Write $\{1, \dots, n\}$ for the first $n$ counting numbers ( $\varnothing$ when $n = 0$ ). A set $A$ is finite with cardinality (size) $\lvert A \rvert = n$ if there is a bijection $\{1, \dots, n\} \to A$ . A set that is not finite is infinite. Two sets $A$ and $B$ have the same cardinality if there is a bijection $A \to B$ .

In one lineA set is finite with n elements if it can be matched with 1, 2, ..., n by a bijection; the number n is its size.

This definition would be useless if one set could be matched to both $\{1, \dots, 5\}$ and $\{1, \dots, 6\}$ . The pigeonhole principle says it cannot, so $\lvert A \rvert$ is well defined.

Theorem B

Pigeonhole principle

If $n > m$ , every function $f: \{1, \dots, n\} \to \{1, \dots, m\}$ is not injective.

In one lineIf more pigeons than holes, two pigeons share a hole: there is no injective function from $\{1, \dots, n\}$ to $\{1, \dots, m\}$ when $n > m$ .

Why it is trueRemove one hole and the pigeon in it, and use induction on the number of holes.

Proofstandard

The idea: Induct on the number of holes m. For the step, look at the last hole: take out the pigeon sitting in it (if any) and use the smaller case.

We prove

S(m)

for

m = 1, 2, 3, \dots

by induction.

Mathematical induction on

m

(0.2). The statement

S(m)

is: every function from a set with more than

m

elements into

\{1, \dots, m\}

is not injective.

S(1)

holds.

Base case. If

m = 1

and

n \ge 2

, then

f(1) = 1 = f(2)

, since there is only one possible output.

Take

f

as above. Split into two cases.

Inductive step: assume

S(m)

and let

n > m + 1

and

f: \{1, \dots, n\} \to \{1, \dots, m + 1\}

. If two inputs already map to

m + 1

we are done, so assume at most one does.

Case 1: if no input goes to

m + 1

, then

f

is not injective by

S(m)

Case 1: no input is sent to

m + 1

. Then

f

is a function into

\{1, \dots, m\}

from

n > m + 1 > m

points, and

S(m)

applies directly.

Case 2: if exactly one input

k

goes to

m + 1

, define

h

\{1, \dots, n-1\}

by skipping

k

Case 2: exactly one input

k

goes to

m + 1

. Delete

k

and close the gap in the numbering:

h(i) = f(i)

for

i \lt k

and

h(i) = f(i + 1)

for

i \ge k

. Then

h

maps

n - 1 > m

points into

\{1, \dots, m\}

f

is not injective, and

S(m + 1)

holds.

S(m)

says

h

is not injective:

h(i) = h(j)

for some

i \ne j

. These come from two different inputs of

f

with the same value, so

f

is not injective either.

If $A$ could be matched with both $\{1, \dots, n\}$ and $\{1, \dots, m\}$ with $n > m$ , composing one bijection with the inverse of the other would give an injective function $\{1, \dots, n\} \to \{1, \dots, m\}$ , which is impossible. So the size of a finite set is well defined.

Your answerThere are 12 months in a year. What is the smallest number of people that guarantees two of them have a birthday in the same month?

Using bijections to compare any two sets gives something that behaves like “equals”: it is reflexive (the identity), symmetric (inverses, by the theorem above) and transitive (compositions, by the proposition above). In the language of 0.4, “has the same cardinality as” is an equivalence relation, and a cardinality is a class of sets that can be matched with each other.

Countable and uncountable

Now the main question. The counting numbers $\mathbb N$ are the smallest infinite set we know. Which infinite sets can be matched with it?

Definition B

Countable

A set $A$ is countable if it is finite, or there is a bijection $f: \mathbb N \to A$ . Writing $a_n = f(n)$ , such a bijection is a listing $a_1, a_2, a_3, \dots$ of $A$ . A countable infinite set is also called countably infinite. (Some books, such as Abbott’s, reserve “countable” for the infinite case and say “at most countable” for the rest. CS 240 calls a bijection like this an enumeration.)

In one lineA set is countable if its elements can be put in a list, first, second, third, with every element appearing exactly once; finite sets count too.

Why it existsCountable sets are the 'discrete' ones. Everything a computer can store or enumerate is countable.

Definition B

Uncountable

A set is uncountable if it is not countable.

In one lineA set is uncountable if it is not countable: no list, however cleverly made, contains all its elements.

Why it existsIt shows that infinity comes in more than one size, and that some infinite sets are strictly bigger than the counting numbers.

How to prove a set is countable

You asked for this explicitly, and for the pieces that are easy to leave out. A listing $a_1, a_2, a_3, \dots$ of $A$ is a bijection $\mathbb N \to A$ , so you must show three things. The first is easy to forget, and the other two are the ones you named.

Every position gives an element of $A$ . The rule $n \mapsto a_n$ really produces members of $A$ (it is a function into $A$ ).
Every element of $A$ appears. For each $x \in A$ you can say at which position it shows up: the listing is onto. Without this, you have only listed part of $A$ .
No element appears twice. Different positions give different elements: the listing is one-to-one. Without this, you have listed things with repeats, which can make $A$ look bigger than it is.

Here is the template, as the lines you would write in a proof. Suppose you propose the rule $f(n) = \dots$ for the $n$ th element.

Define $f(n)$ for every $n \in \mathbb N$ .
It lands in $A$ . Check that $f(n) \in A$ for every $n$ .
It hits everything. Take an arbitrary $x \in A$ . Find the position $n$ with $f(n) = x$ (a formula in $x$ ), and check that this $n$ really is a counting number.
No repeats. Suppose $f(n) = f(m)$ . Show that $n = m$ .
Conclude. $f$ is a bijection $\mathbb N \to A$ , so $A$ is countable.

Steps 3 and 4 are the two halves of “bijection”: step 3 is onto, step 4 is one-to-one. Leaving out step 3 is the most common way to write a wrong proof. A list of $0, 1, 2, 3, \dots$ followed by $-1, -2, -3, \dots$ looks like a listing of $\mathbb Z$ , but the negative numbers would sit after the end of an infinite list, so no position is ever given to $-1$ . Step 3 fails for it, and the proof breaks there.

Quick checkA student 'lists'

\mathbb Z

0, 1, 2, 3, \dots

and then continues

-1, -2, -3, \dots

after all of those. What is wrong?

The “no repeats” condition often fails in natural attempts (as with fractions: $1/2$ and $2/4$ ), so the next theorem says exactly which of the conditions you can relax.

Theorem B

Three ways to show a set is countable

For a set $A$ , the following are equivalent for $A \ne \varnothing$ (and (a), (b) are equivalent for $A = \varnothing$ too):

(a) $A$ is countable;
(b) there is an injective function $A \to \mathbb N$ ;
(c) there is a surjective function $\mathbb N \to A$ .

In one line $A$ is countable iff there is an injection $A \to \mathbb N$ ; and a non-empty $A$ is countable iff there is a surjection $\mathbb N \to A$ (a list that may have repeats).

Why it is trueAn injection into the counting numbers lets you read off a position for each element, and a list with repeats can be cleaned by keeping the first appearance of each element.

ProofAbbott 1.5; Hammack 13.3

The idea: (a) implies (b) by inverting the listing. (b) implies (a) by sorting the used numbers in increasing order, which uses well-ordering. (c) implies (b) by sending each element to the first position where it appears. (a) implies (c) by listing, repeating the last element if finite.

(a) implies (b).

A

is finite with

n

elements, there is a bijection

h: \{1, \dots, n\} \to A

and its inverse maps

A

into

\mathbb N

. If

A

is countably infinite with listing

f

, then

f^{-1}: A \to \mathbb N

. Inverses of bijections are bijections, hence injective.

(b) implies (a). Set

B = \varphi(A)

Let

\varphi: A \to \mathbb N

be injective. If

A

is finite we are done, so assume

A

is infinite. Let

B = \varphi(A) \subseteq \mathbb N

. Then

\varphi: A \to B

is a bijection (injective, and onto

B

by definition), so

B

is infinite too.

Sort

B

by repeatedly taking the least element not yet taken:

b_1, b_2, b_3, \dots

Well-ordering: every non-empty set of counting numbers has a least element. Let

b_1

be the least element of

B

. Having chosen

b_1, \dots, b_k

, the set

B \setminus \{b_1, \dots, b_k\}

is non-empty because

B

is infinite; let

b_{k+1}

be its least element.

The sequence is strictly increasing. Define

g(k) = b_k

. Then

g

is injective, since different positions have different values.

b_{k+1}

lies in

B \setminus \{b_1, \dots, b_{k-1}\}

, where

b_k

was the least element, so

b_k \le b_{k+1}

. They are different, so

b_k \lt b_{k+1}

Also

b_k \ge k

for every

k

Since

b_1 \ge 1

and each

b_{k+1} \gt b_k

is at least one more, induction gives

b_k \ge k

g

is surjective onto

B

: no element of

B

is skipped.

Suppose

m \in B

is never chosen. Then for every

k

m \in B \setminus \{b_1, \dots, b_k\}

, so the least element

b_{k+1}

of that set satisfies

b_{k+1} \le m

. Taking

k = m

gives

b_{m+1} \le m

, but

b_{m+1} \ge m + 1

. This is a contradiction, so every

m \in B

equals some

b_k

\varphi^{-1} \circ g: \mathbb N \to A

is a bijection, and

A

is countable.

Composition of bijections is a bijection, and inverses are bijections.

s: \mathbb N \to A

be onto. For

a \in A

the set

\{n : s(n) = a\}

is non-empty, so by well-ordering it has a least element. Define

\varphi(a)

to be that least element, so

s(\varphi(a)) = a

\varphi

is injective.

\varphi(a) = \varphi(a')

, then

a = s(\varphi(a)) = s(\varphi(a')) = a'

Every non-empty countable set has a surjection from

\mathbb N

(a) implies (c), for

A \ne \varnothing

. If

A

is countably infinite, the listing itself is onto. If

A = \{a_1, \dots, a_n\}

, define

s(k) = a_k

for

k \le n

and

s(k) = a_n

for

k \gt n

In practice this means: if listing without repeats is awkward, you may list with repeats, but you may never leave an element out.

Quick checkYou build a list

a_1, a_2, a_3, \dots

of a non-empty set

A

. Every element of

A

appears at least once, and some appear several times. What can you conclude?

Three consequences are used constantly.

Corollary B

Closure properties of countable sets

If $B$ is countable and $A \subseteq B$ , then $A$ is countable.
If $A$ is countable and $g: A \to C$ is onto, then $C$ is countable.
If $A$ and $B$ are countable, then so is $A \times B$ (provided $\mathbb N \times \mathbb N$ is countable, proved below).

In one lineSubsets of countable sets are countable; the image of a countable set under any function is countable; a product of two countable sets is countable.

Why it is trueEach one follows by composing with the injections and surjections of the previous theorem.

Proofstandard

The idea: Each part builds the required injection or surjection by composing functions.

(1) The restriction of

\psi

A

is an injection

A \to \mathbb N

, so

A

is countable by (b) implies (a).

By (a) implies (b), there is an injection

\psi: B \to \mathbb N

. Restricting an injection to a smaller domain keeps it injective.

(2)

g \circ s: \mathbb N \to C

is onto, so

C

is countable by (c) implies (a).

A = \varnothing

then

C = \varnothing

, which is finite. Otherwise (a) implies (c) gives a surjection

s: \mathbb N \to A

, and a composition of surjections is a surjection.

(3) Compose that map with an injection

\mathbb N \times \mathbb N \to \mathbb N

(the theorem below).

Take injections

\varphi: A \to \mathbb N

and

\psi: B \to \mathbb N

. The map

(a, b) \mapsto (\varphi(a), \psi(b))

is injective into

\mathbb N \times \mathbb N

, since equal pairs have equal coordinates, and each coordinate map is injective.

A \times B

is countable by (b) implies (a).

The composite of injections is injective (the proposition above), so

A \times B

injects into

\mathbb N

The integers are countable

Theorem B

The integers are countable

The function $f: \mathbb N \to \mathbb Z$ defined by $f(n) = n/2$ for even $n$ and $f(n) = -(n - 1)/2$ for odd $n$ is a bijection.

In one line $\mathbb Z$ can be listed as $0, 1, -1, 2, -2, 3, -3, \dots$ with every integer exactly once.

Why it is trueAlternate between non-positive and positive integers, so that going outward on both sides still reaches each integer at a definite position.

The first values are in the table.

Position $n$	1	2	3	4	5	6	7	8	9
$f(n)$	0	1	-1	2	-2	3	-3	4	-4

ProofCS 240; Abbott 1.5

The idea: Check the three things: f lands in the integers, every integer is hit (find its position), and no integer is hit twice. Positive integers sit at the even positions, and zero and negatives at the odd positions.

f

takes integer values.

Both formulas give integers:

n/2

is an integer for even

n

, and

(n-1)/2

is an integer for odd

n

. So

f

is a function

\mathbb N \to \mathbb Z

(property 1).

Let

z \in \mathbb Z

. If

z \ge 1

, then

f(2z) = z

Onto, positive case (property 2). If

z \ge 1

, take

n = 2z

, which is even and in

\mathbb N

. Then

f(n) = 2z/2 = z

z \le 0

, then

f(1 - 2z) = z

Onto, non-positive case. If

z \le 0

, take

n = 1 - 2z

, which is odd and at least

1

, so in

\mathbb N

. Then

f(n) = -(1 - 2z - 1)/2 = -(-2z)/2 = z

Suppose

f(n) = f(m)

. Then

n

and

m

are both even or both odd.

One-to-one, property 3. Suppose

f(n) = f(m)

. Even inputs give positive integers (

n/2 \ge 1

) and odd inputs give integers at most

0

(

-(n-1)/2 \le 0

). So

n

and

m

cannot have different parity.

In either case

n = m

If both are even,

n/2 = m/2

, so

n = m

. If both are odd,

-(n-1)/2 = -(m-1)/2

, so

n = m

f

is a bijection and

\mathbb Z

is countable.

A bijection

\mathbb N \to \mathbb Z

is exactly a listing of

\mathbb Z

in which every integer appears once.

Your answerUsing the listing of

\mathbb Z

above (

f(n) = n/2

for even

n

f(n) = -(n-1)/2

for odd

n

), at which position

n

does the integer

-7

appear?

Proof workshopRebuild the proof that the integers are countable

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

A common worry is that the list “uses up” a whole infinite supply of positives before it reaches any negatives. It does not: the list is an alternating weave, so the positive integer $z$ appears at position $2z$ , and the negative $-k$ appears at position $2k + 1$ . Each integer has a finite position.

The pairs of counting numbers are countable

The next step is the one that surprises people: a whole plane of pairs fits into a single list.

Theorem B

The counting-number pairs are countable

The function $P: \mathbb N \times \mathbb N \to \mathbb N$ , $P(m, n) = \tfrac{(m + n - 2)(m + n - 1)}{2} + m$ , is a bijection.

In one line $\mathbb N \times \mathbb N$ can be listed diagonal by diagonal, and the position of $(m, n)$ is $P(m, n) = \tfrac{(m + n - 2)(m + n - 1)}{2} + m$ .

Why it is trueEach diagonal $m + n = s$ is finite, so listing diagonals one after another reaches every pair after finitely many steps.

Picture the pairs as a grid. Row $m$ and column $n$ hold the pair $(m, n)$ . The diagonal where $m + n = s$ holds exactly $s - 1$ pairs: $(1, s - 1), (2, s - 2), \dots, (s - 1, 1)$ . List the diagonals in order of $s = 2, 3, 4, \dots$ and each diagonal from top to bottom.

Proofstandard

The idea: The pairs with m + n = s fill positions from T(s-2) + 1 to T(s-1), where T(j) = j(j+1)/2 counts the pairs on the diagonals before. Show each position lies in exactly one such block and, inside it, picks out exactly one pair.

P(m, n) = T(s - 2) + m

where

s = m + n

Definition: the triangular number

T(j) = 1 + 2 + \dots + j = j(j+1)/2

, with

T(0) = 0

. The diagonals

s = 2, \dots, s - 1

hold

1 + 2 + \dots + (s - 2) = T(s - 2)

pairs.

So the pairs of diagonal

s

land in the block of positions

T(s-2) + 1, \dots, T(s-1)

, which has

s - 1

places.

Property 1:

P

lands in

\mathbb N

. For a pair on diagonal

s

, we have

1 \le m \le s - 1

, so

T(s-2) \lt P(m,n) \le T(s-2) + (s - 1) = T(s-1)

Every

k \in \mathbb N

lies in exactly one block, for exactly one

s

The numbers

T(0) \lt T(1) \lt T(2) \lt \dots

are strictly increasing and unbounded (

T(j) \ge j

), so the blocks for

s = 2, 3, 4, \dots

are disjoint and together cover every counting number.

Every position

k

is the position of some pair.

Onto (property 2). Given

k

, find the

s

with

T(s-2) \lt k \le T(s-1)

. Put

m = k - T(s-2)

, which satisfies

1 \le m \le s - 1

, and

n = s - m \ge 1

. Then

m, n \in \mathbb N

and

P(m, n) = T(s-2) + m = k

No position is shared by two pairs.

One-to-one (property 3). If

P(m, n) = P(m', n') = k

, then

k

lies in a single block, so

s = m + n

equals

s' = m' + n'

. Then

m = k - T(s-2) = m'

, and

n = s - m = n'

So the whole infinite grid is one list: $(1,1), (1,2), (2,1), (1,3), (2,2), (3,1), \dots$ Every pair is reached after finitely many steps, because it sits on a finite diagonal. (An alternative injection is $(m, n) \mapsto 2^m 3^n$ , which is injective by unique factorization into primes, proved in 0.5.)

Your answerUse

P(m, n) = \tfrac{(m + n - 2)(m + n - 1)}{2} + m

. At which position does the pair

(4, 3)

appear in the diagonal listing?

Your answerHow many pairs

(m, n)

of counting numbers have

m + n \le 10

The rationals are countable

Theorem B

The rationals are countable

The set $\mathbb Q$ of rational numbers is countable.

In one line $\mathbb Q$ can be listed, even though between any two rationals there are infinitely many more.

Why it is trueEvery rational is a fraction of integers, and pairs of integers are countable. The repeats like 1/2 and 2/4 are removed by keeping only the first appearance.

ProofAbbott 1.5; CS 240

The idea: Do not try to list the rationals in order of size; there is no 'next' one. Instead, list the fractions (all pairs of integers), which are countable, and then cover each rational by at least one fraction. A list with repeats is enough, by the theorem on three ways.

\mathbb Z \times \mathbb N

is countable.

\mathbb Z

is countable by the integers theorem, and

\mathbb N

is countable (the identity is a listing). A product of countable sets is countable.

Define

q: \mathbb Z \times \mathbb N \to \mathbb Q

q(z, b) = z / b

. It is onto.

By the definition of

\mathbb Q

, every rational is

z/b

for some

z \in \mathbb Z

and

b \in \mathbb N

. So the function

q(z, b) = z/b

is onto

\mathbb Q

. It is not one-to-one:

q(1, 2) = q(2, 4)

\mathbb Q

is countable.

Closure property 2: the image of a countable set under a function that is onto its target is countable. The repeats do not matter, because the proof of (c) implies (b) keeps only the first position of each rational.

What does the resulting list look like, and why does each rational appear exactly once? The proof says: walk through the pairs in the diagonal order and write $a/b$ for each pair, skipping a fraction if it equals one already written. Do that for positive fractions and put $-q$ after each new $q$ . Here is the start of the list.

Every rational $q = z/b$ is reached: its fraction $(|z|, b)$ sits at a finite position in the diagonal order, so it is written at that position or earlier. No rational is written twice, because a rational is written only if it is not already on the list.

Quick checkBetween any two rational numbers there is another rational (for example their average). So the rationals are 'dense', and there is no next one. Does that make

\mathbb Q

uncountable?

The real numbers are not countable

We now meet a set that cannot be listed at all. Cantor’s idea is to show that any list that claims to contain every number is lying, by writing down a number that the list misses. The number is built from the list itself.

First two school facts that we use about decimal expansions. We take them as known; Unit 1 builds the real numbers carefully enough to prove them.

Every real $x$ with $0 \lt x \lt 1$ can be written as an infinite decimal $0.d_1 d_2 d_3 \dots$ with digits $d_i \in \{0, 1, \dots, 9\}$ .
A number has more than one such expansion only when one of them ends in all zeros and the other in all nines, like $0.5000\dots = 0.4999\dots$ . So an expansion that does not end in all zeros or all nines is the only expansion of its number.

Theorem B Cantor 1891

The real numbers are uncountable

The set $(0, 1) = \{x \in \mathbb R : 0 \lt x \lt 1\}$ is uncountable. Consequently $\mathbb R$ is uncountable.

In one lineThe interval $(0, 1)$ , and so the set $\mathbb R$ of all real numbers, cannot be listed.

Why it is trueGiven any list, build a number that differs from the $n$ th number of the list in its $n$ th digit. It is in $(0, 1)$ but is not on the list.

Here is the idea on a concrete list. Suppose someone claims that this list contains every number in $(0, 1)$ , and the digits shown are the start of each expansion.

Why digits $4$ and $5$ ? Any rule “make the digit different” works, as long as the new digits are never $0$ or $9$ . That avoids the double-expansion trap ( $0.5000\dots = 0.4999\dots$ ), which could otherwise make $y$ equal to some $x_n$ in value while differing in digits.

ProofCantor 1891; Abbott Thm 1.6.1

The idea: Assume for contradiction that (0, 1) can be listed. Write each listed number as a decimal. Build y by changing the n-th digit of the n-th number to something else (never 0 or 9). Then y is in (0, 1) but differs from every listed number, which contradicts the list being complete.

Suppose

(0, 1)

is countable. Then there are numbers

x_1, x_2, x_3, \dots

such that every number in

(0, 1)

equals some

x_n

Proof by contradiction (0.2): assume the statement is false.

(0, 1)

is infinite, so countable means there is a bijection

\mathbb N \to (0, 1)

. We only use that it is onto.

For each

n

fix a decimal expansion

x_n = 0.d_{n1} d_{n2} d_{n3} \dots

Here

d_{nk}

is the

k

th digit of

x_n

School fact 1: every number in

(0, 1)

has a decimal expansion. If a number has two, pick either one and fix the choice.

Define

y = 0.e_1 e_2 e_3 \dots

e_n = 5

d_{nn} \ne 5

, and

e_n = 4

d_{nn} = 5

This is the diagonal: for each

n

, look at the digit

d_{nn}

in position

n

x_n

, and choose a digit of

y

that disagrees with it. The choices

4

and

5

are never

0

9

y \in (0, 1)

All digits of

y

are

4

5

, so

0.444\dots \le y \le 0.555\dots

, which is strictly between

0

and

1

y = x_n

for some

n

The assumption: every number of

(0, 1)

is on the list.

Then the digits of

x_n

are the digits

e_1, e_2, e_3, \dots

y

School fact 2: the digits of

y

never end in all zeros or all nines, so

0.e_1 e_2 \dots

is the only expansion of

y

. The chosen expansion of

x_n

is also an expansion of

y = x_n

, so the two expansions are identical.

d_{nn} = e_n

Compare position

n

on both sides: the

n

th digit of

x_n

d_{nn}

, and the

n

th digit of

y

e_n

This contradicts the definition of

e_n

. So

(0, 1)

is not countable.

But by construction

e_n \ne d_{nn}

for every

n

. We have a statement and its negation, a contradiction.

Hence

\mathbb R

is uncountable too: otherwise

(0,1) \subseteq \mathbb R

would be countable.

Closure property 1: a subset of a countable set is countable. If

\mathbb R

were countable, its subset

(0, 1)

would be countable.

Proof workshopRebuild Cantor's diagonal argument

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

Watch out· 'Just add y to the list' does not fix anything

The usual objection is: “fine, $y$ was missing, so put it at the top and the list is complete.” It is not, because the argument works for every list. Give me the new list and I run the same construction on it and build a new missing number. The point is not that one number is missing. It is that no list can ever be complete.

A preview· Preview: why the real numbers are 'more' than the rationals

$\mathbb Q$ is countable, and $\mathbb R$ is not, so almost all real numbers are irrational, in a strong sense that measure theory later makes precise. What separates them is completeness: the real line has no gaps, while $\mathbb Q$ is full of holes (for example $\sqrt 2$ , see 0.2). Cantor’s first proof, in 1874, used completeness directly. Chapter 1.1 states completeness and uses it to prove that sequences that should converge really do.

Where this came from· Cantor, 1874 and 1891

Georg Cantor’s first proof that the real numbers cannot be listed appeared in 1874, in a paper whose title announced something else: a property of the collection of all real algebraic numbers (roots of polynomials with integer coefficients). He showed that these algebraic numbers can be listed, and that the reals cannot, which proved that there are non-algebraic (“transcendental”) numbers without exhibiting one. That proof used the completeness of the real line. In 1891 he published the diagonal argument you just followed, which works with infinite sequences and also gives the general fact that every set has strictly more subsets than elements. What he was trying to settle was whether all infinite sets are the same size. The answer, no, changed what mathematicians meant by infinity.

Quick checkIn the diagonal argument, why can we not build

y

by 'adding 1 to the diagonal digit'?

Examples of countability proofs

The recipe from the previous section applies to any new set. First find an injection into a set you already know is countable (or a surjection from one), then use the theorem on three ways. Here are three sets of the kind the problems ask for: one by a listing, one by weaving two lists together, one by an injection.

Worked example CS 240

Prove that the set

E = \{2, 4, 6, 8, \dots\}

of positive even integers is countable.

Solution. The plan: write down a listing and check the three properties.

Name the listing. Let $f(n) = 2n$ . The list is $2, 4, 6, \dots$ This is the natural enumeration, a rule that gives the element in each position.
Check it lands in $E$ . For each $n \in \mathbb N$ , $2n$ is positive and equals $2 \cdot n$ with $n$ an integer, so it is a positive even integer. Property 1: every position gives an element of the set.
Check it hits everything. Let $k \in E$ . Then $k = 2j$ for some integer $j$ , and $j = k/2 > 0$ , so $j \in \mathbb N$ and $f(j) = k$ . The element $k$ sits at position $k/2$ . Property 2: for each element we can name the position, and the position is a legal one.
Check there are no repeats. If $f(n) = f(m)$ then $2n = 2m$ , so $n = m$ . Property 3: different positions give different elements.

Answer. $f$ is a bijection $\mathbb N \to E$ , so $E$ is countable. Note that $E \subsetneq \mathbb N$ and the two sets still match perfectly.

Worked example Hammack 13.3

Prove that the union

A \cup B

of two countable sets is countable.

Solution. The plan: use surjections from $\mathbb N$ and weave the two lists together.

Get two lists. If one of $A, B$ is empty the claim is trivial. Otherwise the theorem on three ways gives surjections $s: \mathbb N \to A$ and $t: \mathbb N \to B$ . A surjection is a list that is allowed to repeat, which is all we need.
Weave them. Define $u(n) = s((n + 1)/2)$ if $n$ is odd and $u(n) = t(n/2)$ if $n$ is even. The odd positions list $A$ and the even positions list $B$ , in the same alternating pattern that listed $\mathbb Z$ .
Check $u$ is onto $A \cup B$ . An element $a \in A$ equals $s(k)$ for some $k$ , and then $a = u(2k - 1)$ . An element $b \in B$ equals $t(k)$ for some $k$ , and then $b = u(2k)$ . Every element of the union is in $A$ or in $B$ , and each is reached.
Conclude. $u$ is a surjection from $\mathbb N$ onto $A \cup B$ , so $A \cup B$ is countable. Part (c) implies (a) of the theorem. We did not need to check for repeats, because a repeat only matters for a bijection.

Answer. $A \cup B$ is countable.

Worked example

Prove that the set

W

of all finite strings of

0

s and

1

s (including the empty string) is countable.

Solution. The plan: this time use an injection into $\mathbb N$ and conclude by the theorem on three ways.

Define the map. For a string $s$ , let $\varphi(s)$ be the counting number whose binary (base 2) notation is the digit $1$ followed by $s$ . For example $\varphi(\text{empty}) = 1_2 = 1$ , $\varphi(0) = 10_2 = 2$ , $\varphi(1) = 11_2 = 3$ , $\varphi(00) = 100_2 = 4$ . Putting a leading $1$ in front stops leading zeros of $s$ from being lost, so strings like $0$ and $00$ get different numbers.
It lands in $\mathbb N$ . Every binary notation starting with $1$ is a counting number. Property 1: the rule produces members of the target.
It is injective. Suppose $\varphi(s) = \varphi(t)$ . Then the binary notations " $1s$ " and " $1t$ " are notations of the same number, and a number has only one binary notation that starts with $1$ . So $1s = 1t$ as strings, hence $s = t$ . The template for injective: equal outputs force equal inputs. Uniqueness of binary notation is the fact used.
Conclude. An injection $W \to \mathbb N$ exists, so $W$ is countable. Part (b) implies (a) of the theorem. With an injection we do not have to show that every counting number is used; the theorem sorts out the positions for us.

Answer. $W$ is countable. The same trick shows that the set of all finite programs, written as strings over a fixed alphabet, is countable.

Where it is used

Used inside maths· Inside maths: sequences, probability, and what 'almost all' means

A sequence is a function $\mathbb N \to \mathbb R$ , so the whole of Unit 1 is the study of functions defined on a countable set. In probability (MATH 431) the axioms ask for additivity over countably many disjoint events, and “choose a real number uniformly in $(0, 1)$ ” is only possible because the reals are uncountable: each single number must have probability $0$ . Later in analysis you will see that every countable set of reals has total length $0$ , so the rationals, though dense, take up no room on the line.

Used in the real world· Computer science: what a program can and cannot name

A program is a finite string of characters, and finite strings over a fixed alphabet can be listed (all strings of length 1 first, then length 2, and so on, each length being a finite list). So there are only countably many programs, but there are uncountably many functions from $\mathbb N$ to $\{0, 1\}$ (the same diagonal argument; see the stretch problem). Hence most functions are computed by no program at all, which is the starting point of Turing’s 1936 paper on what computers cannot do. The same argument says that only countably many real numbers can ever be named by a formula or computed to any precision.

The pigeonhole principle is the practical cousin: a checksum with 16 bits has $2^{16} = 65\,536$ possible values, so among $65\,537$ different files two must have the same checksum. No injective function from a large set to a small set exists, however clever the hash. A SQL query that joins a table of 1000 customers with a table of 50 products, with no condition, produces their Cartesian product: $1000 \times 50 = 50\,000$ rows. The condition in a WHERE clause then selects a subset of it (a relation, see 0.4).

Traps

Watch out· Countable does not mean finite, and uncountable does not mean 'big'

“Countable” means “can be put in an infinite list” (or is finite). The integers are infinite and countable. “Uncountable” is the statement that no list can ever be complete. Nobody is asking you to count to the end.

Watch out· A list with repeats still proves countability, but a list with gaps does not

When a listing for $\mathbb Q$ repeats $1/2$ and $2/4$ , you may leave the repeats in: a surjection from $\mathbb N$ is enough. What you may not do is skip elements. Whenever you propose a listing, say at which position an arbitrary element of the set appears.

Watch out· Complement flips union and intersection

$(A \cup B)^c = A^c \cap B^c$ , never $A^c \cup B^c$ . When you push a complement inside brackets, every union becomes an intersection and every intersection becomes a union, just as ‘or’ becomes ‘and’ when you negate.

Watch out· Subset symbols and the empty set

CS 240 writes $\subseteq$ for subset and $\subset$ for proper subset. Many textbooks write $\subset$ for the plain subset, so read the book’s convention first. And $\varnothing \ne \{\varnothing\}$ : the empty set has no elements, while $\{\varnothing\}$ has one, namely the empty set. Both of these are subsets of $\{\varnothing\}$ .

Watch out· A function must be defined everywhere, once

A rule is a function only if every input in the domain has exactly one output in the codomain. $f(x) = 1/x$ is not a function on $\mathbb R$ (no output at $0$ ), and " $\pm\sqrt{x}$ " gives two outputs. Always say the domain and codomain, because injective and surjective depend on them.

Watch out· Injective is 'f(x) = f(y) implies x = y', not the other way round

The statement ” $x = y$ implies $f(x) = f(y)$ ” is true for every function; it is just what “function” means. Injectivity is the converse. This is the converse trap of chapter 0.1, in a new place.

Problems

check

Let $A = \{1, 2, 3\}$ and $B = \{2, 3, 4, 5\}$ in $U = \{1, \dots, 6\}$ . List $A \cup B$ , $A \cap B$ , $A \setminus B$ , $B^c$ , and say how many elements $A \times B$ has.

Solution

$A \cup B = \{1, 2, 3, 4, 5\}$ , $A \cap B = \{2, 3\}$ , $A \setminus B = \{1\}$ , $B^c = \{1, 6\}$ . $A \times B$ has $3 \cdot 4 = 12$ elements.

check

Write, using the rules for ‘not in’, exactly what $x \notin (A \cup B) \cap C$ means (in words, with “and” and “or”).

Solution

$x \in (A \cup B) \cap C$ means $(x \in A \text{ or } x \in B)$ and $x \in C$ . Its negation is: ( $x \notin A$ and $x \notin B$ ) or $x \notin C$ . The ‘and’ became ‘or’ (rule 1) and the ‘or’ became ‘and’ (rule 2).

check

Is $f: \mathbb R \to \mathbb R$ , $f(x) = x^3$ injective? Surjective? What about $f: \mathbb R \to \mathbb R$ , $f(x) = x^3 - x$ ?

Solution

$x^3$ : injective, since $x^3 = y^3$ implies $x = y$ (real cube roots are unique), and surjective, since every $b$ is $\sqrt[3]{b}^3$ . So bijective. $x^3 - x$ : surjective (a continuous function going from $-\infty$ to $+\infty$ takes every value, by the intermediate value theorem of Unit 1), but not injective: $f(0) = f(1) = f(-1) = 0$ .

checkCS 240

At which position does the integer $-5$ appear in the listing of $\mathbb Z$ above, and which integer is at position $50$ ?

Solution

$-5$ is at position $1 - 2(-5) = 11$ (check: $f(11) = -(11 - 1)/2 = -5$ ). Position $50$ is even, so the integer is $50/2 = 25$ .

useHammack 8.3

Prove $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ by element-chasing, justifying each line.

Solution

Let $x$ be arbitrary. $x \in A \cap (B \cup C)$ iff $x \in A$ and ( $x \in B$ or $x \in C$ ) (definitions of $\cap$ and $\cup$ ) iff ( $x \in A$ and $x \in B$ ) or ( $x \in A$ and $x \in C$ ) (distributive law of logic, checkable by a truth table) iff $x \in A \cap B$ or $x \in A \cap C$ (definition of $\cap$ ) iff $x \in (A \cap B) \cup (A \cap C)$ (definition of $\cup$ ). Every line is an if-and-only-if, so the sets are equal.

use

Find a counterexample to " $(A \setminus B) \cup B = A$ " for all sets $A, B$ , and then say what extra condition makes it true.

Solution

Take $A = \{1, 2\}$ and $B = \{2, 3\}$ . Then $A \setminus B = \{1\}$ and $(A \setminus B) \cup B = \{1, 2, 3\} \ne A$ . In general $x \in (A \setminus B) \cup B$ means ( $x \in A$ and $x \notin B$ ) or $x \in B$ , which is the same as $x \in A$ or $x \in B$ (if $x \in B$ the second part holds, and if $x \notin B$ the first part reduces to $x \in A$ ). So the set equals $A \cup B$ , which is $A$ exactly when $B \subseteq A$ .

use

Prove that $f: \mathbb R \setminus \{1\} \to \mathbb R \setminus \{2\}$ , $f(x) = \dfrac{2x}{x - 1}$ is a bijection, and find its inverse.

Solution

Injective: if $\frac{2x}{x-1} = \frac{2y}{y-1}$ , cross-multiplying gives $2x(y - 1) = 2y(x - 1)$ , so $-2x = -2y$ and $x = y$ . Surjective: given $b \ne 2$ , solve $\frac{2a}{a - 1} = b$ : $2a = ab - b$ , so $a(2 - b) = -b$ , so $a = \frac{b}{b - 2}$ . This is defined because $b \ne 2$ , and $a \ne 1$ since $\frac{b}{b-2} = 1$ would need $b = b - 2$ . Then $f(a) = b$ . The inverse is $f^{-1}(b) = \frac{b}{b - 2}$ , that is $f^{-1}(x) = \frac{x}{x - 2}$ for $x \ne 2$ . Check: $f(2) = 4$ and $f^{-1}(4) = 4/(4-2) = 2$ .

use

Prove that the set $O$ of odd positive integers is countable, and that $\mathbb Z \times \mathbb Z$ is countable.

Solution

$O$ : $f(n) = 2n - 1$ is a bijection $\mathbb N \to O$ . It lands in $O$ ( $2n - 1$ is odd and positive). It is onto: if $k = 2j - 1$ is odd and positive, then $j = (k + 1)/2 \in \mathbb N$ and $f(j) = k$ . It is one-to-one: $2n - 1 = 2m - 1$ implies $n = m$ . $\mathbb Z \times \mathbb Z$ : $\mathbb Z$ is countable, and a product of countable sets is countable (closure property 3, which composes an injection into $\mathbb N \times \mathbb N$ with the diagonal bijection $P$ ).

proveHammack 12.2

Prove: if $f: A \to B$ and $g: B \to C$ and $g \circ f$ is surjective, then $g$ is surjective. Is $f$ necessarily surjective?

Solution

Let $c \in C$ . Since $g \circ f$ is surjective, there is $a \in A$ with $g(f(a)) = c$ . Then $b = f(a) \in B$ satisfies $g(b) = c$ . So $g$ is surjective. $f$ need not be: let $A = \{1\}$ , $B = \{1, 2\}$ , $C = \{1\}$ , $f(1) = 1$ and $g(1) = g(2) = 1$ . Then $g \circ f$ is onto $C$ , but $f$ misses $2$ .

prove

Prove that if $f: A \to B$ is injective and $A$ is infinite, then $f(A)$ is infinite. Separately, show: if $A$ is uncountable and $A \subseteq B$ , then $B$ is uncountable.

Solution

Suppose $f(A)$ were finite with a bijection $h: \{1, \dots, n\} \to f(A)$ . Since $f: A \to f(A)$ is a bijection (injective and onto its range), $h^{-1} \circ f: A \to \{1, \dots, n\}$ is a bijection, so $A$ would be finite, a contradiction. For the second claim, suppose $B$ were countable. Then its subset $A$ would be countable (closure property 1), which contradicts $A$ being uncountable. So $B$ is uncountable. This is the step used to pass from $(0,1)$ to $\mathbb R$ .

proveAbbott 1.5

Prove that the set of all finite subsets of $\mathbb N$ is countable.

Solution

Let $\mathcal F$ be the family of finite subsets of $\mathbb N$ . Define $\varphi: \mathcal F \to \mathbb N$ by $\varphi(S) = 1 + \sum_{k \in S} 2^{k}$ (the empty sum is $0$ , so $\varphi(\varnothing) = 1$ ). The number $\sum_{k \in S} 2^k$ has binary digits equal to $1$ exactly at the positions in $S$ . Binary expansions of whole numbers are unique, so different sets $S$ give different numbers, and $\varphi$ is injective. By the theorem on three ways ((b) implies (a)), $\mathcal F$ is countable.

prove

In Cantor’s argument, a student changes the rule to “let $e_n = 1$ if $d_{nn} \ne 1$ and $e_n = 2$ if $d_{nn} = 1$ ”. Is the proof still correct? What if the rule is “let $e_n = 0$ if $d_{nn} \ne 0$ , and $e_n = 1$ if $d_{nn} = 0$ ”?

Solution

The first rule works, for the same reason as $4, 5$ : the digits of $y$ are $1$ and $2$ , never $0$ or $9$ , so $y$ has a unique expansion and differs from each $x_n$ in digit $n$ . The second rule can fail. It uses the digit $0$ , which is dangerous: for instance $y = 0.1000\dots$ equals $0.0999\dots$ as a number, so $y$ could be a listed number $x_n$ whose chosen expansion is $0.0999\dots$ , and then comparing digits would not show $y \ne x_n$ . If every diagonal digit is nonzero, the rule even gives $y = 0.000\dots = 0$ , which is not in $(0, 1)$ . That is why we avoid $0$ and $9$ .

stretchCantor 1891

Prove Cantor’s theorem: for every set $A$ there is no surjection $f: A \to \mathcal P(A)$ , where $\mathcal P(A)$ is the set of all subsets of $A$ . Deduce that $\mathcal P(\mathbb N)$ is uncountable.

Solution

Suppose $f: A \to \mathcal P(A)$ is onto. Let $D = \{a \in A : a \notin f(a)\}$ . Then $D \subseteq A$ so $D \in \mathcal P(A)$ , so $D = f(a_0)$ for some $a_0 \in A$ . Is $a_0 \in D$ ? By the definition of $D$ , $a_0 \in D$ iff $a_0 \notin f(a_0) = D$ . This says $a_0 \in D$ iff $a_0 \notin D$ , a contradiction. So no surjection exists. (This is the diagonal argument: the set $D$ disagrees with $f(a)$ about the element $a$ .) If $\mathcal P(\mathbb N)$ were countable, then since it is non-empty there would be a surjection $\mathbb N \to \mathcal P(\mathbb N)$ by part (c) of the theorem on three ways, which was just ruled out. So $\mathcal P(\mathbb N)$ is uncountable. Applying the theorem again and again gives infinitely many different sizes of infinity.

stretch

Explain why the set of all real numbers that you can define in English with a sentence of at most 1000 characters is countable (in fact finite), and why that does not contradict $\mathbb R$ being uncountable. What does it say about almost every real number?

Solution

A sentence of at most 1000 characters from an alphabet of, say, $N$ symbols is one of at most $N + N^2 + \dots + N^{1000}$ strings, a finite number. Each defines at most one real number, so at most finitely many reals are definable this way. Allowing sentences of any finite length, the set of all finite strings is countable (list by length, then by dictionary order inside each length, which is a finite list), so at most countably many reals are definable. There is no contradiction: $\mathbb R$ is uncountable, so the definable reals form a tiny part of it, and almost every real number has no finite description at all.

Summary

A set is described by its elements; proofs about sets go through “let $x$ be arbitrary” and the definitions. $A = B$ is shown by double inclusion.
Membership in $A \cup B$ , $A \cap B$ , $A^c$ is a logical sentence, so the rules for ‘not in’ are the negation rules of 0.1: not-in-an-intersection is “missing from one”, not-in-a-union is “missing from both”.
De Morgan for sets is not a given fact: it is proved by a chain of if-and-only-ifs from the definitions.
A function gives each input exactly one output. Injective means different inputs give different outputs, surjective means every target is hit, and bijective means both, which is exactly “has an inverse”.
Two sets have the same size if a bijection joins them. A listing of a set is a bijection from $\mathbb N$ ; to prove one you show that it lands in the set, hits every element, and repeats none. An injection into $\mathbb N$ , or a surjection from it, is enough.
$\mathbb Z$ , $\mathbb N \times \mathbb N$ and $\mathbb Q$ are all countable. The rationals are listed by walking the grid of fractions diagonally and skipping repeats.
Cantor’s diagonal argument shows $(0, 1)$ , and so $\mathbb R$ , is uncountable: given any list, change the $n$ th digit of the $n$ th number and get a number that is not on it.
Consequence: only countably many reals can ever be named or computed, so most reals cannot. This is the seed for completeness in chapter 1.1.

Watch and read

The same ideas explained by someone else. Use these when an explanation here does not land.

0.3 Sets, functions, and counting infinity

The picture

The idea, in words

Definitions and theorems

Sets

Set

Subset

Double inclusion

Union, intersection, complement

Union

Intersection

Complement

The rules for ‘not in’

Rules for not in

De Morgan’s laws for sets

De Morgan's laws for sets

Functions

Function

Injective

Surjective

Bijective

Composition of injections and surjections

Bijections and inverses

Size without counting

Finite set

Pigeonhole principle

Countable and uncountable

Countable

Uncountable

How to prove a set is countable

Three ways to show a set is countable

Closure properties of countable sets

The integers are countable

The integers are countable

The pairs of counting numbers are countable

The counting-number pairs are countable

The rationals are countable

The rationals are countable

The real numbers are not countable

The real numbers are uncountable

Examples of countability proofs

Where it is used

Traps

Problems

Summary

Watch and read

Where this sits

Comes from

Leads to

Same idea elsewhere