Mixing
Uncountable Sets and an Infinite Real Number Game
Clash Royale CLAN TAG#URR8PPP
up vote
-1
down vote
favorite
In Problem #1542 of Mathematics Magazine, Grossman and Turett define the Cantor game.
http://people.math.gatech.edu/~mbaker/pdf/realgame.pdf
This is a "proof" of the real numbers being uncountable, that is supposedly "in many ways much simpler than Cantor’s original proof".
I can't even find one of the "many ways". I can't even see why it would be a proof at all.
Unfortunately there is not much information on the web about it. Even Mathematics Magazine does not have it. (may need a subscription to find it)
If anyone can give me a hint as to why this proof works, I would be very grateful.
Edit to make the question more clear:
If this is a correct summation of the proof then my problem follows.
We have a set $S = [0, 1] $, we will let the first element be $s_1$ where it's value will be derived from tossing an infinite number of coins. If the coins land HHTHHHTHHHHHHT $dots$ then the binary value of $s_1 = 0.11011101111110 dots$ we will repeat this for each element $s_n$ of the set $S$
Then Alice and Bob will choose their numbers so that $S_n ≤ a_n lor S_n ≥ b_n$
Since $a_n < α_n < b_n$ for all $n$, we conclude that $α_n notin S$
The idea of the proof is that if by some miraculous stroke of luck our coin toss gives us $α_n$ then we can just make a new $α_n+1$ and keep playing the game till we run out of coin tosses or the probability of the coin tosses producing the new $α_n$ actually becomes zero and not just approaches zero.
My problem is "what allows us to say that we will actually run out of coin tosses when we should have an endless amount of them and why would the probability of the coin toss being $α_n$ ever actually be zero?"
elementary-set-theory
asked Jul 21 at 14:12
Ivan Hieno
1119
 |Â
show 3 more comments
up vote
-1
down vote
favorite
In Problem #1542 of Mathematics Magazine, Grossman and Turett define the Cantor game.
http://people.math.gatech.edu/~mbaker/pdf/realgame.pdf
This is a "proof" of the real numbers being uncountable, that is supposedly "in many ways much simpler than Cantor’s original proof".
I can't even find one of the "many ways". I can't even see why it would be a proof at all.
Unfortunately there is not much information on the web about it. Even Mathematics Magazine does not have it. (may need a subscription to find it)
If anyone can give me a hint as to why this proof works, I would be very grateful.
Edit to make the question more clear:
If this is a correct summation of the proof then my problem follows.
We have a set $S = [0, 1] $, we will let the first element be $s_1$ where it's value will be derived from tossing an infinite number of coins. If the coins land HHTHHHTHHHHHHT $dots$ then the binary value of $s_1 = 0.11011101111110 dots$ we will repeat this for each element $s_n$ of the set $S$
Then Alice and Bob will choose their numbers so that $S_n ≤ a_n lor S_n ≥ b_n$
Since $a_n < α_n < b_n$ for all $n$, we conclude that $α_n notin S$
The idea of the proof is that if by some miraculous stroke of luck our coin toss gives us $α_n$ then we can just make a new $α_n+1$ and keep playing the game till we run out of coin tosses or the probability of the coin tosses producing the new $α_n$ actually becomes zero and not just approaches zero.
My problem is "what allows us to say that we will actually run out of coin tosses when we should have an endless amount of them and why would the probability of the coin toss being $α_n$ ever actually be zero?"
elementary-set-theory
asked Jul 21 at 14:12
Ivan Hieno
1119
1
What is your question? You write as if you did not have access to the article, but you posted a link to it.
– José Carlos Santos
Jul 21 at 14:18
The proof is there in the article....
– Lord Shark the Unknown
Jul 21 at 14:18
@José Carlos Santos, reading the actual article will cost $15 per month. maa.org/press/periodicals/mathematics-magazine
– Ivan Hieno
Jul 21 at 15:20
@IvanHieno I clicked on the link from your first paragraph and the article appeared before my eyes. What happens when you click on it?
– José Carlos Santos
Jul 21 at 15:24
@José Carlos Santos, I get an article by Matthew Baker from Georgia Institute of Technology, not the original article from Mathematics Magazine.
– Ivan Hieno
Jul 21 at 15:27
 |Â
