A.1 Sets and functions · Matrix Theory

This appendix collects the set-theoretic language that the book uses without comment: functions and their inverses, finite sets, induction, equivalence relations, and Zorn’s lemma. The main text cites the results here where they are needed. Several of them have linear counterparts in the main text (one-sided inverses of linear maps in Section 2.5, injectivity and surjectivity in Section 2.6, quotient spaces in Section 4.6), and comparing the two versions shows which parts of a linear-algebra argument are really about linearity.

A.1.1Sets

Notation A.1.1 (Sets). We write $𝑥 \in 𝑋$ when $𝑥$ is an element of the set $𝑋$ , and $𝐴 \subseteq 𝑋$ when every element of $𝐴$ is an element of $𝑋$ . Two sets are equal when they have the same elements, so $𝐴 = 𝐵$ means $𝐴 \subseteq 𝐵$ and $𝐵 \subseteq 𝐴$ (Technique 1.3.14). For subsets $𝐴, 𝐵 \subseteq 𝑋$ ,

𝐴 \cup 𝐵 = {𝑥 \in 𝑋 | 𝑥 \in 𝐴 or 𝑥 \in 𝐵}, 𝐴 \cap 𝐵 = {𝑥 \in 𝑋 | 𝑥 \in 𝐴 and 𝑥 \in 𝐵}, 𝑋 ∖ 𝐴 = {𝑥 \in 𝑋 | 𝑥 \notin 𝐴} .

The empty set is $\emptyset$ , and $𝐴$ and $𝐵$ are disjoint if $𝐴 \cap 𝐵 = \emptyset$ . The power set $𝑃 (𝑋)$ is the set of all subsets of $𝑋$ . The Cartesian product $𝑋 \times 𝑌$ is the set of ordered pairs $(𝑥, 𝑦)$ with $𝑥 \in 𝑋$ and $𝑦 \in 𝑌$ , and $𝑋^{𝑛}$ is the set of $𝑛$ -tuples of elements of $𝑋$ . For an integer $𝑛 \geq 0$ , we write $[𝑛] = {1, 2, \dots, 𝑛}$ , so that $[0] = \emptyset$ . Finally, $ℕ = {0, 1, 2, \dots}$ includes $0$ .

A.1.2Functions, images, and preimages

Definition A.1.2 (Function). A function (or map)

𝑓 : 𝑋 \to 𝑌

assigns to each element

𝑥 \in 𝑋

exactly one element

𝑓 (𝑥) \in 𝑌

. The set

𝑋

is the domain of

𝑓

and

𝑌

is its codomain. Two functions

𝑓, 𝑔 : 𝑋 \to 𝑌

are equal if

𝑓 (𝑥) = 𝑔 (𝑥)

for every

𝑥 \in 𝑋

. The identity of

𝑋

{id}_{𝑋} : 𝑋 \to 𝑋

{id}_{𝑋} (𝑥) = 𝑥

Formally, $𝑓$ is its graph ${(𝑥, 𝑓 (𝑥)) | 𝑥 \in 𝑋} \subseteq$ $𝑋 \times$ $𝑌$ , a subset that contains exactly one pair $(𝑥, 𝑦)$ for each $𝑥 \in 𝑋$ . The codomain is part of the data: $𝑥 \mapsto 𝑥^{2}$ from $ℝ$ to $ℝ$ and from $ℝ$ to $[0, \infty)$ are different functions, since the second is surjective and the first is not. For every set $𝑌$ there is exactly one function $\emptyset \to 𝑌$ , the empty function, and there is no function $𝑋 \to \emptyset$ when $𝑋 \neq \emptyset$ .

Definition A.1.3 (Image and preimage). Let $𝑓 : 𝑋 \to 𝑌$ . For $𝐴 \subseteq 𝑋$ , the image of $𝐴$ under $𝑓$ is

im (𝑓 ↾_{𝐴}) = {𝑓 (𝑎) | 𝑎 \in 𝐴} \subseteq 𝑌,

and the image of $𝑓$ is $im 𝑓 = im (𝑓 ↾_{𝑋})$ . For $𝐵 \subseteq 𝑌$ , the preimage of $𝐵$ under $𝑓$ is

𝑓^{- 1} (𝐵) = {𝑥 \in 𝑋 | 𝑓 (𝑥) \in 𝐵} \subseteq 𝑋 .

For $𝑦 \in 𝑌$ we write $𝑓^{- 1} (𝑦)$ for $𝑓^{- 1} ({𝑦})$ , the set of preimages of $𝑦$ , and call it the fiber of $𝑓$ over $𝑦$ .

The notation $im (𝑓 ↾_{𝐴})$ reads “the image of $𝑓$ restricted to $𝐴$ ”, which is what it is. The notation $𝑓^{- 1} (𝐵)$ does not presuppose that $𝑓$ has an inverse: every function has preimages, and a fiber $𝑓^{- 1} (𝑦)$ can be empty or have many elements. In this language, Definition 2.6.1, Definition 2.6.2 and Definition 2.6.3 say that $𝑓$ is injective, surjective, or bijective when every fiber has at most one, at least one, or exactly one element. For a linear map $𝑇$ , the kernel is the fiber $𝑇^{- 1} (𝟎)$ , and the solution set of $𝑇 (𝐯) = 𝐰$ is the fiber $𝑇^{- 1} (𝐰)$ .

Example A.1.4 (Images and preimages of

𝑥 \mapsto 𝑥^{2}

). Let

𝑓 : ℝ \to ℝ

𝑓 (𝑥) = 𝑥^{2}

. Then

im (𝑓 ↾_{[- 1, 2]}) =

[0, 4]

and

im 𝑓 = [0, \infty)

. Preimages:

𝑓^{- 1} ([1, 4]) =

[- 2, - 1] \cup

[1, 2]

𝑓^{- 1} (4) = {- 2, 2}

, and

𝑓^{- 1} (- 1) = \emptyset

. Taking the image and then the preimage can enlarge a set:

𝑓^{- 1} (im (𝑓 ↾_{[0, 1]})) =

𝑓^{- 1} ([0, 1]) =

[- 1, 1]

. Taking the preimage and then the image can shrink one:

im (𝑓 ↾_{𝑓^{- 1} ([- 1, 1])}) =

[0, 1]

The example shows the general pattern. Preimages respect all the set operations, images respect unions but not intersections, and the two operations undo each other exactly when $𝑓$ is injective (in one order) or surjective (in the other).

Proposition A.1.5 (Images and preimages). Let $𝑓 : 𝑋 \to 𝑌$ , let $𝐴, 𝐴^{'} \subseteq 𝑋$ , and let $𝐵, 𝐵^{'} \subseteq 𝑌$ .

(a) $𝑓^{- 1} (𝐵 \cup 𝐵^{'}) =$ $𝑓^{- 1} (𝐵) \cup$ $𝑓^{- 1} (𝐵^{'})$ , $𝑓^{- 1} (𝐵 \cap 𝐵^{'}) =$ $𝑓^{- 1} (𝐵) \cap$ $𝑓^{- 1} (𝐵^{'})$ , and $𝑓^{- 1} (𝑌 ∖ 𝐵) =$ $𝑋 ∖ 𝑓^{- 1} (𝐵)$ .
(b) $im (𝑓 ↾_{𝐴 \cup 𝐴^{'}}) =$ $im (𝑓 ↾_{𝐴}) \cup$ $im (𝑓 ↾_{𝐴^{'}})$ and $im (𝑓 ↾_{𝐴 \cap 𝐴^{'}}) \subseteq$ $im (𝑓 ↾_{𝐴}) \cap$ $im (𝑓 ↾_{𝐴^{'}})$ , with equality if $𝑓$ is injective.
(c) $𝐴 \subseteq$ $𝑓^{- 1} (im (𝑓 ↾_{𝐴}))$ , with equality if $𝑓$ is injective.
(d) $im (𝑓 ↾_{𝑓^{- 1} (𝐵)}) =$ $𝐵 \cap$ $im 𝑓$ . In particular $im (𝑓 ↾_{𝑓^{- 1} (𝐵)}) \subseteq$ $𝐵$ , with equality if $𝑓$ is surjective.

Proof.routine

Uses. Definition A.1.3 (Image and preimage), Definition 2.6.1 (Injective), Definition 2.6.2 (Surjective)

Techniques. Double containment (Technique 1.3.14), Fix an arbitrary element and chase it (Technique 1.3.13)

Hint 1. Each claim is an equality or containment of sets. Take a generic element of one side and unwind the definitions until it is visibly in the other side.

Hint 2. For preimages,

𝑥 \in 𝑓^{- 1} (𝐵)

is the statement

𝑓 (𝑥) \in 𝐵

, so (a) is the logic of “or”, “and”, and “not” applied to

𝑓 (𝑥)

. For images,

𝑦 \in im (𝑓 ↾_{𝐴})

means

𝑦 = 𝑓 (𝑎)

for some

𝑎 \in 𝐴

Hint 3. Injectivity enters when an element is written as a value in two ways: if

