Mixing
Constructing a Bijection to Demonstrate Countably Infinite Set
I'm looking to prove that $mathbb{Z} times mathbb{Q}$ is countably infinite by constructing a bijection $f: mathbb{Z} times mathbb{Q} rightarrow mathbb{N}$. I understand that I can demonstrate $mathbb{Z} times mathbb{Q}$ is countably infinite by showing that $mathbb{Z}$ and $mathbb{Q}$ individually are countably infinite, and thus it follows that their Cartesian product is countably infinite. However, I was more curious how one would construct a bijection to prove this, since by definition one must exist.
elementary-set-theory cardinals
edited Nov 22 '18 at 3:41
Andrés E. Caicedo
64.9k8158246
asked Nov 22 '18 at 2:40
rcmpgrcrcmpgrc
174
add a comment |
I'm looking to prove that $mathbb{Z} times mathbb{Q}$ is countably infinite by constructing a bijection $f: mathbb{Z} times mathbb{Q} rightarrow mathbb{N}$. I understand that I can demonstrate $mathbb{Z} times mathbb{Q}$ is countably infinite by showing that $mathbb{Z}$ and $mathbb{Q}$ individually are countably infinite, and thus it follows that their Cartesian product is countably infinite. However, I was more curious how one would construct a bijection to prove this, since by definition one must exist.
elementary-set-theory cardinals
edited Nov 22 '18 at 3:41
Andrés E. Caicedo
64.9k8158246
asked Nov 22 '18 at 2:40
rcmpgrcrcmpgrc
174
add a comment |
I'm looking to prove that $mathbb{Z} times mathbb{Q}$ is countably infinite by constructing a bijection $f: mathbb{Z} times mathbb{Q} rightarrow mathbb{N}$. I understand that I can demonstrate $mathbb{Z} times mathbb{Q}$ is countably infinite by showing that $mathbb{Z}$ and $mathbb{Q}$ individually are countably infinite, and thus it follows that their Cartesian product is countably infinite. However, I was more curious how one would construct a bijection to prove this, since by definition one must exist.
elementary-set-theory cardinals
edited Nov 22 '18 at 3:41
Andrés E. Caicedo
64.9k8158246
asked Nov 22 '18 at 2:40
rcmpgrcrcmpgrc
174
I'm looking to prove that $mathbb{Z} times mathbb{Q}$ is countably infinite by constructing a bijection $f: mathbb{Z} times mathbb{Q} rightarrow mathbb{N}$. I understand that I can demonstrate $mathbb{Z} times mathbb{Q}$ is countably infinite by showing that $mathbb{Z}$ and $mathbb{Q}$ individually are countably infinite, and thus it follows that their Cartesian product is countably infinite. However, I was more curious how one would construct a bijection to prove this, since by definition one must exist.
elementary-set-theory cardinals
elementary-set-theory cardinals
edited Nov 22 '18 at 3:41
Andrés E. Caicedo
64.9k8158246
asked Nov 22 '18 at 2:40
rcmpgrcrcmpgrc
174
edited Nov 22 '18 at 3:41
Andrés E. Caicedo
64.9k8158246
asked Nov 22 '18 at 2:40
rcmpgrcrcmpgrc
174
edited Nov 22 '18 at 3:41
Andrés E. Caicedo
64.9k8158246
edited Nov 22 '18 at 3:41
Andrés E. Caicedo
64.9k8158246
edited Nov 22 '18 at 3:41
Andrés E. Caicedo
64.9k8158246
64.9k8158246
asked Nov 22 '18 at 2:40
rcmpgrcrcmpgrc
174
asked Nov 22 '18 at 2:40
rcmpgrcrcmpgrc
174
asked Nov 22 '18 at 2:40
rcmpgrcrcmpgrc
174
174
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
The existence of a bijection $b: mathbb{N}timesmathbb{N}rightarrowmathbb{N}$ - say, the Cantor pairing function - is the thing to understand. If $A,B$ are countable, then we have injections $i,j: A,Brightarrowmathbb{N}$; we can use $b$ to "glue them together" to get an injection $m:Atimes Brightarrowmathbb{N}$, given by $$m:Atimes Brightarrowmathbb{N}:(x,y)mapsto b(i(x),j(y)).$$ If $i$ and $j$ are each bijective, then $m$ is a bijection.
Exercise: check the various claims I've made in the previous paragraph!
So the point is that once you've picked your pairing function $b$, and your bijections $mathbb{Z}rightarrowmathbb{N}$ and $mathbb{Q}rightarrowmathbb{N}$, you've already got all the ingredients needed to give a bijection $mathbb{Z}timesmathbb{Q}rightarrowmathbb{N}$. It is worth noting that there's no reason to expect the resulting bijection to be nice - indeed, is there even a nice bijection between $mathbb{Q}$ and $mathbb{N}$? (OK fine, that's totally subjective, but my point is that we shouldn't hope for an easy-to-write-down example of the type of bijection we know must exist.)
answered Nov 22 '18 at 2:55
Noah SchweberNoah Schweber
122k10149284
add a comment |
It is not hard to construct explicitly an injective function $fcolon
mathbf{Z}times mathbf{Q}tomathbf{N}$. For this we will use base 13 representation of elements in the codomain. We need symbols (digits) to represent numbers 10, 11 and 12. Let us agree to use $t, e, w$ for that purpose.
Now take an element in the domain, e.g., $x=(-7, 308/17)$ we define $f(x)$ as below: stripping away the parentheses $x$ is the string of symbols: $-7, 308/17$. Now in this replace minus sign by $t$, comma by $e$ and slash by $w$ getting $f(x)=t7e308w17$. This expression is a number in base 13 (hence a non-negative integer). As two different strings of digits represent two different integers we see that $f$ indeed is an injection to non-negative integers.
answered Nov 22 '18 at 3:11
P VanchinathanP Vanchinathan
14.9k12136
add a comment |
If you have formulas for bijections $mathbb N mapsto mathbb Z$ and $mathbb N mapsto mathbb Q$, then the proof that $mathbb Z times mathbb Q$ is countable will give you a formula for a bijection $mathbb N mapsto mathbb Z times mathbb Q$.
answered Nov 22 '18 at 4:37
Lee MosherLee Mosher
48.2k33681
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%2f3008675%2fconstructing-a-bijection-to-demonstrate-countably-infinite-set%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
The existence of a bijection $b: mathbb{N}timesmathbb{N}rightarrowmathbb{N}$ - say, the Cantor pairing function - is the thing to understand. If $A,B$ are countable, then we have injections $i,j: A,Brightarrowmathbb{N}$; we can use $b$ to "glue them together" to get an injection $m:Atimes Brightarrowmathbb{N}$, given by $$m:Atimes Brightarrowmathbb{N}:(x,y)mapsto b(i(x),j(y)).$$ If $i$ and $j$ are each bijective, then $m$ is a bijection.
Exercise: check the various claims I've made in the previous paragraph!
So the point is that once you've picked your pairing function $b$, and your bijections $mathbb{Z}rightarrowmathbb{N}$ and $mathbb{Q}rightarrowmathbb{N}$, you've already got all the ingredients needed to give a bijection $mathbb{Z}timesmathbb{Q}rightarrowmathbb{N}$. It is worth noting that there's no reason to expect the resulting bijection to be nice - indeed, is there even a nice bijection between $mathbb{Q}$ and $mathbb{N}$? (OK fine, that's totally subjective, but my point is that we shouldn't hope for an easy-to-write-down example of the type of bijection we know must exist.)
answered Nov 22 '18 at 2:55
Noah SchweberNoah Schweber
122k10149284
add a comment |
The existence of a bijection $b: mathbb{N}timesmathbb{N}rightarrowmathbb{N}$ - say, the Cantor pairing function - is the thing to understand. If $A,B$ are countable, then we have injections $i,j: A,Brightarrowmathbb{N}$; we can use $b$ to "glue them together" to get an injection $m:Atimes Brightarrowmathbb{N}$, given by $$m:Atimes Brightarrowmathbb{N}:(x,y)mapsto b(i(x),j(y)).$$ If $i$ and $j$ are each bijective, then $m$ is a bijection.
Exercise: check the various claims I've made in the previous paragraph!
So the point is that once you've picked your pairing function $b$, and your bijections $mathbb{Z}rightarrowmathbb{N}$ and $mathbb{Q}rightarrowmathbb{N}$, you've already got all the ingredients needed to give a bijection $mathbb{Z}timesmathbb{Q}rightarrowmathbb{N}$. It is worth noting that there's no reason to expect the resulting bijection to be nice - indeed, is there even a nice bijection between $mathbb{Q}$ and $mathbb{N}$? (OK fine, that's totally subjective, but my point is that we shouldn't hope for an easy-to-write-down example of the type of bijection we know must exist.)
answered Nov 22 '18 at 2:55
Noah SchweberNoah Schweber
122k10149284
add a comment |
The existence of a bijection $b: mathbb{N}timesmathbb{N}rightarrowmathbb{N}$ - say, the Cantor pairing function - is the thing to understand. If $A,B$ are countable, then we have injections $i,j: A,Brightarrowmathbb{N}$; we can use $b$ to "glue them together" to get an injection $m:Atimes Brightarrowmathbb{N}$, given by $$m:Atimes Brightarrowmathbb{N}:(x,y)mapsto b(i(x),j(y)).$$ If $i$ and $j$ are each bijective, then $m$ is a bijection.
Exercise: check the various claims I've made in the previous paragraph!
So the point is that once you've picked your pairing function $b$, and your bijections $mathbb{Z}rightarrowmathbb{N}$ and $mathbb{Q}rightarrowmathbb{N}$, you've already got all the ingredients needed to give a bijection $mathbb{Z}timesmathbb{Q}rightarrowmathbb{N}$. It is worth noting that there's no reason to expect the resulting bijection to be nice - indeed, is there even a nice bijection between $mathbb{Q}$ and $mathbb{N}$? (OK fine, that's totally subjective, but my point is that we shouldn't hope for an easy-to-write-down example of the type of bijection we know must exist.)
answered Nov 22 '18 at 2:55
Noah SchweberNoah Schweber
122k10149284
The existence of a bijection $b: mathbb{N}timesmathbb{N}rightarrowmathbb{N}$ - say, the Cantor pairing function - is the thing to understand. If $A,B$ are countable, then we have injections $i,j: A,Brightarrowmathbb{N}$; we can use $b$ to "glue them together" to get an injection $m:Atimes Brightarrowmathbb{N}$, given by $$m:Atimes Brightarrowmathbb{N}:(x,y)mapsto b(i(x),j(y)).$$ If $i$ and $j$ are each bijective, then $m$ is a bijection.
Exercise: check the various claims I've made in the previous paragraph!
So the point is that once you've picked your pairing function $b$, and your bijections $mathbb{Z}rightarrowmathbb{N}$ and $mathbb{Q}rightarrowmathbb{N}$, you've already got all the ingredients needed to give a bijection $mathbb{Z}timesmathbb{Q}rightarrowmathbb{N}$. It is worth noting that there's no reason to expect the resulting bijection to be nice - indeed, is there even a nice bijection between $mathbb{Q}$ and $mathbb{N}$? (OK fine, that's totally subjective, but my point is that we shouldn't hope for an easy-to-write-down example of the type of bijection we know must exist.)
answered Nov 22 '18 at 2:55
Noah SchweberNoah Schweber
122k10149284
answered Nov 22 '18 at 2:55
Noah SchweberNoah Schweber
122k10149284
answered Nov 22 '18 at 2:55
Noah SchweberNoah Schweber
122k10149284
answered Nov 22 '18 at 2:55
Noah SchweberNoah Schweber
122k10149284
122k10149284
add a comment |
add a comment |
It is not hard to construct explicitly an injective function $fcolon
mathbf{Z}times mathbf{Q}tomathbf{N}$. For this we will use base 13 representation of elements in the codomain. We need symbols (digits) to represent numbers 10, 11 and 12. Let us agree to use $t, e, w$ for that purpose.
Now take an element in the domain, e.g., $x=(-7, 308/17)$ we define $f(x)$ as below: stripping away the parentheses $x$ is the string of symbols: $-7, 308/17$. Now in this replace minus sign by $t$, comma by $e$ and slash by $w$ getting $f(x)=t7e308w17$. This expression is a number in base 13 (hence a non-negative integer). As two different strings of digits represent two different integers we see that $f$ indeed is an injection to non-negative integers.
answered Nov 22 '18 at 3:11
P VanchinathanP Vanchinathan
14.9k12136
add a comment |
It is not hard to construct explicitly an injective function $fcolon
mathbf{Z}times mathbf{Q}tomathbf{N}$. For this we will use base 13 representation of elements in the codomain. We need symbols (digits) to represent numbers 10, 11 and 12. Let us agree to use $t, e, w$ for that purpose.
Now take an element in the domain, e.g., $x=(-7, 308/17)$ we define $f(x)$ as below: stripping away the parentheses $x$ is the string of symbols: $-7, 308/17$. Now in this replace minus sign by $t$, comma by $e$ and slash by $w$ getting $f(x)=t7e308w17$. This expression is a number in base 13 (hence a non-negative integer). As two different strings of digits represent two different integers we see that $f$ indeed is an injection to non-negative integers.
answered Nov 22 '18 at 3:11
P VanchinathanP Vanchinathan
14.9k12136
add a comment |
It is not hard to construct explicitly an injective function $fcolon
mathbf{Z}times mathbf{Q}tomathbf{N}$. For this we will use base 13 representation of elements in the codomain. We need symbols (digits) to represent numbers 10, 11 and 12. Let us agree to use $t, e, w$ for that purpose.
Now take an element in the domain, e.g., $x=(-7, 308/17)$ we define $f(x)$ as below: stripping away the parentheses $x$ is the string of symbols: $-7, 308/17$. Now in this replace minus sign by $t$, comma by $e$ and slash by $w$ getting $f(x)=t7e308w17$. This expression is a number in base 13 (hence a non-negative integer). As two different strings of digits represent two different integers we see that $f$ indeed is an injection to non-negative integers.
answered Nov 22 '18 at 3:11
P VanchinathanP Vanchinathan
14.9k12136
It is not hard to construct explicitly an injective function $fcolon
mathbf{Z}times mathbf{Q}tomathbf{N}$. For this we will use base 13 representation of elements in the codomain. We need symbols (digits) to represent numbers 10, 11 and 12. Let us agree to use $t, e, w$ for that purpose.
Now take an element in the domain, e.g., $x=(-7, 308/17)$ we define $f(x)$ as below: stripping away the parentheses $x$ is the string of symbols: $-7, 308/17$. Now in this replace minus sign by $t$, comma by $e$ and slash by $w$ getting $f(x)=t7e308w17$. This expression is a number in base 13 (hence a non-negative integer). As two different strings of digits represent two different integers we see that $f$ indeed is an injection to non-negative integers.
answered Nov 22 '18 at 3:11
P VanchinathanP Vanchinathan
14.9k12136
answered Nov 22 '18 at 3:11
P VanchinathanP Vanchinathan
14.9k12136
answered Nov 22 '18 at 3:11
P VanchinathanP Vanchinathan
14.9k12136
answered Nov 22 '18 at 3:11
P VanchinathanP Vanchinathan
14.9k12136
14.9k12136
add a comment |
add a comment |
If you have formulas for bijections $mathbb N mapsto mathbb Z$ and $mathbb N mapsto mathbb Q$, then the proof that $mathbb Z times mathbb Q$ is countable will give you a formula for a bijection $mathbb N mapsto mathbb Z times mathbb Q$.
answered Nov 22 '18 at 4:37
Lee MosherLee Mosher
48.2k33681
add a comment |
If you have formulas for bijections $mathbb N mapsto mathbb Z$ and $mathbb N mapsto mathbb Q$, then the proof that $mathbb Z times mathbb Q$ is countable will give you a formula for a bijection $mathbb N mapsto mathbb Z times mathbb Q$.
answered Nov 22 '18 at 4:37
Lee MosherLee Mosher
48.2k33681
add a comment |
If you have formulas for bijections $mathbb N mapsto mathbb Z$ and $mathbb N mapsto mathbb Q$, then the proof that $mathbb Z times mathbb Q$ is countable will give you a formula for a bijection $mathbb N mapsto mathbb Z times mathbb Q$.
answered Nov 22 '18 at 4:37
Lee MosherLee Mosher
48.2k33681
If you have formulas for bijections $mathbb N mapsto mathbb Z$ and $mathbb N mapsto mathbb Q$, then the proof that $mathbb Z times mathbb Q$ is countable will give you a formula for a bijection $mathbb N mapsto mathbb Z times mathbb Q$.
answered Nov 22 '18 at 4:37
Lee MosherLee Mosher
48.2k33681
answered Nov 22 '18 at 4:37
Lee MosherLee Mosher
48.2k33681
answered Nov 22 '18 at 4:37
Lee MosherLee Mosher
48.2k33681
answered Nov 22 '18 at 4:37
Lee MosherLee Mosher
48.2k33681
48.2k33681
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%2f3008675%2fconstructing-a-bijection-to-demonstrate-countably-infinite-set%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