show 3 more comments
up vote
-1
down vote
favorite
up vote
-1
down vote
favorite
In Problem #1542 of Mathematics Magazine, Grossman and Turett define the Cantor game.
http://people.math.gatech.edu/~mbaker/pdf/realgame.pdf
This is a "proof" of the real numbers being uncountable, that is supposedly "in many ways much simpler than Cantor’s original proof".
I can't even find one of the "many ways". I can't even see why it would be a proof at all.
Unfortunately there is not much information on the web about it. Even Mathematics Magazine does not have it. (may need a subscription to find it)
If anyone can give me a hint as to why this proof works, I would be very grateful.
Edit to make the question more clear:
If this is a correct summation of the proof then my problem follows.
We have a set $S = [0, 1] $, we will let the first element be $s_1$ where it's value will be derived from tossing an infinite number of coins. If the coins land HHTHHHTHHHHHHT $dots$ then the binary value of $s_1 = 0.11011101111110 dots$ we will repeat this for each element $s_n$ of the set $S$
Then Alice and Bob will choose their numbers so that $S_n ≤ a_n lor S_n ≥ b_n$
Since $a_n < α_n < b_n$ for all $n$, we conclude that $α_n notin S$
The idea of the proof is that if by some miraculous stroke of luck our coin toss gives us $α_n$ then we can just make a new $α_n+1$ and keep playing the game till we run out of coin tosses or the probability of the coin tosses producing the new $α_n$ actually becomes zero and not just approaches zero.
My problem is "what allows us to say that we will actually run out of coin tosses when we should have an endless amount of them and why would the probability of the coin toss being $α_n$ ever actually be zero?"
elementary-set-theory
asked Jul 21 at 14:12
Ivan Hieno
1119
In Problem #1542 of Mathematics Magazine, Grossman and Turett define the Cantor game.
http://people.math.gatech.edu/~mbaker/pdf/realgame.pdf
This is a "proof" of the real numbers being uncountable, that is supposedly "in many ways much simpler than Cantor’s original proof".
I can't even find one of the "many ways". I can't even see why it would be a proof at all.
Unfortunately there is not much information on the web about it. Even Mathematics Magazine does not have it. (may need a subscription to find it)
If anyone can give me a hint as to why this proof works, I would be very grateful.
Edit to make the question more clear:
If this is a correct summation of the proof then my problem follows.
We have a set $S = [0, 1] $, we will let the first element be $s_1$ where it's value will be derived from tossing an infinite number of coins. If the coins land HHTHHHTHHHHHHT $dots$ then the binary value of $s_1 = 0.11011101111110 dots$ we will repeat this for each element $s_n$ of the set $S$
Then Alice and Bob will choose their numbers so that $S_n ≤ a_n lor S_n ≥ b_n$
Since $a_n < α_n < b_n$ for all $n$, we conclude that $α_n notin S$
The idea of the proof is that if by some miraculous stroke of luck our coin toss gives us $α_n$ then we can just make a new $α_n+1$ and keep playing the game till we run out of coin tosses or the probability of the coin tosses producing the new $α_n$ actually becomes zero and not just approaches zero.
My problem is "what allows us to say that we will actually run out of coin tosses when we should have an endless amount of them and why would the probability of the coin toss being $α_n$ ever actually be zero?"
elementary-set-theory
asked Jul 21 at 14:12
Ivan Hieno
1119
edited Jul 25 at 18:19
asked Jul 21 at 14:12
Ivan Hieno
1119
asked Jul 21 at 14:12
Ivan Hieno
1119
asked Jul 21 at 14:12
Ivan Hieno
1119
1119
1
What is your question? You write as if you did not have access to the article, but you posted a link to it.
– José Carlos Santos
Jul 21 at 14:18
The proof is there in the article....
– Lord Shark the Unknown
Jul 21 at 14:18
@José Carlos Santos, reading the actual article will cost $15 per month. maa.org/press/periodicals/mathematics-magazine
– Ivan Hieno
Jul 21 at 15:20
@IvanHieno I clicked on the link from your first paragraph and the article appeared before my eyes. What happens when you click on it?
– José Carlos Santos
Jul 21 at 15:24
@José Carlos Santos, I get an article by Matthew Baker from Georgia Institute of Technology, not the original article from Mathematics Magazine.
– Ivan Hieno
Jul 21 at 15:27
 |Â
