Mixing
Cardinality of sets and usage of Cantor-Bernstein theorem
$begingroup$
I have recently been studying cardinality of finite and infinite sets and the 'theory part' was not hard to understand, but it is pretty problematic for me to apply any of the definitions to solve problems.
The first problem is following and I am not sure whether I solved it correctly:
Does $A_1sim A_2$, $B_1sim B_2$ and $|A_1|leq|B_1|$ implies that $|A_2|leq|B_2|$?
My answer is yes, as $A_1$ is equinumerous to $A_2$ and $B_1$ is equinumerous to $B_2$, we may assume that $|A_1|=|A_2|=n$ and $|B_1|=|B_2|=m$.
Then, $|A_1|leq|B_1| equiv nleq m$.
As $n=|A_2|$ and $m=|B_2|$, we get that $|A_1|leq|B_1| Rightarrow |A_2|leq|B_2|$.
The second problem is connected with Cantor-Bernstein theorem, which says that if $|A|leq|B|$ and $|B|leq|A|$, then $|A|=|B|$. Using the theorem we can determine the cardinality of sets $A$ and $B$ by constructing two injective functions $f:Arightarrow B$ and $g: Brightarrow A$.
My job is to construct injective functions to show that ${0,1}^mathbb{N}$ and $mathbb{N}^mathbb{N}$ have the same cardinality, but I do not know how do I construct such functions:
$f: {0,1}^mathbb{N} rightarrow mathbb{N}^mathbb{N}$,
$g: mathbb{N}^mathbb{N} rightarrow {0,1}^mathbb{N}$. Creating e.g. function $f$ requires to map
$big(mathbb{N}rightarrow{0,1}big)rightarrow big(mathbb{N}rightarrowmathbb{N}big)$, which confuses me a lot and I have no idea how should it work.
elementary-set-theory
asked Jan 13 at 2:11
whiskeyowhiskeyo
1368
$endgroup$
add a comment |
$begingroup$
I have recently been studying cardinality of finite and infinite sets and the 'theory part' was not hard to understand, but it is pretty problematic for me to apply any of the definitions to solve problems.
The first problem is following and I am not sure whether I solved it correctly:
Does $A_1sim A_2$, $B_1sim B_2$ and $|A_1|leq|B_1|$ implies that $|A_2|leq|B_2|$?
My answer is yes, as $A_1$ is equinumerous to $A_2$ and $B_1$ is equinumerous to $B_2$, we may assume that $|A_1|=|A_2|=n$ and $|B_1|=|B_2|=m$.
Then, $|A_1|leq|B_1| equiv nleq m$.
As $n=|A_2|$ and $m=|B_2|$, we get that $|A_1|leq|B_1| Rightarrow |A_2|leq|B_2|$.
The second problem is connected with Cantor-Bernstein theorem, which says that if $|A|leq|B|$ and $|B|leq|A|$, then $|A|=|B|$. Using the theorem we can determine the cardinality of sets $A$ and $B$ by constructing two injective functions $f:Arightarrow B$ and $g: Brightarrow A$.
My job is to construct injective functions to show that ${0,1}^mathbb{N}$ and $mathbb{N}^mathbb{N}$ have the same cardinality, but I do not know how do I construct such functions:
$f: {0,1}^mathbb{N} rightarrow mathbb{N}^mathbb{N}$,
$g: mathbb{N}^mathbb{N} rightarrow {0,1}^mathbb{N}$. Creating e.g. function $f$ requires to map
$big(mathbb{N}rightarrow{0,1}big)rightarrow big(mathbb{N}rightarrowmathbb{N}big)$, which confuses me a lot and I have no idea how should it work.
elementary-set-theory
asked Jan 13 at 2:11
whiskeyowhiskeyo
1368
$endgroup$
$begingroup$
Think of ${0, 1}^mathbb{N}$ and $mathbb{N}^mathbb{N}$ as collections of sequences, which is another way to think of these spaces.
$endgroup$
– twnly
Jan 13 at 2:36
add a comment |
$begingroup$
I have recently been studying cardinality of finite and infinite sets and the 'theory part' was not hard to understand, but it is pretty problematic for me to apply any of the definitions to solve problems.
The first problem is following and I am not sure whether I solved it correctly:
Does $A_1sim A_2$, $B_1sim B_2$ and $|A_1|leq|B_1|$ implies that $|A_2|leq|B_2|$?
My answer is yes, as $A_1$ is equinumerous to $A_2$ and $B_1$ is equinumerous to $B_2$, we may assume that $|A_1|=|A_2|=n$ and $|B_1|=|B_2|=m$.
Then, $|A_1|leq|B_1| equiv nleq m$.
As $n=|A_2|$ and $m=|B_2|$, we get that $|A_1|leq|B_1| Rightarrow |A_2|leq|B_2|$.
The second problem is connected with Cantor-Bernstein theorem, which says that if $|A|leq|B|$ and $|B|leq|A|$, then $|A|=|B|$. Using the theorem we can determine the cardinality of sets $A$ and $B$ by constructing two injective functions $f:Arightarrow B$ and $g: Brightarrow A$.
My job is to construct injective functions to show that ${0,1}^mathbb{N}$ and $mathbb{N}^mathbb{N}$ have the same cardinality, but I do not know how do I construct such functions:
$f: {0,1}^mathbb{N} rightarrow mathbb{N}^mathbb{N}$,
$g: mathbb{N}^mathbb{N} rightarrow {0,1}^mathbb{N}$. Creating e.g. function $f$ requires to map
$big(mathbb{N}rightarrow{0,1}big)rightarrow big(mathbb{N}rightarrowmathbb{N}big)$, which confuses me a lot and I have no idea how should it work.
elementary-set-theory
asked Jan 13 at 2:11
whiskeyowhiskeyo
1368
$endgroup$
I have recently been studying cardinality of finite and infinite sets and the 'theory part' was not hard to understand, but it is pretty problematic for me to apply any of the definitions to solve problems.
The first problem is following and I am not sure whether I solved it correctly:
Does $A_1sim A_2$, $B_1sim B_2$ and $|A_1|leq|B_1|$ implies that $|A_2|leq|B_2|$?
My answer is yes, as $A_1$ is equinumerous to $A_2$ and $B_1$ is equinumerous to $B_2$, we may assume that $|A_1|=|A_2|=n$ and $|B_1|=|B_2|=m$.
Then, $|A_1|leq|B_1| equiv nleq m$.
As $n=|A_2|$ and $m=|B_2|$, we get that $|A_1|leq|B_1| Rightarrow |A_2|leq|B_2|$.
The second problem is connected with Cantor-Bernstein theorem, which says that if $|A|leq|B|$ and $|B|leq|A|$, then $|A|=|B|$. Using the theorem we can determine the cardinality of sets $A$ and $B$ by constructing two injective functions $f:Arightarrow B$ and $g: Brightarrow A$.
My job is to construct injective functions to show that ${0,1}^mathbb{N}$ and $mathbb{N}^mathbb{N}$ have the same cardinality, but I do not know how do I construct such functions:
$f: {0,1}^mathbb{N} rightarrow mathbb{N}^mathbb{N}$,
$g: mathbb{N}^mathbb{N} rightarrow {0,1}^mathbb{N}$. Creating e.g. function $f$ requires to map
$big(mathbb{N}rightarrow{0,1}big)rightarrow big(mathbb{N}rightarrowmathbb{N}big)$, which confuses me a lot and I have no idea how should it work.
elementary-set-theory
elementary-set-theory
asked Jan 13 at 2:11
whiskeyowhiskeyo
1368
asked Jan 13 at 2:11
whiskeyowhiskeyo
1368
asked Jan 13 at 2:11
whiskeyowhiskeyo
1368
asked Jan 13 at 2:11
whiskeyowhiskeyo
1368
asked Jan 13 at 2:11
whiskeyowhiskeyo
1368
1368
$begingroup$
Think of ${0, 1}^mathbb{N}$ and $mathbb{N}^mathbb{N}$ as collections of sequences, which is another way to think of these spaces.
$endgroup$
– twnly
Jan 13 at 2:36
add a comment |
$begingroup$
Think of ${0, 1}^mathbb{N}$ and $mathbb{N}^mathbb{N}$ as collections of sequences, which is another way to think of these spaces.
$endgroup$
– twnly
Jan 13 at 2:36
$begingroup$
Think of ${0, 1}^mathbb{N}$ and $mathbb{N}^mathbb{N}$ as collections of sequences, which is another way to think of these spaces.
$endgroup$
– twnly
Jan 13 at 2:36
$begingroup$
Think of ${0, 1}^mathbb{N}$ and $mathbb{N}^mathbb{N}$ as collections of sequences, which is another way to think of these spaces.
$endgroup$
– twnly
Jan 13 at 2:36
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The way you've done the first part implicitly assumes that the sets are finite (and quite a bit more besides). It would be much better to do this in greater generality. Remember that $A_1sim A_2$ is shorthand for "There is a bijective function $f: A_1 rightarrow A_2$," while $|A_1|leq|B_1|$ is shorthand for "There is an injective function $g: A_1 rightarrow B_1$."
Given bijections $f_A: A_1 rightarrow A_2$ and $f_B: B_1 rightarrow B_2$, and an injection $g: A_1 rightarrow B_1$, can you construct an injection $A_2 rightarrow B_2$?
For the second part, bringing in bulky notation like $big(mathbb{N}rightarrow{0,1}big)rightarrow big(mathbb{N}rightarrowmathbb{N}big)$ is only going to serve to muddle matters. Instead focus on the actual substance of the sets of functions involved. For the easier half, can you see that ${0,1}^mathbb{N}$ is an actual subset of $mathbb{N}^mathbb{N}$? That is, members of ${0,1}^mathbb{N}$ are members of $mathbb{N}^mathbb{N}$ obeying a particular restriction?
The other way round is harder, and where it is crucial to become familiar with the way these set constructions work. The key ones for you are:
${0,1}^X$ is in bijection with the power-set of $X$, using the idea of indicator functions.- A function $f:X rightarrow Y$ can be thought of as a set of ordered pairs $(x,f(x))$. This will let you establish $mathbb{N}^mathbb{N}$ as a subset of a particular power-set.
Chain together the injections you get from each of these steps and you will get the injection $mathbb{N}^mathbb{N} rightarrow {0,1}^mathbb{N}$
answered Jan 13 at 2:41
ChessanatorChessanator
2,0891411
$endgroup$
$begingroup$
To the first problem, we can construct injection $A_2rightarrow B_2$, as there exists injection $g: A_1rightarrow B_1$, and sets $A_1,A_2$ and $B_1,B_2$ are equinumerous. When it comes to the second part, now I can see that ${0,1}^mathbb{N}$ is a subset of $mathbb{N}^mathbb{N}$ and it would be some kind of "binary" sequence, but I still cannot understand how to do it the other way round.
$endgroup$
– whiskeyo
Jan 13 at 3:01
$begingroup$
For the first part, it will definitely help you to actually explicitly construct that injection, since you weren't able to see that function straight away.
$endgroup$
– Chessanator
Jan 13 at 3:29
$begingroup$
For the second part, play around with the two details I gave you. ${0,1}^mathbb{N}$ is (in bijection with) some power-set. $mathbb{N}^mathbb{N}$ is a subset of some power-set. Have a look at those power-sets and see if you can compare them.
$endgroup$
– Chessanator
Jan 13 at 3:31
$begingroup$
When it comes to the injection $mathbb{N}^mathbb{N}rightarrow {0,1}^mathbb{N}$ I thought about mapping a sequence $(x_1,x_2,x_3,dots)$ to number of appearances of ones separated by zero, e.g. $(2,1,3,dots)$ would be $1,1,0,1,0,1,1,1,0,dots$ and inverting the function for the other way round (so from a sequence of zeroes and ones we get a sequence of natural numbers). Is it correct?
$endgroup$
– whiskeyo
Jan 13 at 15:00
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%2f3071630%2fcardinality-of-sets-and-usage-of-cantor-bernstein-theorem%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$
The way you've done the first part implicitly assumes that the sets are finite (and quite a bit more besides). It would be much better to do this in greater generality. Remember that $A_1sim A_2$ is shorthand for "There is a bijective function $f: A_1 rightarrow A_2$," while $|A_1|leq|B_1|$ is shorthand for "There is an injective function $g: A_1 rightarrow B_1$."
Given bijections $f_A: A_1 rightarrow A_2$ and $f_B: B_1 rightarrow B_2$, and an injection $g: A_1 rightarrow B_1$, can you construct an injection $A_2 rightarrow B_2$?
For the second part, bringing in bulky notation like $big(mathbb{N}rightarrow{0,1}big)rightarrow big(mathbb{N}rightarrowmathbb{N}big)$ is only going to serve to muddle matters. Instead focus on the actual substance of the sets of functions involved. For the easier half, can you see that ${0,1}^mathbb{N}$ is an actual subset of $mathbb{N}^mathbb{N}$? That is, members of ${0,1}^mathbb{N}$ are members of $mathbb{N}^mathbb{N}$ obeying a particular restriction?
The other way round is harder, and where it is crucial to become familiar with the way these set constructions work. The key ones for you are:
${0,1}^X$ is in bijection with the power-set of $X$, using the idea of indicator functions.- A function $f:X rightarrow Y$ can be thought of as a set of ordered pairs $(x,f(x))$. This will let you establish $mathbb{N}^mathbb{N}$ as a subset of a particular power-set.
Chain together the injections you get from each of these steps and you will get the injection $mathbb{N}^mathbb{N} rightarrow {0,1}^mathbb{N}$
answered Jan 13 at 2:41
ChessanatorChessanator
2,0891411
$endgroup$
$begingroup$
To the first problem, we can construct injection $A_2rightarrow B_2$, as there exists injection $g: A_1rightarrow B_1$, and sets $A_1,A_2$ and $B_1,B_2$ are equinumerous. When it comes to the second part, now I can see that ${0,1}^mathbb{N}$ is a subset of $mathbb{N}^mathbb{N}$ and it would be some kind of "binary" sequence, but I still cannot understand how to do it the other way round.
$endgroup$
– whiskeyo
Jan 13 at 3:01
$begingroup$
For the first part, it will definitely help you to actually explicitly construct that injection, since you weren't able to see that function straight away.
$endgroup$
– Chessanator
Jan 13 at 3:29
$begingroup$
For the second part, play around with the two details I gave you. ${0,1}^mathbb{N}$ is (in bijection with) some power-set. $mathbb{N}^mathbb{N}$ is a subset of some power-set. Have a look at those power-sets and see if you can compare them.
$endgroup$
– Chessanator
Jan 13 at 3:31
$begingroup$
When it comes to the injection $mathbb{N}^mathbb{N}rightarrow {0,1}^mathbb{N}$ I thought about mapping a sequence $(x_1,x_2,x_3,dots)$ to number of appearances of ones separated by zero, e.g. $(2,1,3,dots)$ would be $1,1,0,1,0,1,1,1,0,dots$ and inverting the function for the other way round (so from a sequence of zeroes and ones we get a sequence of natural numbers). Is it correct?
$endgroup$
– whiskeyo
Jan 13 at 15:00
add a comment |
$begingroup$
The way you've done the first part implicitly assumes that the sets are finite (and quite a bit more besides). It would be much better to do this in greater generality. Remember that $A_1sim A_2$ is shorthand for "There is a bijective function $f: A_1 rightarrow A_2$," while $|A_1|leq|B_1|$ is shorthand for "There is an injective function $g: A_1 rightarrow B_1$."
Given bijections $f_A: A_1 rightarrow A_2$ and $f_B: B_1 rightarrow B_2$, and an injection $g: A_1 rightarrow B_1$, can you construct an injection $A_2 rightarrow B_2$?
For the second part, bringing in bulky notation like $big(mathbb{N}rightarrow{0,1}big)rightarrow big(mathbb{N}rightarrowmathbb{N}big)$ is only going to serve to muddle matters. Instead focus on the actual substance of the sets of functions involved. For the easier half, can you see that ${0,1}^mathbb{N}$ is an actual subset of $mathbb{N}^mathbb{N}$? That is, members of ${0,1}^mathbb{N}$ are members of $mathbb{N}^mathbb{N}$ obeying a particular restriction?
The other way round is harder, and where it is crucial to become familiar with the way these set constructions work. The key ones for you are:
${0,1}^X$ is in bijection with the power-set of $X$, using the idea of indicator functions.- A function $f:X rightarrow Y$ can be thought of as a set of ordered pairs $(x,f(x))$. This will let you establish $mathbb{N}^mathbb{N}$ as a subset of a particular power-set.
Chain together the injections you get from each of these steps and you will get the injection $mathbb{N}^mathbb{N} rightarrow {0,1}^mathbb{N}$
answered Jan 13 at 2:41
ChessanatorChessanator
2,0891411
$endgroup$
$begingroup$
To the first problem, we can construct injection $A_2rightarrow B_2$, as there exists injection $g: A_1rightarrow B_1$, and sets $A_1,A_2$ and $B_1,B_2$ are equinumerous. When it comes to the second part, now I can see that ${0,1}^mathbb{N}$ is a subset of $mathbb{N}^mathbb{N}$ and it would be some kind of "binary" sequence, but I still cannot understand how to do it the other way round.
$endgroup$
– whiskeyo
Jan 13 at 3:01
$begingroup$
For the first part, it will definitely help you to actually explicitly construct that injection, since you weren't able to see that function straight away.
$endgroup$
– Chessanator
Jan 13 at 3:29
$begingroup$
For the second part, play around with the two details I gave you. ${0,1}^mathbb{N}$ is (in bijection with) some power-set. $mathbb{N}^mathbb{N}$ is a subset of some power-set. Have a look at those power-sets and see if you can compare them.
$endgroup$
– Chessanator
Jan 13 at 3:31
$begingroup$
When it comes to the injection $mathbb{N}^mathbb{N}rightarrow {0,1}^mathbb{N}$ I thought about mapping a sequence $(x_1,x_2,x_3,dots)$ to number of appearances of ones separated by zero, e.g. $(2,1,3,dots)$ would be $1,1,0,1,0,1,1,1,0,dots$ and inverting the function for the other way round (so from a sequence of zeroes and ones we get a sequence of natural numbers). Is it correct?
$endgroup$
– whiskeyo
Jan 13 at 15:00
add a comment |
$begingroup$
The way you've done the first part implicitly assumes that the sets are finite (and quite a bit more besides). It would be much better to do this in greater generality. Remember that $A_1sim A_2$ is shorthand for "There is a bijective function $f: A_1 rightarrow A_2$," while $|A_1|leq|B_1|$ is shorthand for "There is an injective function $g: A_1 rightarrow B_1$."
Given bijections $f_A: A_1 rightarrow A_2$ and $f_B: B_1 rightarrow B_2$, and an injection $g: A_1 rightarrow B_1$, can you construct an injection $A_2 rightarrow B_2$?
For the second part, bringing in bulky notation like $big(mathbb{N}rightarrow{0,1}big)rightarrow big(mathbb{N}rightarrowmathbb{N}big)$ is only going to serve to muddle matters. Instead focus on the actual substance of the sets of functions involved. For the easier half, can you see that ${0,1}^mathbb{N}$ is an actual subset of $mathbb{N}^mathbb{N}$? That is, members of ${0,1}^mathbb{N}$ are members of $mathbb{N}^mathbb{N}$ obeying a particular restriction?
The other way round is harder, and where it is crucial to become familiar with the way these set constructions work. The key ones for you are:
${0,1}^X$ is in bijection with the power-set of $X$, using the idea of indicator functions.- A function $f:X rightarrow Y$ can be thought of as a set of ordered pairs $(x,f(x))$. This will let you establish $mathbb{N}^mathbb{N}$ as a subset of a particular power-set.
Chain together the injections you get from each of these steps and you will get the injection $mathbb{N}^mathbb{N} rightarrow {0,1}^mathbb{N}$
answered Jan 13 at 2:41
ChessanatorChessanator
2,0891411
$endgroup$
The way you've done the first part implicitly assumes that the sets are finite (and quite a bit more besides). It would be much better to do this in greater generality. Remember that $A_1sim A_2$ is shorthand for "There is a bijective function $f: A_1 rightarrow A_2$," while $|A_1|leq|B_1|$ is shorthand for "There is an injective function $g: A_1 rightarrow B_1$."
Given bijections $f_A: A_1 rightarrow A_2$ and $f_B: B_1 rightarrow B_2$, and an injection $g: A_1 rightarrow B_1$, can you construct an injection $A_2 rightarrow B_2$?
For the second part, bringing in bulky notation like $big(mathbb{N}rightarrow{0,1}big)rightarrow big(mathbb{N}rightarrowmathbb{N}big)$ is only going to serve to muddle matters. Instead focus on the actual substance of the sets of functions involved. For the easier half, can you see that ${0,1}^mathbb{N}$ is an actual subset of $mathbb{N}^mathbb{N}$? That is, members of ${0,1}^mathbb{N}$ are members of $mathbb{N}^mathbb{N}$ obeying a particular restriction?
The other way round is harder, and where it is crucial to become familiar with the way these set constructions work. The key ones for you are:
${0,1}^X$ is in bijection with the power-set of $X$, using the idea of indicator functions.- A function $f:X rightarrow Y$ can be thought of as a set of ordered pairs $(x,f(x))$. This will let you establish $mathbb{N}^mathbb{N}$ as a subset of a particular power-set.
Chain together the injections you get from each of these steps and you will get the injection $mathbb{N}^mathbb{N} rightarrow {0,1}^mathbb{N}$
answered Jan 13 at 2:41
ChessanatorChessanator
2,0891411
answered Jan 13 at 2:41
ChessanatorChessanator
2,0891411
answered Jan 13 at 2:41
ChessanatorChessanator
2,0891411
answered Jan 13 at 2:41
ChessanatorChessanator
2,0891411
2,0891411
$begingroup$
To the first problem, we can construct injection $A_2rightarrow B_2$, as there exists injection $g: A_1rightarrow B_1$, and sets $A_1,A_2$ and $B_1,B_2$ are equinumerous. When it comes to the second part, now I can see that ${0,1}^mathbb{N}$ is a subset of $mathbb{N}^mathbb{N}$ and it would be some kind of "binary" sequence, but I still cannot understand how to do it the other way round.
$endgroup$
– whiskeyo
Jan 13 at 3:01
$begingroup$
For the first part, it will definitely help you to actually explicitly construct that injection, since you weren't able to see that function straight away.
$endgroup$
– Chessanator
Jan 13 at 3:29
$begingroup$
For the second part, play around with the two details I gave you. ${0,1}^mathbb{N}$ is (in bijection with) some power-set. $mathbb{N}^mathbb{N}$ is a subset of some power-set. Have a look at those power-sets and see if you can compare them.
$endgroup$
– Chessanator
Jan 13 at 3:31
$begingroup$
When it comes to the injection $mathbb{N}^mathbb{N}rightarrow {0,1}^mathbb{N}$ I thought about mapping a sequence $(x_1,x_2,x_3,dots)$ to number of appearances of ones separated by zero, e.g. $(2,1,3,dots)$ would be $1,1,0,1,0,1,1,1,0,dots$ and inverting the function for the other way round (so from a sequence of zeroes and ones we get a sequence of natural numbers). Is it correct?
$endgroup$
– whiskeyo
Jan 13 at 15:00
add a comment |
$begingroup$
To the first problem, we can construct injection $A_2rightarrow B_2$, as there exists injection $g: A_1rightarrow B_1$, and sets $A_1,A_2$ and $B_1,B_2$ are equinumerous. When it comes to the second part, now I can see that ${0,1}^mathbb{N}$ is a subset of $mathbb{N}^mathbb{N}$ and it would be some kind of "binary" sequence, but I still cannot understand how to do it the other way round.
$endgroup$
– whiskeyo
Jan 13 at 3:01
$begingroup$
For the first part, it will definitely help you to actually explicitly construct that injection, since you weren't able to see that function straight away.
$endgroup$
– Chessanator
Jan 13 at 3:29
$begingroup$
For the second part, play around with the two details I gave you. ${0,1}^mathbb{N}$ is (in bijection with) some power-set. $mathbb{N}^mathbb{N}$ is a subset of some power-set. Have a look at those power-sets and see if you can compare them.
$endgroup$
– Chessanator
Jan 13 at 3:31
$begingroup$
When it comes to the injection $mathbb{N}^mathbb{N}rightarrow {0,1}^mathbb{N}$ I thought about mapping a sequence $(x_1,x_2,x_3,dots)$ to number of appearances of ones separated by zero, e.g. $(2,1,3,dots)$ would be $1,1,0,1,0,1,1,1,0,dots$ and inverting the function for the other way round (so from a sequence of zeroes and ones we get a sequence of natural numbers). Is it correct?
$endgroup$
– whiskeyo
Jan 13 at 15:00
$begingroup$
To the first problem, we can construct injection $A_2rightarrow B_2$, as there exists injection $g: A_1rightarrow B_1$, and sets $A_1,A_2$ and $B_1,B_2$ are equinumerous. When it comes to the second part, now I can see that ${0,1}^mathbb{N}$ is a subset of $mathbb{N}^mathbb{N}$ and it would be some kind of "binary" sequence, but I still cannot understand how to do it the other way round.
$endgroup$
– whiskeyo
Jan 13 at 3:01
$begingroup$
To the first problem, we can construct injection $A_2rightarrow B_2$, as there exists injection $g: A_1rightarrow B_1$, and sets $A_1,A_2$ and $B_1,B_2$ are equinumerous. When it comes to the second part, now I can see that ${0,1}^mathbb{N}$ is a subset of $mathbb{N}^mathbb{N}$ and it would be some kind of "binary" sequence, but I still cannot understand how to do it the other way round.
$endgroup$
– whiskeyo
Jan 13 at 3:01
$begingroup$
For the first part, it will definitely help you to actually explicitly construct that injection, since you weren't able to see that function straight away.
$endgroup$
– Chessanator
Jan 13 at 3:29
$begingroup$
For the first part, it will definitely help you to actually explicitly construct that injection, since you weren't able to see that function straight away.
$endgroup$
– Chessanator
Jan 13 at 3:29
$begingroup$
For the second part, play around with the two details I gave you. ${0,1}^mathbb{N}$ is (in bijection with) some power-set. $mathbb{N}^mathbb{N}$ is a subset of some power-set. Have a look at those power-sets and see if you can compare them.
$endgroup$
– Chessanator
Jan 13 at 3:31
$begingroup$
For the second part, play around with the two details I gave you. ${0,1}^mathbb{N}$ is (in bijection with) some power-set. $mathbb{N}^mathbb{N}$ is a subset of some power-set. Have a look at those power-sets and see if you can compare them.
$endgroup$
– Chessanator
Jan 13 at 3:31
$begingroup$
When it comes to the injection $mathbb{N}^mathbb{N}rightarrow {0,1}^mathbb{N}$ I thought about mapping a sequence $(x_1,x_2,x_3,dots)$ to number of appearances of ones separated by zero, e.g. $(2,1,3,dots)$ would be $1,1,0,1,0,1,1,1,0,dots$ and inverting the function for the other way round (so from a sequence of zeroes and ones we get a sequence of natural numbers). Is it correct?
$endgroup$
– whiskeyo
Jan 13 at 15:00
$begingroup$
When it comes to the injection $mathbb{N}^mathbb{N}rightarrow {0,1}^mathbb{N}$ I thought about mapping a sequence $(x_1,x_2,x_3,dots)$ to number of appearances of ones separated by zero, e.g. $(2,1,3,dots)$ would be $1,1,0,1,0,1,1,1,0,dots$ and inverting the function for the other way round (so from a sequence of zeroes and ones we get a sequence of natural numbers). Is it correct?
$endgroup$
– whiskeyo
Jan 13 at 15:00
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%2f3071630%2fcardinality-of-sets-and-usage-of-cantor-bernstein-theorem%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$
Think of ${0, 1}^mathbb{N}$ and $mathbb{N}^mathbb{N}$ as collections of sequences, which is another way to think of these spaces.
$endgroup$
– twnly
Jan 13 at 2:36