Question about diagonal argument

  • Thread starter cragar
  • Start date
  • #1
2,552
3
I thought I understood cantors diagonal argument but then I started to rethink it.
Why couldn't i just line up all the decimal numbers with the the odd natural numbers.
Then when we create a new decimal that is on my list I will line it up with an even number because I haven't used any of those yet.
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,847
967
Yes, you could do that but you haven't proved anything that way. Cantor's diagonal proof does not produce one number that cannot be matched up, it produces an infinite number of them. You have not yet shown that all of those numbers, that are not matched to the odd numbers, can be matched with the even numbers. In fact, we know, from Cantor's proof, that they can't.
 
  • #3
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,129
3,298
Why couldn't i just line up all the decimal numbers with the the odd natural numbers.

Why do you think you can even do that?? You can't. That's the whole point of the diagonal argument, you can't line up all the decimal numbers with the odd natural numbers.

The diagonal argument is a proof by contradiction.
 
  • #4
2,552
3
im not saying you can line up all the decimals with the odd numbers , Im
just saying we will start with that, then the new number that you create that is not on
my list I will line that one up with an even number and the next decimal you line
up with the next even number. I could do that with the rational numbers
I could line up the naturals with the naturals and then create a rational that wasn't on my list but we know that the rationals are countable so it is not clear to me why the diagonal argument works now.
 
  • #5
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,129
3,298
The same does not work with the rationals because the diagonal number is not guaranteed to be rational.
 
  • #6
2,552
3
ok but it still isn't clear to me why the diagonal arguement works for the reals because I could just start to line them up with all the powers of 5 and then I would have all the
powers of primes to line up with the new numbers that you create that aren't on my list .
It just isn't clear to me.
 
  • #7
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,129
3,298
ok but it still isn't clear to me why the diagonal arguement works for the reals because I could just start to line them up with all the powers of 5 and then I would have all the
powers of primes to line up with the new numbers that you create that aren't on my list .
It just isn't clear to me.

So that way you won't find a contradiction.
But the usual way, you do find a contradiction.

It's not because you can't find a contradiction if you do something different, that the diagonal argument doesn't work.
 
  • #8
lurflurf
Homework Helper
2,440
138
First of is the fluff of requiring each number to be uniquely represented. Next given a countably infinite list it is always possible to produce a number not among them by choosing a feature of each listed number and not matching it. Imagine you have an infinite number of binary options for a sandwich (such as has and does not have). Given an infinite number of sandwiched we can always make a new one by switching one option on each sandwich.

like this
1 has egg
2 does not have mayo
3 does not have onion
4 has pickle
5 has worms
6 has orange peel
7 has yak cheese
8 does not have rhubarb
...


To make a new sandwich switch the option given for each existing sandwich. Since the sandwich differs from each existing sandwich in at least one option, it must be new.
 
  • #9
lavinia
Science Advisor
Gold Member
3,269
654
ok but it still isn't clear to me why the diagonal arguement works for the reals because I could just start to line them up with all the powers of 5 and then I would have all the
powers of primes to line up with the new numbers that you create that aren't on my list .
It just isn't clear to me.

You can't line up the reals with the powers of 5 or the odd numbers ot any subset of the integers. You are assuming what you want to disprove.
 
  • #10
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
ok but it still isn't clear to me why the diagonal arguement works for the reals because I could just start to line them up with all the powers of 5 and then I would have all the
powers of primes to line up with the new numbers that you create that aren't on my list .
It just isn't clear to me.
Once we've made infinitely many choices to fill up your list completely, I'm going to apply the diagonal argument again to produce yet another number not on your list.

Since your list is full, there's no room for you to add this new number to the list.
 

Related Threads on Question about diagonal argument

  • Last Post
Replies
5
Views
2K
Replies
19
Views
1K
Replies
22
Views
2K
Replies
36
Views
9K
Replies
12
Views
5K
Replies
5
Views
2K
Replies
4
Views
2K
  • Last Post
Replies
13
Views
5K
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
10
Views
2K
Top