Functions - 3
Cardinality of Finite Sets and Functions
The cardinality of a finite set $S$ is the number of elements in $S$.
A bijection $f:S\rightarrow\{1,\ldots,n\}$. This means that there are as many elements in the set that $S$ maps to as there are in $S$.
For finite sets $A$ and $B$:
- $\vert A\vert \geq\vert B\vert \Rightarrow$ there is a surjective function from $A$ to $B$.
- $\vert A\vert \leq\vert B\vert \Rightarrow$ there is an injective function from $A$ to $B$.
- $\vert A\vert =\vert B\vert \Rightarrow$ there is a bijection function from $A$ to $B$.
graph TD
subgraph A
a[ ]
b[ ]
c[ ]
end
subgraph n1[n]
1
2
n
end
subgraph B
d[ ]
e[ ]
f[ ]
end
a --> 1
b --> 2
c --> n
d --> 1
e --> 2
f --> n
From the graph as $\vert A\vert =n=\vert B\vert$ then we can deduce that $g^{-1}\circ f$.
- Bijective means one to one.
- Surjective means many to one.
- Injective means one to many.
The Pigeonhole Principle
Let $f:A\rightarrow B$ be a function where $A$ and $B$ are finite sets.
The pigeonhole principle states that if $\vert A\vert >\vert B\vert$ then at least one value of $f$ occurs more than once.
In other words, we have $f(a)=f(b)$ for some distinct elements $a,b$ of $A$.
The principle is if $(N+1)$ pigeons occupy $N$ holes, then some hole must have at least 2 pigeons.
Example 1
There are 15 people on a bus. Show that at least two of them have a birthday in the same month of the year.
Proof
Let $A$ be the set of all people on the bus. $\vert A\vert =15$
Let $B$ be the set of months. $\vert B\vert =12$
$f$ associates the month in which a person has been born with that person.
By the pigeonhole principle (PHP), at least two of them have a birthday on the same day.
Example 2
How many different surnames must appear in a telephone directory to guarantee that at least two of the surnames begin with the same letter of the alphabet and end with the same letter of the alphabet?
If we are solving this by the pigeonhole principle then the set $A$ of names must have same cardinality as $\vert B\vert +1$ where $B$ is the set of all pairs of letters.
$\vert B\vert =26^2$
Therefore
$\vert B\vert +1=26^2+1$
Example 3
Five number are selected from the numbers $1,2,3,4,5,6,7$ and $8$. Show that there will always be two of the numbers that sum to $9$.
Proof
graph LR
subgraph B
1[1,8]
2[2,7]
3[3,6]
4[4,5]
end
subgraph A
x1
x2
x3
x4
x5
end
x1 --> 1
x2 --> 2
x3 --> 3
x4 --> 4
x5 --> 1
$\vert A\vert =5$ and $\vert B\vert =4$. If each element with $x_n$ maps to the pair which contains its digit then there must be a pair with more than one mapping. This is to say that the two sets maps via a surjective function.
This proves that there will always be one pair in the list that sums to 9.