A coat check#
At a coat check, every coat gets a numbered hook. Think of the coats as inputs and the hooks as outputs. The attendant’s rule, coat to hook, is a function.
- If no two coats ever share a hook, the rule is injective, also called one-to-one.
- If every hook ends up with a coat, the rule is surjective, also called onto.
- If both happen, one coat per hook and no empty hooks, the rule is bijective. A bijection is a perfect pairing.
Hold on to that picture. Every definition below is one of those three sentences written in symbols.
A function has three parts#
A function f: A → B is read “f from A to B”. It has three parts:
- the domain A, the allowed inputs (the coats);
- the codomain B, where outputs are allowed to land (the hooks);
- the rule, which gives each input exactly one output.
The range (also called the image, Im f) is the set of outputs actually used. It sits inside the codomain and can be smaller.
Change the domain or the codomain and you have a different function, even with the same rule. This matters a lot for x², as you will see.
Injective: no two inputs share an output#
Definition. f is injective when different inputs always give different outputs. For all x₁, x₂ in A: if x₁ ≠ x₂, then f(x₁) ≠ f(x₂).
How to prove it. Statements about ≠ are awkward to work with, so prove the contrapositive, which means the same thing:
Assume f(x₁) = f(x₂). Show x₁ = x₂.
Example: f(x) = 3x − 7 on the real numbers ℝ. Assume 3x₁ − 7 = 3x₂ − 7. Add 7 and divide by 3: x₁ = x₂. Done.
How to disprove it. Find two different inputs with the same output. For x² on ℝ, f(1) = f(−1) = 1.
A trap: “if x₁ = x₂ then f(x₁) = f(x₂)” is true of every function. Proving it shows nothing. Make sure the equal sign you start from is between the outputs.
Surjective: every output gets used#
Definition. f is surjective when the range equals the codomain. For every y in B there is at least one x in A with f(x) = y.
How to prove it. Start from the codomain, not the domain:
Take an arbitrary y in B. Solve f(x) = y for x. Check that x is in A.
Example: f(x) = 3x − 7 on ℝ. Given y, solve 3x − 7 = y to get x = (y + 7)/3. That is a real number, so it is in the domain, and f(x) = y. Done.
How to disprove it. Find one y in the codomain that nothing reaches. For f(n) = 2n on the integers ℤ, the output 3 is never reached, because 2n = 3 has no integer solution.
Bijective: exactly one solution#
Put the two together. f is a bijection when, for every y in the codomain, the equation f(x) = y has exactly one solution.
| For every y, f(x) = y has… | Name |
|---|---|
| at most one solution | injective |
| at least one solution | surjective |
| exactly one solution | bijective |
That unique solution is the inverse function, f−1(y). Only bijections have inverses.
When the domain and codomain are the same set, a bijection is also called a permutation. The map x ↦ 3x mod 7 on {1, …, 6} is one.
If A and B are finite and have the same number of elements, then injective and surjective are the same thing. n different outputs inside an n-element set must fill it. This fails for infinite sets: n ↦ 2n on ℕ is injective and not onto.
Five examples, side by side#
| Function | Injective? | Surjective? | Why |
|---|---|---|---|
| x², ℝ → ℝ | No | No | f(1) = f(−1); −1 is never an output |
| x², [0, ∞) → [0, ∞) | Yes | Yes | no negatives to collide; y is hit by √y |
| 2n, ℤ → ℤ | Yes | No | odd numbers are never hit |
| 3x − 7, ℝ → ℝ | Yes | Yes | x = (y + 7)/3 is the unique solution |
| ⌊n/2⌋, ℤ → ℤ | No | Yes | f(0) = f(1) = 0; f(2m) = m |
The first two rows use the same rule, x². Only the domain and codomain changed, and the answer flipped from “neither” to “bijective”. (⌊n/2⌋ is read “the floor of n over 2”: divide, then round down.)
Counting is a bijection#
When you count a pile of coins, you touch each one and say “one, two, three…”. You never skip a coin and never say a number twice. That is a bijection between the coins and the set {1, 2, …, n}, which the course writes as [n].
So the course defines: a finite set A has n elements, written |A| = n (read “the cardinality of A is n”), when there is a bijection from A to [n]. More generally, two sets have the same cardinality when there is a bijection between them.
This definition also works for infinite sets, where it gives surprising answers. The map n ↦ 2n is a bijection from ℕ = {1, 2, 3, …} to the even numbers {2, 4, 6, …}. So there are exactly as many even numbers as natural numbers, even though the evens are a proper part of ℕ.
Why a set with n elements has 2n subsets#
The power set P(A) is the set of all subsets of A. For A = {a, b, c}:
∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}. That is 8 = 23.
Both ∅ (the empty set) and A itself count. The empty set is a subset of every set, and every set is a subset of itself.
Why 2n: to build a subset, go through the elements one at a time and answer in or out. That is two independent choices per element, so 2 · 2 · … · 2 = 2n. In the language of this page, subsets are in bijection with strings of n bits, 1 for in and 0 for out.
Injective: assume f(x₁) = f(x₂) and show x₁ = x₂. Surjective: take any y and solve f(x) = y inside the domain.
Where this goes wrong#
- Proving the wrong direction for injective. Starting from x₁ = x₂ proves nothing.
- Starting a surjectivity proof from x. Computing some outputs does not show every y is reached. Start from y.
- Ignoring the codomain. “Is x² onto?” has no answer until you know the codomain.
- Solving for x and not checking it lies in the domain. For f(n) = 2n on ℤ, solving 2n = 3 gives n = 1.5, which is not an integer. That is exactly why f is not onto.
- Forgetting ∅ or A when listing subsets. The count is 2n, not 2n − 2.
Test yourself in the free Kestrel Exams app
Topic-selectable Discrete Math practice — offline, no ads, no account.
Practice functions and cardinality →Frequently asked questions#
What is the difference between injective and surjective?
Injective (one-to-one) means no two inputs share an output. Surjective (onto) means every element of the codomain is an output of something. A function can be either, both, or neither; both together is a bijection.
How do you prove a function is injective?
Assume f(x₁) = f(x₂) and use algebra to show x₁ = x₂. This is the contrapositive of the definition, and it is easier because you get to start from an equation.
How do you prove a function is surjective?
Take an arbitrary y in the codomain, solve f(x) = y for x, and check that the x you found is in the domain. If some y has no solution in the domain, the function is not onto.
Is f(x) = x² one-to-one?
Not on the real numbers, since f(1) = f(−1). On the domain [0, ∞) it is one-to-one, and with codomain [0, ∞) it is also onto, so it becomes a bijection. The domain and codomain are part of the function.
Why does a set with n elements have 2^n subsets?
Each element is independently either in the subset or out of it, which is 2 choices per element. Multiplying gives 2^n. This counts the empty set and the whole set too.
Something here not clear? A topic you wish we covered? Tell us. We read every message, and a request is the fastest way to get a guide written — several of these exist because somebody asked.