Once you have an equation, you can add the same number to both sides to get an equivalent equation. That's all that's happening at that step.MathDoofus wrote:Twistar wrote:
Which step?
Step 1, where you include the (k + 1) in the series on the lefthand side.
Mathematical Induction  Help for a Beginner?
Moderators: gmalivuk, Moderators General, Prelates
Re: Mathematical Induction  Help for a Beginner?

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Mathematical Induction  Help for a Beginner?
Twistar wrote:Let me rewrite the proof
We are attempting to prove "1 + 2 + 3 + ... + n = n(n+1)/2" for all integers n
1) Base case n = 1
1 = 1(2)/2 = 1 Check
2) Induction step, assume n = k case and prove n = k + 1 case
a) 1 + 2 + 3 + ... + k = k(k+1)/2 assumption
b) 1 + 2 + 3 + ... + k + (k+1) = ??? We don't know what this is equal to. Let's find out
c) 1 + 2 + 3 + ... + k + (k+1) = k(k+1)/2 + (k+1) plugging in assumption from line a)
d) 1 + 2 + 3 + ... + k + (k+1) = k(k+1)/2 + (k+1) = (k^2 + 3k +2)/2 = (k+1)(k+2)/2  algebra
e) 1 + 2 + 3 + ... + k + (k+1) = (k+1)(k+2)/2 Simple rewriting of the previous line, no math here
f) This is the statement "1 + 2 + 3 + ... + n = n(n+1)/2" for the n = k + 1 case so we have done what we wanted. Proof complete.
edit: Yeah, I see your confusion. I'm not assuming the k + 1 case because I am not assuming that the left hand side equals anything. I am just writing down "1 + 2 + 3 + ... + k + (k+1)" and sort of seeing where it takes me. The reason I wrote it down is because I know that that expression is part of what I'm looking for (the equation in blue).
I think I've got it! You're not assuming the (k + 1) case; instead, you're inserting (k + 1) into the lefthand side, then substituting the assumption for the series of integers, and then rewriting, manipulating, and simplifying the lefthand side until you reach the result, which happens to be the same as the assumption. Is that correct?
Re: Mathematical Induction  Help for a Beginner?
MathDoofus wrote:Twistar wrote:Let me rewrite the proof
We are attempting to prove "1 + 2 + 3 + ... + n = n(n+1)/2" for all integers n
1) Base case n = 1
1 = 1(2)/2 = 1 Check
2) Induction step, assume n = k case and prove n = k + 1 case
a) 1 + 2 + 3 + ... + k = k(k+1)/2 assumption
b) 1 + 2 + 3 + ... + k + (k+1) = ??? We don't know what this is equal to. Let's find out
c) 1 + 2 + 3 + ... + k + (k+1) = k(k+1)/2 + (k+1) plugging in assumption from line a)
d) 1 + 2 + 3 + ... + k + (k+1) = k(k+1)/2 + (k+1) = (k^2 + 3k +2)/2 = (k+1)(k+2)/2  algebra
e) 1 + 2 + 3 + ... + k + (k+1) = (k+1)(k+2)/2 Simple rewriting of the previous line, no math here
f) This is the statement "1 + 2 + 3 + ... + n = n(n+1)/2" for the n = k + 1 case so we have done what we wanted. Proof complete.
edit: Yeah, I see your confusion. I'm not assuming the k + 1 case because I am not assuming that the left hand side equals anything. I am just writing down "1 + 2 + 3 + ... + k + (k+1)" and sort of seeing where it takes me. The reason I wrote it down is because I know that that expression is part of what I'm looking for (the equation in blue).
I think I've got it! You're not assuming the (k + 1) case; instead, you're inserting (k + 1) into the lefthand side, then substituting the assumption for the series of integers, and then rewriting, manipulating, and simplifying the lefthand side until you reach the result, which happens to be the same as the assumption. Is that correct?
Yup! you're correct except for one word:
"..until you reach the result, which happens to be the same as the assumption."
Not sure if that is a typo or not. Remember that I didn't assume the k+1 case so that would be an assumption. Rather, the result is the same as "1 + 2 + 3 + ... + n = n(n+1)/2" if you plug in k+1. So what I would instead say is
"..until you reach the result, which happens to be the same as the statement of the k+1 case."

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Mathematical Induction  Help for a Beginner?
My next question is how I can generalize what I've learned in this starter example to solve other cases. Any tips?
Re: Mathematical Induction  Help for a Beginner?
The real answer is to really just work through practice examples. Induction is 2 steps:
1) Prove the base (n=0 or n=1) case
2) Prove the inductive step. I.e. prove that IF the n = k case holds THEN the n = k + 1 case holds.
Those are the only 'rules' to induction proofs. Induction doesn't give you any tips of how to prove step 1 or step 2. In this particular example you proved step 1 by just plugging it in and seeing that it works. for step 2 you can basically start with the assumption and then derive the conclusion you're looking for by doing some algebraic manipulations. That's basically how a lot of these proofs go but you'll just have to try more examples from your text and see how it goes. Good luck! If you have more questions bring them here!
1) Prove the base (n=0 or n=1) case
2) Prove the inductive step. I.e. prove that IF the n = k case holds THEN the n = k + 1 case holds.
Those are the only 'rules' to induction proofs. Induction doesn't give you any tips of how to prove step 1 or step 2. In this particular example you proved step 1 by just plugging it in and seeing that it works. for step 2 you can basically start with the assumption and then derive the conclusion you're looking for by doing some algebraic manipulations. That's basically how a lot of these proofs go but you'll just have to try more examples from your text and see how it goes. Good luck! If you have more questions bring them here!
Re: Mathematical Induction  Help for a Beginner?
FWIW, it's possible to find this particular formula without induction.
First a simple example.
Let S = 1 + 2 + 3 + 4 + 5
Then 2S =
1 + 2 + 3 + 4 + 5 +
5 + 4 + 3 + 2 + 1
= 6 + 6 + 6 + 6 + 6
We have 5 columns where each column sums to 6.
So 2S = 5 x 6 and thus S = 5 x 6 / 2 = 15.
Now we generalize:
Let S = 1 + 2 + 3 + ... + (k2) + (k1) + k
Then 2S =
1 + 2 + 3 + ... + (k2) + (k1) + k +
k + (k1) + (k2)+ ... + 3 + 2 + 1
Now we have k columns where each column sums to k+1
So 2S = k x (k+1) and thus S = k(k+1)/2
Allegedly, the young C. F. Gauss used this method in primary school to sum the numbers from 1 to 100. See http://en.wikipedia.org/wiki/Carl_Fried ... #Anecdotes
First a simple example.
Let S = 1 + 2 + 3 + 4 + 5
Then 2S =
1 + 2 + 3 + 4 + 5 +
5 + 4 + 3 + 2 + 1
= 6 + 6 + 6 + 6 + 6
We have 5 columns where each column sums to 6.
So 2S = 5 x 6 and thus S = 5 x 6 / 2 = 15.
Now we generalize:
Let S = 1 + 2 + 3 + ... + (k2) + (k1) + k
Then 2S =
1 + 2 + 3 + ... + (k2) + (k1) + k +
k + (k1) + (k2)+ ... + 3 + 2 + 1
Now we have k columns where each column sums to k+1
So 2S = k x (k+1) and thus S = k(k+1)/2
Allegedly, the young C. F. Gauss used this method in primary school to sum the numbers from 1 to 100. See http://en.wikipedia.org/wiki/Carl_Fried ... #Anecdotes
Re: Mathematical Induction  Help for a Beginner?
It may be worth mentioning that “proof by induction” is nothing more than syntactic sugar for a proof by contradiction. The goal is to prove that there is no smallest counterexample to a claim, hence there can be no counterexamples at all, and the argument is as follows:
Claim to be proved: Some function f(n) = 0 for all natural numbers.
Proof: Suppose the claim is false. Then there is at least one natural number for which f(n) is nonzero. Let m be the smallest such number. In other words, m is the least counterexample to the claim.
For all natural numbers k < m, we know that f(k) = 0, because m is the smallest number where that is not the case. Then, using the fact that f(k) = 0 for all k < m and that f(m) is not zero, and using the specific properties of the given function f, we derive a contradiction.
Most commonly, the contradiction is reached by demonstrating that f(m1)=0 implies f(m)=0. Having f(m)=0 contradicts the assumption that m is a counterexample. However, to finish the proof one must also show that m is not zero, because if m were zero then m1 would not belong to the set of natural numbers.
Having produced a contradiction based on the assumption that a counterexample exists, it follows that no counterexample can possibly exist. Therefore the claim is true for all natural numbers.
Claim to be proved: Some function f(n) = 0 for all natural numbers.
Proof: Suppose the claim is false. Then there is at least one natural number for which f(n) is nonzero. Let m be the smallest such number. In other words, m is the least counterexample to the claim.
For all natural numbers k < m, we know that f(k) = 0, because m is the smallest number where that is not the case. Then, using the fact that f(k) = 0 for all k < m and that f(m) is not zero, and using the specific properties of the given function f, we derive a contradiction.
Most commonly, the contradiction is reached by demonstrating that f(m1)=0 implies f(m)=0. Having f(m)=0 contradicts the assumption that m is a counterexample. However, to finish the proof one must also show that m is not zero, because if m were zero then m1 would not belong to the set of natural numbers.
Having produced a contradiction based on the assumption that a counterexample exists, it follows that no counterexample can possibly exist. Therefore the claim is true for all natural numbers.
wee free kings
Re: Mathematical Induction  Help for a Beginner?
That sounds like an a bit artificial way to equate it with a proof by contradiction. Proof by contradiction works by working from the assumption that the proposition is false and showing that that leads to a contradiction. Induction works by showing that when it's true for 0 or 1 it's true for all the natural numbers after that.
It explicitly shows that it's true for all these numbers. Where exactly is the contradiction when using the normal method?
If I not missing something in your reasoning I don't see the difference to calling Proof by exhaustion a proof by contradiction because it being wrong requires a counter example an we have exhaustively shown that it's true for all cases and thus that there is no counterexample.
Sure you can arrive at the method from a proof from contradiction, but it works fine without doing that and formulating it as proof by contradiction adds nothing to it nor does it lead to a better understanding of induction.
It explicitly shows that it's true for all these numbers. Where exactly is the contradiction when using the normal method?
If I not missing something in your reasoning I don't see the difference to calling Proof by exhaustion a proof by contradiction because it being wrong requires a counter example an we have exhaustively shown that it's true for all cases and thus that there is no counterexample.
Sure you can arrive at the method from a proof from contradiction, but it works fine without doing that and formulating it as proof by contradiction adds nothing to it nor does it lead to a better understanding of induction.
Re: Mathematical Induction  Help for a Beginner?
Well but you've haven't actually exhaustively proved all cases. You've proven one cased and you've proven that P(n) implies P(n+1) for all n. The argument for why those two things are enough to conclude that P(n) holds for all n is by contradiction.
I do agree that that's a little different from saying induction is the "same thing" as proofbycontradiction, but it is true that any any induction proof can be reformulated as a proof by contradiction using the wellordering principle.
I do agree that that's a little different from saying induction is the "same thing" as proofbycontradiction, but it is true that any any induction proof can be reformulated as a proof by contradiction using the wellordering principle.
Re: Mathematical Induction  Help for a Beginner?
Doesn't the Induction Axiom show that it holds for all n?
 Robert'); DROP TABLE *;
 Posts: 730
 Joined: Mon Sep 08, 2008 6:46 pm UTC
 Location: in ur fieldz
