Uncountable sets

[Steven G]

Here is what I accepted until the other day.

1) there are more than a countable number of real numbers between 0 and 1. The proof that I accepted until recently is that if you number all the numbers between 0 and 1 you can produce a number that is not on this list, showing that the numbers between 0 and 1 (and hence the real numbers) are uncountable. In fact I see how to produce an infinite countable number of numbers not on this list.
2) Hilbert’s countable infinite hotel— if the hotel is full we can find rooms for a finite number of guests, a countable infinite number of guests and even a countable infinite number of countable infinite number of guests.

I have no problem with number 2 at all. HoweverI now feel that based on number 2 that the argument in number 1 is pure garbage.

How can we always have room for any countable number of new guests while the hotel still has a countable number of rooms but when we add just one number to the list of real number between 0 and 1 causes this set to be uncountable?

What am I missing?!

 

[Otis]

if you number all the numbers between 0 and 1 you can produce a number that is not on this list

Hi Steven. If you number all the numbers between 0 and 1, then you have a list counting all of them. But, if you subsequently produce a number between 0 and 1 that is not on that list, then how could that list initially be described as a counting of "all" numbers between 0 and 1?



[imath]\;[/imath]

 

[Steven G]

Hi Steven. If you number all the numbers between 0 and 1, then you have a list counting all of them. But, if you subsequently produce a number between 0 and 1 that is not on that list, then how could that list initially be described as a counting of "all" numbers between 0 and 1?



[imath]\;[/imath]

Otis, I appreciate the time you took to read and reply to my post.
Yes, I know this proof. I’m suddenly not buying it! Of course I should accept it.
Again, here is my problem with buying it. If the HH (Hilbert hotel) is full—which means we can number the rooms with the counting numbers-and then find room for one more guest, the total number of rooms is countable. In the proof with the numbers from 0 to 1, we assume that the number of numbers from 0 to 1 is countable. Now when we find one number not on the list and add it to the list we now say that this list is not countable.
I see the difference in words between the two but don’t see exactly why the difference in the meaning is so great.
In HH we can always find a room for another guest and the number of rooms is countable.
In the proof of why the set of numbers between 0 and 1 we find a number that is not on the list so we conclude that this list is uncountable.
These two last statement are very similar to me.

 

[pka]

Steven, you may find this helpful.

 

[blamocur]

Here is what I accepted until the other day.

1) there are more than a countable number of real numbers between 0 and 1. The proof that I accepted until recently is that if you number all the numbers between 0 and 1 you can produce a number that is not on this list, showing that the numbers between 0 and 1 (and hence the real numbers) are uncountable. In fact I see how to produce an infinite countable number of numbers not on this list.
2) Hilbert’s countable infinite hotel— if the hotel is full we can find rooms for a finite number of guests, a countable infinite number of guests and even a countable infinite number of countable infinite number of guests.

I have no problem with number 2 at all. HoweverI now feel that based on number 2 that the argument in number 1 is pure garbage.

How can we always have room for any countable number of new guests while the hotel still has a countable number of rooms but when we add just one number to the list of real number between 0 and 1 causes this set to be uncountable?

What am I missing?!

The 1) is a typical proof by contradiction, i.e., "Let's assume that all real numbers are countable ...". And the proof does not make the set uncountable, just contradict the assumption that the list contains all real numbers.

It won't surprise me if you understood this without my post, but just in case...

 

[JeffM]

Steven

The Hilbert Hotel stipulates that we are dealing with what are assumed to be countable infinities. As blamocur said, Cantor's diagonal proof is a proof by contradiction that relies on his definition that two sets have equal numbers. We start by assuming that there is a one-to-one correspondence and then show that there cannot be a one-to-one correspondence. So we are not comparing countable sets.

I feel that Cantor's diagonal proof is a great feat of the human imagination and reasoning. What it convinces me of in addition is that everything dealing with infinite sets and irrational numbers is purely in the human mind and has nothing to do with physical reality.

 

[Otis]

"No other question has ever moved so profoundly the spirit of man; no other idea has so fruitfully stimulated his intellect; yet no other concept stands in greater need of clarification than that of the infinite." ~David Hilbert

[imath]\;[/imath]

 

[lex]

How can we always have room for any countable number of new guests while the hotel still has a countable number of rooms but when we add just one number to the list of real number between 0 and 1 causes this set to be uncountable?

As you are correctly pointing out, adding one number to the list does not suddenly make the list uncountable. The list is still countable. However adding one number to the list proves that the list was not a list of all the numbers between 0 and 1.

