← MA0 1 · Introduction to University Mathematics (Proofs)

Lesson 4

Functions

Taught 14 Aug 2026

More Sets

Once the axioms of set theory are in place, we can review some elementary albeit very useful constructions that these axioms enable.

Ordered Pairs

We often need to pair two elements while retaining their positions, and an ordinary two-element set cannot do this, since $\{a, b\} = \{b, a\}$ ; something more is needed if one element is to be marked as coming before the other. We could simply declare that the notation $(a, b)$ is ordered, but what does ordered mean in terms of sets?

Before choosing a set to represent $(a, b)$ , we state the property any such choice must have: whenever $(a, b)$ and $(c, d)$ are ordered pairs,

(a, b) = (c, d) \iff (a = c) \land (b = d). \tag{$*$}

In particular, the two coordinates must be recoverable from the pair.

Definition 4.1 (Ordered pair).

Let $a$ and $b$ be objects. The ordered pair $(a, b)$ is the set

(a, b) \;\defeq\; \bigl\{\{a\}, \{a, b\}\bigr\},

where $a$ is its first coordinate and $b$ its second coordinate.

The sets used to encode the pair, $\{a\}$ and $\{a, b\}$ , are supplied by the pairing axiom of the last chapter, and the set on the right exists by that same axiom applied once more, to those two. The construction is due to Kuratowski. Does it satisfy $(*)$ ?

Proposition 4.2 (Equality of ordered pairs).

For objects $a$ , $b$ , $c$ and $d$ , $(a, b) = (c, d)$ if and only if $a = c$ and $b = d$ .

Discussion.

Our statement is a biconditional. The reverse implication, $a = c$ and $b = d$ implies $(a, b) = (c, d)$ , is a direct substitution into the definition of the ordered pair. For the forward implication we assume $\bigl\{\{a\}, \{a, b\}\bigr\} = \bigl\{\{c\}, \{c, d\}\bigr\}$ and must recover the coordinates from the set; the argument splits into the cases $a = b$ and $a \neq b$ , because in the first case the pair collapses to the singleton $\bigl\{\{a\}\bigr\}$ while in the second its two elements are distinct and can be chased through the equality one at a time. The logical proof avoids the split: it expands each ordered pair, rewrites set equality as the two inclusions by mutual inclusion, and lets the distributive and absorption laws of the first chapter reduce the resulting disjunctions to the conjunction $a = c \land b = d$ .

Proof (element style).

Let $a$ , $b$ , $c$ and $d$ be arbitrary objects. For the reverse implication, suppose $a = c$ and $b = d$ . Then $\{a\} = \{c\}$ and $\{a, b\} = \{c, d\}$ ; hence $(a, b) = \bigl\{\{a\}, \{a, b\}\bigr\} = \bigl\{\{c\}, \{c, d\}\bigr\} = (c, d)$ .

For the forward implication, suppose $(a, b) = (c, d)$ . By the definition of set equality, every element of either ordered pair belongs to the other; we divide the argument into two cases, $a = b$ and $a \neq b$ .

If $a = b$ , then $(a, b) = \bigl\{\{a\}, \{a, a\}\bigr\} = \bigl\{\{a\}\bigr\}$ . Both $\{c\}$ and $\{c, d\}$ belong to $(c, d) = (a, b) = \bigl\{\{a\}\bigr\}$ , so each must equal $\{a\}$ ; hence $c = a$ and $d = a$ . Since $b = a$ as well, we obtain $a = c$ and $b = d$ .

If $a \neq b$ , then $\{a\} \neq \{a, b\}$ ; consequently $(a, b)$ has two distinct elements. Since $\{a\} \in (a, b) = (c, d)$ , either $\{a\} = \{c\}$ or $\{a\} = \{c, d\}$ . The latter equality would give $c = d = a$ , so $(c, d) = \bigl\{\{a\}\bigr\}$ would have only one element; this contradicts $(a, b) = (c, d)$ , since $(a, b)$ has two. Therefore $\{a\} = \{c\}$ , and hence $a = c$ .

Similarly, since $\{a, b\} \in (a, b) = (c, d)$ , either $\{a, b\} = \{c\}$ or $\{a, b\} = \{c, d\}$ . The former equality would give $a = b = c$ , contradicting $a \neq b$ ; therefore $\{a, b\} = \{c, d\}$ . It follows that $b = c$ or $b = d$ ; but $c = a \neq b$ , so $b \neq c$ and hence $b = d$ . Thus $a = c$ and $b = d$ .

Remark.

This logical proof is dumb and covoluted lol but why not.

Proof (logical style).

Let $a$ , $b$ , $c$ and $d$ be arbitrary objects. By the definition of set equality,

\begin{aligned} (a, b) = (c, d) &\equiv \Bigl(\bigl\{\{a\}, \{a, b\}\bigr\} \subset \bigl\{\{c\}, \{c, d\}\bigr\}\Bigr) \\ &\qquad {}\land \Bigl(\bigl\{\{c\}, \{c, d\}\bigr\} \subset \bigl\{\{a\}, \{a, b\}\bigr\}\Bigr) \\[2pt] &\equiv \Bigl(\bigl(\{a\} = \{c\} \lor \{a\} = \{c, d\}\bigr) \\ &\qquad\quad {}\land \bigl(\{a, b\} = \{c\} \lor \{a, b\} = \{c, d\}\bigr)\Bigr) \\ &\qquad {}\land \Bigl(\bigl(\{c\} = \{a, b\} \lor \{c\} = \{a\}\bigr) \\ &\qquad\qquad {}\land \bigl(\{c, d\} = \{a\} \lor \{c, d\} = \{a, b\}\bigr)\Bigr) \\[2pt] &\equiv \Bigl(\bigl(\{a\} = \{c\} \lor \{a\} = \{c, d\}\bigr) \\ &\qquad\quad {}\land \bigl(\{c\} = \{a, b\} \lor \{c\} = \{a\}\bigr)\Bigr) \\ &\qquad {}\land \Bigl(\bigl(\{a, b\} = \{c\} \lor \{a, b\} = \{c, d\}\bigr) \\ &\qquad\qquad {}\land \bigl(\{c, d\} = \{a\} \lor \{c, d\} = \{a, b\}\bigr)\Bigr) \\[2pt] &\equiv \Bigl(\{a\} = \{c\} \lor \bigl(\{a\} = \{c, d\} \land \{a, b\} = \{c\}\bigr)\Bigr) \\ &\qquad {}\land \Bigl(\{a, b\} = \{c, d\} \lor \bigl(\{a, b\} = \{c\} \land \{c, d\} = \{a\}\bigr)\Bigr) \\[2pt] &\equiv \bigl(\{a\} = \{c, d\} \land \{a, b\} = \{c\}\bigr) \\ &\qquad {}\lor \bigl(\{a\} = \{c\} \land \{a, b\} = \{c, d\}\bigr) \\[2pt] &\equiv \Bigl(\bigl(a = c \land a = d\bigr) \land \bigl(a = c \land b = c\bigr)\Bigr) \\ &\qquad {}\lor \Bigl(a = c \land \bigl((a = c \land b = d) \lor (a = d \land b = c)\bigr)\Bigr) \\[2pt] &\equiv (a = c \land a = d \land b = c) \lor (a = c \land b = d) \\ &\qquad {}\lor (a = c \land a = d \land b = c) \\[2pt] &\equiv (a = c \land a = d \land b = c) \lor (a = c \land b = d) \\[2pt] &\equiv (a = c \land a = d \land b = c \land b = d) \lor (a = c \land b = d) \\[2pt] &\equiv a = c \land b = d. \end{aligned}

Corollary 4.3 (Swapping coordinates).

For objects $a$ and $b$ , $(a, b) = (b, a)$ if and only if $a = b$ .

Proof.

If $(a, b) = (b, a)$ , then Proposition 4.2 gives $a = b$ by comparing first coordinates. Conversely, if $a = b$ , then $(a, b) = (a, a) = (b, a)$ .

Kuratowski’s is not the only possible choice, and the next problem looks at a shorter one.

Problem 4.1.

Some authors define the ordered pair by the shorter set

\langle a, b \rangle \;\defeq\; \bigl\{a, \{a, b\}\bigr\}.

Prove that this also satisfies $(*)$ , so that $\langle a, b \rangle = \langle c, d \rangle$ if and only if $a = c$ and $b = d$ . You may use the axiom of regularity from the last chapter, and in particular the conclusion of its second problem.
Show that regularity is genuinely needed, by identifying the step of your argument that fails without it, and say why the same step does not arise for Definition 4.1 .

Nesting ordered pairs builds longer ordered tuples.

Definition 4.4 (Ordered triples and longer).

Let $a$ , $b$ , $c$ and $d$ be objects. The ordered triple and ordered quadruple are

(a, b, c) \;\defeq\; \bigl((a, b), c\bigr), \qquad (a, b, c, d) \;\defeq\; \bigl((a, b, c), d\bigr),

and further tuples are assembled the same way.

Remark.

We have now overloaded the parenthesis symbols $(\ )$ once again: they are used not only to group operators and arguments, but also to enclose ordered pairs. This is usually not a problem in practice, as one can still determine from context which usage is intended.

Cartesian Products

With ordered pairs in hand we can collect all of them at once. The collection has to come from somewhere, and the power set supplies it.

Proposition 4.5 (Where ordered pairs live).

Let $A$ and $B$ be sets, let $a \in A$ and $b \in B$ . Then $(a, b) \in \mathcal{P}\bigl(\mathcal{P}(A \cup B)\bigr)$ .

Discussion.

An ordered pair is a set of two sets, so it sits two power sets up from whatever holds its coordinates, and the set holding both coordinates is $A \cup B$ . We go up one power set at a time: show each of $\{a\}$ and $\{a, b\}$ is a subset of $A \cup B$ , which puts both in $\mathcal{P}(A \cup B)$ , and then that having both as elements makes $(a, b)$ a subset of $\mathcal{P}(A \cup B)$ , which is what membership in the next power set asks for.

Proof.

Since $a \in A$ we have $a \in A \cup B$ , and since $b \in B$ we have $b \in A \cup B$ . Every element of $\{a\}$ is $a$ , and every element of $\{a, b\}$ is $a$ or $b$ , so both $\{a\} \subset A \cup B$ and $\{a, b\} \subset A \cup B$ , that is, both belong to $\mathcal{P}(A \cup B)$ .

