CommeUnJeu · L1 MPSI

Maps

⌚ ~107 min ▢ 13 blocks ✓ 44 exercises ➣ Prerequisites : Sets

A map (or application) is the most fundamental tool of mathematics: a rule that, given any element of a starting set $E$, returns one and only one element of an arrival set $F$. The function $x \mapsto x^2$, the squaring rule sending each real to its square, is a map; the inclusion $\mathbb{N} \hookrightarrow \mathbb{Z}$ that sees each natural as an integer is a map; even the operation that picks the smallest element of a finite non-empty subset of $\mathbb{R}$ is a map (defined on the set of finite non-empty subsets).

This chapter develops the language and the calculus of maps. Three threads run through it. The first is the language itself: definition of a map, its graph, equality, families, restriction and extension, indicator function. The second is the set-level action of a map: direct image $f(A)$, inverse image $f^{-1}(B)$, and the asymmetry between them under union and intersection. The third is the structural typology: injection, surjection, bijection --- and the notion of inverse map for bijections, with the formula $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ at the heart of it.

Composition is the connective tissue between threads two and three: it propagates structural properties along chains, and the inverse of a bijection is characterized by the two compositions $f^{-1} \circ f = \operatorname{Id}_E$ and $f \circ f^{-1} = \operatorname{Id}_F$. Binary relations on a set --- equivalences, orders, congruences --- are the subject of a separate chapter, see Relations.

I Maps

We start by setting up the basic language of maps: what a map is, how its rule is encoded by its graph, when two maps are equal. Three derived constructions close the section: families (a family of elements is just a map indexed by a set), restriction and extension (shrinking or enlarging the starting set), and the indicator function of a subset (the most useful map in combinatorics).

I.1 Map$\virgule$ graph$\virgule$ equality

Definition — Map (application)

Let $E$ and $F$ be two sets. An application (or map, or function) from $E$ to $F$ is a rule that, to each element $x \in E$, associates one and only one element of $F$, denoted $f(x)$ and called the image of $x$ under $f$. We write $f : E \to F$, or $$ f : E \to F, \quad x \mapsto f(x). $$

$E$ is the domain (or starting set) of $f$.
$F$ is the codomain (or arrival set) of $f$.
For $y = f(x)$, the element $x$ is called an antecedent (or preimage) of $y$.
The set $f(E) = \{ f(x) \ \mid \ x \in E\}$ is the image set of $f$, a subset of $F$.

Example

A map can be visualized by a sagittal diagram: each element of $E$ is drawn on the left, each element of $F$ on the right, and an arrow goes from $x$ to $f(x)$. For $E = \{a, b, c\}$ and $F = \{A, B, C, D\}$, the map $f$ defined by $f(a) = A$, $f(b) = B$, $f(c) = D$ is depicted below.

The image set is $f(E) = \{A, B, D\}$. The element $C$ has no antecedent: $C \in F$ but $C \notin f(E)$. Both $a$ and $A$ are linked, $A$ being « the image of $a$ » and $a$ being « an antecedent of $A$ ».

Definition — Graph of a map

The graph of a map $f : E \to F$ is the subset of $E \times F$ $$ \Gamma_f = \{ (x, f(x)) \ \mid \ x \in E \} \subset E \times F. $$ The graph captures the rule: $(x, y) \in \Gamma_f \iff y = f(x)$. Conversely, a subset $\Gamma \subset E \times F$ is the graph of some map iff for every $x \in E$ there exists exactly one $y \in F$ with $(x, y) \in \Gamma$.

Example

The graph of a real function $f : \mathbb{R} \to \mathbb{R}$ is the curve $\Gamma_f = \{ (x, f(x)) \mid x \in \mathbb{R} \}$ in the plane $\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}$. The defining property « exactly one $y$ for each $x$ » translates into a geometric criterion: every vertical line meets $\Gamma_f$ at exactly one point.

On the left, the curve $y = 0.3 x^2 - 0.5 x + 1.4$ is a graph: the dashed vertical above each $x$ meets it once, giving the unique image $f(x)$. On the right, the circle $x^2 + y^2 = R^2$ is not a graph: the dashed vertical meets it at two points, so the rule « given $x$, return $y$ » would be ambiguous.

