Expand/Contract All

Countability

Page Contents

Cardinality Definitions

Finite Sets

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.

Enumerable Sets

~B is #~{enumerable} if there is a bijection _ &naturals. ~B.

Countable Sets

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

Cardinality Results

#{Lemma}: _ ~B countable _ <=> _ &exist. sequence \{ ~{b_i} \}_{~i &in. &naturals.} &subseteq. ~B, _ such that ~B = \{ ~{b_i} \}.

Proof:

  1. ~B countable then &exist. surjection _ &naturals. --> ~B . _ This defines the sequence.
  2. \{ ~{b_i} \}_{~i &in. &naturals.} _ such that ~B = \{ ~{b_i} \}. _ This defines a surjection _ &naturals. --> ~B , _ so ~B is countable.

#{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!

Cardinality of the Rationals

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

Cardinality of the Real Numbers

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.

 

Algebraic and Trancendental Numbers

Algebraic Numbers

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.

Trancendental Numbers

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.