Proof by induction using functions












0















Prop: If the set $A$ is infinite then there exists an injective function $z:N→A$. $z$ is defined inductively, for the base case, explain how it is plausible to define$ z(1)$. Now suppose that $z(1),z(2),…,z(n)$ where no two values are equal. Prove that it is possible to define $z(n+1)$ where its value is not equal to any previous value.




I now understand that this has a never-ending injective function that can be created, however, I do not understand how to actually write out the proof. I have written induction proofs before but not seeing an equation or sigma notation to follow I feel quite lost setting up a base case or inductive step showing $z(n + 1)$.



A written proof with explanation would be much appreciated!



Link to similar question: Proofs involving functions and induction










share|cite|improve this question
























  • 'Prove that it is plausible ...'?!? the 'plausible' part is pretty weird ... do they want a proof or not?
    – Bram28
    Nov 28 '18 at 14:09










  • Its possible my bad
    – Zdravstvuyte94
    Nov 28 '18 at 14:20










  • @Zdravstvuyte94 I am puzzled. I just spent a fair amount of time answering your question. Then when I looked at your profile I discovered that you asked the identical question $10$ hours ago, math.stackexchange.com/questions/3016681/… , and accepted an answer. Why did you ask again?
    – Ethan Bolker
    Nov 28 '18 at 14:45












  • The response I got was not suitable for my studies and after replying to the answer I received I got nothing in return from him. Because of his long answer, I knew no one would view the question again so I decided to make it a much more concise question. I suppose the proper thing would be to decline his answer but after already accepting it on mistake I felt that the best thing would be to re-ask the question and hopefully get a much more explained solution such as yours. I thank you for your time, please don't feel as if it was a waste of time because you helped me out immensely!
    – Zdravstvuyte94
    Nov 28 '18 at 17:37












  • @Zdravstvuyte94 You should at least edit both questions to provide a link to the other.
    – Ethan Bolker
    Nov 28 '18 at 19:23
















0















Prop: If the set $A$ is infinite then there exists an injective function $z:N→A$. $z$ is defined inductively, for the base case, explain how it is plausible to define$ z(1)$. Now suppose that $z(1),z(2),…,z(n)$ where no two values are equal. Prove that it is possible to define $z(n+1)$ where its value is not equal to any previous value.




I now understand that this has a never-ending injective function that can be created, however, I do not understand how to actually write out the proof. I have written induction proofs before but not seeing an equation or sigma notation to follow I feel quite lost setting up a base case or inductive step showing $z(n + 1)$.



A written proof with explanation would be much appreciated!



Link to similar question: Proofs involving functions and induction










share|cite|improve this question
























  • 'Prove that it is plausible ...'?!? the 'plausible' part is pretty weird ... do they want a proof or not?
    – Bram28
    Nov 28 '18 at 14:09










  • Its possible my bad
    – Zdravstvuyte94
    Nov 28 '18 at 14:20










  • @Zdravstvuyte94 I am puzzled. I just spent a fair amount of time answering your question. Then when I looked at your profile I discovered that you asked the identical question $10$ hours ago, math.stackexchange.com/questions/3016681/… , and accepted an answer. Why did you ask again?
    – Ethan Bolker
    Nov 28 '18 at 14:45












  • The response I got was not suitable for my studies and after replying to the answer I received I got nothing in return from him. Because of his long answer, I knew no one would view the question again so I decided to make it a much more concise question. I suppose the proper thing would be to decline his answer but after already accepting it on mistake I felt that the best thing would be to re-ask the question and hopefully get a much more explained solution such as yours. I thank you for your time, please don't feel as if it was a waste of time because you helped me out immensely!
    – Zdravstvuyte94
    Nov 28 '18 at 17:37












  • @Zdravstvuyte94 You should at least edit both questions to provide a link to the other.
    – Ethan Bolker
    Nov 28 '18 at 19:23














0












0








0








Prop: If the set $A$ is infinite then there exists an injective function $z:N→A$. $z$ is defined inductively, for the base case, explain how it is plausible to define$ z(1)$. Now suppose that $z(1),z(2),…,z(n)$ where no two values are equal. Prove that it is possible to define $z(n+1)$ where its value is not equal to any previous value.