Definition — Equality of maps

Two maps $f : E \to F$ and $g : E' \to F'$ are equal if and only if:

their domains agree: $E = E'$;
their codomains agree: $F = F'$;
for every $x \in E$, $f(x) = g(x)$.

Forgetting any one of the three conditions makes the equality wrong. The maps $\mathbb{R} \to \mathbb{R}, \ x \mapsto x^2$ and $\mathbb{R} \to \mathbb{R}_+, \ x \mapsto x^2$ have the same rule but different codomains, so they are different maps.

Definition — Set of maps

The set of all maps from $E$ to $F$ is denoted $$ \mathcal{F}(E, F) \quad \text{or} \quad F^E. $$ The notation $F^E$ is consistent with cardinals: when $E$ and $F$ are finite, $|\mathcal{F}(E, F)| = |F|^{|E|}$ (each of the $|E|$ inputs is mapped independently to one of $|F|$ outputs).

Example

$\mathcal{F}(\{1, 2\}, \{a, b\})$ has $2^2 = 4$ elements: the four maps that send $1$ to either $a$ or $b$, and $2$ to either $a$ or $b$.
The identity of $E$, denoted $\operatorname{Id}_E$, is the map $E \to E, \ x \mapsto x$. It exists for any set $E$ and is an element of $\mathcal{F}(E, E) = E^E$.
A real-valued sequence $(u_n)_{n \in \mathbb{N}}$ is just an element of $\mathbb{R}^{\mathbb{N}}$, i.e. a map from $\mathbb{N}$ to $\mathbb{R}$.

Skills to practice

Testing the « one-element-per-input » property
Stating the three sets $E$$\virgule$ $F$$\virgule$ $f(E)$
Applying the three-condition test

I.2 Family of elements$\virgule$ restriction$\virgule$ extension

Definition — Family of elements

Let $E$ be a set and $I$ another set, called the index set. A family of elements of $E$ indexed by $I$ is simply a map $I \to E$, but written with the indexed notation $$ (x_i)_{i \in I} \quad \text{instead of} \quad i \mapsto x_i. $$ The set of all such families is $E^I = \mathcal{F}(I, E)$. When $I$ is finite, say $I = \{1, 2, \dots, n\}$, the family is also called an $n$-tuple and written $(x_1, x_2, \dots, x_n)$. The case $I = \mathbb{N}$ gives sequences.

Example

For $I = \{1, 2, 3\}$ and $E = \mathbb{R}$, the family $(x_i)_{i \in I} = (\sqrt{2}, \pi, e)$ is just the triple $(x_1, x_2, x_3) = (\sqrt{2}, \pi, e) \in \mathbb{R}^3$.
The Fibonacci sequence $(F_n)_{n \in \mathbb{N}}$ defined by $F_0 = 0$, $F_1 = 1$, $F_{n+2} = F_{n+1} + F_n$ is a family in $\mathbb{N}$ indexed by $\mathbb{N}$.
For $a \in \mathbb{R}$, the family $(f_a)_{a \in \mathbb{R}}$ where $f_a : x \mapsto |x - a|$ is a family of functions, indexed by the parameter $a$.

Definition — Restriction and extension

Let $f : E \to F$ be a map.

For $A \subset E$, the restriction of $f$ to $A$ is the map $f|_A : A \to F$ defined by $f|_A(x) = f(x)$ for every $x \in A$. Restriction shrinks the domain.
Conversely, an extension of $f$ to a larger set $E_1 \supset E$ is any map $g : E_1 \to F$ such that $g(x) = f(x)$ for every $x \in E$. Extension enlarges the domain. An extension exists as soon as $F \ne \emptyset$ (assign any value of $F$ to each new point); a map can have several extensions precisely when the enlarged domain is strictly bigger ($E_1 \supsetneq E$) and the codomain has at least two elements ($|F| \ge 2$), since the points of $E_1 \setminus E$ may then be sent to different images. By contrast, the restriction to a given subset $A$ is always unique.

Example

