A Comment on Georg Cantor’s Diagonal Argument

In 1891, Georg Cantor proved that the real numbers are uncountable. His proof is based on the diagonal argument. Cantor considered the set T of all sequences of binary digits. Since the number of 0 and 1 in an infinite string is countable.

Let $s_1 =a_{11}a_{12}\ldots$ be a binary string. Generally $s_i=a_{ij}$ be a string. Put them in a matrix such that $s_1$ is first and $s_2$ is the second row. According to diagonal argument the row $d= a^c_{ii}$ where $a^c$ is the complement of $a$ . Then by construction, $d$ is not in the sequence.

Here it is assumed that matrix is $N\times N$ . In reality, the matrix is $N\times 2^N$ . Therefore the element $d$ does not exist in $N\times N$ . It exists in $N\times 2^N$ .

2 thoughts on “A Comment on Georg Cantor’s Diagonal Argument”

Add yours

JeffJo says:

October 1, 2024 at 7:23 pm

In 1875, Cantor proved that the real numbers were uncountable. In 1891, he proved that uncountable sets exist, without using irrational numbers. He EXPLICITLY SAID THIS. The array he used was NxN (I assume you meant Aleph0 where you said N; it doesn’t come through well here). He never assumed an array that was Nx(2^N). He proved that N rows were insufficient to contain all length-N binary strings. A later proof showed that there are 2^N of them.

LikeLike

Reply
1. Monologist says:
  
  October 1, 2024 at 8:48 pm
  
  Thank Jeff for the detailed comment. First from N I meant Aleph0. Cantor did not say an array of Nx2^N. This is my observation that one needs Nx 2^N. I have no question about uncountability of reals though. Other proofs may also exist which proves the uncountability.
  
  LikeLike
  
  Reply

Share this:

2 thoughts on “A Comment on Georg Cantor’s Diagonal Argument”

Add yours

Leave a reply to JeffJo Cancel reply