Counting Ordered Pairs

The set of ordered pairs of elements of a countable set is countable.

Every integer is uniquely represented in the form 2^pq, where p ≥ 0, q ≥ 1, q an odd number.

For a pair (m, n) ∈ N×N, where N is the set of natural numbers, define

f(m, n) = 2^{m - 1}(2n - 1).

Function f is a bijection from N×N to N. (It is obviously 1-1. It is onto because of the sentence that opens the proof.)

That's it.

41169511

Supported by