SP20:Lecture 8 Cardinality
'Jectivity and inverses
- injections have left inverses, and functions with left inverses are injective
- surjections have right inverses, and functions with right inverses are surjective
- bijections have two-sided inverses, and functions with two-sided inverses are bijective
We went through the first two of these claims in detail in this lecture. The proofs of the other two are similar.
Although we haven't proven them, you may use any of these claims without proof on the homework. I encourage you to prove them as excercises.
Injections have left inverses
We want to construct an inverse for ; obviously such a function must map to 1 and to 2. We must also define (so that is a function, i.e. total). So we'll just arbitrarily choose a value to map it to (say, 2).
Note that this wouldn't work if injective. For example,was not
Here is the general proof:
Let be given by
so, which is the definition of a left inverse.
Functions with left inverses are injections
You may have noticed that in our examples of injections , there are always at least as many elements in as there are in . Similarly, surjections always map to smaller sets, and bijections map to sets of the same size.
The cardinality of a set (written ) is the size of the set. However, for the time being, we will not use this definition by itself. Doing so will encourage you to write proofs about cardinality that don't apply to infinite sets.
Note that it is dangerous to redefine symbols like ≤ and ≥! People expect that these relations work the same way they do for numbers, but it is not a-priori obvious that they do. For example, you might expect that
- |A| ≤ |A|
- if |A| ≤ |B| and |B| ≤ |C| then |A| ≤ |C|
- if |A| ≤ |B| then |B| ≥ |A|
- if |A| ≤ |B| and |A| ≥ |B| then |A| = |B|
- if A ⊆ B then |A| ≤ |B|
Luckily, these are all true (most will be proved on the homework), but it's important to note that they need to be proved!