The elements of $(a, b) = \bigl\{\{a\}, \{a, b\}\bigr\}$ are exactly those two sets, so $(a, b) \subset \mathcal{P}(A \cup B)$ , which is $(a, b) \in \mathcal{P}\bigl(\mathcal{P}(A \cup B)\bigr)$ .

Definition 4.6 (Cartesian product).

Let $A$ and $B$ be sets. The Cartesian product $A \times B$ is the set of all ordered pairs with first coordinate in $A$ and second in $B$ ,

A \times B \;\defeq\; \Bigl\{p \in \mathcal{P}\bigl(\mathcal{P}(A \cup B)\bigr) \;\Big|\; \exists a \in A\ \exists b \in B\,\bigl(p = (a, b)\bigr)\Bigr\},

so that for every object $p$ , $p \in A \times B$ exactly when $p = (a, b)$ for some $a \in A$ and some $b \in B$ .

The product needs no axiom of its own. The proposition above puts every candidate pair inside $\mathcal{P}(\mathcal{P}(A \cup B))$ , a set we are already holding, and comprehension carves the product out of it.

Example 4.7.

Let $A = \{1, 2\}$ and $B = \{r, s\}$ . Then $A \times B = \bigl\{(1, r), (1, s), (2, r), (2, s)\bigr\}$ . Order matters here in a way it did not for unordered pairs: $(1, r) \in A \times B$ while $(r, 1) \in B \times A$ , and the two products are different sets.

Problem 4.2.

Let $A$ and $B$ be sets. Show that $A \times B = \emptyset$ if and only if $A = \emptyset$ or $B = \emptyset$ .

Membership in a product is a conjunction, which adds another line to the dictionary:

\bigl((s, t) \in S \times T\bigr) \equiv (s \in S) \land (t \in T).

Example 4.8.

Order matters, and in general $S \times T \neq T \times S$ . With $S = \{1, 2\}$ and $T = \{a, b, c\}$ we have $T \times S = \{(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)\}$ , which is not the earlier set: the element $(1, a)$ lies in $S \times T$ but not in $T \times S$ , since $1 \notin T$ .

Example 4.9.

For any set $S$ , both $S \times \emptyset$ and $\emptyset \times S$ are empty. A pair in $S \times \emptyset$ would need its second coordinate from $\emptyset$ , which has nothing to give; through the dictionary, $\bigl((s, t) \in S \times \emptyset\bigr) \equiv (s \in S) \land \bot \equiv \bot$ .

Products of three or more sets work the same way, $S \times T \times R$ collecting the triples $(s, t, r)$ with $s \in S$ , $t \in T$ and $r \in R$ , and so on upwards. There is a subtlety here.

Remark (Order of operations).

The definition takes two sets at a time, so for three sets there are two readings, and they are not the same set. Applying it twice, the elements of $A \times (B \times C)$ are the pairs $\bigl(x, (y, z)\bigr)$ , which unfold to

\bigl\{\{x\},\ \bigl\{x, \{\{y\}, \{y, z\}\}\bigr\}\bigr\},

while the elements of $(A \times B) \times C$ are the pairs $\bigl((x, y), z\bigr)$ , which unfold to

\Bigl\{\bigl\{\{\{x\}, \{x, y\}\}\bigr\},\ \bigl\{\{\{x\}, \{x, y\}\}, z\bigr\}\Bigr\}.

Both should intuitively be the set of all triples $(x, y, z)$ , and they do describe the same object once we identify them. Using a term we introduce below, the identification amounts to checking that

\bigl(x, (y, z)\bigr) \longmapsto \bigl((x, y), z\bigr)

is a bijection from the first set onto the second, so the product is associative up to that correspondence. Once bijections are in hand this is a short piece of work, and the problems below ask you to do it; from then on we drop the brackets and write $A \times B \times C$ .

Problem 4.3.

We said that $S \times T \neq T \times S$ in general. Find every case in which they are equal.

Indexed Families

It is often convenient to give each set in a collection a label.

Definition 4.10 (Indexed family).

Let $I$ be a set. An indexed family consists of one object $x_i$ for each $i \in I$ , and is written $\{x_i\}_{i \in I}$ . The set $I$ is the index set and $i$ is an index. Different indices may label the same object.

Example 4.11.

Let $A$ , $C$ and $D$ be sets, take $I = \{1, 2, 3, 4\}$ , and declare $B_1 \defeq A$ , $B_2 \defeq C$ , $B_3 \defeq A$ and $B_4 \defeq D$ . The family $\{B_i\}_{i \in I}$ has four entries, and the equality $B_1 = B_3$ removes neither of them: the labels $1$ and $3$ are different even though the sets they label are equal. The braces in the notation are a convention, since what we are holding is an assignment of an object to each index, and that assignment records more than the plain set of members $\{A, C, D\}$ , which does not record that $A$ occurs twice.

Definition 4.12 (Indexed unions and intersections).

Let $\{A_i\}_{i \in I}$ be an indexed family of sets with $I$ non-empty. Its union and intersection are

\bigcup_{i \in I} A_i \defeq \bigcup \{A_i : i \in I\}, \qquad \bigcap_{i \in I} A_i \defeq \Bigl\{x \in \bigcup_{i \in I} A_i \;\Big|\; \forall i \in I\,(x \in A_i)\Bigr\},

so that $x \in \bigcup_{i \in I} A_i$ exactly when $x \in A_i$ for some $i \in I$ , and $x \in \bigcap_{i \in I} A_i$ exactly when $x \in A_i$ for every $i \in I$ .

Neither needs an axiom beyond those we have. Replacement turns the index set into the set $\{A_i : i \in I\}$ of members, since each $i$ has exactly one partner $A_i$ , and the union axiom pools what those members hold. The intersection is then carved out of that union by comprehension, exactly as the intersection of a system of sets was in the last chapter, and for the same reason: an object lying in every member lies in some member, so nothing is lost by looking only inside the union.

By the bounded quantifier convention of the last chapter, the two membership tests unabbreviate to $\exists i\,\bigl((i \in I) \land (x \in A_i)\bigr)$ for the union and $\forall i\,\bigl((i \in I) \implies (x \in A_i)\bigr)$ for the intersection.

For $I = \{1, 2\}$ the new symbols hand back the old ones, $\bigcup_{i \in I} A_i = A_1 \cup A_2$ and $\bigcap_{i \in I} A_i = A_1 \cap A_2$ . With quantifiers doing the work, the negation rules settle what it takes not to belong:

x \notin \bigcap_{i \in I} A_i \iff \exists i \in I\,(x \notin A_i), \qquad x \notin \bigcup_{i \in I} A_i \iff \forall i \in I\,(x \notin A_i).

So $x$ is outside the intersection if it misses a single $A_i$ , but outside the union only if it misses every $A_i$ .

Problem 4.4 (Informal).

Let $I = \{1, 2, 3, 4\}$ and let $A_i$ be the set of whole numbers $m$ with $i \leqslant m \leqslant 2i$ . Determine $\bigcup_{i \in I} A_i$ and $\bigcap_{i \in I} A_i$ .

Problem 4.5.

Let $I$ be a non-empty set, let $P$ be a statement not involving $i$ , and let $Q(i)$ be a predicate on $I$ . Prove the two exchange laws

P \land \exists i \in I\,Q(i) \equiv \exists i \in I\,\bigl(P \land Q(i)\bigr), \qquad P \land \forall i \in I\,Q(i) \equiv \forall i \in I\,\bigl(P \land Q(i)\bigr).

Where does the non-emptiness of $I$ enter? Show that if $I = \emptyset$ one of the two equivalences survives and the other fails.

Proposition 4.13 (Set difference over indexed families).

Let $A$ be a set and let $\{B_i\}_{i \in I}$ be an indexed family of sets with $I$ non-empty. Then

$A \setminus \bigcap_{i \in I} B_i = \bigcup_{i \in I} (A \setminus B_i)$ ;
$A \setminus \bigcup_{i \in I} B_i = \bigcap_{i \in I} (A \setminus B_i)$ .

Discussion.

Both are equalities of sets, so we compare membership on the two sides, and each comparison admits two readings. Elementwise, an element of $A \setminus \bigcap_{i \in I} B_i$ sits in $A$ and misses some $B_j$ , so it sits in $A \setminus B_j$ and hence in the union of the differences; conversely, belonging to one difference $A \setminus B_j$ already keeps the element out of the intersection. The second identity is the same argument with “some” replaced by “every”. The logical route says this through the dictionary: the definition turns membership in the intersection into a universal quantifier and membership in the union into an existential one, the negation rules swap $\forall$ for $\exists$ and back, and the exchange laws of the problem above push the fixed condition $x \in A$ through the quantifier.

Proof (element style).

For the first, suppose $x \in A \setminus \bigcap_{i \in I} B_i$ . Then $x \in A$ , but $x$ does not belong to every $B_i$ , so $x \notin B_j$ for some $j \in I$ . Hence $x \in A \setminus B_j$ , and therefore $x \in \bigcup_{i \in I} (A \setminus B_i)$ . Conversely, suppose $x$ belongs to that union. Then for some $j \in I$ we have $x \in A \setminus B_j$ , so $x \in A$ and $x \notin B_j$ . It follows that $x \notin \bigcap_{i \in I} B_i$ , whence $x \in A \setminus \bigcap_{i \in I} B_i$ .

For the second, suppose $x \in A \setminus \bigcup_{i \in I} B_i$ . Then $x \in A$ and $x \notin B_i$ for every $i \in I$ , so $x \in A \setminus B_i$ for every $i \in I$ , that is, $x \in \bigcap_{i \in I} (A \setminus B_i)$ . Conversely, membership in that intersection gives $x \in A \setminus B_i$ for every $i \in I$ , so $x \in A$ and no $B_i$ holds $x$ , which puts $x$ in $A \setminus \bigcup_{i \in I} B_i$ .

Proof (logical style).

For any $x$ ,

\begin{aligned} x \in A \setminus \bigcap_{i \in I} B_i &\equiv (x \in A) \land \neg\,\forall i \in I\,(x \in B_i) && \text{by the definitions} \\ &\equiv (x \in A) \land \exists i \in I\,(x \notin B_i) && \text{by quantifier negation} \\ &\equiv \exists i \in I\,\bigl((x \in A) \land (x \notin B_i)\bigr) && \text{by the exchange law} \\ &\equiv x \in \bigcup_{i \in I} (A \setminus B_i) && \text{by the definitions} \end{aligned}

and likewise

