Prove that set $ mathbb{Z}×mathbb{Q}$ is countably infinite by constructing a bijection from that set to...
up vote
0
down vote
favorite
Prove that set $ mathbb{Z}×mathbb{Q}$ is countably infinite by constructing a bijection from that set to the natural numbers.
It's obvious that the set is countable since it is the cartesian product of two countable sets. However, I am still confused as to how we can construct a bijection. Wouldn't it be enough to construct an injection from $mathbb{Z} times mathbb{Q}$ to $mathbb{N}$?
This can be done simply by constructing a set of the manner $2^k3^p5^q...$. But how would we go about defining a bijection?
elementary-set-theory
edited Nov 22 at 12:39
Asaf Karagila♦
300k32421751
asked Nov 22 at 8:05
Gummy bears
1,86311329
|
show 1 more comment
up vote
0
down vote
favorite
Prove that set $ mathbb{Z}×mathbb{Q}$ is countably infinite by constructing a bijection from that set to the natural numbers.
It's obvious that the set is countable since it is the cartesian product of two countable sets. However, I am still confused as to how we can construct a bijection. Wouldn't it be enough to construct an injection from $mathbb{Z} times mathbb{Q}$ to $mathbb{N}$?
This can be done simply by constructing a set of the manner $2^k3^p5^q...$. But how would we go about defining a bijection?
elementary-set-theory
edited Nov 22 at 12:39
Asaf Karagila♦
300k32421751
asked Nov 22 at 8:05
Gummy bears
1,86311329
1
"It's obvious that the set is countable since it is the cartesian product of two countable sets." How is this obvious if you don't know how to construct a bijection?
– Arthur
Nov 22 at 8:07
1
@Arthur If you know that the theorem "a cartesian product of two countable sets is countable" is true, then it is obvious, from that theorem, that $mathbb Ztimes mathbb Q$ is countable. Just because OP doesn't know how to prove the statement by actually constructing the bijection, it doesn't mean that the fact that the statement is true is not obvious.
– 5xum
Nov 22 at 8:34
" Wouldn't it be enough to construct an injection ...?" - In general, yes. However, it seems you have been given an explicite task to prove it "... by constructing a bijection from that set to the natural numbers."
– Hagen von Eitzen
Nov 22 at 8:35
1
Many people spent many hours adding description to the tags. Please make sure to read them carefully when choosing your tags. (This is neither "proof verification" since you are not presenting any proof, nor about large cardinals which is a technical notion in set theory.)
– Asaf Karagila♦
Nov 22 at 12:40
1
(Also with 150 characters for a title, you should be able to do better than "Prove that a set is countable - cartesian product".)
– Asaf Karagila♦
Nov 22 at 12:43
|
show 1 more comment
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Prove that set $ mathbb{Z}×mathbb{Q}$ is countably infinite by constructing a bijection from that set to the natural numbers.
It's obvious that the set is countable since it is the cartesian product of two countable sets. However, I am still confused as to how we can construct a bijection. Wouldn't it be enough to construct an injection from $mathbb{Z} times mathbb{Q}$ to $mathbb{N}$?
This can be done simply by constructing a set of the manner $2^k3^p5^q...$. But how would we go about defining a bijection?
elementary-set-theory
edited Nov 22 at 12:39
Asaf Karagila♦
300k32421751
asked Nov 22 at 8:05
Gummy bears
1,86311329
Prove that set $ mathbb{Z}×mathbb{Q}$ is countably infinite by constructing a bijection from that set to the natural numbers.
It's obvious that the set is countable since it is the cartesian product of two countable sets. However, I am still confused as to how we can construct a bijection. Wouldn't it be enough to construct an injection from $mathbb{Z} times mathbb{Q}$ to $mathbb{N}$?
This can be done simply by constructing a set of the manner $2^k3^p5^q...$. But how would we go about defining a bijection?
elementary-set-theory
elementary-set-theory
edited Nov 22 at 12:39
Asaf Karagila♦
300k32421751
asked Nov 22 at 8:05
Gummy bears
1,86311329
edited Nov 22 at 12:39
Asaf Karagila♦
300k32421751
asked Nov 22 at 8:05
Gummy bears
1,86311329
edited Nov 22 at 12:39
Asaf Karagila♦
300k32421751
edited Nov 22 at 12:39
Asaf Karagila♦
300k32421751
edited Nov 22 at 12:39
Asaf Karagila♦
300k32421751
300k32421751
asked Nov 22 at 8:05
Gummy bears
1,86311329
asked Nov 22 at 8:05
Gummy bears
1,86311329
asked Nov 22 at 8:05
Gummy bears
1,86311329
1,86311329
1
"It's obvious that the set is countable since it is the cartesian product of two countable sets." How is this obvious if you don't know how to construct a bijection?
– Arthur
Nov 22 at 8:07
1
@Arthur If you know that the theorem "a cartesian product of two countable sets is countable" is true, then it is obvious, from that theorem, that $mathbb Ztimes mathbb Q$ is countable. Just because OP doesn't know how to prove the statement by actually constructing the bijection, it doesn't mean that the fact that the statement is true is not obvious.
– 5xum
Nov 22 at 8:34
" Wouldn't it be enough to construct an injection ...?" - In general, yes. However, it seems you have been given an explicite task to prove it "... by constructing a bijection from that set to the natural numbers."
– Hagen von Eitzen
Nov 22 at 8:35
1
Many people spent many hours adding description to the tags. Please make sure to read them carefully when choosing your tags. (This is neither "proof verification" since you are not presenting any proof, nor about large cardinals which is a technical notion in set theory.)
– Asaf Karagila♦
Nov 22 at 12:40
1
(Also with 150 characters for a title, you should be able to do better than "Prove that a set is countable - cartesian product".)
– Asaf Karagila♦
Nov 22 at 12:43
|
show 1 more comment
1
"It's obvious that the set is countable since it is the cartesian product of two countable sets." How is this obvious if you don't know how to construct a bijection?
– Arthur
Nov 22 at 8:07
1
@Arthur If you know that the theorem "a cartesian product of two countable sets is countable" is true, then it is obvious, from that theorem, that $mathbb Ztimes mathbb Q$ is countable. Just because OP doesn't know how to prove the statement by actually constructing the bijection, it doesn't mean that the fact that the statement is true is not obvious.
– 5xum
Nov 22 at 8:34
" Wouldn't it be enough to construct an injection ...?" - In general, yes. However, it seems you have been given an explicite task to prove it "... by constructing a bijection from that set to the natural numbers."
– Hagen von Eitzen
Nov 22 at 8:35
1
Many people spent many hours adding description to the tags. Please make sure to read them carefully when choosing your tags. (This is neither "proof verification" since you are not presenting any proof, nor about large cardinals which is a technical notion in set theory.)
– Asaf Karagila♦
Nov 22 at 12:40
1
(Also with 150 characters for a title, you should be able to do better than "Prove that a set is countable - cartesian product".)
– Asaf Karagila♦
Nov 22 at 12:43
1
1
"It's obvious that the set is countable since it is the cartesian product of two countable sets." How is this obvious if you don't know how to construct a bijection?
– Arthur
Nov 22 at 8:07
"It's obvious that the set is countable since it is the cartesian product of two countable sets." How is this obvious if you don't know how to construct a bijection?
– Arthur
Nov 22 at 8:07
1
1
@Arthur If you know that the theorem "a cartesian product of two countable sets is countable" is true, then it is obvious, from that theorem, that $mathbb Ztimes mathbb Q$ is countable. Just because OP doesn't know how to prove the statement by actually constructing the bijection, it doesn't mean that the fact that the statement is true is not obvious.
– 5xum
Nov 22 at 8:34
@Arthur If you know that the theorem "a cartesian product of two countable sets is countable" is true, then it is obvious, from that theorem, that $mathbb Ztimes mathbb Q$ is countable. Just because OP doesn't know how to prove the statement by actually constructing the bijection, it doesn't mean that the fact that the statement is true is not obvious.
– 5xum
Nov 22 at 8:34
" Wouldn't it be enough to construct an injection ...?" - In general, yes. However, it seems you have been given an explicite task to prove it "... by constructing a bijection from that set to the natural numbers."
– Hagen von Eitzen
Nov 22 at 8:35
" Wouldn't it be enough to construct an injection ...?" - In general, yes. However, it seems you have been given an explicite task to prove it "... by constructing a bijection from that set to the natural numbers."
– Hagen von Eitzen
Nov 22 at 8:35
1
1
Many people spent many hours adding description to the tags. Please make sure to read them carefully when choosing your tags. (This is neither "proof verification" since you are not presenting any proof, nor about large cardinals which is a technical notion in set theory.)
– Asaf Karagila♦
Nov 22 at 12:40
Many people spent many hours adding description to the tags. Please make sure to read them carefully when choosing your tags. (This is neither "proof verification" since you are not presenting any proof, nor about large cardinals which is a technical notion in set theory.)
– Asaf Karagila♦
Nov 22 at 12:40
1
1
(Also with 150 characters for a title, you should be able to do better than "Prove that a set is countable - cartesian product".)
– Asaf Karagila♦
Nov 22 at 12:43
(Also with 150 characters for a title, you should be able to do better than "Prove that a set is countable - cartesian product".)
– Asaf Karagila♦
Nov 22 at 12:43
|
show 1 more comment
2 Answers
2
active
oldest
votes
up vote
0
down vote
Take the map $left(m,dfrac pqright)rightarrow (m,p,q) quad p,q,minmathbb{Z}:$
i.e. mapping $mathbb{Z}timesmathbb{Q} rightarrow mathbb{Z}timesmathbb{Z}timesmathbb{Z}$. Assuming you know finite (countable as well) union of countable sets is countable, the result follows.
answered Nov 22 at 8:15
Yadati Kiran
1,282317
add a comment |
up vote
0
down vote
Hint: every natural can be expressed as $2^{n-1}m$, with $n, m ≥ 1$, where $m$ is odd. Try to construct a bijection $f: mathbb{N}timesmathbb{N} to mathbb{N}$ thinking about that.
Alternatively, the result that given a injection from $A$ to $B$ and another one from $B$ to $A$ there exists a bijection between the two sets is the content of the Schröder-Bernstein theorem.
edited Nov 22 at 12:52
user26857
39.1k123882
answered Nov 22 at 8:26
M. Santos
564
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
Take the map $left(m,dfrac pqright)rightarrow (m,p,q) quad p,q,minmathbb{Z}:$
i.e. mapping $mathbb{Z}timesmathbb{Q} rightarrow mathbb{Z}timesmathbb{Z}timesmathbb{Z}$. Assuming you know finite (countable as well) union of countable sets is countable, the result follows.
answered Nov 22 at 8:15
Yadati Kiran
1,282317
add a comment |
up vote
0
down vote
Take the map $left(m,dfrac pqright)rightarrow (m,p,q) quad p,q,minmathbb{Z}:$
i.e. mapping $mathbb{Z}timesmathbb{Q} rightarrow mathbb{Z}timesmathbb{Z}timesmathbb{Z}$. Assuming you know finite (countable as well) union of countable sets is countable, the result follows.
answered Nov 22 at 8:15
Yadati Kiran
1,282317
add a comment |
up vote
0
down vote
up vote
0
down vote
Take the map $left(m,dfrac pqright)rightarrow (m,p,q) quad p,q,minmathbb{Z}:$
i.e. mapping $mathbb{Z}timesmathbb{Q} rightarrow mathbb{Z}timesmathbb{Z}timesmathbb{Z}$. Assuming you know finite (countable as well) union of countable sets is countable, the result follows.
answered Nov 22 at 8:15
Yadati Kiran
1,282317
Take the map $left(m,dfrac pqright)rightarrow (m,p,q) quad p,q,minmathbb{Z}:$
i.e. mapping $mathbb{Z}timesmathbb{Q} rightarrow mathbb{Z}timesmathbb{Z}timesmathbb{Z}$. Assuming you know finite (countable as well) union of countable sets is countable, the result follows.
answered Nov 22 at 8:15
Yadati Kiran
1,282317
answered Nov 22 at 8:15
Yadati Kiran
1,282317
answered Nov 22 at 8:15
Yadati Kiran
1,282317
answered Nov 22 at 8:15
Yadati Kiran
1,282317
1,282317
add a comment |
add a comment |
up vote
0
down vote
Hint: every natural can be expressed as $2^{n-1}m$, with $n, m ≥ 1$, where $m$ is odd. Try to construct a bijection $f: mathbb{N}timesmathbb{N} to mathbb{N}$ thinking about that.
Alternatively, the result that given a injection from $A$ to $B$ and another one from $B$ to $A$ there exists a bijection between the two sets is the content of the Schröder-Bernstein theorem.
edited Nov 22 at 12:52
user26857
39.1k123882
answered Nov 22 at 8:26
M. Santos
564
add a comment |
up vote
0
down vote
Hint: every natural can be expressed as $2^{n-1}m$, with $n, m ≥ 1$, where $m$ is odd. Try to construct a bijection $f: mathbb{N}timesmathbb{N} to mathbb{N}$ thinking about that.
Alternatively, the result that given a injection from $A$ to $B$ and another one from $B$ to $A$ there exists a bijection between the two sets is the content of the Schröder-Bernstein theorem.
edited Nov 22 at 12:52
user26857
39.1k123882
answered Nov 22 at 8:26
M. Santos
564
add a comment |
up vote
0
down vote
up vote
0
down vote
Hint: every natural can be expressed as $2^{n-1}m$, with $n, m ≥ 1$, where $m$ is odd. Try to construct a bijection $f: mathbb{N}timesmathbb{N} to mathbb{N}$ thinking about that.
Alternatively, the result that given a injection from $A$ to $B$ and another one from $B$ to $A$ there exists a bijection between the two sets is the content of the Schröder-Bernstein theorem.
edited Nov 22 at 12:52
user26857
39.1k123882
answered Nov 22 at 8:26
M. Santos
564
Hint: every natural can be expressed as $2^{n-1}m$, with $n, m ≥ 1$, where $m$ is odd. Try to construct a bijection $f: mathbb{N}timesmathbb{N} to mathbb{N}$ thinking about that.
Alternatively, the result that given a injection from $A$ to $B$ and another one from $B$ to $A$ there exists a bijection between the two sets is the content of the Schröder-Bernstein theorem.
edited Nov 22 at 12:52
user26857
39.1k123882
answered Nov 22 at 8:26
M. Santos
564
edited Nov 22 at 12:52
user26857
39.1k123882
edited Nov 22 at 12:52
user26857
39.1k123882
edited Nov 22 at 12:52
user26857
39.1k123882
39.1k123882
answered Nov 22 at 8:26
M. Santos
564
answered Nov 22 at 8:26
M. Santos
564
answered Nov 22 at 8:26
M. Santos
564
564
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3008864%2fprove-that-set-mathbbz%25c3%2597-mathbbq-is-countably-in%25ef%25ac%2581nite-by-constructing-a-b%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
"It's obvious that the set is countable since it is the cartesian product of two countable sets." How is this obvious if you don't know how to construct a bijection?
– Arthur
Nov 22 at 8:07
1
@Arthur If you know that the theorem "a cartesian product of two countable sets is countable" is true, then it is obvious, from that theorem, that $mathbb Ztimes mathbb Q$ is countable. Just because OP doesn't know how to prove the statement by actually constructing the bijection, it doesn't mean that the fact that the statement is true is not obvious.
– 5xum
Nov 22 at 8:34
" Wouldn't it be enough to construct an injection ...?" - In general, yes. However, it seems you have been given an explicite task to prove it "... by constructing a bijection from that set to the natural numbers."
– Hagen von Eitzen
Nov 22 at 8:35
1
Many people spent many hours adding description to the tags. Please make sure to read them carefully when choosing your tags. (This is neither "proof verification" since you are not presenting any proof, nor about large cardinals which is a technical notion in set theory.)
– Asaf Karagila♦
Nov 22 at 12:40
1
(Also with 150 characters for a title, you should be able to do better than "Prove that a set is countable - cartesian product".)
– Asaf Karagila♦
Nov 22 at 12:43