Construct bijections of given sets to show that they have the same cardinality and prove they are correct
$begingroup$
I need to construct bijections of few sets to show that they have the same cardinality and prove their correctness. I have already done $f: mathbb{N}rightarrowmathbb{Z}$, which was not very hard, but I am struggling with a bit more complex examples.
In the following examples $a bot b$ means, that $a$ and $b$ are coprime numbers.
Ex. 1:
$mathbb{N}$ and ${langle n,mrangle in mathbb{N}^+timesmathbb{N}^+ :|: mbot n}$
It should be a function of the form $g: mathbb{N}rightarrow mathbb{N}^+times mathbb{N}^+$, but I do not know how should a function of one number create a pair of coprime numbers.
Ex. 2:
${langle n,mrangle in mathbb{N}^+timesmathbb{N}^+ :|: mbot n}$ and $mathbb{Q}^+$
There the function should have the form $h:mathbb{N}^+timesmathbb{N}^+rightarrow mathbb{Q}^+$ and I was thinking about a function which would divide $n$ by $m$, which in my opinion would be pretty understandable, but I am not sure whether it is a correct idea.
I would like to get some tips how should I get a grasp in solving such problems, as well as some hints how to solve and prove these two examples.
elementary-set-theory
asked Jan 6 at 13:05
whiskeyowhiskeyo
1107
$endgroup$
add a comment |
$begingroup$
I need to construct bijections of few sets to show that they have the same cardinality and prove their correctness. I have already done $f: mathbb{N}rightarrowmathbb{Z}$, which was not very hard, but I am struggling with a bit more complex examples.
In the following examples $a bot b$ means, that $a$ and $b$ are coprime numbers.
Ex. 1:
$mathbb{N}$ and ${langle n,mrangle in mathbb{N}^+timesmathbb{N}^+ :|: mbot n}$
It should be a function of the form $g: mathbb{N}rightarrow mathbb{N}^+times mathbb{N}^+$, but I do not know how should a function of one number create a pair of coprime numbers.
Ex. 2:
${langle n,mrangle in mathbb{N}^+timesmathbb{N}^+ :|: mbot n}$ and $mathbb{Q}^+$
There the function should have the form $h:mathbb{N}^+timesmathbb{N}^+rightarrow mathbb{Q}^+$ and I was thinking about a function which would divide $n$ by $m$, which in my opinion would be pretty understandable, but I am not sure whether it is a correct idea.
I would like to get some tips how should I get a grasp in solving such problems, as well as some hints how to solve and prove these two examples.
elementary-set-theory
asked Jan 6 at 13:05
whiskeyowhiskeyo
1107
$endgroup$
$begingroup$
No, sadly my lectures did not involve them.
$endgroup$
– whiskeyo
Jan 6 at 13:10
1
$begingroup$
For the general problem, it's useful to know constructive proofs of the Cantor-Schröder-Berstein theorem, but I suspect that in these exercises you're supposed to come out with the appropriate bijection out of thin air.
$endgroup$
– Git Gud
Jan 6 at 13:25
$begingroup$
Hint: For Ex.1 do you know of that diagonal argument that proves that (for example) $mathbb{Q}$ is countable, or that $mathbb{N}^{2}$ has the same cardinality as $mathbb{N}$. If so can you adapt that proof?
$endgroup$
– Adam Higgins
Jan 6 at 13:51
add a comment |
$begingroup$
I need to construct bijections of few sets to show that they have the same cardinality and prove their correctness. I have already done $f: mathbb{N}rightarrowmathbb{Z}$, which was not very hard, but I am struggling with a bit more complex examples.
In the following examples $a bot b$ means, that $a$ and $b$ are coprime numbers.
Ex. 1:
$mathbb{N}$ and ${langle n,mrangle in mathbb{N}^+timesmathbb{N}^+ :|: mbot n}$
It should be a function of the form $g: mathbb{N}rightarrow mathbb{N}^+times mathbb{N}^+$, but I do not know how should a function of one number create a pair of coprime numbers.
Ex. 2:
${langle n,mrangle in mathbb{N}^+timesmathbb{N}^+ :|: mbot n}$ and $mathbb{Q}^+$
There the function should have the form $h:mathbb{N}^+timesmathbb{N}^+rightarrow mathbb{Q}^+$ and I was thinking about a function which would divide $n$ by $m$, which in my opinion would be pretty understandable, but I am not sure whether it is a correct idea.
I would like to get some tips how should I get a grasp in solving such problems, as well as some hints how to solve and prove these two examples.
elementary-set-theory
asked Jan 6 at 13:05
whiskeyowhiskeyo
1107
$endgroup$
I need to construct bijections of few sets to show that they have the same cardinality and prove their correctness. I have already done $f: mathbb{N}rightarrowmathbb{Z}$, which was not very hard, but I am struggling with a bit more complex examples.
In the following examples $a bot b$ means, that $a$ and $b$ are coprime numbers.
Ex. 1:
$mathbb{N}$ and ${langle n,mrangle in mathbb{N}^+timesmathbb{N}^+ :|: mbot n}$
It should be a function of the form $g: mathbb{N}rightarrow mathbb{N}^+times mathbb{N}^+$, but I do not know how should a function of one number create a pair of coprime numbers.
Ex. 2:
${langle n,mrangle in mathbb{N}^+timesmathbb{N}^+ :|: mbot n}$ and $mathbb{Q}^+$
There the function should have the form $h:mathbb{N}^+timesmathbb{N}^+rightarrow mathbb{Q}^+$ and I was thinking about a function which would divide $n$ by $m$, which in my opinion would be pretty understandable, but I am not sure whether it is a correct idea.
I would like to get some tips how should I get a grasp in solving such problems, as well as some hints how to solve and prove these two examples.
elementary-set-theory
elementary-set-theory
asked Jan 6 at 13:05
whiskeyowhiskeyo
1107
asked Jan 6 at 13:05
whiskeyowhiskeyo
1107
edited Jan 13 at 22:18
whiskeyo
asked Jan 6 at 13:05
whiskeyowhiskeyo
1107
asked Jan 6 at 13:05
whiskeyowhiskeyo
1107
asked Jan 6 at 13:05
whiskeyowhiskeyo
1107
1107
$begingroup$
No, sadly my lectures did not involve them.
$endgroup$
– whiskeyo
Jan 6 at 13:10
1
$begingroup$
For the general problem, it's useful to know constructive proofs of the Cantor-Schröder-Berstein theorem, but I suspect that in these exercises you're supposed to come out with the appropriate bijection out of thin air.
$endgroup$
– Git Gud
Jan 6 at 13:25
$begingroup$
Hint: For Ex.1 do you know of that diagonal argument that proves that (for example) $mathbb{Q}$ is countable, or that $mathbb{N}^{2}$ has the same cardinality as $mathbb{N}$. If so can you adapt that proof?
$endgroup$
– Adam Higgins
Jan 6 at 13:51
add a comment |
$begingroup$
No, sadly my lectures did not involve them.
$endgroup$
– whiskeyo
Jan 6 at 13:10
1
$begingroup$
For the general problem, it's useful to know constructive proofs of the Cantor-Schröder-Berstein theorem, but I suspect that in these exercises you're supposed to come out with the appropriate bijection out of thin air.
$endgroup$
– Git Gud
Jan 6 at 13:25
$begingroup$
Hint: For Ex.1 do you know of that diagonal argument that proves that (for example) $mathbb{Q}$ is countable, or that $mathbb{N}^{2}$ has the same cardinality as $mathbb{N}$. If so can you adapt that proof?
$endgroup$
– Adam Higgins
Jan 6 at 13:51
$begingroup$
No, sadly my lectures did not involve them.
$endgroup$
– whiskeyo
Jan 6 at 13:10
$begingroup$
No, sadly my lectures did not involve them.
$endgroup$
– whiskeyo
Jan 6 at 13:10
1
1
$begingroup$
For the general problem, it's useful to know constructive proofs of the Cantor-Schröder-Berstein theorem, but I suspect that in these exercises you're supposed to come out with the appropriate bijection out of thin air.
$endgroup$
– Git Gud
Jan 6 at 13:25
$begingroup$
For the general problem, it's useful to know constructive proofs of the Cantor-Schröder-Berstein theorem, but I suspect that in these exercises you're supposed to come out with the appropriate bijection out of thin air.
$endgroup$
– Git Gud
Jan 6 at 13:25
$begingroup$
Hint: For Ex.1 do you know of that diagonal argument that proves that (for example) $mathbb{Q}$ is countable, or that $mathbb{N}^{2}$ has the same cardinality as $mathbb{N}$. If so can you adapt that proof?
$endgroup$
– Adam Higgins
Jan 6 at 13:51
$begingroup$
Hint: For Ex.1 do you know of that diagonal argument that proves that (for example) $mathbb{Q}$ is countable, or that $mathbb{N}^{2}$ has the same cardinality as $mathbb{N}$. If so can you adapt that proof?
$endgroup$
– Adam Higgins
Jan 6 at 13:51
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
For $2$ we have the obvious map sending $(m,n)in C$ to $frac{m}{n} in mathbb{Q}^+$, where $C$ are the co-prime pairs of positive integers. It's onto and 1-1 because every positive rational has a unique representation as a quotient of co-prime positive integers (after cancelling common factors in numerator and denominator).
As to $1$, did you do a bijection from $mathbb{N}$ to $mathbb{N}^2$? You could use that for the subset $C$ as well: If $f$ is that earlier bijection, define $g: mathbb{N} to mathbb{N}$ recursively by $g(0) = min {n: f(n) in C}$ and $g(n+1) = min{n : n > g(n) text{ and } f(n) in C}$ and then $h(n) := f(g(n))$ is a bijection from $mathbb{N}$ to $C$.
answered Jan 6 at 14:06
Henno BrandsmaHenno Brandsma
106k347114
$endgroup$
$begingroup$
When it comes to the 2nd example, I understand it well, as it is pretty close answer to what I thought at first. I have had a bijection from $mathbb{N}^2$ to $mathbb{N}$, which is Cantor's pairing function on 2D array, but I did not have an inverse function to that, also when I read about inverting it on Wikipidia, it makes me confused and I do not understand how it is done.
$endgroup$
– whiskeyo
Jan 6 at 15:34
$begingroup$
@whiskeyo if $f$ is a bijection from $mathbb{N}^2$ to $mathbb{N}$ then $f$ restricted to $C$ is a bijection to an infinite subset of $mathbb{N}$ which you then enumerate to get a bijection with $mathbb{N}$ (map each $n$ in $f[C]$ to its “rank”.
$endgroup$
– Henno Brandsma
Jan 6 at 16:11
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%2f3063834%2fconstruct-bijections-of-given-sets-to-show-that-they-have-the-same-cardinality-a%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
For $2$ we have the obvious map sending $(m,n)in C$ to $frac{m}{n} in mathbb{Q}^+$, where $C$ are the co-prime pairs of positive integers. It's onto and 1-1 because every positive rational has a unique representation as a quotient of co-prime positive integers (after cancelling common factors in numerator and denominator).
As to $1$, did you do a bijection from $mathbb{N}$ to $mathbb{N}^2$? You could use that for the subset $C$ as well: If $f$ is that earlier bijection, define $g: mathbb{N} to mathbb{N}$ recursively by $g(0) = min {n: f(n) in C}$ and $g(n+1) = min{n : n > g(n) text{ and } f(n) in C}$ and then $h(n) := f(g(n))$ is a bijection from $mathbb{N}$ to $C$.
answered Jan 6 at 14:06
Henno BrandsmaHenno Brandsma
106k347114
$endgroup$
$begingroup$
When it comes to the 2nd example, I understand it well, as it is pretty close answer to what I thought at first. I have had a bijection from $mathbb{N}^2$ to $mathbb{N}$, which is Cantor's pairing function on 2D array, but I did not have an inverse function to that, also when I read about inverting it on Wikipidia, it makes me confused and I do not understand how it is done.
$endgroup$
– whiskeyo
Jan 6 at 15:34
$begingroup$
@whiskeyo if $f$ is a bijection from $mathbb{N}^2$ to $mathbb{N}$ then $f$ restricted to $C$ is a bijection to an infinite subset of $mathbb{N}$ which you then enumerate to get a bijection with $mathbb{N}$ (map each $n$ in $f[C]$ to its “rank”.
$endgroup$
– Henno Brandsma
Jan 6 at 16:11
add a comment |
$begingroup$
For $2$ we have the obvious map sending $(m,n)in C$ to $frac{m}{n} in mathbb{Q}^+$, where $C$ are the co-prime pairs of positive integers. It's onto and 1-1 because every positive rational has a unique representation as a quotient of co-prime positive integers (after cancelling common factors in numerator and denominator).
As to $1$, did you do a bijection from $mathbb{N}$ to $mathbb{N}^2$? You could use that for the subset $C$ as well: If $f$ is that earlier bijection, define $g: mathbb{N} to mathbb{N}$ recursively by $g(0) = min {n: f(n) in C}$ and $g(n+1) = min{n : n > g(n) text{ and } f(n) in C}$ and then $h(n) := f(g(n))$ is a bijection from $mathbb{N}$ to $C$.
answered Jan 6 at 14:06
Henno BrandsmaHenno Brandsma
106k347114
$endgroup$
$begingroup$
When it comes to the 2nd example, I understand it well, as it is pretty close answer to what I thought at first. I have had a bijection from $mathbb{N}^2$ to $mathbb{N}$, which is Cantor's pairing function on 2D array, but I did not have an inverse function to that, also when I read about inverting it on Wikipidia, it makes me confused and I do not understand how it is done.
$endgroup$
– whiskeyo
Jan 6 at 15:34
$begingroup$
@whiskeyo if $f$ is a bijection from $mathbb{N}^2$ to $mathbb{N}$ then $f$ restricted to $C$ is a bijection to an infinite subset of $mathbb{N}$ which you then enumerate to get a bijection with $mathbb{N}$ (map each $n$ in $f[C]$ to its “rank”.
$endgroup$
– Henno Brandsma
Jan 6 at 16:11
add a comment |
$begingroup$
For $2$ we have the obvious map sending $(m,n)in C$ to $frac{m}{n} in mathbb{Q}^+$, where $C$ are the co-prime pairs of positive integers. It's onto and 1-1 because every positive rational has a unique representation as a quotient of co-prime positive integers (after cancelling common factors in numerator and denominator).
As to $1$, did you do a bijection from $mathbb{N}$ to $mathbb{N}^2$? You could use that for the subset $C$ as well: If $f$ is that earlier bijection, define $g: mathbb{N} to mathbb{N}$ recursively by $g(0) = min {n: f(n) in C}$ and $g(n+1) = min{n : n > g(n) text{ and } f(n) in C}$ and then $h(n) := f(g(n))$ is a bijection from $mathbb{N}$ to $C$.
answered Jan 6 at 14:06
Henno BrandsmaHenno Brandsma
106k347114
$endgroup$
For $2$ we have the obvious map sending $(m,n)in C$ to $frac{m}{n} in mathbb{Q}^+$, where $C$ are the co-prime pairs of positive integers. It's onto and 1-1 because every positive rational has a unique representation as a quotient of co-prime positive integers (after cancelling common factors in numerator and denominator).
As to $1$, did you do a bijection from $mathbb{N}$ to $mathbb{N}^2$? You could use that for the subset $C$ as well: If $f$ is that earlier bijection, define $g: mathbb{N} to mathbb{N}$ recursively by $g(0) = min {n: f(n) in C}$ and $g(n+1) = min{n : n > g(n) text{ and } f(n) in C}$ and then $h(n) := f(g(n))$ is a bijection from $mathbb{N}$ to $C$.
answered Jan 6 at 14:06
Henno BrandsmaHenno Brandsma
106k347114
answered Jan 6 at 14:06
Henno BrandsmaHenno Brandsma
106k347114
answered Jan 6 at 14:06
Henno BrandsmaHenno Brandsma
106k347114
answered Jan 6 at 14:06
Henno BrandsmaHenno Brandsma
106k347114
106k347114
$begingroup$
When it comes to the 2nd example, I understand it well, as it is pretty close answer to what I thought at first. I have had a bijection from $mathbb{N}^2$ to $mathbb{N}$, which is Cantor's pairing function on 2D array, but I did not have an inverse function to that, also when I read about inverting it on Wikipidia, it makes me confused and I do not understand how it is done.
$endgroup$
– whiskeyo
Jan 6 at 15:34
$begingroup$
@whiskeyo if $f$ is a bijection from $mathbb{N}^2$ to $mathbb{N}$ then $f$ restricted to $C$ is a bijection to an infinite subset of $mathbb{N}$ which you then enumerate to get a bijection with $mathbb{N}$ (map each $n$ in $f[C]$ to its “rank”.
$endgroup$
– Henno Brandsma
Jan 6 at 16:11
add a comment |
$begingroup$
When it comes to the 2nd example, I understand it well, as it is pretty close answer to what I thought at first. I have had a bijection from $mathbb{N}^2$ to $mathbb{N}$, which is Cantor's pairing function on 2D array, but I did not have an inverse function to that, also when I read about inverting it on Wikipidia, it makes me confused and I do not understand how it is done.
$endgroup$
– whiskeyo
Jan 6 at 15:34
$begingroup$
@whiskeyo if $f$ is a bijection from $mathbb{N}^2$ to $mathbb{N}$ then $f$ restricted to $C$ is a bijection to an infinite subset of $mathbb{N}$ which you then enumerate to get a bijection with $mathbb{N}$ (map each $n$ in $f[C]$ to its “rank”.
$endgroup$
– Henno Brandsma
Jan 6 at 16:11
$begingroup$
When it comes to the 2nd example, I understand it well, as it is pretty close answer to what I thought at first. I have had a bijection from $mathbb{N}^2$ to $mathbb{N}$, which is Cantor's pairing function on 2D array, but I did not have an inverse function to that, also when I read about inverting it on Wikipidia, it makes me confused and I do not understand how it is done.
$endgroup$
– whiskeyo
Jan 6 at 15:34
$begingroup$
When it comes to the 2nd example, I understand it well, as it is pretty close answer to what I thought at first. I have had a bijection from $mathbb{N}^2$ to $mathbb{N}$, which is Cantor's pairing function on 2D array, but I did not have an inverse function to that, also when I read about inverting it on Wikipidia, it makes me confused and I do not understand how it is done.
$endgroup$
– whiskeyo
Jan 6 at 15:34
$begingroup$
@whiskeyo if $f$ is a bijection from $mathbb{N}^2$ to $mathbb{N}$ then $f$ restricted to $C$ is a bijection to an infinite subset of $mathbb{N}$ which you then enumerate to get a bijection with $mathbb{N}$ (map each $n$ in $f[C]$ to its “rank”.
$endgroup$
– Henno Brandsma
Jan 6 at 16:11
$begingroup$
@whiskeyo if $f$ is a bijection from $mathbb{N}^2$ to $mathbb{N}$ then $f$ restricted to $C$ is a bijection to an infinite subset of $mathbb{N}$ which you then enumerate to get a bijection with $mathbb{N}$ (map each $n$ in $f[C]$ to its “rank”.
$endgroup$
– Henno Brandsma
Jan 6 at 16:11
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.
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%2f3063834%2fconstruct-bijections-of-given-sets-to-show-that-they-have-the-same-cardinality-a%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
$begingroup$
No, sadly my lectures did not involve them.
$endgroup$
– whiskeyo
Jan 6 at 13:10
1
$begingroup$
For the general problem, it's useful to know constructive proofs of the Cantor-Schröder-Berstein theorem, but I suspect that in these exercises you're supposed to come out with the appropriate bijection out of thin air.
$endgroup$
– Git Gud
Jan 6 at 13:25
$begingroup$
Hint: For Ex.1 do you know of that diagonal argument that proves that (for example) $mathbb{Q}$ is countable, or that $mathbb{N}^{2}$ has the same cardinality as $mathbb{N}$. If so can you adapt that proof?
$endgroup$
– Adam Higgins
Jan 6 at 13:51