\begin{aligned} x \in A \setminus \bigcup_{i \in I} B_i &\equiv (x \in A) \land \neg\,\exists i \in I\,(x \in B_i) && \text{by the definitions} \\ &\equiv (x \in A) \land \forall i \in I\,(x \notin B_i) && \text{by quantifier negation} \\ &\equiv \forall i \in I\,\bigl((x \in A) \land (x \notin B_i)\bigr) && \text{by the exchange law} \\ &\equiv x \in \bigcap_{i \in I} (A \setminus B_i) && \text{by the definitions.} \end{aligned}

Corollary 4.14 (De Morgan's laws for indexed families).

Let $\{B_i\}_{i \in I}$ be an indexed family of subsets of an ambient set $U$ , with $I$ non-empty. With every complement taken in $U$ ,

\overline{\bigcap_{i \in I} B_i} = \bigcup_{i \in I} \overline{B_i}, \qquad \overline{\bigcup_{i \in I} B_i} = \bigcap_{i \in I} \overline{B_i}.

Proof.

Take $A = U$ in the two parts of the proposition. Each difference $U \setminus B_i$ is the complement $\overline{B_i}$ , and the identities follow.

Problem 4.6.

Let $A$ be a set and $\{B_i\}_{i \in I}$ an indexed family of sets with $I$ non-empty. Prove that $A \subset \bigcap_{i \in I} B_i$ if and only if $A \subset B_i$ for every $i \in I$ , and that $\bigcup_{i \in I} B_i \subset A$ if and only if $B_i \subset A$ for every $i \in I$ .

Problem 4.7.

Let $\{A_{i,j}\}_{(i,j) \in I \times J}$ be an indexed family of sets with $I$ and $J$ non-empty. Decide which inclusion between

\bigcup_{i \in I} \bigcap_{j \in J} A_{i,j} \qquad\text{and}\qquad \bigcap_{j \in J} \bigcup_{i \in I} A_{i,j}

holds for every such family, and whether equality is forced. (Harder.)

Functions

In order to do analysis it is not particularly useful to have only the notion of a set; we also need the notion of a function from one set to another. Informally, a function $f : X \to Y$ is an operation which assigns to each element, or input, $x$ in $X$ a single element, or output, $f(x)$ in $Y$ . Formulas, rules and graphs are convenient ways to describe the pairing of inputs with outputs, but the set of pairs itself is the function.

Definition 4.15 (Function).

Let $X$ and $Y$ be sets. A function from $X$ to $Y$ is a subset $f \subset X \times Y$ such that for every $x \in X$ there is exactly one $y \in Y$ with $(x, y) \in f$ . We write $f : X \to Y$ , call $X$ the domain of $f$ , written $\operatorname{dom} f$ , and $Y$ the codomain, and write $f(x)$ for the unique $y$ paired with $x$ , so that for any $x \in X$ and $y \in Y$ ,

y = f(x) \iff (x, y) \in f.

The condition on $f$ is sometimes called the vertical line test: exactly one pair of $f$ stands above each point of the domain. It is two demands at once, existence and uniqueness, and either can fail on its own.

We also write $x \mapsto f(x)$ for the pairing. The object $f(x)$ is the image of $x$ , and $x$ is a preimage of $f(x)$ , one of possibly several. Functions are also called maps, mappings or transformations, depending on the context.

Remark.

A function is often handed to us as a property rather than a set of pairs. Let $P(x, y)$ pertain to $x \in X$ and $y \in Y$ , and suppose that for every $x \in X$ there is exactly one $y \in Y$ making $P(x, y)$ true. Then

f \;\defeq\; \bigl\{p \in X \times Y \;\big|\; \exists x \in X\ \exists y \in Y\,\bigl(p = (x, y) \land P(x, y)\bigr)\bigr\}

is a set by comprehension, and the hypothesis on $P$ is exactly the vertical line test, so $f$ is a function from $X$ to $Y$ with $y = f(x)$ precisely when $P(x, y)$ holds. No further axiom is needed to turn a property into a function; the ones we already have build the set of pairs for us.

Example 4.16 (Informal).

Assuming you know what the real numbers are, take both domain and codomain to be them. The declaration $g(x) = 1/x$ assigns nothing at $x = 0$ , so existence fails there and $g$ is not a function on that domain. The condition $h(x)^2 = x^2$ offers two candidates whenever $x \neq 0$ , namely $x$ and $-x$ , so uniqueness fails and $h$ is not a function either.

Remark (Informal examples).

Several examples below assume you know the real numbers and the whole numbers, which we have not built yet. In those we write $R$ for the real numbers and $W$ for the whole numbers, and we borrow the rules of school algebra openly. Nothing in the theory rests on them; they are there because familiar objects make the definitions easier to read.

A rule that meets both requirements, assigning a unique value in the codomain to every element of the domain, is said to be well defined. One common way to present a function is to specify its domain, its codomain, and how the output $f(x)$ is generated from each input; this is an explicit definition.

Remark.

Functions obey substitution: if $x = x'$ then $f(x) = f(x')$ , since $f(x)$ was defined as the unique $y$ paired with $x$ , and $x$ and $x'$ name the same object. Equal inputs give equal outputs. Unequal inputs need not give unequal outputs, as a constant map shows.

Three functions occur often enough to deserve names.

Definition 4.17 (Inclusion, identity and constant maps).

Let $S \subset T$ . The inclusion map $\iota : S \to T$ is defined by $\iota(x) \defeq x$ . When $S = T$ this is the identity map on $S$ , written $\mathrm{id}_S$ . For sets $A$ and $B$ and a fixed $b_0 \in B$ , the constant map with value $b_0$ is $c : A \to B$ given by $c(a) \defeq b_0$ for every $a \in A$ .

Example 4.18.

There is a function from $\emptyset$ to any set $B$ , namely the empty set of pairs. Neither requirement can find an element of $\emptyset$ on which to fail, so both hold vacuously. We shall see below that it is the only one from $\emptyset$ to $B$ .

When the domain and codomain are sets of real numbers we can plot the pairs of $f \subset A \times B$ in the Cartesian plane to draw its graph; for $q(x) = x^2$ this yields the familiar parabola. An arbitrary domain might admit no geometric picture, but the underlying set of pairs remains. Drawn this way, the identity on $S$ is the diagonal, since it pairs each $x$ with itself, and a constant map is a horizontal line.

Proposition 4.19 (Equality of functions).

Functions $f$ and $g$ are equal if and only if they have the same domain and $f(x) = g(x)$ for every $x$ in it.

Discussion.

We prove the two implications of the biconditional. Suppose first that $f = g$ . Equality of the sets of ordered pairs gives equality of their first coordinates, hence equality of the domains; for an arbitrary element of the common domain the pair $(x, f(x))$ belongs to $g$ , and the uniqueness clause of Definition 4.15 gives $f(x) = g(x)$ . Conversely, assume the domains agree and the two functions have the same value at every point of the common domain. By mutual inclusion it is enough to prove the two inclusions. An arbitrary $(x, y) \in f$ has $x$ in the domain and $y = f(x)$ , so the hypotheses put $(x, y)$ in $g$ ; the reverse inclusion follows symmetrically.

Proof (element style).

Suppose first that $f = g$ . The domain of a function consists of the first coordinates of its elements, so $f$ and $g$ have the same domain. For any $x$ in it the pair $(x, f(x))$ belongs to $f$ , and since $f = g$ we have $(x, f(x)) \in g$ , which gives $f(x) = g(x)$ by the uniqueness of images in $g$ .

Conversely, assume the domains agree and $f(x) = g(x)$ for every $x$ in the common domain. If $(x, y) \in f$ , then $x$ lies in that domain and $y = f(x)$ ; since $f(x) = g(x)$ we have $y = g(x)$ , so $(x, y) \in g$ . Hence $f \subset g$ . A symmetric argument gives $g \subset f$ , so $f = g$ .

Proof (logical style).

If $f = g$ , then for every $x$ ,

\begin{aligned} x \in \operatorname{dom} f &\equiv \exists y\,\bigl((x, y) \in f\bigr) \\ &\equiv \exists y\,\bigl((x, y) \in g\bigr) \equiv x \in \operatorname{dom} g, \end{aligned}

and for $x$ in this common domain $(x, f(x)) \in f = g$ , so uniqueness gives $f(x) = g(x)$ . Conversely, for every ordered pair $(x, y)$ ,

\begin{aligned} (x, y) \in f &\equiv (x \in \operatorname{dom} f) \land \bigl(y = f(x)\bigr) \\ &\equiv (x \in \operatorname{dom} g) \land \bigl(y = g(x)\bigr) \equiv (x, y) \in g. \end{aligned}

Remark.

The codomain does not enter the criterion, because under Definition 4.15 a function is simply its set of ordered pairs. Consequently the set $\{(x, x) \mid x \in S\}$ defines the identity map $\mathrm{id}_S : S \to S$ , but for any $T$ with $S \subset T$ it equally defines the inclusion map $\iota : S \to T$ . The set of pairs is identical; the declared codomain matters when we ask whether every element of the target is reached.

Example 4.20.

There is only one function from $\emptyset$ to a given set $X$ . Any two have the same domain, namely $\emptyset$ , and agree at every point of it, since there are none, so the proposition makes them equal.

Definition 4.21 (Restriction and extension).

Let $g : B \to C$ be a function and let $A \subset B$ . The restriction of $g$ to $A$ is the function $g|_A : A \to C$ given by $g|_A(x) \defeq g(x)$ . The function $g$ is called an extension of $g|_A$ to $B$ .

Example 4.22 (Informal).

Consider

\begin{aligned} f &: W \to R, & f(x) &\defeq x^2 - 1, \\ g &: R \to R, & g(x) &\defeq x^2 - 1, \\ h &: R \to R, & h(x) &\defeq (x - 1)(x + 1). \end{aligned}

By the proposition, $g = h$ : the domains agree, and the rules of school algebra give $(x-1)(x+1) = x^2 - 1$ for every real number. The function $f$ is a different object entirely. Its domain is $W$ , so it cannot equal $g$ or $h$ , even though its values agree with theirs at every whole number. It is their common restriction, $f = g|_W = h|_W$ . Equality of functions depends on domains, not on formulas.

Remark.

Definition 4.15 builds a function as a set of pairs, and the domain and codomain are read off the notation $f : X \to Y$ rather than carried by the set. A tidier alternative is to package all three, taking a function to be the ordered triple $(X, Y, G)$ of a domain, a codomain and a set $G \subset X \times Y$ obeying the vertical line test. Nothing in what follows depends on the choice, and the problems below ask you to check that the two accounts agree.

Problem 4.8.

