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.
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:
U
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
-
f(u + 1, v - 1) = 1 + f(u, v) for v > 0, and
-
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 S
n = { (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 S
n and an element from S
m (n != m) have different values of f. The
disjoint union of all S
n's is
N ×
N, hence f
injective also.
Proof 1: an injection exists for each direction
The identity is an injection
N →
Q.
Define a function h:
Q →
N.
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 {a
n} of rationals as such: for even terms, a
n = a / (b + 1) where a and b are from (a, b) = f
-1(n/2). For odd terms,
a
n = -a
n+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) = a
nk, 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.