My Math Forum > Math I don't see the significance of Cantor's diagonal argument

 Math General Math Forum - For general math related discussion and news

January 10th, 2017, 11:18 PM   #11
Senior Member

Joined: Aug 2012

Posts: 1,681
Thanks: 437

Quote:
 Originally Posted by Mathbound Thanks, but I just watched a video from a university lecture, and a student had a similar issue. The professor said that reals can be infinitely long decimals. So I suppose you could never exhaust an irrational like pi with n still as a natural number. Is that what the argument is essentially about?
No but that is a very good point to bring up.

There IS a bijection between the natural numbers and the digits of any particular real number.

A number like $\pi - 3 = .14159 \dots$ (I'm subtracting $3$ just so all the digits are to the right of the decimal point for simplicity) can be thought of as a bijection between the set of natural numbers $1, 2, 3, \dots$ and the digit positions of $\pi - 3$. If you ask me for digit position $4$ I just start at the decimal point, count over to that digit position, and tell you that the digit in that position is "$5$".

In principle we can look up any digit position. If you ask me for the digit in position one million or one billion or one trillion, I just start at the decimal point and count that far over to find out the digit.

Conceptually it's like a lookup table or array in a computer program; except that the array has infinitely many cells, one for each natural number; and we can look up any cell of the array immediately. That's the conceptual model of standard math. Everything exists at once and is always available for use. That's one of the basic rules of the game. As you can see this is a highly abstract conceptual world we live in when we do math.

Now the Cantor diagonal argument assumes we have a list of real numbers written one below the other. Each row is the decimal representation of a single real number, with its infinitely many digits. In fact there are exactly countably many digits: one for each natural number. In fact the assignment of digits to digit positions IS the bijection, or one-to-one correspondence, that establishes that the set of digits is countably infinite.

So now we have a big array. Each row is the countably long list of digits of some real number. And we suppose we have a list of these infinitely long strings, from top to bottom. Then we diagonalize to produce an infinitely long string that can not possibly be any row of the array; because it differs from row $n$ in digit position $n$.

So no matter what list of reals we choose, it's always missing some number. This is in contrast to the situation with the rationals, where we CAN correspond each rational to a natural number. Of course not every proposed function works; but at least one does.

Countability is an existence condition. It says that some function between the naturals and the rationals is a bijection. That doesn't mean that every function is a bijection, as you noticed.

Last edited by Maschke; January 10th, 2017 at 11:25 PM.

January 11th, 2017, 05:11 AM   #12
Math Team

Joined: Dec 2013
From: Colombia

Posts: 7,118
Thanks: 2369

Math Focus: Mainly analysis and algebra
Quote:
 Originally Posted by Mathbound But you could guarantee it to be a rational depending on the rule, right?
No. That's why the procedure doesn't work on the rationals.

January 11th, 2017, 12:23 PM   #13
Member

Joined: Jun 2014
From: Alberta

Posts: 55
Thanks: 2

Quote:
 Originally Posted by Maschke No but that is a very good point to bring up. There IS a bijection between the natural numbers and the digits of any particular real number. A number like $\pi - 3 = .14159 \dots$ (I'm subtracting $3$ just so all the digits are to the right of the decimal point for simplicity) can be thought of as a bijection between the set of natural numbers $1, 2, 3, \dots$ and the digit positions of $\pi - 3$. If you ask me for digit position $4$ I just start at the decimal point, count over to that digit position, and tell you that the digit in that position is "$5$". In principle we can look up any digit position. If you ask me for the digit in position one million or one billion or one trillion, I just start at the decimal point and count that far over to find out the digit. Conceptually it's like a lookup table or array in a computer program; except that the array has infinitely many cells, one for each natural number; and we can look up any cell of the array immediately. That's the conceptual model of standard math. Everything exists at once and is always available for use. That's one of the basic rules of the game. As you can see this is a highly abstract conceptual world we live in when we do math. Now the Cantor diagonal argument assumes we have a list of real numbers written one below the other. Each row is the decimal representation of a single real number, with its infinitely many digits. In fact there are exactly countably many digits: one for each natural number. In fact the assignment of digits to digit positions IS the bijection, or one-to-one correspondence, that establishes that the set of digits is countably infinite. So now we have a big array. Each row is the countably long list of digits of some real number. And we suppose we have a list of these infinitely long strings, from top to bottom. Then we diagonalize to produce an infinitely long string that can not possibly be any row of the array; because it differs from row $n$ in digit position $n$. So no matter what list of reals we choose, it's always missing some number. This is in contrast to the situation with the rationals, where we CAN correspond each rational to a natural number. Of course not every proposed function works; but at least one does. Countability is an existence condition. It says that some function between the naturals and the rationals is a bijection. That doesn't mean that every function is a bijection, as you noticed.
Then would this bijection work for all real numbers between 1 and 0 to the naturals:

1 -> 0.1000 ...
2 -> 0.2000 ...
3 -> 0.3000 ...
4 -> 0.4000 ...
.
.
.
9 -> 0.9000 ...
11 -> 0.0100 ...
12 -> 0.0200 ...
.
.
.
19 -> 0.0900 ...
21 -> 0.1100 ...
22 -> 0.1200 ...
.
.
.
29 -> 0.1900 ...
31 -> 0.2100 ...
32 -> 0.2200 ...
.
.
.

Now if n can go to infinite, I can find you pi - 3, or any other number with some infinitely large n.

 January 11th, 2017, 12:34 PM #14 Math Team   Joined: Dec 2013 From: Colombia Posts: 7,118 Thanks: 2369 Math Focus: Mainly analysis and algebra No. Because every one of those decimals is of finite length and thus rational. Thanks from Mathbound
January 11th, 2017, 02:23 PM   #15
Member

Joined: Jun 2014
From: Alberta

Posts: 55
Thanks: 2

Quote:
 Originally Posted by v8archie No. Because every one of those decimals is of finite length and thus rational.
But like Maschke says, there would be a bijection between n and the decimal place of infinitely long decimal numbers. Couldn't we list all decimal places of, say, pi?

(so confused)

Last edited by Mathbound; January 11th, 2017 at 02:26 PM.

January 11th, 2017, 02:27 PM   #16
Senior Member

Joined: Aug 2012

Posts: 1,681
Thanks: 437

Quote:
 Originally Posted by Mathbound But like Maschke says, there would be a bijection between n and the decimal place of infinitely long decimal numbers. Couldn't we list all decimal places of, say, pi? (so confused)
Yes, we can list all of the decimal places of $\pi$.

But $\pi$ is only one single real number. We can't list ALL of them.

January 11th, 2017, 02:42 PM   #17
Member

Joined: Jun 2014
From: Alberta

Posts: 55
Thanks: 2

Quote:
 Originally Posted by Maschke Yes, we can list all of the decimal places of $\pi$. But $\pi$ is only one single real number. We can't list ALL of them.
Right, but there are n infinite elements of rationals between each natural number - and even between any 2 rational numbers between each natural number.

January 11th, 2017, 02:53 PM   #18
Senior Member

Joined: Aug 2012

Posts: 1,681
Thanks: 437

Quote:
 Originally Posted by Mathbound Right, but there are n infinite elements of rationals between each natural number - and even between any 2 rational numbers between each natural number.
The order properties of the reals aren't relevant to this discussion.

I don't see how your comment was in response to what I wrote.

Last edited by Maschke; January 11th, 2017 at 02:56 PM.

January 11th, 2017, 03:55 PM   #19
Member

Joined: Jun 2014
From: Alberta

Posts: 55
Thanks: 2

Quote:
 Originally Posted by Maschke The order properties of the reals aren't relevant to this discussion. I don't see how your comment was in response to what I wrote.
Because we can exhaust all decimal places for a number like pi - 3 using natural numbers (or aleph 0 elements), I don't see how my list a few posts above this post could leave out a real number.

Like, I do and I don't see. On one hand, the rule forces us to leave out a number. But on the other hand, my list gives every possible digit in every possible decimal place. It will eventually give all possible combinations of digits 0 to 9 in all decimal positions for real numbers between 0 and 1.

January 11th, 2017, 04:16 PM   #20
Senior Member

Joined: Aug 2012

Posts: 1,681
Thanks: 437

Quote:
 Originally Posted by Mathbound Because we can exhaust all decimal places for a number like pi - 3 using natural numbers (or aleph 0 elements), I don't see how my list a few posts above this post could leave out a real number. Like, I do and I don't see. On one hand, the rule forces us to leave out a number. But on the other hand, my list gives every possible digit in every possible decimal place. It will eventually give all possible combinations of digits 0 to 9 in all decimal positions for real numbers between 0 and 1.
Didn't v8archie explain that all your decimals have only finitely many nonzero digits, hence are rational? Where is .101010101010101010101... on your list?

 Tags argument, cantor, diagonal, significance

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post zylo Topology 59 May 21st, 2016 08:13 AM zylo Topology 12 March 24th, 2016 10:53 AM zylo Math 22 January 26th, 2016 09:05 PM mjcguest Applied Math 9 July 25th, 2013 08:22 AM netzweltler Applied Math 191 November 7th, 2010 02:39 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top