Question on how to prove that a set has one-to-one correspondence with the set of positive integersHow to create a one to one correspondence between two sets?Prove that $t$ is a one-to-one correspondence.Countable or uncountable questionone to one positive integers and positive rationalsOne-to-one correspondence of a set within a setHow to display one to one correspondence?Prove that the set n mod 3 = 1 is countably infinite if n belongs to all non-negative integersProving for onto. For the set where n belong to non negative integers with n mod 3 = 1 and the second set of all positive integers.Exhibit a one-to-one correspondence between the set of positive integers and the set of integers not divisible by $3$.How to formalize the fact that $f(i)=lceil i/2rceil$ is surjective but not one-to-one from $Bbb N$ to itself?
What is the difference between "behavior" and "behaviour"?
India just shot down a satellite from the ground. At what altitude range is the resulting debris field?
Closest Prime Number
How to Reset Passwords on Multiple Websites Easily?
Increase performance creating Mandelbrot set in python
A particular customize with green line and letters for subfloat
How do scammers retract money, while you can’t?
How does buying out courses with grant money work?
How can I get through very long and very dry, but also very useful technical documents when learning a new tool?
Class Action - which options I have?
What does the word "Atten" mean?
System.debug(JSON.Serialize(o)) Not longer shows full string
Short story about space worker geeks who zone out by 'listening' to radiation from stars
Pole-zeros of a real-valued causal FIR system
Customer Requests (Sometimes) Drive Me Bonkers!
You cannot touch me, but I can touch you, who am I?
Why escape if the_content isnt?
What Brexit proposals are on the table in the indicative votes on the 27th of March 2019?
Fine Tuning of the Universe
Sort a list by elements of another list
Why not increase contact surface when reentering the atmosphere?
Lay out the Carpet
What can we do to stop prior company from asking us questions?
Did Dumbledore lie to Harry about how long he had James Potter's invisibility cloak when he was examining it? If so, why?
Question on how to prove that a set has one-to-one correspondence with the set of positive integers
How to create a one to one correspondence between two sets?Prove that $t$ is a one-to-one correspondence.Countable or uncountable questionone to one positive integers and positive rationalsOne-to-one correspondence of a set within a setHow to display one to one correspondence?Prove that the set n mod 3 = 1 is countably infinite if n belongs to all non-negative integersProving for onto. For the set where n belong to non negative integers with n mod 3 = 1 and the second set of all positive integers.Exhibit a one-to-one correspondence between the set of positive integers and the set of integers not divisible by $3$.How to formalize the fact that $f(i)=lceil i/2rceil$ is surjective but not one-to-one from $Bbb N$ to itself?
$begingroup$
I am having a hard time understanding how to prove a question such as the following
Determine whether each of these sets is finite, countably infinite, or uncountable. For those that are
countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set.
a) the integers greater than 10
b) the odd negative integers
for part a) I put that it is countably infinite.
This is how I proved it:
$f: mathbbZ^+ rightarrow A$, $f(x)= x+10$
$f(x)$ is one-to-one because $f(m)=f(n)$ implies $m=n$
$f(x)$ is onto because: $y=f(x), y= x+10, x=y-10$, therefore, $f(x)= f(y-10)= (y-10)+10=y$
So therefore, f is a one-to-one correspondance with the set of positive integers.
Did I prove this correctly?
Now for part b) I put countably infinite and I tried to do the same:
$f: mathbbZ^+ rightarrow A, f(x)= -(2x+1)$
It is one-to-one because $f(m)=f(n)$ implies $m=n$
onto: $y=f(x), y=-(2x+1), -y-1/2=x$
This is where I got stuck. If $y=2$, we get that $x= -3/2$, which is not part of $mathbbZ$? That is a real number, not an integer. Therefore, it isn't surjective because there is a value for $y$, for which $y$ does not equal $f(x)$? But I know for a fact that the answer is countably infinite, and if I think about it, it makes sense, but I am not sure why I am so stuck on wrapping my head around this part. Can someone help me?
functions discrete-mathematics proof-explanation
edited Mar 17 at 22:51
twnly
1,2011214
asked Mar 17 at 21:51
NevNev
305
$endgroup$
add a comment |
$begingroup$
I am having a hard time understanding how to prove a question such as the following
Determine whether each of these sets is finite, countably infinite, or uncountable. For those that are
countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set.
a) the integers greater than 10
b) the odd negative integers
for part a) I put that it is countably infinite.
This is how I proved it:
$f: mathbbZ^+ rightarrow A$, $f(x)= x+10$
$f(x)$ is one-to-one because $f(m)=f(n)$ implies $m=n$
$f(x)$ is onto because: $y=f(x), y= x+10, x=y-10$, therefore, $f(x)= f(y-10)= (y-10)+10=y$
So therefore, f is a one-to-one correspondance with the set of positive integers.
Did I prove this correctly?
Now for part b) I put countably infinite and I tried to do the same:
$f: mathbbZ^+ rightarrow A, f(x)= -(2x+1)$
It is one-to-one because $f(m)=f(n)$ implies $m=n$
onto: $y=f(x), y=-(2x+1), -y-1/2=x$
This is where I got stuck. If $y=2$, we get that $x= -3/2$, which is not part of $mathbbZ$? That is a real number, not an integer. Therefore, it isn't surjective because there is a value for $y$, for which $y$ does not equal $f(x)$? But I know for a fact that the answer is countably infinite, and if I think about it, it makes sense, but I am not sure why I am so stuck on wrapping my head around this part. Can someone help me?
functions discrete-mathematics proof-explanation
edited Mar 17 at 22:51
twnly
1,2011214
asked Mar 17 at 21:51
NevNev
305
$endgroup$
1
$begingroup$
Please use MathJax to typeset your posts. You are far more likely to get a positive response, especially considering you are no longer a new contributor.
$endgroup$
– K.Power
Mar 17 at 21:56
$begingroup$
You actually want $y=-(2x-1)$ in order to get $-1$
$endgroup$
– saulspatz
Mar 17 at 22:16
add a comment |
$begingroup$
I am having a hard time understanding how to prove a question such as the following
Determine whether each of these sets is finite, countably infinite, or uncountable. For those that are
countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set.
a) the integers greater than 10
b) the odd negative integers
for part a) I put that it is countably infinite.
This is how I proved it:
$f: mathbbZ^+ rightarrow A$, $f(x)= x+10$
$f(x)$ is one-to-one because $f(m)=f(n)$ implies $m=n$
$f(x)$ is onto because: $y=f(x), y= x+10, x=y-10$, therefore, $f(x)= f(y-10)= (y-10)+10=y$
So therefore, f is a one-to-one correspondance with the set of positive integers.
Did I prove this correctly?
Now for part b) I put countably infinite and I tried to do the same:
$f: mathbbZ^+ rightarrow A, f(x)= -(2x+1)$
It is one-to-one because $f(m)=f(n)$ implies $m=n$
onto: $y=f(x), y=-(2x+1), -y-1/2=x$
This is where I got stuck. If $y=2$, we get that $x= -3/2$, which is not part of $mathbbZ$? That is a real number, not an integer. Therefore, it isn't surjective because there is a value for $y$, for which $y$ does not equal $f(x)$? But I know for a fact that the answer is countably infinite, and if I think about it, it makes sense, but I am not sure why I am so stuck on wrapping my head around this part. Can someone help me?
functions discrete-mathematics proof-explanation
edited Mar 17 at 22:51
twnly
1,2011214
asked Mar 17 at 21:51
NevNev
305
$endgroup$
I am having a hard time understanding how to prove a question such as the following
Determine whether each of these sets is finite, countably infinite, or uncountable. For those that are
countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set.
a) the integers greater than 10
b) the odd negative integers
for part a) I put that it is countably infinite.
This is how I proved it:
$f: mathbbZ^+ rightarrow A$, $f(x)= x+10$
$f(x)$ is one-to-one because $f(m)=f(n)$ implies $m=n$
$f(x)$ is onto because: $y=f(x), y= x+10, x=y-10$, therefore, $f(x)= f(y-10)= (y-10)+10=y$
So therefore, f is a one-to-one correspondance with the set of positive integers.
Did I prove this correctly?
Now for part b) I put countably infinite and I tried to do the same:
$f: mathbbZ^+ rightarrow A, f(x)= -(2x+1)$
It is one-to-one because $f(m)=f(n)$ implies $m=n$
onto: $y=f(x), y=-(2x+1), -y-1/2=x$
This is where I got stuck. If $y=2$, we get that $x= -3/2$, which is not part of $mathbbZ$? That is a real number, not an integer. Therefore, it isn't surjective because there is a value for $y$, for which $y$ does not equal $f(x)$? But I know for a fact that the answer is countably infinite, and if I think about it, it makes sense, but I am not sure why I am so stuck on wrapping my head around this part. Can someone help me?
functions discrete-mathematics proof-explanation
functions discrete-mathematics proof-explanation
edited Mar 17 at 22:51
twnly
1,2011214
asked Mar 17 at 21:51
NevNev
305
edited Mar 17 at 22:51
twnly
1,2011214
asked Mar 17 at 21:51
NevNev
305
edited Mar 17 at 22:51
twnly
1,2011214
edited Mar 17 at 22:51
twnly
1,2011214
edited Mar 17 at 22:51
twnly
1,2011214
1,2011214
asked Mar 17 at 21:51
NevNev
305
asked Mar 17 at 21:51
NevNev
305
asked Mar 17 at 21:51
NevNev
305
305
1
$begingroup$
Please use MathJax to typeset your posts. You are far more likely to get a positive response, especially considering you are no longer a new contributor.
$endgroup$
– K.Power
Mar 17 at 21:56
$begingroup$
You actually want $y=-(2x-1)$ in order to get $-1$
$endgroup$
– saulspatz
Mar 17 at 22:16
add a comment |
1
$begingroup$
Please use MathJax to typeset your posts. You are far more likely to get a positive response, especially considering you are no longer a new contributor.
$endgroup$
– K.Power
Mar 17 at 21:56
$begingroup$
You actually want $y=-(2x-1)$ in order to get $-1$
$endgroup$
– saulspatz
Mar 17 at 22:16
1
1
$begingroup$
Please use MathJax to typeset your posts. You are far more likely to get a positive response, especially considering you are no longer a new contributor.
$endgroup$
– K.Power
Mar 17 at 21:56
$begingroup$
Please use MathJax to typeset your posts. You are far more likely to get a positive response, especially considering you are no longer a new contributor.
$endgroup$
– K.Power
Mar 17 at 21:56
$begingroup$
You actually want $y=-(2x-1)$ in order to get $-1$
$endgroup$
– saulspatz
Mar 17 at 22:16
$begingroup$
You actually want $y=-(2x-1)$ in order to get $-1$
$endgroup$
– saulspatz
Mar 17 at 22:16
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
$y = 2$ is not an odd negative integer. ;-)
Your reasoning is correct.
answered Mar 17 at 21:58
KlausKlaus
2,782113
$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%2f3152131%2fquestion-on-how-to-prove-that-a-set-has-one-to-one-correspondence-with-the-set-o%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$
$y = 2$ is not an odd negative integer. ;-)
Your reasoning is correct.
answered Mar 17 at 21:58
KlausKlaus
2,782113
$endgroup$
add a comment |
$begingroup$
$y = 2$ is not an odd negative integer. ;-)
Your reasoning is correct.
answered Mar 17 at 21:58
KlausKlaus
2,782113
$endgroup$
add a comment |
$begingroup$
$y = 2$ is not an odd negative integer. ;-)
Your reasoning is correct.
answered Mar 17 at 21:58
KlausKlaus
2,782113
$endgroup$
$y = 2$ is not an odd negative integer. ;-)
Your reasoning is correct.
answered Mar 17 at 21:58
KlausKlaus
2,782113
answered Mar 17 at 21:58
KlausKlaus
2,782113
answered Mar 17 at 21:58
KlausKlaus
2,782113
answered Mar 17 at 21:58
KlausKlaus
2,782113
2,782113
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%2f3152131%2fquestion-on-how-to-prove-that-a-set-has-one-to-one-correspondence-with-the-set-o%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
1
$begingroup$
Please use MathJax to typeset your posts. You are far more likely to get a positive response, especially considering you are no longer a new contributor.
$endgroup$
– K.Power
Mar 17 at 21:56
$begingroup$
You actually want $y=-(2x-1)$ in order to get $-1$
$endgroup$
– saulspatz
Mar 17 at 22:16