Let function $f$ be defined by $f(X)$. Prove that $f$ is bijective.
$begingroup$
Let function $f: mathcal{P}(mathbb{N}times{0,1}) rightarrow mathcal{P}(mathbb{N})$ be defined by $f(X) = {2x+y:|:langle x,yrangle in X}$.
Prove that $f$ is bijective.
$mathcal{P}(X)$ is a power set over $X$.
In order for function to be bijective, it has to be:
- 1-1: $f(langle x_1,y_1rangle) = f(langle x_2,y_2rangle) Rightarrow langle x_1,y_1rangle = langle x_2,y_2rangle$
- onto: $forall z in mathcal{P}(mathbb{N}) :exists x,yinmathcal{P}(mathbb{N}times{0,1}): f(x,y) = z$
To show that $f$ is 1-1, we take any $x_1, x_2in mathcal{P}(mathbb{N})$; $y_1, y_2in {0,1}$ and we need to show that the first condition is true. Similarly, we need to show that the second condition is true, then it would mean that $f$ is bijective, though I do not know how to prove it step-by-step.
I also thought about other possible way of solving it. Function $h:Arightarrow B$ is bijective iff it has an inverse function $h^{-1}:Brightarrow A$, so I could think of a function which would satisfy this condition, but would it be a sufficient proof?
functions elementary-set-theory
asked Dec 13 '18 at 17:10
whiskeyowhiskeyo
1368
$endgroup$
add a comment |
$begingroup$
Let function $f: mathcal{P}(mathbb{N}times{0,1}) rightarrow mathcal{P}(mathbb{N})$ be defined by $f(X) = {2x+y:|:langle x,yrangle in X}$.
Prove that $f$ is bijective.
$mathcal{P}(X)$ is a power set over $X$.
In order for function to be bijective, it has to be:
- 1-1: $f(langle x_1,y_1rangle) = f(langle x_2,y_2rangle) Rightarrow langle x_1,y_1rangle = langle x_2,y_2rangle$
- onto: $forall z in mathcal{P}(mathbb{N}) :exists x,yinmathcal{P}(mathbb{N}times{0,1}): f(x,y) = z$
To show that $f$ is 1-1, we take any $x_1, x_2in mathcal{P}(mathbb{N})$; $y_1, y_2in {0,1}$ and we need to show that the first condition is true. Similarly, we need to show that the second condition is true, then it would mean that $f$ is bijective, though I do not know how to prove it step-by-step.
I also thought about other possible way of solving it. Function $h:Arightarrow B$ is bijective iff it has an inverse function $h^{-1}:Brightarrow A$, so I could think of a function which would satisfy this condition, but would it be a sufficient proof?
functions elementary-set-theory
asked Dec 13 '18 at 17:10
whiskeyowhiskeyo
1368
$endgroup$
$begingroup$
Yes, both approaches work. But you have to do it. It is not that difficult.
$endgroup$
– Paul Frost
Dec 13 '18 at 17:53
$begingroup$
This is why I asked for help, I mentioned that I cannot prove it step-by-step using first method, as I do not know how should I start it and what I have to do next (sadly proofs are not my strong point). When it comes to the second method with finding the inverse function, I am trying to get it, but all my ideas were wrong. I was thinking about $f^{-1}(n) = n$ for $nin N$, but it does not contain whole ${0,1}$ set, as it is $f^{-1}(n) = n + 0$ in every case.
$endgroup$
– whiskeyo
Dec 13 '18 at 18:47
add a comment |
$begingroup$
Let function $f: mathcal{P}(mathbb{N}times{0,1}) rightarrow mathcal{P}(mathbb{N})$ be defined by $f(X) = {2x+y:|:langle x,yrangle in X}$.
Prove that $f$ is bijective.
$mathcal{P}(X)$ is a power set over $X$.
In order for function to be bijective, it has to be:
- 1-1: $f(langle x_1,y_1rangle) = f(langle x_2,y_2rangle) Rightarrow langle x_1,y_1rangle = langle x_2,y_2rangle$
- onto: $forall z in mathcal{P}(mathbb{N}) :exists x,yinmathcal{P}(mathbb{N}times{0,1}): f(x,y) = z$
To show that $f$ is 1-1, we take any $x_1, x_2in mathcal{P}(mathbb{N})$; $y_1, y_2in {0,1}$ and we need to show that the first condition is true. Similarly, we need to show that the second condition is true, then it would mean that $f$ is bijective, though I do not know how to prove it step-by-step.
I also thought about other possible way of solving it. Function $h:Arightarrow B$ is bijective iff it has an inverse function $h^{-1}:Brightarrow A$, so I could think of a function which would satisfy this condition, but would it be a sufficient proof?
functions elementary-set-theory
asked Dec 13 '18 at 17:10
whiskeyowhiskeyo
1368
$endgroup$
Let function $f: mathcal{P}(mathbb{N}times{0,1}) rightarrow mathcal{P}(mathbb{N})$ be defined by $f(X) = {2x+y:|:langle x,yrangle in X}$.
Prove that $f$ is bijective.
$mathcal{P}(X)$ is a power set over $X$.
In order for function to be bijective, it has to be:
- 1-1: $f(langle x_1,y_1rangle) = f(langle x_2,y_2rangle) Rightarrow langle x_1,y_1rangle = langle x_2,y_2rangle$
- onto: $forall z in mathcal{P}(mathbb{N}) :exists x,yinmathcal{P}(mathbb{N}times{0,1}): f(x,y) = z$
To show that $f$ is 1-1, we take any $x_1, x_2in mathcal{P}(mathbb{N})$; $y_1, y_2in {0,1}$ and we need to show that the first condition is true. Similarly, we need to show that the second condition is true, then it would mean that $f$ is bijective, though I do not know how to prove it step-by-step.
I also thought about other possible way of solving it. Function $h:Arightarrow B$ is bijective iff it has an inverse function $h^{-1}:Brightarrow A$, so I could think of a function which would satisfy this condition, but would it be a sufficient proof?
functions elementary-set-theory
functions elementary-set-theory
asked Dec 13 '18 at 17:10
whiskeyowhiskeyo
1368
asked Dec 13 '18 at 17:10
whiskeyowhiskeyo
1368
asked Dec 13 '18 at 17:10
whiskeyowhiskeyo
1368
asked Dec 13 '18 at 17:10
whiskeyowhiskeyo
1368
asked Dec 13 '18 at 17:10
whiskeyowhiskeyo
1368
1368
$begingroup$
Yes, both approaches work. But you have to do it. It is not that difficult.
$endgroup$
– Paul Frost
Dec 13 '18 at 17:53
$begingroup$
This is why I asked for help, I mentioned that I cannot prove it step-by-step using first method, as I do not know how should I start it and what I have to do next (sadly proofs are not my strong point). When it comes to the second method with finding the inverse function, I am trying to get it, but all my ideas were wrong. I was thinking about $f^{-1}(n) = n$ for $nin N$, but it does not contain whole ${0,1}$ set, as it is $f^{-1}(n) = n + 0$ in every case.
$endgroup$
– whiskeyo
Dec 13 '18 at 18:47
add a comment |
$begingroup$
Yes, both approaches work. But you have to do it. It is not that difficult.
$endgroup$
– Paul Frost
Dec 13 '18 at 17:53
$begingroup$
This is why I asked for help, I mentioned that I cannot prove it step-by-step using first method, as I do not know how should I start it and what I have to do next (sadly proofs are not my strong point). When it comes to the second method with finding the inverse function, I am trying to get it, but all my ideas were wrong. I was thinking about $f^{-1}(n) = n$ for $nin N$, but it does not contain whole ${0,1}$ set, as it is $f^{-1}(n) = n + 0$ in every case.
$endgroup$
– whiskeyo
Dec 13 '18 at 18:47
$begingroup$
Yes, both approaches work. But you have to do it. It is not that difficult.
$endgroup$
– Paul Frost
Dec 13 '18 at 17:53
$begingroup$
Yes, both approaches work. But you have to do it. It is not that difficult.
$endgroup$
– Paul Frost
Dec 13 '18 at 17:53
$begingroup$
This is why I asked for help, I mentioned that I cannot prove it step-by-step using first method, as I do not know how should I start it and what I have to do next (sadly proofs are not my strong point). When it comes to the second method with finding the inverse function, I am trying to get it, but all my ideas were wrong. I was thinking about $f^{-1}(n) = n$ for $nin N$, but it does not contain whole ${0,1}$ set, as it is $f^{-1}(n) = n + 0$ in every case.
$endgroup$
– whiskeyo
Dec 13 '18 at 18:47
$begingroup$
This is why I asked for help, I mentioned that I cannot prove it step-by-step using first method, as I do not know how should I start it and what I have to do next (sadly proofs are not my strong point). When it comes to the second method with finding the inverse function, I am trying to get it, but all my ideas were wrong. I was thinking about $f^{-1}(n) = n$ for $nin N$, but it does not contain whole ${0,1}$ set, as it is $f^{-1}(n) = n + 0$ in every case.
$endgroup$
– whiskeyo
Dec 13 '18 at 18:47
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Hint: Each $Y in mathcal{P}(mathbb{N})$ has a unique decomposition $Y = Y_0 cup Y_1$ where $Y_0$ contains all even numbers in $Y$ and $Y_1$ contains all odd numbers in $Y$. Define
$$Y_0' = { n/2 mid n in Y_0 } ,$$
$$Y_1' = { (n-1)/2 mid n in Y_1 } ,$$
$$g : mathcal{P}(mathbb{N}) to mathcal{P}(mathbb{N} times { 0,1 }), g(Y) = Y_0' times { 0 } cup Y_1' times { 1 } $$
and show that $g$ is an inverse for $f$.
answered Dec 13 '18 at 18:53
Paul FrostPaul Frost
11.3k3934
$endgroup$
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%2f3038306%2flet-function-f-be-defined-by-fx-prove-that-f-is-bijective%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$
Hint: Each $Y in mathcal{P}(mathbb{N})$ has a unique decomposition $Y = Y_0 cup Y_1$ where $Y_0$ contains all even numbers in $Y$ and $Y_1$ contains all odd numbers in $Y$. Define
$$Y_0' = { n/2 mid n in Y_0 } ,$$
$$Y_1' = { (n-1)/2 mid n in Y_1 } ,$$
$$g : mathcal{P}(mathbb{N}) to mathcal{P}(mathbb{N} times { 0,1 }), g(Y) = Y_0' times { 0 } cup Y_1' times { 1 } $$
and show that $g$ is an inverse for $f$.
answered Dec 13 '18 at 18:53
Paul FrostPaul Frost
11.3k3934
$endgroup$
add a comment |
$begingroup$
Hint: Each $Y in mathcal{P}(mathbb{N})$ has a unique decomposition $Y = Y_0 cup Y_1$ where $Y_0$ contains all even numbers in $Y$ and $Y_1$ contains all odd numbers in $Y$. Define
$$Y_0' = { n/2 mid n in Y_0 } ,$$
$$Y_1' = { (n-1)/2 mid n in Y_1 } ,$$
$$g : mathcal{P}(mathbb{N}) to mathcal{P}(mathbb{N} times { 0,1 }), g(Y) = Y_0' times { 0 } cup Y_1' times { 1 } $$
and show that $g$ is an inverse for $f$.
answered Dec 13 '18 at 18:53
Paul FrostPaul Frost
11.3k3934
$endgroup$
add a comment |
$begingroup$
Hint: Each $Y in mathcal{P}(mathbb{N})$ has a unique decomposition $Y = Y_0 cup Y_1$ where $Y_0$ contains all even numbers in $Y$ and $Y_1$ contains all odd numbers in $Y$. Define
$$Y_0' = { n/2 mid n in Y_0 } ,$$
$$Y_1' = { (n-1)/2 mid n in Y_1 } ,$$
$$g : mathcal{P}(mathbb{N}) to mathcal{P}(mathbb{N} times { 0,1 }), g(Y) = Y_0' times { 0 } cup Y_1' times { 1 } $$
and show that $g$ is an inverse for $f$.
answered Dec 13 '18 at 18:53
Paul FrostPaul Frost
11.3k3934
$endgroup$
Hint: Each $Y in mathcal{P}(mathbb{N})$ has a unique decomposition $Y = Y_0 cup Y_1$ where $Y_0$ contains all even numbers in $Y$ and $Y_1$ contains all odd numbers in $Y$. Define
$$Y_0' = { n/2 mid n in Y_0 } ,$$
$$Y_1' = { (n-1)/2 mid n in Y_1 } ,$$
$$g : mathcal{P}(mathbb{N}) to mathcal{P}(mathbb{N} times { 0,1 }), g(Y) = Y_0' times { 0 } cup Y_1' times { 1 } $$
and show that $g$ is an inverse for $f$.
answered Dec 13 '18 at 18:53
Paul FrostPaul Frost
11.3k3934
edited Dec 13 '18 at 19:19
answered Dec 13 '18 at 18:53
Paul FrostPaul Frost
11.3k3934
answered Dec 13 '18 at 18:53
Paul FrostPaul Frost
11.3k3934
answered Dec 13 '18 at 18:53
Paul FrostPaul Frost
11.3k3934
11.3k3934
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.
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%2f3038306%2flet-function-f-be-defined-by-fx-prove-that-f-is-bijective%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$
Yes, both approaches work. But you have to do it. It is not that difficult.
$endgroup$
– Paul Frost
Dec 13 '18 at 17:53
$begingroup$
This is why I asked for help, I mentioned that I cannot prove it step-by-step using first method, as I do not know how should I start it and what I have to do next (sadly proofs are not my strong point). When it comes to the second method with finding the inverse function, I am trying to get it, but all my ideas were wrong. I was thinking about $f^{-1}(n) = n$ for $nin N$, but it does not contain whole ${0,1}$ set, as it is $f^{-1}(n) = n + 0$ in every case.
$endgroup$
– whiskeyo
Dec 13 '18 at 18:47