Start with the Domain and Codomain
The previous tutorial used lower bounds and approximations to prove facts about infima. When working with functions, the first step is different: identify the domain, the codomain, and what must be shown about inputs or outputs. A function \(f:A\to B\) assigns exactly one element of \(B\) to each element of \(A\). Its domain is \(A\), and its codomain is \(B\).
Many function proofs follow one of two patterns. To show that different inputs cannot produce the same output, assume two outputs are equal and prove the inputs were equal. To show that every element of the codomain occurs as an output, start with an arbitrary element of the codomain and find an input that maps to it. These are not merely convenient strategies; they match the definitions of injectivity and surjectivity.
The quantifiers in these definitions suggest the proof structure. For injectivity, the two inputs \(x_1,x_2\) are arbitrary, and equality of their outputs is the assumption. For surjectivity, the output \(y\) is arbitrary, and the proof must produce a suitable input \(x\). In a surjectivity proof, finding an input is not enough: it must belong to the stated domain, and substituting it into the function must give the chosen \(y\).
Worked Example: A Linear Function Is Bijective
Let \(f:\mathbb{R}\to\mathbb{R}\) be defined by \(f(x)=3x-2\). We prove injectivity directly. Suppose \(x_1,x_2\in\mathbb{R}\) and \(f(x_1)=f(x_2)\). Then
Thus \(f\) is injective. To prove surjectivity, let \(y\in\mathbb{R}\) be arbitrary. Set \(x=(y+2)/3\), which is a real number and therefore belongs to the domain. Substitution verifies the required output:
So \(f\) is surjective as well as injective, and hence is bijective. The two steps have different jobs: the equality argument proves that no two inputs share an output, while solving \(3x-2=y\) supplies an input for each requested output.
What Composition Preserves
Suppose \(f:A\to B\) and \(g:B\to C\). Their composition \(g\circ f:A\to C\) is defined by \((g\circ f)(x)=g(f(x))\). It applies \(f\) first and then \(g\). To prove a statement about the composition, write out this two-stage evaluation rather than treating \(g\circ f\) as an unexplained symbol.
- If \(g\circ f\) is injective, then \(f\) is injective. If both \(f\) and \(g\) are injective, then \(g\circ f\) is injective.
- If \(g\circ f\) is surjective, then \(g\) is surjective. If both \(f\) and \(g\) are surjective, then \(g\circ f\) is surjective.
Proof. First suppose \(g\circ f\) is injective. Take \(x_1,x_2\in A\) and suppose \(f(x_1)=f(x_2)\). Applying \(g\) to both sides gives \(g(f(x_1))=g(f(x_2))\), or \((g\circ f)(x_1)=(g\circ f)(x_2)\). Injectivity of the composition implies \(x_1=x_2\). This proves that \(f\) is injective.
Now suppose that \(f\) and \(g\) are both injective. Take \(x_1,x_2\in A\) and assume \((g\circ f)(x_1)=(g\circ f)(x_2)\). This says \(g(f(x_1))=g(f(x_2))\). Since \(g\) is injective, \(f(x_1)=f(x_2)\). Since \(f\) is injective, \(x_1=x_2\). Therefore \(g\circ f\) is injective.
For the surjectivity implication, suppose \(g\circ f\) is surjective. Let \(z\in C\). By surjectivity, there is an \(x\in A\) such that \((g\circ f)(x)=z\). Taking \(b=f(x)\in B\), we have \(g(b)=z\). Thus every \(z\in C\) is an output of \(g\), so \(g\) is surjective.
Finally, suppose \(f\) and \(g\) are both surjective. Let \(z\in C\). Since \(g\) is surjective, there is a \(b\in B\) with \(g(b)=z\). Since \(f\) is surjective, there is an \(x\in A\) with \(f(x)=b\). Hence
Every \(z\in C\) is therefore an output of \(g\circ f\), proving that the composition is surjective. \(\square\)
The theorem gives useful one-way implications, but not every converse holds. In particular, a composition can be injective even when \(g\) is not injective, and a composition can be surjective even when \(f\) is not surjective. Under extra assumptions, some converses do hold: if \(g\) is injective, then \(g\circ f\) is injective exactly when \(f\) is; if \(f\) is surjective, then \(g\circ f\) is surjective exactly when \(g\) is. These follow from the theorem and the corresponding direct implications in its proof.
Worked Example: A Composition Can Be Injective When the Second Function Is Not
Let \(A=\{0\}\), \(B=\{0,1\}\), and \(C=\{0\}\). Define \(f:A\to B\) by \(f(0)=0\), and define \(g:B\to C\) by \(g(0)=0\) and \(g(1)=0\). The function \(g\) is not injective, since \(0\ne1\) but \(g(0)=g(1)\). However, the composition has just one input, and
To check injectivity from the definition, any two elements of \(A\) must both equal \(0\); thus they equal each other whenever their outputs are equal. So \(g\circ f\) is injective. This does not contradict the theorem: the theorem says that if both functions are injective, their composition is injective, not that injectivity of the composition forces \(g\) to be injective.
Worked Example: A Surjective Composition Does Not Force the First Function to Be Surjective
Use \(A=\{0\}\), \(B=\{0,1\}\), and \(C=\{0\}\) again, with \(f(0)=0\) and \(g(0)=g(1)=0\). The function \(f\) is not surjective onto \(B\), since there is no \(x\in A\) for which \(f(x)=1\). But \(g\circ f:A\to C\) is surjective: the only element \(0\in C\) is the output at \(x=0\), as the calculation
shows. In this example \(g\) is surjective, as the composition theorem requires. The distinction is between reaching every element of \(B\), which \(f\) fails to do, and reaching every element of \(C\) after applying \(g\), which the composition does.
Bijections and Inverse Functions
For a bijective function, each element of the codomain comes from exactly one input: surjectivity guarantees at least one such input, and injectivity guarantees at most one. This allows us to reverse the input-output assignment. The resulting function is called the inverse.
Proof. Suppose first that \(g:B\to A\) is an inverse of \(f\). To prove \(f\) is injective, let \(x_1,x_2\in A\) and suppose \(f(x_1)=f(x_2)\). Applying \(g\) and using the inverse identity gives
Thus \(f\) is injective. To prove surjectivity, take any \(y\in B\). The element \(g(y)\) belongs to \(A\), and the other inverse identity gives \(f(g(y))=y\). Hence \(y\) is an output of \(f\). This proves that \(f\) is bijective.
Conversely, suppose \(f\) is bijective. For each \(y\in B\), surjectivity gives an \(x\in A\) with \(f(x)=y\), and injectivity ensures that there is only one such \(x\). Define \(g(y)\) to be that unique \(x\). This defines a function \(g:B\to A\). For \(x\in A\), the unique input that maps to \(f(x)\) is \(x\), so \(g(f(x))=x\). For \(y\in B\), the definition of \(g(y)\) gives \(f(g(y))=y\). Thus \(g\) is a two-sided inverse of \(f\). \(\square\)
Both parts of bijectivity are needed. Without surjectivity, some elements of \(B\) have no input to assign as their inverse value. Without injectivity, an element of \(B\) may have multiple possible inputs, so reversing the assignment would not define a unique function.
Worked Example: The Square Function Depends on Its Codomain
Define \(q:\mathbb{R}\to[0,\infty)\) by \(q(x)=x^2\). It is not injective, because \(q(1)=1=q(-1)\) while \(1\ne-1\). It is surjective onto the stated codomain: for any \(y\in[0,\infty)\), the existence of a nonnegative square root gives an \(x\in\mathbb{R}\) with \(x^2=y\). Therefore \(q\) is not bijective and, by the inverse theorem, has no two-sided inverse from \([0,\infty)\) to \(\mathbb{R}\).
If we instead define \(r:[0,\infty)\to[0,\infty)\) by \(r(x)=x^2\), then \(r\) is injective. Indeed, if \(x_1,x_2\geq0\) and \(x_1^2=x_2^2\), then
If \(x_1+x_2=0\), nonnegativity forces \(x_1=x_2=0\). If \(x_1+x_2>0\), the displayed product being zero forces \(x_1-x_2=0\), again giving \(x_1=x_2\). The function \(r\) is also surjective onto \([0,\infty)\), by the existence of nonnegative square roots. It is therefore bijective and has an inverse. The formula is \(r^{-1}(y)=\sqrt{y}\): for \(y\geq0\), \((\sqrt y)^2=y\), and for \(x\geq0\), \(\sqrt{x^2}=x\).
The formula \(x^2\) alone does not determine whether a function is surjective; the codomain matters. A claim that a function is onto must be checked against the codomain named in its definition.
Proof Checks and a Common Pitfall
When writing a function proof, make the role of each variable explicit. For injectivity, choose arbitrary inputs from the domain, assume their outputs are equal, and derive equality of the inputs. For surjectivity, choose an arbitrary target from the codomain, construct a domain element, and verify its image. For a composition, keep track of the intermediate value in the middle codomain.
A frequent error is to solve the equation \(f(x)=y\) and stop without checking the domain. For instance, an algebraic formula for a candidate \(x\) does not establish surjectivity if that candidate is not in \(A\). Another error is to use the word “onto” without specifying the codomain. As the square-function example shows, the same rule can be surjective for one codomain and not for another.
Take arbitrary \(x_1,x_2\) in the domain. Assume \(f(x_1)=f(x_2)\), then use the formula or known properties to prove \(x_1=x_2\).
Take arbitrary \(y\) in the codomain. Find a candidate \(x\) in the domain and calculate \(f(x)\) to verify it equals \(y\).
Establish both injectivity and surjectivity, or verify directly that a proposed inverse satisfies both composition identities.
Check Your Understanding
Use the definitions and proof patterns in this tutorial to answer the following questions.
- To prove \(f:A\to B\) is injective, what should you assume about two arbitrary inputs, and what must you conclude?
- In a surjectivity proof, why must the target be chosen from the codomain rather than the domain?
- If \(g\circ f\) is injective, which of \(f\) and \(g\) must be injective according to the composition theorem?
- Why does surjectivity of \(g\circ f\) imply surjectivity of \(g\), but not necessarily surjectivity of \(f\)?
- What two identities must a proposed inverse satisfy?
- How can the same formula \(x^2\) define a surjective function for one codomain and a nonsurjective function for another?