PG6.2 Injective, surjective and bijective maps

Simulate

Check the claim with numbers

A map $f: X \to Y$ gives each element of the set $X$ one element of the set $Y$ . Lesson 1.1.3 asked when a function can be run backwards. That depends on two properties: no two inputs share an output, and every element of $Y$ is an output.

On small sets every map can be listed. A map from $\{0, 1, 2\}$ to $\{0, 1\}$ is a tuple of three outputs, such as $(1, 0, 1)$ . The cell counts the maps between sets of sizes $m$ and $n$ , and how many have each property.

from itertools import product def maps(m, n): return list(product(range(n), repeat=m)) def injective(f): return len(set(f)) == len(f) def surjective(f, n): return set(f) == set(range(n)) for m, n in [(2, 3), (3, 3), (3, 2)]: F = maps(m, n) inj = sum(injective(f) for f in F) sur = sum(surjective(f, n) for f in F) both = sum(injective(f) and surjective(f, n) for f in F) print(m, n, len(F), inj, sur, both)

⌘/Ctrl + Enter runs the cell

From 2 elements to 3, 6 of the 9 maps keep outputs apart, but none reaches all 3 elements. From 3 to 2, 6 of the 8 maps reach both elements, but none keeps 3 outputs apart. Only between sets of the same size, 3 and 3, do 6 maps have both properties.

Now chain two maps. The cell tries every $f$ from a 2-element set to a 3-element set, with every $g$ from there to a 4-element set.

from itertools import product def maps(m, n): return list(product(range(n), repeat=m)) def injective(f): return len(set(f)) == len(f) def compose(g, f): return tuple(g[f[x]] for x in range(len(f))) F, G = maps(2, 3), maps(3, 4) print(len(F) * len(G)) print(all(injective(compose(g, f)) for f in F for g in G if injective(f) and injective(g))) print(sum(1 for f in F for g in G if injective(compose(g, f)) and not injective(g)))

⌘/Ctrl + Enter runs the cell

In all 576 pairs, $g \circ f$ keeps outputs apart whenever $f$ and $g$ both do. The last line shows the reverse fails: in 144 pairs $g \circ f$ keeps them apart, but $g$ does not.

Conjecture

f: X \to Y

Every pair of maps between three small sets. The proof must work for every set, finite or not.

Three properties of a map

The two properties have names. A map with both has an inverse, as lesson 1.1.3 found with the horizontal line test.

Rule: Injective, surjective, bijective

\begin{gathered} \text{injective:} \\ f(a) = f(a') \Rightarrow a = a' \\[4pt] \text{surjective:} \\ \text{each } y \in Y \text{ equals some } f(x) \\[4pt] \text{bijective: both} \end{gathered}

Injective (one-to-one, as in lesson 1.1.3): different inputs give different outputs. Surjective (onto): every element of $Y$ is an output. A bijective map, a bijection, pairs off $X$ and $Y$ exactly, so it has an inverse $f^{-1}: Y \to X$ .

To prove that a map is injective, take two inputs with the same output and show they are equal. To prove it is surjective, take any $y \in Y$ and find an input that gives it. Composition is as in lesson 1.1.3: $(g \circ f)(x) = g\big(f(x)\big)$ .

Format 1

Reorder the steps

Here is the proof of the claim, with its lines shuffled. Put them in order with the arrows, or drag a line by its handle.

So inputs of $g \circ f$ with the same output are equal: $g \circ f$ is injective.
By the meaning of composition, that says $g\big(f(a)\big) = g\big(f(a')\big)$ .
The map $f$ is injective, so $f(a) = f(a')$ gives $a = a'$ .
Suppose $f$ and $g$ are injective, and take any $a, a' \in X$ with $(g \circ f)(a) = (g \circ f)(a')$ .
The map $g$ is injective, and $f(a)$ and $f(a')$ have the same output under $g$ , so $f(a) = f(a')$ .

Simulate

Is this map injective?

Take $f(x) = x^2 + 2x$ on all real numbers. The cell evaluates it at every quarter from $-5$ to 5 with exact fractions, and looks for two inputs with the same output.

from fractions import Fraction def f(x): return x * x + 2 * x grid = [Fraction(k, 4) for k in range(-20, 21)] seen, pairs = {}, [] for x in grid: y = f(x) if y in seen: pairs.append((str(seen[y]), str(x))) else: seen[y] = x print(len(grid), len(pairs), pairs[:3]) right = [x for x in grid if x >= -1] print(len(right), len({f(x) for x in right}) == len(right)) print(f(0), f(-2), f(1), f(-3))

⌘/Ctrl + Enter runs the cell

Of the 41 inputs, 16 share an output with an earlier one: $f(-\frac{5}{4}) = f(-\frac{3}{4})$ , for example, and $f(0) = f(-2) = 0$ . Kept to $x \ge -1$ , the 25 inputs give 25 different outputs.

Conjecture

f(x) = x^2 + 2x

A grid of 41 points. The collisions come in pairs placed evenly about $-1$ , which the algebra should explain.

Format 3

Find the error

A proof that $f(x) = x^2 + 2x$ is injective on all of $\mathbb{R}$ , which the simulation contradicts. One line loses part of the truth. Select it.

Simulate

Chains of surjective maps

Now the other property. The cell tries every $f$ from a 4-element set onto a 3-element set, with every $g$ from there to a 2-element set.

from itertools import product def maps(m, n): return list(product(range(n), repeat=m)) def surjective(f, n): return set(f) == set(range(n)) def compose(g, f): return tuple(g[f[x]] for x in range(len(f))) F, G = maps(4, 3), maps(3, 2) print(len(F) * len(G)) print(all(surjective(compose(g, f), 2) for f in F for g in G if surjective(f, 3) and surjective(g, 2))) print(sum(1 for f in F for g in G if surjective(compose(g, f), 2) and not surjective(f, 3)))

⌘/Ctrl + Enter runs the cell

In all 648 pairs, $g \circ f$ reaches every element whenever $f$ and $g$ both do. Again the reverse fails: in 168 pairs $g \circ f$ reaches every element, but $f$ does not.

Conjecture

f: X \to Y

Every pair of maps between three small sets, as before. With the first claim, this makes a chain of two bijections a bijection.

Format 4

Write it

Prove that if $f: X \to Y$ and $g: Y \to Z$ are surjective, then $g \circ f$ is surjective. Then explain why a chain of two bijections is a bijection.

Your proof

Saved in this browser as you type.

Write your own first: a proof you have tried to write teaches far more than one you only read.

Lesson PG6.3 uses bijections to compare the sizes of infinite sets.

f: X \to Y

Injective, surjective and bijective maps

Check the claim with numbers

Three properties of a map

Rule: Injective, surjective, bijective

Reorder the steps

Is this map injective?

Find the error

Chains of surjective maps

Write it

Summary card

Free further reading