The square function $f : \mathbb{R} \to \mathbb{R}_+, \ x \mapsto x^2$ admits the restriction $f|_{\mathbb{R}_+} : \mathbb{R}_+ \to \mathbb{R}_+, \ x \mapsto x^2$. The restriction is non-decreasing on its domain, while $f$ itself is not. Conversely, the map $g : \mathbb{R} \to \mathbb{R}_+, \ x \mapsto x^2$ is an extension of $f|_{\mathbb{R}_+}$: it has the same codomain $\mathbb{R}_+$ and satisfies $g|_{\mathbb{R}_+} = f|_{\mathbb{R}_+}$. The extension is not unique: any map $h : \mathbb{R} \to \mathbb{R}_+$ that agrees with $x \mapsto x^2$ on $\mathbb{R}_+$ --- for instance $h(x) = x^2$ for $x \ge 0$ and $h(x) = 0$ for $x < 0$ --- is also an extension of $f|_{\mathbb{R}_+}$.

Skills to practice

Computing restrictions

I.3 Indicator function

Definition — Indicator function

Let $E$ be a set and $A \subset E$. The indicator function of $A$ (also called characteristic function) is the map $\mathbf{1}_A : E \to \{0, 1\}$ defined by $$ \mathbf{1}_A(x) = \begin{cases} 1 & \text{if } x \in A, \\ 0 & \text{if } x \notin A. \end{cases} $$ Knowing $A$ is the same thing as knowing $\mathbf{1}_A$: the part $A$ is recovered by $A = \{x \in E \ \mid \ \mathbf{1}_A(x) = 1\}$. The map $A \mapsto \mathbf{1}_A$ is a one-to-one correspondence between $\mathcal{P}(E)$ and $\{0, 1\}^E$.

Example

On the real line, the graph of an indicator function is a step function: it jumps to $1$ over $A$, and is $0$ everywhere else. For $E = \mathbb{R}$ and $A = [1, 2] \cup [3, 4]$:

The set $A$ is « painted » below: above $A$ the indicator is $1$, off $A$ it is $0$. The set is encoded by the function and the function by the set.

Proposition — Indicator and set operations

For $A, B \subset E$ and any $x \in E$:

Inclusion. $A \subset B \iff \mathbf{1}_A \le \mathbf{1}_B$.
Equality. $A = B \iff \mathbf{1}_A = \mathbf{1}_B$.
Intersection. $\mathbf{1}_{A \cap B} = \mathbf{1}_A \cdot \mathbf{1}_B$.
Union. $\mathbf{1}_{A \cup B} = \mathbf{1}_A + \mathbf{1}_B - \mathbf{1}_A \cdot \mathbf{1}_B$.
Complement. $\mathbf{1}_{\complement_E A} = 1 - \mathbf{1}_A$.

Proof

For each identity, we check pointwise: the value of both sides at an arbitrary $x \in E$ depends only on whether $x$ belongs to $A$ and to $B$, giving four cases.

Intersection. $\mathbf{1}_{A \cap B}(x) = 1$ iff $x \in A \cap B$ iff ($x \in A$ and $x \in B$) iff $\mathbf{1}_A(x) = 1$ and $\mathbf{1}_B(x) = 1$ iff $\mathbf{1}_A(x) \cdot \mathbf{1}_B(x) = 1$. Otherwise both sides are $0$.
Complement. $\mathbf{1}_{\complement A}(x) = 1$ iff $x \notin A$ iff $\mathbf{1}_A(x) = 0$ iff $1 - \mathbf{1}_A(x) = 1$.
Union. Apply De Morgan: $A \cup B = \complement(\complement A \cap \complement B)$. So $\mathbf{1}_{A \cup B} = 1 - \mathbf{1}_{\complement A} \cdot \mathbf{1}_{\complement B} = 1 - (1 - \mathbf{1}_A)(1 - \mathbf{1}_B) = \mathbf{1}_A + \mathbf{1}_B - \mathbf{1}_A \mathbf{1}_B$.
Inclusion. $A \subset B \iff (\forall x, x \in A \Rightarrow x \in B) \iff (\forall x, \mathbf{1}_A(x) = 1 \Rightarrow \mathbf{1}_B(x) = 1) \iff \mathbf{1}_A \le \mathbf{1}_B$ (since both functions take only values $0$ or $1$).
Equality. Two functions are equal iff their values agree at every point; a part is determined by its indicator, hence the equivalence.

