Let ~{S_n} &subset. &naturals., _ ~{S_n} = \{ ~k &in. &naturals. | ~k &le. ~n \}
A set ~B is #~{finite} (#~{of cardinality n}) if there is a bijection _ ~{S_n} ~B.
~B is #~{enumerable} if there is a bijection _ &naturals. ~B.
~B is #~{countable} if there is a surjection _ &naturals. --> ~B.
Clearly any finite or enumerable set is countable. Conversely any countable set is either finite or enumerable.
#{Lemma}: _ ~B countable _ <=> _ &exist. sequence \{ ~{b_i} \}_{~i &in. &naturals.} &subseteq. ~B, _ such that ~B = \{ ~{b_i} \}.
Proof:
#{Lemma}: _ Any subset of ~B enumerable &imply. ~B is not finite
Proof:
| &naturals. | zDgrmHzDbl{ _ ,~f} | _ ~A | zDgrmRight{&subseteq.,~g} | _ ~B | zDgrmHzDbl{ _ ,~h} | _ ~S_~n |
~g _ is the "inclusion" function which is injective. _ Suppose now that _ ~f _ and _ ~h _ are bijective, _ then
_ _ _ _ im (~h &comp. ~g) _ &subseteq. _ ~{S_n}, _ _ => _ _ im (~h &comp. ~g) = ~{S_k} , _ some ~k =< ~n
so (~h &comp. ~g) restricted to ~{S_k} is bijective, _ => _ ~A is finite - contradiction!
&naturals. # &naturals. is enumarable.
Consider the mapping &naturals. --> &naturals. # &naturals. given by associating a number to each cell of &naturals. # &naturals. diagonally:
|
array{ ^1 _ {(1,1)} _ , ^2 _ {(1,2)} _ , ^4 _ {(1,3)} _ , ^7 _ {(1,4)} _ / ^3 _ {(2,1)} _ , ^5 _ {(2,2)} _ , ^8 _ {(2,3)} _ , ... / ^6 _ {(3,1)} _ , ^9 _ {(3,2)} _ , ... , ... / ^{10} _ {(4,1)} _ , ... , ... , ... } |
This is clearly injective and surjective. |
It follows that the rational numbers are enumerable, by considering the composition of the above mapping with _ &naturals. # &naturals. --> Q _ given by (~a,~b) -> [~a,~b], where [~a,~b] is the equivalence class in Q containing ~a/~b.
This is a surjective but not bijective (e.g. 1 -> 1/1, and 5 -> 2/2, both of which are the same rational). However there is a bijection from &naturals. to a subset of Q given by ~n -> ~n/1. So as Q has an enumerable subset it must itself be enumerable.
The real numbers are not countable, in fact the interval [0,1] is not countable.
Proof:
Let &set. ~s_~n &xset. be a sequence in [0,1]. Divide the interval in three:
_ _ _ _ _ _ I_1 _ = _ [ 0 , 1 ] _ = _ [ 0 , 1/3 ] &union. [ 1/3 , 2/3 ] &union. [ 2/3 , 1 ]
and choose an interval, I_2 say, which does not contain ~s_1 . _ Similarly divide this interval in three and choose one, I_3 say, that does not contain ~s_2, and so on.
In this way we produce a sequence _ &set. I_~n &xset. _ of closed intervals satisfying the conditions of the nested interval theorem .
&therefore. &exist. ~x &in. I_~n _ &forall. ~n , _ ~x &nin. &set. ~s_~n &xset. , _ since ~s_~n &nin. I_~n for any ~n. _ So by cardinality result above, [0,1] and therefore &reals. are not countable.
An _ #~{algebraic number} _ is a solution of an equation (of some #~{degree} ~n):
_ _ _ _ _ ~x^~n + ~r_1~x^{~n - 1} + ... + ~r_~n = 0, _ _ _ where _ ~r_1 ... ~r_~n &in. Q
The algebraic numbers are countable, since there are a countable number of degrees, and for each degree there are a countable number of coefficients _ ~r_~n _ since these are rational, and as a countable union of countables sets is countable (not proved here) this proves the assertion.
The square root of 2 is an algebraic number, being the root of _ ~x^2 - 2 = 0.
A real number which is not algebraic is called a _ #~{trancendental number}.
As &reals. is inummerable but the algebraic numbers are countable, there must be uncountably many trancendental numbers.