Mappings

Try this

Give every element of $A$ exactly one arrow and “A mapping?” turns to ✓. What happens if some element has no arrow, or (switch on “Allow several arrows”) has two?
If some element of $B$ receives no arrow at all, is it still a mapping? What if two $a$ 's hit the same $b$ ?
Set $∣ A ∣$ to $3$ and $∣ B ∣$ to $2$ and try to draw an injection. Can you? Now swap the sizes and try to draw a surjection.
Look at the counting panel: when $∣ A ∣ = ∣ B ∣$ , how are the numbers of injections, surjections and bijections related?

Let $A$ and $B$ be two sets. If, under some rule of correspondence $f$ , every element $x$ of $A$ corresponds to a unique element $y$ of $B$ , we say $f$ is a mapping from $A$ to $B$ , and write $f : A \to B$ . Then $y = f (x)$ is called the image of $x$ , and $x$ a preimage of $y$ . In an arrow diagram this is a single sentence:

Every element of A fires exactly one arrow.

Now look at where the arrows land. If every element of $B$ is hit at most once, the mapping is an injection; if every element of $B$ is hit at least once, it is a surjection; if both, it is a bijection (a one-to-one correspondence).

Predict first

$A$ has $2$ elements and $B$ has $3$ . How many different mappings are there from $A$ to $B$ ?

6

8

9

5

Choose an answer first; then you can see the result.

Why: counting mappings means counting choices

Example: A = {a₁, a₂, a₃}, B = {b₁, b₂}

Step 1 / 5

a₁ chooses first
A mapping just picks one image for each element of $A$ . $a_{1}$ can pick $b_{1}$ or $b_{2}$ : $2$ choices.

$2$
a₂ and a₃ choose too
Injections: none at all
Surjections: remove the ones that miss
The general formulas

The same reasoning gives two facts you will use again and again: if there is an injection from $A$ to $B$ , then $∣ A ∣ \leq ∣ B ∣$ ; if there is a surjection from $A$ to $B$ , then $∣ A ∣ \geq ∣ B ∣$ . So to prove that two finite sets have the same number of elements, it is enough to build a bijection between them. This is where “correspondence and pairing” starts.

For example, every subset $S$ of $A = {a_{1}, a_{2}, a_{3}}$ corresponds to a mapping $f : A \to {0, 1}$ : $f (a) = 1$ if $a \in S$ , and $f (a) = 0$ otherwise. This is a one-to-one correspondence between subsets and mappings, so $A$ has $2^{3} = 8$ subsets.

Read

b_{1}

0

and

b_{2}

1

: this diagram is the subset

{a_{1}, a_{3}}

. Draw the mapping for the subset

{a_{2}}

Remove one condition

Break it

Counterexample lab: remove one condition

Conclusion: if $f : A \to B$ is an injection, it is also a surjection

$∣ A ∣ = ∣ B ∣ = 3$ . Draw an injection: three arrows land on three different elements, and $B$ has only three elements, so every one of them is hit. It is automatically a surjection.

Practice

Exercise 1Basic

$A = {1, 2, 3, 4}$ and $B = {0, 1}$ . How many mappings are there from $A$ to $B$ ?

Exercise 2Basic

$∣ A ∣ = 3$ and $∣ B ∣ = 5$ . How many injections are there from $A$ to $B$ ?

Exercise 3Advanced

$∣ A ∣ = 4$ and $∣ B ∣ = 3$ . How many surjections are there from $A$ to $B$ ?

Exercise 4Challenge

Let $A = {1, 2, 3}$ . How many mappings $f : A \to A$ satisfy $f (f (x)) = f (x)$ for every $x \in A$ ?

Try this

Why: counting mappings means counting choices

Example: A = {a₁, a₂, a₃}, B = {b₁, b₂}

Remove one condition

Counterexample lab: remove one condition

Practice

Mistake Museum · Exhibits from this stop

Base and exponent swapped when counting mappings

Checking “is there an arrow?” but not “how many arrows?”