Injection, surjection, bijection

Let $A$ and $B$ be sets and let $f : A \to B$ be a function (A function is a relation $f$ with $(a,b) \in f$ and $(a,c) \in f$ implying $b = c$; $f : A \to B$, the value $f(a)$, domain and codomain).

• $f$ is injective (one-to-one) if $f(x) = f(y)$ implies $x = y$, for all $x, y \in A$.
• $f$ is surjective (onto) if for every $b \in B$ there is some $x \in A$ with $f(x) = b$; equivalently, the image $f[A] := \{ f(x) : x \in A \}$ equals $B$.
• $f$ is bijective if it is both injective and surjective.

For $S \subseteq A$ we write $f[S] = \{ f(x) : x \in S \}$ for the image of $S$, and for $T \subseteq B$ we write $f^{-1}[T] = \{ x \in A : f(x) \in T \}$ for the preimage of $T$; these are the image and preimage of a set under $f$ read as a relation (The image $R[A]$ and the preimage $R^{-1}[B]$ of a set under a relation).

• Composition. If $f : A \to B$ and $g : B \to C$ are both injective then so is $g \circ f$, since $g(f(x)) = g(f(y))$ forces $f(x) = f(y)$ and then $x = y$; if both are surjective then so is $g \circ f$, since any $c \in C$ is $g(b)$ for some $b \in B$ and that $b$ is $f(a)$ for some $a \in A$. Hence a composition of bijections is a bijection. These verifications, together with the two partial converses, are For $f : A \to B$ and $g : B \to C$: if both are injective so is $g \circ f$; if both are surjective so is $g \circ f$; if $g \circ f$ is injective so is $f$; and if $g \circ f$ is surjective so is $g$.

• Inverses. $f : A \to B$ is bijective exactly when there is a function $f^{-1} : B \to A$ with $f^{-1}(f(x)) = x$ for all $x \in A$ and $f(f^{-1}(b)) = b$ for all $b \in B$; that two-sided inverse is unique, and it is itself a bijection. Injectivity alone gives a bijection from $A$ onto the image $f[A]$, and hence an inverse defined on $f[A]$ only. No choice principle is involved: the value $f^{-1}(b)$ is the unique $x$ with $f(x) = b$, so it is determined rather than selected. The full statement, with the uniqueness of the two-sided inverse, is $f : A \to B$ is a bijection if and only if there is a function $g : B \to A$ with $g \circ f = \Delta_A$ and $f \circ g = \Delta_B$; such a $g$ is unique, equals the inverse relation $f^{-1}$, and is itself a bijection; the corresponding statement for an arbitrary surjection is not available at this point in the reading order, because a right inverse for every surjection is equivalent to the Axiom of Choice.

• What this item does and does not do. A function $A \to B$ is a set of ordered pairs, single valued and total on $A$ (A function is a relation $f$ with $(a,b) \in f$ and $(a,c) \in f$ implying $b = c$; $f : A \to B$, the value $f(a)$, domain and codomain); ordered pairs, Cartesian products, images and preimages are fixed by The Kuratowski ordered pair $(a,b) := \{\{a\},\{a,b\}\}$, The Cartesian product $A \times B := \{\, z \in \mathcal{P}(\mathcal{P}(A \cup B)) : \exists a \in A\ \exists b \in B\ z = (a,b) \,\}$ and The image $R[A]$ and the preimage $R^{-1}[B]$ of a set under a relation. This item only fixes the three adjectives and the notation used for them. Nothing here is proved.