---
title: "Logic, Sets and Maps"
book: "University Mathematics — Year 1"
subject: math
language: en
chapter: 1
exercises: 12
source: https://one-course.com/books/math/3/en/chapter/1-logic-sets-and-maps
---

# Chapter 1 — Logic, Sets and Maps

Up to now, proofs have been carried out with an informal but honest idea of what “proving” means. This first chapter of undergraduate mathematics makes the rules of the game explicit: what a mathematical [statement](#def-b1-logic-statement) is, how the connectives and quantifiers combine [statements](#def-b1-logic-statement), which moves are legal in a proof — and then builds, on this footing, the two universal languages of mathematics: [sets](#def-b1-logic-sets) and [maps](#def-b1-logic-map).

## 1.1 Statements and connectives

**Definition 1.1 (Statement, connectives).**

A *statement* (or *proposition*) is a sentence which is either true (T) or false (F) — exactly one of the two. From statements $P$ and $Q$ one forms:

- the *negation* $\lnot P$ (“not $P$ ”), true exactly when $P$ is false;
- the *conjunction* $P \land Q$ (“ $P$ and $Q$ ”), true exactly when both are true;
- the *disjunction* $P \lor Q$ (“ $P$ or $Q$ ”), true exactly when at least one is true (this “or” is inclusive);
- the *implication* $P \implies Q$ , false exactly when $P$ is true and $Q$ is false;
- the *equivalence* $P \iff Q$ , true exactly when $P$ and $Q$ have the same truth value.

**Remark 1.2.**

The truth table of $P \implies Q$ deserves a pause: when $P$ is false, $P \implies Q$ is *true*, whatever $Q$ is. “If $2 < 1$ then $0 = 5$” is a true implication. An implication asserts nothing about what happens when its hypothesis fails.

**Proposition 1.3 (Rules of computation on statements).**

For all [statements](#def-b1-logic-statement) $P$, $Q$, $R$:

1. $\lnot(\lnot P) \iff P$ ;
2. De Morgan’s laws: $\lnot(P \land Q) \iff (\lnot P) \lor (\lnot Q)$ and $\lnot(P \lor Q) \iff (\lnot P) \land (\lnot Q)$ ;
3. $(P \implies Q) \iff \bigl((\lnot P) \lor Q\bigr)$ , hence $\lnot(P \implies Q) \iff P \land (\lnot Q)$ ;
4. contraposition: $(P \implies Q) \iff \bigl((\lnot Q) \implies (\lnot P)\bigr)$ ;
5. $(P \iff Q) \iff \bigl((P \implies Q) \land (Q \implies  P)\bigr)$ ;
6. distributivity: $P \land (Q \lor R) \iff (P \land Q) \lor  (P \land R)$ and $P \lor (Q \land R) \iff (P \lor Q) \land  (P \lor R)$ .

**Proof.** Each equivalence is checked by comparing truth tables: two compound [statements](#def-b1-logic-statement) built from $P$, $Q$, $R$ are equivalent exactly when they take the same truth value in each of the (four or eight) cases. Let us display one table in full, for the first De Morgan law:

| $P$ | $Q$ | $P \land Q$ | $\lnot(P \land Q)$ | $\lnot P$ | $\lnot Q$ | $(\lnot P) \lor (\lnot Q)$ |
| --- | --- | --- | --- | --- | --- | --- |
| T | T | T | F | F | F | F |
| T | F | F | T | F | T | T |
| F | T | F | T | T | F | T |
| F | F | F | T | T | T | T |

Columns $4$ and $7$ coincide, which proves the law. For contraposition a verbal shortcut is quicker: $P \implies Q$ is false exactly in the case ($P$ true, $Q$ false), and $(\lnot Q) \implies (\lnot P)$ is false exactly in the case ($\lnot Q$ true, $\lnot P$ false), i.e. ($Q$ false, $P$ true) — the same single case, so the two implications have identical tables. The remaining rules are checked the same way; note that (3) reduces every implication to a disjunction, so that (2) mechanically produces the negation rule $\lnot(P \implies Q) \iff P
\land (\lnot Q)$: to contradict an implication one must exhibit a case where the hypothesis holds and the conclusion fails. ∎

## 1.2 Quantifiers

**Definition 1.4 (Quantifiers).**

Let $P(x)$ be a property of an element $x$ of a [set](#def-b1-logic-sets) $E$.

- $\forall x \in E,\ P(x)$ (“for all $x$ in $E$ , $P(x)$ ”) is true when every element of $E$ satisfies $P$ ;
- $\exists x \in E,\ P(x)$ (“there exists $x$ in $E$ such that $P(x)$ ”) is true when at least one element of $E$ satisfies $P$ .

One writes $\exists!$ for “there exists a unique”.

**Proposition 1.5 (Negation of quantifiers).**

$$
\lnot\bigl(\forall x \in E,\ P(x)\bigr) \iff
\exists x \in E,\ \lnot P(x),
\qquad
\lnot\bigl(\exists x \in E,\ P(x)\bigr) \iff
\forall x \in E,\ \lnot P(x).
$$

**Proof.** Let us argue the first equivalence in both directions; the second is symmetric. If $\forall x \in E,\ P(x)$ is false, then not every element satisfies $P$: the [set](#def-b1-logic-sets) $A = \{x \in E : \lnot P(x)\}$ cannot be empty, and any of its elements witnesses $\exists x \in
E,\ \lnot P(x)$. Conversely, if some $x_0 \in E$ satisfies $\lnot
P(x_0)$, then $x_0$ is a counterexample and the universal [statement](#def-b1-logic-statement) fails. For the second rule: “no $x$ satisfies $P$” means the [set](#def-b1-logic-sets) $\{x : P(x)\}$ is empty, i.e. every $x$ lies in its complement $A$. Applied in cascade to a nested prefix of quantifiers, the two rules give the mechanical procedure of [Example 1.8](#ex-b1-logic-limit): the negation walks left to right, flipping every $\forall$ into $\exists$ and every $\exists$ into $\forall$, and finally negates the innermost predicate. ∎

**Example 1.6 (Negating everyday mathematical sentences).**

Let $f \colon \R \to \R$. The sentence “$f$ is increasing” reads

$$
\forall x \in \R,\ \forall y \in \R,\quad
x \leq y \implies f(x) \leq f(y) ,
$$

and its negation, by [Proposition 1.5](#prop-b1-logic-negquant) plus the rule $\lnot(P \implies Q) \iff P \land \lnot Q$:

$$
\exists x \in \R,\ \exists y \in \R,\quad
x \leq y \ \text{ and }\ f(x) > f(y) :
$$

a single witnessing pair suffices. Likewise “$f$ is bounded” is $\exists M \in \R,\ \forall x \in \R,\ \abs{f(x)} \leq M$, with negation

$$
\forall M \in \R,\ \exists x \in \R,\quad \abs{f(x)} > M :
$$

*whatever* bound is proposed, some point beats it. The insight: a correct negation never contains “not” applied to a quantified block — it is a new positive [statement](#def-b1-logic-statement), in which the roles are exchanged: one now produces the witnesses one previously received.

**Example 1.7 (Order of quantifiers).**

The [order](#def-b1-logic-order) of different quantifiers matters:

$$
\forall x \in \R,\ \exists y \in \R,\ y > x
\quad\text{is true (take } y = x+1\text{),}
$$

$$
\exists y \in \R,\ \forall x \in \R,\ y > x
\quad\text{is false (no real number exceeds all reals).}
$$

In the first [statement](#def-b1-logic-statement) $y$ may depend on $x$; in the second, one single $y$ must work for all $x$. Two identical quantifiers, on the other hand, always commute.

**Example 1.8 (Reading a definition with three quantifiers).**

The sentence “the sequence $(u_n)$ converges to $\ell$” will be written in [Chapter 11](https://one-course.com/books/math/3/en/chapter/11-sequences#ch-b1-seq) as

$$
\forall \varepsilon > 0,\ \exists N \in \N,\ \forall n \geq N,\quad
\abs{u_n - \ell} \leq \varepsilon .
$$

Its negation, by [Proposition 1.5](#prop-b1-logic-negquant) applied three times, is

$$
\exists \varepsilon > 0,\ \forall N \in \N,\ \exists n \geq N,\quad
\abs{u_n - \ell} > \varepsilon .
$$

Being able to negate such sentences mechanically, without thinking about what they mean, is a genuine skill: it separates the logical work from the mathematical work.

## 1.3 Proof techniques

**Method 1.9 (The standard proof patterns).**

To prove…

1. *an implication $P \implies Q$ directly* : assume $P$ , deduce $Q$ ;
2. *by contraposition* : assume $\lnot Q$ , deduce $\lnot P$ — valid by [Proposition 1.3](#prop-b1-logic-rules) (4);
3. *by contradiction* : assume the [statement](#def-b1-logic-statement) is false, derive a contradiction;
4. *an equivalence* : prove both implications separately (or chain known equivalences);
5. *a “for all” [statement](#def-b1-logic-statement)* : pick an *arbitrary* $x$ in $E$ (“let $x \in E$ ”) and prove $P(x)$ ;
6. *a “there exists” [statement](#def-b1-logic-statement)* : exhibit a witness, or prove existence indirectly;
7. *by induction* : see [Theorem 1.12](#thm-b1-logic-induction) .

When proving a [statement](#def-b1-logic-statement) about a well-chosen but arbitrary element, never give the element extra properties: “let $x \in \R$” followed by “since $x > 0$…” proves nothing about negative $x$.

**Remark 1.10 (Common pitfalls in proofs).**

Four classical traps, all worth naming once.

1. *Converse instead of contrapositive.* $Q \implies P$ is *not* equivalent to $P \implies Q$ ; only $\lnot Q  \implies \lnot P$ is. “If it rains, the street is wet” does not entitle one to conclude rain from a wet street.
2. *Proving an equivalence by one implication.* An “iff” claim is two theorems; announce which direction is being proved, and prove both. Chains of $\iff$ are legal only if *every* link is genuinely reversible — squaring an equation, for instance, is not.
3. *Backwards proofs.* Starting from the desired conclusion and deducing a true [statement](#def-b1-logic-statement) proves nothing (from $-1 = 1$ one derives the true $1 = 1$ by squaring). A computation may be *discovered* backwards, but it must be *written* forwards, or with explicit equivalences.
4. *Fixed witness versus arbitrary element.* To prove $\exists x,\ P(x)$ , one may exhibit a single cleverly chosen $x$ ; to prove $\forall x,\ P(x)$ , the chosen $x$ must remain arbitrary. Mixing the two — checking a universal claim on an example — is the most common error in beginners’ copies.

**Example 1.11 (Contraposition and contradiction at work).**

*For $n \in \N$: if $n^2$ is even then $n$ is even.* By contraposition: if $n$ is odd, $n = 2k+1$, then $n^2 = 4k^2 + 4k + 1$ is odd.

*$\sqrt 2$ is irrational.* By contradiction: suppose $\sqrt 2 = p/q$ with $p, q \in \N^*$ and the fraction in lowest terms. Then $p^2 = 2q^2$ is even, so $p$ is even (previous point), $p = 2r$; then $q^2 = 2r^2$ is even, so $q$ is even — contradicting lowest terms.

**Theorem 1.12 (Induction).**

Let $P(n)$ be a property of the integer $n$. If

1. $P(0)$ is true, and
2. for all $n \in \N$ , $P(n) \implies P(n+1)$ ,

then $P(n)$ is true for all $n \in \N$.

*Strong induction:* conclusion unchanged if (2) is replaced by: for all $n$, $\bigl(P(0) \land \dots \land P(n)\bigr) \implies
P(n+1)$.

**Proof.** This is a property of $\N$ itself, equivalent to: *every nonempty subset of $\N$ has a least element* (which we take as known). Indeed, suppose (1) and (2) hold and let $A = \{n \in \N : P(n)
\text{ false}\}$. If $A \neq \emptyset$, it has a least element $m$; $m \neq 0$ by (1); then $m - 1 \notin A$, so $P(m-1)$ holds, and (2) gives $P(m)$ — contradiction. So $A = \emptyset$. For strong induction, apply the same argument: $P(0), \dots, P(m-1)$ all hold since $m$ is least in $A$. ∎

**Example 1.13 (Proving unique existence).**

A [statement](#def-b1-logic-statement) $\exists!\,x,\ P(x)$ is *two* [statements](#def-b1-logic-statement), proved separately: existence (exhibit or construct some $x_0$ with $P(x_0)$) and uniqueness (assume $P(x)$ and $P(x')$, deduce $x =
x'$). Sample: *there is a unique real $x$ with $x^3 + x =
2$.* Existence: $x_0 = 1$ works, since $1 + 1 = 2$. Uniqueness: if $x^3 + x = x'^3 + x'$, then

$$
0 = (x^3 - x'^3) + (x - x')
= (x - x')\,\bigl(x^2 + xx' + x'^2 + 1\bigr),
$$

and the second factor is positive (it equals $\bigl(x +
\tfrac{x'}2\bigr)^2 + \tfrac34 x'^2 + 1 \geq 1$), so $x = x'$. Note the division of labor: existence used a lucky guess, uniqueness used algebra valid for *arbitrary* solutions — neither argument does the other’s job, and forgetting the second half is a standing temptation once a solution has been found.

**Example 1.14.**

For all $n \in \N^*$: $\;\sum_{k=1}^n k = \frac{n(n+1)}{2}$. Base case $n = 1$: both sides equal $1$. Step: assuming the formula for $n$,

$$
\sum_{k=1}^{n+1} k = \frac{n(n+1)}{2} + (n+1)
= (n+1)\Bigl(\frac n2 + 1\Bigr) = \frac{(n+1)(n+2)}{2}. \qedhere
$$

**Example 1.15 (Strong induction at work).**

*Every integer $n \geq 2$ is a product of prime numbers* (a prime being an integer $\geq 2$ whose only divisors $\geq 1$ are $1$ and itself; primes are studied for their own sake in [Chapter 6](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#ch-b1-arith)). Ordinary induction is helpless here: knowing that $95 = 5 \times 19$ factors says nothing about $96$. Strong induction fits exactly. Base case: $2$ is prime, hence a (one-factor) product of primes. Step: let $n \geq 2$ and assume every integer $m$ with $2 \leq m \leq n$ is a product of primes. If $n + 1$ is prime, done. Otherwise $n + 1 = ab$ with $2 \leq a, b \leq n$; by the strong hypothesis both $a$ and $b$ are products of primes, hence so is $n + 1$. The insight: strong induction is the right tool whenever the “reason” for $P(n+1)$ lives at some unpredictable earlier rank, not at rank $n$.

## 1.4 Sets

**Definition 1.16 (Set operations).**

We take the notion of *set* and the membership relation $x \in E$ as primitive. For sets $A, B$ inside an ambient set $E$:

- *inclusion* : $A \subseteq B$ when $\forall x,\ x \in A  \implies x \in B$ ; equality $A = B$ when $A \subseteq B$ and $B \subseteq A$ ;
- *union* $A \cup B$ , *intersection* $A \cap B$ , *difference* $A \setminus B = \{x \in A : x \notin B\}$ , *complement* $\overline{A} = E \setminus A$ ;
- the *empty set* $\emptyset$ , contained in every set;
- the *power set* $\mathcal{P}(E)$ : the set of all subsets of $E$ ;
- the *product* $E \times F$ : the set of ordered pairs $(x, y)$ with $x \in E$ , $y \in F$ .

**Example 1.17 (Getting used to the power set).**

For $E = \{a, b\}$:

$$
\mathcal P(E) = \bigl\{\, \emptyset,\ \{a\},\ \{b\},\ \{a, b\}
\,\bigr\},
$$

four elements — and note the type discipline: $a \in E$ but $\{a\} \in \mathcal P(E)$; the [statements](#def-b1-logic-statement) $a \in \mathcal P(E)$ and $\{a\} \subseteq \mathcal P(E)$ are both false as written (the second would require $a$ to be a *subset* of $E$). Iterating from nothing: $\mathcal P(\emptyset) = \{\emptyset\}$ has one element, $\mathcal P(\mathcal P(\emptyset)) = \{\emptyset,
\{\emptyset\}\}$ has two, the next has four — [sets](#def-b1-logic-sets) of [sets](#def-b1-logic-sets) are ordinary [sets](#def-b1-logic-sets), and [Chapter 2](https://one-course.com/books/math/3/en/chapter/2-counting#ch-b1-counting) will confirm the doubling pattern: $\abs{\mathcal P(E)} = 2^{\abs E}$. Keeping the levels ($x$, $\{x\}$, $\{\{x\}\}$) straight is half the battle in exercises like Exercises [1.11](#exo-b1-logic-11) and [1.12](#exo-b1-logic-12).

**Proposition 1.18 (Set algebra).**

For subsets $A, B, C$ of $E$:

1. $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ and $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ ;
2. De Morgan: $\overline{A \cup B} = \overline{A} \cap  \overline{B}$ and $\overline{A \cap B} = \overline{A} \cup  \overline{B}$ ;
3. $A \subseteq B \iff \overline{B} \subseteq \overline{A}$ .

**Proof.** Each identity translates a rule of [Proposition 1.3](#prop-b1-logic-rules) through the dictionary ($\in A$ or not) $\leftrightarrow$ ([statement](#def-b1-logic-statement) true or false): e.g. $x \in \overline{A \cup B} \iff \lnot(x \in A \lor x \in
B) \iff (x \notin A) \land (x \notin B) \iff x \in \overline{A} \cap
\overline{B}$. Point (3) is contraposition. As a second sample, the first distributivity law in full:

$$
x \in A \cap (B \cup C)
\iff (x \in A) \land \bigl(x \in B \lor x \in C\bigr)
\iff \bigl(x \in A \land x \in B\bigr) \lor
\bigl(x \in A \land x \in C\bigr),
$$

by the distributivity of [Proposition 1.3](#prop-b1-logic-rules) (6), and the last [statement](#def-b1-logic-statement) reads $x \in (A \cap B) \cup (A \cap C)$. Every [set](#def-b1-logic-sets) identity of this kind is provable by this one mechanical translation — which is why none of them needs memorizing. ∎

**Method 1.19 (Proving set equalities).**

To prove $A = B$, prove the two inclusions: let $x \in A$, show $x \in
B$; then let $x \in B$, show $x \in A$. Alternatively, chain equivalences $x \in A \iff \dots \iff x \in B$ when each step really is an equivalence.

![De Morgan’s laws in pictures: the shaded region on the left is A ∪ B = A ∩ B (everything outside both disks); on the right, A ∩ B = A ∪ B (everything except the lens-shaped overlap). A diagram is not a proof, but it makes the element-chasing proof of impossible to misremember.](https://one-course.com/images/onecourse/chapters/math-3/b1-logic/fig-5465323f1d10.svg)

*De Morgan’s laws in pictures: the shaded region on the left is $\overline{A \cup B} = \overline A \cap \overline B$ (everything outside both disks); on the right, $\overline{A \cap B} = \overline
A \cup \overline B$ (everything except the lens-shaped overlap). A diagram is not a proof, but it makes the element-chasing proof of [Proposition 1.18](#prop-b1-logic-setalgebra) impossible to misremember.*

## 1.5 Maps

**Definition 1.20 (Map, image, preimage).**

A *map* (or *function*) $f \colon E \to F$ assigns to every element $x$ of the [set](#def-b1-logic-sets) $E$ (the *domain*) exactly one element $f(x)$ of the [set](#def-b1-logic-sets) $F$ (the *codomain*). For $A
\subseteq E$ and $B \subseteq F$:

$$
f(A) = \{f(x) : x \in A\} \subseteq F,
\qquad
f^{-1}(B) = \{x \in E : f(x) \in B\} \subseteq E
$$

are the *direct image* of $A$ and the *preimage* of $B$. The *composition* of $f \colon E \to F$ and $g \colon F \to G$ is $g \circ f \colon E \to G$, $x \mapsto
g(f(x))$.

**Remark 1.21.**

The notation $f^{-1}(B)$ does *not* presuppose an inverse [map](#def-b1-logic-map): $f^{-1}(B)$ is defined for every $f$. [Preimages](#def-b1-logic-map) behave better than images: $f^{-1}$ preserves unions, intersections and complements, whereas $f(A \cap A') \subseteq f(A) \cap f(A')$ can be strict ([Exercise 1.8](#exo-b1-logic-8)).

**Example 1.22 (Computing images and preimages).**

Let $f \colon \R \to \R$, $x \mapsto x^2$. Then:

$$
f\bigl(\intcc{-1}{2}\bigr) = \intcc04, \qquad
f^{-1}\bigl(\intcc14\bigr) = \intcc{-2}{-1} \cup \intcc12, \qquad
f^{-1}(\{-1\}) = \emptyset .
$$

For the first: every $x \in \intcc{-1}2$ has $x^2 \in \intcc04$, and every $y \in \intcc04$ is attained as $y = (\sqrt y)^2$ with $\sqrt y
\in \intcc02 \subseteq \intcc{-1}2$ — note that the image is *not* $\intcc14 = \{(-1)^2, 2^2\}$: images of intervals are not computed from endpoints alone. For the second: $1 \leq x^2 \leq 4 \iff
1 \leq \abs x \leq 2$, which splits into two pieces. The third illustrates that a [preimage](#def-b1-logic-map) may be empty — $f^{-1}(B)$ always makes sense, however small the intersection of $B$ with the image. Finally observe on this example the strictness phenomenon of the remark above: with $A = \intcc{-1}0$ and $A' = \intcc01$, one has $f(A \cap A') =
f(\{0\}) = \{0\}$, while $f(A) \cap f(A') = \intcc01$.

**Definition 1.23 (Injective, surjective, bijective).**

A [map](#def-b1-logic-map) $f \colon E \to F$ is:

- *injective* when distinct elements have distinct images: $\forall x, x' \in E,\ f(x) = f(x') \implies  x = x'$ ;
- *surjective* when every element of $F$ is attained: $\forall y \in F,\ \exists x \in E,\ f(x) = y$ ;
- *bijective* when it is both, i.e. every $y \in F$ has exactly one [preimage](#def-b1-logic-map) .

**Theorem 1.24 (Inverse map).**

A [map](#def-b1-logic-map) $f \colon E \to F$ is [bijective](#def-b1-logic-inj) if and only if there is a [map](#def-b1-logic-map) $g \colon F \to E$ with $g \circ f = \mathrm{id}_E$ and $f \circ g =
\mathrm{id}_F$. In that case $g$ is unique; it is written $f^{-1}$ and called the *inverse* of $f$, and $f^{-1}$ is itself [bijective](#def-b1-logic-inj) with $(f^{-1})^{-1} = f$.

**Proof.** ($\Rightarrow$) If $f$ is [bijective](#def-b1-logic-inj), every $y \in F$ has a unique [preimage](#def-b1-logic-map); define $g(y)$ to be that [preimage](#def-b1-logic-map). Then $f(g(y)) = y$ by construction, and $g(f(x)) = x$ because $x$ is *the* [preimage](#def-b1-logic-map) of $f(x)$.

($\Leftarrow$) Suppose such a $g$ exists. If $f(x) = f(x')$, applying $g$ gives $x = x'$: $f$ is [injective](#def-b1-logic-inj). For $y \in F$, $x = g(y)$ satisfies $f(x) = y$: $f$ is [surjective](#def-b1-logic-inj).

Uniqueness: if $g$ and $h$ both work, then $g = g \circ \mathrm{id}_F
= g \circ (f \circ h) = (g \circ f) \circ h = h$. Finally the pair of identities is symmetric in $f$ and $g$, so $g = f^{-1}$ is [bijective](#def-b1-logic-inj) with inverse $f$. ∎

**Example 1.25 (Computing an inverse in practice).**

Let $f \colon \R \to \intoo0{+\infty}$, $f(x) = \eu^{2x+1}$. To invert, solve $y = f(x)$ for a given $y > 0$:

$$
y = \eu^{2x+1} \iff \ln y = 2x + 1 \iff x = \frac{\ln y - 1}2 ,
$$

each step being reversible on the announced domains. The computation delivers everything at once: for each $y$ in the codomain there is exactly one solution $x$, so $f$ is [bijective](#def-b1-logic-inj), and

$$
f^{-1} \colon \intoo0{+\infty} \to \R,
\qquad
f^{-1}(y) = \frac{\ln y - 1}2 .
$$

A quick check of both compositions ($f^{-1}(f(x)) = \frac{(2x+1) -
1}2 = x$ and $f(f^{-1}(y)) = \eu^{\ln y} = y$) confirms [Theorem 1.24](#thm-b1-logic-inverse)’s criterion. The insight: “solve for $x$ and watch the equivalences” is simultaneously the existence proof, the uniqueness proof, and the formula — but it only works if the codomain was announced correctly ($f$ is *not* [surjective](#def-b1-logic-inj) onto $\R$).

**Proposition 1.26 (Composition and the three properties).**

Let $f \colon E \to F$ and $g \colon F \to G$.

1. If $f$ and $g$ are [injective](#def-b1-logic-inj) (resp. [surjective](#def-b1-logic-inj) , [bijective](#def-b1-logic-inj) ), so is $g \circ f$ ; and then $(g \circ f)^{-1} = f^{-1} \circ  g^{-1}$ in the [bijective](#def-b1-logic-inj) case.
2. If $g \circ f$ is [injective](#def-b1-logic-inj) , then $f$ is [injective](#def-b1-logic-inj) . If $g \circ f$ is [surjective](#def-b1-logic-inj) , then $g$ is [surjective](#def-b1-logic-inj) .

**Proof.** (1) If $g(f(x)) = g(f(x'))$, injectivity of $g$ gives $f(x) = f(x')$, then injectivity of $f$ gives $x = x'$. If $z \in G$, surjectivity of $g$ gives $y$ with $g(y) = z$, then surjectivity of $f$ gives $x$ with $f(x) = y$, so $g(f(x)) = z$. In the [bijective](#def-b1-logic-inj) case one checks directly that $f^{-1} \circ g^{-1}$ is a two-sided inverse of $g \circ f$, and uniqueness in [Theorem 1.24](#thm-b1-logic-inverse) concludes.

(2) If $f(x) = f(x')$ then $g(f(x)) = g(f(x'))$, and injectivity of $g \circ f$ gives $x = x'$. If $z \in G$, surjectivity of $g \circ f$ gives $x$ with $g(f(x)) = z$: then $y = f(x)$ satisfies $g(y) = z$. ∎

**Example 1.27 (Point (2) is sharp).**

In [Proposition 1.26](#prop-b1-logic-comp) (2), one cannot upgrade the conclusions: $g \circ f$ [bijective](#def-b1-logic-inj) does *not* force $f$ [surjective](#def-b1-logic-inj) or $g$ [injective](#def-b1-logic-inj). Take $E = G = \{1\}$, $F = \{1,
2\}$, with $f(1) = 1$ and $g(1) = g(2) = 1$: then $g \circ f =
\mathrm{id}_E$ is [bijective](#def-b1-logic-inj), yet $f$ misses the element $2$ and $g$ collapses both elements. The moral is a precise bookkeeping rule: composition information flows to the *inner* [map](#def-b1-logic-map) for injectivity and to the *outer* [map](#def-b1-logic-map) for surjectivity, never the other way. ([Exercise 1.9](#exo-b1-logic-9) builds the same phenomenon with infinite [sets](#def-b1-logic-sets), where it is the engine behind one-sided inverses.)

**Example 1.28.**

$f \colon \R \to \R$, $x \mapsto x^2$ is neither [injective](#def-b1-logic-inj) ($f(-1) =
f(1)$) nor [surjective](#def-b1-logic-inj) ($-1$ has no [preimage](#def-b1-logic-map)). Restricting the domain and codomain, $f \colon \R_+ \to \R_+$, $x \mapsto x^2$ is [bijective](#def-b1-logic-inj), with inverse $y \mapsto \sqrt y$. A [map](#def-b1-logic-map)’s injectivity or surjectivity depends on the announced domain and codomain, not only on the formula.

## 1.6 Relations

**Definition 1.29 (Equivalence relation).**

A *binary relation* $\mathcal{R}$ on a [set](#def-b1-logic-sets) $E$ is an *equivalence relation* when it is: *reflexive* ($x \mathbin{\mathcal{R}} x$ for all $x$), *symmetric* ($x \mathbin{\mathcal{R}} y \implies y
\mathbin{\mathcal{R}} x$) and *transitive* ($x
\mathbin{\mathcal{R}} y$ and $y \mathbin{\mathcal{R}} z$ imply $x
\mathbin{\mathcal{R}} z$). The *equivalence class* of $x$ is $\mathrm{cl}(x) = \{y \in E : x \mathbin{\mathcal{R}} y\}$.

**Example 1.30 (Checking the three axioms).**

On $\R$, declare $x \mathbin{\mathcal{R}} y$ when $x - y \in \Z$. *Reflexive:* $x - x = 0 \in \Z$. *Symmetric:* if $x - y
\in \Z$ then $y - x = -(x - y) \in \Z$. *Transitive:* if $x -
y \in \Z$ and $y - z \in \Z$, then $x - z = (x - y) + (y - z) \in
\Z$ (a sum of integers). So $\mathcal R$ is an [equivalence relation](#def-b1-logic-equiv), and $\mathrm{cl}(x) = x + \Z = \{x + k : k \in \Z\}$: each class contains exactly one representative in $\intco01$, its *fractional part*. By contrast, the relation “$\abs{x - y}
\leq 1$” on $\R$ is reflexive and symmetric but *not* transitive ($0 \mathbin{\mathcal R} 1$ and $1 \mathbin{\mathcal R}
2$, yet $\abs{0 - 2} > 1$): closeness does not propagate, and no [partition](#thm-b1-logic-partition) into classes exists — a useful counterexample to keep in mind when verifying the axioms feels routine.

**Theorem 1.31 (Classes form a partition).**

Let $\mathcal{R}$ be an [equivalence relation](#def-b1-logic-equiv) on $E$. Then the equivalence classes are nonempty, pairwise disjoint or equal, and their union is $E$: they form a *partition* of $E$. Conversely, every [partition](#thm-b1-logic-partition) of $E$ arises this way from exactly one [equivalence relation](#def-b1-logic-equiv) (“being in the same piece”).

**Proof.** $x \in \mathrm{cl}(x)$ by reflexivity, so classes are nonempty with union $E$. Suppose $\mathrm{cl}(x) \cap \mathrm{cl}(y) \neq \emptyset$, say $z$ lies in both. Then $x \mathbin{\mathcal{R}} z$ and $y
\mathbin{\mathcal{R}} z$, so by symmetry and transitivity $x
\mathbin{\mathcal{R}} y$. Now for any $t \in \mathrm{cl}(y)$, transitivity gives $t \in \mathrm{cl}(x)$, and symmetrically: the two classes are equal. For the converse, let $(E_i)_{i \in I}$ be a [partition](#thm-b1-logic-partition) of $E$ and define $x \mathbin{\mathcal S} y$ to mean “some piece contains both $x$ and $y$”. *Reflexive:* $x$ lies in some piece, which then contains $x$ twice over. *Symmetric:* the defining condition is symmetric in $x$ and $y$. *Transitive:* if $x, y \in E_i$ and $y, z \in E_j$, then $y \in E_i \cap E_j$, so $E_i = E_j$ (distinct pieces are disjoint) and $x, z$ share a piece. The $\mathcal S$-class of $x$ is exactly the piece containing $x$, so the classes are the given pieces. Finally the relation is determined by its classes: two [equivalence relations](#def-b1-logic-equiv) with the same classes relate the same pairs, since each relates $x$ and $y$ exactly when $y$ belongs to the class of $x$ — whence the uniqueness claim. ∎

**Example 1.32.**

On $\Z$, congruence modulo $n$ ($x \equiv y \pmod n$ when $n$ divides $x - y$) is an [equivalence relation](#def-b1-logic-equiv); its classes are the $n$ [sets](#def-b1-logic-sets) of integers with a given remainder upon division by $n$. This example becomes the ring $\Z/n\Z$ in [Chapter 7](https://one-course.com/books/math/3/en/chapter/7-algebraic-structures#ch-b1-structures).

**Definition 1.33 (Order relation).**

A relation $\preceq$ on $E$ is an *order* when it is reflexive, *antisymmetric* ($x \preceq y$ and $y
\preceq x$ imply $x = y$) and transitive. The order is *total* when any two elements are comparable, *partial* otherwise. An element $M \in A \subseteq E$ is a *greatest element* of $A$ when $a \preceq M$ for all $a \in A$; greatest (and least) elements are unique when they exist.

**Example 1.34.**

$(\R, \leq)$ is totally ordered. $(\mathcal{P}(E), \subseteq)$ is partially ordered as soon as $E$ has two elements: $\{a\}$ and $\{b\}$ are not comparable. The subset $A = \{\{a\}, \{b\}\}$ of $\mathcal{P}(\{a,b\})$ has no greatest element, yet has an upper bound $\{a, b\}$: the distinction between greatest elements and upper bounds returns, for $\R$, in [Chapter 10](https://one-course.com/books/math/3/en/chapter/10-real-numbers#ch-b1-reals).

**Example 1.35 (Two orders on the grid N2\N^2N2).**

On pairs of naturals, compare componentwise: $(a, b) \preceq (a',
b')$ when $a \leq a'$ *and* $b \leq b'$ (the *product [order](#def-b1-logic-order)*). This is an [order](#def-b1-logic-order) — each axiom is inherited coordinate by coordinate — but a partial one: $(1, 3)$ and $(2, 0)$ are incomparable. Now compare like a dictionary: $(a, b)
\preceq_{\mathrm{lex}} (a', b')$ when $a < a'$, or $a = a'$ and $b
\leq b'$ (the *lexicographic [order](#def-b1-logic-order)*). Transitivity requires a two-case check but holds, and any two pairs are now comparable: the [order](#def-b1-logic-order) is total. The two [orders](#def-b1-logic-order) rank the same [set](#def-b1-logic-sets) differently — $(0, 100) \preceq_{\mathrm{lex}} (1, 0)$ though the product [order](#def-b1-logic-order) says nothing — a reminder that an [order](#def-b1-logic-order) is a structure one *chooses*, not a property of the [set](#def-b1-logic-sets). Lexicographic comparison is also the standard trick for turning several sorting criteria into one.

**Remark 1.36 (Interlude: size as bijection).**

A quiet theme of this chapter deserves a spotlight: bijections are the mathematician’s notion of “same size”. For finite [sets](#def-b1-logic-sets) this becomes the counting calculus of [Chapter 2](https://one-course.com/books/math/3/en/chapter/2-counting#ch-b1-counting), where every formula is secretly a bijection; for infinite [sets](#def-b1-logic-sets) it becomes the weekend problem below, where $\N$, $\Q$ and $\R$ turn out to have genuinely different sizes. The same dictionary reappears twice more in this volume in refined forms: sequences ([Chapter 11](https://one-course.com/books/math/3/en/chapter/11-sequences#ch-b1-seq)) are nothing but [maps](#def-b1-logic-map) $\N \to \R$, so [statements](#def-b1-logic-statement) about sequences are [statements](#def-b1-logic-statement) about a [set](#def-b1-logic-sets) of [maps](#def-b1-logic-map); and linear algebra will measure vector spaces not by bijections but by *linear* bijections, whose existence is governed by a single number, the dimension ([Chapter 19](https://one-course.com/books/math/3/en/chapter/19-finite-dimension#ch-b1-findim)). Whenever a new “sameness” appears — equipotence, isomorphism of groups ([Chapter 7](https://one-course.com/books/math/3/en/chapter/7-algebraic-structures#ch-b1-structures)), linear isomorphism — the pattern of [Theorem 1.24](#thm-b1-logic-inverse) repeats: sameness is an invertible, structure-respecting [map](#def-b1-logic-map).

**Remark 1.37 (Where this chapter is used).**

Everywhere — but a few places deserve flagging. The three-quantifier gymnastics of [Example 1.8](#ex-b1-logic-limit) is the daily bread of Chapters [11](https://one-course.com/books/math/3/en/chapter/11-sequences#ch-b1-seq) and [13](https://one-course.com/books/math/3/en/chapter/13-limits-and-continuity#ch-b1-continuity): every limit proof is a game played against an arbitrary $\varepsilon$. Equivalence classes reappear as the congruence classes of $\Z/n\Z$ in [Chapter 7](https://one-course.com/books/math/3/en/chapter/7-algebraic-structures#ch-b1-structures), where the [partition](#thm-b1-logic-partition) of [Theorem 1.31](#thm-b1-logic-partition) acquires an algebraic structure of its own. [Order relations](#def-b1-logic-order), upper bounds and least upper bounds become the axiomatic heart of $\R$ in [Chapter 10](https://one-course.com/books/math/3/en/chapter/10-real-numbers#ch-b1-reals). Injections, surjections and bijections return as the linear [maps](#def-b1-logic-map) of [Chapter 20](https://one-course.com/books/math/3/en/chapter/20-linear-maps#ch-b1-linmaps), where injectivity can be tested on a single vector (the kernel); and the weekend problem below turns the bare notion of bijection into a theory of the *sizes of infinite [sets](#def-b1-logic-sets)*, whose conclusions (countability of $\Q$, uncountability of $\R$) resurface in Chapters [10](https://one-course.com/books/math/3/en/chapter/10-real-numbers#ch-b1-reals) and [12](https://one-course.com/books/math/3/en/chapter/12-topology-of-the-real-line#ch-b1-topology).

## 1.7 Exercises

**Exercise 1.1 ★.**

Write the negation of each [statement](#def-b1-logic-statement), without using the word “not”:

1. $\forall x \in \R,\ \exists y \in \R,\ x + y > 0$ ;
2. $\exists x \in \R,\ \forall y \in \R,\ xy = 0$ ;
3. $\forall \varepsilon > 0,\ \exists \delta > 0,\ \forall x \in  \R,\ \abs{x} \leq \delta \implies \abs{f(x)} \leq \varepsilon$ (for a fixed [map](#def-b1-logic-map) $f \colon \R \to \R$ ).

Then decide whether [statements](#def-b1-logic-statement) (1) and (2) are true.

**Solution of Exercise 1.1.**

Negations, pushing $\lnot$ through each quantifier ([Proposition 1.5](#prop-b1-logic-negquant)) and using $\lnot(P \implies Q) \iff
P \land \lnot Q$:

1. $\exists x \in \R,\ \forall y \in \R,\ x + y \leq 0$ ;
2. $\forall x \in \R,\ \exists y \in \R,\ xy \neq 0$ ;
3. $\exists \varepsilon > 0,\ \forall \delta > 0,\ \exists x \in  \R,\ \abs{x} \leq \delta \text{ and } \abs{f(x)} >  \varepsilon$ .

[Statement](#def-b1-logic-statement) (1) is true: given $x$, take $y = -x + 1$; then $x + y = 1 >
0$. [Statement](#def-b1-logic-statement) (2) is true: $x = 0$ satisfies $xy = 0$ for all $y$.

**Exercise 1.2 ★.**

Let $P, Q$ be [statements](#def-b1-logic-statement). Using truth tables, prove that $\lnot(P \implies Q) \iff P \land (\lnot Q)$, and deduce the negation of: “if a function is differentiable then it is continuous”.

**Solution of Exercise 1.2.**

Truth table, writing T/F for the four cases $(P, Q)$:

| $P$ | $Q$ | $P \implies Q$ | $\lnot(P \implies Q)$ | $\lnot Q$ | $P \land \lnot Q$ |
| --- | --- | --- | --- | --- | --- |
| T | T | T | F | F | F |
| T | F | F | T | T | T |
| F | T | T | F | F | F |
| F | F | T | F | T | F |

Columns $4$ and $6$ coincide, proving the equivalence. The negation of “if a function is differentiable then it is continuous” is therefore: “there is a function which is differentiable and not continuous” (a false [statement](#def-b1-logic-statement), as it happens: the original implication is true, see [Chapter 14](https://one-course.com/books/math/3/en/chapter/14-differentiation#ch-b1-derivative)).

**Exercise 1.3 ★.**

Prove by contraposition: for $x \in \R$, if $x^3 + x \geq 2$ then $x \geq 1$. Then prove by contradiction: there is no smallest strictly positive real number.

**Solution of Exercise 1.3.**

*Contraposition.* Assume $x < 1$. Then $x^3 < 1$ (the cube function is increasing) and $x < 1$, so $x^3 + x < 2$. This proves the contrapositive, hence the [statement](#def-b1-logic-statement).

*Contradiction.* Suppose $a > 0$ is the smallest strictly positive real. Then $a/2$ is strictly positive and $a/2 < a$ (since $a > 0$), contradicting minimality. Hence no such $a$ exists.

**Exercise 1.4 ★.**

Prove by induction that for all $n \in \N$:

1. $\sum_{k=0}^{n} 2^k = 2^{n+1} - 1$ ;
2. $4^n + 5$ is divisible by $3$ .

**Solution of Exercise 1.4.**

1. Base case $n = 0$: $2^0 = 1 = 2^1 - 1$. Step: assuming the identity for $n$, $$\sum_{k=0}^{n+1} 2^k = (2^{n+1} - 1) + 2^{n+1}  = 2 \cdot 2^{n+1} - 1 = 2^{n+2} - 1 .$$
2. Base case $n = 0$: $4^0 + 5 = 6 = 3 \times 2$. Step: if $4^n + 5 = 3m$, then $$4^{n+1} + 5 = 4(4^n + 5) - 15 = 3(4m - 5),$$ divisible by $3$.

**Exercise 1.5 ★.**

Find the flaw in the following “proof” that all pencils have the same color. *Let $P(n)$: “in every [set](#def-b1-logic-sets) of $n$ pencils, all pencils have the same color”. $P(1)$ is clear. Assume $P(n)$ and take $n+1$ pencils; removing the last one, the first $n$ share their color; removing the first one, the last $n$ share their color; hence all $n+1$ share their color.*

**Solution of Exercise 1.5.**

The inductive step silently assumes that the two groups (“the first $n$” and “the last $n$”) overlap, so that the shared pencils carry the color from one group to the other. For $n + 1 = 2$ the two groups are $\{$first pencil$\}$ and $\{$second pencil$\}$: they are disjoint, and the argument breaks. So $P(1) \implies P(2)$ was never proved, and the induction collapses — even though $P(n) \implies P(n+1)$ is valid for every $n \geq 2$.

**Exercise 1.6 ★.**

Let $A, B, C$ be subsets of $E$. Prove:

1. $A \setminus B = A \cap \overline{B}$ ;
2. $(A \cup B) \setminus C = (A \setminus C) \cup (B \setminus  C)$ ;
3. $A \subseteq B \iff A \cup B = B \iff A \cap B = A$ .

**Solution of Exercise 1.6.**

1. $x \in A \setminus B \iff x \in A \land x \notin B \iff x \in  A \land x \in \overline{B} \iff x \in A \cap \overline{B}$ .
2. Using (1) and distributivity ( [Proposition 1.18](#prop-b1-logic-setalgebra) ): $(A \cup B) \cap \overline{C} = (A \cap \overline{C}) \cup  (B \cap \overline{C})$ .
3. Suppose $A \subseteq B$ . Then $A \cup B \subseteq B$ (both pieces lie in $B$ ) and $B \subseteq A \cup B$ always, so $A \cup B = B$ . Suppose $A \cup B = B$ : then $A \cap B  \subseteq A$ always, and $A \subseteq A \cup B = B$ gives $A \subseteq A \cap B$ , so $A \cap B = A$ . Suppose $A \cap B =  A$ : then $A = A \cap B \subseteq B$ . The three conditions are thus equivalent (we proved a cycle of implications).

**Exercise 1.7 ★★.**

For each [map](#def-b1-logic-map), decide (with proof) whether it is [injective](#def-b1-logic-inj), [surjective](#def-b1-logic-inj), [bijective](#def-b1-logic-inj):

1. $f \colon \N \to \N$ , $n \mapsto n + 1$ ;
2. $g \colon \Z \to \Z$ , $n \mapsto n + 1$ ;
3. $h \colon \R \setminus \{1\} \to \R$ , $x \mapsto  \frac{x+1}{x-1}$ .

For $h$, adjust the codomain to make it [bijective](#def-b1-logic-inj) and compute the inverse.

**Solution of Exercise 1.7.**

1. $f$ is [injective](#def-b1-logic-inj) ( $n + 1 = m + 1 \implies n = m$ ) but not [surjective](#def-b1-logic-inj) : $0$ has no [preimage](#def-b1-logic-map) in $\N$ .
2. $g$ is [bijective](#def-b1-logic-inj) : $n \mapsto n - 1$ is a two-sided inverse on $\Z$ .
3. $h$ is [injective](#def-b1-logic-inj) : $\frac{x+1}{x-1} = \frac{x'+1}{x'-1}$ gives $(x+1)(x'-1) = (x'+1)(x-1)$ , i.e. $xx' - x + x' - 1 = xx' -  x' + x - 1$ , so $2x' = 2x$ . It is not [surjective](#def-b1-logic-inj) onto $\R$ : solving $y = \frac{x+1}{x-1}$ gives $x(y - 1) = y + 1$ , which has no solution when $y = 1$ (the equation reads $0 = 2$ ). With codomain $\R \setminus \{1\}$ , the same computation gives the unique [preimage](#def-b1-logic-map) $x = \frac{y+1}{y-1}$ , so $h \colon \R \setminus \{1\} \to \R \setminus \{1\}$ is [bijective](#def-b1-logic-inj) and $h^{-1}(y) = \frac{y+1}{y-1} = h(y)$ : $h$ is its own inverse.

**Exercise 1.8 ★★.**

Let $f \colon E \to F$, let $A, A' \subseteq E$ and $B, B' \subseteq
F$.

1. Prove $f^{-1}(B \cap B') = f^{-1}(B) \cap f^{-1}(B')$ and $f(A \cup A') = f(A) \cup f(A')$ .
2. Prove $f(A \cap A') \subseteq f(A) \cap f(A')$ and give an example where the inclusion is strict.
3. Prove: $f$ is [injective](#def-b1-logic-inj) if and only if $f(A \cap A') = f(A)  \cap f(A')$ for all $A, A'$ .

**Solution of Exercise 1.8.**

1. $x \in f^{-1}(B \cap B') \iff f(x) \in B \cap B' \iff f(x) \in  B \land f(x) \in B' \iff x \in f^{-1}(B) \cap f^{-1}(B')$ . For images: $y \in f(A \cup A')$ iff $y = f(x)$ for some $x$ in $A$ or in $A'$ , iff $y \in f(A)$ or $y \in f(A')$ .
2. If $y \in f(A \cap A')$ , then $y = f(x)$ with $x \in A$ and $x \in A'$ , so $y \in f(A)$ and $y \in f(A')$ . Strictness: take $f \colon \R \to \R$ , $x \mapsto x^2$ , $A = \{-1\}$ , $A' = \{1\}$ : then $f(A \cap A') = f(\emptyset) = \emptyset$ but $f(A) \cap f(A') = \{1\}$ .
3. ( $\Leftarrow$ ) With $A = \{x\}$ , $A' = \{x'\}$ for $x \neq  x'$ : if $f(x) = f(x')$ , then $f(A) \cap f(A') = \{f(x)\}$ while $f(A \cap A') = \emptyset$ , contradicting the assumed equality; so $f$ is [injective](#def-b1-logic-inj) . ( $\Rightarrow$ ) Let $f$ be [injective](#def-b1-logic-inj) and $y \in f(A) \cap f(A')$ : $y = f(x) = f(x')$ with $x \in A$ , $x' \in A'$ ; injectivity gives $x = x' \in A \cap  A'$ , so $y \in f(A \cap A')$ . With (2), equality holds.

**Exercise 1.9 ★★.**

Let $f \colon E \to F$ and $g \colon F \to E$ satisfy $g \circ f =
\mathrm{id}_E$. Prove that $f$ is [injective](#def-b1-logic-inj) and $g$ is [surjective](#def-b1-logic-inj). Give an example where neither $f$ nor $g$ is [bijective](#def-b1-logic-inj).

**Solution of Exercise 1.9.**

$g \circ f = \mathrm{id}_E$ is [injective](#def-b1-logic-inj) and [surjective](#def-b1-logic-inj), so by [Proposition 1.26](#prop-b1-logic-comp) (2), $f$ is [injective](#def-b1-logic-inj) and $g$ is [surjective](#def-b1-logic-inj). Example: $E = \N$, $F = \Z$, $f$ the inclusion $n \mapsto n$, and $g \colon \Z \to \N$, $g(n) = n$ for $n \geq 0$ and $g(n) = 0$ for $n < 0$. Then $g(f(n)) = n$ for all $n \in \N$, but $f$ is not [surjective](#def-b1-logic-inj) and $g$ is not [injective](#def-b1-logic-inj).

**Exercise 1.10 ★★.**

On $\R$, define $x \mathbin{\mathcal{R}} y \iff x^2 - y^2 = x - y$. Prove that $\mathcal{R}$ is an [equivalence relation](#def-b1-logic-equiv) and describe the [equivalence class](#def-b1-logic-equiv) of each real $x$. Which classes have exactly one element?

**Solution of Exercise 1.10.**

$x^2 - y^2 = x - y \iff (x - y)(x + y) = x - y \iff (x - y)(x + y - 1)
= 0 \iff y = x$ or $y = 1 - x$. *Reflexive:* $y = x$ works. *Symmetric:* the condition “$y = x$ or $y = 1 - x$” is symmetric in $x$ and $y$ (if $y = 1 - x$ then $x = 1 - y$). *Transitive:* suppose $x \mathbin{\mathcal{R}} y$ and $y
\mathbin{\mathcal{R}} z$; going through the four cases, $z$ equals $x$ or $1 - x$ each time (e.g. $y = 1 - x$ and $z = 1 - y$ give $z = x$). So $\mathcal{R}$ is an [equivalence relation](#def-b1-logic-equiv) and $\mathrm{cl}(x) =
\{x,\, 1 - x\}$. This class has one element exactly when $x = 1 - x$, i.e. for $x = \frac12$.

**Exercise 1.11 ★★★.**

(Cantor) Let $E$ be a [set](#def-b1-logic-sets). Prove that there is no surjection from $E$ onto $\mathcal{P}(E)$. *Hint: given $f \colon E \to
\mathcal{P}(E)$, consider $D = \{x \in E : x \notin f(x)\}$.*

**Solution of Exercise 1.11.**

Let $f \colon E \to \mathcal{P}(E)$ be any [map](#def-b1-logic-map) and set $D = \{x \in E : x \notin f(x)\} \in \mathcal{P}(E)$. Suppose $D =
f(a)$ for some $a \in E$. If $a \in D$, then by definition of $D$, $a \notin f(a) = D$: contradiction. If $a \notin D$, then $a \notin
f(a)$, so by definition of $D$, $a \in D$: contradiction. Hence $D$ is not in the image of $f$, and $f$ is not [surjective](#def-b1-logic-inj). (In particular no [set](#def-b1-logic-sets) is in bijection with its [power set](#def-b1-logic-sets): there are “more” subsets of $\N$ than integers.)

**Exercise 1.12 ★★★.**

Let $f \colon E \to F$ be a [map](#def-b1-logic-map). Define $\Phi \colon \mathcal{P}(F)
\to \mathcal{P}(E)$ by $\Phi(B) = f^{-1}(B)$.

1. Prove that $f$ is [surjective](#def-b1-logic-inj) if and only if $\Phi$ is [injective](#def-b1-logic-inj) .
2. Prove that $f$ is [injective](#def-b1-logic-inj) if and only if $\Phi$ is [surjective](#def-b1-logic-inj) .

**Solution of Exercise 1.12.**

1. ( $\Rightarrow$ ) Let $f$ be [surjective](#def-b1-logic-inj) and $\Phi(B) =  \Phi(B')$ . For $y \in B$ , pick $x$ with $f(x) = y$ ; then $x  \in f^{-1}(B) = f^{-1}(B')$ , so $y = f(x) \in B'$ . Hence $B  \subseteq B'$ , and symmetrically $B' \subseteq B$ : $\Phi$ is [injective](#def-b1-logic-inj) . ( $\Leftarrow$ ) If $f$ is not [surjective](#def-b1-logic-inj) , pick $y_0  \in F$ outside the image; then $f^{-1}(\{y_0\}) = \emptyset =  f^{-1}(\emptyset)$ with $\{y_0\} \neq \emptyset$ , so $\Phi$ is not [injective](#def-b1-logic-inj) .
2. ( $\Rightarrow$ ) Let $f$ be [injective](#def-b1-logic-inj) and $A \subseteq E$ . Set $B = f(A)$ ; then $f^{-1}(B) = \{x : f(x) \in f(A)\}$ , and injectivity gives $f(x) \in f(A) \iff x \in A$ , so $\Phi(B) =  A$ : $\Phi$ is [surjective](#def-b1-logic-inj) . ( $\Leftarrow$ ) If $f$ is not [injective](#def-b1-logic-inj) , take $x \neq x'$ with $f(x) = f(x')$ . Every [preimage](#def-b1-logic-map) [set](#def-b1-logic-sets) $f^{-1}(B)$ contains $x$ if and only if it contains $x'$ ; hence $\{x\}$ is not of the form $\Phi(B)$ , and $\Phi$ is not [surjective](#def-b1-logic-inj) .

## 1.8 Problem: Comparing infinities

**Problem 1.1.**

When do two [sets](#def-b1-logic-sets) have “the same number of elements”? Cantor’s answer — when there is a bijection between them — turns out to be usable even for infinite [sets](#def-b1-logic-sets), and it splits infinity into genuinely different sizes. This problem builds the whole toolbox from the bare definitions of this chapter: the Cantor–Schröder–Bernstein theorem (two injections manufacture a bijection), the countability of $\Q$, the uncountability of $\R$ by the diagonal argument, and Cantor’s astonishing 1874 conclusion: *[transcendental numbers](#pb-b1-logic-1) exist, and massively so*, without exhibiting a single one. Throughout, for [sets](#def-b1-logic-sets) $E$ and $F$, write $E \preceq F$ when there exists an injection from $E$ into $F$, and $E \approx F$ (“$E$ and $F$ are *equipotent*”) when there exists a bijection from $E$ onto $F$.

**Part I — The vocabulary of comparison.**

1. Show that $\approx$ behaves like an [equivalence relation](#def-b1-logic-equiv) : $E \approx E$ ; if $E \approx F$ then $F \approx E$ ; if $E \approx F$ and $F \approx G$ then $E \approx G$ . (Quote precisely [Theorem 1.24](#thm-b1-logic-inverse) and [Proposition 1.26](#prop-b1-logic-comp) .)
2. Show that $\preceq$ is transitive, and that an injection $f \colon E \to F$ always induces $E \approx f(E)$ .
3. Let $E \neq \emptyset$ . Show that $E \preceq F$ if and only if there exists a surjection from $F$ onto $E$ .
4. Verify that $n \mapsto n + 1$ is a bijection from $\N$ onto $\N^* = \N \setminus \{0\}$, and that $$\sigma(n) = \frac n2 \ \ (n \text{ even}), \qquad  \sigma(n) = -\frac{n+1}2 \ \ (n \text{ odd})$$ is a bijection from $\N$ onto $\Z$. Hence removing a point, or doubling into negatives, does not change the size of $\N$.

**Part II — The Cantor–Schröder–Bernstein theorem.** Let $f \colon E \to F$ and $g \colon F \to E$ be two injections. Define

$$
C_0 = E \setminus g(F), \qquad C_{n+1} = g\bigl(f(C_n)\bigr)
\ \ (n \in \N), \qquad C = \bigcup_{n \in \N} C_n,
$$

and let $h \colon E \to F$ send $x \in C$ to $f(x)$, and $x \notin C$ to the unique $y \in F$ with $g(y) = x$.

5. Check that $h$ is well defined: if $x \notin C$ then $x \in  g(F)$ , and the element $y$ with $g(y) = x$ is unique.
6. Show that $g\bigl(f(C)\bigr) = \bigcup_{n \geq 1} C_n  \subseteq C$ . (Direct images commute with unions: [Exercise 1.8](#exo-b1-logic-8) .)
7. Show that $h$ is [injective](#def-b1-logic-inj) . (Three cases; in the mixed case $x \in C$ , $x' \notin C$ , show that $h(x) = h(x')$ would force $x' \in g(f(C)) \subseteq C$ .)
8. Show that $h$ is [surjective](#def-b1-logic-inj) : given $y \in F$ , distinguish the cases $g(y) \notin C$ and $g(y) \in C_n$ for some $n  \geq 1$ (why is $g(y) \in C_0$ impossible?), and exhibit a [preimage](#def-b1-logic-map) of $y$ in each case.
9. Conclude with the *Cantor–Schröder–Bernstein theorem* : if $E \preceq F$ and $F \preceq E$ , then $E  \approx F$ . Comment in one sentence on what makes this [statement](#def-b1-logic-statement) nontrivial.
10. Two applications. (a) Show $\intcc01 \approx \intoo01$ . (b) Show that $\varphi(p, q) = 2^p(2q + 1) - 1$ defines a bijection from $\N \times \N$ onto $\N$ — injectivity by a parity argument, surjectivity by strong induction ( [Theorem 1.12](#thm-b1-logic-induction) ). Hence $\N \times \N \approx  \N$ : the plane of integer points is no bigger than the line.

**Part III — [Countable sets](#pb-b1-logic-1).** Call a [set](#def-b1-logic-sets) $E$ *at most countable* when $E \preceq \N$, and *countable* when $E \approx \N$.

11. Show that every infinite subset $A \subseteq \N$ is countable. (Define $\varphi(n)$ recursively as the least element of $A \setminus \{\varphi(0), \dots,  \varphi(n-1)\}$ ; show $\varphi$ is strictly increasing, satisfies $\varphi(n) \geq n$ , and attains every element of $A$ .)
12. Deduce that a [set](#def-b1-logic-sets) is at most countable if and only if it is finite or countable, and observe that question 9 gives the shortcut: if $E \preceq \N$ and $\N \preceq E$ , then $E$ is countable.
13. Show that if $E$ and $F$ are at most countable, so is $E  \times F$ . Deduce that $\Z \times \N^*$ is countable.
14. Show that $\Q$ is countable. (Inject $\Q$ into $\Z \times  \N^*$ by writing each rational in lowest terms with positive denominator — the uniqueness of that representation is proved in [Chapter 6](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#ch-b1-arith) ; then apply question 12.)
15. Show that a countable union of at most [countable sets](#pb-b1-logic-1) is at most countable: if each $E_n$ ( $n \in \N$ ) is at most countable, so is $\bigcup_{n \in \N} E_n$ . (Send $x$ to the pair $(n, f_n(x))$ where $n$ is the *least* index with $x \in E_n$ .)
16. Show that the [set](#def-b1-logic-sets) of *finite* subsets of $\N$ is countable. (Map a finite subset $F$ to $\sum_{i \in F} 2^i$ ; prove injectivity by comparing the largest element where two finite [sets](#def-b1-logic-sets) differ, using $\sum_{k=0}^{m-1} 2^k = 2^m - 1$ from [Exercise 1.4](#exo-b1-logic-4) .)

**Part IV — Diagonalization.** Let $\{0,1\}^{\N}$ denote the [set](#def-b1-logic-sets) of all [maps](#def-b1-logic-map) $u \colon \N \to \{0, 1\}$, i.e. the [set](#def-b1-logic-sets) of binary sequences.

17. Construct a bijection between $\mathcal{P}(\N)$ and $\{0,1\}^{\N}$ (indicator functions).
18. (The diagonal argument) Let $\Phi \colon \N \to  \{0,1\}^{\N}$ be any [map](#def-b1-logic-map) . Consider the sequence $d$ defined by $d(n) = 1 - \Phi(n)(n)$ . Show that $d$ is not in the image of $\Phi$ , and conclude that $\{0,1\}^{\N}$ is *not* at most countable. Explain in one sentence why, through question 17, this is exactly Cantor’s theorem ( [Exercise 1.11](#exo-b1-logic-11) ) for $E = \N$ .
19. Admit — as familiar from school, and established rigorously in [Chapter 10](https://one-course.com/books/math/3/en/chapter/10-real-numbers#ch-b1-reals) — that every $x \in  \intco01$ has a unique *proper* decimal expansion $x =  0.d_1 d_2 d_3\dots$ (one not ending in an infinite string of $9$ s). Given any sequence $(x_n)_{n \geq 1}$ of elements of $\intco01$ , construct $x \in \intco01$ with $x \neq x_n$ for all $n$ : choose its $n$ -th digit to be $5$ if the $n$ -th digit of $x_n$ differs from $5$ , and $6$ otherwise. Justify carefully that $x$ is proper and avoids every $x_n$ , and conclude that $\intco01$ is not at most countable.
20. Deduce that $\R$ is uncountable, and that the [set](#def-b1-logic-sets) $\R  \setminus \Q$ of irrational numbers is uncountable as well. In what precise sense are “most” real numbers irrational?

**Part V — Cantor’s 1874 theorem: [transcendental numbers](#pb-b1-logic-1) exist.** A real number $x$ is *algebraic* when $P(x) = 0$ for some nonzero polynomial $P$ with integer coefficients, and *transcendental* otherwise. Admit for this part — it is proved in [Chapter 8](https://one-course.com/books/math/3/en/chapter/8-polynomials#ch-b1-poly) — that a nonzero polynomial of degree $n$ has at most $n$ real roots.

21. Show that every rational number is algebraic, and find explicit polynomials with integer coefficients annihilating $\sqrt 2$ and $\sqrt 2 + \sqrt 3$ .
22. For fixed $n \in \N$ , show that the [set](#def-b1-logic-sets) of polynomials of degree at most $n$ with integer coefficients is countable. (Inject it into $\Z^{n+1}$ and induct on $n$ with question 13.)
23. Deduce that the [set](#def-b1-logic-sets) of *all* polynomials with integer coefficients is countable.
24. Prove *Cantor’s theorem on [algebraic numbers](#pb-b1-logic-1)* : the [set](#def-b1-logic-sets) $\mathcal{A}$ of algebraic real numbers is countable.
25. Conclude: transcendental real numbers exist, and the [set](#def-b1-logic-sets) of [transcendental numbers](#pb-b1-logic-1) is uncountable. Then take stock of the whole problem in a few sentences: the chain $\N \approx  \Z \approx \Q \approx \mathcal{A}$ , the strict jump to $\R  \approx$ (essentially) $\mathcal{P}(\N)$ , where each tool (Cantor–Schröder–Bernstein, countable unions, the diagonal) was decisive — and the philosophical punch of proving that uncountably many [transcendental numbers](#pb-b1-logic-1) exist without naming even one. (Proving a *specific* number such as $\pi$ transcendental is far harder and beyond this volume.)

**Solution of Problem 1.1.**

**1.** *Reflexive:* $\mathrm{id}_E$ is a bijection of $E$ onto itself. *Symmetric:* if $f \colon E \to F$ is [bijective](#def-b1-logic-inj), [Theorem 1.24](#thm-b1-logic-inverse) provides $f^{-1} \colon F \to E$, itself [bijective](#def-b1-logic-inj). *Transitive:* if $f \colon E \to F$ and $g \colon F
\to G$ are bijections, [Proposition 1.26](#prop-b1-logic-comp) (1) says $g \circ f
\colon E \to G$ is a bijection. (This is only “like” an [equivalence relation](#def-b1-logic-equiv): the collection of all [sets](#def-b1-logic-sets) is not itself a [set](#def-b1-logic-sets), by the paradoxes that [Exercise 1.11](#exo-b1-logic-11) hints at; the three properties are what matters.)

**2.** If $f \colon E \to F$ and $g \colon F \to G$ are [injective](#def-b1-logic-inj), $g \circ f$ is [injective](#def-b1-logic-inj) by [Proposition 1.26](#prop-b1-logic-comp) (1): $E \preceq G$. For the second point, corestrict $f$ to its image: the [map](#def-b1-logic-map) $\tilde f \colon E \to f(E)$, $x \mapsto f(x)$, is [surjective](#def-b1-logic-inj) by construction of $f(E)$ and [injective](#def-b1-logic-inj) because $f$ is, hence [bijective](#def-b1-logic-inj): $E \approx f(E)$.

**3.** ($\Rightarrow$) Let $f \colon E \to F$ be [injective](#def-b1-logic-inj) and fix $a \in E$ ($E \neq \emptyset$). Define $s \colon F \to E$ by: $s(y)$ is the unique $x$ with $f(x) = y$ when $y \in f(E)$ (uniqueness by injectivity), and $s(y) = a$ otherwise. For every $x
\in E$, $s(f(x)) = x$, so every $x$ is attained: $s$ is [surjective](#def-b1-logic-inj). ($\Leftarrow$) Let $s \colon F \to E$ be [surjective](#def-b1-logic-inj). For each $x \in
E$ choose one $y_x \in F$ with $s(y_x) = x$, and set $u(x) = y_x$. If $u(x) = u(x')$ then $x = s(u(x)) = s(u(x')) = x'$: $u \colon E \to F$ is [injective](#def-b1-logic-inj).

**4.** $n \mapsto n + 1$ [maps](#def-b1-logic-map) $\N$ into $\N^*$, is [injective](#def-b1-logic-inj) ($n + 1 = m + 1 \implies n = m$) and [surjective](#def-b1-logic-inj) (every $m \geq 1$ is $(m - 1) + 1$ with $m - 1 \in \N$). For $\sigma$: it [maps](#def-b1-logic-map) even numbers $0, 2, 4, \dots$ to $0, 1, 2, \dots$ and odd numbers $1, 3,
5, \dots$ to $-1, -2, -3, \dots$ Injectivity: the even inputs land in $\N$ ($\sigma(n) = n/2 \geq 0$) and the odd inputs land in the strictly negative integers ($\sigma(n) = -(n+1)/2 \leq -1$), so a collision must happen within one parity class, where $\sigma$ is strictly monotonic ($n/2 = m/2$ or $(n+1)/2 = (m+1)/2$ forces $n =
m$). Surjectivity: $k \geq 0$ is $\sigma(2k)$; $k \leq -1$ is $\sigma(-2k - 1)$ with $-2k - 1 \geq 1$ odd. So $\N \approx \N^*$ and $\N \approx \Z$.

**5.** $C_0 = E \setminus g(F) \subseteq C$, so $x \notin C$ implies $x \notin C_0$, i.e. $x \in g(F)$: some $y \in F$ satisfies $g(y) = x$. If also $g(y') = x$, injectivity of $g$ gives $y' = y$. Hence the second clause of the definition of $h$ picks out a unique, well-defined element $g^{-1}(x)$.

**6.** Direct images commute with unions ([Exercise 1.8](#exo-b1-logic-8) (1), applied to $f$ then to $g$):

$$
g\bigl(f(C)\bigr)
= g\Bigl(f\Bigl(\bigcup_{n \in \N} C_n\Bigr)\Bigr)
= \bigcup_{n \in \N} g\bigl(f(C_n)\bigr)
= \bigcup_{n \in \N} C_{n+1}
= \bigcup_{n \geq 1} C_n \subseteq C .
$$

**7.** Let $x \neq x'$ in $E$. If both lie in $C$, then $h(x) =
f(x) \neq f(x') = h(x')$ by injectivity of $f$. If neither lies in $C$, then $g(h(x)) = x \neq x' = g(h(x'))$, so $h(x) \neq h(x')$. If $x \in C$ and $x' \notin C$ (the mixed case, up to swapping names): suppose $h(x) = h(x')$, i.e. $f(x) = g^{-1}(x')$. Applying $g$: $x' = g(f(x)) \in g(f(C))$, and question 6 gives $x' \in C$ — contradiction. So $h(x) \neq h(x')$ in all cases: $h$ is [injective](#def-b1-logic-inj).

**8.** Let $y \in F$. *Case 1: $g(y) \notin C$.* Then $h(g(y)) = g^{-1}(g(y)) = y$: the element $g(y)$ is a [preimage](#def-b1-logic-map). *Case 2: $g(y) \in C$*, say $g(y) \in C_n$. Since $g(y) \in
g(F)$, we have $g(y) \notin C_0 = E \setminus g(F)$, so $n \geq 1$ and $g(y) \in C_n = g(f(C_{n-1}))$: there is $x \in C_{n-1}$ with $g(y) = g(f(x))$. Injectivity of $g$ gives $y = f(x)$, and $x \in
C_{n-1} \subseteq C$, so $h(x) = f(x) = y$. In both cases $y$ is attained: $h$ is [surjective](#def-b1-logic-inj), hence [bijective](#def-b1-logic-inj).

**9.** If $E \preceq F$ and $F \preceq E$, pick injections $f
\colon E \to F$ and $g \colon F \to E$; questions 5–8 build a bijection $h \colon E \to F$, so $E \approx F$. The [statement](#def-b1-logic-statement) is nontrivial because the two given injections are unrelated — neither need be [surjective](#def-b1-logic-inj), and no formula mixing $f$ and $g$ naively defines a [map](#def-b1-logic-map): the whole content is the [partition](#thm-b1-logic-partition) of $E$ into the region $C$ (where one copies $f$) and its complement (where one runs $g$ backwards).

**10.** (a) The inclusion $\intoo01 \to \intcc01$ is [injective](#def-b1-logic-inj); and $x \mapsto \frac{x + 1}3$ [maps](#def-b1-logic-map) $\intcc01$ [injectively](#def-b1-logic-inj) into $\intcc{\frac13}{\frac23} \subseteq \intoo01$ (it is affine with nonzero slope). By question 9, $\intcc01 \approx \intoo01$ — a bijection which is quite unpleasant to write down explicitly. (b) *Injectivity.* Suppose $2^p(2q + 1) = 2^{p'}(2q' + 1)$ with, say, $p \leq p'$. Dividing by $2^p$: $2q + 1 = 2^{p' - p}(2q' + 1)$. If $p' > p$ the right side is even and the left side odd — impossible; so $p = p'$, then $2q + 1 = 2q' + 1$ and $q = q'$. *Surjectivity.* We show by strong induction that every integer $m \geq 1$ is of the form $2^p(2q + 1)$. For $m = 1$: $p = q = 0$. Let $m \geq 1$ and assume the claim for all integers of $\intint1m$. If $m + 1$ is odd, $m + 1 = 2q + 1$ with $p = 0$. If $m + 1$ is even, $m + 1 = 2m'$ with $1 \leq m' \leq m$; by hypothesis $m' = 2^p(2q + 1)$, so $m + 1 = 2^{p+1}(2q + 1)$. Hence $\varphi(p, q) = 2^p(2q + 1) - 1$ hits every $n \in \N$, and $\varphi$ is a bijection $\N \times \N \to \N$.

**11.** Since $A$ is infinite, $A \setminus \{\varphi(0), \dots,
\varphi(n - 1)\}$ is never empty, and the least-element property of $\N$ (used to prove [Theorem 1.12](#thm-b1-logic-induction)) makes the recursive definition legitimate. *Strictly increasing:* $\varphi(n + 1)$ belongs to $A \setminus \{\varphi(0), \dots,
\varphi(n)\} \subseteq A \setminus \{\varphi(0), \dots, \varphi(n -
1)\}$, whose minimum is $\varphi(n)$; so $\varphi(n + 1) \geq
\varphi(n)$, and equality is excluded, whence $\varphi(n+1) >
\varphi(n)$. *$\varphi(n) \geq n$:* by induction, $\varphi(0)
\geq 0$, and $\varphi(n + 1) \geq \varphi(n) + 1 \geq n + 1$. *Injectivity* follows from strict monotonicity. *Surjectivity onto $A$:* suppose some $a \in A$ is never attained. Since $\varphi(a + 1) \geq a + 1 > a$, the [set](#def-b1-logic-sets) of $n$ with $\varphi(n) > a$ is nonempty; let $n$ be its least element. For every $k < n$, $\varphi(k) \leq a$, hence $\varphi(k) < a$ ($a$ is not attained). Then $a$ lies in $A \setminus \{\varphi(0), \dots,
\varphi(n - 1)\}$ and $a < \varphi(n)$, contradicting the minimality defining $\varphi(n)$. So $\varphi$ is a bijection $\N \to A$, and $A$ is countable.

**12.** Let $E \preceq \N$ via an injection $f$; then $E \approx
f(E)$ (question 2). If $f(E)$ is finite, $E$ is finite; if $f(E)$ is infinite, question 11 gives $f(E) \approx \N$, so $E \approx \N$ by transitivity (question 1). Conversely finite [sets](#def-b1-logic-sets) and [countable sets](#pb-b1-logic-1) obviously inject into $\N$. The shortcut: $E \preceq \N$ and $\N
\preceq E$ give $E \approx \N$ directly by Cantor–Schröder–Bernstein — no enumeration argument needed.

**13.** Let $f \colon E \to \N$ and $g \colon F \to \N$ be injections. Then $(x, y) \mapsto \varphi\bigl(f(x), g(y)\bigr)$ is an injection $E \times F \to \N$: if the images coincide, injectivity of $\varphi$ (question 10) gives $f(x) = f(x')$ and $g(y) = g(y')$, then $x = x'$, $y = y'$. For $\Z \times \N^*$: both factors are countable (question 4), so $\Z \times \N^* \preceq \N$; it is infinite (it contains $\{0\} \times \N^*$), hence countable by question 12.

**14.** Every rational $r$ has a unique representation $r =
p/q$ with $p \in \Z$, $q \in \N^*$ and the fraction in lowest terms (uniqueness is proved in [Chapter 6](https://one-course.com/books/math/3/en/chapter/6-integer-arithmetic#ch-b1-arith); for $r = 0$ take $0/1$). The [map](#def-b1-logic-map) $r \mapsto (p, q)$ is then [injective](#def-b1-logic-inj): the pair determines $r = p/q$. Hence $\Q \preceq \Z \times \N^* \preceq \N$ by question 13. Since $\N \subseteq \Q$ gives $\N \preceq \Q$, question 12 (or Cantor–Schröder–Bernstein directly) shows $\Q
\approx \N$: the rationals are countable.

**15.** For each $n$ fix an injection $f_n \colon E_n \to \N$. For $x \in \bigcup_n E_n$, let $n(x)$ be the *least* $n$ with $x \in E_n$, and set $u(x) = \varphi\bigl(n(x), f_{n(x)}(x)\bigr)
\in \N$. If $u(x) = u(x')$, injectivity of $\varphi$ gives $n(x) =
n(x') = n$ and $f_n(x) = f_n(x')$, hence $x = x'$ by injectivity of $f_n$. So the union injects into $\N$: it is at most countable.

**16.** Let $\Psi(F) = \sum_{i \in F} 2^i$ for $F \subseteq \N$ finite ($\Psi(\emptyset) = 0$). Suppose $F \neq F'$ and let $m$ be the largest element on which they differ, say $m \in F \setminus
F'$ (swap names if needed). Elements $> m$ belong to both or neither, so they contribute equally to both sums; comparing the contributions of elements $\leq m$:

$$
\sum_{i \in F,\, i \leq m} 2^i \geq 2^m
> 2^m - 1 = \sum_{k=0}^{m-1} 2^k
\geq \sum_{i \in F',\, i \leq m} 2^i ,
$$

using the geometric sum of [Exercise 1.4](#exo-b1-logic-4). Hence $\Psi(F)
\neq \Psi(F')$: $\Psi$ is [injective](#def-b1-logic-inj) and the [set](#def-b1-logic-sets) of finite subsets of $\N$ is at most countable; it is infinite (it contains all singletons), hence countable.

**17.** Send $A \subseteq \N$ to its indicator $\mathbf 1_A
\colon \N \to \{0,1\}$, $\mathbf 1_A(n) = 1$ if $n \in A$ and $0$ otherwise; send $u \in \{0,1\}^{\N}$ to $A_u = \{n \in \N : u(n) =
1\}$. The two [maps](#def-b1-logic-map) are mutually inverse: $A_{\mathbf 1_A} = A$ and $\mathbf 1_{A_u} = u$ (check the value at each $n$). By [Theorem 1.24](#thm-b1-logic-inverse), each is a bijection: $\mathcal{P}(\N)
\approx \{0,1\}^{\N}$.

**18.** For every $n$, $d(n) = 1 - \Phi(n)(n) \neq \Phi(n)(n)$, so the sequences $d$ and $\Phi(n)$ differ at the index $n$: $d \neq
\Phi(n)$. Hence no $\Phi$ is [surjective](#def-b1-logic-inj), and by question 3 there is no injection $\{0,1\}^{\N} \to \N$ either: $\{0,1\}^{\N}$ is not at most countable. Through the dictionary of question 17, a [map](#def-b1-logic-map) $\Phi
\colon \N \to \{0,1\}^{\N}$ is a [map](#def-b1-logic-map) $f \colon \N \to
\mathcal{P}(\N)$, and $d$ corresponds to the [set](#def-b1-logic-sets) $D = \{n : n
\notin f(n)\}$ (indeed $d(n) = 1 \iff \Phi(n)(n) = 0 \iff n \notin
f(n)$): the diagonal argument *is* Cantor’s proof of [Exercise 1.11](#exo-b1-logic-11) for $E = \N$.

**19.** Write $x_n = 0.d_1(n)\,d_2(n)\,d_3(n)\dots$ in proper form and define $\delta_n = 5$ if $d_n(n) \neq 5$, $\delta_n = 6$ if $d_n(n) = 5$, then $x = 0.\delta_1\delta_2\delta_3\dots$ This expansion uses only the digits $5$ and $6$, so it does not end in all $9$s: it is the proper expansion of a real $x \in \intco01$. For each $n$, the $n$-th digits of $x$ and $x_n$ differ ($\delta_n \neq d_n(n)$ by construction); since proper expansions are unique, $x \neq x_n$. Thus no sequence exhausts $\intco01$: by question 3 again, $\intco01$ is not at most countable.

**20.** $\intco01 \subseteq \R$, so an injection $\R \to \N$ would restrict to one on $\intco01$, contradicting question 19: $\R$ is uncountable. If $\R \setminus \Q$ were at most countable, then $\R = \Q \cup (\R \setminus \Q)$ would be a union of two at most [countable sets](#pb-b1-logic-1), hence at most countable by question 15 (take $E_0 = \Q$, $E_n = \R \setminus \Q$ for $n \geq 1$) — contradiction. So the irrationals are uncountable. Precisely: inside $\R$, the rationals form a [countable set](#pb-b1-logic-1) while their complement is uncountable; no bijection can ever match $\R
\setminus \Q$ with $\Q$ — there are strictly “more” irrationals than rationals, even though both are infinite and both are dense.

**21.** $p/q$ (with $q \neq 0$) is a root of $qX - p$, a nonzero polynomial with integer coefficients. $\sqrt 2$ is a root of $X^2 - 2$. For $x = \sqrt 2 + \sqrt 3$: $x^2 = 5 + 2\sqrt 6$, so $x^2 - 5 = 2\sqrt 6$ and $(x^2 - 5)^2 = 24$, i.e.

$$
x^4 - 10x^2 + 1 = 0 :
$$

$\sqrt 2 + \sqrt 3$ is a root of $X^4 - 10X^2 + 1$.

**22.** Map $P = a_0 + a_1X + \dots + a_nX^n$ (degree $\leq n$, integer coefficients) to $(a_0, \dots, a_n) \in \Z^{n+1}$: this is [injective](#def-b1-logic-inj), since a polynomial is determined by its coefficients. By induction on $n$: $\Z^1 = \Z$ is countable (question 4), and $\Z^{n+2} \approx \Z^{n+1} \times \Z$ is at most countable by question 13. So each [set](#def-b1-logic-sets) of bounded-degree integer polynomials is at most countable; it is infinite (it contains the constants), hence countable by question 12.

**23.** The [set](#def-b1-logic-sets) of all integer polynomials is $\bigcup_{n \in
\N} \{P : \deg P \leq n,\ P \text{ has integer coefficients}\}$, a countable union of [countable sets](#pb-b1-logic-1): at most countable by question 15, infinite, hence countable.

**24.** For each nonzero integer polynomial $P$, the root [set](#def-b1-logic-sets) $R_P = \{x \in \R : P(x) = 0\}$ is finite (at most $\deg P$ elements, admitted). By question 23 the nonzero integer polynomials can be enumerated $P_0, P_1, P_2, \dots$; then $\mathcal{A} =
\bigcup_{n \in \N} R_{P_n}$ is a countable union of finite (hence at most countable) [sets](#def-b1-logic-sets): at most countable by question 15. It contains $\Q$ (question 21), so it is infinite: $\mathcal{A}$ is countable.

**25.** If $\R \setminus \mathcal{A}$ were at most countable, $\R = \mathcal{A} \cup (\R \setminus \mathcal{A})$ would be at most countable (question 15), contradicting question 20. Hence [transcendental numbers](#pb-b1-logic-1) exist and even form an uncountable [set](#def-b1-logic-sets), while the [algebraic numbers](#pb-b1-logic-1) — which include every number built from integers by radicals — form a mere countable skeleton inside $\R$. Summary of the architecture: questions 1–3 [set](#def-b1-logic-sets) up the comparison language; Cantor–Schröder–Bernstein (questions 5–9) let us prove equipotence by two easy injections instead of one clever bijection, and was used for $\intcc01 \approx \intoo01$, for $\Q$ and throughout Part V; the pairing bijection (question 10) powered products and countable unions (questions 13, 15), which in turn powered $\Q$, the integer polynomials and $\mathcal{A}$; the diagonal argument (questions 18–19) provided the one strict inequality $\N \prec \R$ that makes the whole story nontrivial. Cantor’s conclusion is philosophically striking: the proof exhibits no [transcendental number](#pb-b1-logic-1) at all, yet shows that in the sense of equipotence *almost every* real number is transcendental. Naming one specific transcendental — $\pi$ or $\eu$ — required entirely different mathematics and decades more work.