Discrete Math › Section F · Discrete structures revisited › Topic F.2
Functions: injections, surjections, bijections
A function sends every input to exactly one output. Asking whether different inputs can share an output, and whether every possible output is reached, sorts functions into injections, surjections and bijections, and those ideas underlie counting, inverses and even the comparison of infinite sets.
What a function is
A function \(f: A \to B\) assigns to every element of the domain \(A\) exactly one element of the codomain \(B\). Both parts of "exactly one" matter: a rule that gives some input two outputs, or no output at all, is not a function. The range, or image, of \(f\) is the set of outputs actually produced, and it can be smaller than the codomain. The codomain is part of the function's definition, so \(n \mapsto 2n\) from \(\mathbb{Z}\) to \(\mathbb{Z}\) and the same rule from \(\mathbb{Z}\) to the even integers count as different functions with different properties.
Describing functions
With a finite domain you can simply list the assignments. Two-line notation puts the inputs on a top row and each output directly beneath its input. For example, take \(f: \{1, 2, 3, 4, 5\} \to \{a, b, c, d\}\) with \(f(1) = b\), \(f(2) = a\), \(f(3) = b\), \(f(4) = d\) and \(f(5) = a\). An arrow diagram carries the same information, and infinite domains need a formula such as \(f(n) = 3n + 1\). In an arrow diagram, "function" means exactly one arrow leaves every input; any number of arrows, including none, may arrive at an output.
Image and inverse image
For a subset \(S\) of the domain, the image \(f(S)\) is the set of outputs of elements of \(S\). For a subset \(T\) of the codomain, the inverse image \(f^{-1}(T)\) is the set of inputs whose outputs land in \(T\). With the function of the previous card, \(f(\{1, 2, 3\}) = \{a, b\}\), \(f^{-1}(\{a\}) = \{2, 5\}\), and \(f^{-1}(\{c\}) = \varnothing\) because nothing maps to \(c\). The range is \(f(A) = \{a, b, d\}\). The inverse image always makes sense, even when \(f\) has no inverse function: the notation \(f^{-1}(T)\) names a set of inputs, not the output of an inverse.
Injections: no collisions
A function is injective, or one-to-one, if different inputs always give different outputs. Equivalently, \(f(x) = f(y)\) implies \(x = y\), which is the form used in proofs. On \(\mathbb{Z}\), \(f(n) = 3n + 1\) is injective: if \(3x + 1 = 3y + 1\) then \(x = y\). The squaring function \(n \mapsto n^2\) on \(\mathbb{Z}\) is not, since \(2\) and \(-2\) both go to 4. One collision disproves injectivity: the five-element function above fails because \(f(1) = f(3)\). In an arrow diagram, injective means no output receives two arrows.
Surjections: nothing missed
A function is surjective, or onto, when each codomain element is produced by at least one input; that is, the range equals the codomain. On \(\mathbb{Z}\), \(f(n) = 3n + 1\) is not surjective: \(3n + 1 = 2\) has no integer solution, so 2 is never produced. The function \(g(n) = n - 5\) is surjective, because any target \(m\) is reached from \(n = m + 5\). Surjectivity depends on the codomain: \(n \mapsto 3n + 1\) becomes surjective if the codomain is shrunk to its own range, \(\{\ldots, -2, 1, 4, 7, \ldots\}\). To prove surjectivity, take an arbitrary target and produce an input that hits it.
Bijections and inverses
A bijection is a function that is both injective and surjective, so it pairs the elements of the domain and codomain perfectly, one to one. Exactly the bijections have inverse functions: \(f^{-1}(b)\) is the unique input that maps to \(b\), so \(f^{-1}(f(a)) = a\) for every \(a\). For \(g(n) = n - 5\) on \(\mathbb{Z}\), the inverse is \(g^{-1}(m) = m + 5\). Bijections make "the same size" precise: two finite sets have the same number of elements exactly when there is a bijection between them.
Worked example: classifying functions
Classify \(h: \mathbb{N} \to \mathbb{N}\) with \(h(n) = \lfloor n/2 \rfloor\), where \(\lfloor x \rfloor\) means \(x\) rounded down. 1. List some values: \(h(0) = 0\), \(h(1) = 0\), \(h(2) = 1\), \(h(3) = 1\), \(h(4) = 2\). 2. Injective? No: \(h(0) = h(1) = 0\) is a collision. 3. Surjective? Take any target \(m \in \mathbb{N}\). Then \(h(2m) = m\), so every target is hit. Yes. 4. So \(h\) is a surjection but not a bijection, and it has no inverse function. 5. Compare \(k(n) = 2n\) on \(\mathbb{N}\): injective, since \(2x = 2y\) gives \(x = y\), but not surjective, since 1 is never hit.
Composition
If \(f: A \to B\) and \(g: B \to C\), the composition \(g \circ f: A \to C\) is \((g \circ f)(x) = g(f(x))\): apply \(f\) first, then \(g\). Order matters. With \(f(x) = x + 2\) and \(g(x) = 3x\), \((g \circ f)(4) = g(6) = 18\) but \((f \circ g)(4) = f(12) = 14\). Compositions keep good properties: a composition of injections is injective, of surjections is surjective, and so of bijections is a bijection, with \((g \circ f)^{-1} = f^{-1} \circ g^{-1}\). Undoing the steps happens in reverse order, like taking off shoes before socks.
Worked example: counting functions
How many functions are there from \(A = \{1, 2, 3\}\) to \(B = \{w, x, y, z\}\), and how many are injective? 1. A function is fixed by choosing an output for each input. Each of the 3 inputs has 4 choices, so the product principle gives \(4^3 = 64\) functions. 2. For an injection, input 1 has 4 choices, input 2 must avoid that output (3 choices), and input 3 must avoid both (2 choices): \(4 \cdot 3 \cdot 2 = 24\). 3. None of the 24 is surjective: 3 inputs cannot hit 4 outputs. 4. In general, from an \(m\)-set to an \(n\)-set there are \(n^m\) functions and \(n(n-1)\cdots(n - m + 1)\) injections when \(m \le n\). When \(m > n\) there are no injections at all, the idea behind "The pigeonhole principle".
Floors, ceilings and infinite sets
Two functions from \(\mathbb{R}\) to \(\mathbb{Z}\) appear constantly in computing: the floor \(\lfloor x \rfloor\) rounds down and the ceiling \(\lceil x \rceil\) rounds up, so \(\lfloor 4.6 \rfloor = 4\) and \(\lceil 4.6 \rceil = 5\). Showing 23 items at 5 per page needs \(\lceil 23/5 \rceil = 5\) pages. Bijections also compare infinite sets. The list 0, 1, \(-1\), 2, \(-2\), … pairs \(\mathbb{N}\) with \(\mathbb{Z}\), so the integers are countable. Cantor's diagonal argument shows that no list can contain every real number, so \(\mathbb{R}\) is uncountable: some infinite sets are strictly larger than others.
Common mistakes to avoid
First, ignoring the codomain: whether a function is surjective depends on it. Second, confusing range and codomain. Third, proving injectivity by checking a few values; you need \(f(x) = f(y) \Rightarrow x = y\) for all \(x\) and \(y\), while one collision disproves it. Fourth, reading \(f^{-1}(T)\) as requiring an inverse function; inverse images exist for every function. Fifth, composing in the wrong order: \(g \circ f\) applies \(f\) first. Sixth, counting functions as \(m^n\) instead of \(n^m\): the inputs make the choices.
Key takeaways
A function gives each input exactly one output in the codomain; the range is what is actually hit. Images \(f(S)\) and inverse images \(f^{-1}(T)\) are sets. Injective means no two inputs share an output, surjective means every codomain element is hit, and bijective means both, which is exactly when an inverse exists. Composition applies the right-hand function first and preserves all three properties. There are \(n^m\) functions from an \(m\)-set to an \(n\)-set, and bijections compare sizes of sets, finite or infinite.
Flashcards
Flashcard
Each element of A gets exactly one output in B
Test your understanding
Question 1 of 5
Consider f: ℤ → ℤ given by f(n) = 2n. Which description is correct?
Question 2 of 5
How many functions are there from a 3-element set to a 4-element set?
Question 3 of 5
With f(x) = x + 2 and g(x) = 3x, what is (g ∘ f)(4)?
Question 4 of 5
Let f: {1, 2, 3, 4} → {a, b, c} with f(1) = c, f(2) = a, f(3) = c, f(4) = b. What is the inverse image f⁻¹({c})?
Question 5 of 5
A website shows 5 results per page. How many pages does it need for 23 results?