I now understand that this has a never-ending injective function that can be created, however, I do not understand how to actually write out the proof. I have written induction proofs before but not seeing an equation or sigma notation to follow I feel quite lost setting up a base case or inductive step showing $z(n + 1)$.



A written proof with explanation would be much appreciated!



Link to similar question: Proofs involving functions and induction










share|cite|improve this question
















Prop: If the set $A$ is infinite then there exists an injective function $z:N→A$. $z$ is defined inductively, for the base case, explain how it is plausible to define$ z(1)$. Now suppose that $z(1),z(2),…,z(n)$ where no two values are equal. Prove that it is possible to define $z(n+1)$ where its value is not equal to any previous value.




I now understand that this has a never-ending injective function that can be created, however, I do not understand how to actually write out the proof. I have written induction proofs before but not seeing an equation or sigma notation to follow I feel quite lost setting up a base case or inductive step showing $z(n + 1)$.



A written proof with explanation would be much appreciated!



Link to similar question: Proofs involving functions and induction







functions discrete-mathematics induction






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 29 '18 at 8:50









Bertrand Wittgenstein's Ghost

354114




354114










asked Nov 28 '18 at 13:13









Zdravstvuyte94

395




395












  • 'Prove that it is plausible ...'?!? the 'plausible' part is pretty weird ... do they want a proof or not?
    – Bram28
    Nov 28 '18 at 14:09










  • Its possible my bad
    – Zdravstvuyte94
    Nov 28 '18 at 14:20










  • @Zdravstvuyte94 I am puzzled. I just spent a fair amount of time answering your question. Then when I looked at your profile I discovered that you asked the identical question $10$ hours ago, math.stackexchange.com/questions/3016681/… , and accepted an answer. Why did you ask again?
    – Ethan Bolker
    Nov 28 '18 at 14:45












  • The response I got was not suitable for my studies and after replying to the answer I received I got nothing in return from him. Because of his long answer, I knew no one would view the question again so I decided to make it a much more concise question. I suppose the proper thing would be to decline his answer but after already accepting it on mistake I felt that the best thing would be to re-ask the question and hopefully get a much more explained solution such as yours. I thank you for your time, please don't feel as if it was a waste of time because you helped me out immensely!
    – Zdravstvuyte94
    Nov 28 '18 at 17:37












  • @Zdravstvuyte94 You should at least edit both questions to provide a link to the other.
    – Ethan Bolker
    Nov 28 '18 at 19:23


















  • 'Prove that it is plausible ...'?!? the 'plausible' part is pretty weird ... do they want a proof or not?
    – Bram28
    Nov 28 '18 at 14:09










  • Its possible my bad
    – Zdravstvuyte94
    Nov 28 '18 at 14:20










  • @Zdravstvuyte94 I am puzzled. I just spent a fair amount of time answering your question. Then when I looked at your profile I discovered that you asked the identical question $10$ hours ago, math.stackexchange.com/questions/3016681/… , and accepted an answer. Why did you ask again?
    – Ethan Bolker
    Nov 28 '18 at 14:45












  • The response I got was not suitable for my studies and after replying to the answer I received I got nothing in return from him. Because of his long answer, I knew no one would view the question again so I decided to make it a much more concise question. I suppose the proper thing would be to decline his answer but after already accepting it on mistake I felt that the best thing would be to re-ask the question and hopefully get a much more explained solution such as yours. I thank you for your time, please don't feel as if it was a waste of time because you helped me out immensely!
    – Zdravstvuyte94
    Nov 28 '18 at 17:37












  • @Zdravstvuyte94 You should at least edit both questions to provide a link to the other.
    – Ethan Bolker
    Nov 28 '18 at 19:23
















'Prove that it is plausible ...'?!? the 'plausible' part is pretty weird ... do they want a proof or not?
– Bram28
Nov 28 '18 at 14:09




'Prove that it is plausible ...'?!? the 'plausible' part is pretty weird ... do they want a proof or not?
– Bram28
Nov 28 '18 at 14:09












