Sunday, 19 July 2015

Proving uncountability without diagonalization

In this post, I propose a proof of the uncountability of the set of real numbers without using the famous diagonalization method of Georg Cantor. My proof is based on the Church-Turing thesis which states that any computable operation may be computed or simulated by a Turing Machine. So, if a set of mathematical objects is countable a counting operation may be performed and there is a Turing Machine that may compute it.

Definition. Let S be an ordered set of discrete objects. If S is countable then there is Turing Machine M which on input of the descriptions of objects a and b it outputs c which is a representation of the number of elements in S between objects a and b.

If we may count the elements between a and b (or else the distance of a and b in S) then we may count the whole set, as a and b may be any objects. This definition avoids a direct connection of the set N of natural numbers to S, so it differs from diagonalization, yet as I show below it reaches the same conclusions on natural, rational and real numbers. Output c has to be a number and not the symbol of infinity or anything similar, otherwise we cannot consider it as a counting result. First let’s test this definition on natural and rational numbers.

Theorem 1. Set N of natural numbers and set Q or rational numbers are countable.

Proof for N. Set N may be defined as an ordered set of linear structure. For every i we place in the i-th place of N number i. Let a and b be the representations of two natural numbers where a represents a smaller value than b and M a TM that computes their distance. In order to make the presentation more simple and intuitive and without loss of generality, let M be a 2-tape machine and a, b and c be represented in unary numeral system. Then we print a in tape-1 and b in tape-2. For any “1” printed in tape-1 M erases one “1” that is printed in tape-2. Finally a representation of c is left in tape-2 and this is the output.

For instance, on a = 8 and b = 13 we print
tape-1 : #11111111######
tape-2 : #1111111111111#
After running the configuration of M we get
tape-1 : #11111111######
tape-2 : #11111#########

Proof for Q. Let’s first define Q as an ordered set. It is known that Q may be defined as the Cartesian product of sets X and Y, where X and Y are equal to N / {0}. For every ordered pair (x, y) of the product there is corresponding number q which is in Q and stands that q = y / x. Using this definition we may create an ordered set of linear structure equivalent to Q.
Set Q may be structured as an ordered set of subsets. Initially we place numbers “0” and “1 /1”, then for every i > 2 we place in the i-th place of the set the subset of Q that for all its elements stands x+y=i. By placing in ascending order the elements within each subset we create an ordered set of linear structure with all the elements of Q. On this procedure we end up with a representation of Q that is commonly used in literature.
On input of the descriptions of a and b, TM M using the above procedure creates the ordered subset of Q that contains a and b and then computes their distance by simply counting the elements between them one by one.
The ordered set of linear structure that is subset of Q and contains a and b is computable as it may be constructed algorithmically as shown above and is finite as I will show next.
Let a=y1/x1 and b=y2/x2, then between a and b there is a finite number of subsets d= (x2+y2)-(x1+y1). For each subset stands that i=x+y and is finite as there is a finite number of combinations that may generate i given that i, x, y belong in N.

Cartesian product

1/1   1/2   1/3   1/4 ……
2/1   2/2   2/3   2/4 ……
3/1   3/2   3/3   3/4 ……
4/1   4/2   4/3   4/4 ……

Order of elements

 1       2       4       7  ……
 3       5       8      11 ……
 6       9      12     14 ……
10     13     15     16 ……

Q as set of subsets

(0), (1/1), (1/2, 2/1), (1/3, 2/2, 3/1), (1/4, 2/3, 3/2, 4/1), (… 2/4, 3/3, 4/2 …), (… 3/4, 4/3 …), (… 4/4 …)

Q as an ordered set of linear structure

0, 1/1, 1/2, 2/1, 1/3, 2/2, 3/1, 1/4, 2/3, 3/2, 4/1, …, 2/4, 3/3, 4/2, …, 3/4, 4/3, …, 4/4 …

Theorem 2. The set R of real numbers is uncountable.

Proof. It is known that there is no algorithmic procedure which may produce the numbers in R. That is because most of numbers in R are uncomputable. 
Let's consider a description d for the numbers in R so that they may be represented in TM M. If there is procedure implemented in M that structures R as an ordered set then M computes uncomputable numbers which is a contradiction. As a result R may not be structured as an ordered set and is not countable by M.