Let $A = \{1, 2, 3\}$ and $B = \{r, s\}$ . Which of the following are functions from $A$ to $B$ ? Justify each answer.

$\{(1, r), (2, s), (3, r)\}$ ;
$\{(1, r), (2, s)\}$ ;
$\{(1, r), (1, s), (2, r), (3, s)\}$ .

Problem 4.9.

Give sets $A$ and $B$ for which $f = \{(3, 2), (1, 1), (8, 5), (9, -4), (\pi, 1)\}$ is a function from $A$ to $B$ . What is $f(8)$ , and what are the preimages of $1$ ? Is your choice of $A$ and $B$ the only one?

Problem 4.10.

Let $X$ and $Y$ be non-empty sets. Prove that $X \times Y$ is a function from $X$ to $Y$ if and only if $Y$ has exactly one element.

Problem 4.11.

Let $f : X \to Y$ be a function and define its graph to be the subset $\{(x, f(x)) \mid x \in X\}$ of $X \times Y$ .

Show that two functions $f, \tilde{f} : X \to Y$ are equal if and only if they have the same graph.
Conversely, let $G \subset X \times Y$ be such that for each $x \in X$ the set $\{y \in Y \mid (x, y) \in G\}$ has exactly one element. Show that there is exactly one function $f : X \to Y$ whose graph is $G$ .
Suppose we define a function instead to be an ordered triple $(X, Y, G)$ with $G \subset X \times Y$ obeying the vertical line test, taking the domain to be $X$ , the codomain $Y$ , and $f(x)$ the unique $y$ with $(x, y) \in G$ . Show that this definition agrees with Definition 4.15 , in the sense that every choice of domain, codomain and property obeying the vertical line test produces a function in this sense with all the properties the earlier definition requires.

Images and Preimages

Definition 4.23 (Image of a set).

Let $f : A \to B$ be a function and let $S \subset A$ . The image of $S$ under $f$ is $f(S) \defeq \{f(x) \mid x \in S\}$ . The image of the whole domain is the range of $f$ , written $\operatorname{im} f \defeq f(A)$ .

The range is a subset of the codomain, and it may be a proper one. In terms of the ordered pairs of Definition 4.15 ,

\begin{aligned} \operatorname{im} f &= \bigl\{y \in B \;\big|\; \exists x \in A\,\bigl((x, y) \in f\bigr)\bigr\} \\ &= \bigl\{y \in B \;\big|\; \exists x \in A\,\bigl(f(x) = y\bigr)\bigr\}. \end{aligned}

Definition 4.24 (Preimage of a set).

Let $f : A \to B$ be a function and let $U \subset B$ . The preimage of $U$ under $f$ is $f^{-1}(U) \defeq \{x \in A \mid f(x) \in U\}$ . In particular $f^{-1}(\{y\}) = \{x \in A \mid f(x) = y\}$ is the set of all preimages of $y \in B$ .

The notation $f^{-1}(U)$ does not assume that $f$ has an inverse function; the definition applies to every function. The set $f^{-1}(\{y\})$ may be empty, may hold one element, or may hold several.

Example 4.25.

Let $A = \{1, 2, 3, 4\}$ and $B = \{r, s, t, u\}$ , and define $f : A \to B$ by $f(1) \defeq r$ , $f(2) \defeq s$ , $f(3) \defeq s$ , $f(4) \defeq t$ . Then $f(\{1, 3\}) = \{r, s\}$ , $f(\{2, 3, 4\}) = \{s, t\}$ and $\operatorname{im} f = \{r, s, t\}$ . The element $u$ belongs to the codomain but not to the range, and its point preimage is empty. In general $f^{-1}(\{y\})$ is non-empty exactly when $y \in \operatorname{im} f$ , and how many elements it holds records how many inputs are sent to $y$ . Here $f^{-1}(\{s\}) = \{2, 3\}$ , $f^{-1}(\{r, t\}) = \{1, 4\}$ and $f^{-1}(\{u\}) = \emptyset$ .

Example 4.26 (Informal).

Take $g : R \to R$ with $g(x) \defeq x + 1$ , and let $S$ be the set of real numbers $x$ with $0 \leqslant x \leqslant 2$ . Then $g(S)$ is the set of real numbers $y$ with $1 \leqslant y \leqslant 3$ : on the one hand $0 \leqslant x \leqslant 2$ gives $1 \leqslant x + 1 \leqslant 3$ , which proves one inclusion, and on the other, any such $y$ has $y - 1$ in $S$ with $g(y - 1) = y$ , which proves the reverse. The same calculation read backwards gives $g^{-1}\bigl(g(S)\bigr) = S$ .

Proposition 4.27 (Set laws for preimages).

Let $f : A \to B$ be a function and let $U, V \subset B$ . Then

$f^{-1}(B \setminus U) = A \setminus f^{-1}(U)$ ;
$f^{-1}(U \cup V) = f^{-1}(U) \cup f^{-1}(V)$ ;
$f^{-1}(U \cap V) = f^{-1}(U) \cap f^{-1}(V)$ .

Discussion.

We prove each equality by comparing membership at an arbitrary $x$ . By the definition of the preimage, membership says that $x \in A$ and that its image has the required property. So $f(x) \in B \setminus U$ says precisely that $f(x) \notin U$ ; membership in $U \cup V$ means membership in at least one of $U$ and $V$ ; and membership in $U \cap V$ means membership in both. Translating those three conditions back through the same definition yields the complement, the union and the intersection we want.

Proof (element style).

If $x \in f^{-1}(B \setminus U)$ , then $x \in A$ and $f(x) \notin U$ , so $x \in A \setminus f^{-1}(U)$ . Conversely, if $x \in A \setminus f^{-1}(U)$ , then $f(x) \notin U$ ; since $f(x) \in B$ this puts $f(x) \in B \setminus U$ , whence $x \in f^{-1}(B \setminus U)$ .

If $x \in f^{-1}(U \cup V)$ , then $f(x)$ belongs to $U$ or to $V$ , so $x$ belongs to $f^{-1}(U) \cup f^{-1}(V)$ . Conversely, membership in that union puts $x$ in one of the two preimages, so $f(x) \in U \cup V$ and $x \in f^{-1}(U \cup V)$ .

Finally $x \in f^{-1}(U \cap V)$ gives both $f(x) \in U$ and $f(x) \in V$ , so $x \in f^{-1}(U) \cap f^{-1}(V)$ ; and membership in both preimages gives $f(x) \in U \cap V$ , which is the reverse inclusion.

Proof (logical style).

For every $x$ ,

\begin{aligned} x \in f^{-1}(B \setminus U) &\equiv (x \in A) \land \bigl(f(x) \notin U\bigr) \equiv x \in A \setminus f^{-1}(U), \\[2pt] x \in f^{-1}(U \cup V) &\equiv (x \in A) \land \bigl((f(x) \in U) \lor (f(x) \in V)\bigr) \\ &\equiv \bigl(x \in f^{-1}(U)\bigr) \lor \bigl(x \in f^{-1}(V)\bigr) \equiv x \in f^{-1}(U) \cup f^{-1}(V), \\[2pt] x \in f^{-1}(U \cap V) &\equiv (x \in A) \land \bigl((f(x) \in U) \land (f(x) \in V)\bigr) \\ &\equiv \bigl(x \in f^{-1}(U)\bigr) \land \bigl(x \in f^{-1}(V)\bigr) \equiv x \in f^{-1}(U) \cap f^{-1}(V). \end{aligned}

The middle steps distribute the conjunct $x \in A$ across the disjunction and the conjunction, which is Distributivity and, for the third line, Idempotence. The membership conditions agree in each pair, so the corresponding sets are equal.

Preimages preserve complements, unions and intersections. Images preserve unions, but need not preserve intersections, as the problems below ask you to show.

Read as the assignments $S \mapsto f(S)$ and $U \mapsto f^{-1}(U)$ , a function $f : A \to B$ induces two maps between power sets, one from $\mathcal{P}(A)$ to $\mathcal{P}(B)$ and one from $\mathcal{P}(B)$ to $\mathcal{P}(A)$ , written $f$ and $f^{-1}$ again. The two behave differently, and the proposition is the reason: the preimage map preserves all three operations, while the image map preserves only unions.

Remark.

This asymmetry is why continuity is later stated in terms of preimages rather than images: a function is continuous exactly when the preimage of every open set is open.

Problem 4.12.

For the finite function above, determine $f(\emptyset)$ , $f(\{1, 4\})$ , $f^{-1}(\{r, s\})$ and $f^{-1}(\{s, u\})$ .

Problem 4.13.

Let $f : A \to B$ be a function and let $S, T \subset A$ . Prove that $f(S \cup T) = f(S) \cup f(T)$ . Must $f(S \cap T) = f(S) \cap f(T)$ always hold?

Surjections, Injections, Bijections

Definition 4.28 (Surjection).

A function $f : A \to B$ is surjective, or onto $B$ , if $f(A) = B$ ; equivalently, if for every $y \in B$ there is some $x \in A$ with $f(x) = y$ .

Every function is surjective onto its range.

Example 4.29 (Informal).

The successor map $s : W \to W$ given by $s(n) \defeq n + 1$ is not surjective, since $0$ has no preimage among the whole numbers. The same ordered pairs define a surjection onto $W \setminus \{0\}$ . So surjectivity depends on the declared codomain, not on the pairs alone.

Definition 4.30 (Injection).

A function $f : A \to B$ is injective, or one-to-one, if for all $x_1, x_2 \in A$ , $f(x_1) = f(x_2) \implies x_1 = x_2$ .

The contrapositive of that implication says distinct inputs have distinct images. To show a function is not injective it is enough to give two distinct inputs with the same image; to show it is not surjective it is enough to give an element of the codomain with no preimage.

Proposition 4.31 (Point preimages).

Let $f : A \to B$ be a function.

$f$ is injective if and only if $f^{-1}(\{y\})$ holds at most one element for every $y \in B$ ;
$f$ is surjective if and only if $f^{-1}(\{y\})$ is non-empty for every $y \in B$ .

Discussion.

For the first part we compare the definition of injectivity with the assertion that two members of $f^{-1}(\{y\})$ coincide. In one direction two such members have equal images; in the other, equal images make the two inputs members of one point preimage. For the second part, the definition of the preimage says $f^{-1}(\{y\})$ is non-empty exactly when some $x \in A$ satisfies $f(x) = y$ , which is what surjectivity asks.

Proof.