𝑦 = 𝑓 (𝑎) = 𝑓 (𝑎^{'})

with

𝑎 \in 𝐴

and

𝑎^{'} \in 𝐴^{'}

, then

𝑎 = 𝑎^{'} \in 𝐴 \cap 𝐴^{'}

Sketch. (a) unwinds to

𝑓 (𝑥) \in 𝐵 \cup 𝐵^{'}

iff

𝑓 (𝑥) \in 𝐵

𝑓 (𝑥) \in 𝐵^{'}

, and similarly for

\cap

and complements. In (b),

𝑓 (𝑎)

with

𝑎 \in 𝐴 \cup 𝐴^{'}

lies in one of the two images; for the intersection, a common value

𝑓 (𝑎) = 𝑓 (𝑎^{'})

forces

𝑎 = 𝑎^{'}

when

𝑓

is injective. (c):

𝑎 \in 𝐴

has

𝑓 (𝑎) \in im (𝑓 ↾_{𝐴})

; if

𝑓 (𝑥) = 𝑓 (𝑎)

and

𝑓

is injective, then

𝑥 = 𝑎

. (d): the values

𝑓 (𝑥)

with

𝑓 (𝑥) \in 𝐵

are exactly the elements of

𝐵

that are values.

(a) For $𝑥 \in 𝑋$ , $𝑥 \in 𝑓^{- 1} (𝐵 \cup 𝐵^{'})$ means $𝑓 (𝑥) \in 𝐵 \cup 𝐵^{'}$ , that is, $𝑓 (𝑥) \in 𝐵$ or $𝑓 (𝑥) \in 𝐵^{'}$ , that is, $𝑥 \in 𝑓^{- 1} (𝐵)$ or $𝑥 \in 𝑓^{- 1} (𝐵^{'})$ . The same unwinding with “and” proves the second equality. For the third, $𝑥 \in 𝑓^{- 1} (𝑌 ∖ 𝐵)$ means $𝑓 (𝑥) \notin 𝐵$ , that is, $𝑥 \notin 𝑓^{- 1} (𝐵)$ .

(b) An element of $im (𝑓 ↾_{𝐴 \cup 𝐴^{'}})$ is $𝑓 (𝑎)$ with $𝑎 \in 𝐴$ or $𝑎 \in 𝐴^{'}$ , so it lies in $im (𝑓 ↾_{𝐴})$ or in $im (𝑓 ↾_{𝐴^{'}})$ ; conversely, $im (𝑓 ↾_{𝐴})$ and $im (𝑓 ↾_{𝐴^{'}})$ are both contained in $im (𝑓 ↾_{𝐴 \cup 𝐴^{'}})$ . If $𝑎 \in 𝐴 \cap 𝐴^{'}$ , then $𝑓 (𝑎)$ lies in both images, which proves the containment. Now suppose $𝑓$ is injective and $𝑦 \in$ $im (𝑓 ↾_{𝐴}) \cap$ $im (𝑓 ↾_{𝐴^{'}})$ , say $𝑦 = 𝑓 (𝑎) = 𝑓 (𝑎^{'})$ with $𝑎 \in 𝐴$ and $𝑎^{'} \in 𝐴^{'}$ . Then $𝑎 = 𝑎^{'}$ , so $𝑎 \in 𝐴 \cap 𝐴^{'}$ and $𝑦 \in im (𝑓 ↾_{𝐴 \cap 𝐴^{'}})$ .

(c) If $𝑎 \in 𝐴$ , then $𝑓 (𝑎) \in im (𝑓 ↾_{𝐴})$ , so $𝑎 \in$ $𝑓^{- 1} (im (𝑓 ↾_{𝐴}))$ . Suppose $𝑓$ is injective and $𝑥 \in$ $𝑓^{- 1} (im (𝑓 ↾_{𝐴}))$ . Then $𝑓 (𝑥) = 𝑓 (𝑎)$ for some $𝑎 \in 𝐴$ , so $𝑥 = 𝑎 \in 𝐴$ .

(d) An element of $im (𝑓 ↾_{𝑓^{- 1} (𝐵)})$ is $𝑓 (𝑥)$ with $𝑓 (𝑥) \in 𝐵$ , so it lies in $𝐵 \cap im 𝑓$ . Conversely, if $𝑦 \in 𝐵 \cap im 𝑓$ , write $𝑦 = 𝑓 (𝑥)$ ; then $𝑥 \in 𝑓^{- 1} (𝐵)$ and $𝑦 \in$ $im (𝑓 ↾_{𝑓^{- 1} (𝐵)})$ . If $𝑓$ is surjective, then $im 𝑓 = 𝑌$ and $𝐵 \cap im 𝑓 = 𝐵$ . □

The hypotheses in (b), (c), and (d) cannot be dropped. For $𝑓 (𝑥) = 𝑥^{2}$ , the sets $𝐴 = {- 1}$ and $𝐴^{'} = {1}$ are disjoint, so $im (𝑓 ↾_{𝐴 \cap 𝐴^{'}}) = \emptyset$ , while $im (𝑓 ↾_{𝐴}) \cap$ $im (𝑓 ↾_{𝐴^{'}}) =$ ${1}$ ; Example A.1.4 does the same for (c) and (d). Exercise A.1.24 shows that injectivity is also necessary for equality in (b).

A.1.3Composition and inverses

Definition A.1.6 (Composition). For

𝑓 : 𝑋 \to 𝑌

and

𝑔 : 𝑌 \to 𝑍

, the composition

𝑔 \circ 𝑓 : 𝑋 \to 𝑍

is the function

(𝑔 \circ 𝑓) (𝑥) =

𝑔 (𝑓 (𝑥))

Composition is defined only when the codomain of $𝑓$ is the domain of $𝑔$ , and it is read right to left: $𝑔 \circ 𝑓$ applies $𝑓$ first. Even when both $𝑔 \circ 𝑓$ and $𝑓 \circ 𝑔$ are defined, they are usually different (Example 2.1.19 shows this for linear maps).

Proposition A.1.7 (Associativity and identities). Let

𝑓 : 𝑋 \to 𝑌

𝑔 : 𝑌 \to 𝑍

, and

ℎ : 𝑍 \to 𝑊

. Then

ℎ \circ

(𝑔 \circ 𝑓) =

(ℎ \circ 𝑔) \circ

𝑓

, and

𝑓 \circ

{id}_{𝑋} =

𝑓 =

{id}_{𝑌} \circ

𝑓

Proof.routine

Uses. Definition A.1.6 (Composition), Definition A.1.2 (Function)

Hint 1. Two functions

𝑋 \to 𝑊

are equal when they agree at every

𝑥 \in 𝑋

Hint 2. Evaluate both sides at

𝑥

and apply the definition of composition twice on each side.

Sketch. Both sides of the first identity send

𝑥

ℎ (𝑔 (𝑓 (𝑥)))

. Both

𝑓 \circ {id}_{𝑋}

and

{id}_{𝑌} \circ 𝑓

send

𝑥

𝑓 (𝑥)

Both sides are functions $𝑋 \to 𝑊$ . For $𝑥 \in 𝑋$ ,

(ℎ \circ (𝑔 \circ 𝑓)) (𝑥) = ℎ ((𝑔 \circ 𝑓) (𝑥)) = ℎ (𝑔 (𝑓 (𝑥))) = (ℎ \circ 𝑔) (𝑓 (𝑥)) = ((ℎ \circ 𝑔) \circ 𝑓) (𝑥) .

Similarly $(𝑓 \circ {id}_{𝑋}) (𝑥) =$ $𝑓 (𝑥) =$ ${id}_{𝑌} (𝑓 (𝑥)) =$ $({id}_{𝑌} \circ 𝑓) (𝑥)$ . □

So we may write $ℎ \circ 𝑔 \circ 𝑓$ without parentheses. The next proposition is used constantly, and its last two parts are easy to get backwards. If $𝑔 \circ 𝑓$ is injective, the function applied first must be injective, since a collision $𝑓 (𝑥) = 𝑓 (𝑥^{'})$ would survive into $𝑔 (𝑓 (𝑥)) =$ $𝑔 (𝑓 (𝑥^{'}))$ . If $𝑔 \circ 𝑓$ is surjective, the function applied last must be surjective, since every value of $𝑔 \circ 𝑓$ is a value of $𝑔$ .

Proposition A.1.8 (Composites, injectivity, and surjectivity). Let $𝑓 : 𝑋 \to 𝑌$ and $𝑔 : 𝑌 \to 𝑍$ .

(a)If $𝑓$ and $𝑔$ are injective, so is $𝑔 \circ 𝑓$ . If $𝑓$ and $𝑔$ are surjective, so is $𝑔 \circ 𝑓$ .
(b)If $𝑔 \circ 𝑓$ is injective, then $𝑓$ is injective.
(c)If $𝑔 \circ 𝑓$ is surjective, then $𝑔$ is surjective.

Proof.routine

Uses. Definition 2.6.1 (Injective), Definition 2.6.2 (Surjective), Definition A.1.6 (Composition)

Hint 1. For injectivity, start from

(𝑔 \circ 𝑓) (𝑥) =

(𝑔 \circ 𝑓) (𝑥^{'})

, or from

𝑓 (𝑥) = 𝑓 (𝑥^{'})

, and see what follows.

Hint 2. For (b), apply

𝑔

to both sides of

𝑓 (𝑥) = 𝑓 (𝑥^{'})

. For (c), every value of

𝑔 \circ 𝑓

𝑔

of something.

Sketch. (a) Peel off

𝑔

, then

𝑓

𝑔 (𝑓 (𝑥)) =

𝑔 (𝑓 (𝑥^{'}))

gives

𝑓 (𝑥) = 𝑓 (𝑥^{'})

, then

𝑥 = 𝑥^{'}

. For surjectivity, lift

𝑧

through

𝑔

, then through

𝑓

. (b)

𝑓 (𝑥) = 𝑓 (𝑥^{'})

gives

𝑔 (𝑓 (𝑥)) =

𝑔 (𝑓 (𝑥^{'}))

, so

𝑥 = 𝑥^{'}

. (c)

𝑧 = 𝑔 (𝑓 (𝑥))

is a value of

𝑔

(a) Suppose $𝑓$ and $𝑔$ are injective, and $𝑔 (𝑓 (𝑥)) =$ $𝑔 (𝑓 (𝑥^{'}))$ . Injectivity of $𝑔$ gives $𝑓 (𝑥) = 𝑓 (𝑥^{'})$ , and injectivity of $𝑓$ gives $𝑥 = 𝑥^{'}$ . Suppose $𝑓$ and $𝑔$ are surjective, and let $𝑧 \in 𝑍$ . Then $𝑧 = 𝑔 (𝑦)$ for some $𝑦 \in 𝑌$ , and $𝑦 = 𝑓 (𝑥)$ for some $𝑥 \in 𝑋$ , so $𝑧 = (𝑔 \circ 𝑓) (𝑥)$ .

(b) If $𝑓 (𝑥) = 𝑓 (𝑥^{'})$ , then $(𝑔 \circ 𝑓) (𝑥) =$ $𝑔 (𝑓 (𝑥)) =$ $𝑔 (𝑓 (𝑥^{'})) =$ $(𝑔 \circ 𝑓) (𝑥^{'})$ , so $𝑥 = 𝑥^{'}$ because $𝑔 \circ 𝑓$ is injective.

(c) Let $𝑧 \in 𝑍$ . Since $𝑔 \circ 𝑓$ is surjective, $𝑧 = 𝑔 (𝑓 (𝑥))$ for some $𝑥 \in 𝑋$ , so $𝑧$ is a value of $𝑔$ . □

Definition A.1.9 (One-sided inverses of a function). Let

𝑓 : 𝑋 \to 𝑌

. A function

𝑔 : 𝑌 \to 𝑋

is a left inverse of

𝑓

𝑔 \circ 𝑓 = {id}_{𝑋}

, and a right inverse of

𝑓

𝑓 \circ 𝑔 = {id}_{𝑌}

Definition A.1.10 (Inverse function). A function

𝑔 : 𝑌 \to 𝑋

is an inverse of

𝑓 : 𝑋 \to 𝑌

if it is both a left and a right inverse of

𝑓

, that is,

𝑔 \circ 𝑓 = {id}_{𝑋}

and

𝑓 \circ 𝑔 = {id}_{𝑌}

. If

𝑓

has an inverse,

𝑓

is invertible.

These are Definition 2.5.1, Definition 2.5.2 and Definition 2.5.12 without linearity. The definitions in Section 2.5 ask for more: there, a left inverse of a linear map must itself be linear. Remark 2.5.8 explains why that matters for one-sided inverses, and Proposition 2.7.7 shows that it does not matter for two-sided ones.

Example A.1.11 (The successor function). Let $𝑠 : ℕ \to ℕ$ , $𝑠 (𝑛) = 𝑛 + 1$ . For any $𝑐 \in ℕ$ , the function

𝑔_{𝑐} (𝑛) = {\begin{cases} 𝑛 - 1 & if 𝑛 \geq 1 \\ 𝑐 & if 𝑛 = 0 \end{cases}

satisfies $𝑔_{𝑐} (𝑠 (𝑛)) = 𝑛$ for all $𝑛$ , so every $𝑔_{𝑐}$ is a left inverse of $𝑠$ . The value at $0$ is free because $0$ is not a value of $𝑠$ . On the other hand, $𝑠$ has no right inverse: $𝑠 (𝑔 (0)) = 0$ is impossible for every function $𝑔$ , since $0 \notin im 𝑠$ . Multiplication by $𝑥$ on $𝐹 [𝑥]$ (Example 2.6.4(e)) is the linear version of $𝑠$ : it shifts coefficients up by one place.

Theorem A.1.12 (One-sided inverses of functions). Let $𝑓 : 𝑋 \to 𝑌$ .

(a)If $𝑓$ has a left inverse, then $𝑓$ is injective. Conversely, if $𝑓$ is injective and $𝑋 \neq \emptyset$ , then $𝑓$ has a left inverse.
(b) $𝑓$ has a right inverse if and only if $𝑓$ is surjective.

Intuition. A left inverse

𝑔

must send each value

𝑓 (𝑥)

back to

𝑥

. This is possible exactly when no value comes from two different inputs, and then

𝑔

is forced on

im 𝑓

and free elsewhere, which is where

𝑋 \neq \emptyset

is needed:

𝑔

needs somewhere to send the points outside

im 𝑓

. A right inverse must choose, for each

𝑦 \in 𝑌

, some preimage of

𝑦

. This is possible exactly when every

𝑦

has one, but there may be many, and

𝑔

chooses one in each fiber.

Proof.routine

Uses. Definition A.1.9 (One-sided inverses of a function), Definition 2.6.1 (Injective), Definition 2.6.2 (Surjective), Remark A.1.13 (The axiom of choice)

Techniques. Fix an arbitrary element and chase it (Technique 1.3.13)

Hint 1. The two “if” directions are one line each: apply

𝑔

𝑓 (𝑥) = 𝑓 (𝑥^{'})

, or apply

𝑓

𝑔 (𝑦)

Hint 2. For the converse in (a), define

𝑔

im 𝑓

by sending

𝑓 (𝑥)

𝑥

. Why is this a function there? What should

𝑔

do off

im 𝑓

Hint 3. For the converse in (b), each fiber

𝑓^{- 1} (𝑦)

is nonempty. Let

𝑔 (𝑦)

be an element of it.

Sketch. If

𝑔 \circ 𝑓 = {id}_{𝑋}

, then

𝑓 (𝑥) = 𝑓 (𝑥^{'})

gives

𝑥 =

𝑔 (𝑓 (𝑥)) =

𝑔 (𝑓 (𝑥^{'})) =

𝑥^{'}

. If

𝑓

is injective, each

𝑦 \in im 𝑓

has a unique preimage; send it there, and send every

𝑦 \notin im 𝑓

to a fixed

𝑥_{0} \in 𝑋

. If

𝑓 \circ 𝑔 = {id}_{𝑌}

, then

𝑦 = 𝑓 (𝑔 (𝑦))

is a value. If

𝑓

is surjective, choose

𝑔 (𝑦) \in 𝑓^{- 1} (𝑦)

for each

𝑦

; then

𝑓 (𝑔 (𝑦)) = 𝑦

(a) Suppose $𝑔 \circ 𝑓 = {id}_{𝑋}$ , and $𝑓 (𝑥) = 𝑓 (𝑥^{'})$ . Then $𝑥 =$ $𝑔 (𝑓 (𝑥)) =$ $𝑔 (𝑓 (𝑥^{'})) =$ $𝑥^{'}$ , so $𝑓$ is injective.

Conversely, suppose $𝑓$ is injective, and fix some $𝑥_{0} \in 𝑋$ . Each $𝑦 \in im 𝑓$ has exactly one preimage, which we call $𝑥_{𝑦}$ . Define $𝑔 : 𝑌 \to 𝑋$ by $𝑔 (𝑦) = 𝑥_{𝑦}$ if $𝑦 \in im 𝑓$ and $𝑔 (𝑦) = 𝑥_{0}$ otherwise. For every $𝑥 \in 𝑋$ , $𝑥$ is the preimage of $𝑓 (𝑥) \in im 𝑓$ , so $𝑔 (𝑓 (𝑥)) = 𝑥$ . Hence $𝑔 \circ 𝑓 = {id}_{𝑋}$ .

(b) If $𝑓 \circ 𝑔 = {id}_{𝑌}$ , then every $𝑦 \in 𝑌$ equals $𝑓 (𝑔 (𝑦))$ , so $𝑓$ is surjective. Conversely, suppose $𝑓$ is surjective. Then every fiber $𝑓^{- 1} (𝑦)$ is nonempty, and we let $𝑔 (𝑦)$ be an element of $𝑓^{- 1} (𝑦)$ for each $𝑦 \in 𝑌$ (Remark A.1.13). Then $𝑓 (𝑔 (𝑦)) = 𝑦$ for all $𝑦$ , so $𝑓 \circ 𝑔 = {id}_{𝑌}$ . □

Remark A.1.13 (The axiom of choice). The last step of the proof chooses an element of every fiber at once. When $𝑌$ is finite, these are finitely many choices, and induction on $| 𝑌 |$ makes the construction precise. In general, the step is an instance of the axiom of choice: for every family of nonempty sets ${(𝑆_{𝑖})}_{𝑖 \in 𝐼}$ there is a function $𝑐$ on $𝐼$ with $𝑐 (𝑖) \in 𝑆_{𝑖}$ for every $𝑖$ . Conversely, the axiom of choice follows from (b): given nonempty sets $𝑆_{𝑖}$ , the map $(𝑖, 𝑠) \mapsto 𝑖$ from the set of pairs ${(𝑖, 𝑠) | 𝑖 \in 𝐼, 𝑠 \in 𝑆_{𝑖}}$ to $𝐼$ is surjective, and if $𝑔$ is a right inverse of it, then $𝑐 (𝑖) =$ the second coordinate of $𝑔 (𝑖)$ is a choice function. So “every surjection has a right inverse” is the axiom of choice in another form. The left inverses in (a) need no choice, because $𝑔$ is forced on $im 𝑓$ and constant elsewhere.

The axiom is part of the standard foundations (ZFC), and we use it freely. Its most useful form for linear algebra is Zorn’s lemma (Section A.4), which shows that every vector space has a basis (Section 15.1).

When $𝑓$ is a bijection, neither half of the construction involves a choice, and the one-sided inverses merge.

Theorem A.1.14 (Bijections and inverses). Let $𝑓 : 𝑋 \to 𝑌$ .

(a)If $𝑓$ has a left inverse $𝑔$ and a right inverse $ℎ$ , then $𝑔 = ℎ$ . In particular, an inverse of $𝑓$ , if it exists, is unique. We denote it $𝑓^{- 1}$ .
(b) $𝑓$ is invertible if and only if $𝑓$ is bijective. In that case $𝑓^{- 1} (𝑦)$ is the unique preimage of $𝑦$ , and $𝑓^{- 1}$ is bijective with ${(𝑓^{- 1})}^{- 1} = 𝑓$ .
(c)If $𝑓 : 𝑋 \to 𝑌$ and $𝑔 : 𝑌 \to 𝑍$ are bijective, then so is $𝑔 \circ 𝑓$ , and ${(𝑔 \circ 𝑓)}^{- 1} =$ $𝑓^{- 1} \circ$ $𝑔^{- 1}$ .

Proof.routine

Uses. Proposition A.1.7 (Associativity and identities), Theorem A.1.12 (One-sided inverses of functions), Proposition A.1.8 (Composites, injectivity, and surjectivity), Definition A.1.10 (Inverse function)

Techniques. Uniqueness via two candidates (Technique 1.1.8)

Hint 1. For (a), evaluate

𝑔 \circ 𝑓 \circ ℎ

in two ways, using associativity.

Hint 2. For (b), “

\Rightarrow

” is Theorem A.1.12. For “

\Leftarrow

”, send each

𝑦

to its unique preimage; no choice and no

𝑥_{0}

is needed.

Hint 3. For (c), guess the inverse and check both composites.

Sketch.

𝑔 =

𝑔 \circ

(𝑓 \circ ℎ) =

(𝑔 \circ 𝑓) \circ

ℎ =

ℎ

. An invertible

𝑓

has one-sided inverses on both sides, so it is injective and surjective; a bijective

𝑓

is inverted by “the unique preimage”. The equations

𝑓^{- 1} \circ 𝑓 = id

𝑓 \circ 𝑓^{- 1} = id

say that

𝑓

is an inverse of

𝑓^{- 1}

. For (c),

𝑓^{- 1} \circ 𝑔^{- 1}

is an inverse of

𝑔 \circ 𝑓

by associativity.

(a) By Proposition A.1.7,

𝑔 = 𝑔 \circ {id}_{𝑌} = 𝑔 \circ (𝑓 \circ ℎ) = (𝑔 \circ 𝑓) \circ ℎ = {id}_{𝑋} \circ ℎ = ℎ .

If $𝑔$ and $ℎ$ are both inverses of $𝑓$ , then $𝑔$ is a left inverse and $ℎ$ is a right inverse, so $𝑔 = ℎ$ .

(b) If $𝑓$ is invertible, it has a left and a right inverse, so it is injective and surjective by Theorem A.1.12. Conversely, if $𝑓$ is bijective, every $𝑦 \in 𝑌$ has exactly one preimage $𝑥_{𝑦}$ . Let $𝑔 (𝑦) = 𝑥_{𝑦}$ . Then $𝑓 (𝑔 (𝑦)) = 𝑦$ , and $𝑔 (𝑓 (𝑥)) = 𝑥$ because $𝑥$ is the preimage of $𝑓 (𝑥)$ . So $𝑔$ is an inverse of $𝑓$ , and by (a) it is the only one. Finally, the equations $𝑓^{- 1} \circ 𝑓 = {id}_{𝑋}$ and $𝑓 \circ 𝑓^{- 1} = {id}_{𝑌}$ say that $𝑓$ is an inverse of $𝑓^{- 1}$ . So $𝑓^{- 1}$ is invertible, hence bijective, and ${(𝑓^{- 1})}^{- 1} = 𝑓$ by (a).

(c) By Proposition A.1.7,

(𝑓^{- 1} \circ 𝑔^{- 1}) \circ (𝑔 \circ 𝑓) = 𝑓^{- 1} \circ (𝑔^{- 1} \circ 𝑔) \circ 𝑓 = 𝑓^{- 1} \circ 𝑓 = {id}_{𝑋},

and similarly $(𝑔 \circ 𝑓) \circ$ $(𝑓^{- 1} \circ 𝑔^{- 1}) =$ ${id}_{𝑍}$ . So $𝑔 \circ 𝑓$ is invertible with the stated inverse, and bijective by (b). □

For a bijection $𝑓$ and $𝐵 \subseteq 𝑌$ , the preimage $𝑓^{- 1} (𝐵)$ of Definition A.1.3 equals the image $im (𝑓^{- 1} ↾_{𝐵})$ of $𝐵$ under the inverse function, so the two meanings of $𝑓^{- 1} (𝐵)$ agree whenever both make sense.

Exercise A.1.15.routine Prove or disprove: if

𝑓 : 𝑋 \to 𝑌

has exactly one left inverse, then

𝑓

is bijective.

Solution.

Uses. Theorem A.1.12 (One-sided inverses of functions), Theorem A.1.14 (Bijections and inverses)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. The construction of a left inverse is forced on

im 𝑓

and free elsewhere. When is the freedom not really a freedom?

Hint 2. Try

𝑋

with one element.

Sketch. False. If

𝑋 = {1}

and

𝑌 = {1, 2}

, then every function

𝑌 \to 𝑋

is constant, so the inclusion

𝑓 : 𝑋 \to 𝑌

has exactly one left inverse, but it is not surjective.

The claim is false. Let $𝑋 = {1}$ , $𝑌 = {1, 2}$ , and $𝑓 (1) = 1$ . There is exactly one function $𝑌 \to 𝑋$ , the constant function $𝑔$ with value $1$ , and $𝑔 (𝑓 (1)) = 1$ , so $𝑓$ has exactly one left inverse. But $2 \notin im 𝑓$ , so $𝑓$ is not surjective.

The claim becomes true when $𝑋$ has at least two elements. A left inverse exists only if $𝑓$ is injective (Theorem A.1.12), and it is forced on $im 𝑓$ . If some $𝑦 \in 𝑌$ is not in $im 𝑓$ , changing the value at $𝑦$ to any other element of $𝑋$ gives a second left inverse. So a unique left inverse forces $im 𝑓 = 𝑌$ , and $𝑓$ is bijective.

A.1.4Finite sets and counting

A finite set is one whose elements can be listed as $𝑥_{1}, \dots, 𝑥_{𝑛}$ without repetition, which is a bijection $[𝑛] \to 𝑋$ . That the number $𝑛$ does not depend on the listing is a theorem, and the same theorem is behind every counting argument in the book.

Definition A.1.16 (Finite set and cardinality). A set

𝑋

is finite with

𝑛

elements if there is a bijection

[𝑛] \to 𝑋

for some integer

𝑛 \geq 0

. We then write

| 𝑋 | = 𝑛

, the cardinality of

𝑋

. A set that is not finite is infinite.

Theorem A.1.17 (Pigeonhole principle). If

𝑚 > 𝑛 \geq 0

, there is no injective function

[𝑚] \to [𝑛]

Intuition. We induct on the number

𝑛

of boxes. Given an injection

[𝑚] \to [𝑛]

, we want an injection

[𝑚 - 1] \to [𝑛 - 1]

, so we delete the last box and one object. The object to delete is the one in box

𝑛

, if any; after swapping it into position

𝑚

, the rest of the objects avoid box

𝑛

Proof.standard

Uses. Theorem A.2.1 (Induction, strong induction, and well-ordering), Proposition A.1.8 (Composites, injectivity, and surjectivity)

Hint 1. Induct on

𝑛

. For

𝑛 = 0

, is there any function

[𝑚] \to \emptyset

with

𝑚 \geq 1

Hint 2. Given an injection

𝑓 : [𝑚] \to [𝑛]

, you want an injection

[𝑚 - 1] \to [𝑛 - 1]

. If

𝑛 \notin im 𝑓

, restrict

𝑓

[𝑚 - 1]

Hint 3. If

𝑓 (𝑘) = 𝑛

, first compose

𝑓

with the bijection of

[𝑚]

that swaps

𝑘

and

𝑚

. The new function sends

𝑚

𝑛

and, being injective, sends nothing else there.

Sketch. Induction on

𝑛

. For

𝑛 = 0

there is no function

[𝑚] \to \emptyset

. For the step, let

𝑓 : [𝑚] \to [𝑛]

be injective. Compose with the swap of

𝑘

and

𝑚

, where

𝑓 (𝑘) = 𝑛

(if

𝑛 \in im 𝑓

), so that only

𝑚

can map to

𝑛

. Then

𝑓

restricted to

[𝑚 - 1]

is an injection into

[𝑛 - 1]

with

𝑚 - 1 > 𝑛 - 1

, which contradicts the induction hypothesis.

We use induction on $𝑛$ (Theorem A.2.1). For $𝑛 = 0$ and $𝑚 \geq 1$ there is no function $[𝑚] \to [0] = \emptyset$ at all, since $1 \in [𝑚]$ would need a value.

Let $𝑛 \geq 1$ , suppose that there is no injection $[𝑚^{'}] \to [𝑛 - 1]$ whenever $𝑚^{'} > 𝑛 - 1$ , and suppose for contradiction that $𝑓 : [𝑚] \to [𝑛]$ is injective with $𝑚 > 𝑛$ . We first arrange that only $𝑚$ can map to $𝑛$ . If $𝑛 = 𝑓 (𝑘)$ for some $𝑘 \in [𝑚]$ , let $𝜏 : [𝑚] \to [𝑚]$ swap $𝑘$ and $𝑚$ and fix everything else. Then $𝜏$ is a bijection, so $𝑓^{'} = 𝑓 \circ 𝜏$ is injective (Proposition A.1.8), and $𝑓^{'} (𝑚) = 𝑓 (𝑘) = 𝑛$ . If $𝑛 \notin im 𝑓$ , let $𝑓^{'} = 𝑓$ . In either case, $𝑓^{'}$ is injective and no $𝑖 \in [𝑚 - 1]$ has $𝑓^{'} (𝑖) = 𝑛$ : in the first case because $𝑓^{'} (𝑖) =$ $𝑛 =$ $𝑓^{'} (𝑚)$ would force $𝑖 = 𝑚$ , and in the second because $𝑛$ is not a value at all. So the restriction of $𝑓^{'}$ to $[𝑚 - 1]$ is an injective function $[𝑚 - 1] \to [𝑛 - 1]$ . Since $𝑚 - 1 > 𝑛 - 1$ , this contradicts the induction hypothesis. □

Corollary A.1.18 (Cardinality is well defined). Let $𝑋$ and $𝑌$ be finite.

(a)If there are bijections $[𝑚] \to 𝑋$ and $[𝑛] \to 𝑋$ , then $𝑚 = 𝑛$ . So $| 𝑋 |$ is well defined.
(b)If there is an injection $𝑋 \to 𝑌$ , then $| 𝑋 | \leq | 𝑌 |$ . There is a bijection $𝑋 \to 𝑌$ if and only if $| 𝑋 | = | 𝑌 |$ .

Proof.routine

Uses. Theorem A.1.17 (Pigeonhole principle), Theorem A.1.14 (Bijections and inverses), Proposition A.1.8 (Composites, injectivity, and surjectivity)

Hint 1. Transport the question to

[𝑚]

and

[𝑛]

by composing with the given bijections and their inverses.

Hint 2. In (a),

𝜓^{- 1} \circ 𝜑 : [𝑚] \to [𝑛]

is a bijection; apply Theorem A.1.17 in both directions.

Sketch. With bijections

𝜑 : [𝑚] \to 𝑋

and

𝜓 : [𝑛] \to 𝑌

, an injection

𝑓 : 𝑋 \to 𝑌

gives the injection

𝜓^{- 1} \circ

𝑓 \circ

𝜑 : [𝑚] \to

[𝑛]

, so

𝑚 \leq 𝑛

by pigeonhole. Part (a) is the case

𝑌 = 𝑋

𝑓 = {id}_{𝑋}

, applied in both directions. A bijection

𝑋 \to 𝑌

exists when

𝑚 = 𝑛

by composing

𝜓 \circ 𝜑^{- 1}

Let $𝜑 : [𝑚] \to 𝑋$ and $𝜓 : [𝑛] \to 𝑌$ be bijections. If $𝑓 : 𝑋 \to 𝑌$ is injective, then $𝜓^{- 1} \circ$ $𝑓 \circ$ $𝜑 : [𝑚] \to$ $[𝑛]$ is injective by Proposition A.1.8, since bijections are injective (Theorem A.1.14). By Theorem A.1.17, $𝑚 \leq 𝑛$ .

(a) Take $𝑌 = 𝑋$ and $𝑓 = {id}_{𝑋}$ : with two bijections $𝜑 : [𝑚] \to 𝑋$ and $𝜓 : [𝑛] \to 𝑋$ , the argument above gives $𝑚 \leq 𝑛$ , and exchanging their roles gives $𝑛 \leq 𝑚$ .

(b) The first claim is the argument above. If $𝑓 : 𝑋 \to 𝑌$ is a bijection, it is injective, and so is $𝑓^{- 1}$ , which gives $| 𝑋 | \leq | 𝑌 | \leq | 𝑋 |$ . Conversely, if $𝑚 = 𝑛$ , then $𝜓 \circ 𝜑^{- 1} : 𝑋 \to 𝑌$ is a bijection by Theorem A.1.14(c). □

Proposition A.1.19 (Subsets of finite sets). Let

𝑋

be finite and

𝐴 \subseteq 𝑋

. Then

𝐴

is finite and

| 𝐴 | \leq | 𝑋 |

, with equality if and only if

𝐴 = 𝑋

Proof.standard

Uses. Corollary A.1.18 (Cardinality is well defined), Theorem A.2.1 (Induction, strong induction, and well-ordering), Definition A.1.16 (Finite set and cardinality)

Hint 1. A bijection

[𝑛] \to 𝑋

carries subsets of

[𝑛]

to subsets of

𝑋

of the same size, so it suffices to treat

𝑋 = [𝑛]

Hint 2. Induct on

𝑛

. For

𝐴 \subseteq [𝑛]

, apply the hypothesis to

𝐴 \cap [𝑛 - 1]

and then ask whether

𝑛 \in 𝐴

Sketch. Reduce to

𝑋 = [𝑛]

via a bijection

𝜑 : [𝑛] \to 𝑋

, replacing

𝐴

by its preimage. Induct on

𝑛

. Write

𝐴^{'} = 𝐴 \cap [𝑛 - 1]

, with

| 𝐴^{'} | = 𝑘 \leq 𝑛 - 1

and equality only for

𝐴^{'} = [𝑛 - 1]

. If

𝑛 \notin 𝐴

, then

𝐴 = 𝐴^{'}

and

| 𝐴 | < 𝑛

. If

𝑛 \in 𝐴

, extend a bijection

[𝑘] \to 𝐴^{'}

𝑘 + 1 \mapsto 𝑛

to get

| 𝐴 | = 𝑘 + 1 \leq 𝑛

, with equality only if

𝐴^{'} = [𝑛 - 1]

, that is,

𝐴 = [𝑛]

Let $𝜑 : [𝑛] \to 𝑋$ be a bijection and $𝐴_{0} = 𝜑^{- 1} (𝐴) \subseteq [𝑛]$ . Then $𝜑$ restricts to a bijection $𝐴_{0} \to 𝐴$ , so $𝐴$ is finite with $| 𝐴 | = | 𝐴_{0} |$ once $𝐴_{0}$ is, and $𝐴 = 𝑋$ if and only if $𝐴_{0} = [𝑛]$ . So we may assume $𝑋 = [𝑛]$ , and we induct on $𝑛$ . If $𝑛 = 0$ , then $𝐴 = \emptyset = [0]$ .

Let $𝑛 \geq 1$ and $𝐴 \subseteq [𝑛]$ . By the induction hypothesis, $𝐴^{'} = 𝐴 \cap [𝑛 - 1]$ is finite with $𝑘 = | 𝐴^{'} | \leq 𝑛 - 1$ , and $𝑘 = 𝑛 - 1$ only if $𝐴^{'} = [𝑛 - 1]$ . If $𝑛 \notin 𝐴$ , then $𝐴 = 𝐴^{'}$ , so $𝐴$ is finite with $| 𝐴 | \leq 𝑛 - 1 < 𝑛$ . If $𝑛 \in 𝐴$ , then $𝐴 = 𝐴^{'} \cup {𝑛}$ with $𝑛 \notin 𝐴^{'}$ . A bijection $[𝑘] \to 𝐴^{'}$ , extended by $𝑘 + 1 \mapsto 𝑛$ , is a bijection $[𝑘 + 1] \to 𝐴$ , so $| 𝐴 | = 𝑘 + 1 \leq 𝑛$ . Equality holds if and only if $𝑘 = 𝑛 - 1$ , that is, $𝐴^{'} = [𝑛 - 1]$ , and since $𝑛 \in 𝐴$ this means $𝐴 = [𝑛]$ . □

For finite sets of the same size, half of bijectivity is free. This is the set-theoretic model for Corollary 4.2.18, where an operator on a finite-dimensional space is injective if and only if it is surjective; there, dimension plays the role of cardinality.

Theorem A.1.20 (Injective, surjective, and bijective for finite sets). Let

𝑋

and

𝑌

be finite with

| 𝑋 | = | 𝑌 |

, and let

𝑓 : 𝑋 \to 𝑌

. Then

𝑓

is injective if and only if

𝑓

is surjective, and hence if and only if

𝑓

is bijective.

Proof.standard

Uses. Proposition A.1.19 (Subsets of finite sets), Corollary A.1.18 (Cardinality is well defined), Theorem A.1.12 (One-sided inverses of functions), Theorem A.1.14 (Bijections and inverses)

Hint 1. If

𝑓

is injective, then

𝑓

is a bijection from

𝑋

onto

im 𝑓

. What does that say about

| im 𝑓 |

Hint 2. Use Proposition A.1.19 to compare

im 𝑓

with

𝑌

Hint 3. For the converse, a surjection has a right inverse

𝑔 : 𝑌 \to 𝑋

, which is injective. Apply the first half to

𝑔

Sketch. If

𝑓

is injective,

𝑓 : 𝑋 \to im 𝑓

is a bijection, so

| im 𝑓 | = | 𝑋 | = | 𝑌 |

, and

im 𝑓 = 𝑌

by Proposition A.1.19. If

𝑓

is surjective, it has a right inverse

𝑔

, which is injective (it has the left inverse

𝑓

), hence bijective by the first half; then

𝑓 =

𝑓 \circ

𝑔 \circ

𝑔^{- 1} =

𝑔^{- 1}

is bijective.

Suppose $𝑓$ is injective. Then $𝑓$ , viewed as a function $𝑋 \to im 𝑓$ , is a bijection, so $| im 𝑓 | = | 𝑋 | = | 𝑌 |$ by Corollary A.1.18. Since $im 𝑓 \subseteq 𝑌$ , Proposition A.1.19 gives $im 𝑓 = 𝑌$ , and $𝑓$ is surjective.

Suppose $𝑓$ is surjective. By Theorem A.1.12(b) it has a right inverse $𝑔 : 𝑌 \to 𝑋$ . Since $𝑓 \circ 𝑔 = {id}_{𝑌}$ , $𝑓$ is a left inverse of $𝑔$ , so $𝑔$ is injective by Theorem A.1.12(a). As $| 𝑌 | = | 𝑋 |$ , the first half applied to $𝑔$ shows that $𝑔$ is bijective. Then

𝑓 = 𝑓 \circ (𝑔 \circ 𝑔^{- 1}) = (𝑓 \circ 𝑔) \circ 𝑔^{- 1} = 𝑔^{- 1},

so $𝑓$ is bijective by Theorem A.1.14(b). (Here $𝑌$ is finite, so the choice of $𝑔$ needs no axiom of choice.) □

The successor function $𝑠 (𝑛) = 𝑛 + 1$ on $ℕ$ (Example A.1.11) is injective and not surjective, so Theorem A.1.20 fails for infinite sets. It is one way of saying that $ℕ$ is infinite.

Technique A.1.21 (Pigeonhole). If a function goes from a finite set to a smaller one, two inputs share a value (Theorem A.1.17). In practice: more than $𝑛$ objects in $𝑛$ boxes put two objects in one box. The skill is in choosing the boxes, which are often the values of some quantity that can take only $𝑛$ values, such as a remainder mod $𝑛$ or an element of a finite field or of a finite set of matrices.

Reach for it when a statement claims that some coincidence or repetition must occur, but gives no way to find it. A typical consequence is that a sequence in a finite set repeats, so an invertible operation applied repeatedly eventually returns to the start. The canonical example is Example A.1.22; the cycle decomposition of permutations (Section 5.2) uses the same idea.

Used in 1 place and 1 practice exercise

Exercise A.1.29; 1 practice exercise.

Example A.1.22 (Powers of a matrix over a finite field). Let $𝐹$ be a finite field with $𝑞$ elements and $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ invertible. We show that $𝐴^{𝑘} = 𝐼_{𝑛}$ for some $𝑘$ with $1 \leq 𝑘 \leq 𝑞^{𝑛^{2}}$ .

The set $𝐹^{𝑛 \times 𝑛}$ has $𝑁 = 𝑞^{𝑛^{2}}$ elements (Exercise A.1.28). The function $𝑖 \mapsto 𝐴^{𝑖}$ from ${0, 1, \dots, 𝑁}$ , a set of $𝑁 + 1$ elements, to $𝐹^{𝑛 \times 𝑛}$ is not injective by Theorem A.1.17 (composed with bijections to $[𝑁 + 1]$ and $[𝑁]$ ). So $𝐴^{𝑖} = 𝐴^{𝑗}$ for some $0 \leq 𝑖 < 𝑗 \leq 𝑁$ . Multiplying by ${(𝐴^{- 1})}^{𝑖}$ gives $𝐼_{𝑛} = 𝐴^{𝑗 - 𝑖}$ , and $𝑘 = 𝑗 - 𝑖$ satisfies $1 \leq 𝑘 \leq 𝑁$ .

For example, over $𝔽_{2}$ the matrix $𝐴 = (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix})$ has $𝐴^{2} = (\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix})$ and $𝐴^{3} = 𝐼_{2}$ , much sooner than the bound $2^{4} = 16$ . Over $ℝ$ the conclusion fails: ${(\begin{matrix} 2 & 0 \\ 0 & 1 \end{matrix})}^{𝑘} \neq 𝐼_{2}$ for every $𝑘 \geq 1$ .

Exercises

Exercise A.1.23.routine Let

𝑓 : ℝ \to ℝ

𝑓 (𝑥) = 𝑥^{2} - 2 𝑥

. Compute

im (𝑓 ↾_{[0, 3]})

𝑓^{- 1} ([- 1, 0])

, and

𝑓^{- 1} (im (𝑓 ↾_{[0, 1]}))

. Which part of Proposition A.1.5 does the last answer illustrate?

Solution.

Uses. Definition A.1.3 (Image and preimage), Proposition A.1.5 (Images and preimages)

Hint 1. Complete the square:

𝑓 (𝑥) = {(𝑥 - 1)}^{2} - 1

Hint 2.

𝑓 (𝑥) \leq 0

means

{(𝑥 - 1)}^{2} \leq 1

. On

[0, 1]

𝑓

decreases from

0

- 1

Sketch. With

𝑓 (𝑥) = {(𝑥 - 1)}^{2} - 1

: on

[0, 3]

the values fill

[- 1, 3]

;

𝑓 (𝑥) \in [- 1, 0]

iff

| 𝑥 - 1 | \leq 1

, so the preimage is

[0, 2]

;

im (𝑓 ↾_{[0, 1]}) =

[- 1, 0]

, whose preimage is

[0, 2] ⊋ [0, 1]

, illustrating (c) for a non-injective

𝑓

Write $𝑓 (𝑥) = {(𝑥 - 1)}^{2} - 1$ . For $𝑥 \in [0, 3]$ , $𝑥 - 1$ ranges over $[- 1, 2]$ , so ${(𝑥 - 1)}^{2}$ ranges over $[0, 4]$ and $im (𝑓 ↾_{[0, 3]}) =$ $[- 1, 3]$ .

Every value of $𝑓$ is at least $- 1$ , so $𝑓 (𝑥) \in [- 1, 0]$ if and only if ${(𝑥 - 1)}^{2} \leq 1$ , that is, $| 𝑥 - 1 | \leq 1$ . Hence $𝑓^{- 1} ([- 1, 0]) =$ $[0, 2]$ .

For $𝑥 \in [0, 1]$ , ${(𝑥 - 1)}^{2}$ ranges over $[0, 1]$ , so $im (𝑓 ↾_{[0, 1]}) =$ $[- 1, 0]$ , and by the previous computation $𝑓^{- 1} (im (𝑓 ↾_{[0, 1]})) =$ $[0, 2]$ . This strictly contains $[0, 1]$ , as Proposition A.1.5(c) allows: $𝑓$ is not injective, since $𝑓 (1 - 𝑡) = 𝑓 (1 + 𝑡)$ .

Exercise A.1.24.standard Let

𝑓 : 𝑋 \to 𝑌

. Show that

𝑓

is injective if and only if

im (𝑓 ↾_{𝐴 \cap 𝐴^{'}}) =

im (𝑓 ↾_{𝐴}) \cap

im (𝑓 ↾_{𝐴^{'}})

for all subsets

𝐴, 𝐴^{'} \subseteq 𝑋

Solution.

Uses. Proposition A.1.5 (Images and preimages), Definition 2.6.1 (Injective)

Techniques. Contrapositive (Technique 1.5.4)

Hint 1. One direction is Proposition A.1.5(b).

Hint 2. For the other, suppose

𝑓 (𝑥) = 𝑓 (𝑥^{'})

with

𝑥 \neq 𝑥^{'}

, and choose

𝐴

and

𝐴^{'}

as small as possible.

Sketch. If

𝑓

is injective, this is Proposition A.1.5(b). If

𝑓 (𝑥) = 𝑓 (𝑥^{'})

with

𝑥 \neq 𝑥^{'}

, then

𝐴 = {𝑥}

and

𝐴^{'} = {𝑥^{'}}

give

im (𝑓 ↾_{𝐴 \cap 𝐴^{'}}) = \emptyset

but

im (𝑓 ↾_{𝐴}) \cap

im (𝑓 ↾_{𝐴^{'}}) =

{𝑓 (𝑥)}

If $𝑓$ is injective, the equality is Proposition A.1.5(b). We prove the converse by contrapositive. Suppose $𝑓$ is not injective, say $𝑓 (𝑥) = 𝑓 (𝑥^{'})$ with $𝑥 \neq 𝑥^{'}$ . Let $𝐴 = {𝑥}$ and $𝐴^{'} = {𝑥^{'}}$ . Then $𝐴 \cap 𝐴^{'} = \emptyset$ , so $im (𝑓 ↾_{𝐴 \cap 𝐴^{'}}) = \emptyset$ , while

im (𝑓 ↾_{𝐴}) \cap im (𝑓 ↾_{𝐴^{'}}) = {𝑓 (𝑥)} \cap {𝑓 (𝑥^{'})} = {𝑓 (𝑥)} \neq \emptyset .

So the equality fails for this pair.

Exercise A.1.25.routine Let $𝑓 : 𝑋 \to 𝑌$ and $𝑔 : 𝑌 \to 𝑍$ . Prove or disprove each claim.

(a)If $𝑔 \circ 𝑓$ is injective, then $𝑔$ is injective.
(b)If $𝑔 \circ 𝑓$ is bijective, then $𝑓$ is injective and $𝑔$ is surjective.
(c)If $𝑔 \circ 𝑓$ is bijective, then $𝑓$ and $𝑔$ are bijective.

Solution.

Uses. Proposition A.1.8 (Composites, injectivity, and surjectivity)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. (b) is Proposition A.1.8. For (a) and (c), make

𝑌

bigger than

𝑋

and

𝑍

Hint 2. Try

𝑋 = 𝑍 = {1}

and

𝑌 = {1, 2}

Sketch. (a) False:

𝑋 = 𝑍 = {1}

𝑌 = {1, 2}

𝑓 (1) = 1

𝑔

constant;

𝑔 \circ 𝑓 = id

is injective,

𝑔

is not. (b) True by Proposition A.1.8(b), (c). (c) False by the same example:

𝑓

is not surjective and

𝑔

is not injective.

Let $𝑋 = 𝑍 = {1}$ , $𝑌 = {1, 2}$ , $𝑓 (1) = 1$ , and let $𝑔 : 𝑌 \to 𝑍$ be the constant function with value $1$ . Then $𝑔 \circ 𝑓 = {id}_{𝑋}$ is bijective.

(a) False: in the example, $𝑔 \circ 𝑓$ is injective but $𝑔 (1) = 𝑔 (2)$ .

(b) True. If $𝑔 \circ 𝑓$ is bijective, it is injective, so $𝑓$ is injective by Proposition A.1.8(b), and it is surjective, so $𝑔$ is surjective by Proposition A.1.8(c).

(c) False: in the example, $𝑓$ is not surjective ( $2 \notin im 𝑓$ ) and $𝑔$ is not injective. By (b), what is true is that $𝑓$ is injective and $𝑔$ surjective; if moreover $| 𝑋 | = | 𝑌 | = | 𝑍 |$ are finite, then both are bijective by Theorem A.1.20.

Exercise A.1.26.standard Let

𝑓 : 𝑋 \to 𝑌

. Show that

𝑓

is injective if and only if it can be cancelled on the left: for every set

𝑊

and all functions

𝑔, ℎ : 𝑊 \to 𝑋

𝑓 \circ 𝑔 = 𝑓 \circ ℎ

implies

𝑔 = ℎ

. State and prove the analogous characterization of surjectivity, with cancellation on the right.

Solution.

Uses. Definition 2.6.1 (Injective), Definition 2.6.2 (Surjective), Definition A.1.2 (Function)

Techniques. Fix an arbitrary element and chase it (Technique 1.3.13)

Hint 1. For “injective

\Rightarrow

cancellable”, evaluate

𝑓 \circ 𝑔 = 𝑓 \circ ℎ

at each

𝑤 \in 𝑊

Hint 2. For the converse, test cancellability with

𝑊 = {0}

: a function

{0} \to 𝑋

is just a choice of one element of

𝑋

Hint 3. For surjectivity the statement is:

𝑓

is surjective iff

𝑔 \circ 𝑓 = ℎ \circ 𝑓

implies

𝑔 = ℎ

for all

𝑔, ℎ : 𝑌 \to 𝑍

. For the converse, if

𝑦_{0} \notin im 𝑓

, compare two functions

𝑌 \to {0, 1}

that differ only at

𝑦_{0}

Sketch. If

𝑓

is injective and

𝑓 (𝑔 (𝑤)) =

𝑓 (ℎ (𝑤))

, then

𝑔 (𝑤) = ℎ (𝑤)

. If

𝑓 (𝑥) = 𝑓 (𝑥^{'})

, the functions

𝑔, ℎ : {0} \to 𝑋

with values

𝑥, 𝑥^{'}

satisfy

𝑓 \circ 𝑔 = 𝑓 \circ ℎ

, so

𝑥 = 𝑥^{'}

. Dually, if

𝑓

is surjective, every

𝑦

𝑓 (𝑥)

, and

𝑔 (𝑓 (𝑥)) =

ℎ (𝑓 (𝑥))

; if

𝑦_{0} \notin im 𝑓

, the indicator function of

{𝑦_{0}}

and the zero function

𝑌 \to {0, 1}

agree after composing with

𝑓

Suppose $𝑓$ is injective and $𝑓 \circ 𝑔 = 𝑓 \circ ℎ$ . For each $𝑤 \in 𝑊$ , $𝑓 (𝑔 (𝑤)) =$ $𝑓 (ℎ (𝑤))$ , so $𝑔 (𝑤) = ℎ (𝑤)$ . Hence $𝑔 = ℎ$ . Conversely, suppose $𝑓$ can be cancelled on the left, and let $𝑓 (𝑥) = 𝑓 (𝑥^{'})$ . Define $𝑔, ℎ : {0} \to 𝑋$ by $𝑔 (0) = 𝑥$ and $ℎ (0) = 𝑥^{'}$ . Then $𝑓 \circ 𝑔 = 𝑓 \circ ℎ$ , so $𝑔 = ℎ$ , that is, $𝑥 = 𝑥^{'}$ .

The analogue: $𝑓$ is surjective if and only if, for every set $𝑍$ and all $𝑔, ℎ : 𝑌 \to 𝑍$ , $𝑔 \circ 𝑓 = ℎ \circ 𝑓$ implies $𝑔 = ℎ$ . Suppose $𝑓$ is surjective and $𝑔 \circ 𝑓 = ℎ \circ 𝑓$ . Each $𝑦 \in 𝑌$ equals $𝑓 (𝑥)$ for some $𝑥$ , so $𝑔 (𝑦) =$ $𝑔 (𝑓 (𝑥)) =$ $ℎ (𝑓 (𝑥)) =$ $ℎ (𝑦)$ . Conversely, suppose $𝑓$ is not surjective, and let $𝑦_{0} \in 𝑌 ∖ im 𝑓$ . Let $𝑔, ℎ : 𝑌 \to {0, 1}$ with $𝑔 (𝑦) = 0$ for all $𝑦$ , and $ℎ (𝑦_{0}) = 1$ , $ℎ (𝑦) = 0$ for $𝑦 \neq 𝑦_{0}$ . For every $𝑥 \in 𝑋$ , $𝑓 (𝑥) \neq 𝑦_{0}$ , so $𝑔 (𝑓 (𝑥)) =$ $0 =$ $ℎ (𝑓 (𝑥))$ . Thus $𝑔 \circ 𝑓 = ℎ \circ 𝑓$ but $𝑔 \neq ℎ$ , and $𝑓$ cannot be cancelled on the right.

For matrices, Section 2.5 shows that a left-invertible matrix can be cancelled on the left. For functions, left cancellation is in fact equivalent to having a left inverse when $𝑋 \neq \emptyset$ , by Theorem A.1.12(a).

Exercise A.1.27.standard

(a)Let $𝑋$ and $𝑌$ be finite with $| 𝑋 | = 𝑚 \geq 1$ and $| 𝑌 | = 𝑛$ , and let $𝑓 : 𝑋 \to 𝑌$ be injective. How many left inverses does $𝑓$ have?
(b)Let $𝑓 : 𝑋 \to 𝑌$ be surjective with $𝑌 = {𝑦_{1}, \dots, 𝑦_{𝑘}}$ finite and every fiber finite. Show that $𝑓$ has exactly $| 𝑓^{- 1} (𝑦_{1}) | \dots | 𝑓^{- 1} (𝑦_{𝑘}) |$ right inverses.
(c)Find the number of left inverses of $𝑓 : [2] \to [4]$ , $𝑓 (𝑖) = 𝑖$ , and the number of right inverses of $𝑝 : [4] \to [2]$ , $𝑝 (𝑖) = 1$ for $𝑖$ odd and $𝑝 (𝑖) = 2$ for $𝑖$ even.

Solution.

Uses. Theorem A.1.12 (One-sided inverses of functions), Exercise A.1.28

Hint 1. A left inverse is forced on

im 𝑓

, which has

𝑚

elements, and arbitrary on the other

𝑛 - 𝑚

elements of

𝑌

Hint 2. A right inverse is exactly a choice of one element

𝑔 (𝑦_{𝑖}) \in

𝑓^{- 1} (𝑦_{𝑖})

for each

𝑖

, and the choices are independent.

Sketch. (a)

𝑔

is determined on

im 𝑓

(

𝑚

points) and free on the remaining

𝑛 - 𝑚

points, with

𝑚

options each:

𝑚^{𝑛 - 𝑚}

. (b)

𝑔

is a right inverse iff

𝑔 (𝑦_{𝑖}) \in

𝑓^{- 1} (𝑦_{𝑖})

for all

𝑖

, and the choices are independent. (c)

2^{2} = 4

left inverses;

2 \cdot 2 = 4

right inverses.

(a) A function $𝑔 : 𝑌 \to 𝑋$ is a left inverse of $𝑓$ if and only if $𝑔 (𝑓 (𝑥)) = 𝑥$ for all $𝑥$ . Since $𝑓$ is injective, this fixes $𝑔$ at each of the $𝑚$ elements of $im 𝑓$ and says nothing about the $𝑛 - 𝑚$ elements of $𝑌 ∖ im 𝑓$ , where $𝑔$ may take any of the $𝑚$ values in $𝑋$ . By Exercise A.1.28 there are $𝑚^{𝑛 - 𝑚}$ such $𝑔$ .

(b) A function $𝑔 : 𝑌 \to 𝑋$ is a right inverse of $𝑓$ if and only if $𝑓 (𝑔 (𝑦_{𝑖})) = 𝑦_{𝑖}$ for each $𝑖$ , that is, $𝑔 (𝑦_{𝑖}) \in$ $𝑓^{- 1} (𝑦_{𝑖})$ . So a right inverse is a choice of an element in each of the $𝑘$ fibers, independently, and there are $| 𝑓^{- 1} (𝑦_{1}) | \dots | 𝑓^{- 1} (𝑦_{𝑘}) |$ ways to choose.

(c) For $𝑓$ , $𝑚 = 2$ and $𝑛 = 4$ , so there are $2^{4 - 2} = 4$ left inverses: $𝑔 (1) = 1$ , $𝑔 (2) = 2$ , and $𝑔 (3), 𝑔 (4) \in {1, 2}$ arbitrary. For $𝑝$ , the fibers are $𝑝^{- 1} (1) = {1, 3}$ and $𝑝^{- 1} (2) = {2, 4}$ , so there are $2 \cdot 2 = 4$ right inverses.

Exercise A.1.28.standard For sets $𝑋$ and $𝑌$ , let $𝑌^{𝑋}$ be the set of all functions $𝑋 \to 𝑌$ .

(a)Show by induction on $| 𝑋 |$ that if $𝑋$ and $𝑌$ are finite, then $| 𝑌^{𝑋} | = {| 𝑌 |}^{| 𝑋 |}$ (with $0^{0} = 1$ ).
(b)Construct a bijection $𝑃 (𝑋) \to {0, 1}^{𝑋}$ , and deduce that $| 𝑃 (𝑋) | = 2^{| 𝑋 |}$ .
(c)Deduce that $| 𝐹^{𝑛} | = 𝑞^{𝑛}$ and $| 𝐹^{𝑚 \times 𝑛} | = 𝑞^{𝑚 𝑛}$ for a field $𝐹$ with $𝑞$ elements.

Solution.

Uses. Corollary A.1.18 (Cardinality is well defined), Theorem A.1.14 (Bijections and inverses), Remark 1.2.11 (Tuples and matrices are functions)

Hint 1. For the step in (a), with

𝑋 = 𝑋^{'} \cup {𝑥_{0}}

and

𝑥_{0} \notin 𝑋^{'}

, a function

𝑋 \to 𝑌

is a function

𝑋^{'} \to 𝑌

together with a value at

𝑥_{0}

Hint 2. The map

(ℎ, 𝑦) \mapsto

“

ℎ

extended by

𝑥_{0} \mapsto 𝑦

” is a bijection

𝑌^{𝑋^{'}} \times 𝑌 \to 𝑌^{𝑋}

, and

| 𝐴 \times 𝐵 | = | 𝐴 | | 𝐵 |

(list the pairs row by row).

Hint 3. In (b), send

𝐴

to its indicator function. In (c), an element of

𝐹^{𝑛}

is a function

[𝑛] \to 𝐹

Sketch. (a) Induction: if

𝑋 = \emptyset

𝑌^{𝑋}

has one element. Otherwise remove

𝑥_{0}

; restricting to

𝑋^{'}

and recording the value at

𝑥_{0}

is a bijection

𝑌^{𝑋} \to 𝑌^{𝑋^{'}} \times 𝑌

, giving

{| 𝑌 |}^{| 𝑋 | - 1} \cdot | 𝑌 |

. (b)

𝐴 \mapsto 𝟙_{𝐴}

with inverse

ℎ \mapsto ℎ^{- 1} (1)

. (c)

𝐹^{𝑛} = 𝐹^{[𝑛]}

and

𝐹^{𝑚 \times 𝑛} =

𝐹^{[𝑚] \times [𝑛]}

(a) If $| 𝑋 | = 0$ , then $𝑋 = \emptyset$ , and there is exactly one function $\emptyset \to 𝑌$ , so $| 𝑌^{𝑋} | = 1 = {| 𝑌 |}^{0}$ . Let $| 𝑋 | = 𝑘 \geq 1$ , pick $𝑥_{0} \in 𝑋$ , and let $𝑋^{'} = 𝑋 ∖ {𝑥_{0}}$ , so $| 𝑋^{'} | = 𝑘 - 1$ (remove $𝑥_{0}$ from a listing of $𝑋$ ). The map

𝑌^{𝑋} \to 𝑌^{𝑋^{'}} \times 𝑌, ℎ \mapsto (ℎ ↾_{𝑋^{'}}, ℎ (𝑥_{0})),

is a bijection, with inverse sending $(ℎ^{'}, 𝑦)$ to the function that agrees with $ℎ^{'}$ on $𝑋^{'}$ and takes the value $𝑦$ at $𝑥_{0}$ . If $| 𝐴 | = 𝑟$ and $| 𝐵 | = 𝑠$ , then $| 𝐴 \times 𝐵 | = 𝑟 𝑠$ : listing $𝐴 = {𝛼_{1}, \dots, 𝛼_{𝑟}}$ and $𝐵 = {𝛽_{1}, \dots, 𝛽_{𝑠}}$ , the pair $(𝛼_{𝑖}, 𝛽_{𝑗})$ corresponds to $(𝑖 - 1) 𝑠 +$ $𝑗 \in$ $[𝑟 𝑠]$ . Hence, by the induction hypothesis and Corollary A.1.18, $| 𝑌^{𝑋} | =$ ${| 𝑌 |}^{𝑘 - 1} \cdot$ $| 𝑌 | =$ ${| 𝑌 |}^{𝑘}$ .

(b) For $𝐴 \subseteq 𝑋$ , let $𝟙_{𝐴} : 𝑋 \to {0, 1}$ be its indicator function: $𝟙_{𝐴} (𝑥) = 1$ if $𝑥 \in 𝐴$ and $0$ otherwise. The map $𝐴 \mapsto 𝟙_{𝐴}$ has inverse $ℎ \mapsto ℎ^{- 1} (1)$ : indeed $𝟙_{𝐴}^{- 1} (1) = 𝐴$ , and $ℎ$ and $𝟙_{ℎ^{- 1} (1)}$ agree at every $𝑥$ . So it is a bijection (Theorem A.1.14), and $| 𝑃 (𝑋) | =$ $| {0, 1}^{𝑋} | =$ $2^{| 𝑋 |}$ by (a).

(c) An element of $𝐹^{𝑛}$ is a function $[𝑛] \to 𝐹$ , and an element of $𝐹^{𝑚 \times 𝑛}$ is a function $[𝑚] \times [𝑛] \to 𝐹$ (Remark 1.2.11). So $| 𝐹^{𝑛} | = 𝑞^{𝑛}$ and $| 𝐹^{𝑚 \times 𝑛} | = 𝑞^{𝑚 𝑛}$ by (a), using $| [𝑚] \times [𝑛] | = 𝑚 𝑛$ .

Exercise A.1.29.standard Let

𝑎_{1}, \dots, 𝑎_{𝑛}

be integers, where

𝑛 \geq 1

. Show that some nonempty block of consecutive terms

𝑎_{𝑖 + 1} +

𝑎_{𝑖 + 2} +

\dots +

𝑎_{𝑗}

, with

0 \leq 𝑖 < 𝑗 \leq 𝑛

, is divisible by

𝑛

Solution.

Uses. Theorem A.1.17 (Pigeonhole principle), Definition 1.1.19 (Integers modulo $𝑛$ )

Techniques. Pigeonhole (Technique A.1.21)

Hint 1. Blocks of consecutive terms are differences of partial sums

𝑠_{𝑗} = 𝑎_{1} + \dots + 𝑎_{𝑗}

, with

𝑠_{0} = 0

Hint 2. There are

𝑛 + 1

partial sums

𝑠_{0}, \dots, 𝑠_{𝑛}

and only

𝑛

remainders mod

𝑛

Sketch. The

𝑛 + 1

partial sums

𝑠_{0}, \dots, 𝑠_{𝑛}

have only

𝑛

possible remainders mod

𝑛

, so

𝑠_{𝑖} mod 𝑛 =

𝑠_{𝑗} mod 𝑛

for some

𝑖 < 𝑗

, and then

𝑛

divides

𝑠_{𝑗} -

𝑠_{𝑖} =

𝑎_{𝑖 + 1} +

\dots +

𝑎_{𝑗}

Let $𝑠_{0} = 0$ and $𝑠_{𝑗} = 𝑎_{1} + \dots + 𝑎_{𝑗}$ for $1 \leq 𝑗 \leq 𝑛$ . The function ${0, 1, \dots, 𝑛} \to$ ${0, 1, \dots, 𝑛 - 1}$ , $𝑗 \mapsto 𝑠_{𝑗} mod 𝑛$ , goes from a set with $𝑛 + 1$ elements to one with $𝑛$ elements, so it is not injective (Theorem A.1.17). Hence $𝑠_{𝑖} mod 𝑛 =$ $𝑠_{𝑗} mod 𝑛$ for some $𝑖 < 𝑗$ , which means $𝑛$ divides $𝑠_{𝑗} -$ $𝑠_{𝑖} =$ $𝑎_{𝑖 + 1} +$ $\dots +$ $𝑎_{𝑗}$ .

The bound is sharp: for $𝑎_{1} = \dots = 𝑎_{𝑛 - 1} = 1$ , which has only $𝑛 - 1$ terms, every block sum lies between $1$ and $𝑛 - 1$ .

Exercise A.1.30.hardBeyond 21-242 Let

𝑋

be any set. Show that there is no surjective function

𝑋 \to 𝑃 (𝑋)

. In particular, there is no bijection

ℕ \to 𝑃 (ℕ)

Solution.

Uses. Definition 2.6.2 (Surjective)

Techniques. Extremal choice and minimal counterexamples (Technique 1.5.9)

Hint 1. Given

𝑓 : 𝑋 \to 𝑃 (𝑋)

, build a subset of

𝑋

that differs from every

𝑓 (𝑥)

, by making it disagree with

𝑓 (𝑥)

at the element

𝑥

Hint 2. Let

𝐷 =

{𝑥 \in 𝑋 | 𝑥 \notin 𝑓 (𝑥)}

. Could

𝐷 = 𝑓 (𝑑)

? Ask whether

𝑑 \in 𝐷

Sketch. Diagonal argument:

𝐷 = {𝑥 | 𝑥 \notin 𝑓 (𝑥)}

is not a value of

𝑓

, since

𝐷 = 𝑓 (𝑑)

would give

𝑑 \in 𝐷 \Leftrightarrow 𝑑 \notin 𝐷

Let $𝑓 : 𝑋 \to 𝑃 (𝑋)$ and $𝐷 =$ ${𝑥 \in 𝑋 | 𝑥 \notin 𝑓 (𝑥)} \in$ $𝑃 (𝑋)$ . Suppose $𝐷 = 𝑓 (𝑑)$ for some $𝑑 \in 𝑋$ . If $𝑑 \in 𝐷$ , then $𝑑 \notin 𝑓 (𝑑) = 𝐷$ ; if $𝑑 \notin 𝐷$ , then $𝑑 \notin 𝑓 (𝑑)$ , so $𝑑 \in 𝐷$ by definition of $𝐷$ . Both cases are contradictions, so $𝐷$ is not a value of $𝑓$ , and $𝑓$ is not surjective. In particular there is no bijection $ℕ \to 𝑃 (ℕ)$ , although $ℕ$ and $𝑃 (ℕ)$ are both infinite.

The set $𝐷$ is built to disagree with $𝑓 (𝑥)$ about the single element $𝑥$ . The same diagonal idea shows that the real numbers cannot be listed as a sequence.

More practice

The practice bank has 5 exercises on this section’s topics.