Mixing
Confusion about countability [closed]
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
$(0, 1)$ can be proved uncountable by using Cantor's diagonalization argument. It shows there are real numbers not in the list $(x_1, x_2...)$, where $x_n=0.a_n1a_n2...$, a decimal expansion of $x_n$. I think I do not quite understand the proof since I'm not very convinced by it and it's clearly a right proof. I feel it somehow not explicitly showed that there don't exist any bijection function from $(0,1)$ to $mathbbN$. I feel the proof is showing that since every natural number is already corresponding to a $x_n$, there are not place for anything else. And since both $mathbbZ$ and $mathbbQ$ are countable, then all the natural numbers are already corresponding to $mathbbZ$, but we can still insert the rational numbers that are not integer to corresponding to some natural numbers.What's the difference here? Can someone help me clear my mind? Thank ahead.
elementary-set-theory
asked Jul 27 at 3:30
Cathy
1067
closed as off-topic by Andrés E. Caicedo, Lord Shark the Unknown, Xander Henderson, Shailesh, José Carlos Santos Jul 27 at 16:45
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Xander Henderson, Shailesh
add a comment |Â
up vote
1
down vote
favorite
$(0, 1)$ can be proved uncountable by using Cantor's diagonalization argument. It shows there are real numbers not in the list $(x_1, x_2...)$, where $x_n=0.a_n1a_n2...$, a decimal expansion of $x_n$. I think I do not quite understand the proof since I'm not very convinced by it and it's clearly a right proof. I feel it somehow not explicitly showed that there don't exist any bijection function from $(0,1)$ to $mathbbN$. I feel the proof is showing that since every natural number is already corresponding to a $x_n$, there are not place for anything else. And since both $mathbbZ$ and $mathbbQ$ are countable, then all the natural numbers are already corresponding to $mathbbZ$, but we can still insert the rational numbers that are not integer to corresponding to some natural numbers.What's the difference here? Can someone help me clear my mind? Thank ahead.
elementary-set-theory
asked Jul 27 at 3:30
Cathy
1067
closed as off-topic by Andrés E. Caicedo, Lord Shark the Unknown, Xander Henderson, Shailesh, José Carlos Santos Jul 27 at 16:45
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Xander Henderson, Shailesh
1
The proof is definitely not direct. One assumes there is a bijection from $mathbfN$ to $(0,1)$ and writes $x_n$ for the image of the natural number $n$ under this function. Then a contradiction is derived using decimal expansions of the numbers $x_n$, $ngeq 1$.
– Keenan Kidwell
Jul 27 at 3:38
I think this exact same point of confusion has been covered in earlier posts about Canto's diagonalization argument. Did you search the site?
– Jyrki Lahtonen
Jul 27 at 6:07
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
$(0, 1)$ can be proved uncountable by using Cantor's diagonalization argument. It shows there are real numbers not in the list $(x_1, x_2...)$, where $x_n=0.a_n1a_n2...$, a decimal expansion of $x_n$. I think I do not quite understand the proof since I'm not very convinced by it and it's clearly a right proof. I feel it somehow not explicitly showed that there don't exist any bijection function from $(0,1)$ to $mathbbN$. I feel the proof is showing that since every natural number is already corresponding to a $x_n$, there are not place for anything else. And since both $mathbbZ$ and $mathbbQ$ are countable, then all the natural numbers are already corresponding to $mathbbZ$, but we can still insert the rational numbers that are not integer to corresponding to some natural numbers.What's the difference here? Can someone help me clear my mind? Thank ahead.
elementary-set-theory
asked Jul 27 at 3:30
Cathy
1067
$(0, 1)$ can be proved uncountable by using Cantor's diagonalization argument. It shows there are real numbers not in the list $(x_1, x_2...)$, where $x_n=0.a_n1a_n2...$, a decimal expansion of $x_n$. I think I do not quite understand the proof since I'm not very convinced by it and it's clearly a right proof. I feel it somehow not explicitly showed that there don't exist any bijection function from $(0,1)$ to $mathbbN$. I feel the proof is showing that since every natural number is already corresponding to a $x_n$, there are not place for anything else. And since both $mathbbZ$ and $mathbbQ$ are countable, then all the natural numbers are already corresponding to $mathbbZ$, but we can still insert the rational numbers that are not integer to corresponding to some natural numbers.What's the difference here? Can someone help me clear my mind? Thank ahead.
elementary-set-theory
asked Jul 27 at 3:30
Cathy
1067
edited Jul 27 at 3:44
asked Jul 27 at 3:30
Cathy
1067
asked Jul 27 at 3:30
Cathy
1067
asked Jul 27 at 3:30
Cathy
1067
1067
closed as off-topic by Andrés E. Caicedo, Lord Shark the Unknown, Xander Henderson, Shailesh, José Carlos Santos Jul 27 at 16:45
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Xander Henderson, Shailesh
closed as off-topic by Andrés E. Caicedo, Lord Shark the Unknown, Xander Henderson, Shailesh, José Carlos Santos Jul 27 at 16:45
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Xander Henderson, Shailesh
1
The proof is definitely not direct. One assumes there is a bijection from $mathbfN$ to $(0,1)$ and writes $x_n$ for the image of the natural number $n$ under this function. Then a contradiction is derived using decimal expansions of the numbers $x_n$, $ngeq 1$.
– Keenan Kidwell
Jul 27 at 3:38
I think this exact same point of confusion has been covered in earlier posts about Canto's diagonalization argument. Did you search the site?
– Jyrki Lahtonen
Jul 27 at 6:07
add a comment |Â
1
The proof is definitely not direct. One assumes there is a bijection from $mathbfN$ to $(0,1)$ and writes $x_n$ for the image of the natural number $n$ under this function. Then a contradiction is derived using decimal expansions of the numbers $x_n$, $ngeq 1$.
– Keenan Kidwell
Jul 27 at 3:38
I think this exact same point of confusion has been covered in earlier posts about Canto's diagonalization argument. Did you search the site?
– Jyrki Lahtonen
Jul 27 at 6:07
1
1
The proof is definitely not direct. One assumes there is a bijection from $mathbfN$ to $(0,1)$ and writes $x_n$ for the image of the natural number $n$ under this function. Then a contradiction is derived using decimal expansions of the numbers $x_n$, $ngeq 1$.
– Keenan Kidwell
Jul 27 at 3:38
The proof is definitely not direct. One assumes there is a bijection from $mathbfN$ to $(0,1)$ and writes $x_n$ for the image of the natural number $n$ under this function. Then a contradiction is derived using decimal expansions of the numbers $x_n$, $ngeq 1$.
– Keenan Kidwell
Jul 27 at 3:38
I think this exact same point of confusion has been covered in earlier posts about Canto's diagonalization argument. Did you search the site?
– Jyrki Lahtonen
Jul 27 at 6:07
I think this exact same point of confusion has been covered in earlier posts about Canto's diagonalization argument. Did you search the site?
– Jyrki Lahtonen
Jul 27 at 6:07
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
accepted
In a nutshell, Cantor's argument was to show there cannot be a surjection from $mathbbN$ to $(0,1)$. E.g. no matter what map you give me, there is always some real number that your map from the naturals does not hit. However, for the naturals to the rationals there are many surjective and bijective maps from $mathbbN rightarrow mathbbQ$.
In addition, cardinality is an equivalence relation e.g. if $|A| = |B|$ and $|B| = |C|$, we see $|A| = |C|$. By using this we see by Cantor's argument that there is no map from ANY countable set to $(0,1)$, which bisects to $mathbbR$.
Here's the intuition of why there is at least one real number not in the range of any map from $mathbbN rightarrow (0,1)$.
Assume $(0,1)$ is countable, then we can list every element out, which is the hallmark of countable sets. E.g. for every $x in (0,1)$ there is some $n$ such that $x=$ $x_n = 0.k_1k_2k_3.....$.
Now on our "$n^th$" digit of $x_n$ set $m_n = k_n + 1$ (with $9+1$ being sent to $0$). Then consider $gamma = 0.m_1m_2m_3...m_n....$, clearly $gamma$ is a real number. At the same time $gamma$ is different from every $x_n$ because it differs by every $x_n$ by at least one digit. Therefore, $gamma$ is not in $(0,1)$ as we assumed every $x in (0,1)$, we can write out as $x_n$ for some $n$, but we showed $
gamma$ is not on that list! But it clearly is also in $(0,1)$. Hence, we found a real number on $(0,1)$ that is not in our list, so we see no matter for what mapping we give, we cannot have a surjection from $mathbbN rightarrow (0,1)$. Therefore, it cannot be a bijection. Then by the equivalence class as $|(0,1)| = |mathbbR|$, we see the result follows.
answered Jul 27 at 3:39
Raymond Chu
1,02219
Thanks, but I still didn't quite understand how Cantor's argument shows there cannot be a surjection from N to (0, 1). I know how the proof goes, but not know how the process in the proof proved there cannot be such a surjection.
– Cathy
Jul 27 at 5:48
It's somehow seems to me that it denied one kind of mapping not all kinds of mapping from N to (0, 1). Where I am wrong?
– Cathy
Jul 27 at 5:59
1
Well, I guess another way of looking at this proof is that no matter what countable subset of $(0,1)$ that you give me, I can always find a number not in your countable subset (in particular the $gamma$). Therefore, $(0,1)$ is not countable; otherwise, there would be a countable subset that contained the entire interval.
– Raymond Chu
Jul 27 at 6:16
add a comment |Â
up vote
0
down vote
You're right, it does show that there is not a "place" for the number created from diagonalization. So this conclusion is stating the bijection we assumed we had was not really a bijection since it missed a number. They are logically equivalent statements.
I don't quite understand the second half of your question.
answered Jul 27 at 3:39
El Gallo Negro
233
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
In a nutshell, Cantor's argument was to show there cannot be a surjection from $mathbbN$ to $(0,1)$. E.g. no matter what map you give me, there is always some real number that your map from the naturals does not hit. However, for the naturals to the rationals there are many surjective and bijective maps from $mathbbN rightarrow mathbbQ$.
In addition, cardinality is an equivalence relation e.g. if $|A| = |B|$ and $|B| = |C|$, we see $|A| = |C|$. By using this we see by Cantor's argument that there is no map from ANY countable set to $(0,1)$, which bisects to $mathbbR$.
Here's the intuition of why there is at least one real number not in the range of any map from $mathbbN rightarrow (0,1)$.
Assume $(0,1)$ is countable, then we can list every element out, which is the hallmark of countable sets. E.g. for every $x in (0,1)$ there is some $n$ such that $x=$ $x_n = 0.k_1k_2k_3.....$.
Now on our "$n^th$" digit of $x_n$ set $m_n = k_n + 1$ (with $9+1$ being sent to $0$). Then consider $gamma = 0.m_1m_2m_3...m_n....$, clearly $gamma$ is a real number. At the same time $gamma$ is different from every $x_n$ because it differs by every $x_n$ by at least one digit. Therefore, $gamma$ is not in $(0,1)$ as we assumed every $x in (0,1)$, we can write out as $x_n$ for some $n$, but we showed $
gamma$ is not on that list! But it clearly is also in $(0,1)$. Hence, we found a real number on $(0,1)$ that is not in our list, so we see no matter for what mapping we give, we cannot have a surjection from $mathbbN rightarrow (0,1)$. Therefore, it cannot be a bijection. Then by the equivalence class as $|(0,1)| = |mathbbR|$, we see the result follows.
answered Jul 27 at 3:39
Raymond Chu
1,02219
Thanks, but I still didn't quite understand how Cantor's argument shows there cannot be a surjection from N to (0, 1). I know how the proof goes, but not know how the process in the proof proved there cannot be such a surjection.
– Cathy
Jul 27 at 5:48
It's somehow seems to me that it denied one kind of mapping not all kinds of mapping from N to (0, 1). Where I am wrong?
– Cathy
Jul 27 at 5:59
1
Well, I guess another way of looking at this proof is that no matter what countable subset of $(0,1)$ that you give me, I can always find a number not in your countable subset (in particular the $gamma$). Therefore, $(0,1)$ is not countable; otherwise, there would be a countable subset that contained the entire interval.
– Raymond Chu
Jul 27 at 6:16
add a comment |Â
up vote
3
down vote
accepted
In a nutshell, Cantor's argument was to show there cannot be a surjection from $mathbbN$ to $(0,1)$. E.g. no matter what map you give me, there is always some real number that your map from the naturals does not hit. However, for the naturals to the rationals there are many surjective and bijective maps from $mathbbN rightarrow mathbbQ$.
In addition, cardinality is an equivalence relation e.g. if $|A| = |B|$ and $|B| = |C|$, we see $|A| = |C|$. By using this we see by Cantor's argument that there is no map from ANY countable set to $(0,1)$, which bisects to $mathbbR$.
Here's the intuition of why there is at least one real number not in the range of any map from $mathbbN rightarrow (0,1)$.
Assume $(0,1)$ is countable, then we can list every element out, which is the hallmark of countable sets. E.g. for every $x in (0,1)$ there is some $n$ such that $x=$ $x_n = 0.k_1k_2k_3.....$.
Now on our "$n^th$" digit of $x_n$ set $m_n = k_n + 1$ (with $9+1$ being sent to $0$). Then consider $gamma = 0.m_1m_2m_3...m_n....$, clearly $gamma$ is a real number. At the same time $gamma$ is different from every $x_n$ because it differs by every $x_n$ by at least one digit. Therefore, $gamma$ is not in $(0,1)$ as we assumed every $x in (0,1)$, we can write out as $x_n$ for some $n$, but we showed $
gamma$ is not on that list! But it clearly is also in $(0,1)$. Hence, we found a real number on $(0,1)$ that is not in our list, so we see no matter for what mapping we give, we cannot have a surjection from $mathbbN rightarrow (0,1)$. Therefore, it cannot be a bijection. Then by the equivalence class as $|(0,1)| = |mathbbR|$, we see the result follows.
answered Jul 27 at 3:39
Raymond Chu
1,02219
Thanks, but I still didn't quite understand how Cantor's argument shows there cannot be a surjection from N to (0, 1). I know how the proof goes, but not know how the process in the proof proved there cannot be such a surjection.
– Cathy
Jul 27 at 5:48
It's somehow seems to me that it denied one kind of mapping not all kinds of mapping from N to (0, 1). Where I am wrong?
– Cathy
Jul 27 at 5:59
1
Well, I guess another way of looking at this proof is that no matter what countable subset of $(0,1)$ that you give me, I can always find a number not in your countable subset (in particular the $gamma$). Therefore, $(0,1)$ is not countable; otherwise, there would be a countable subset that contained the entire interval.
– Raymond Chu
Jul 27 at 6:16
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
In a nutshell, Cantor's argument was to show there cannot be a surjection from $mathbbN$ to $(0,1)$. E.g. no matter what map you give me, there is always some real number that your map from the naturals does not hit. However, for the naturals to the rationals there are many surjective and bijective maps from $mathbbN rightarrow mathbbQ$.
In addition, cardinality is an equivalence relation e.g. if $|A| = |B|$ and $|B| = |C|$, we see $|A| = |C|$. By using this we see by Cantor's argument that there is no map from ANY countable set to $(0,1)$, which bisects to $mathbbR$.
Here's the intuition of why there is at least one real number not in the range of any map from $mathbbN rightarrow (0,1)$.
Assume $(0,1)$ is countable, then we can list every element out, which is the hallmark of countable sets. E.g. for every $x in (0,1)$ there is some $n$ such that $x=$ $x_n = 0.k_1k_2k_3.....$.
Now on our "$n^th$" digit of $x_n$ set $m_n = k_n + 1$ (with $9+1$ being sent to $0$). Then consider $gamma = 0.m_1m_2m_3...m_n....$, clearly $gamma$ is a real number. At the same time $gamma$ is different from every $x_n$ because it differs by every $x_n$ by at least one digit. Therefore, $gamma$ is not in $(0,1)$ as we assumed every $x in (0,1)$, we can write out as $x_n$ for some $n$, but we showed $
gamma$ is not on that list! But it clearly is also in $(0,1)$. Hence, we found a real number on $(0,1)$ that is not in our list, so we see no matter for what mapping we give, we cannot have a surjection from $mathbbN rightarrow (0,1)$. Therefore, it cannot be a bijection. Then by the equivalence class as $|(0,1)| = |mathbbR|$, we see the result follows.
answered Jul 27 at 3:39
Raymond Chu
1,02219
In a nutshell, Cantor's argument was to show there cannot be a surjection from $mathbbN$ to $(0,1)$. E.g. no matter what map you give me, there is always some real number that your map from the naturals does not hit. However, for the naturals to the rationals there are many surjective and bijective maps from $mathbbN rightarrow mathbbQ$.
In addition, cardinality is an equivalence relation e.g. if $|A| = |B|$ and $|B| = |C|$, we see $|A| = |C|$. By using this we see by Cantor's argument that there is no map from ANY countable set to $(0,1)$, which bisects to $mathbbR$.
Here's the intuition of why there is at least one real number not in the range of any map from $mathbbN rightarrow (0,1)$.
Assume $(0,1)$ is countable, then we can list every element out, which is the hallmark of countable sets. E.g. for every $x in (0,1)$ there is some $n$ such that $x=$ $x_n = 0.k_1k_2k_3.....$.
Now on our "$n^th$" digit of $x_n$ set $m_n = k_n + 1$ (with $9+1$ being sent to $0$). Then consider $gamma = 0.m_1m_2m_3...m_n....$, clearly $gamma$ is a real number. At the same time $gamma$ is different from every $x_n$ because it differs by every $x_n$ by at least one digit. Therefore, $gamma$ is not in $(0,1)$ as we assumed every $x in (0,1)$, we can write out as $x_n$ for some $n$, but we showed $
gamma$ is not on that list! But it clearly is also in $(0,1)$. Hence, we found a real number on $(0,1)$ that is not in our list, so we see no matter for what mapping we give, we cannot have a surjection from $mathbbN rightarrow (0,1)$. Therefore, it cannot be a bijection. Then by the equivalence class as $|(0,1)| = |mathbbR|$, we see the result follows.
answered Jul 27 at 3:39
Raymond Chu
1,02219
edited Jul 27 at 3:46
answered Jul 27 at 3:39
Raymond Chu
1,02219
answered Jul 27 at 3:39
Raymond Chu
1,02219
answered Jul 27 at 3:39
Raymond Chu
1,02219
1,02219
Thanks, but I still didn't quite understand how Cantor's argument shows there cannot be a surjection from N to (0, 1). I know how the proof goes, but not know how the process in the proof proved there cannot be such a surjection.
– Cathy
Jul 27 at 5:48
It's somehow seems to me that it denied one kind of mapping not all kinds of mapping from N to (0, 1). Where I am wrong?
– Cathy
Jul 27 at 5:59
1
Well, I guess another way of looking at this proof is that no matter what countable subset of $(0,1)$ that you give me, I can always find a number not in your countable subset (in particular the $gamma$). Therefore, $(0,1)$ is not countable; otherwise, there would be a countable subset that contained the entire interval.
– Raymond Chu
Jul 27 at 6:16
add a comment |Â
Thanks, but I still didn't quite understand how Cantor's argument shows there cannot be a surjection from N to (0, 1). I know how the proof goes, but not know how the process in the proof proved there cannot be such a surjection.
– Cathy
Jul 27 at 5:48
It's somehow seems to me that it denied one kind of mapping not all kinds of mapping from N to (0, 1). Where I am wrong?
– Cathy
Jul 27 at 5:59
1
Well, I guess another way of looking at this proof is that no matter what countable subset of $(0,1)$ that you give me, I can always find a number not in your countable subset (in particular the $gamma$). Therefore, $(0,1)$ is not countable; otherwise, there would be a countable subset that contained the entire interval.
– Raymond Chu
Jul 27 at 6:16
Thanks, but I still didn't quite understand how Cantor's argument shows there cannot be a surjection from N to (0, 1). I know how the proof goes, but not know how the process in the proof proved there cannot be such a surjection.
– Cathy
Jul 27 at 5:48
Thanks, but I still didn't quite understand how Cantor's argument shows there cannot be a surjection from N to (0, 1). I know how the proof goes, but not know how the process in the proof proved there cannot be such a surjection.
– Cathy
Jul 27 at 5:48
It's somehow seems to me that it denied one kind of mapping not all kinds of mapping from N to (0, 1). Where I am wrong?
– Cathy
Jul 27 at 5:59
It's somehow seems to me that it denied one kind of mapping not all kinds of mapping from N to (0, 1). Where I am wrong?
– Cathy
Jul 27 at 5:59
1
1
Well, I guess another way of looking at this proof is that no matter what countable subset of $(0,1)$ that you give me, I can always find a number not in your countable subset (in particular the $gamma$). Therefore, $(0,1)$ is not countable; otherwise, there would be a countable subset that contained the entire interval.
– Raymond Chu
Jul 27 at 6:16
Well, I guess another way of looking at this proof is that no matter what countable subset of $(0,1)$ that you give me, I can always find a number not in your countable subset (in particular the $gamma$). Therefore, $(0,1)$ is not countable; otherwise, there would be a countable subset that contained the entire interval.
– Raymond Chu
Jul 27 at 6:16
add a comment |Â
up vote
0
down vote
You're right, it does show that there is not a "place" for the number created from diagonalization. So this conclusion is stating the bijection we assumed we had was not really a bijection since it missed a number. They are logically equivalent statements.
I don't quite understand the second half of your question.
answered Jul 27 at 3:39
El Gallo Negro
233
add a comment |Â
up vote
0
down vote
You're right, it does show that there is not a "place" for the number created from diagonalization. So this conclusion is stating the bijection we assumed we had was not really a bijection since it missed a number. They are logically equivalent statements.
I don't quite understand the second half of your question.
answered Jul 27 at 3:39
El Gallo Negro
233
add a comment |Â
up vote
0
down vote
up vote
0
down vote
You're right, it does show that there is not a "place" for the number created from diagonalization. So this conclusion is stating the bijection we assumed we had was not really a bijection since it missed a number. They are logically equivalent statements.
I don't quite understand the second half of your question.
answered Jul 27 at 3:39
El Gallo Negro
233
You're right, it does show that there is not a "place" for the number created from diagonalization. So this conclusion is stating the bijection we assumed we had was not really a bijection since it missed a number. They are logically equivalent statements.
I don't quite understand the second half of your question.
answered Jul 27 at 3:39
El Gallo Negro
233
answered Jul 27 at 3:39
El Gallo Negro
233
answered Jul 27 at 3:39
El Gallo Negro
233
answered Jul 27 at 3:39
El Gallo Negro
233
233
add a comment |Â
add a comment |Â
1
The proof is definitely not direct. One assumes there is a bijection from $mathbfN$ to $(0,1)$ and writes $x_n$ for the image of the natural number $n$ under this function. Then a contradiction is derived using decimal expansions of the numbers $x_n$, $ngeq 1$.
– Keenan Kidwell
Jul 27 at 3:38
I think this exact same point of confusion has been covered in earlier posts about Canto's diagonalization argument. Did you search the site?
– Jyrki Lahtonen
Jul 27 at 6:07