Suppose $f$ is injective. If $x_1, x_2 \in f^{-1}(\{y\})$ , then $f(x_1) = y = f(x_2)$ , so $x_1 = x_2$ . Conversely, suppose every point preimage holds at most one element. Whenever $f(x_1) = f(x_2) = y$ , both $x_1$ and $x_2$ belong to $f^{-1}(\{y\})$ , and hence they are equal. This proves the first part.

The second is the surjectivity condition rewritten: $f^{-1}(\{y\})$ is non-empty exactly when some $x \in A$ satisfies $f(x) = y$ .

Example 4.32 (Informal).

For a real number $c$ , the translation $\tau_c : R \to R$ given by $\tau_c(x) \defeq x + c$ is injective and surjective. If $\tau_c(x_1) = \tau_c(x_2)$ , then $x_1 + c = x_2 + c$ , and adding $-c$ to both sides gives $x_1 = x_2$ . For surjectivity, take any $y$ and put $x = y - c$ ; then $\tau_c(x) = (y - c) + c = y$ , so every element of the codomain has a preimage.

Example 4.33 (Informal).

The squaring map $q : R \to R$ with $q(x) \defeq x^2$ is neither injective nor surjective: $q(-1) = q(1)$ , and $-1$ lies outside its range because every square is non-negative.

Example 4.34 (Informal).

The product map $m : W \times W \to W$ with $m(a, b) \defeq ab$ is surjective, since $m(n, 1) = n$ for every whole number $n$ . It is not injective, since $m(1, 6) = m(2, 3)$ while $(1, 6) \neq (2, 3)$ by Proposition 4.2 .

Problem 4.14.

For the finite function of the previous section, decide whether it is injective and whether it is surjective, justifying each answer from the definitions.

Problem 4.15.

Let $A$ be non-empty and let $B$ have exactly two elements. How many functions from $A$ to $B$ are not surjective?

Problem 4.16.

A function $f : A \to B$ is a set of ordered pairs, so its pairs may be reversed to form the set $\rho(f) \defeq \{(y, x) \in B \times A \mid (x, y) \in f\}$ . Call the set of first coordinates of a set of pairs its domain.

Determine $\rho$ of the set $\{(1, r), (2, s), (3, r)\}$ of Problem 4.8 and of the function $f$ of Problem 4.9 , and say which of the two is a function.
Prove that if $f$ is not injective, then $\rho(f)$ is not a function.
Prove that if $f$ is injective but not surjective, then $\rho(f)$ is a function whose domain $D$ satisfies $D \subsetneq B$ .

Bijections

Definition 4.35 (Bijection).

A function $f : A \to B$ is bijective, or a bijection, if it is both injective and surjective. A bijection from $A$ to $B$ is also called a one-to-one correspondence between them.

Surjectivity asks for at least one preimage of each point of the codomain and injectivity permits at most one, so a bijection has exactly one.

Proposition 4.36 (Unique preimages).

A function $f : A \to B$ is bijective if and only if for every $y \in B$ there is a unique $x \in A$ with $f(x) = y$ .

Discussion.

We use the two parts of Proposition 4.31 . If $f$ is bijective, surjectivity gives a preimage of each $y \in B$ and injectivity shows no second preimage is possible. Conversely, existence of a preimage for every $y$ gives surjectivity, and its uniqueness gives injectivity. The same criterion is what will let us reverse the ordered pairs of a bijection later.

Proof.

Suppose first that $f$ is bijective. Surjectivity supplies, for each $y \in B$ , an $x \in A$ with $f(x) = y$ . If $x_1$ and $x_2$ both have this property, then $f(x_1) = f(x_2)$ , so injectivity gives $x_1 = x_2$ .

Conversely, suppose every $y \in B$ has exactly one preimage. Existence makes $f$ surjective. If $f(x_1) = f(x_2)$ , both $x_1$ and $x_2$ are preimages of the same element of $B$ , so uniqueness gives $x_1 = x_2$ and $f$ is injective as well.

For finite sets, an injection from $A$ to $B$ needs at least as many elements in $B$ as in $A$ , and a surjection needs at least as many in $A$ as in $B$ ; a bijection therefore forces the two to have the same number of elements. Comparing sets by functions rather than by counting is what will extend this to infinite sets, where counting is no longer available.

Example 4.37.

With $A = \{1, 2, 3, 4\}$ and $B = \{r, s, t, u\}$ as above, take $\beta \defeq \{(1, s), (2, u), (3, r), (4, t)\}$ . Each member of $A$ appears once as a first coordinate and each member of $B$ once as a second, so $\beta : A \to B$ is a bijection. The function $f$ of the previous section is neither injective nor surjective: $s$ is hit twice and $u$ is not hit at all.

Proposition 4.38 (An injection onto its range).

If $f : A \to B$ is injective, then the function from $A$ to $f(A)$ with the same ordered pairs is bijective.

Discussion.

The new function has the same ordered pairs as $f$ , so injectivity carries over unchanged, the definition mentioning only inputs and their images. For surjectivity, take $y$ in the new codomain $f(A)$ ; the definition of the image provides an $x \in A$ with $f(x) = y$ , which is the preimage required.

Proof.

Changing the codomain from $B$ to $f(A)$ does not alter the ordered pairs, and injectivity is a condition on those alone, so the new function is injective. Every $y \in f(A)$ is $f(x)$ for some $x \in A$ by the definition of the image, so it is also surjective.

Every translation is a bijection, by the example above, and so is the identity map $\mathrm{id}_A$ , since each $y \in A$ is its own unique preimage. The squaring map and the product map are not, each having already failed one of the two conditions.

Problem 4.17.

Let $f : A \to B$ be bijective and let $S \subset A$ . Prove that the restriction $f|_S : S \to f(S)$ is bijective.

Problem 4.18.

For each of the following, exhibit sets $A$ and $B$ , a subset $C \subset A$ and a function $f : A \to B$ meeting the condition, or show that none exists.

$f$ is surjective and $f|_C$ is surjective.
$f$ is surjective and $f|_C$ is not.
$f$ is injective and $f|_C$ is injective.
$f$ is injective and $f|_C$ is not.

Problem 4.19.

Let $f : A \to B$ be injective and let $S, T \subset A$ . Prove that $f(S \cap T) = f(S) \cap f(T)$ .

Problem 4.20.

Let $A$ , $B$ and $C$ be sets. Prove that

\bigl(x, (y, z)\bigr) \longmapsto \bigl((x, y), z\bigr)

is a bijection from $A \times (B \times C)$ onto $(A \times B) \times C$ , so that the two readings of a triple product agree up to that correspondence. Show also that the two sets are not in general equal, by exhibiting an element of one which is not an element of the other.

Composition

Definition 4.39 (Composition).

Let $f : A \to B$ and $g : B \to C$ be functions. Their composition is the function $g \circ f : A \to C$ given by $(g \circ f)(x) \defeq g(f(x))$ .

The notation is read from right to left: $f$ acts first and $g$ second. The codomain of $f$ must be the domain of $g$ , so that every value of $f$ can serve as an input of $g$ .

Example 4.40 (Informal).

For the squaring map $q$ and the translation $\tau_1$ above, $(q \circ \tau_1)(x) = (x + 1)^2$ while $(\tau_1 \circ q)(x) = x^2 + 1$ . At $x = 1$ these take the values $4$ and $2$ , so $q \circ \tau_1 \neq \tau_1 \circ q$ by Proposition 4.19 . Composition is not commutative.

Theorem 4.41 (Associativity of composition).

Let $f : A \to B$ , $g : B \to C$ and $h : C \to D$ be functions. Then $h \circ (g \circ f) = (h \circ g) \circ f$ .

Discussion.

By Proposition 4.19 we must check that the two functions have the same domain and agree at every input. Both are functions from $A$ to $D$ , so only the values are in question, and at an arbitrary $x \in A$ the definition of composition evaluates either side by applying $f$ , then $g$ , then $h$ .

Proof.

Both sides have domain $A$ . For every $x \in A$ , $\bigl(h \circ (g \circ f)\bigr)(x) = h\bigl(g(f(x))\bigr) = \bigl((h \circ g) \circ f\bigr)(x),$ so Proposition 4.19 gives the equality.

Associativity lets us write $h \circ g \circ f$ without brackets. The identity maps satisfy the identity laws one expects.

Proposition 4.42 (Identity laws).

If $f : A \to B$ , then $\mathrm{id}_B \circ f = f$ and $f \circ \mathrm{id}_A = f$ .

Discussion.

Again Proposition 4.19 reduces each identity to a comparison of domains and values. Both sides of each have domain $A$ , and at an arbitrary $x \in A$ the definitions of composition and of the identity map reduce both composites to $f(x)$ .

Proof.

For every $x \in A$ we have $(\mathrm{id}_B \circ f)(x) = \mathrm{id}_B(f(x)) = f(x)$ and $(f \circ \mathrm{id}_A)(x) = f(\mathrm{id}_A(x)) = f(x)$ . Each pair of functions has the same domain, so Proposition 4.19 applies.

Theorem 4.43 (Composition and bijections).

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

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

Discussion.

For the first part the definition of injectivity asks us to start from an equality of composite values; expanding the composition, injectivity of $g$ gives equality of the $f$ -values, and injectivity of $f$ then gives equality of the inputs. For the second, take an arbitrary $z \in C$ , choose $y \in B$ with $g(y) = z$ , then choose $x \in A$ with $f(x) = y$ , and evaluate the composite at $x$ . The third is the first two together with the definition of a bijection.

Proof.

Suppose $(g \circ f)(x_1) = (g \circ f)(x_2)$ , that is, $g(f(x_1)) = g(f(x_2))$ . Injectivity of $g$ gives $f(x_1) = f(x_2)$ , and injectivity of $f$ then gives $x_1 = x_2$ , which is the first part.

For the second, take $z \in C$ . Since $g$ is surjective, some $y \in B$ has $g(y) = z$ ; since $f$ is surjective, some $x \in A$ has $f(x) = y$ . Then $(g \circ f)(x) = g(f(x)) = g(y) = z$ . The third part follows from the other two.

Problem 4.21.

Let $f : A \to B$ and $g : B \to C$ . Prove that if $g \circ f$ is injective then $f$ is injective, and that if $g \circ f$ is surjective then $g$ is surjective.

Problem 4.22.

Construct finite sets $A$ , $B$ , $C$ and functions $f : A \to B$ , $g : B \to C$ for which $g \circ f$ is bijective although $f$ is not surjective and $g$ is not injective.

Inverse Functions

Definition 4.44 (Inverse function).

Let $f : A \to B$ and $g : B \to A$ be functions. The function $g$ is an inverse of $f$ if $g \circ f = \mathrm{id}_A$ and $f \circ g = \mathrm{id}_B$ . A function which has an inverse is called invertible.

