Proving $v(s,p)=2^{p-1}(2s-1)$ is a bijection of natural numbers and $f(s)=2s-1$ is a bijection between...
$begingroup$
How do I prove this function is bijective?
$$
v(s,p)=2^{p-1}(2s-1).
$$
The domain is natural numbers and the codomain is also the natural numbers.
And this one:
$$
f(s)=2s-1.
$$
The domain is the natural numbers, and the codomain is the odd numbers in the natural numbers.
With this one I would do this to show it's injective:
$$
begin{align}
v(s)&=v(s_1)\
implies 2s-1&=2s_1-1\
implies (2s_1)/2&=(2s_2)/2\
implies s=s_1
end{align}
$$
So it's injective since if $v(s)=v(s_1)$ then $s=s_1$.
And to show it's surjective $f(s)=y$:
$$
begin{align}
y&=2s-1\
implies s&=(y+1)/2
end{align}
$$
Then the function must be surjective since every $y$ is the same as the codomain for $f$.
Am I correct?
functions elementary-set-theory
edited Dec 15 '18 at 4:47
Brahadeesh
6,46942363
asked Dec 14 '18 at 14:37
J. RasJ. Ras
11
$endgroup$
add a comment |
$begingroup$
How do I prove this function is bijective?
$$
v(s,p)=2^{p-1}(2s-1).
$$
The domain is natural numbers and the codomain is also the natural numbers.
And this one:
$$
f(s)=2s-1.
$$
The domain is the natural numbers, and the codomain is the odd numbers in the natural numbers.
With this one I would do this to show it's injective:
$$
begin{align}
v(s)&=v(s_1)\
implies 2s-1&=2s_1-1\
implies (2s_1)/2&=(2s_2)/2\
implies s=s_1
end{align}
$$
So it's injective since if $v(s)=v(s_1)$ then $s=s_1$.
And to show it's surjective $f(s)=y$:
$$
begin{align}
y&=2s-1\
implies s&=(y+1)/2
end{align}
$$
Then the function must be surjective since every $y$ is the same as the codomain for $f$.
Am I correct?
functions elementary-set-theory
edited Dec 15 '18 at 4:47
Brahadeesh
6,46942363
asked Dec 14 '18 at 14:37
J. RasJ. Ras
11
$endgroup$
$begingroup$
It is impossible to know if your functions are bijective without knowing what their domains and codomains are. For example, your $f$ is a bijection $mathbb{R} to mathbb{R}$ but is not a bijection $mathbb{Z} to mathbb{Z}$ (or $mathbb{N} to mathbb{N}$).
$endgroup$
– Clive Newstead
Dec 14 '18 at 14:42
add a comment |
$begingroup$
How do I prove this function is bijective?
$$
v(s,p)=2^{p-1}(2s-1).
$$
The domain is natural numbers and the codomain is also the natural numbers.
And this one:
$$
f(s)=2s-1.
$$
The domain is the natural numbers, and the codomain is the odd numbers in the natural numbers.
With this one I would do this to show it's injective:
$$
begin{align}
v(s)&=v(s_1)\
implies 2s-1&=2s_1-1\
implies (2s_1)/2&=(2s_2)/2\
implies s=s_1
end{align}
$$
So it's injective since if $v(s)=v(s_1)$ then $s=s_1$.
And to show it's surjective $f(s)=y$:
$$
begin{align}
y&=2s-1\
implies s&=(y+1)/2
end{align}
$$
Then the function must be surjective since every $y$ is the same as the codomain for $f$.
Am I correct?
functions elementary-set-theory
edited Dec 15 '18 at 4:47
Brahadeesh
6,46942363
asked Dec 14 '18 at 14:37
J. RasJ. Ras
11
$endgroup$
How do I prove this function is bijective?
$$
v(s,p)=2^{p-1}(2s-1).
$$
The domain is natural numbers and the codomain is also the natural numbers.
And this one:
$$
f(s)=2s-1.
$$
The domain is the natural numbers, and the codomain is the odd numbers in the natural numbers.
With this one I would do this to show it's injective:
$$
begin{align}
v(s)&=v(s_1)\
implies 2s-1&=2s_1-1\
implies (2s_1)/2&=(2s_2)/2\
implies s=s_1
end{align}
$$
So it's injective since if $v(s)=v(s_1)$ then $s=s_1$.
And to show it's surjective $f(s)=y$:
$$
begin{align}
y&=2s-1\
implies s&=(y+1)/2
end{align}
$$
Then the function must be surjective since every $y$ is the same as the codomain for $f$.
Am I correct?
functions elementary-set-theory
functions elementary-set-theory
edited Dec 15 '18 at 4:47
Brahadeesh
6,46942363
asked Dec 14 '18 at 14:37
J. RasJ. Ras
11
edited Dec 15 '18 at 4:47
Brahadeesh
6,46942363
asked Dec 14 '18 at 14:37
J. RasJ. Ras
11
edited Dec 15 '18 at 4:47
Brahadeesh
6,46942363
edited Dec 15 '18 at 4:47
Brahadeesh
6,46942363
edited Dec 15 '18 at 4:47
Brahadeesh
6,46942363
6,46942363
asked Dec 14 '18 at 14:37
J. RasJ. Ras
11
asked Dec 14 '18 at 14:37
J. RasJ. Ras
11
asked Dec 14 '18 at 14:37
J. RasJ. Ras
11
11
$begingroup$
It is impossible to know if your functions are bijective without knowing what their domains and codomains are. For example, your $f$ is a bijection $mathbb{R} to mathbb{R}$ but is not a bijection $mathbb{Z} to mathbb{Z}$ (or $mathbb{N} to mathbb{N}$).
$endgroup$
– Clive Newstead
Dec 14 '18 at 14:42
add a comment |
$begingroup$
It is impossible to know if your functions are bijective without knowing what their domains and codomains are. For example, your $f$ is a bijection $mathbb{R} to mathbb{R}$ but is not a bijection $mathbb{Z} to mathbb{Z}$ (or $mathbb{N} to mathbb{N}$).
$endgroup$
– Clive Newstead
Dec 14 '18 at 14:42
$begingroup$
It is impossible to know if your functions are bijective without knowing what their domains and codomains are. For example, your $f$ is a bijection $mathbb{R} to mathbb{R}$ but is not a bijection $mathbb{Z} to mathbb{Z}$ (or $mathbb{N} to mathbb{N}$).
$endgroup$
– Clive Newstead
Dec 14 '18 at 14:42
$begingroup$
It is impossible to know if your functions are bijective without knowing what their domains and codomains are. For example, your $f$ is a bijection $mathbb{R} to mathbb{R}$ but is not a bijection $mathbb{Z} to mathbb{Z}$ (or $mathbb{N} to mathbb{N}$).
$endgroup$
– Clive Newstead
Dec 14 '18 at 14:42
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Yes, "bijective" means "both injective and surjective". "Injective" means "if f(x)= f(y) then x= y" and "surjective" means "for any y, there exist x such that f(x)= y". With f(x)= 2x- 1 then if f(x)= f(y), 2x- 1= 2y- 1. Adding 1 to both sides, 2x= 2y. Dividing by 2, x= y. To show that f is surjective, if y= 2x- 1, then 2x= y+ 1 and x= (y+ 1)/2. Since that last, (y+ 1)/2, exists for all y, the function is surjective.
For $v(s, p)= 2^{p-1}(2s+ 1)$, to show "injective" we have to show that if $v(s_1,p_1)= v(s_2, p_2)$ then $s_1= s_2$ and $p_1= p_2$. A crucial point is that $2^{p-1}$ is a power of 2 while 2s+1 is an odd number. Use "unique prime factorization".
answered Dec 14 '18 at 14:55
user247327user247327
11.2k1515
$endgroup$
$begingroup$
So the thing I did was correct, I suppose? What do you mean by using "unique prime factorization?
$endgroup$
– J. Ras
Dec 14 '18 at 15:09
$begingroup$
And can I do it by arguing that every natural number can be written as a product of 2^k-1 and an odd number?
$endgroup$
– J. Ras
Dec 14 '18 at 15:17
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%2f3039432%2fproving-vs-p-2p-12s-1-is-a-bijection-of-natural-numbers-and-fs-2s-1%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$
Yes, "bijective" means "both injective and surjective". "Injective" means "if f(x)= f(y) then x= y" and "surjective" means "for any y, there exist x such that f(x)= y". With f(x)= 2x- 1 then if f(x)= f(y), 2x- 1= 2y- 1. Adding 1 to both sides, 2x= 2y. Dividing by 2, x= y. To show that f is surjective, if y= 2x- 1, then 2x= y+ 1 and x= (y+ 1)/2. Since that last, (y+ 1)/2, exists for all y, the function is surjective.
For $v(s, p)= 2^{p-1}(2s+ 1)$, to show "injective" we have to show that if $v(s_1,p_1)= v(s_2, p_2)$ then $s_1= s_2$ and $p_1= p_2$. A crucial point is that $2^{p-1}$ is a power of 2 while 2s+1 is an odd number. Use "unique prime factorization".
answered Dec 14 '18 at 14:55
user247327user247327
11.2k1515
$endgroup$
$begingroup$
So the thing I did was correct, I suppose? What do you mean by using "unique prime factorization?
$endgroup$
– J. Ras
Dec 14 '18 at 15:09
$begingroup$
And can I do it by arguing that every natural number can be written as a product of 2^k-1 and an odd number?
$endgroup$
– J. Ras
Dec 14 '18 at 15:17
add a comment |
$begingroup$
Yes, "bijective" means "both injective and surjective". "Injective" means "if f(x)= f(y) then x= y" and "surjective" means "for any y, there exist x such that f(x)= y". With f(x)= 2x- 1 then if f(x)= f(y), 2x- 1= 2y- 1. Adding 1 to both sides, 2x= 2y. Dividing by 2, x= y. To show that f is surjective, if y= 2x- 1, then 2x= y+ 1 and x= (y+ 1)/2. Since that last, (y+ 1)/2, exists for all y, the function is surjective.
For $v(s, p)= 2^{p-1}(2s+ 1)$, to show "injective" we have to show that if $v(s_1,p_1)= v(s_2, p_2)$ then $s_1= s_2$ and $p_1= p_2$. A crucial point is that $2^{p-1}$ is a power of 2 while 2s+1 is an odd number. Use "unique prime factorization".
answered Dec 14 '18 at 14:55
user247327user247327
11.2k1515
$endgroup$
$begingroup$
So the thing I did was correct, I suppose? What do you mean by using "unique prime factorization?
$endgroup$
– J. Ras
Dec 14 '18 at 15:09
$begingroup$
And can I do it by arguing that every natural number can be written as a product of 2^k-1 and an odd number?
$endgroup$
– J. Ras
Dec 14 '18 at 15:17
add a comment |
$begingroup$
Yes, "bijective" means "both injective and surjective". "Injective" means "if f(x)= f(y) then x= y" and "surjective" means "for any y, there exist x such that f(x)= y". With f(x)= 2x- 1 then if f(x)= f(y), 2x- 1= 2y- 1. Adding 1 to both sides, 2x= 2y. Dividing by 2, x= y. To show that f is surjective, if y= 2x- 1, then 2x= y+ 1 and x= (y+ 1)/2. Since that last, (y+ 1)/2, exists for all y, the function is surjective.
For $v(s, p)= 2^{p-1}(2s+ 1)$, to show "injective" we have to show that if $v(s_1,p_1)= v(s_2, p_2)$ then $s_1= s_2$ and $p_1= p_2$. A crucial point is that $2^{p-1}$ is a power of 2 while 2s+1 is an odd number. Use "unique prime factorization".
answered Dec 14 '18 at 14:55
user247327user247327
11.2k1515
$endgroup$
Yes, "bijective" means "both injective and surjective". "Injective" means "if f(x)= f(y) then x= y" and "surjective" means "for any y, there exist x such that f(x)= y". With f(x)= 2x- 1 then if f(x)= f(y), 2x- 1= 2y- 1. Adding 1 to both sides, 2x= 2y. Dividing by 2, x= y. To show that f is surjective, if y= 2x- 1, then 2x= y+ 1 and x= (y+ 1)/2. Since that last, (y+ 1)/2, exists for all y, the function is surjective.
For $v(s, p)= 2^{p-1}(2s+ 1)$, to show "injective" we have to show that if $v(s_1,p_1)= v(s_2, p_2)$ then $s_1= s_2$ and $p_1= p_2$. A crucial point is that $2^{p-1}$ is a power of 2 while 2s+1 is an odd number. Use "unique prime factorization".
answered Dec 14 '18 at 14:55
user247327user247327
11.2k1515
answered Dec 14 '18 at 14:55
user247327user247327
11.2k1515
answered Dec 14 '18 at 14:55
user247327user247327
11.2k1515
answered Dec 14 '18 at 14:55
user247327user247327
11.2k1515
11.2k1515
$begingroup$
So the thing I did was correct, I suppose? What do you mean by using "unique prime factorization?
$endgroup$
– J. Ras
Dec 14 '18 at 15:09
$begingroup$
And can I do it by arguing that every natural number can be written as a product of 2^k-1 and an odd number?
$endgroup$
– J. Ras
Dec 14 '18 at 15:17
add a comment |
$begingroup$
So the thing I did was correct, I suppose? What do you mean by using "unique prime factorization?
$endgroup$
– J. Ras
Dec 14 '18 at 15:09
$begingroup$
And can I do it by arguing that every natural number can be written as a product of 2^k-1 and an odd number?
$endgroup$
– J. Ras
Dec 14 '18 at 15:17
$begingroup$
So the thing I did was correct, I suppose? What do you mean by using "unique prime factorization?
$endgroup$
– J. Ras
Dec 14 '18 at 15:09
$begingroup$
So the thing I did was correct, I suppose? What do you mean by using "unique prime factorization?
$endgroup$
– J. Ras
Dec 14 '18 at 15:09
$begingroup$
And can I do it by arguing that every natural number can be written as a product of 2^k-1 and an odd number?
$endgroup$
– J. Ras
Dec 14 '18 at 15:17
$begingroup$
And can I do it by arguing that every natural number can be written as a product of 2^k-1 and an odd number?
$endgroup$
– J. Ras
Dec 14 '18 at 15:17
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%2f3039432%2fproving-vs-p-2p-12s-1-is-a-bijection-of-natural-numbers-and-fs-2s-1%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$
It is impossible to know if your functions are bijective without knowing what their domains and codomains are. For example, your $f$ is a bijection $mathbb{R} to mathbb{R}$ but is not a bijection $mathbb{Z} to mathbb{Z}$ (or $mathbb{N} to mathbb{N}$).
$endgroup$
– Clive Newstead
Dec 14 '18 at 14:42