25
$\begingroup$

Context: I'm studying for my discrete mathematics exam and I keep running into this question that I've failed to solve. The question is as follows.


Problem: The main form for normal induction over natural numbers $n$ takes the following form:

  1. $P(1)$ is true, and
  2. for every $n, P(n-1)\to P(n).\qquad\qquad\qquad\text{[Sometimes written as $P(n)\to P(n+1)$]}$

If both 1 and 2 are true, then $P(n)$ is true for every $n$.

The question is to prove the correctness of the form above.


My work: My idea was to make a boolean statement and if it's a tautology in a true false table. That means the statement is always correct.

I've tried many times but I've failed.

Here is the original question in Hebrew:

n טענה כלשהי לגבי מםפר טבעי $P(n)$ תהי

אם מתקימיים שני התנאים הבאים:

1- הטענה $P(0)$ נכונה

2- לכל n>0, $P(n)$ נכונות הטענה $P(n-1)$ גוררת את נכונות הטענה

אז $P(n)$ נכונה לכל מספר טבעי n

הוכיחו את נכונות משפט זה

$\endgroup$

marked as duplicate by Najib Idrissi, Alex M., Tom-Tom, Mankind, user149792 Sep 2 '15 at 15:41

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ What's "the previous form"? $\endgroup$ – GFauxPas Feb 8 '15 at 20:13
  • 1
    $\begingroup$ Do you know about the well-ordering principle? $\endgroup$ – Daniel W. Farlow Feb 8 '15 at 20:19
  • 14
    $\begingroup$ You cannot prove Induction by truth-table, because it is not a tautology. $\endgroup$ – Mauro ALLEGRANZA Feb 8 '15 at 20:29
  • 3
    $\begingroup$ The Hebrew shows that the question is asking for a proof for the validity of induction. $\endgroup$ – GFauxPas Feb 8 '15 at 23:33
  • 2
    $\begingroup$ You have lots of good answers here; now that you understand that induction is either an axiom on its own, or a consequence of some other axiom, it is entertaining to imagine number systems in which induction does not hold. For instance, you could have a number system with the numbers zero, one, two... and also Bob, a number that is the successor of no number. You could define rules for summing Bob with other numbers, and so on. Induction doesn't have to work in this system; a proof by induction just shows that the fact is true for all non-Bob numbers, not for all numbers. $\endgroup$ – Eric Lippert Feb 8 '15 at 23:48
16
$\begingroup$

Your question seems somewhat unclear to me, as it stands, but I'll answer the one in the title, and if the question is updated, I'll address that too.

Mathematical induction can be taken as its own axiom, independent from the other (though, as comments point out, it can be proven as a theorem in common systems like ZF). That is to say, it is more akin to statements like: $$x\cdot (y+1)=x\cdot y + x$$ which are often taken to be part of the definition of multiplication and may not be derivable from more basic statements. The point behind such definitions is to capture some intuitive idea - the above starts to capture the distributive property of multiplication, which we know from intuition to be a reasonable idea. Yet, it is possible that we could not prove the above statement without taking it as an axiom.

Induction basically says every natural number can be "reached" from zero. That is, if we have proven the statements:

  • $P(1)$ is true
  • $P(n)\rightarrow P(n+1).$

Then, we can build a proof for every natural number. For instance, if we wanted to know that $P(5)$ was true, we could infer that, since $P(1)$ is true and $P(1)\rightarrow P(2)$, we have $P(2)$. But $P(2)\rightarrow P(3)$ and $P(3)\rightarrow P(4)$ and $P(4)\rightarrow P(5)$, thus we can deduce $P(5)$ too. Induction merely says that $P(n)$ must be true for all natural numbers because we can create a proof like the one above for every natural. Without induction, we can, for any natural $n$, create a proof for $P(n)$ - induction just formalizes that and says we're allowed to jump from there to $\forall n[ P(n)]$.