Re: Mathematical Induction  Help for a Beginner?
I wouldn't say that the two are equivalent, at least without some caveats, e.g. you might want to only talk about a specific subset of the naturals, or you're inducting over a treelike structure and your inductive case has multiple "parents". My high school math textbook certainly involved some proofs by induction that started out with n=2 or n=3, and you wind up with a more complicated case if you want to do something like prove correctness of merge sort.
The way I generally think of it is that you're taking advantage of the (IIRC, axiomatic) statement that IF P(m) AND [P(k)→P(k+1)] THEN P(A) is true for all A>m. The most important part of that statement being that the second part of the AND is a implication, not a standalone statement, and can still be true even if the antecedent is false. That makes it slightly clearer why the 2nd part of the proof is allowed to assume that P(k) is true  you're not proving the statement P(k+1), you're proving the conditional [P(k)→P(k+1)] and the easiest (only?) way to do that is to assume P(k) (that is, imagine a new hypothetical system where P(k) is true) and then, within this new notsureifcorrect system/universe, prove P(k+1).
(Although, of course, "k+1" in the above doesn't always mean k+1, but whatever is immediately "after" k in whatever set you want to induct over.)
The way I generally think of it is that you're taking advantage of the (IIRC, axiomatic) statement that IF P(m) AND [P(k)→P(k+1)] THEN P(A) is true for all A>m. The most important part of that statement being that the second part of the AND is a implication, not a standalone statement, and can still be true even if the antecedent is false. That makes it slightly clearer why the 2nd part of the proof is allowed to assume that P(k) is true  you're not proving the statement P(k+1), you're proving the conditional [P(k)→P(k+1)] and the easiest (only?) way to do that is to assume P(k) (that is, imagine a new hypothetical system where P(k) is true) and then, within this new notsureifcorrect system/universe, prove P(k+1).
(Although, of course, "k+1" in the above doesn't always mean k+1, but whatever is immediately "after" k in whatever set you want to induct over.)
...And that is how we know the Earth to be bananashaped.
Re: Mathematical Induction  Help for a Beginner?
I guess Wikipedia says mathematical induction is equivalent to well ordering. You use well ordering in combination with a proof by contradiction to prove you can do mathematical induction on a set.
edit: I guess also also that the axiom of regularity is equivalent to an axiom of induction..
edit: I guess also also that the axiom of regularity is equivalent to an axiom of induction..
Re: Mathematical Induction  Help for a Beginner?
From the sidebar at http://en.wikipedia.org/wiki/Peano_axioms#Formulation
And from ωconsistent theory
Wikipedia wrote:
The set of natural numbers can be illustrated by the infinite chain of light wood domino pieces, their first one corresponding to zero, and each piece facing its top side towards its successor. However, the Peano axioms 1–8 are also fulfilled by the incontiguous structure consisting of both light and dark wood pieces. The induction axiom, 9, corresponds to the requirement that if the first light wood domino piece (0) is overthrown, then each piece will eventually fall ("domino effect"); this is satisfied only in the absence of the dark pieces.
And from ωconsistent theory
Wikipedia wrote:A theory T is said to interpret the language of arithmetic if there is a translation of formulas of arithmetic into the language of T so that T is able to prove the basic axioms of the natural numbers under this translation.
A T that interprets arithmetic is ωinconsistent if, for some property P of natural numbers (defined by a formula in the language of T), T proves P(0), P(1), P(2), and so on (that is, for every standard natural number n, T proves that P(n) holds), but T also proves that there is some (necessarily nonstandard) natural number n such that P(n) fails. This may not lead directly to an outright contradiction, because T may not be able to prove for any specific value of n that P(n) fails, only that there is such an n.
T is ωconsistent if it is not ωinconsistent.
Re: Mathematical Induction  Help for a Beginner?
One of the common operations in propositional logic is modus ponens, or implication elimination, which boils down to:
In other words, if you know that when S is true that T is also true, and you also know that S is true, then you know that T is true.
Induction says that you can apply that logic in an infinite regression. It's like having a list of implications:
Then all you need to do to prove S(n) (that is, prove that some statement about integers is true for a particular integer n) is prove S(1), and then apply n steps of modus ponens. Induction is just letting you boil that list of implications into a single one, and then saying that it's allowed to apply that implication an arbitrary number of times:
Code: Select all
1. IF S implies T; and
2. IF S; then
3. T
In other words, if you know that when S is true that T is also true, and you also know that S is true, then you know that T is true.
Induction says that you can apply that logic in an infinite regression. It's like having a list of implications:
Code: Select all
1. IF S(1) implies S(2); and
2. IF S(2) implies S(3); and
3. IF S(3) implies S(4); and
...
Then all you need to do to prove S(n) (that is, prove that some statement about integers is true for a particular integer n) is prove S(1), and then apply n steps of modus ponens. Induction is just letting you boil that list of implications into a single one, and then saying that it's allowed to apply that implication an arbitrary number of times:
Code: Select all
1. IF, for some arbitrary k, S(k) implies S(k+1); and
2. S(0); then
3. S(n) for all n >= 0
pollywog wrote:I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Mathematical Induction  Help for a Beginner?
ConMan wrote:Induction says that you can apply that logic in an infinite regression.
Excepting that you only ever apply it a finite number of times for any number. The chain of implications is never other than finite.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Mathematical Induction  Help for a Beginner?
jestingrabbit wrote:ConMan wrote:Induction says that you can apply that logic in an infinite regression.
Excepting that you only ever apply it a finite number of times for any number. The chain of implications is never other than finite.
True. In this case, I use infinite to mean "the number of times you can apply the logic has no upper bound".
pollywog wrote:I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
 phlip
 Restorer of Worlds
 Posts: 7572
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: Mathematical Induction  Help for a Beginner?
Here's one way to think about it: Say you're trying to prove some sequence of statements, P_{n}, is true for all n. In this case, P_{n} is "1 + 2 + ... + n = n(n+1)/2"... so for example P_{3} is the statement "1+2+3 = 3(3+1)/2". But it can be any sequence of statements, this is just an example.
Now, we can try to prove this directly... that is, we can try to prove:
So the simple thing to do is write a general proof for all the statements at once. A proof that says "For any given n, [words words proof words] and so P_{n} is true." And since the proof we wrote works for any n, without caring which one it is, it should work for every n, and we've proven all the different statements at once. In principle, you could take any particular one of the statements you cared about, substitute the appropriate value of n into the proof, and you'd have a proof of that particular statement.
For a simple example, take P_{n} as the statement "n^{2} + 2n + 1 = (n+1)^{2}". We can say "For any given n, n^{2} + 2n + 1 = (n^{2} + n) + (n + 1) = n(n + 1) + (n + 1) = (n + 1)(n + 1) = (n + 1)^{2}".
Then, if we needed to prove the statement for, say, P_{17}, we can just say "17^{2} + 2*17 + 1 = (17^{2} + 17) + (17 + 1) = 17(17 + 1) + (17 + 1) = (17 + 1)(17 + 1) = (17 + 1)^{2}"... even though we could directly prove P_{17} by just calculating that both sides are 324, the general proof means we've proven it for all the different n's at once.
However, for things like the trianglenumber sum, we can't use this method of just solving it directly for every n. We don't really have the tools we need to figure out what "1 + 2 + ... + n" adds up to, in a general sense... that's what we're trying to figure out with this proof. So we need a different tack.
Induction means that instead of trying to prove each statement individually directly, we use each one to prove the next:
But again, that's an infinite list of things we need to prove, so we go general, in the same way as before... and we end up needing two proofs: our base case, "[words words proof here], therefore P_{1}", and our inductive statement: "For any given n, [more proof words], therefore if P_{n} is true, then P_{n+1} must be true".
It's that second proof that's usually the more complicated one (usually the base case is pretty trivial)... and much of the challenge is just that the thing you're trying to prove, "if P_{n} is true, then P_{n+1} must be true", is a relatively complicated statement. But once you break it down, it comes down to the same as proving any other conditional.
And the way you do that, is by assumption. That is, to prove "if A is true, then B must be true" your proof looks like "Assume A is true. Then, [word words words]. Therefore, B is also true." Since assuming A lead you to prove B, then the whole proof including the assumption is, together, a proof that if A is true then B must be true (because whenever A is true, the assumption in our proof holds, and so the rest of the proof must apply, proving B). For instance, "Assume it's raining. Water is currently falling on the ground. Therefore the ground is wet." is a proof of "if it's raining, then the ground will be wet".
And so, to break down our inductive statement, the proof will look like "For any given n, assume P_{n} is true. Then, [words words words]. Therefore, P_{n+1} is also true."
It feels kinda circular, because the thing that you're assuming looks so similar to the thing you're proving... but what you're doing is assuming each statement and using it to prove the next one... and the base case is what keeps it all nailed down, and stops it from looping in on itself forever.
The usual mathematical term here is "arbitrarily large"... reserving "infinite" for things that actually are, well, not finite.
Now, we can try to prove this directly... that is, we can try to prove:
 Prove P_{1}
 Prove P_{2}
 Prove P_{3}
 ...
So the simple thing to do is write a general proof for all the statements at once. A proof that says "For any given n, [words words proof words] and so P_{n} is true." And since the proof we wrote works for any n, without caring which one it is, it should work for every n, and we've proven all the different statements at once. In principle, you could take any particular one of the statements you cared about, substitute the appropriate value of n into the proof, and you'd have a proof of that particular statement.
For a simple example, take P_{n} as the statement "n^{2} + 2n + 1 = (n+1)^{2}". We can say "For any given n, n^{2} + 2n + 1 = (n^{2} + n) + (n + 1) = n(n + 1) + (n + 1) = (n + 1)(n + 1) = (n + 1)^{2}".
Then, if we needed to prove the statement for, say, P_{17}, we can just say "17^{2} + 2*17 + 1 = (17^{2} + 17) + (17 + 1) = 17(17 + 1) + (17 + 1) = (17 + 1)(17 + 1) = (17 + 1)^{2}"... even though we could directly prove P_{17} by just calculating that both sides are 324, the general proof means we've proven it for all the different n's at once.
However, for things like the trianglenumber sum, we can't use this method of just solving it directly for every n. We don't really have the tools we need to figure out what "1 + 2 + ... + n" adds up to, in a general sense... that's what we're trying to figure out with this proof. So we need a different tack.
Induction means that instead of trying to prove each statement individually directly, we use each one to prove the next:
 Prove P_{1}
 Prove that if P_{1} is true, then P_{2} must be true
 Prove that if P_{2} is true, then P_{3} must be true
 Prove that if P_{3} is true, then P_{4} must be true
 ...
But again, that's an infinite list of things we need to prove, so we go general, in the same way as before... and we end up needing two proofs: our base case, "[words words proof here], therefore P_{1}", and our inductive statement: "For any given n, [more proof words], therefore if P_{n} is true, then P_{n+1} must be true".
It's that second proof that's usually the more complicated one (usually the base case is pretty trivial)... and much of the challenge is just that the thing you're trying to prove, "if P_{n} is true, then P_{n+1} must be true", is a relatively complicated statement. But once you break it down, it comes down to the same as proving any other conditional.
And the way you do that, is by assumption. That is, to prove "if A is true, then B must be true" your proof looks like "Assume A is true. Then, [word words words]. Therefore, B is also true." Since assuming A lead you to prove B, then the whole proof including the assumption is, together, a proof that if A is true then B must be true (because whenever A is true, the assumption in our proof holds, and so the rest of the proof must apply, proving B). For instance, "Assume it's raining. Water is currently falling on the ground. Therefore the ground is wet." is a proof of "if it's raining, then the ground will be wet".
And so, to break down our inductive statement, the proof will look like "For any given n, assume P_{n} is true. Then, [words words words]. Therefore, P_{n+1} is also true."
It feels kinda circular, because the thing that you're assuming looks so similar to the thing you're proving... but what you're doing is assuming each statement and using it to prove the next one... and the base case is what keeps it all nailed down, and stops it from looping in on itself forever.
ConMan wrote:True. In this case, I use infinite to mean "the number of times you can apply the logic has no upper bound".
The usual mathematical term here is "arbitrarily large"... reserving "infinite" for things that actually are, well, not finite.
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Re: Mathematical Induction  Help for a Beginner?
phlip wrote:So the simple thing to do is write a general proof for all the statements at once. A proof that says "For any given n, [words words proof words] and so P_{n} is true." And since the proof we wrote works for any n, without caring which one it is, it should work for every n, and we've proven all the different statements at once. In principle, you could take any particular one of the statements you cared about, substitute the appropriate value of n into the proof, and you'd have a proof of that particular statement.
This is not the correct understanding of induction on natural numbers.
Specifically, the rule of logic being used is the infinite law of excluded middle (ILEM) Ex(~P(x)) v Ax(P(x)) where x is a natural number NN(x) and ~ means not. In fact, this is what Cantor used to justify his infinitary mathematics. For example, it is used in the diagonal argument.
Not all agree with this step in logic. Below is from Solomon Feferman.
Brouwer argued that LEM for infinite sets is based on an unjustified extension of that principle from finite sets. In his doctoral dissertation of 1907, he had already insisted on the subjective origin of mathematics in human intuition, and on the necessity to restrict questions of truth in mathematics to those statements which can be verified or disproved.
Solomon Feferman. “The development of programs for the foundations of mathematics in the ﬁrst third of the 20th century” academia.edu.
So, induction may feel funny to some. Anyway, ILEM is used to prove mathematical induction as follows.
TH. Assume P(0) is true and for any NN(n) P(n)>P(n+1). Then P(n) is true for all natural numbers n.
PROOF. Apply ILEM and assume P fails for some NN(x). Form the set S={k: P(k)} fails. S is nonempty since P(x) fails. So choose the least element s in S. Assume s=0. But, by assumption P(0) is true, which is a contradiction. So assume s>0. Then P(s1) is true since s is the least such element in S. But, by assumption P(s1)>p(s). Hence, P(s) is true, which is a contradiction. By ILEM, Ex(~P(x)) has been proven false so Ax(P(x) and the theorem is proven.
Hence, the theorem above shows why induction holds as true and ILEM is the logical basis on which it depends,
 gmalivuk
 GNU Terry Pratchett
 Posts: 26767
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Mathematical Induction  Help for a Beginner?
It's not meant to be the rigorous proof of induction, it's meant to be an explanation of how/why it works.who cares wrote:This is not the correct understanding of induction on natural numbers.
Re: Mathematical Induction  Help for a Beginner?
gmalivuk wrote:It's not meant to be the rigorous proof of induction, it's meant to be an explanation of how/why it works.who cares wrote:This is not the correct understanding of induction on natural numbers.
Moreover, it was just an early part of a long verbal exposition about induction, and hadn't even got into induction per se at that point. At that early point, phlip was merely pointing out that proving something true for all natural numbers requires proving infinitely many statements.
 Forest Goose
 Posts: 377
 Joined: Sat May 18, 2013 9:27 am UTC
Re: Mathematical Induction  Help for a Beginner?
who cares wrote:So, induction may feel funny to some. Anyway, ILEM is used to prove mathematical induction as follows.
TH. Assume P(0) is true and for any NN(n) P(n)>P(n+1). Then P(n) is true for all natural numbers n.
PROOF. Apply ILEM and assume P fails for some NN(x). Form the set S={k: P(k)} fails. S is nonempty since P(x) fails. So choose the least element s in S. Assume s=0. But, by assumption P(0) is true, which is a contradiction. So assume s>0. Then P(s1) is true since s is the least such element in S. But, by assumption P(s1)>p(s). Hence, P(s) is true, which is a contradiction. By ILEM, Ex(~P(x)) has been proven false so Ax(P(x) and the theorem is proven.
Hence, the theorem above shows why induction holds as true and ILEM is the logical basis on which it depends,
Your proof, also, is a little bit off, or pointless, since you're assuming that every set of naturals has a least element, which is classically equivalent to induction. Ultimately, your presentation is misleading since the excluded middle applies to situations where induction/least elements aren't being used (it applies to sets of reals too; and while we can well order them, we needn't do so to apply the excluded middle) and because you are assuming a classical equivalent, then pointing to EM as if it was doing the work (like a magician pointing to their assistant).
This is not the correct understanding of induction on natural numbers.
Heyting Arithmetic has induction too, in exactly the same form...you just have to use intuitionistic logic in proofs, so it doesn't prove everything that can be proven in PA.
Hilbert and Brouwer did have debates over all of this stuff, that's true, but the basic notion of induction wasn't the problem  and your comments don't really seem to highlight any of the issues, they seem to do the opposite, actually (and I'm confused what any of this has to do with helping someone understand induction in a classical context anyway...all you've done is use way too many symbols and abbreviations in a misleading proof and, seemingly, mention some vaguely related things about intuitionism and Cantor).
In fact, this is what Cantor used to justify his infinitary mathematics.
That's a weird statement for this conversation, honestly. Also, while it is outside of my usual, I know that IZF talks about "large sets" ("large cardinals" doesn't work out so well since we lose linear order on the ordinals). I'm not sure about CZF, or whatever else is out there, but constructive mathematics doesn't imply finitism, as far as I've seen. Of course, there are models with everything subcountable in CZF; and everything with an apartness in IZF...
But that's digressing, I don't see the point of the statement to begin with, as pertains to anything being discussed here.
Qaanol wrote:It may be worth mentioning that “proof by induction” is nothing more than syntactic sugar for a proof by contradiction.
I'm not sure I'd go with that, it's rather glib. In PA, induction and well ordering work out to say the same thing, but I wouldn't relate induction as, somehow, reducing to proof by contradiction (in general or specific)  even if that would be the simple, and usual, way to use it. Moreover, induction is intuitive on its own, just as much as using the well ordering (maybe more so, actually).
Twistar wrote:edit: I guess also also that the axiom of regularity is equivalent to an axiom of induction..
They're talking about a different kind of induction, though  specifically, episiloninduction, not arithmetical induction (as in the sense of PA).
Forest Goose: A rare, but wily, form of goose; best known for dropping on unsuspecting hikers, from trees, to steal sweets.
Re: Mathematical Induction  Help for a Beginner?
gmalivuk wrote:It's not meant to be the rigorous proof of induction, it's meant to be an explanation of how/why it works.
It's not really about rigor. It's a question as to why induction is justified.
And it is justified based on ILEM and that is why it works. That was the point of my post.
Re: Mathematical Induction  Help for a Beginner?
skullturf wrote:At that early point, phlip was merely pointing out that proving something true for all natural numbers requires proving infinitely many statements.
Nope proving an infinite collection of statements is based on infinitary logic. Traditional first order logic only includes finite length proofs.
Further, mathematical induction is proven without verifying an infinite collection of statements which many regard as impossible.
So, I simply pointed out that ILEM is required to prove induction.
Now, if you think you or others can prove some property P holds true for all natural numbers without using ILEM I would like to see that proof because Solomon Feferman concedes, for example, that there is no way to apply a decidable predicate P to every element of an infinite collection.
Re: Mathematical Induction  Help for a Beginner?
Forest Goose wrote:Your proof, also, is a little bit off, or pointless, since you're assuming that every set of naturals has a least element, which is classically equivalent to induction.
Uhhh, no. Every natural number is coded in ZFC as an ordinal. Every set of ordinals has a least element (see Kunen theorem 7.3(5)). Now, if you can produce any set of natural numbers that does not contain a least element, then do it.
Forest Goose wrote:Ultimately, your presentation is misleading since the excluded middle applies to situations where induction/least elements aren't being used
See Keisler & Chang Model Theory, the appendix for set theory and their proof of transfinite induction A.6. ILEM is used and the least element of a set of ordinals is part of the proof.
 Forest Goose
 Posts: 377
 Joined: Sat May 18, 2013 9:27 am UTC
Re: Mathematical Induction  Help for a Beginner?
who cares wrote:Uhhh, no. Every natural number is coded in ZFC as an ordinal. Every set of ordinals has a least element (see Kunen theorem 7.3(5)). Now, if you can produce any set of natural numbers that does not contain a least element, then do it.
See Keisler & Chang Model Theory, the appendix for set theory and their proof of transfinite induction A.6. ILEM is used and the least element of a set of ordinals is part of the proof.
See, I assumed, as most would, that we were talking PA not ZFC  it's weird to encounter induction over the naturals and find someone complaining about the excluded middle in ZFC and induction over the ordinals...you realize one of those, and it isn't PA, is about a billion times stronger than the other, right? I'm sorry, your objection is so strange, I'm not sure how to respond to it. It is really really odd, though, to me, that you feel the need to bring in the entire strength of ZFC and the standard model of PA to justify induction and well order on the naturals (especially when they already classically have them anyway). It's also weird that you are going on about intuitionistic things, but then asserting, as if platonistically, that naturals do have such things...but, whatever.
I am a bit surprised that you don't bring up the actual objections, of Brouwer's, about Hilbert's formalizing induction, etc. etc.
Your last bit is weird too, by the way, why am I looking up transfinite induction in response to my comment about the reals? The excluded middle doesn't require that I be working in the context of any given well ordering (and the ordinals aren't the universe of sets, anyway, so I'm still not sure what the point of your comment was)?
Why, by the way, are you, citing an appendix on set theory from an intro to classical model theory to make a point about ZFC and transfinite induction in response to a comment about reals in response to your discussion of intuitionistic stuff pertaining to induction in PA...see why that seems weird? That's kind of weird. What, ultimately, is your point?
You don't need to cite undergraduate set theory, by the way, that's a very basic fact  perhaps, the problem isn't that I'm not aware of it (I am), but that it isn't actually salient? Something to mull over
Forest Goose: A rare, but wily, form of goose; best known for dropping on unsuspecting hikers, from trees, to steal sweets.
Re: Mathematical Induction  Help for a Beginner?
Indeed your questions deserve a reply.
I am not bringing in the "strength" of ZFC, I am simply indicating why PA induction has a justification. If you have a proof in some I don't know PA world, please show it in a finite number of steps. I already know why it is accepted and the ILEM is why as I showed.
Odd you think I am promoting "intuitionistic things" when it does not include ILEM. Now understand, platonists accept ILEM and many cardinalities and intuitionists only believe in a set of all natural numbers with ILEM as not included. But, they accept a set of all natural numbers not with ILEM but with human intuition, whatever that means.
This is not relevant to this thread. If you want to open up a thread and discuss these things feel free.
Well the rank function would characterize the universe of sets. But,this thread is about proofs as applied to natural numbers (finite ordinals).
I did not just cite Keisler & Chang, I also cited Kunen. I presented no Intuitionism at all. So, the rest of your comment is. I don't even know.
The sources I cited are grad school references. If you think that is false, prove it.
Forest Goose wrote:See, I assumed, as most would, that we were talking PA not ZFC  it's weird to encounter induction over the naturals and find someone complaining about the excluded middle in ZFC and induction over the ordinals...you realize one of those, and it isn't PA, is about a billion times stronger than the other, right? I'm sorry, your objection is so strange, I'm not sure how to respond to it. It is really really odd, though, to me, that you feel the need to bring in the entire strength of ZFC and the standard model of PA to justify induction and well order on the naturals (especially when they already classically have them anyway). It's also weird that you are going on about intuitionistic things, but then asserting, as if platonistically, that naturals do have such things...but, whatever.
I am not bringing in the "strength" of ZFC, I am simply indicating why PA induction has a justification. If you have a proof in some I don't know PA world, please show it in a finite number of steps. I already know why it is accepted and the ILEM is why as I showed.
Odd you think I am promoting "intuitionistic things" when it does not include ILEM. Now understand, platonists accept ILEM and many cardinalities and intuitionists only believe in a set of all natural numbers with ILEM as not included. But, they accept a set of all natural numbers not with ILEM but with human intuition, whatever that means.
Forest Goose wrote:I am a bit surprised that you don't bring up the actual objections, of Brouwer's, about Hilbert's formalizing induction, etc. etc.
This is not relevant to this thread. If you want to open up a thread and discuss these things feel free.
Forest Goose wrote:]
Your last bit is weird too, by the way, why am I looking up transfinite induction in response to my comment about the reals? The excluded middle doesn't require that I be working in the context of any given well ordering (and the ordinals aren't the universe of sets, anyway, so I'm still not sure what the point of your comment was)?
Well the rank function would characterize the universe of sets. But,this thread is about proofs as applied to natural numbers (finite ordinals).
Forest Goose wrote:Why, by the way, are you, citing an appendix on set theory from an intro to classical model theory to make a point about ZFC and transfinite induction in response to a comment about reals in response to your discussion of intuitionistic stuff pertaining to induction in PA...see why that seems weird? That's kind of weird. What, ultimately, is your point?
I did not just cite Keisler & Chang, I also cited Kunen. I presented no Intuitionism at all. So, the rest of your comment is. I don't even know.
Forest Goose wrote:You don't need to cite undergraduate set theory, by the way, that's a very basic fact  perhaps, the problem isn't that I'm not aware of it (I am), but that it isn't actually salient? Something to mull over
The sources I cited are grad school references. If you think that is false, prove it.
Re: Mathematical Induction  Help for a Beginner?
who cares wrote:The sources I cited are grad school references. If you think that is false, prove it.
Hey just a friendly tip here: when the title of a thread includes the words “Help for a beginner” and your first idea is to cite multiple graduatelevel references, it may be worth taking the time to think of a second idea.
wee free kings
Re: Mathematical Induction  Help for a Beginner?
who cares wrote:skullturf wrote:At that early point, phlip was merely pointing out that proving something true for all natural numbers requires proving infinitely many statements.
Nope proving an infinite collection of statements is based on infinitary logic. Traditional first order logic only includes finite length proofs.
Further, mathematical induction is proven without verifying an infinite collection of statements which many regard as impossible.
Fair point. I chose my words carelessly. I probably shouldn't have said "proving infinitely many statements". Perhaps I should have said something along the lines of "establishing the truth of infinitely many facts" or "establishing that a property holds of infinitely many numbers".
who cares wrote:So, I simply pointed out that ILEM is required to prove induction.
That may or may not be true, but in a thread about helping a beginner with induction, it's kind of a digression.
When helping beginners with mathematical induction, it makes sense to assume classical logic, and to point out that although we cannot directly prove an infinite list of statements
1 has property P
2 has property P
3 has property P
4 has property P
etc.
we nonetheless regard their truth as established if we can prove the two statements
1 has property P
If n has property P, then n+1 has property P.
This is an acceptable description of induction for a beginner, in a context in which classical logic is used.
I'm sure there's an interesting discussion to be had about the ways in which alternative logics deal with mathematical induction, but that's sort of a separate issue from the question of how to explain standard induction to a beginner.
 phlip
 Restorer of Worlds
 Posts: 7572
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: Mathematical Induction  Help for a Beginner?
To clarify: my explanation above of what induction is was in no way rigorous, was full of handwaviness, and even if completely fleshed out probably wouldn't stand up under scrutiny. That's not the point.
The point was to given an explanation of induction that made sense for a beginner (the hint is in the thread title). That means using analogies and highlevel explanations to trigger the reader's intuition, to try to make the penny drop, so they understand what's going on, before diving into what's going on at the lowlevel with specific PA models, let alone different basis logic systems.
If everything you're saying about intuitionist logic and ZFC and omegainconsistency and philosophy of logic and whatnot is how you'd provide quote "Help for a beginner"... then I recommend you not become a teacher any time soon.
The point was to given an explanation of induction that made sense for a beginner (the hint is in the thread title). That means using analogies and highlevel explanations to trigger the reader's intuition, to try to make the penny drop, so they understand what's going on, before diving into what's going on at the lowlevel with specific PA models, let alone different basis logic systems.
If everything you're saying about intuitionist logic and ZFC and omegainconsistency and philosophy of logic and whatnot is how you'd provide quote "Help for a beginner"... then I recommend you not become a teacher any time soon.
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
 Forest Goose
 Posts: 377
 Joined: Sat May 18, 2013 9:27 am UTC
Re: Mathematical Induction  Help for a Beginner?
who cares wrote:I am not bringing in the "strength" of ZFC, I am simply indicating why PA induction has a justification. If you have a proof in some I don't know PA world, please show it in a finite number of steps. I already know why it is accepted and the ILEM is why as I showed.
Yes, you are. As soon as you start talking about encoding things as ordinals, you're talking about ZFC, not PA.
Odd you think I am promoting "intuitionistic things" when it does not include ILEM. Now understand, platonists accept ILEM and many cardinalities and intuitionists only believe in a set of all natural numbers with ILEM as not included. But, they accept a set of all natural numbers not with ILEM but with human intuition, whatever that means.
Then, wtf? You're the one that started talking about the excluded middle and correct understandings of induction and Brouwer, you realize that, right? What was your point, then? Induction is not equivalent to the excluded middle (especially not PA induction...).
Was your entire point, "Excluded middle is involved somewhere"? The excluded middle certainly doesn't "justify", or "found" induction, induction exists in settings without the excluded middle  and the excluded middle, in general, is used most everywhere that isn't intuitionistic stuff. That'd be like interjecting in every math thread everywhere and saying, "Ah, but excluded middle, that's how you understand it" or you might as well say "Induction is founded on the material conditional!", because those are involved too. Just because the excluded middle is someways used doesn't mean it is center stage  and your Brouwer quote, regarding intuitionistic things (which we were never discussing and weren't involved) does not entail that the excluded middle is the right way to understand induction.
This is not relevant to this thread. If you want to open up a thread and discuss these things feel free.
So...you bring up Brouwer, the excluded middle, and complain about explanations of induction; but those things aren't relevant? Again, what were you trying to say?
Well the rank function would characterize the universe of sets. But,this thread is about proofs as applied to natural numbers (finite ordinals).
Are you talking about finite ordinals or are you talking about PA? Just because one encodes in the other does not make them the same thing.
I did not just cite Keisler & Chang, I also cited Kunen. I presented no Intuitionism at all. So, the rest of your comment is. I don't even know.
You're bringing up things about Brouwer and the excluded middle, to what end?
The sources I cited are grad school references. If you think that is false, prove it.
1.) You cited a trivial undergrad point; grad ref or no.
2.) Still introductory stuff, honestly.
3.) Never said it was false, said it wasn't relevant and was too trivial to require one (let alone two) references.
You seem to assume I've been saying "You're wrong", I'm saying "You either have no real point" or "You're saying something so so very trivial, there's no point in mentioning it, and you're saying it in an obfuscating way"  one of those seems to be the case. Your first post really doesn't need a bunch of random symbols and halfbaked proofs. Sorry, but multiple grad sources for trivial facts, goofy symbols in a thread for "Helping a beginner", and objecting to informal descriptions with random quotes (totally not related to Brouwer and intuitionism) and some point (whatever it was) about the "ILEM"...you just seem like you're trying to look impressive, more than actually saying something.
Last edited by Forest Goose on Thu Feb 26, 2015 5:35 am UTC, edited 2 times in total.
Forest Goose: A rare, but wily, form of goose; best known for dropping on unsuspecting hikers, from trees, to steal sweets.
 gmalivuk
 GNU Terry Pratchett
 Posts: 26767
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Mathematical Induction  Help for a Beginner?
who cares wrote:Forest Goose wrote:I am a bit surprised that you don't bring up the actual objections, of Brouwer's, about Hilbert's formalizing induction, etc. etc.
This is not relevant to this thread. If you want to open up a thread and discuss these things feel free.
1) You do not get to decide what is relevant to this thread, as you neither started it nor do you moderate this or any other part of the forum.The sources I cited are grad school references. If you think that is false, prove it.
2) You especially don't get to tell someone else their post isn't relevant when you're the one who thinks it's appropriate to bring "grad school references" and the full strength of ZFC to bear on a beginner's question about induction.
Re: Mathematical Induction  Help for a Beginner?
gmalivuk wrote:who cares wrote:Forest Goose wrote:I am a bit surprised that you don't bring up the actual objections, of Brouwer's, about Hilbert's formalizing induction, etc. etc.
This is not relevant to this thread. If you want to open up a thread and discuss these things feel free.1) You do not get to decide what is relevant to this thread, as you neither started it nor do you moderate this or any other part of the forum.The sources I cited are grad school references. If you think that is false, prove it.
2) You especially don't get to tell someone else their post isn't relevant when you're the one who thinks it's appropriate to bring "grad school references" and the full strength of ZFC to bear on a beginner's question about induction.
When you write in red does that mean you are not to be questioned?
If that is not the case what is the purpose of writing in red?
Re: Mathematical Induction  Help for a Beginner?
The red writing means he has his moderator hat on. So proceed with caution.
 gmalivuk
 GNU Terry Pratchett
 Posts: 26767
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Mathematical Induction  Help for a Beginner?
Writing in red means I'm posting in "official" moderator mode, usually to explain rules and consequences in a thread.who cares wrote:gmalivuk wrote:who cares wrote:Forest Goose wrote:I am a bit surprised that you don't bring up the actual objections, of Brouwer's, about Hilbert's formalizing induction, etc. etc.
This is not relevant to this thread. If you want to open up a thread and discuss these things feel free.1) You do not get to decide what is relevant to this thread, as you neither started it nor do you moderate this or any other part of the forum.The sources I cited are grad school references. If you think that is false, prove it.
2) You especially don't get to tell someone else their post isn't relevant when you're the one who thinks it's appropriate to bring "grad school references" and the full strength of ZFC to bear on a beginner's question about induction.
When you write in red does that mean you are not to be questioned?
If that is not the case what is the purpose of writing in red?
And yes, inasmuch as general threads aren't the place to discuss mod decisions (that should be done via PM instead), it also means I'm not to be questioned.
Re: Mathematical Induction  Help for a Beginner?
gmalivuk wrote: it also means I'm not to be questioned.
Yes, well enjoy your forum.
I am not into Nazi type authoritative arrangements.
I've already measured you and you are in no position to act intellectually in a position of authority over me with this matter. But, if you would like to debate this matter without having to resort to forum authority instead of intellectual authority, then I would do that. Otherwise, I am simply not into those that cannot defend their thinking with pure intellect.
Have a nice day.
 gmalivuk
 GNU Terry Pratchett
 Posts: 26767
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Mathematical Induction  Help for a Beginner?
who cares wrote:gmalivuk wrote: it also means I'm not to be questioned.
Yes, well enjoy your forum.
I am not into Nazi type authoritative arrangements.
I've already measured you and you are in no position to act intellectually in a position of authority over me with this matter. But, if you would like to debate this matter without having to resort to forum authority instead of intellectual authority, then I would do that. Otherwise, I am simply not into those that cannot defend their thinking with pure intellect.
Have a nice day.
I'm honestly tempted to frame this and put it on the wall over my computer, except if I started doing that for every child who quit the forums in a blaze of Mike Godwin, I would quickly run out of wall space.
Who is online
Users browsing this forum: No registered users and 3 guests