The first equation returns each element of $A$ after applying $f$ and then $g$ ; the second does the same for $B$ . The problems below examine what each equation achieves on its own.

Theorem 4.45 (Invertibility and bijections).

A function is invertible if and only if it is bijective, and when an inverse exists it is unique.

Discussion.

Suppose first that $g$ is an inverse of $f$ . To get injectivity, apply $g$ to an equality $f(x_1) = f(x_2)$ and use $g \circ f = \mathrm{id}_A$ ; to get surjectivity, use $g(y)$ as a preimage of an arbitrary $y \in B$ and use $f \circ g = \mathrm{id}_B$ . Conversely, Proposition 4.36 gives exactly one reversed pair $(y, x)$ for each $y \in B$ , so the set of reversed pairs passes the vertical line test and is a function from $B$ to $A$ ; the two inverse identities are then those pairs read in the two directions. For uniqueness, two inverses are compared by sandwiching $f$ between them, where associativity and the identity laws collapse the composite in two ways.

Proof.

Let $f : A \to B$ have an inverse $g : B \to A$ . If $f(x_1) = f(x_2)$ , then $x_1 = g(f(x_1)) = g(f(x_2)) = x_2$ , so $f$ is injective. Given $y \in B$ , put $x = g(y)$ ; the second identity gives $f(x) = f(g(y)) = y$ , so $f$ is surjective.

Conversely, suppose $f$ is bijective and set $g \defeq \{(y, x) \in B \times A \mid (x, y) \in f\}$ . For each $y \in B$ , Proposition 4.36 gives a unique $x \in A$ with $f(x) = y$ , so $g$ is a function from $B$ to $A$ . Reading the pairs in each direction gives $g(f(x)) = x$ for $x \in A$ and $f(g(y)) = y$ for $y \in B$ , that is, $g \circ f = \mathrm{id}_A$ and $f \circ g = \mathrm{id}_B$ .

For uniqueness, let $g$ and $h$ both be inverses of $f$ . Associativity and the identity laws give

g = \mathrm{id}_A \circ g = (h \circ f) \circ g = h \circ (f \circ g) = h \circ \mathrm{id}_B = h.

The unique inverse of a bijection $f$ is written $f^{-1}$ . The construction in the proof gives

f^{-1} = \{(y, x) \in B \times A \mid (x, y) \in f\}, \qquad\text{so}\qquad f^{-1}(y) = x \iff f(x) = y.

Remark.

The symbol $f^{-1}$ also denotes the preimage of a set. The two uses are distinct: $f^{-1}(y)$ is an element of $A$ produced by the inverse function, and exists only for a bijection, while $f^{-1}(U)$ is a subset of $A$ and is defined for every function. For a bijection they are related by $f^{-1}(\{y\}) = \{f^{-1}(y)\}$ , the preimage of a point being the singleton of its inverse image.

Example 4.46.

Reversing the pairs of the bijection $\beta = \{(1, s), (2, u), (3, r), (4, t)\}$ gives $\beta^{-1} = \{(s, 1), (u, 2), (r, 3), (t, 4)\}$ . Also $\mathrm{id}_A^{-1} = \mathrm{id}_A$ for any set $A$ .

Example 4.47 (Informal).

The translations invert one another: $\tau_c^{-1} = \tau_{-c}$ , since $\tau_{-c}(\tau_c(x)) = x = \tau_c(\tau_{-c}(x))$ for every real number $x$ .

Proposition 4.48 (The inverse is a bijection).

If $f : A \to B$ is bijective, then $f^{-1} : B \to A$ is bijective and $(f^{-1})^{-1} = f$ .

Discussion.

The two equations defining an inverse are symmetric in $f$ and $f^{-1}$ , so they say equally that $f$ is an inverse of $f^{-1}$ . That makes $f^{-1}$ invertible, and the theorem above turns invertibility into bijectivity; its uniqueness clause then names $f$ as the inverse of $f^{-1}$ .

Proof.

The identities $f^{-1} \circ f = \mathrm{id}_A$ and $f \circ f^{-1} = \mathrm{id}_B$ also say that $f$ is an inverse of $f^{-1}$ . So $f^{-1}$ is invertible and hence bijective by Theorem 4.45 , and uniqueness of its inverse gives $(f^{-1})^{-1} = f$ .

Theorem 4.49 (Inverse of a composition).

If $f : A \to B$ and $g : B \to C$ are bijections, then $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ .

Discussion.

Put $k \defeq f^{-1} \circ g^{-1}$ . Rather than compute $(g \circ f)^{-1}$ we show directly that $k$ meets the definition of an inverse of $g \circ f$ : evaluate $k \circ (g \circ f)$ at an arbitrary $x \in A$ and $(g \circ f) \circ k$ at an arbitrary $z \in C$ , where associativity and the inverse identities cancel the adjacent pairs. Since $g \circ f$ is bijective, uniqueness of inverses then identifies $k$ as the one.

Proof.

Put $k \defeq f^{-1} \circ g^{-1} : C \to A$ . For $x \in A$ and $z \in C$ ,

\bigl(k \circ (g \circ f)\bigr)(x) = f^{-1}\bigl(g^{-1}(g(f(x)))\bigr) = x, \qquad \bigl((g \circ f) \circ k\bigr)(z) = g\bigl(f(f^{-1}(g^{-1}(z)))\bigr) = z.

So $k$ is an inverse of $g \circ f$ , which is bijective by Theorem 4.43 , and uniqueness in Theorem 4.45 gives the formula.

Corollary 4.50 (Cancellation by a bijection).

Let $f : B \to C$ be bijective and let $g, h : A \to B$ . Then $f \circ g = f \circ h$ implies $g = h$ . Likewise, if $f : A \to B$ is bijective and $r, s : B \to C$ , then $r \circ f = s \circ f$ implies $r = s$ .

Proof.

For the first, compose on the left with $f^{-1}$ and use associativity:

\begin{aligned} g &= (f^{-1} \circ f) \circ g = f^{-1} \circ (f \circ g) \\ &= f^{-1} \circ (f \circ h) = (f^{-1} \circ f) \circ h = h. \end{aligned}

For the second, compose on the right with $f^{-1}$ :

\begin{aligned} r &= r \circ (f \circ f^{-1}) = (r \circ f) \circ f^{-1} \\ &= (s \circ f) \circ f^{-1} = s \circ (f \circ f^{-1}) = s. \end{aligned}

Problem 4.23 (Informal).

Let $a$ and $b$ be real numbers with $a \neq 0$ . Prove that $F : R \to R$ given by $F(x) \defeq ax + b$ is bijective, and determine $F^{-1}$ .

Problem 4.24.

Let $f : A \to B$ be bijective and let $S \subset A$ . Determine the inverse of $f|_S : S \to f(S)$ .

Problem 4.25.

Let $f : A \to B$ and $g : B \to A$ . Prove that $g \circ f = \mathrm{id}_A$ forces $f$ to be injective and $g$ to be surjective, while $f \circ g = \mathrm{id}_B$ forces $f$ to be surjective and $g$ to be injective.

Left and Right Inverses

Definition 4.51 (Left and right inverses).

Let $f : A \to B$ and $g : B \to A$ be functions. The function $g$ is a left inverse of $f$ if $g \circ f = \mathrm{id}_A$ , and a right inverse of $f$ if $f \circ g = \mathrm{id}_B$ . When it is both, it is an inverse in the earlier sense.

The names record the side on which $g$ sits in the composite. The last problem above gave two implications: a left inverse makes $f$ injective, and a right inverse makes $f$ surjective. The next theorem combines them.

Theorem 4.52 (Bijections via one-sided inverses).

Let $f : A \to B$ be a function. Then $f$ is bijective if and only if it has both a left inverse and a right inverse; when both exist they coincide, and their common value is $f^{-1}$ .

Discussion.

One direction is immediate: a bijection has $f^{-1}$ , which is a left and a right inverse by definition. For the other, the left inverse gives injectivity and the right inverse gives surjectivity, so $f$ is bijective and $f^{-1}$ exists. To identify the one-sided inverses with each other we evaluate the triple composite $g_l \circ f \circ g_r$ in its two groupings: associativity and the identity laws collapse the middle pair either way, leaving $g_l = g_r$ . The same calculation with $f^{-1}$ in place of either names their common value.

Proof.

Suppose $f$ has a left inverse $g_l$ and a right inverse $g_r$ . If $f(x_1) = f(x_2)$ , then $x_1 = g_l(f(x_1)) = g_l(f(x_2)) = x_2$ , so $f$ is injective. For $y \in B$ , the element $g_r(y) \in A$ satisfies $f(g_r(y)) = y$ , so $f$ is surjective. Hence $f$ is bijective and $f^{-1}$ exists by Theorem 4.45 . Associativity and the identity laws give

\begin{aligned} g_l &= g_l \circ \mathrm{id}_B = g_l \circ (f \circ g_r) \\ &= (g_l \circ f) \circ g_r = \mathrm{id}_A \circ g_r = g_r, \end{aligned}

so the two agree; and since $f^{-1}$ is itself both a left and a right inverse of $f$ , the same computation identifies their common value with $f^{-1}$ .

Conversely, if $f$ is bijective then $f^{-1}$ is a left and a right inverse by definition.

Theorem 4.53 (Injections and left inverses).

Let $A$ be non-empty. A function $f : A \to B$ is injective if and only if it has a left inverse.

Discussion.

If a left inverse exists, injectivity is the implication already noted. For the converse, an injective $f$ is a bijection onto its range by Proposition 4.38 , so it has an inverse there. On the range a left inverse is forced to be that one, since $g(f(x)) = x$ determines $g$ at every point of $f(A)$ ; on the rest of $B$ we are free, and non-emptiness of $A$ lets us send all of $B \setminus f(A)$ to one fixed element. That freedom is why left inverses are rarely unique. The hypothesis on $A$ cannot be dropped: the function from $\emptyset$ to $B$ is injective, but a function from $B$ to $\emptyset$ exists only when $B$ is empty.

Proof.

Suppose first that $g \circ f = \mathrm{id}_A$ . If $f(x_1) = f(x_2)$ , then $x_1 = g(f(x_1)) = g(f(x_2)) = x_2$ , so $f$ is injective.

