A countably infinite set is a set with the cardinality of aleph-null, or the cardinality of the set of all natural numbers N. In set theory, given a and b that are cardinalities representing some sets A and B, respectively, an order relation a ≤ b exists iff there exists an injection f: A → B. Hence a and b are eqivalent iff there exists injections going both ways. A result from set theory states that such is the case if and only if there exists a bijection between the two sets. Textbooks may simply cut to the chase and state the existance of a bijection as the definition of equivalence in size of two sets. I will show two proofs, one showing the existance of an injection for each direction A → B, B → A, and in another proof, a bijection between the two sets. But first, a useful result is the existance of a bijection between N and N × N.


A bijection exists from N × N to N.

Lemma proof

A bijection from N × N to N is f(u, v) = u + (u + v + 1)(u + v) / 2. This mapping can be represented in a grid:
       0  1  2  3  ...
  0 |  0  2  5  9  ...
V 1 |  1  4  8  ...
  2 |  3  7
  3 |  6  :
  4 |  :  :
  5 |  :
Every entry is assigned a unique index. The indexing goes diagonally upwards repeatedly starting from the 0-th column. f has the properties
  1. f(u + 1, v - 1) = 1 + f(u, v) for v > 0, and
  2. f(0, u + 1) = 1 + f(u, v) for v = 0.
Therefore every (u, v) has a succsessor (u', v') such that f(u', v') = 1 + f(u, v). This implies surjectivity. f defined on the domain Sn = { (u, v) ∈ N × N : n = u + v} is injective because of (a). Also from (a) we get f(0, u + v) ≤ f(u, v) ≤ f(u + v, 0). This fact and (b) implies an element from Sn and an element from Sm (n != m) have different values of f. The disjoint union of all Sn's is N × N, hence f injective also.

Proof 1: an injection exists for each direction

The identity is an injection NQ. Define a function h: QN. For every q ∈ Q, choose a representation in the form a / b where a is an integer, and b is a positive integer. Then define h(q) = 2 * f(a, b) for q nonnegative, and h(q) = 1 + 2 * f(-a, b) for q negative. Different rationals do not have the same representation in a / b form. Therefore h is injective.

Proof 2: a bijection exists

Define a sequence {an} of rationals as such: for even terms, an = a / (b + 1) where a and b are from (a, b) = f-1(n/2). For odd terms, an = -an+1. A rational has the form a / b where a is an integer and b is a positive integer, hence it appears in the sequence. Now define h(k) = ank, a subsequence that eliminates all duplicate rationals. The set of all h(k)'s is the set of all rationals, and no h(k)'s are the same. Hence h is a bijection from N to Q.

Log in or register to write something here or to contact authors.