Relations and Functions · Lesson 2 of 4
One-One, Onto and Bijective Functions
“Use domain, codomain and output patterns to classify functions and justify your conclusions.”
• Distinguish domain, codomain and range when classifying a function. • Prove or disprove injectivity and surjectivity. • Read function classifications from arrow diagrams and graphs. • Explain why changing a domain or codomain can change the classification. • Compare the finite-set result with functions on infinite sets. • Handle piecewise and restricted-domain functions with complete reasoning.
Two different questions about outputs
A function gives exactly one output to every input in its domain. That requirement still allows two inputs to share an output, and it allows some codomain elements to remain unused. We now study these two possibilities separately: whether inputs collide and whether the whole codomain is reached.
For f : X → Y, X is the domain and Y is the codomain. The range is the set of outputs actually produced, {f(x) : x ∈ X}. The range is always a subset of Y, but it need not equal Y. A formula alone does not specify a complete function: its domain and codomain are part of the information.
A function is one-one when distinct inputs always have distinct outputs. Equivalently, if f(x₁) = f(x₂), then x₁ = x₂. A function that is not one-one is called many-one.
A function f : X → Y is onto when every y in the codomain Y is f(x) for at least one x in the domain X.
A function is bijective when it is both one-one and onto. Each codomain element then has exactly one preimage.
A preimage of y is an input x satisfying f(x) = y. Onto asks for at least one such input for every codomain element. One-one allows at most one. Together they give exactly one, which is the reason bijections can later be reversed to form inverse functions.
Many-one does not mean one input has many outputs. Such a rule would fail to be a function. Many-one means that at least two different inputs share one output. Also, one-one does not automatically mean onto.
Proving one-one and checking the codomain
A simple linear formula is a useful starting point because equal outputs can be solved directly. Yet the same formula may reach the entire codomain in one setting and miss most of it in another. Always keep the sets beside the rule as you work.
Problem
Let A contain 50 students, and let f : A → ℕ assign each student their distinct roll number from 1 to 50. Classify f.
- 1.Different students have different assigned numbers, so f is one-one.
- 2.The codomain is all natural numbers, not merely the numbers 1 through 50.
- 3.The number 51 has no preimage in A. Therefore f is not onto.
- 4.If the codomain were changed to {1, 2, …, 50}, the same assignment would be bijective.
Problem
Show that f : ℕ → ℕ, f(x) = 2x, is one-one but not onto. Here ℕ = {1, 2, 3, …}.
- 1.Suppose f(x₁) = f(x₂). Then 2x₁ = 2x₂; division by 2 gives x₁ = x₂. So f is one-one.
- 2.Its range is {2, 4, 6, …}, the positive even integers.
- 3.For the codomain element 1, the equation 2x = 1 would require x = 1/2, which is not natural.
- 4.Thus 1 is missed, and f is not onto. It is enough to find one missed codomain element.
Problem
Now classify f : ℝ → ℝ, f(x) = 2x.
- 1.The same equal-output argument gives x₁ = x₂, so f is one-one.
- 2.To test onto, choose an arbitrary y ∈ ℝ and solve 2x = y, giving x = y/2.
- 3.Since y/2 is real, it is an allowed input. Substitution gives f(y/2) = 2(y/2) = y.
- 4.Every real y is reached, so f is onto and therefore bijective. The domain change altered the answer.
Collisions and missed outputs
To disprove injectivity, look for a repeated value from distinct inputs. To disprove surjectivity, look for a codomain value outside the range. These are independent checks: a function may have collisions while still reaching every required output.
Problem
Define f : ℕ → ℕ by f(1) = f(2) = 1 and f(x) = x − 1 for x > 2. Classify f.
- 1.The distinct inputs 1 and 2 both produce 1, so f is not one-one.
- 2.For y = 1, we can use input x = 1, giving f(1) = 1.
- 3.For any y > 1, use x = y + 1. This is a natural number greater than 2, so the rule f(x) = x − 1 applies.
- 4.Then f(y + 1) = y. Every natural output has a preimage, so f is onto but many-one.
Problem
Classify f : ℝ → ℝ, f(x) = x².
- 1.The inputs −1 and 1 are distinct, but f(−1) = f(1) = 1. Hence f is not one-one.
- 2.Every square of a real number is nonnegative. The negative codomain value −2 cannot be an output.
- 3.Thus f is not onto ℝ. Its range is [0, ∞).
- 4.The function is neither one-one nor onto. Its graph makes both the collision and the missing negative outputs visible.
Changing sets can remove one obstruction at a time. The square function from ℝ to [0, ∞) is onto but still many-one. From [0, ∞) to ℝ it is one-one but not onto. From [0, ∞) to [0, ∞) it is bijective: each y ≥ 0 has the unique nonnegative input √y. The formula is unchanged, but the function data is different.
| Domain | Codomain | Classification for x² |
|---|---|---|
| ℝ | ℝ | Neither one-one nor onto |
| ℝ | [0, ∞) | Many-one and onto |
| [0, ∞) | ℝ | One-one, not onto |
| [0, ∞) | [0, ∞) | Bijective |
A graph can show a collision or suggest a range, but a finite plot alone cannot prove a claim for every real input. Use the graph to guide an algebraic argument. In particular, the horizontal-line test for onto must refer to the stated codomain.
Piecewise rules require all cases
A piecewise function uses different formulas on different parts of the domain. For injectivity, compare inputs within each part and across different parts. For surjectivity, show how every output is produced, including boundary or exceptional values.
Problem
Let f : ℕ → ℕ be f(x) = x + 1 when x is odd and f(x) = x − 1 when x is even. Prove bijectivity.
- 1.The outputs are 1 ↦ 2, 2 ↦ 1, 3 ↦ 4, 4 ↦ 3, and so on. The rule swaps each adjacent odd-even pair.
- 2.For two odd inputs with equal outputs, x₁ + 1 = x₂ + 1 gives x₁ = x₂. For two even inputs, x₁ − 1 = x₂ − 1 gives the same conclusion.
- 3.Across the cases, an odd input produces an even output and an even input produces an odd output. Equal outputs cannot occur across the cases. Thus f is one-one.
- 4.For an odd output y, input y + 1 is even and f(y + 1) = y. For an even output y, input y − 1 is a positive odd integer and f(y − 1) = y.
- 5.Both output cases are reached. Therefore f is onto and hence bijective.
Problem
Let f : ℕ → ℕ satisfy f(n) = (n + 1)/2 for odd n and f(n) = n/2 for even n. Classify f.
- 1.For each positive integer k, the inputs 2k − 1 and 2k both map to k.
- 2.They are distinct, so f is many-one.
- 3.Every positive integer k has a preimage, for example 2k. Thus f is onto.
- 4.This rule pairs neighbouring inputs into one output; it does not swap them. Therefore it is not bijective.
Familiar functions under the two tests
Functions studied earlier now provide useful classification examples. The goal is to reuse their output behaviour, not to learn a separate procedure for each name. A collision disproves one-one, and the range identifies what the codomain test can or cannot pass.
| Function from ℝ to ℝ | A collision or injectivity reason | Range and onto conclusion |
|---|---|---|
| Greatest integer [x] | [0.2] = [0.8] = 0, so many-one | ℤ; not onto ℝ |
| Modulus |x| | |−1| = |1| = 1, so many-one | [0, ∞); not onto ℝ |
| Signum sgn(x) | sgn(1) = sgn(2) = 1, so many-one | {−1, 0, 1}; not onto ℝ |
| x³ | Strictly increasing; equal cubes give equal inputs | ℝ; onto ℝ |
| x⁴ | (−1)⁴ = 1⁴, so many-one | [0, ∞); not onto ℝ |
The greatest integer [x] is the integer immediately at or below x. The modulus |x| is x for x ≥ 0 and −x for x < 0. The signum function records only the sign of x: −1 for negative x, 0 for zero, and 1 for positive x. These rules explain the range statements in the table.
The cube function also illustrates the importance of number sets. On ℕ → ℕ and ℤ → ℤ, x³ is one-one, but a value such as 2 has no natural or integer cube-root input, so it is not onto. On ℝ → ℝ, every real number has a real cube root, so it is bijective. Similarly, x² on ℕ is one-one but not onto, while on ℤ it is neither.
Problem
Prove directly that f : ℝ → ℝ, f(x) = x³, is one-one and onto.
- 1.Suppose x₁³ = x₂³. Subtract and factor: (x₁ − x₂)(x₁² + x₁x₂ + x₂²) = 0.
- 2.The second factor equals (x₁ + x₂/2)² + 3x₂²/4. It is nonnegative and can be zero only when x₂ = 0 and x₁ = 0.
- 3.If that factor is positive, the first factor must be zero, giving x₁ = x₂. If it is zero, both inputs are already zero. Thus equal cubes always give equal inputs.
- 4.For any y ∈ ℝ, the real cube root x = ∛y belongs to ℝ and satisfies x³ = y. Therefore the function is onto as well as one-one.
Problem
Classify f : ℝ* → ℝ*, f(x) = 1/x, where ℝ* is the set of nonzero real numbers. Then change only the domain to ℕ.
- 1.For nonzero x₁ and x₂, equality 1/x₁ = 1/x₂ allows multiplication by x₁x₂, giving x₂ = x₁. Thus f is one-one.
- 2.For any nonzero real output y, choose x = 1/y. This is a nonzero real input and f(1/y) = y.
- 3.The original function is therefore bijective.
- 4.With domain ℕ and codomain ℝ*, the equal-output proof still works, but −1 has no natural preimage. The changed function is one-one, not onto.
Problem
Let A = ℝ ∖ {3}, B = ℝ ∖ {1}, and f : A → B be f(x) = (x − 2)/(x − 3). Prove that f is bijective.
- 1.The denominator is nonzero on A. Also f(x) = 1 would imply x − 2 = x − 3, an impossibility. Thus all outputs lie in B.
- 2.If f(x₁) = f(x₂), cross-multiply using nonzero denominators: (x₁ − 2)(x₂ − 3) = (x₂ − 2)(x₁ − 3).
- 3.Expand: x₁x₂ − 3x₁ − 2x₂ + 6 = x₁x₂ − 3x₂ − 2x₁ + 6. Cancel shared terms to obtain −x₁ + x₂ = 0, so x₁ = x₂.
- 4.For onto, let y ∈ B. Solve y(x − 3) = x − 2, so x(y − 1) = 3y − 2 and x = (3y − 2)/(y − 1). This is defined because y ≠ 1.
- 5.This x cannot equal 3: that would imply 3y − 2 = 3y − 3. Therefore x ∈ A. Substitution gives f(x) = y, proving onto and hence bijectivity.
Problem
For sets A and B, show that f : A × B → B × A, f(a, b) = (b, a), is bijective.
- 1.If f(a₁, b₁) = f(a₂, b₂), then (b₁, a₁) = (b₂, a₂). Equality of ordered pairs gives b₁ = b₂ and a₁ = a₂. Hence the original inputs are equal.
- 2.For any output (b, a) ∈ B × A, the input (a, b) ∈ A × B maps to it.
- 3.Both injectivity and surjectivity hold, so f is bijective. If a product is empty, the same statements hold vacuously.
A special fact about finite sets
On a finite set, an output collision reduces the number of distinct outputs. If domain and codomain have the same finite size, there is no spare capacity to make up that loss. This counting idea explains why one-one and onto become equivalent in this particular setting.
Problem
Let f : {1, 2, 3} → {1, 2, 3} be onto. Show that f is one-one.
- 1.Suppose two different inputs shared an output. Those two inputs would then supply only one distinct output.
- 2.The remaining input supplies at most one more distinct output. The range would contain at most two elements.
- 3.But onto requires all three codomain elements to appear. This contradicts the assumption, so f is one-one.
Problem
Let f : {1, 2, 3} → {1, 2, 3} be one-one. Show that f is onto.
- 1.The three domain elements must produce three different outputs.
- 2.All three outputs lie in a codomain containing exactly three elements.
- 3.Therefore the range fills the codomain and f is onto.
The argument works for any finite set X: a function f : X → X is one-one if and only if it is onto. It also works for two finite sets of equal size. It does not say that every function on a finite set is bijective, and it does not apply without the equal-size requirement.
For an infinite set, the earlier examples show both failures. Doubling on ℕ is one-one but not onto. The function with f(1) = f(2) = 1 and f(x) = x − 1 for x > 2 is onto but not one-one. These are concrete reasons why a finite counting argument cannot simply be transferred to an infinite set.
Check your understanding
Read the declared sets before classifying each rule. Use one distinct-input collision for a failed injectivity test and one missed codomain value for a failed surjectivity test. When a test succeeds, think about a reason that covers all allowed elements.
Quiz
Which condition means f : X → Y is onto?
For f : ℕ → ℕ, f(n) = 2n, which statement is correct?
For f : [0, ∞) → [0, ∞), f(x) = x², which is correct?
What disproves one-one for the greatest integer function on ℝ?
An onto function from a finite set X to itself must be:
The rule f(n) = (n + 1)/2 for odd n and n/2 for even n, from ℕ to ℕ, is:
For f : ℝ → ℝ, f(x) = 1 + x², which codomain element shows it is not onto?
What must an onto proof check after solving f(x) = y?
Practice Problems
- Classify f(x) = x² on ℕ → ℕ, ℤ → ℤ and ℝ → ℝ. Give explicit reasons for each classification.
- Prove that f : ℝ → ℝ, f(x) = 3 − 4x, is bijective, including the domain check for a preimage of an arbitrary y.
- For f : {1, 2, 3} → {4, 5, 6, 7}, f = {(1, 4), (2, 5), (3, 6)}, identify the range and classify the function.
- Explain why changing the codomain of the modulus function to [0, ∞) changes surjectivity but does not remove its input collisions.
- Write a piecewise rule that swaps adjacent positive integers, and prove it is one-one across as well as within its cases.
- Prove that x³ is one-one on ℝ. Then explain why the same rule is not onto when both domain and codomain are ℤ.
- For f : ℝ ∖ {3} → ℝ ∖ {1}, f(x) = (x − 2)/(x − 3), find a preimage of y = 2 and explain why y = 1 is excluded.
- Construct an onto but many-one function from {1, 2, 3, 4} to {a, b, c}. Explain why it does not contradict the finite-set result.
Key Takeaways
• Injectivity prevents different inputs from sharing an output; surjectivity reaches every stated codomain element. • A bijection supplies exactly one preimage for each codomain element. • Domain, codomain and range are different pieces of information; changing sets can change a classification. • Use arbitrary-input proofs for successful tests and explicit counterexamples for failed tests. • Piecewise functions require comparisons within and across their cases. • For a function from a finite set to itself, one-one and onto are equivalent; infinite-set examples show why this is not a general rule.