Mixing
Prove that set $ mathbb{Z}×mathbb{Q}$ is countably infinite by constructing a bijection from that set to...
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 '18 at 12:39
Asaf Karagila♦
302k32427757
asked Nov 22 '18 at 8:05
Gummy bearsGummy bears
1,88311431
|
show 1 more comment
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 '18 at 12:39
Asaf Karagila♦
302k32427757
asked Nov 22 '18 at 8:05
Gummy bearsGummy bears
1,88311431
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 '18 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 '18 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 '18 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 '18 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 '18 at 12:43
|
show 1 more comment
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 '18 at 12:39
Asaf Karagila♦
302k32427757
asked Nov 22 '18 at 8:05
Gummy bearsGummy bears
1,88311431
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 '18 at 12:39
Asaf Karagila♦
302k32427757
asked Nov 22 '18 at 8:05
Gummy bearsGummy bears
1,88311431
edited Nov 22 '18 at 12:39
Asaf Karagila♦
302k32427757
asked Nov 22 '18 at 8:05
Gummy bearsGummy bears
1,88311431
edited Nov 22 '18 at 12:39
Asaf Karagila♦
302k32427757
edited Nov 22 '18 at 12:39
Asaf Karagila♦
302k32427757
edited Nov 22 '18 at 12:39
Asaf Karagila♦
302k32427757
302k32427757
asked Nov 22 '18 at 8:05
Gummy bearsGummy bears
1,88311431
asked Nov 22 '18 at 8:05
Gummy bearsGummy bears
1,88311431
asked Nov 22 '18 at 8:05
Gummy bearsGummy bears
1,88311431
1,88311431
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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 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 '18 at 12:43
|
show 1 more comment
2 Answers
2
active
oldest
votes
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 '18 at 8:15
Yadati KiranYadati Kiran
1,692619
add a comment |
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 '18 at 12:52
user26857
39.3k124083
answered Nov 22 '18 at 8:26
M. SantosM. Santos
764
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
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 '18 at 8:15
Yadati KiranYadati Kiran
1,692619
add a comment |
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 '18 at 8:15
Yadati KiranYadati Kiran
1,692619
add a comment |
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 '18 at 8:15
Yadati KiranYadati Kiran
1,692619
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 '18 at 8:15
Yadati KiranYadati Kiran
1,692619
answered Nov 22 '18 at 8:15
Yadati KiranYadati Kiran
1,692619
answered Nov 22 '18 at 8:15
Yadati KiranYadati Kiran
1,692619
answered Nov 22 '18 at 8:15
Yadati KiranYadati Kiran
1,692619
1,692619
add a comment |
add a comment |
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 '18 at 12:52
user26857
39.3k124083
answered Nov 22 '18 at 8:26
M. SantosM. Santos
764
add a comment |
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 '18 at 12:52
user26857
39.3k124083
answered Nov 22 '18 at 8:26
M. SantosM. Santos
764
add a comment |
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 '18 at 12:52
user26857
39.3k124083
answered Nov 22 '18 at 8:26
M. SantosM. Santos
764
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 '18 at 12:52
user26857
39.3k124083
answered Nov 22 '18 at 8:26
M. SantosM. Santos
764
edited Nov 22 '18 at 12:52
user26857
39.3k124083
edited Nov 22 '18 at 12:52
user26857
39.3k124083
edited Nov 22 '18 at 12:52
user26857
39.3k124083
39.3k124083
answered Nov 22 '18 at 8:26
M. SantosM. Santos
764
answered Nov 22 '18 at 8:26
M. SantosM. Santos
764
answered Nov 22 '18 at 8:26
M. SantosM. Santos
764
764
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 '18 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 '18 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 '18 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 '18 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 '18 at 12:43