Question about diagonal argument

cragar

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.

HallsofIvy

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.

micromass

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.

cragar

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.

micromass

The same does not work with the rationals because the diagonal number is not guaranteed to be rational.

cragar

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.

micromass

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.

lurflurf

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.

lavinia

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.

Hurkyl

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.