FA18:Lecture 8 cardinality

From CS2800 wiki

We use 'jectivity to define cardinality.

Cardinality definitions

You may have noticed that in our examples of injections [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math], there are always at least as many elements in [math]B [/math] as there are in [math]A [/math]. 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 [math]A [/math] (written [math]|A| [/math]) 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.

If [math]A [/math] and [math]B [/math] are sets, then [math]|A| \href{/cs2800/wiki/index.php/%E2%89%A4}{≤} |B| [/math] means that there exists an injection [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math]
If [math]A [/math] and [math]B [/math] are sets, then [math]|A| \href{/cs2800/wiki/index.php/%E2%89%A5}{≥} |B| [/math] means that there exists a surjection [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math]
If [math]A [/math] and [math]B [/math] are sets, then [math]|A| \href{/cs2800/wiki/index.php/Equality_(cardinality)}{=} |B| [/math] means that there exists a bijection [math]f : A \href{/cs2800/wiki/index.php/%E2%86%92}{→} B [/math]

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

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.


ℕ ∪ {-1}

You might imagine the adding an element to a set makes it bigger. While this is true for finite sets, it is not true in general:

[math]│\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} \{-1\}│ \href{/cs2800/wiki/index.php/Equality_(cardinality)}{=} │\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}│ [/math]
Let [math]f : \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}\href{/cs2800/wiki/index.php/%E2%88%AA}{∪}\{-1\} [/math] be given by [math]f(n) := n-1 [/math].

I claim that [math]f [/math] is a bijection.

To see that [math]f [/math] is injective, choose arbitrary [math]x_1, x_2 [/math] in and assume [math]f(x_1) = f(x_2) [/math]. Then [math]x_1-1 = x_2-1 [/math] so [math]x_1 = x_2 [/math] as required.

To see that [math]f [/math] is surjective, choose an arbitrary [math]y \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math]. Let [math]x = y+1 [/math]. Since [math]y \geq -1 [/math] we have [math]x \geq 0 [/math] so [math]x \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math]. Moreover, [math]f(x) = x-1 = y [/math] as required.

Even naturals

You might expect that the set of even natural numbers is smaller than the set of all natural numbers. But in fact, funny things happen with infinite sets:

Let [math]X := \href{/cs2800/wiki/index.php/Set_comprehension}{\{2n} \href{/cs2800/wiki/index.php/%5Cmid}{\mid} n \href{/cs2800/wiki/index.php/%E2%88%88}{∈} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}\} [/math] be the set of even natural numbers. Then [math]│X│ \href{/cs2800/wiki/index.php/Equality_(cardinality)}{=} │ℕ│ [/math].
Proof: cardinality of evens
Let [math]f : X \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] be given by [math]f(2n) := n [/math]. [math]f [/math] is clearly a well-defined function, because every element of the domain is of the form [math]2n [/math] for exactly one [math]n [/math]. It is also clearly a bijection (details left as an exercise). Thus the evens and the naturals have the same cardinality.


You might think that adding an infinite number of numbers to the set of natural numbers might make it bigger. But in fact, this is not (necessarily) so. The integers have the same cardinality as the natural numbers:

[math]│\href{/cs2800/wiki/index.php/%E2%84%A4}{ℤ}│ \href{/cs2800/wiki/index.php/Equality_(cardinality)}{=} │\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}│ [/math]
Proof: cardinality of the integers
The following image clearly defines a bijection:


Details are left as an exercise.

ℕ ⨯ ℕ

You might imagine that the set of pairs of natural numbers is larger than the set of natural numbers, but in fact they can still be matched one-to-one:

[math]│\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php?title=%E2%A8%AF&action=edit&redlink=1}{⨯} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}│ \href{/cs2800/wiki/index.php/Equality_(cardinality)}{=} │\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}│ [/math]
Proof: │ℕ ⨯ ℕ│ = │ℕ│
Note: Although this proof creates a bijection by enumerating the elements on the diagonal, this technique is 'not' called diagonalization (which is used to prove that sets are uncountable). This often leads to confusion.

We wish to construct a bijection [math]f : \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php?title=%E2%A8%AF&action=edit&redlink=1}{⨯} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math].

We can draw a table containing all pairs of natural numbers:

0 1 2 [math]\cdots [/math]
0 (0,0) (0,1) (0,2) [math]\cdots [/math]
1 (1,0) (1,1) (1,2) [math]\cdots [/math]
2 (2,0) (2,1) (2,2) [math]\cdots [/math]
[math]\vdots [/math] [math]\ddots [/math]

Now, giving a function [math]f : \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php/%E2%86%92}{→} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} \href{/cs2800/wiki/index.php?title=%E2%A8%AF&action=edit&redlink=1}{⨯} \href{/cs2800/wiki/index.php/%E2%84%95}{ℕ} [/math] is the same as giving a method for iterating through this table (identifying the 0th element, the 1th element, etc.). [math]f [/math] will be a bijection if we enumerate each pair exactly once.

To do so, we will start in the upper left hand corner, and then enumerate each pair along each diagonal, starting in the lower left, and ending in the upper right. For example, the first few pairs would be:

n f(n)
0 (0,0)
1 (1,0)
2 (0,1)
3 (2,0)
4 (1,1)
5 (0,2)
6 (3,0)
7 (2,1)
8 (1,2)
9 (0,3)
10 (4,0)
[math]\cdots [/math] [math]\cdots [/math]

This pattern clearly hits each pair once, and doesn't hit any pair more than once, so it defines a bijection.

Note: I would consider this a complete and correct proof. It clearly defines a function, and explains why it is bijective. Some students have worried about the lack of clarity of the function.

To the address the former concern, we could write down a formula for this function. However, it is 'not' necessary to write down a formula for every function; indeed many functions do not have formulae at all. Rather, we must check that the function definition is unambiguous. A good way to reason about this informally is to ask "how would I go about computing f(73)?" If there is enough description to answer this question (and it will only give one answer!), the function is probably well defined.

If we wanted to provide more specificity on the bijectivity of the function, we could note that the function first lists every pair that sums to 0, then all pairs that sum to 1, and then all pairs that sum to 2, and so on. So a pair (a,b) will be on the (a+b)th diagonal (and will be the bth element of that diagonal).