Mathematical Induction - Help for a Beginner?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Nyktos
Posts: 138
Joined: Mon Mar 02, 2009 4:02 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Nyktos » Fri Jan 02, 2015 10:02 pm UTC

MathDoofus wrote:
Twistar wrote:
Which step?


Step 1, where you include the (k + 1) in the series on the left-hand side.
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
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby MathDoofus » Fri Jan 02, 2015 10:30 pm UTC

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 left-hand side, then substituting the assumption for the series of integers, and then re-writing, manipulating, and simplifying the left-hand side until you reach the result, which happens to be the same as the assumption. Is that correct?

Twistar
Posts: 445
Joined: Sat May 09, 2009 11:39 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Twistar » Fri Jan 02, 2015 10:53 pm UTC

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 left-hand side, then substituting the assumption for the series of integers, and then re-writing, manipulating, and simplifying the left-hand 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."

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby MathDoofus » Fri Jan 02, 2015 10:56 pm UTC

My next question is how I can generalize what I've learned in this starter example to solve other cases. Any tips?

Twistar
Posts: 445
Joined: Sat May 09, 2009 11:39 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Twistar » Fri Jan 02, 2015 11:01 pm UTC

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!

User avatar
PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: Mathematical Induction - Help for a Beginner?

Postby PM 2Ring » Sat Jan 03, 2015 6:36 am UTC

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 + ... + (k-2) + (k-1) + k
Then 2S =
  1   +  2    +   3 +  ... + (k-2) + (k-1) + k +
  k + (k-1) + (k-2)+ ...  +  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

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Qaanol » Sat Jan 03, 2015 8:18 am UTC

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(m-1)=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 m-1 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

User avatar
PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby PeteP » Sat Jan 03, 2015 4:59 pm UTC

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.

Nyktos
Posts: 138
Joined: Mon Mar 02, 2009 4:02 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Nyktos » Sat Jan 03, 2015 5:28 pm UTC

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 proof-by-contradiction, but it is true that any any induction proof can be reformulated as a proof by contradiction using the well-ordering principle.

User avatar
PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby PeteP » Sat Jan 03, 2015 5:52 pm UTC

Doesn't the Induction Axiom show that it holds for all n?

User avatar
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?

Postby Robert'); DROP TABLE *; » Sat Jan 03, 2015 6:03 pm UTC

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 tree-like 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 not-sure-if-correct 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 banana-shaped.

Twistar
Posts: 445
Joined: Sat May 09, 2009 11:39 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Twistar » Sat Jan 03, 2015 8:10 pm UTC

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

User avatar
PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: Mathematical Induction - Help for a Beginner?

Postby PM 2Ring » Sun Jan 04, 2015 1:06 am UTC

From the sidebar at http://en.wikipedia.org/wiki/Peano_axioms#Formulation
Wikipedia wrote:Image
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.

User avatar
ConMan
Shepherd's Pie?
Posts: 1690
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: Mathematical Induction - Help for a Beginner?

Postby ConMan » Sun Jan 04, 2015 10:52 pm UTC

One of the common operations in propositional logic is modus ponens, or implication elimination, which boils down to:

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:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.

User avatar
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?

Postby jestingrabbit » Mon Jan 05, 2015 5:06 am UTC

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.

User avatar
ConMan
Shepherd's Pie?
Posts: 1690
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: Mathematical Induction - Help for a Beginner?

Postby ConMan » Mon Jan 05, 2015 5:30 am UTC

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:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.

User avatar
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?

Postby phlip » Mon Jan 05, 2015 6:03 am UTC

Here's one way to think about it: Say you're trying to prove some sequence of statements, Pn, is true for all n. In this case, Pn is "1 + 2 + ... + n = n(n+1)/2"... so for example P3 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:
  • Prove P1
  • Prove P2
  • Prove P3
  • ...
but trying to prove these all one at a time will take a long time - there's infinitely many of them, after all!

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 Pn 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 Pn as the statement "n2 + 2n + 1 = (n+1)2". We can say "For any given n, n2 + 2n + 1 = (n2 + 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, P17, we can just say "172 + 2*17 + 1 = (172 + 17) + (17 + 1) = 17(17 + 1) + (17 + 1) = (17 + 1)(17 + 1) = (17 + 1)2"... even though we could directly prove P17 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 triangle-number 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 P1
  • Prove that if P1 is true, then P2 must be true
  • Prove that if P2 is true, then P3 must be true
  • Prove that if P3 is true, then P4 must be true
  • ...
