# SP20:Lecture 8 Cardinality

- Due to the snow day, I've recorded the lecture: lecture video
- slides

## Contents

# 'Jectivity and inverses

There is a connection between '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).

Then we plug left inverse and we see that and , so that is indeed a left inverse.

into the definition ofNote that this wouldn't work if injective. For example,

was notthen the ambiguous and thus not a function. If we chose one of the two (say ), then would give the wrong answer on the other ( would be , not ).

we constructed would need to map to both and ; if we did both then would beHere is the general proof:

Choose an arbitrary , , and an injection . We want to show that there exists a left inverse of .

Let element of (we know that such an element exists because ).

be anLet be given by

well defined, because if and then (since is injective). Thus the output of is unambiguous.

isTo see that left inverse of , choose an arbitrary ; we have

is a

so

, which is the definition of a left inverse.# Functions with left inverses are injections

# Cardinality definitions

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.

This insight lets us use functions to compare the sizes of sets in a way that applies to infinite sets as well as finite sets. We give some definitions here.

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.

Instead, we will only define relationships between the cardinalities of sets; these definitions come from the intuitive relationship between sizes and 'jectivity described above.

**≤**

**≥**

**Equality (cardinality)**

# Cardinality properties

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!

The last of these claims is called the Cantor-Schroeder-Bernstein theorem; the proof is much more difficult than the others.