Its possible my bad
– Zdravstvuyte94
Nov 28 '18 at 14:20




Its possible my bad
– Zdravstvuyte94
Nov 28 '18 at 14:20












@Zdravstvuyte94 I am puzzled. I just spent a fair amount of time answering your question. Then when I looked at your profile I discovered that you asked the identical question $10$ hours ago, math.stackexchange.com/questions/3016681/… , and accepted an answer. Why did you ask again?
– Ethan Bolker
Nov 28 '18 at 14:45






@Zdravstvuyte94 I am puzzled. I just spent a fair amount of time answering your question. Then when I looked at your profile I discovered that you asked the identical question $10$ hours ago, math.stackexchange.com/questions/3016681/… , and accepted an answer. Why did you ask again?
– Ethan Bolker
Nov 28 '18 at 14:45














The response I got was not suitable for my studies and after replying to the answer I received I got nothing in return from him. Because of his long answer, I knew no one would view the question again so I decided to make it a much more concise question. I suppose the proper thing would be to decline his answer but after already accepting it on mistake I felt that the best thing would be to re-ask the question and hopefully get a much more explained solution such as yours. I thank you for your time, please don't feel as if it was a waste of time because you helped me out immensely!
– Zdravstvuyte94
Nov 28 '18 at 17:37






The response I got was not suitable for my studies and after replying to the answer I received I got nothing in return from him. Because of his long answer, I knew no one would view the question again so I decided to make it a much more concise question. I suppose the proper thing would be to decline his answer but after already accepting it on mistake I felt that the best thing would be to re-ask the question and hopefully get a much more explained solution such as yours. I thank you for your time, please don't feel as if it was a waste of time because you helped me out immensely!
– Zdravstvuyte94
Nov 28 '18 at 17:37














@Zdravstvuyte94 You should at least edit both questions to provide a link to the other.
– Ethan Bolker
Nov 28 '18 at 19:23




@Zdravstvuyte94 You should at least edit both questions to provide a link to the other.
– Ethan Bolker
Nov 28 '18 at 19:23










1 Answer
1






active

oldest

votes


















1














The heart of the argument goes something like this.



Suppose that for some particular $n$ you have found $B = {z_1, ldots. z_n} subset A$ in $A$, where the $z_i$ are all different. That's an assertion about the number $n$. You want to show the same assertion is true for $n+1$. Well, by hypothesis $A$ is infinite. Since $B$ is finite, it can't be all of $A$, so you can find some element $a in A$ that's not one of the $z_i$. Then define $z_{n+1} = a$.



What about the base case, to get the induction started? Well, since $A$ is infinite it's not empty, so you can choose some element $a in A$ for the value $z_1$.



I think the reason you have trouble with this exercise is that so far what you've been taught about induction suggests to you that it's about equations. It's not, it's about statements about integers. Often but not always that statement asserts the truth of some equation involving an integer.



I recommend that you prove the inductive step first, and then the base case. That stresses the fact that what you are proving is that




If the statement $P(n)$ is true then the statement $P(n+1)$ is true, even though I don't at the moment know any particular value of
$n$ for which $P(n)$ is true
.




Related: https://matheducators.stackexchange.com/questions/10021/why-are-induction-proofs-so-challenging-for-students/10057#10057






share|cite|improve this answer























  • Would you be able to supply a proof or at least a hint on how to start the inductive and or base case and the rest hidden unless I move my cursor over it? You are correct, all of my induction has involved equations dealing with integers so I have zero experience using on functions and sets such as these.
    – Zdravstvuyte94
    Nov 28 '18 at 18:28










  • @Zdravstvuyte94 This is a proof, as it stands, not merely a hint. The inductive step is the second paragraph - just change "you" to "I".. The base case is the third paragraph.
    – Ethan Bolker
    Nov 28 '18 at 18:33











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
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3017127%2fproof-by-induction-using-functions%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









1














The heart of the argument goes something like this.