Conversely, assume $f$ is injective. By Proposition 4.38 the function from $A$ to $f(A)$ with the same pairs is bijective; let $h : f(A) \to A$ be its inverse, which exists by Theorem 4.45 . Fix $x_0 \in A$ , which we may do since $A$ is non-empty, and define $g : B \to A$ by $g(y) \defeq h(y)$ for $y \in f(A)$ and $g(y) \defeq x_0$ for $y \in B \setminus f(A)$ . For every $x \in A$ the point $f(x)$ lies in $f(A)$ and $h(f(x)) = x$ , so $g(f(x)) = x$ and $g \circ f = \mathrm{id}_A$ .

For surjections the situation is different. A right inverse forces surjectivity, as we have seen; the converse, that every surjection has a right inverse, is a claim of a different kind. A right inverse must choose, for every $y \in B$ at once, one element of $f^{-1}(\{y\})$ , and when $B$ is infinite nothing among our axioms says such a simultaneous choice can be made. That is what the axiom of choice provides.

Problem 4.26.

Let $A$ be non-empty and $f : A \to B$ injective. Show that any two left inverses of $f$ agree on $f(A)$ . For the inclusion map from $\{1, 2\}$ to $\{1, 2, 3\}$ , exhibit two left inverses and say where they differ.

General Cartesian Products

With functions in hand we can take the product of an arbitrary collection of sets, not just two. First, the informal indexed family of the earlier section can now be said properly.

Remark.

An indexed family $\{A_\alpha\}_{\alpha \in I}$ of subsets of a set $A$ is formally a function $\varphi : I \to \mathcal{P}(A)$ , with $A_\alpha \defeq \varphi(\alpha)$ . It is the function itself, not its range: the range is the plain set of members, which forgets the labels, as in the earlier example, while $\varphi$ remembers which member sits at which index. Since $\varphi$ is a subset of $I \times \mathcal{P}(A)$ , it is a set by the axioms of the last chapter, and that is why we ask that all the $A_\alpha$ be subsets of one set $A$ .

Definition 4.54 (General Cartesian product).

Let $I$ be a set and let $\{A_\alpha\}_{\alpha \in I}$ be an indexed family of sets, all of them subsets of a given set. The Cartesian product of the family is

\prod_{\alpha \in I} A_\alpha \defeq \Bigl\{ f \in \mathcal{P}\Bigl(I \times \bigcup_{\alpha \in I} A_\alpha\Bigr) \;\Big|\; f \text{ is a function},\ \operatorname{dom} f = I,\ \forall \alpha \in I\,\bigl(f(\alpha) \in A_\alpha\bigr) \Bigr\}.

The notation is easier to read once we recall that a function from $I$ to $\bigcup_{\alpha \in I} A_\alpha$ is by Definition 4.15 a subset of $I \times \bigcup_{\alpha \in I} A_\alpha$ . So every candidate lies in the power set displayed above, a set we are already holding, and comprehension carves the product out of it. An element of the product picks one member from each $A_\alpha$ , all at once.

Example 4.55.

The definition subsumes the earlier one. A function $f$ defined on the two-element set $\{0, 1\}$ is determined by the pair of values $\bigl(f(0), f(1)\bigr)$ , so the functions with $f(0) \in A$ and $f(1) \in B$ correspond to the pairs $(a, b)$ with $a \in A$ and $b \in B$ . This identifies $A \times B$ with the general product for $I = \{0, 1\}$ , $A_0 = A$ and $A_1 = B$ , and we will not distinguish between the two readings from here on.

Definition 4.56 (Cartesian power).

Let $I$ and $A$ be sets. The Cartesian power $A^I$ is the product of the constant family,

A^I \defeq \prod_{\alpha \in I} A = \{f \in \mathcal{P}(I \times A) \mid f \text{ is a function with } \operatorname{dom} f = I\}.

Problem 4.27.

Let $A$ , $B$ and $C$ be sets, with $B^A$ the Cartesian power of Definition 4.56 .

Prove that if $A \subset B$ , then $A^C \subset B^C$ .
Prove that $\emptyset^A = \emptyset$ for every non-empty $A$ , and that $B^{\emptyset} = \{\emptyset\}$ for every $B$ .
Prove that $A^B \cap A^C = \emptyset$ whenever $B \neq C$ , and deduce that $\{1, 2\}^{\{1,2\}}$ and $\{1, 2\}^{\{1,2,3\}}$ are disjoint.

Problem 4.28.

Let $S$ be a set. For each $A \subset S$ , the characteristic function of $A$ is the function $\chi_A : S \to \{0, 1\}$ with $\chi_A(x) \defeq 1$ for $x \in A$ and $\chi_A(x) \defeq 0$ for $x \notin A$ ; so $\chi_A(1) = \chi_A(2) = \chi_A(4) = 1$ and $\chi_A(3) = 0$ when $S = \{1, 2, 3, 4\}$ and $A = \{1, 2, 4\}$ .

Give the formulas for $\chi_{\emptyset}$ and $\chi_S$ .
Express $\chi_{\overline{A}}$ in terms of $\chi_A$ , where $\overline{A}$ is the complement of $A$ in $S$ .
Prove that $A = B$ if and only if $\chi_A = \chi_B$ , for all $A, B \subset S$ .
Prove that $\chi_{A \cap B}(x) = \chi_A(x)\,\chi_B(x)$ and $\chi_{A \cup B}(x) = \chi_A(x) + \chi_B(x) - \chi_A(x)\,\chi_B(x)$ for every $x \in S$ .

Problem 4.29.

Keep the characteristic functions of the previous problem.

Prove that every function $u : S \to \{0, 1\}$ is $\chi_A$ for exactly one $A \subset S$ .
Suppose $S$ has $n$ elements. Determine the number of elements of $\{0, 1\}^S$ , and use the first part to count $\mathcal{P}(S)$ .

Problem 4.30.

Let $S$ be a set.

Prove that no function $g : S \to \mathcal{P}(S)$ is surjective.
Deduce that there is no bijection from $S$ to $\mathcal{P}(S)$ , and decide whether there can be a surjection from $\mathcal{P}(S)$ to $S$ .

The product of two non-empty sets is non-empty, witnessed by any pair $(x, y)$ with $x \in A$ and $y \in B$ , and the same argument covers three sets, four, and any collection we can write out in full. Once $I$ is infinite the argument fails for the reason we met in the last chapter: we have no way to string an unspecified number of such choices together. Closing that gap takes another axiom.

The Axiom of Choice

Axiom 4.57 (Choice).

Let $I$ be a non-empty set and let $\{A_\alpha\}_{\alpha \in I}$ be an indexed family of sets with $A_\alpha \neq \emptyset$ for every $\alpha \in I$ . Then there exists a function $f : I \to \bigcup_{\alpha \in I} A_\alpha$ with $\operatorname{dom} f = I$ and $f(\alpha) \in A_\alpha$ for every $\alpha \in I$ . Equivalently, a non-empty family of non-empty sets has non-empty product.

Such an $f$ is a choice function for the family. The point is the order of the quantifiers: the hypothesis grants each set an element of its own, while the conclusion assembles one selection from every set into a single function.

Remark.

The axiom is independent of the others, in the sense that neither it nor its negation follows from them. In sets carrying some structure a distinguished element can often be picked out constructively, and no axiom is needed; the axiom supplies one in full generality, where no rule for choosing is available. Mathematicians find it rather less comfortable than the rest, so it is good practice, which we will follow, to say plainly whenever it is used.

Theorem 4.58 (Every surjection has a right inverse).

Let $f : A \to B$ be surjective. Then $f$ has a right inverse $g : B \to A$ .

Discussion.

Surjectivity says, through Proposition 4.31 , that every point preimage $f^{-1}(\{y\})$ is non-empty. That is exactly the hypothesis of the axiom of choice applied to the family of point preimages indexed by $B$ , and what the axiom returns is a function $\varphi$ picking one element out of each. The union of the point preimages is $A$ , and $\varphi(y) \in f^{-1}(\{y\})$ says precisely that $f(\varphi(y)) = y$ , which is the right-inverse identity. The axiom is needed here: each preimage alone has an element, and the theorem needs one choice per preimage assembled into a single map.

Proof.

If $B$ is empty then so is $A$ , since every element of $A$ would have an image in $B$ , and the empty function is a right inverse; so assume $B$ is non-empty. For every $y \in B$ the set $f^{-1}(\{y\})$ is non-empty by Proposition 4.31 . Applying the axiom of choice to the family $\{f^{-1}(\{y\})\}_{y \in B}$ gives a function $\varphi$ from $B$ to $\bigcup_{y \in B} f^{-1}(\{y\})$ with $\varphi(y) \in f^{-1}(\{y\})$ for every $y \in B$ . Each point preimage is a subset of $A$ , so that union is $A$ and $\varphi : B \to A$ . Finally $\varphi(y) \in f^{-1}(\{y\})$ is equivalent to $f(\varphi(y)) = y$ , so $f \circ \varphi = \mathrm{id}_B$ and $\varphi$ is a right inverse of $f$ .

Corollary 4.59 (Surjections and right inverses).

A function $f : A \to B$ is surjective if and only if it has a right inverse.

Proof.

One direction is the theorem. For the other, a right inverse $g$ gives $f(g(y)) = y$ for every $y \in B$ , so $g(y)$ is a preimage of $y$ and $f$ is surjective.

Problem 4.31.

Let $I = \{1, 2, 3\}$ and let $\{M_i\}_{i \in I}$ be a family of non-empty sets. Show that $\prod_{i \in I} M_i$ is non-empty without appealing to the axiom of choice. Where would the argument break down for an index set that cannot be written out in full?

Exercises

Answers are checked in your browser, as often as you like. Nothing is sent anywhere and nothing is kept but your own work. A formula may be written with the symbols themselves or with ~ & | -> <-> ^, and \and, \or, \to expand as you type.

Exercises in Lean

The proofs below are checked in your browser. Nothing is sent anywhere, and nothing is stored but your own work. Type \to for →, \and for ∧, \< and \> for ⟨ ⟩.

The last sheet gave the checker a universe of objects and the algebra of sets. This one adds the constructions of this chapter: the ordered pair, the product, the indexed family and the map.

A pair is typed as it is written, (a, b), and longer tuples nest to the left exactly as Definition 4.4 says, so (a, b, c) is ((a, b), c). The product is ×, typed \x, and it binds like ∩. A map is written f : Obj → Obj and applied by juxtaposition, f x; the domain and codomain of Definition 4.15 are carried by the statement being proved rather than by the arrow.

One piece of the last chapter is written out here for the first time as well: a set listed by its members, {x} and {x, y}. Its membership criterion is the equation the pairing axiom gives, so y ∈ {x} is y = x, and the later exercises use it to name a set with a single point in it.