show 3 more comments
1
What is your question? You write as if you did not have access to the article, but you posted a link to it.
– José Carlos Santos
Jul 21 at 14:18
The proof is there in the article....
– Lord Shark the Unknown
Jul 21 at 14:18
@José Carlos Santos, reading the actual article will cost $15 per month. maa.org/press/periodicals/mathematics-magazine
– Ivan Hieno
Jul 21 at 15:20
@IvanHieno I clicked on the link from your first paragraph and the article appeared before my eyes. What happens when you click on it?
– José Carlos Santos
Jul 21 at 15:24
@José Carlos Santos, I get an article by Matthew Baker from Georgia Institute of Technology, not the original article from Mathematics Magazine.
– Ivan Hieno
Jul 21 at 15:27
1
1
What is your question? You write as if you did not have access to the article, but you posted a link to it.
– José Carlos Santos
Jul 21 at 14:18
What is your question? You write as if you did not have access to the article, but you posted a link to it.
– José Carlos Santos
Jul 21 at 14:18
The proof is there in the article....
– Lord Shark the Unknown
Jul 21 at 14:18
The proof is there in the article....
– Lord Shark the Unknown
Jul 21 at 14:18
@José Carlos Santos, reading the actual article will cost $15 per month. maa.org/press/periodicals/mathematics-magazine
– Ivan Hieno
Jul 21 at 15:20
@José Carlos Santos, reading the actual article will cost $15 per month. maa.org/press/periodicals/mathematics-magazine
– Ivan Hieno
Jul 21 at 15:20
@IvanHieno I clicked on the link from your first paragraph and the article appeared before my eyes. What happens when you click on it?
– José Carlos Santos
Jul 21 at 15:24
@IvanHieno I clicked on the link from your first paragraph and the article appeared before my eyes. What happens when you click on it?
– José Carlos Santos
Jul 21 at 15:24
@José Carlos Santos, I get an article by Matthew Baker from Georgia Institute of Technology, not the original article from Mathematics Magazine.
– Ivan Hieno
Jul 21 at 15:27
@José Carlos Santos, I get an article by Matthew Baker from Georgia Institute of Technology, not the original article from Mathematics Magazine.
– Ivan Hieno
Jul 21 at 15:27
 |Â