$\endgroup$
  • 8
    $\begingroup$ Induction is rarely an axiom outside Peano or similar systems. But most of the mathematics people see (including things that need induction) does not take place in such a system. Instead, it usually takes place in some variation of ZF where it is a theorem following from the axiom of infinity. $\endgroup$ – Tobias Kildetoft Feb 8 '15 at 21:15
  • 2
    $\begingroup$ @TobiasKildetoft Normally, one shows that the intersection of all inductive sets (which makes sense by the ZF axiom of infinity) gives us a model of Peano's axioms (and that only comforts us that the thing called $\mathbb N$ we want to use exists and is at least as sound as ZF). An induction proof to show, say, $n^2\le 3n!$ for all $n$ almost certainly does not spell out how to define multiplication on the set $\{\{\},\{\{\}\},\{ \{\},\{\{\}\}\},\ldots\}$ $\endgroup$ – Hagen von Eitzen Feb 9 '15 at 9:56
  • $\begingroup$ @HagenvonEitzen Indeed, and thus "induction" becomes a consequence of that axiom rather than being an axiom itself. So sure, we have the Peano axioms "build in", but the fact that they are "build in" is a very important part. $\endgroup$ – Tobias Kildetoft Feb 9 '15 at 9:59
  • 3
    $\begingroup$ @TobiasKildetoft Proving induction from ZF is helpful if and only if the reader was familiar with ZF and the intuition behind its axioms to begin with. The purpose of my answer is to say why we'd expect induction to be true, based on what manipulations we can do for finite cases. A reader interested in what other axioms induction follows from will have to look elsewhere, but I don't think the answer will mislead them (and I slightly edited one questionable statement in the answer). It is not rigorous, but it is not trying to be. $\endgroup$ – Milo Brandt Feb 9 '15 at 13:55
  • 1
    $\begingroup$ @HagenvonEitzen: How can you be comforted by knowing that the standard natural numbers exist based on ZF when the axiom of infinity essentially is a convoluted version of induction itself? To put the question more precisely, why should one believe that the specified inductive class is actually a ZF set? It is more questionable than even higher-order induction axioms, while the meta-logical justification that Milo Brandt and I give (matheducators.stackexchange.com/a/8101/1550) actually do explain induction directly. $\endgroup$ – user21820 Aug 1 '15 at 7:49
31
$\begingroup$