Example

For $E$ finite of cardinal $n$, summing the indicator $\mathbf{1}_A$ over all of $E$ gives the cardinal of $A$: $$ |A| = \sum_{x \in E} \mathbf{1}_A(x). $$ This converts set-counting problems into algebraic ones. For instance, the inclusion-exclusion formula $|A \cup B| = |A| + |B| - |A \cap B|$ is the sum of $\mathbf{1}_{A \cup B} = \mathbf{1}_A + \mathbf{1}_B - \mathbf{1}_{A \cap B}$ over $E$.

Skills to practice

Computing indicator functions and their products

II Direct image$\virgule$ inverse image

A map $f : E \to F$ acts on elements: $x \mapsto f(x)$. But it can also be made to act on subsets, in two complementary ways. The direct image sends a subset $A \subset E$ to the set $f(A)$ of all images of elements of $A$; this works « in the direction of $f$ ». The inverse image sends a subset $B \subset F$ to the set $f^{-1}(B)$ of all elements of $E$ whose image lies in $B$; this works « against $f$ ».

The two constructions are essential, and they have very different behaviors. Inverse image plays well with all set operations (union, intersection, complement); direct image plays well only with union, in general. Mastering this asymmetry is one of the main pay-offs of the chapter.

II.1 Direct image

Definition — Direct image

Let $f : E \to F$ be a map and $A \subset E$. The direct image of $A$ by $f$ is the subset of $F$ $$ f(A) = \{ f(x) \ \mid \ x \in A \} = \{ y \in F \ \mid \ \exists x \in A, \ y = f(x) \}. $$ For a single-element $\{x\}$, $f(\{x\}) = \{f(x)\}$. The image $f(E)$ of the whole domain is also called the image set of $f$.

Example

Visually, $f(A)$ is obtained by projecting onto the codomain axis the portion of the graph of $f$ that lies above $A$.

For $f : \mathbb{R} \to \mathbb{R}, \ x \mapsto x^2$:

$f([-2, 2]) = [0, 4]$ (the square sends $[-2, 2]$ to $[0, 4]$).
$f([-1, 2]) = [0, 4]$ (same image --- the asymmetry of $[-1, 2]$ is hidden by squaring).
$f(\mathbb{R}) = \mathbb{R}_+$ (every non-negative real has at least one square root).

Proposition — Direct image and set operations

For $f : E \to F$ and $A, A' \subset E$:

Monotonicity. $A \subset A' \implies f(A) \subset f(A')$.
Union. $f(A \cup A') = f(A) \cup f(A')$.
Intersection. $f(A \cap A') \subset f(A) \cap f(A')$, with equality not granted in general.

Proof

