Example:Cardinality of ℕ ⨯ ℕ

From CS2800 wiki

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).