Ordered pairs

The pair itself is opaque: the checker knows nothing about $\bigl\{\{a\}, \{a, b\}\bigr\}$ , only what Proposition 4.2 established about it. That proposition is Set.pair_eq, a biconditional, so .mp reads coordinates off an equality of pairs and .mpr builds one.

Example.

The forward direction turns the equality into a conjunction; the first half of it is the first coordinate.

Exercise 4.12.

Corollary 4.3 , in one direction.

Exercise 4.13.

Coordinates read off one pair and put back into another.

Exercise 4.14.

A triple is a pair of a pair, so its middle coordinate takes two steps to reach.

Products

Membership in a product is the dictionary line of the chapter: (x, y) ∈ A × B is x ∈ A ∧ y ∈ B, in the way that x ∈ A ∩ B was a conjunction on the last sheet, so ⟨_, _⟩ builds one and .left and .right take one apart.

Example.

Two memberships, one pair.

An arbitrary object is not written as a pair, and for it the criterion says the rest of Definition 4.6 : p ∈ A × B is

∃ a, ∃ b, p = (a, b) ∧ a ∈ A ∧ b ∈ B

so a membership hypothesis about an unknown $p$ hands over two coordinates, an equation and two memberships. obtain takes all five at once, and the equation is what rw then uses to turn $p$ into a pair everywhere it is needed.

Example.

Once $p$ has been rewritten, the goal is about a pair and the criterion applies to it.

Exercise 4.15.

The coordinates change places and so do the factors.

Exercise 4.16.

Nothing can serve as a second coordinate.

Exercise 4.17.

The product respects inclusion in each factor.

Exercise 4.18.

Products distribute over intersections.

Exercise 4.19.

And over unions.

Exercise 4.20.

An intersection of products is a product of intersections.

Exercise 4.21.

The inclusion that never fails.

Exercise 4.22.

The equality the last exercise fell short of, with the two mixed products restored.

Indexed families

A family $\{B_i\}_{i \in I}$ is a map from indices to sets, written B : Obj → Obj, and its union and intersection are ⋃ i ∈ I, B i and ⋂ i ∈ I, B i, typed \bigcup and \bigcap. Their criteria are the two the chapter gave: membership in the union is ∃ i, i ∈ I ∧ x ∈ B i, and membership in the intersection is ∀ i, i ∈ I → x ∈ B i. So an intersection is used by applying it to an index and a proof that the index belongs to $I$ , and a union is built with use.

Example.

The intersection applied at one index.

Example.

use supplies the index; what remains is that the index is one of ours and that $x$ lies in its set.

An object outside an intersection misses some set, but we are not given its index: all we hold is that no index can be a witness. Getting the index out is the classical step, and by_contra twice is what does it.

Example.

The first by_contra denies the index we want; the second turns that denial into membership at every index, which contradicts the hypothesis.

Exercise 4.23.

A set lies inside the intersection exactly when it lies inside every member.

Exercise 4.24.

And the union lies inside a set exactly when every member does.

Exercise 4.25.

The first part of Proposition 4.13 .

Exercise 4.26.

The second part. The hypothesis hj is the non-emptiness of $I$ , and one of the two inclusions cannot be had without it.

Exercise 4.27.

The inclusion between the two mixed families, in the direction that holds.

Maps

For a map f : Obj → Obj, the image and preimage of a set are f '' S and f ⁻¹' U, typed as two apostrophes and as \preimage. Their criteria are those of Definition 4.23 and Definition 4.24 : y ∈ f '' S is ∃ x, x ∈ S ∧ f x = y, and x ∈ f ⁻¹' U is f x ∈ U. Composition is g ∘ f, typed \o, and (g ∘ f) x is g (f x). Finally Injective f and Surjective f are the two conditions of Definition 4.30 and Definition 4.28 , ∀ x y, f x = f y → x = y and ∀ y, ∃ x, f x = y, so both are opened with intro.

Example.

The witness is the point itself, and the equation it has to satisfy is an identity.

The preimage passes membership straight through to $f x$ , which is why it preserves the operations: both sides of each law are the same statement about $f x$ .

Example.

Part three of Proposition 4.27 , which follows from the criterion.

Exercise 4.28.

Images preserve unions.

Exercise 4.29.

Every point of $S$ is sent into the image of $S$ .

Exercise 4.30.

And the image of a preimage is no bigger than the set it came from.

Exercise 4.31.

The first part of Theorem 4.43 .

Exercise 4.32.

Its second part.

Exercise 4.33.

Only the first map need be injective for the composite to be.

Exercise 4.34.

And only the second need be surjective.

Exercise 4.35.

A left inverse, written out pointwise, makes $f$ injective.

Exercise 4.36.

A right inverse makes it surjective.

Exercise 4.37.

Images preserve intersections exactly when the map is injective.

Exercise 4.38.

The inclusion two exercises above becomes an equality for an injective map.

Exercise 4.39.

And the other inclusion becomes an equality for a surjective one.

Exercise 4.40.

An image loses no more than the part removed.

Exercise 4.41.

Injectivity closes the gap.

Exercise 4.42.

The converse of the exercise three above: only an injection returns every set unchanged.

Exercise 4.43.

And nothing but a surjection.

A map $f : A \to B$ carries two maps between the power sets with it, $F : \mathcal{P}(A) \to \mathcal{P}(B)$ sending $S$ to $f(S)$ and $G : \mathcal{P}(B) \to \mathcal{P}(A)$ sending $U$ to $f^{-1}(U)$ . The checker has no power set to quantify over, so each of the four statements below says what injectivity or surjectivity of $F$ or of $G$ amounts to at the level of the sets themselves.

Exercise 4.44.

$f$ is injective exactly when $F$ is.

Exercise 4.45.

And surjective exactly when $F$ is.

Exercise 4.46.

The other pairing: $f$ is injective exactly when $G$ is surjective.

Exercise 4.47.

And surjective exactly when $G$ is injective.

What the checker understands

Tactics

intro h	assume the hypothesis of an implication, naming it h
exact e	give the proof outright
apply f	reduce the goal to the hypotheses of f
assumption	close the goal with a hypothesis already present
trivial	close the goal True
exfalso	replace the goal with False
by_contra h	assume the negation of the goal
constructor	split ∧ into both halves, or ↔ into both directions
left / right	choose which half of a ∨ to prove
rcases h with a \| b	argue by cases on a disjunction
obtain ⟨a, b⟩ := h	take a conjunction or an existential apart
cases h	as above, keeping the name
refine e	give the proof with holes left in it
have h : p := …	record an intermediate result
show p	restate the goal in an equal form
use w	give a witness for ∃
specialize h a	instantiate a ∀ hypothesis
rw [h]	rewrite with an equation, ← to go backwards
rfl	both sides compute to the same thing
decide / norm_num	settle a closed computation
tauto	close a goal that is true by pure logic

Results you may cite

Classical.em	∀ (a : Prop), a ∨ ¬a — the law of excluded middle
Classical.byContradiction	∀ {a : Prop}, (¬a → False) → a — proof by contradiction; the tactic by_contra does this for you
Classical.byCases	∀ {a b : Prop}, (a → b) → (¬a → b) → b — split on whether a holds
not_not	∀ {a : Prop}, ¬¬a ↔ a — double negation
not_and_or	∀ {a b : Prop}, ¬(a ∧ b) ↔ ¬a ∨ ¬b — De Morgan
not_or	∀ {a b : Prop}, ¬(a ∨ b) ↔ ¬a ∧ ¬b — De Morgan
not_imp	∀ {a b : Prop}, ¬(a → b) ↔ a ∧ ¬b
and_comm	∀ {a b : Prop}, a ∧ b ↔ b ∧ a
or_comm	∀ {a b : Prop}, a ∨ b ↔ b ∨ a
Set.ext	∀ {A B : Obj}, (∀ x : Obj, x ∈ A ↔ x ∈ B) → A = B — extensionality: sets with the same elements are equal
Set.ext_iff	∀ {A B : Obj}, A = B ↔ (∀ x : Obj, x ∈ A ↔ x ∈ B) — extensionality and substitution, in one biconditional
Set.subset_antisymm	∀ {A B : Obj}, A ⊆ B → B ⊆ A → A = B — mutual inclusion is equality
Set.empty_subset	∀ {A : Obj}, ∅ ⊆ A — the empty set is a subset of every set
Set.pair_eq	∀ {a b c d : Obj}, ((a, b) = (c, d)) ↔ (a = c ∧ b = d) — two ordered pairs are equal exactly when their coordinates are

From the logical core

And.intro	∀ {a b : Prop}, a → b → a ∧ b
And.left	∀ {a b : Prop}, a ∧ b → a
And.right	∀ {a b : Prop}, a ∧ b → b
And.symm	∀ {a b : Prop}, a ∧ b → b ∧ a
Or.inl	∀ {a b : Prop}, a → a ∨ b
Or.inr	∀ {a b : Prop}, b → a ∨ b
Or.elim	∀ {a b c : Prop}, a ∨ b → (a → c) → (b → c) → c
Or.symm	∀ {a b : Prop}, a ∨ b → b ∨ a
Iff.intro	∀ {a b : Prop}, (a → b) → (b → a) → (a ↔ b)
Iff.mp	∀ {a b : Prop}, (a ↔ b) → a → b
Iff.mpr	∀ {a b : Prop}, (a ↔ b) → b → a
Iff.symm	∀ {a b : Prop}, (a ↔ b) → (b ↔ a)
Iff.rfl	∀ {a : Prop}, a ↔ a
Iff.trans	∀ {a b c : Prop}, (a ↔ b) → (b ↔ c) → (a ↔ c)
True.intro	True
False.elim	∀ {a : Prop}, False → a
absurd	∀ {a b : Prop}, a → ¬a → b
id	∀ {a : Prop}, a → a
mt	∀ {a b : Prop}, (a → b) → ¬b → ¬a
Eq.refl	∀ {α : Type} (a : α), a = a
Eq.symm	∀ {α : Type} {a b : α}, a = b → b = a
Eq.trans	∀ {α : Type} {a b c : α}, a = b → b = c → a = c
congrArg	∀ {α : Type} {β : Type} {a b : α} (f : α → β), a = b → f a = f b
Exists.intro	∀ {α : Type} {p : α → Prop} (w : α), p w → ∃ x : α, p x
Exists.elim	∀ {α : Type} {p : α → Prop} {b : Prop}, (∃ x : α, p x) → (∀ y : α, p y → b) → b