Monotonicity. If $y \in f(A)$, write $y = f(x)$ with $x \in A \subset A'$, so $y \in f(A')$.
Union. Both sides describe « images of elements that belong to $A$ or to $A'$ ».
Intersection. Let $y \in f(A \cap A')$, write $y = f(x)$ with $x \in A \cap A'$. Then $x \in A$ so $y \in f(A)$, and $x \in A'$ so $y \in f(A')$, hence $y \in f(A) \cap f(A')$.

The reverse inclusion may fail. Take $f : \mathbb{R} \to \mathbb{R}, x \mapsto x^2$, $A = \{1\}$, $A' = \{-1\}$. Then $A \cap A' = \emptyset$ so $f(A \cap A') = \emptyset$, but $f(A) \cap f(A') = \{1\} \cap \{1\} = \{1\}$. The phenomenon is caused by two distinct elements having the same image.

Skills to practice

Computing $f(A)$ for explicit $A$

II.2 Inverse image

Definition — Inverse image

Let $f : E \to F$ be a map and $B \subset F$. The inverse image of $B$ by $f$ is the subset of $E$ $$ f^{-1}(B) = \{ x \in E \ \mid \ f(x) \in B \}. $$ For a single-element $\{y\}$, $f^{-1}(\{y\})$ is the set of all antecedents of $y$ --- possibly empty (if $y \notin f(E)$), possibly a single element, possibly more.

Example

Visually, $f^{-1}(B)$ is obtained by projecting onto the domain axis the portion of the graph that lies in the horizontal strip defined by $B$.

For $f : \mathbb{R} \to \mathbb{R}, \ x \mapsto x^2$:

$f^{-1}(\{4\}) = \{-2, 2\}$ (two antecedents).
$f^{-1}(\{-1\}) = \emptyset$ (no real has square equal to $-1$).
$f^{-1}([0, 4]) = [-2, 2]$, $f^{-1}([1, 4]) = [-2, -1] \cup [1, 2]$.

Caveat on the notation $f^{-1}(B)$

The notation $f^{-1}(B)$ does not require $f$ to be bijective. It is well-defined for any map $f : E \to F$ and any $B \subset F$. We will see in the bijectivity section that when $f$ is bijective, the notation collides with the inverse map $f^{-1} : F \to E$, but the two meanings are compatible: $f^{-1}(B)$ as inverse image equals $f^{-1}(B)$ as direct image of $B$ by the inverse map.

Skills to practice

Computing $f^{-1}(B)$ for explicit $B$

II.3 Operations on inverse images

Proposition — Inverse image and set operations

For $f : E \to F$ and $B, B' \subset F$:

Monotonicity. $B \subset B' \implies f^{-1}(B) \subset f^{-1}(B')$.
Union. $f^{-1}(B \cup B') = f^{-1}(B) \cup f^{-1}(B')$.
Intersection. $f^{-1}(B \cap B') = f^{-1}(B) \cap f^{-1}(B')$.
Complement. $f^{-1}(\complement_F B) = \complement_E f^{-1}(B)$.

Inverse image commutes with all set operations --- this is the asymmetry with direct image.

Proof