Consider the following definition of mathematical induction (adapted from David Gunderson's book Handbook of Mathematical Induction):


Principle of mathematical induciton: For some fixed integer $b$, and for each integer $n\geq b$, let $S(n)$ be a statement involving $n$. If

  1. $S(b)$ is true, and
  2. for any integer $k\geq b, S(k)\to S(k+1)$,

then for all $n\geq b$, the statement $S(n)$ is true.


Mathematical induction's validity as a valid proof technique may be established as a consequence of a fundamental axiom concerning the set of positive integers (note: this is only one of many possible ways of viewing induction--see the addendum at the end of this answer). The following statement of this axiom is adapted from John Durbin's book Modern Algebra, wherein it is called the Least Integer Principle, but it is often referred to as the Well-Ordering Principle or WOP. The principle is as follows:

Well-Ordering Principle: Every nonempty set of positive integers contains a least element.

The validity of mathematical induction, in this context where we are using the WOP to prove the validity of mathematical induction, is established by using a proof by contradiction. This proof will contain several "steps" or "parts." Before giving all of the steps to the proof of mathematical induction, it may be useful to reformulate the definition of the proof technique in terms of the notation that will be used throughout the sequence of steps in the explanation (for consistency and facilitated understanding):


Reformulated principle of mathematical induction: For some fixed integer $1$, and for each integer $n\geq 1$, let $S(n)$ be a statement involving $n$. If

  1. $S(1)$ is true, and
  2. for any integer $k\geq 1, S(k)\to S(k+1)$,

then for all $n\geq 1$, the statement $S(n)$ is true.

Let 1 and 2 above be denoted by $(\dagger)$ and $(\dagger\dagger)$, respectively.


Steps of the proof that mathematical induction is a consequence of the WOP:

  1. Start by supposing that $S(1)$ is true and that the proposition $S(k) \rightarrow S(k+1)$ is true for all positive integers $k$, i.e., where $(\dagger)$ and $(\dagger\dagger)$ hold as indicated above.

  2. The goal is to verify whether or not $S(n)$ is true for all $n \geq 1$ if $S(1)$ and $S(k) \rightarrow S(k+1)$ are true. The statement of mathematical induction above indicates that $S(n)$ will logically follow if $S(1)$ and $S(k) \rightarrow S(k+1)$ are true, but does $S(n)$ really follow if $(\dagger)$ and $(\dagger\dagger)$ are true? If yes, then mathematical induction is a valid proof technique. If not, then it is mere rubbish.

  3. We are skeptics, and we think that mathematical induction is a sham (hint: a proof by contradiction is about to take place). Our skepticism induces us to assume that there is at least one positive integer for which $S(n)$ is false [keep in mind that we are assuming that $(\dagger)$ and $(\dagger\dagger)$ are true, albeit we are disputing whether or not $S(n)$ really follows from their truthfulness]. Surely there is at least one positive integer for which $S(n)$ is false even though $S(1)$ and $S(k) \rightarrow S(k+1)$ are true.

  4. Let $\mathcal{P}$ denote the set of all positive integers for which $S(n)$ is false. Is this set empty? We think not---after all, we are assuming that there is at least one positive integer, say $\ell$, for which $S(n)$ is false; that is, the assumption is that $S(\ell)$ is false, where $\ell \in \mathcal{P}$. Are there other positive integers in $\mathcal{P}$? Perhaps, but we cannot say for certain at the moment. We can, however, declare with certainty that $\mathcal{P}$ has a least element by the well-ordering principle. We let the least element of $\mathcal{P}$ be $\ell$ without loss of generality.

  5. Since $S(1)$ is true, we know that $\ell \neq 1$, and because $\ell$ is positive and greater than $1$, we also know that $\ell -1$ must be a positive integer. Moreover, because $\ell -1$ is less than $\ell$, it should be clear that $\ell -1$ cannot be in $\mathcal{P}$ [this is because $\ell$ is the least element in $\mathcal{P}$, meaning that any lesser positive integer cannot be in $\mathcal{P}$]. Notationally, we have it that $\ell \in \mathcal{P}$ and $(\ell - 1) \notin \mathcal{P}$. What does this mean? Since $(\ell - 1) \notin \mathcal{P}$ and $\ell -1$ is a positive integer, and because $\mathcal{P}$ is the set of all positive integers for which $S(n)$ is false, it must be that $S(\ell-1)$ is true.

  6. Finally, recall that we maintained that $(\dagger\dagger)$ was true; that is, $S(k) \rightarrow S(k+1)$ is true for any integer $k \geq 1$. Since $\ell$ and $\ell -1$ are both positive integers, we may let $k = \ell -1$ and $k+1 = \ell$. Substituting these values into the implication that we assume to be true, we get that $S(\ell-1) \rightarrow S(\ell)$. Do you see the problem now (and hence the conclusion of the proof by contradiction)?

  7. By supposing that $(\dagger)$ and $(\dagger\dagger)$ held while also supposing that $S(n)$ was false for some positive integer $\ell$, we deduced through a series of steps that $S(\ell-1) \rightarrow S(\ell)$ [by $(\dagger\dagger)$ where $k = \ell -1$ and $k+1 = \ell$]. What is wrong with this? Simply consider the following three assertions that occur within the proof:

    • $S(\ell-1)\to S(\ell)\qquad$ [True---by supposition $(\dagger\dagger)$]
    • $S(\ell)\qquad$ [False---because of the assumption that $S(n)$ was false for $\ell\in\mathbb{Z^+}$]
    • $S(\ell-1)\qquad$ [True---by the well-ordering principle]

    The logical issue should now be apparent. We know $S(\ell-1) \rightarrow S(\ell)$ is true by our original supposition, but this implication cannot be true if $S(\ell)$ is false. Why? Because an implication of the form $p \rightarrow q$ is only false when the hypothesis, $p$, is true and the conclusion, $q$, is false. In our own case, since $S(\ell-1)$ is true, the implication $S(\ell-1) \rightarrow S(\ell)$ is only true when $S(\ell)$ is also true, thus contradicting the choice of $\ell$. Consequently, $S(n)$ must be true for every positive integer $n$.


Addendum: It may be of interest to other students taking discrete mathematics courses that the form of induction proved above (often referred to simply as "induction") is actually equivalent to both strong induction and the WOP. This may be surprising, but there is a good paper about the Equivalence of Three Variations on Inducton for readers who are interested.

The basic idea behind the equivalence proofs is as follows:

  1. Strong induction implies Induction.
  2. Induction implies Strong Induction.
  3. Well-Ordering of $\mathbb{N}$ implies Induction [This is the proof outlined in this answer but with much greater detail]
  4. Strong Induction implies Well-Ordering of $\mathbb{N}$.

Equivalence of Induction, Strong Induction, and Well-Ordering on $\mathbb{N}$ follows after having proved the four implications outlined above (the paper linked to contains details of the proof(s)).

The answer I provided takes care of (3) above, but you can explore the other three to show equivalence if desired.

$\endgroup$
  • 2
    $\begingroup$ "We also know that $\ell − 1$ must be a positive integer." Can you prove that without induction? It doesn't seem like a trivial statement to me, just hiding a lot inside the assumption of the existence of a predecessor function. $\endgroup$ – DanielV Feb 9 '15 at 6:11
  • 2
    $\begingroup$ By the way, for some food for thought for why @DanielV's objection is an important one, consider why your proof doesn't also show that induction holds on $\mathbb{N}[x]$, under the lexicographic ordering. $\endgroup$ – user7530 Feb 9 '15 at 7:19
  • $\begingroup$ @user7530 Could you please clarify for my sake what $\mathbb N [x]$ refers to? $\endgroup$ – DanielV Feb 9 '15 at 7:28
  • $\begingroup$ Polynomials with natural number coefficients, with $f(x) < g(x)$ if $g(x)-f(x)$ has positive leading term. $\endgroup$ – user7530 Feb 9 '15 at 7:31
  • $\begingroup$ I suggest those who do not understand the proof to read the more concise proof here, en.wikipedia.org/wiki/… , on Wikipedia first. The only step I didn't get is why we assumed the base case must be true, which I understood well after the explanation of Daniel's 3rd step through the first sentence of his 5th step. $\endgroup$ – user3773048 Feb 8 '17 at 0:08
4
$\begingroup$

Formally, induction is an axiom or a consequence of other axioms.

Informally, it can be seen as similar to a proof by contradiction, perhaps something like:

Let $n$ be the smallest value for which $P(n)$ is false.

Unless $n$ is the smallest possible value in $\mathbb{N}$ (i.e. $1$, or if you prefer $0$), we know $P(n-1) \implies P(n)$, so if $P(n)$ is false then so too is $P(n-1)$ contradicting the definition of $n$.

Meanwhile $n$ cannot be the smallest possible value in $\mathbb{N}$, as we know that $P(1)$ was true.

$\endgroup$
4
$\begingroup$

If it feel strange that such a strong proof technique has been placed, almost like cheating, in the definition of the natural numbers, one must bear in mind that induction only is valid in the formal model. There is an ambiguity in our mind, where we might mix up the numbers we obtained from reality with the objects in the slick model of Peano.

Induction is an important part of the definition of the model of natural numbers. If one omit the axiom of induction from the Peano axioms, $\Bbb N$ isn't well defined and larger sets can satisfy the axioms.

The axiom of induction ensures that $\Bbb N$ is the minimal set that satisfies the other axioms.

To see this, let $P(n)\iff n\in N$, where $N$ satisfies the other axioms of Peano. Then the axiom of induction states:

$0\in N$ and $(n\in N\implies n+1\in N)$ implies that for all $n\in\Bbb N$ it holds that $n\in N$. That is, $\Bbb N\subseteq N$.

Also, the minimal $\Bbb N \implies$ principle of induction.

If we can't use axioms for proving theorems, I believe nothing can be proved.

$\endgroup$
  • 1
    $\begingroup$ This seems to be a bit confusing. If you spaek about Peano axioms (that is, an infinite scheme of axioms..) then there are many models of natural numbers, not just the "minimal" one. But maybe you talk about some second-order logic, or uniquness inside ZF (?) $\endgroup$ – Peter Franek Feb 11 '15 at 2:15
  • $\begingroup$ @PeterFranek: It become confusing when mixing the formal model with every day thinking about numbers. But the Peano system is categorical - any two models are isomorphic. $\endgroup$ – Lehs Feb 11 '15 at 8:29
  • $\begingroup$ In which sense are they isomorphic? You are probably familiar with non-standard models of Peano.. $\endgroup$ – Peter Franek Feb 11 '15 at 10:10
  • 1
    $\begingroup$ @PeterFranek: Yes, I see now that only the second order system is categorical. So I guess I consider induction in an second order definition, even if I can't see this. It might be that I include set theory. $\endgroup$ – Lehs Feb 11 '15 at 10:37
0
$\begingroup$

Mathematical induction is definitely the black sheep of common proof methods.

Common proof methods include:

  • Proof by contradiction
  • Direct proof
  • Proof by exhaustion
  • Proof by induction

I'm not sure what else a high school geometry text book might discuss, but let's go with that. The first three all pertain to logic. The fourth pertains to the natural numbers.

Do you agree...

that every subset of the natural numbers $S$ that

  • contains 1, and
  • if it contains some number $a$, then it contains $a+1$

must be the natural numbers?

Then you believe proof by induction works.

That is proof by induction. Say you want to prove that $1+\cdots+n=\frac{(n)(n+1)}{2}$ for all natural numbers $n$. Then let $S$ be the set of all numbers (!!) where that property is true (!!). Now proof by induction looks exactly like that pretty agreeable property of the natural numbers I just stated above.

$\endgroup$
  • 1
    $\begingroup$ @induktio I believe he is addressing frameworks of proofs, where as contraposition is merely a step in a proof $a \rightarrow b \vdash \lnot b \rightarrow \lnot a$. For my part I would add geometric proofs to the list, maybe under the title "proof by construction". $\endgroup$ – DanielV Feb 9 '15 at 10:45
  • $\begingroup$ @induktio I... wasn't trying to write a comprehensive list of proof techniques. $\endgroup$ – djechlin Feb 9 '15 at 14:43
  • $\begingroup$ @djechlin Oh no worries--I've simply seen it almost always listed with the proofs echinacea you did so I thought it was odd to leave it out. Wouldn't expect you to write out all of the proofs techniques there are...that mighty take$\infty$ $\endgroup$ – Daniel W. Farlow Feb 9 '15 at 15:40
0
$\begingroup$

$P(1)$ is given.

With $n=2$, $P(1)\to P(2)$.

With $n=3$, $P(2)\to P(3)$.

With $n=4$, $P(3)\to P(4)$.

$\cdots$

You can continue to establish any $P(n)$.

$\endgroup$
  • 1
    $\begingroup$ This is not a proof. $\endgroup$ – Tobias Kildetoft Feb 9 '15 at 9:01
  • $\begingroup$ @TobiasKildetoft: Please explain why. $\endgroup$ – Yves Daoust Feb 9 '15 at 9:02
  • 1
    $\begingroup$ What do you mean "why"? This is an intuitive explanation for why induction works, which is fine. But it does not say anything about this. And it is certainly not a proof that induction works. $\endgroup$ – Tobias Kildetoft Feb 9 '15 at 9:03
  • 1
    $\begingroup$ @TobiasKildetoft: I disagree. The proof shows that for any $n$ there is a finite chain of implications that establishes $P(n)$, hence $P(n)$ is true for all $n$. The proof is even constructive in that it exhibits that chain of implications. Show me the flaw or undo the downvote. $\endgroup$ – Yves Daoust Feb 9 '15 at 9:06
  • 1
    $\begingroup$ @DanielV: yep, this is intended to be an elementary proof (no axiomatic frame being specified) and "without words". $\endgroup$ – Yves Daoust Feb 9 '15 at 9:58

Not the answer you're looking for? Browse other questions tagged or ask your own question.