It's easy enough to see that if we can prove every one of these, then Pn must be true for every n, because for each n there's a (possibly very long, but still finite) list of implications that leads back to something we know to be true (P1).

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 P1", and our inductive statement: "For any given n, [more proof words], therefore if Pn is true, then Pn+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 Pn is true, then Pn+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 Pn is true. Then, [words words words]. Therefore, Pn+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)⚠);}
[he/him/his]

who cares
Posts: 7
Joined: Mon Feb 23, 2015 11:14 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby who cares » Mon Feb 23, 2015 11:50 pm UTC

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 Pn 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 first 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(s-1) is true since s is the least such element in S. But, by assumption P(s-1)->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,

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26765
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Mathematical Induction - Help for a Beginner?

Postby gmalivuk » Tue Feb 24, 2015 3:43 am UTC

who cares wrote:This is not the correct understanding of induction on natural numbers.
It's not meant to be the rigorous proof of induction, it's meant to be an explanation of how/why it works.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

skullturf
Posts: 556
Joined: Thu Dec 07, 2006 8:37 pm UTC
Location: Chicago
Contact:

Re: Mathematical Induction - Help for a Beginner?

Postby skullturf » Tue Feb 24, 2015 5:06 am UTC

gmalivuk wrote:
who cares wrote:This is not the correct understanding of induction on natural numbers.
It's not meant to be the rigorous proof of induction, it's meant to be an explanation of how/why it works.


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.

User avatar
Forest Goose
Posts: 377
Joined: Sat May 18, 2013 9:27 am UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Forest Goose » Tue Feb 24, 2015 5:32 am UTC

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(s-1) is true since s is the least such element in S. But, by assumption P(s-1)->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, episilon-induction, 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.

who cares
Posts: 7
Joined: Mon Feb 23, 2015 11:14 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby who cares » Tue Feb 24, 2015 10:34 pm UTC

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.

who cares
Posts: 7
Joined: Mon Feb 23, 2015 11:14 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby who cares » Tue Feb 24, 2015 10:43 pm UTC

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.

who cares
Posts: 7
Joined: Mon Feb 23, 2015 11:14 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby who cares » Tue Feb 24, 2015 10:56 pm UTC

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.

User avatar
Forest Goose
Posts: 377
Joined: Sat May 18, 2013 9:27 am UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Forest Goose » Wed Feb 25, 2015 4:27 am UTC

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.

who cares
Posts: 7
Joined: Mon Feb 23, 2015 11:14 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby who cares » Wed Feb 25, 2015 11:59 pm UTC

Indeed your questions deserve a reply.
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.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Qaanol » Thu Feb 26, 2015 2:19 am UTC

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 graduate-level references, it may be worth taking the time to think of a second idea.
wee free kings

skullturf
Posts: 556
Joined: Thu Dec 07, 2006 8:37 pm UTC
Location: Chicago
Contact:

Re: Mathematical Induction - Help for a Beginner?

Postby skullturf » Thu Feb 26, 2015 3:04 am UTC

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.

User avatar
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?

Postby phlip » Thu Feb 26, 2015 4:43 am UTC

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 high-level 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 low-level with specific PA models, let alone different basis logic systems.

If everything you're saying about intuitionist logic and ZFC and omega-inconsistency 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)⚠);}
[he/him/his]

User avatar
Forest Goose
Posts: 377
Joined: Sat May 18, 2013 9:27 am UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Forest Goose » Thu Feb 26, 2015 4:53 am UTC

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 half-baked 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.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26765
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Mathematical Induction - Help for a Beginner?

Postby gmalivuk » Thu Feb 26, 2015 4:55 am UTC

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.
The sources I cited are grad school references. If you think that is false, prove it.
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.

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.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

who cares
Posts: 7
Joined: Mon Feb 23, 2015 11:14 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby who cares » Sun Mar 01, 2015 12:14 am UTC

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.
The sources I cited are grad school references. If you think that is false, prove it.
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.

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?

User avatar
PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: Mathematical Induction - Help for a Beginner?

Postby PM 2Ring » Sun Mar 01, 2015 12:18 am UTC

The red writing means he has his moderator hat on. So proceed with caution.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26765
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Mathematical Induction - Help for a Beginner?

Postby gmalivuk » Sun Mar 01, 2015 12:23 am UTC

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.
The sources I cited are grad school references. If you think that is false, prove it.
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.

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?
Writing in red means I'm posting in "official" moderator mode, usually to explain rules and consequences in a thread.

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.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

who cares
Posts: 7
Joined: Mon Feb 23, 2015 11:14 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby who cares » Sun Mar 01, 2015 12:35 am UTC

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.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26765
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Mathematical Induction - Help for a Beginner?

Postby gmalivuk » Sun Mar 01, 2015 12:54 am UTC

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.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 8 guests