We prove the union case; the others follow the same pattern. For $x \in E$: $$ \begin{aligned} x \in f^{-1}(B \cup B') &\iff f(x) \in B \cup B' \\ &\iff f(x) \in B \text{ or } f(x) \in B' \\ &\iff x \in f^{-1}(B) \text{ or } x \in f^{-1}(B') \\ &\iff x \in f^{-1}(B) \cup f^{-1}(B'). \end{aligned} $$ The intersection and complement cases are similar, replacing « or » by « and », respectively « not ».

Skills to practice

Proving identities for direct and inverse images

III Composition$\virgule$ injection$\virgule$ surjection$\virgule$ bijection

Two structural properties of a map $f : E \to F$ are independent and equally fundamental:

is the rule one-to-one? (different $x$ give different $f(x)$): injection;
is the codomain covered? (every $y \in F$ has at least one antecedent): surjection.

A map that is both is a bijection --- a true correspondence between $E$ and $F$. Bijections are reversible: they admit an inverse map. The composition operation lets us assemble maps and lifts the structural properties along the chain.

III.1 Composition

Definition — Composition

Let $f : E \to F$ and $g : F \to G$ be two maps. The composition of $g$ by $f$, denoted $g \circ f$, is the map $E \to G$ defined by $$ (g \circ f)(x) = g(f(x)) \quad \text{for every } x \in E. $$ The composition exists only when the codomain of $f$ matches the domain of $g$. The notation $g \circ f$ is read « $g$ composed with $f$ » or « $g$ after $f$ ».

Example

The chain diagram below illustrates the composition: $f$ takes $E$ into $F$, then $g$ takes $F$ into $G$; $g \circ f$ does both at once.

For $f : \mathbb{R} \to \mathbb{R}, \ x \mapsto x^2$ and $g : \mathbb{R} \to \mathbb{R}, \ y \mapsto y + 1$: $$ (g \circ f)(x) = g(x^2) = x^2 + 1, \qquad (f \circ g)(x) = f(x + 1) = (x + 1)^2. $$ The two compositions differ: composition is not commutative in general.

Proposition — Associativity$\virgule$ identity

Let $f : E \to F$, $g : F \to G$, $h : G \to H$ be three maps.

Associativity. $h \circ (g \circ f) = (h \circ g) \circ f$. Both compositions are well-defined and equal as maps $E \to H$.
Neutral elements. $f \circ \operatorname{Id}_E = f$ and $\operatorname{Id}_F \circ f = f$.

Hence we can write unparenthesized $h \circ g \circ f$ without ambiguity.

Proof

Both maps $h \circ (g \circ f)$ and $(h \circ g) \circ f$ have domain $E$ and codomain $H$. For $x \in E$: $$ \big(h \circ (g \circ f)\big)(x) = h\big((g \circ f)(x)\big) = h(g(f(x))) = (h \circ g)(f(x)) = \big((h \circ g) \circ f\big)(x). $$ The neutral-element identities are immediate: $(f \circ \operatorname{Id}_E)(x) = f(\operatorname{Id}_E(x)) = f(x)$ for every $x \in E$.

Skills to practice

Composing explicit maps

III.2 Injection$\virgule$ surjection

Definition — Injection

A map $f : E \to F$ is injective (or one-to-one) if it satisfies any of the following equivalent properties:

every $y \in F$ has at most one antecedent under $f$;
for every $y \in F$, the equation $f(x) = y$ has at most one solution;
for every $x_1, x_2 \in E$, $\ f(x_1) = f(x_2) \implies x_1 = x_2$.

The contrapositive of the third form is the working definition: « if $x_1 \ne x_2$, then $f(x_1) \ne f(x_2) $».

Method — To prove $f$ is injective

Three standard approaches:

By definition. Take $x_1, x_2 \in E$ with $f(x_1) = f(x_2)$ and deduce $x_1 = x_2$ by algebraic manipulation. Most flexible, works for any $f$.
Strict monotonicity. If $E \subset \mathbb{R}$ and $f$ is strictly increasing or strictly decreasing on $E$, then $f$ is injective. Most efficient for real-variable functions.
Counterexample (to disprove). Exhibit $x_1 \ne x_2$ with $f(x_1) = f(x_2)$. Useful when $f$ is not injective.

Definition — Surjection

A map $f : E \to F$ is surjective (or is a surjection, or « is from $E$ onto $F$ ») if it satisfies any of the following equivalent properties:

every $y \in F$ has at least one antecedent under $f$;
for every $y \in F$, the equation $f(x) = y$ has at least one solution;
$f(E) = F$.

Example

The three behaviors are best contrasted on sagittal diagrams.

Injection: every arrow lands at a distinct target; some targets may be unhit ($D$ here).
Surjection: every target is hit at least once; some targets may be hit multiple times ($A$ here, by $1$ and $2$).
Bijection: every target is hit exactly once.

Standard examples on $\mathbb{R}$:

$\mathbb{R} \to \mathbb{R}, \ x \mapsto x^2$ is neither injective ($(-1)^2 = 1^2$) nor surjective ($-1$ has no antecedent).
$\mathbb{R}_+ \to \mathbb{R}_+, \ x \mapsto x^2$ is bijective (the inverse is $\sqrt{\cdot}$).
$\mathbb{R} \to \mathbb{R}, \ x \mapsto e^x$ is injective (strictly increasing) but not surjective (image is $\mathbb{R}_+^*$).

Proposition — Composition and structural properties

Let $f : E \to F$ and $g : F \to G$ be two maps.

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.

The converses are partial: if $g \circ f$ is injective then $f$ is injective; if $g \circ f$ is surjective then $g$ is surjective.

Proof

Injectivity. Suppose $f, g$ injective. Let $x_1, x_2 \in E$ with $(g \circ f)(x_1) = (g \circ f)(x_2)$, i.e. $g(f(x_1)) = g(f(x_2))$. By injectivity of $g$, $f(x_1) = f(x_2)$. By injectivity of $f$, $x_1 = x_2$.
Surjectivity. Suppose $f, g$ surjective. Let $z \in G$. By surjectivity of $g$, $z = g(y)$ for some $y \in F$. By surjectivity of $f$, $y = f(x)$ for some $x \in E$. Then $z = g(f(x)) = (g \circ f)(x)$, so $z \in (g \circ f)(E)$.
Bijectivity. A bijection is an injection-and-surjection; combine the two cases above.
Partial converse, injectivity. Suppose $g \circ f$ injective. If $f(x_1) = f(x_2)$, then $g(f(x_1)) = g(f(x_2))$, so $(g \circ f)(x_1) = (g \circ f)(x_2)$, hence $x_1 = x_2$.
Partial converse, surjectivity. Suppose $g \circ f$ surjective. Let $z \in G$, write $z = g(f(x))$. Then $z = g(y)$ with $y = f(x) \in F$, so $z \in g(F)$.

Skills to practice

Deciding injectivity
Deciding surjectivity

III.3 Bijection and inverse

Definition — Bijection

A map $f : E \to F$ is bijective (or one-to-one correspondence) if it is both injective and surjective. Equivalently, every $y \in F$ has exactly one antecedent: $\forall y \in F, \ \exists ! x \in E, \ y = f(x)$.

Definition — Inverse map

Let $f : E \to F$ be a bijection. The inverse map of $f$, denoted $f^{-1}$, is the map $F \to E$ that, to each $y \in F$, associates the unique $x \in E$ such that $y = f(x)$. Symbolically: $$ y = f(x) \iff x = f^{-1}(y). $$

Proposition — Characterization of the inverse

Let $f : E \to F$ be a map.

If $f$ is bijective, then $f^{-1} \circ f = \operatorname{Id}_E$ and $f \circ f^{-1} = \operatorname{Id}_F$.
Conversely, if there exists a map $g : F \to E$ such that $g \circ f = \operatorname{Id}_E$ and $f \circ g = \operatorname{Id}_F$, then $f$ is bijective and $f^{-1} = g$.

This gives a method to prove a map is bijective: find a candidate inverse and check both compositions equal the identity.

Proof

Direct sense. Suppose $f$ bijective. For $x \in E$, $(f^{-1} \circ f)(x) = f^{-1}(f(x))$. Setting $y = f(x)$, the unique antecedent of $y$ is $x$, so $f^{-1}(y) = x$. Hence $(f^{-1} \circ f)(x) = x = \operatorname{Id}_E(x)$. Symmetrically, $(f \circ f^{-1})(y) = f(f^{-1}(y))$: by definition $f^{-1}(y)$ is the antecedent of $y$, so $f(f^{-1}(y)) = y$.
Converse sense. Suppose $g \circ f = \operatorname{Id}_E$ and $f \circ g = \operatorname{Id}_F$. Then $g \circ f$ is bijective ($\operatorname{Id}_E$ is), so $f$ is injective (partial converse of the composition proposition); and $f \circ g$ is bijective, so $f$ is surjective. Hence $f$ is bijective. Finally, for $y \in F$, $f^{-1}(y)$ is the unique antecedent of $y$; but $f(g(y)) = y$ shows $g(y)$ is one antecedent, hence $g(y) = f^{-1}(y)$. So $g = f^{-1}$.

Example

Let $f : \mathbb{R} \to \mathbb{R}, \ x \mapsto 3x + 5$. Solve $y = 3x + 5 \iff x = (y - 5)/3$. Define $g : \mathbb{R} \to \mathbb{R}, \ y \mapsto (y - 5)/3$. Check: $$ (g \circ f)(x) = \frac{(3x + 5) - 5}{3} = x, \qquad (f \circ g)(y) = 3 \cdot \frac{y - 5}{3} + 5 = y. $$ So $f$ is bijective and $f^{-1} = g$.

Method — To compute $f^{-1}$ explicitly

Given a candidate bijection $f : E \to F$:

Solve $y = f(x)$ for $x$. For each $y \in F$, find the unique $x \in E$ with $f(x) = y$. The expression $x = g(y)$ obtained this way is the candidate for $f^{-1}$.
Verify both compositions. Check $g \circ f = \operatorname{Id}_E$ and $f \circ g = \operatorname{Id}_F$. By the characterization of bijectivity established above, $f$ is then bijective and $f^{-1} = g$.
Watch the sets. If the equation $y = f(x)$ has a solution only for $y$ in some subset of $F$, then $f$ is not surjective onto $F$. Restrict the codomain to $f(E)$ before declaring $f$ bijective.

Example

The graphs of $f$ and $f^{-1}$ are symmetric across the line $y = x$: the equivalence $y = f(x) \iff x = f^{-1}(y)$ says that $(x_0, y_0) \in \Gamma_f$ if and only if $(y_0, x_0) \in \Gamma_{f^{-1}}$, and swapping coordinates is exactly the reflection across $y = x$. For $f : \mathbb{R}_+ \to \mathbb{R}_+, \ x \mapsto x^2$, the inverse is $f^{-1} : y \mapsto \sqrt{y}$.

The dotted segment links a point on the graph of $f$ to its mirror image on the graph of $f^{-1}$. The two graphs cross on the diagonal at fixed points (here, $0$ and $1$).

Proposition — Inverse and composition

If $f : E \to F$ is bijective, then $f^{-1}$ is bijective and $(f^{-1})^{-1} = f$.
If $f : E \to F$ and $g : F \to G$ are bijective, then $g \circ f$ is bijective and $$ (g \circ f)^{-1} = f^{-1} \circ g^{-1}. $$

The inversion reverses the order: to undo « put in box, then bury », one must first dig up (apply $g^{-1}$), then open the box (apply $f^{-1}$). The reverse order $g^{-1} \circ f^{-1}$ would not even type-check: $g^{-1}$ is defined on $G$ and $f^{-1}$ on $F$, and the composition requires the codomain of the inner map to match the domain of the outer.

Proof

For the inverse alone: $f^{-1} \circ f = \operatorname{Id}_E$ and $f \circ f^{-1} = \operatorname{Id}_F$ both hold by definition. Apply the characterization of bijectivity established above with $g := f$: $f^{-1}$ is bijective and its inverse is $f$, i.e. $(f^{-1})^{-1} = f$.
For the composition: set $h = f^{-1} \circ g^{-1}$ and check both compositions using associativity. $$ \begin{aligned} (g \circ f) \circ h &= g \circ f \circ f^{-1} \circ g^{-1} = g \circ \operatorname{Id}_F \circ g^{-1} = g \circ g^{-1} = \operatorname{Id}_G, \\ h \circ (g \circ f) &= f^{-1} \circ g^{-1} \circ g \circ f = f^{-1} \circ \operatorname{Id}_F \circ f = f^{-1} \circ f = \operatorname{Id}_E. \end{aligned} $$ By the characterization, $g \circ f$ is bijective with inverse $h = f^{-1} \circ g^{-1}$.

Definition — Permutation

A bijection from $E$ to itself is called a permutation of $E$. The set of permutations of $E$ is denoted $\mathfrak{S}(E)$ (or $\mathcal{S}_E$). When $E = \{1, 2, \dots, n\}$, the standard notation is $\mathfrak{S}_n$ and $|\mathfrak{S}_n| = n!$.

Skills to practice

Solving $y \equal f(x)$ and verifying the inverse

III.4 Compatibility of $f^{-1}$ notations

The notation $f^{-1}(B)$ has now two possible meanings:

Inverse image (defined for any $f$): $f^{-1}(B) = \{ x \in E \mid f(x) \in B\}$.
Direct image of $B$ by the inverse map (defined only if $f$ is bijective): $f^{-1}(B) = \{ f^{-1}(y) \mid y \in B\}$.

The next proposition shows that, when $f$ is bijective, the two definitions agree, so the notation is unambiguous.

Proposition — Compatibility

Let $f : E \to F$ be a bijection and $B \subset F$. The inverse image of $B$ by $f$ equals the direct image of $B$ by the inverse map $f^{-1}$.

Proof

For $x \in E$: $$ \begin{aligned} x \in \{u \in E \mid f(u) \in B\} &\iff f(x) \in B \\ &\iff \exists y \in B, \ f(x) = y \\ &\iff \exists y \in B, \ x = f^{-1}(y) \\ &\iff x \in \{f^{-1}(y) \mid y \in B\}. \end{aligned} $$ The two sets agree, so the notations are compatible.

Skills to practice

Applying the partial-converse propositions