

The set of all real numbers is uncountable
We prove that it is false that there exists a 11 and "onto" function from N to R.
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:Nx(i)>a(1)}) a(n+1) := x(min{i:Na(n)<x(i)<b(n)}) b(n+1) := x(min{i:Na(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: n<m or n>m. 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:Na(n1)<x(i)<b(n1)}). Since x is 11, m = min{i:Na(n1)<x(i)<b(n1)}. Since x(k)=c, the natural number k satisfies a(n1)<x(k)<b(n1). 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.