(We have shown that if there is a list of all the real numbers between 0 and 1 then it does not contain all the numbers between 0 and 1.
From this we can conclude, that there is no list of all the real numbers between 0 and 1.
So, yes, if you add a number to a list of numbers it still remains countable, but the list just isn't what we claimed it was - a list of all the real numbers between 0 and 1).

 

[Steven G]

As you are correctly pointing out, adding one number to the list does not suddenly make the list uncountable. The list is still countable. However adding one number to the list proves that the list was not a list of all the numbers between 0 and 1.

(We have shown that if there is a list of all the real numbers between 0 and 1 then it does not contain all the numbers between 0 and 1.
From this we can conclude, that there is no list of all the real numbers between 0 and 1.
So, yes, if you add a number to a list of numbers it still remains countable, but the list just isn't what we claimed it was - a list of all the real numbers between 0 and 1).

OK, I guess that I have to accept logic--and for decades it has been sound logic to me.
Thanks for your time in replying to me.

 

[lex]

OK, I guess that I have to accept logic--and for decades it has been sound logic to me.
Thanks for your time in replying to me.

Oh dear, you know it must be true but your gut is against it. I suspect you will be wrestling with this thought for a while.
It is a familiar feeling!

I don't know if the following is of any help.
The two scenarios deal with different issues.
The conundrum in Hilbert's Hotel is that you can add 1 item to an infinite set and still have the same 'size' of set.
In Cantor's diagonal argument the issue is the impossibility of listing the real numbers between 0 and 1.

If you want to 'mix the metaphors' - in Cantor showing that the reals between 0 and 1 are not countable, he is assuming that all the numbers between 0 and 1 are (single) residents of Hilbert's hotel, and he then goes on to identify a person (related to each person in each room of the hotel), but this person (real number between 0 and 1) is clearly not in any of the rooms. This gives a contradiction. Therefore the assumption that all the real numbers between 0 and 1 are (single) residents in the rooms of the hotel, must be false.

That is a very different issue from showing that when all the rooms in the hotel are occupied you can re-room people and fit another in.

Good luck!

 

[Steven G]

Oh dear, you know it must be true but your gut is against it. I suspect you will be wrestling with this thought for a while.
It is a familiar feeling!

I don't know if the following is of any help.
The two scenarios deal with different issues.
The conundrum in Hilbert's Hotel is that you can add 1 item to an infinite set and still have the same 'size' of set.
In Cantor's diagonal argument the issue is the impossibility of listing the real numbers between 0 and 1.

If you want to 'mix the metaphors' - in Cantor showing that the reals between 0 and 1 are not countable, he is assuming that all the numbers between 0 and 1 are (single) residents of Hilbert's hotel, and he then goes on to identify a person (related to each person in each room of the hotel), but this person (real number between 0 and 1) is clearly not in any of the rooms. This gives a contradiction. Therefore the assumption that all the real numbers between 0 and 1 are (single) residents in the rooms of the hotel, must be false.

That is a very different issue from showing that when all the rooms in the hotel are occupied you can re-room people and fit another in.

Good luck!

I need to absorb all this. Just give me a few more days and I'll be satisfied. Sometimes I just need to settle things in my mind. My PhD mathematician friend claims that this is why he (incorrectly) calls me a mathematician.
If I do not understand something I will not let it go until I finally settle things to my own satisfaction. I think that this makes me a stronger math person.
Thanks for your reply.

 

[JeffM]

I need to absorb all this. Just give me a few more days and I'll be satisfied. Sometimes I just need to settle things in my mind. My PhD mathematician friend claims that this is why he (incorrectly) calls me a mathematician.
If I do not understand something I will not let it go until I finally settle things to my own satisfaction. I think that this makes me a stronger math person.
Thanks for your reply.

Actually, this may be a peculiarity of mathematicians, but it is not unique to them. I am as far from a mathematician as anyone can get, but I can invest considerable effort on those math problems I understand but find difficult because I am stubborn as a mule. (I am dubious whether stubbornness is a virtue, a vice, or a form of insanity.) Last year, I spent weeks on a problem I called the Jomo problem (it was essentially posed by Jomo) before I could find an answer even close to elegant. Most other work that I could have done during those weeks was foregone because I became obsessed with the Jomo problem.

 

[lex]

@JeffM
I'm glad you haven't stated the problem, as I know what you mean!

 

[Steven G]

Jeff,
What is the Jomo problem? You got me curious.
In my opinion, a mathematician is a blind man in a dark room looking for a black cat which isn’t there. No no, I meant that a mathematician, in my opinion, is someone who has a PhD in math and does mathematical research. Some may say that I should not include doing mathematical research.
However my friend, who is a research mathematician, claims that someone who sees the beauty in math is a mathematician. You, Jeff, clearly see the beauty in math (you wouldn't be part of this forum otherwise) and according to my friend you are a mathematician. Even if you disagree with being a mathematician, you see the beauty in math and hence would spend a considerable amount of time on a given problem. Seeing the beauty in math is all that it takes to work on a problem until you have it settled in your mind.

 

[Steven G]

I found the Jomo problem. Am I now famous with a problem named after me?

 

[JeffM]

Here is the Jomo problem as I formulated it for myself. The problem arose from a student's question and a comment from jomo about his intuition.

If f(x) is a conforming polynomial defined by the stipulations below, MUST it have a local maximum to the right of the y-axis?

The short answer to that generalized question is "NO." Jomo's intuition was CORRECT. That leads naturally to a second question. A conforming polynomial must have a local maximum to the left of the y-axis and another local maximum further to the right. What determines whether that second local maximum is to the left of, or on, or to the right of the y-axis? The answer to this question was not so intuitive as I wanted a proof that worked for any conforming polynomial of any degree.

[math]\text {Given } \pi,\ \sigma,\ \tau, \text { and } \omega \text { are all real and} > 0,\\ \text f(x) \text { is a conforming polynomial} \iff \\ \text {Stipulation 1: } f(x) \text { is a real polynomial};\\ \text {Stipulation 2: } f(0) = \omega; \\ \text {Stipulation 3: } x < - \sigma \implies \text {sgn}\{f(x)\} = -1;\\ \text {Stipulation 4: } \text {sgn}\{f(- \sigma)\} = 0;\\ \text {Stipulation 5: } - \sigma < x < - \pi \implies \text {sgn}\{f(x)\} = -1;\\ \text {Stipulation 6: } - \pi < x < \tau \implies\text {sgn}\{f(x)\} = 1;\text { and}\\ \text {Stipulation 7: } x > \tau \implies \text {sgn}\{f(x)\} = -1.[/math]
It cannot be a famous problem because only I worked on it. My approach used the fundamental theorem of algebra and the intermediate value theorem in addition to induction. Obviously, it is not a profound problem, but it intrigued me for some reason.