Suppose that for some particular $n$ you have found $B = {z_1, ldots. z_n} subset A$ in $A$, where the $z_i$ are all different. That's an assertion about the number $n$. You want to show the same assertion is true for $n+1$. Well, by hypothesis $A$ is infinite. Since $B$ is finite, it can't be all of $A$, so you can find some element $a in A$ that's not one of the $z_i$. Then define $z_{n+1} = a$.



What about the base case, to get the induction started? Well, since $A$ is infinite it's not empty, so you can choose some element $a in A$ for the value $z_1$.



I think the reason you have trouble with this exercise is that so far what you've been taught about induction suggests to you that it's about equations. It's not, it's about statements about integers. Often but not always that statement asserts the truth of some equation involving an integer.



I recommend that you prove the inductive step first, and then the base case. That stresses the fact that what you are proving is that




If the statement $P(n)$ is true then the statement $P(n+1)$ is true, even though I don't at the moment know any particular value of
$n$ for which $P(n)$ is true
.




Related: https://matheducators.stackexchange.com/questions/10021/why-are-induction-proofs-so-challenging-for-students/10057#10057






share|cite|improve this answer























  • Would you be able to supply a proof or at least a hint on how to start the inductive and or base case and the rest hidden unless I move my cursor over it? You are correct, all of my induction has involved equations dealing with integers so I have zero experience using on functions and sets such as these.
    – Zdravstvuyte94
    Nov 28 '18 at 18:28










  • @Zdravstvuyte94 This is a proof, as it stands, not merely a hint. The inductive step is the second paragraph - just change "you" to "I".. The base case is the third paragraph.
    – Ethan Bolker
    Nov 28 '18 at 18:33
















1














The heart of the argument goes something like this.



Suppose that for some particular $n$ you have found $B = {z_1, ldots. z_n} subset A$ in $A$, where the $z_i$ are all different. That's an assertion about the number $n$. You want to show the same assertion is true for $n+1$. Well, by hypothesis $A$ is infinite. Since $B$ is finite, it can't be all of $A$, so you can find some element $a in A$ that's not one of the $z_i$. Then define $z_{n+1} = a$.



What about the base case, to get the induction started? Well, since $A$ is infinite it's not empty, so you can choose some element $a in A$ for the value $z_1$.



I think the reason you have trouble with this exercise is that so far what you've been taught about induction suggests to you that it's about equations. It's not, it's about statements about integers. Often but not always that statement asserts the truth of some equation involving an integer.



I recommend that you prove the inductive step first, and then the base case. That stresses the fact that what you are proving is that




If the statement $P(n)$ is true then the statement $P(n+1)$ is true, even though I don't at the moment know any particular value of
$n$ for which $P(n)$ is true
.




Related: https://matheducators.stackexchange.com/questions/10021/why-are-induction-proofs-so-challenging-for-students/10057#10057






share|cite|improve this answer























  • Would you be able to supply a proof or at least a hint on how to start the inductive and or base case and the rest hidden unless I move my cursor over it? You are correct, all of my induction has involved equations dealing with integers so I have zero experience using on functions and sets such as these.
    – Zdravstvuyte94
    Nov 28 '18 at 18:28










  • @Zdravstvuyte94 This is a proof, as it stands, not merely a hint. The inductive step is the second paragraph - just change "you" to "I".. The base case is the third paragraph.
    – Ethan Bolker
    Nov 28 '18 at 18:33














1












1








1






The heart of the argument goes something like this.



Suppose that for some particular $n$ you have found $B = {z_1, ldots. z_n} subset A$ in $A$, where the $z_i$ are all different. That's an assertion about the number $n$. You want to show the same assertion is true for $n+1$. Well, by hypothesis $A$ is infinite. Since $B$ is finite, it can't be all of $A$, so you can find some element $a in A$ that's not one of the $z_i$. Then define $z_{n+1} = a$.



What about the base case, to get the induction started? Well, since $A$ is infinite it's not empty, so you can choose some element $a in A$ for the value $z_1$.



I think the reason you have trouble with this exercise is that so far what you've been taught about induction suggests to you that it's about equations. It's not, it's about statements about integers. Often but not always that statement asserts the truth of some equation involving an integer.



