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**of natural numbers to***N**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

**of natural numbers and set**

*N***or rational numbers are countable.**

*Q**Proof for*. Set

**N***may be defined as an ordered set of linear structure. For every*

**N***i*we place in the

*i*-th place of

*number*

**N***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*. Let’s first define

**Q***as an ordered set. It is known that*

**Q***may be defined as the Cartesian product of sets*

**Q***X*and

*Y*, where

*X*and

*Y*are equal to

*/ {0}. For every ordered pair (*

**N***x*,

*y*) of the product there is corresponding number

*q*which is in

*and stands that*

**Q***q*=

*y*/

*x*. Using this definition we may create an ordered set of linear structure equivalent to

*.*

**Q**
Set

*may be structured as an ordered set of subsets. Initially we place numbers “0” and “1 /1”, then for every***Q***i*> 2 we place in the*i*-th place of the set the subset of*that for all its elements stands***Q***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*. On this procedure we end up with a representation of***Q***that is commonly used in literature.***Q**
On input of the descriptions of

*a*and*b*, TM*M*using the above procedure creates the ordered subset of*that contains***Q***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

**and contains***Q**a*and*b*is computable as it may be constructed algorithmically as shown above and is finite as I will show next.
Let

*a*=*/**y*1*x*1 and*b*=*y*2/*x*2, then between*a*and*b*there is a finite number of subsets*d*= (*x*2+*y*2)-(*x*1+*y*1). 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 ……

………………………...

**as set of subsets**

*Q*(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 …)

**as an ordered set of linear structure**

*Q*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

**of real numbers is uncountable.**

*R**Proof*. It is known that there is no algorithmic procedure which may produce the numbers in

*. That is because most of numbers in*

**R***are uncomputable.*

**R**
Let's consider a description

*d*for the numbers in**so that they may be represented in TM***R**M*. If there is procedure implemented in*M*that structures**as an ordered set then***R**M*computes uncomputable numbers which is a contradiction. As a result**may not be structured as an ordered set and is not countable by M.***R*
## No comments:

## Post a Comment