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={\mathrm{\Delta }}_A$ and $f\circ g={\mathrm{\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)):\mathrm{\exists }a\in A\mathrm{\exists }b\in Bz=(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.