Uncountability of Real Numbers (original) (raw)

The set of all real numbers is uncountable

We prove that it is false that there exists a 1-1 and "onto" function from |N to |R.

Notation Help

Suppose that /(x:N->R) [(/(y:-R) /(n:-N) x(n)=y) and /(n,m:-N) (x(n)=x(m) => n=m) ]. As soon as we reach an unavoidable contradiction, we have proved the uncountability of the set of all real numbers.

Let us construct recursively two sequences: a:N->R and b:N->R. a(1) := x(1) b(1) := x(min{i:-N|x(i)>a(1)}) a(n+1) := x(min{i:-N|a(n)<x(i)<b(n)}) b(n+1) := x(min{i:-N|a(n+1)<x(i)<b(n)})

Notice that /(n:-N) a(n)<a(n+1)<b(n+1)<b(n).

We will show that /(n,m:-N) a(n)<b(m). Let us argue by contradiction. Suppose there exist n,m:-N such that a(n)>=b(m). Then we have two possibilities: nm. If n<m then a(m)>a(n)>=b(m) hence a(m)>b(m) - contradiction. If n>m then b(n)<b(m)<=a(n) hence b(n)<a(n) - contradiction. Thus we have showed that /(n,m:-N) a(n)<b(m).

Let c = sup{a(n)|n:-N}. Notice that /(n:-N) a(n)<c.

We will show that /(n:-N) c<b(n). Let us argue by contradiction. Suppose there exists n:-N such that b(n)<=c. Then b(n+1)<b(n)<=c. Hence b(n+1)<c. By the definition of c, there exists m:-N such that b(n+1)<a(m) - contradiction. Thus we have showed that /(n:-N) c<b(n).

So we have /(n:-N) a(n)<c<b(n).

Recall that x has this property: /(y:-R) /(n:-N) x(n)=y. Hence there exists k:-N such that x(k)=c.

Let m = min{i:-N|/(n:-N) a(n)=x(i) and i>=k}. Notice that m>=k. Notice that there exists n:-N such that a(n)=x(m). Recall that a(n) = x(min{i:-N|a(n-1)<x(i)<b(n-1)}). Since x is 1-1, m = min{i:-N|a(n-1)<x(i)<b(n-1)}. Since x(k)=c, the natural number k satisfies a(n-1)<x(k)<b(n-1). Hence m<=k. Now we have m>=k and m<=k. Hence m=k. So a(n)=x(m)=x(k)=c. But a(n)<c. Unavoidable contradiction. End of proof.