Back to the on-screen lesson ·
Two independent questions asked of one function, the four combinations they produce, and the matching that lets one set be counted by another.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to prove a function injective by assuming equal outputs and deriving equal inputs, prove it surjective by solving for an arbitrary target, and refute either with a single pair or a single unreached element. You will also be able to count the functions, the injections and the bijections between two finite sets, and say why a bijection is what makes two sets the same size — including the infinite case, where a set can be matched exactly with a proper subset of itself.
You have used functions since school and you met injective, surjective and bijective in precalculus, where they decided whether an inverse exists. What is new here is that each is a quantified statement of the kind lesson 4 taught you to read, so each is proved and refuted by a definite kind of object, and that a bijection is a way of counting one set with another.
A function $f : A \to B$ assigns exactly one element of $B$ to each element of $A$; $A$ is the domain and $B$ the codomain. The image is the set of values actually taken, which may be smaller than the codomain. $f$ is injective (one-to-one) when different inputs give different outputs, surjective (onto) when the image is the whole codomain, and bijective when it is both.
| Property | Says | Refuted by |
|---|---|---|
| injective | $\forall a, b\, (f(a) = f(b) \Rightarrow a = b)$ | one pair of distinct inputs sharing an output |
| surjective | $\forall y \in B\, \exists a \in A\, (f(a) = y)$ | one element of $B$ nothing reaches |
These are separate questions and all four combinations happen. $f(n) = 2n$ on the integers is injective and not surjective; $f(n) = \lfloor n/2 \rfloor$ on the whole numbers is surjective and not injective; $f(x) = x^3$ on the reals is both; $f(x) = x^2$ on the reals is neither.
The domain and codomain are part of the function. $f(x) = x^2$ is not injective on $\mathbb{R}$ and is injective on $[0, \infty)$; it is not surjective onto $\mathbb{R}$ and is surjective onto $[0, \infty)$. The rule did not change. A question about injectivity with no domain named is not a question yet.
Why bijections matter. A bijection $f : A \to B$ pairs the elements of $A$ with those of $B$ with nothing left over on either side. For finite sets that means $|A| = |B|$, and it is how almost every count in unit 4 is really done: rather than counting the things you want, match them with things already counted. Lesson 12's $2^n$ was exactly this — subsets matched with sequences of in-or-out decisions.
For infinite sets the bijection becomes the definition of same size, and the consequences are strange and forced. The even numbers can be matched with all the whole numbers by $n \mapsto 2n$, so there are as many even numbers as whole numbers. Nothing has gone wrong; same size simply cannot mean one is contained in the other once the sets are infinite, and the bijection is the only definition that survives.
Another way: steps
To decide what kind a function is:
Another way: picture
Two rows of dots with arrows from the first row to the second. Injective means no two arrows land on the same dot; surjective means no dot in the second row is missed. A bijection is a perfect pairing-off, and you can see at a glance that a perfect pairing forces the two rows to be the same length.
| What | How many, from $A$ to $B$ | Why |
|---|---|---|
| all functions | $|B|^{|A|}$ | one free choice per input |
| injections | $|B|(|B|-1)\cdots(|B|-|A|+1)$ | each input uses up a target |
| bijections | $|A|!$ when $|A| = |B|$, else $0$ | a perfect pairing is a permutation |
The exponent in the first row is the size of the domain, which is worth checking on a small case rather than remembering: from one element to three there are three functions, and $3^1$ is three while $1^3$ is one.
The second row hands you the pigeonhole principle before unit 4 states it. When $|A| > |B|$ the product runs down past zero and there are no injections at all — which says that some two inputs must share an output, which is exactly what the principle asserts.
Deciding injectivity without a domain. $x^2$ is injective or not depending on where it is defined.
Confusing image and codomain. Surjectivity is a claim about the codomain the function was declared with.
Putting the exponent on the wrong set. It is $|B|^{|A|}$.
Expecting an inverse from injectivity alone. An injective function has an inverse defined on its image; to have one defined on the whole codomain it must also be surjective.
Arguing about infinite sets from containment. The even numbers are a proper subset of the whole numbers and are the same size; for infinite sets, containment and size are different questions.
The horizontal line test is a way of seeing injectivity for a function of one real variable, and it is not the definition. The definition is a statement about every pair of inputs, and it applies to functions between sets of people, sets of subsets and sets of sequences, where there is no graph to look at. Proving injectivity means assuming $f(a) = f(b)$ and deriving $a = b$; that argument works everywhere, and the picture works only on the plane.
$f(x) = 2x + 1$ from $\mathbb{R}$ to $\mathbb{R}$. Injective: suppose $2a + 1 = 2b + 1$; subtracting and halving gives $a = b$.
Assume equal outputs, derive equal inputs.
Surjective: let $y$ be any real. Solving $2a + 1 = y$ gives $a = (y-1)/2$, which is a real number, so it is in the domain.
Solve for the input, and check it is in the domain.
Both, so $f$ is a bijection — and step two has already written the inverse, $f^{-1}(y) = (y-1)/2$. A surjectivity proof that solves rather than argues always does.
The proof produces the inverse for free.
Let $f(n) = 2n$ from the whole numbers to the even whole numbers. Injective: $2a = 2b$ gives $a = b$.
One line.
Surjective onto the evens: any even number is $2n$ for some whole $n$, and that $n$ is in the domain.
Solve for the input.
So the whole numbers and the even numbers can be paired off exactly, and there are as many of one as the other. This is impossible for finite sets, and for infinite ones it is simply what same size means.
The definition is the bijection, not the containment.
Injective: suppose $a^2 = b^2$ with $a$ and $b$ whole numbers. Then $a = b$, because a whole number is not negative and squaring is one-to-one there.
The domain is doing the work — on the integers this would fail.
Surjective: is every whole number a square? $2$ is not.
One unreached target settles it.
So injective and not surjective. Change the codomain to the perfect squares and the same rule becomes a bijection — a reminder that the two questions are about the function together with its domain and codomain, and not about the formula.
Take $f(x) = 2x + 1$ from the reals to the reals. For each property write $1$ if it holds and $0$ if it does not.
| $1$ for yes, $0$ for no | |
|---|---|
| Injective (one-to-one) | |
| Surjective (onto) |
$|A| = 3$ and $|B| = 2$. How many functions are there from $A$ to $B$?
Answer:
Match each function to the kind it is.
| One-to-one, but not onto | Both — a bijection | Neither one-to-one nor onto | Onto, but not one-to-one | |
|---|---|---|---|---|
| $f(n) = 2n$ from the integers to the integers | ||||
| $f(x) = x^3$ from the reals to the reals | ||||
| $f(x) = x^2$ from the reals to the reals | ||||
| $f(n) = \lfloor n/2 \rfloor$ from the whole numbers to the whole numbers |
$|A| = 3$ and $|B| = 4$. How many **injective** functions are there from $A$ to $B$?
Answer:
Let $f(x) = 3x$, a bijection from the reals to the reals. Where does $f$ send the interval $[1, 4)$?
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Take $f(x) = x^3$ from the reals to the reals. For each property write $1$ if it holds and $0$ if it does not.
| $1$ for yes, $0$ for no | |
|---|---|
| Injective (one-to-one) | |
| Surjective (onto) |
You can decide and prove which kind a function is, and count how many there are between two finite sets. Say in your own words why the domain and codomain are part of the question, and what a bijection buys that an injection alone does not. Next: counting itself, and the two rules everything else is built from.
10. Your turn: is $f(n) = n^2$ from the whole numbers to the whole numbers injective? Surjective?, step 3