# 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: 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:-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.