Proof by induction using functions
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
add a comment |
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
'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
add a comment |
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
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
functions discrete-mathematics induction
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
add a comment |
'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
add a comment |
1 Answer
1
active
oldest
votes
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
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
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%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
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
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
add a comment |
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
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
add a comment |
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
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
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
add a comment |
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
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.
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.
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%2f3017127%2fproof-by-induction-using-functions%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
'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