show 3 more comments
2 Answers
2
active
oldest
votes
up vote
1
down vote
If you assume $S$ is countable, and Bob always chooses $s_n$ on his $n$th move if possible, then eventually each element of $S$ can no longer be chosen, i.e. for all $n$ there exists $N$ such that if $m geq N$ then $s_n not in (a_m,b_m)$. In fact one can be more explicit: $N=n$ is sufficient, because either $b_n=s_n$ or $s_n not in (a_n-1,b_n-1)$. On the other hand, $alpha in (a_m,b_m)$ for all $m$. Thus for all $n,s_n neq alpha$, so $alpha not in S$.
On the other hand, if you assume $S=[0,1]$, then whatever $alpha$ winds up being, Alice wins by definition, because $alpha$ will always exist and will always be in $[0,1]$. So $[0,1]$ cannot be countable or it would contradict the previous case.
Really it is not so different from Cantor's proof when you think carefully. Each move where Bob actually does pick $s_n$, he is forcing $alpha$ to be at least a little bit smaller than $s_n$, which rules out $alpha$ actually being equal to $s_n$. This is similar to setting the $n$th digit in the expansion of $alpha$ to be something other than the $n$th digit in the expansion of $s_n$.
answered Jul 21 at 14:25
Ian
65k24681
add a comment |Â
up vote
0
down vote
I would say it is proving a different proposition than Cantor. Cantor proved the power set of the naturals is uncountable by constructing a subset that is not in any countable list. This article proves that a dense linear order that satisfies the least upper bound property is uncountable. It needs a dense linear order to be able to pick a number in any interval and needs the least upper bound property to claim the chosen numbers converge to something.
answered Jul 21 at 14:59
Ross Millikan
276k21186352
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
If you assume $S$ is countable, and Bob always chooses $s_n$ on his $n$th move if possible, then eventually each element of $S$ can no longer be chosen, i.e. for all $n$ there exists $N$ such that if $m geq N$ then $s_n not in (a_m,b_m)$. In fact one can be more explicit: $N=n$ is sufficient, because either $b_n=s_n$ or $s_n not in (a_n-1,b_n-1)$. On the other hand, $alpha in (a_m,b_m)$ for all $m$. Thus for all $n,s_n neq alpha$, so $alpha not in S$.
On the other hand, if you assume $S=[0,1]$, then whatever $alpha$ winds up being, Alice wins by definition, because $alpha$ will always exist and will always be in $[0,1]$. So $[0,1]$ cannot be countable or it would contradict the previous case.
Really it is not so different from Cantor's proof when you think carefully. Each move where Bob actually does pick $s_n$, he is forcing $alpha$ to be at least a little bit smaller than $s_n$, which rules out $alpha$ actually being equal to $s_n$. This is similar to setting the $n$th digit in the expansion of $alpha$ to be something other than the $n$th digit in the expansion of $s_n$.
answered Jul 21 at 14:25
Ian
65k24681
add a comment |Â
up vote
1
down vote
If you assume $S$ is countable, and Bob always chooses $s_n$ on his $n$th move if possible, then eventually each element of $S$ can no longer be chosen, i.e. for all $n$ there exists $N$ such that if $m geq N$ then $s_n not in (a_m,b_m)$. In fact one can be more explicit: $N=n$ is sufficient, because either $b_n=s_n$ or $s_n not in (a_n-1,b_n-1)$. On the other hand, $alpha in (a_m,b_m)$ for all $m$. Thus for all $n,s_n neq alpha$, so $alpha not in S$.
On the other hand, if you assume $S=[0,1]$, then whatever $alpha$ winds up being, Alice wins by definition, because $alpha$ will always exist and will always be in $[0,1]$. So $[0,1]$ cannot be countable or it would contradict the previous case.
Really it is not so different from Cantor's proof when you think carefully. Each move where Bob actually does pick $s_n$, he is forcing $alpha$ to be at least a little bit smaller than $s_n$, which rules out $alpha$ actually being equal to $s_n$. This is similar to setting the $n$th digit in the expansion of $alpha$ to be something other than the $n$th digit in the expansion of $s_n$.
answered Jul 21 at 14:25
Ian
65k24681
add a comment |Â
up vote
1
down vote
up vote
1
down vote
If you assume $S$ is countable, and Bob always chooses $s_n$ on his $n$th move if possible, then eventually each element of $S$ can no longer be chosen, i.e. for all $n$ there exists $N$ such that if $m geq N$ then $s_n not in (a_m,b_m)$. In fact one can be more explicit: $N=n$ is sufficient, because either $b_n=s_n$ or $s_n not in (a_n-1,b_n-1)$. On the other hand, $alpha in (a_m,b_m)$ for all $m$. Thus for all $n,s_n neq alpha$, so $alpha not in S$.
On the other hand, if you assume $S=[0,1]$, then whatever $alpha$ winds up being, Alice wins by definition, because $alpha$ will always exist and will always be in $[0,1]$. So $[0,1]$ cannot be countable or it would contradict the previous case.
Really it is not so different from Cantor's proof when you think carefully. Each move where Bob actually does pick $s_n$, he is forcing $alpha$ to be at least a little bit smaller than $s_n$, which rules out $alpha$ actually being equal to $s_n$. This is similar to setting the $n$th digit in the expansion of $alpha$ to be something other than the $n$th digit in the expansion of $s_n$.
answered Jul 21 at 14:25
Ian
65k24681
If you assume $S$ is countable, and Bob always chooses $s_n$ on his $n$th move if possible, then eventually each element of $S$ can no longer be chosen, i.e. for all $n$ there exists $N$ such that if $m geq N$ then $s_n not in (a_m,b_m)$. In fact one can be more explicit: $N=n$ is sufficient, because either $b_n=s_n$ or $s_n not in (a_n-1,b_n-1)$. On the other hand, $alpha in (a_m,b_m)$ for all $m$. Thus for all $n,s_n neq alpha$, so $alpha not in S$.
On the other hand, if you assume $S=[0,1]$, then whatever $alpha$ winds up being, Alice wins by definition, because $alpha$ will always exist and will always be in $[0,1]$. So $[0,1]$ cannot be countable or it would contradict the previous case.
Really it is not so different from Cantor's proof when you think carefully. Each move where Bob actually does pick $s_n$, he is forcing $alpha$ to be at least a little bit smaller than $s_n$, which rules out $alpha$ actually being equal to $s_n$. This is similar to setting the $n$th digit in the expansion of $alpha$ to be something other than the $n$th digit in the expansion of $s_n$.
answered Jul 21 at 14:25
Ian
65k24681
answered Jul 21 at 14:25
Ian
65k24681
answered Jul 21 at 14:25
Ian
65k24681
answered Jul 21 at 14:25
Ian
65k24681
65k24681
add a comment |Â
add a comment |Â
up vote
0
down vote
I would say it is proving a different proposition than Cantor. Cantor proved the power set of the naturals is uncountable by constructing a subset that is not in any countable list. This article proves that a dense linear order that satisfies the least upper bound property is uncountable. It needs a dense linear order to be able to pick a number in any interval and needs the least upper bound property to claim the chosen numbers converge to something.
answered Jul 21 at 14:59
Ross Millikan
276k21186352
add a comment |Â
up vote
0
down vote
I would say it is proving a different proposition than Cantor. Cantor proved the power set of the naturals is uncountable by constructing a subset that is not in any countable list. This article proves that a dense linear order that satisfies the least upper bound property is uncountable. It needs a dense linear order to be able to pick a number in any interval and needs the least upper bound property to claim the chosen numbers converge to something.
answered Jul 21 at 14:59
Ross Millikan
276k21186352
add a comment |Â
up vote
0
down vote
up vote
0
down vote
I would say it is proving a different proposition than Cantor. Cantor proved the power set of the naturals is uncountable by constructing a subset that is not in any countable list. This article proves that a dense linear order that satisfies the least upper bound property is uncountable. It needs a dense linear order to be able to pick a number in any interval and needs the least upper bound property to claim the chosen numbers converge to something.
answered Jul 21 at 14:59
Ross Millikan
276k21186352
I would say it is proving a different proposition than Cantor. Cantor proved the power set of the naturals is uncountable by constructing a subset that is not in any countable list. This article proves that a dense linear order that satisfies the least upper bound property is uncountable. It needs a dense linear order to be able to pick a number in any interval and needs the least upper bound property to claim the chosen numbers converge to something.
answered Jul 21 at 14:59
Ross Millikan
276k21186352
answered Jul 21 at 14:59
Ross Millikan
276k21186352
answered Jul 21 at 14:59
Ross Millikan
276k21186352
answered Jul 21 at 14:59
Ross Millikan
276k21186352
276k21186352
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2858527%2funcountable-sets-and-an-infinite-real-number-game%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
What is your question? You write as if you did not have access to the article, but you posted a link to it.
– José Carlos Santos
Jul 21 at 14:18
The proof is there in the article....
– Lord Shark the Unknown
Jul 21 at 14:18
@José Carlos Santos, reading the actual article will cost $15 per month. maa.org/press/periodicals/mathematics-magazine
– Ivan Hieno
Jul 21 at 15:20
@IvanHieno I clicked on the link from your first paragraph and the article appeared before my eyes. What happens when you click on it?
– José Carlos Santos
Jul 21 at 15:24
@José Carlos Santos, I get an article by Matthew Baker from Georgia Institute of Technology, not the original article from Mathematics Magazine.
– Ivan Hieno
Jul 21 at 15:27