Reading Injectivity and Surjectivity from a Map
A function can send different inputs to the same output, and it may fail to use some of the elements in its codomain. These two possibilities are measured by injectivity and surjectivity. They can be described directly using elements, but images and preimages of subsets give useful tests as well. Throughout, \(f:X\to Y\) is a function between sets; no topology is assumed.
For \(A\subseteq X\), the image is \(f(A)=\{f(x):x\in A\}\). For \(C\subseteq Y\), the preimage is \(f^{-1}(C)=\{x\in X:f(x)\in C\}\). In particular, \(f^{-1}(\{y\})\) is the set of inputs mapped to \(y\); this notation denotes a preimage, not an inverse function.
The two definitions ask different questions. Injectivity restricts how many inputs may map to one output. Surjectivity asks whether each element of the specified codomain is reached. Thus surjectivity depends on the choice of codomain: the same rule for assigning values can be surjective with one codomain and not surjective with a larger one.
“At most one” includes the possibility that a fiber is empty. If \(Y=\varnothing\), a function \(f:X\to Y\) can exist only when \(X=\varnothing\); in that case every fiber condition is vacuous, and the function is both injective and surjective. If \(X=\varnothing\) and \(Y\ne\varnothing\), the unique function from \(X\) to \(Y\) is injective but not surjective: every fiber is empty.
Fibers and Image Tests
Proof. First consider injectivity. If \(f\) is injective and \(x,x'\in f^{-1}(\{y\})\), then \(f(x)=y=f(x')\), so \(x=x'\). Thus each fiber has at most one element. Conversely, suppose every fiber has at most one element and \(f(x)=f(x')\). Put \(y=f(x)=f(x')\). Both \(x\) and \(x'\) belong to \(f^{-1}(\{y\})\), so \(x=x'\); hence \(f\) is injective. For surjectivity, if \(f\) is surjective, then for each \(y\in Y\) some \(x\in X\) satisfies \(f(x)=y\), so \(x\in f^{-1}(\{y\})\), making the fiber nonempty. Conversely, if every fiber is nonempty, then for each \(y\in Y\) there is \(x\in f^{-1}(\{y\})\), which means \(f(x)=y\). Therefore \(f\) is surjective. \(\square\)
Fibers can also reveal which set identities hold. For arbitrary \(A,B\subseteq X\), an element \(y\in f(A\cap B)\) comes from an input in both \(A\) and \(B\), so \(y\in f(A)\cap f(B)\). This always gives one inclusion. The reverse inclusion can fail: the same output may come from one input in \(A\) and a different input in \(B\).
Proof. For any \(A,B\subseteq X\), if \(y\in f(A\cap B)\), then \(y=f(x)\) for some \(x\in A\cap B\). Since \(x\in A\) and \(x\in B\), we have \(y\in f(A)\cap f(B)\). Thus \(f(A\cap B)\subseteq f(A)\cap f(B)\) for every function. If \(f\) is injective and \(y\in f(A)\cap f(B)\), there are \(a\in A\) and \(b\in B\) with \(f(a)=y=f(b)\). Injectivity gives \(a=b\), so \(a\in A\cap B\) and \(y\in f(A\cap B)\). This proves equality. Conversely, suppose equality holds for every pair of subsets. If \(f(x)=f(x')\), choose \(A=\{x\}\) and \(B=\{x'\}\). Then \(f(A)\cap f(B)=\{f(x)\}\), so the assumed equality implies \(f(A\cap B)\ne\varnothing\). Therefore \(A\cap B\ne\varnothing\), which for these singleton sets means \(x=x'\). Hence \(f\) is injective. \(\square\)
Worked Example: A Map That Is Neither Injective Nor Surjective
Let \(X=\{1,2,3,4\}\), \(Y=\{a,b,c\}\), and define \(f:X\to Y\) by \(f(1)=a\), \(f(2)=b\), \(f(3)=b\), and \(f(4)=a\). Find its fibers and test both properties using subsets.
The fiber over \(a\) is \(f^{-1}(\{a\})=\{1,4\}\), since the inputs 1 and 4 map to \(a\). The fiber over \(b\) is \(f^{-1}(\{b\})=\{2,3\}\), since 2 and 3 map to \(b\). The fiber over \(c\) is \(f^{-1}(\{c\})=\varnothing\), since none of the four inputs maps to \(c\). The first two fibers each have two elements, so the map is not injective. The fiber over \(c\) is empty, so the map is not surjective.
For the image-intersection test, take \(A=\{1\}\) and \(B=\{4\}\). Then \(A\cap B=\varnothing\), so \(f(A\cap B)=f(\varnothing)=\varnothing\). But \(f(A)=\{a\}\) and \(f(B)=\{a\}\), hence \(f(A)\cap f(B)=\{a\}\). The two sides differ, as expected for a map that is not injective.
Check: The full image is \(f(X)=\{a,b\}\), which omits \(c\). This agrees with the empty fiber over \(c\) and confirms that the map is not surjective.
Preimages of Images and Images of Preimages
There are two more useful identities. For \(A\subseteq X\), every element of \(A\) certainly maps into \(f(A)\), so \(A\subseteq f^{-1}(f(A))\). Equality may fail when an input outside \(A\) has the same output as an input in \(A\). For \(C\subseteq Y\), the set \(f(f^{-1}(C))\) consists of the elements of \(C\) that are actually attained by \(f\). Precisely, the identity is \(f(f^{-1}(C))=C\cap f(X)\).
Proof. For part (a), the inclusion \(A\subseteq f^{-1}(f(A))\) holds because if \(x\in A\), then \(f(x)\in f(A)\). Suppose \(f\) is injective and \(x\in f^{-1}(f(A))\). Then \(f(x)\in f(A)\), so there is \(a\in A\) with \(f(x)=f(a)\). Injectivity gives \(x=a\), hence \(x\in A\). This proves equality. Conversely, suppose the equality holds for every \(A\subseteq X\). If \(f(x)=f(x')\), set \(A=\{x\}\). Then \(x'\in f^{-1}(f(A))=A\), so \(x'=x\), proving injectivity.
For part (b), an element \(y\) belongs to \(f(f^{-1}(C))\) exactly when there is \(x\in X\) with \(x\in f^{-1}(C)\) and \(f(x)=y\). The first condition says \(f(x)\in C\), so \(y=f(x)\in C\); also \(y\in f(X)\). Conversely, if \(y\in C\cap f(X)\), then \(y=f(x)\) for some \(x\in X\), and \(f(x)=y\in C\) gives \(x\in f^{-1}(C)\). Thus \(y\in f(f^{-1}(C))\), proving \(f(f^{-1}(C))=C\cap f(X)\). If \(f\) is surjective, \(f(X)=Y\), so this identity gives \(f(f^{-1}(C))=C\) for every \(C\subseteq Y\). Conversely, if that equality holds for every \(C\subseteq Y\), take \(C=Y\). Then \(f(X)=f(f^{-1}(Y))=Y\), so \(f\) is surjective. \(\square\)
Worked Example: Injective but Not Surjective
Let \(X=\{1,2\}\), \(Y=\{a,b,c\}\), with \(f(1)=a\) and \(f(2)=c\). The fibers are \(f^{-1}(\{a\})=\{1\}\), \(f^{-1}(\{b\})=\varnothing\), and \(f^{-1}(\{c\})=\{2\}\). Each fiber has at most one element, so \(f\) is injective; the empty fiber over \(b\) shows it is not surjective.
Take \(A=\{2\}\). Its image is \(f(A)=\{c\}\), and the preimage of that image is \(f^{-1}(\{c\})=\{2\}=A\). Now take \(C=\{a,b\}\). Its preimage is \(f^{-1}(C)=\{1\}\), so \(f(f^{-1}(C))=f(\{1\})=\{a\}\), not \(C\). The missing element is \(b\), which is not in \(f(X)=\{a,c\}\).
Check: For \(C=\{a,b\}\), \(C\cap f(X)=\{a,b\}\cap\{a,c\}=\{a\}\). This equals the computed value \(f(f^{-1}(C))=\{a\}\), as the identity requires.
Worked Example: Surjective but Not Injective
Let \(X=\{1,2,3\}\), \(Y=\{a,b\}\), with \(f(1)=a\), \(f(2)=a\), and \(f(3)=b\). The fibers are \(f^{-1}(\{a\})=\{1,2\}\) and \(f^{-1}(\{b\})=\{3\}\). Both are nonempty, so \(f\) is surjective; the fiber over \(a\) has two elements, so it is not injective.
Let \(A=\{1\}\). Then \(f(A)=\{a\}\), and \(f^{-1}(f(A))=f^{-1}(\{a\})=\{1,2\}\), which is larger than \(A\). This shows concretely why the preimage of an image need not return the original subset. For the surjectivity test, take \(C=\{b\}\). Then \(f^{-1}(C)=\{3\}\), and \(f(f^{-1}(C))=f(\{3\})=\{b\}=C\).
Check: The image of the whole domain is \(f(X)=\{a,b\}=Y\), so the map is surjective. The equality \(f(1)=f(2)=a\) with \(1\ne2\) confirms directly that it is not injective.
A Common Mistake and a Practical Checklist
A frequent error is to assume that images always preserve intersections. In the first example, \(A=\{1\}\) and \(B=\{4\}\) are disjoint, yet \(f(A)\cap f(B)=\{a\}\). The incorrect calculation would be \(f(A)\cap f(B)=f(A\cap B)=f(\varnothing)=\varnothing\). The correction is that the identity \(f(A\cap B)=f(A)\cap f(B)\) is guaranteed when \(f\) is injective; for an arbitrary function only the inclusion \(f(A\cap B)\subseteq f(A)\cap f(B)\) is guaranteed. Distinct inputs can produce the same output.
When diagnosing a map, first write down its domain and codomain: the codomain determines which fibers must be checked for surjectivity. Then compute fibers or the full image. Fibers with more than one input disprove injectivity; empty fibers disprove surjectivity. If working with subsets instead, use the appropriate tests:
- Injectivity is equivalent to \(f(A\cap B)=f(A)\cap f(B)\) for all \(A,B\subseteq X\).
- Injectivity is equivalent to \(f^{-1}(f(A))=A\) for all \(A\subseteq X\).
- Surjectivity is equivalent to \(f(X)=Y\), or to \(f(f^{-1}(C))=C\) for all \(C\subseteq Y\).
Check Your Understanding
For each question, keep track of the domain and codomain as well as the assignment rule.
- For \(f:\{1,2,3\}\to\{a,b\}\) with \(f(1)=a\), \(f(2)=b\), \(f(3)=b\), list both fibers and decide whether \(f\) is injective and surjective.
- Give a function that is injective but not surjective, and verify both properties by its fibers.
- Prove directly from the element definition that \(f(A)\subseteq f(B)\) whenever \(A\subseteq B\).
- For an arbitrary function \(f:X\to Y\), explain why \(f^{-1}(C\cap D)=f^{-1}(C)\cap f^{-1}(D)\) for \(C,D\subseteq Y\), without assuming injectivity or surjectivity.
- For the map in question 1, choose \(A=\{1\}\) and \(B=\{2,3\}\). Compute \(f(A\cap B)\) and \(f(A)\cap f(B)\), and relate the results to injectivity.