I recommend that you prove the inductive step first, and then the base case. That stresses the fact that what you are proving is that




If the statement $P(n)$ is true then the statement $P(n+1)$ is true, even though I don't at the moment know any particular value of
$n$ for which $P(n)$ is true
.




Related: https://matheducators.stackexchange.com/questions/10021/why-are-induction-proofs-so-challenging-for-students/10057#10057






share|cite|improve this answer














The heart of the argument goes something like this.



Suppose that for some particular $n$ you have found $B = {z_1, ldots. z_n} subset A$ in $A$, where the $z_i$ are all different. That's an assertion about the number $n$. You want to show the same assertion is true for $n+1$. Well, by hypothesis $A$ is infinite. Since $B$ is finite, it can't be all of $A$, so you can find some element $a in A$ that's not one of the $z_i$. Then define $z_{n+1} = a$.



What about the base case, to get the induction started? Well, since $A$ is infinite it's not empty, so you can choose some element $a in A$ for the value $z_1$.



I think the reason you have trouble with this exercise is that so far what you've been taught about induction suggests to you that it's about equations. It's not, it's about statements about integers. Often but not always that statement asserts the truth of some equation involving an integer.



I recommend that you prove the inductive step first, and then the base case. That stresses the fact that what you are proving is that




If the statement $P(n)$ is true then the statement $P(n+1)$ is true, even though I don't at the moment know any particular value of
$n$ for which $P(n)$ is true
.




Related: https://matheducators.stackexchange.com/questions/10021/why-are-induction-proofs-so-challenging-for-students/10057#10057







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Nov 28 '18 at 14:42

























answered Nov 28 '18 at 14:34









Ethan Bolker

41.6k547110




41.6k547110












  • Would you be able to supply a proof or at least a hint on how to start the inductive and or base case and the rest hidden unless I move my cursor over it? You are correct, all of my induction has involved equations dealing with integers so I have zero experience using on functions and sets such as these.
    – Zdravstvuyte94
    Nov 28 '18 at 18:28










  • @Zdravstvuyte94 This is a proof, as it stands, not merely a hint. The inductive step is the second paragraph - just change "you" to "I".. The base case is the third paragraph.
    – Ethan Bolker
    Nov 28 '18 at 18:33


















  • Would you be able to supply a proof or at least a hint on how to start the inductive and or base case and the rest hidden unless I move my cursor over it? You are correct, all of my induction has involved equations dealing with integers so I have zero experience using on functions and sets such as these.
    – Zdravstvuyte94
    Nov 28 '18 at 18:28










  • @Zdravstvuyte94 This is a proof, as it stands, not merely a hint. The inductive step is the second paragraph - just change "you" to "I".. The base case is the third paragraph.
    – Ethan Bolker
    Nov 28 '18 at 18:33
















Would you be able to supply a proof or at least a hint on how to start the inductive and or base case and the rest hidden unless I move my cursor over it? You are correct, all of my induction has involved equations dealing with integers so I have zero experience using on functions and sets such as these.
– Zdravstvuyte94
Nov 28 '18 at 18:28




Would you be able to supply a proof or at least a hint on how to start the inductive and or base case and the rest hidden unless I move my cursor over it? You are correct, all of my induction has involved equations dealing with integers so I have zero experience using on functions and sets such as these.
– Zdravstvuyte94
Nov 28 '18 at 18:28












@Zdravstvuyte94 This is a proof, as it stands, not merely a hint. The inductive step is the second paragraph - just change "you" to "I".. The base case is the third paragraph.
– Ethan Bolker
Nov 28 '18 at 18:33




@Zdravstvuyte94 This is a proof, as it stands, not merely a hint. The inductive step is the second paragraph - just change "you" to "I".. The base case is the third paragraph.
– Ethan Bolker
Nov 28 '18 at 18:33


















draft saved

draft discarded




















































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.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


  • 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.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3017127%2fproof-by-induction-using-functions%23new-answer', 'question_page');
}
);

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







Popular posts from this blog

How do I know what Microsoft account the skydrive app is syncing to?

When does type information flow backwards in C++?

Grease: Live!