With the Curry-Howard correspondence and its realization in Coq in mind, we can now take a deeper look at induction principles.

Basics

Every time we declare a new Inductive datatype, Coq automatically generates an induction principle for this type. This induction principle is a theorem like any other: If t is defined inductively, the corresponding induction principle is called t_ind. Here is the one for natural numbers:

In English: Suppose P is a property of natural numbers (that is, P n is a Prop for every n). To show that P n holds of all n, it suffices to show:

• P holds of 0
• for any n, if P holds of n, then P holds of S n.

The induction tactic is a straightforward wrapper that, at its core, simply performs apply t_ind. To see this more clearly, let's experiment with directly using apply nat_ind, instead of the induction tactic, to carry out some proofs. Here, for example, is an alternate proof of a theorem that we saw in the Induction chapter.

This proof is basically the same as the earlier one, but a few minor differences are worth noting. First, in the induction step of the proof (the "S" case), we have to do a little bookkeeping manually (the intros) that induction does automatically. Second, we do not introduce n into the context before applying nat_ind -- the conclusion of nat_ind is a quantified formula, and apply needs this conclusion to exactly match the shape of the goal state, including the quantifier. By contrast, the induction tactic works either with a variable in the context or a quantified variable in the goal. Third, we had to manually supply the name of the induction principle with apply, but induction figures that out itself. These conveniences make induction nicer to use in practice than applying induction principles like nat_ind directly. But it is important to realize that, modulo these bits of bookkeeping, applying nat_ind is what we are really doing.

Exercise: 2 stars, standard, optional (plus_one_r')

Complete this proof without using the induction tactic.

Coq generates induction principles for every datatype defined with Inductive, including those that aren't recursive. Although of course we don't need induction to prove properties of non-recursive datatypes, the idea of an induction principle still makes sense for them: it gives a way to prove that a property holds for all values of the type. These generated principles follow a similar pattern. If we define a type t with constructors c₁ ... cn, Coq generates a theorem with this shape:
    t_ind : ∀ P : t → Prop,
              ... case for c₁ ... →
              ... case for c₂ ... → ...
              ... case for cn ... →
              ∀ n : t, P n

The specific shape of each case depends on the arguments to the corresponding constructor. Before trying to write down a general rule, let's look at some more examples. First, an example where the constructors take no arguments:

Exercise: 1 star, standard, optional (rgb)

Write out the induction principle that Coq will generate for the following datatype. Write down your answer on paper or type it into a comment, and then compare it with what Coq prints.

Here's another example, this time with one of the constructors taking some arguments.

Exercise: 1 star, standard, optional (natlist1)

Suppose we had written the above definition a little differently:

Now what will the induction principle look like? ☐ In general, the automatically generated induction principle for inductive type t is formed as follows:

• Each constructor c generates one case of the principle.
• If c takes no arguments, that case is:
        "P holds of c"
• If c takes arguments x₁:a₁ ... xn:an, that case is:
        "For all x₁:a₁ ... xn:an, if [P] holds of each of the arguments of type [t], then [P] holds of [c x₁ ... xn]"

Exercise: 1 star, standard, optional (booltree_ind)

Write out the induction principle that Coq will generate for the following datatype. (Again, write down your answer on paper or type it into a comment, and then compare it with what Coq prints.)

Exercise: 1 star, standard, optional (ex_set)

Here is an induction principle for an inductively defined set.
      ExSet_ind :
         ∀ P : ExSet → Prop,
             (∀ b : bool, P (con1 b)) →
             (∀ (n : nat) (e : ExSet), P e → P (con2 n e)) →
             ∀ e : ExSet, P e

Give an Inductive definition of ExSet:

Polymorphism

What about polymorphic datatypes? The inductive definition of polymorphic lists
      Inductive list (X:Type) : Type :=
        | nil : list X
        | cons : X → list X → list X.

is very similar to that of natlist. The main difference is that, here, the whole definition is parameterized on a set X: that is, we are defining a family of inductive types list X, one for each X. (Note that, wherever list appears in the body of the declaration, it is always applied to the parameter X.) The induction principle is likewise parameterized on X:
      list_ind :
        ∀ (X : Type) (P : list X → Prop),
           P [] →
           (∀ (x : X) (l : list X), P l → P (x :: l)) →
           ∀ l : list X, P l

Note that the whole induction principle is parameterized on X. That is, list_ind can be thought of as a polymorphic function that, when applied to a type X, gives us back an induction principle specialized to the type list X.

Exercise: 1 star, standard, optional (tree)

Write out the induction principle that Coq will generate for the following datatype. Compare your answer with what Coq prints.

Exercise: 1 star, standard, optional (mytype)

Find an inductive definition that gives rise to the following induction principle:
      mytype_ind :
        ∀ (X : Type) (P : mytype X → Prop),
            (∀ x : X, P (constr1 X x)) →
            (∀ n : nat, P (constr2 X n)) →
            (∀ m : mytype X, P m →
               ∀ n : nat, P (constr3 X m n)) →
            ∀ m : mytype X, P m

☐

Exercise: 1 star, standard, optional (foo)

Find an inductive definition that gives rise to the following induction principle:
      foo_ind :
        ∀ (X Y : Type) (P : foo X Y → Prop),
             (∀ x : X, P (bar X Y x)) →
             (∀ y : Y, P (baz X Y y)) →
             (∀ f₁ : nat → foo X Y,
               (∀ n : nat, P (f₁ n)) → P (quux X Y f₁)) →
             ∀ f₂ : foo X Y, P f₂

☐

Exercise: 1 star, standard, optional (foo')

Consider the following inductive definition:

What induction principle will Coq generate for foo'? Fill in the blanks, then check your answer with Coq.)
     foo'_ind :
        ∀ (X : Type) (P : foo' X → Prop),
              (∀ (l : list X) (f : foo' X),
                    _______________________ →
                    _______________________ ) →
             ___________________________________________ →
             ∀ f : foo' X, ________________________

☐

Induction Hypotheses

Where does the phrase "induction hypothesis" fit into this story? The induction principle for numbers
       ∀ P : nat → Prop,
            P 0 →
            (∀ n : nat, P n → P (S n)) →
            ∀ n : nat, P n

is a generic statement that holds for all propositions P (or rather, strictly speaking, for all families of propositions P indexed by a number n). Each time we use this principle, we are choosing P to be a particular expression of type nat→Prop. We can make proofs by induction more explicit by giving this expression a name. For example, instead of stating the theorem mult_0_r as "∀ n, n × 0 = 0," we can write it as "∀ n, P_m0r n", where P_m0r is defined as...

... or equivalently:

Now it is easier to see where P_m0r appears in the proof.

This extra naming step isn't something that we do in normal proofs, but it is useful to do it explicitly for an example or two, because it allows us to see exactly what the induction hypothesis is. If we prove ∀ n, P_m0r n by induction on n (using either induction or apply nat_ind), we see that the first subgoal requires us to prove P_m0r 0 ("P holds for zero"), while the second subgoal requires us to prove ∀ n', P_m0r n' → P_m0r (S n') (that is "P holds of S n' if it holds of n'" or, more elegantly, "P is preserved by S"). The induction hypothesis is the premise of this latter implication -- the assumption that P holds of n', which we are allowed to use in proving that P holds for S n'.

More on the induction Tactic

The induction tactic actually does even more low-level bookkeeping for us than we discussed above. Recall the informal statement of the induction principle for natural numbers:

• If P n is some proposition involving a natural number n, and we want to show that P holds for all numbers n, we can reason like this:
  • show that P O holds
  • show that, if P n' holds, then so does P (S n')
  • conclude that P n holds for all n.

So, when we begin a proof with intros n and then induction n, we are first telling Coq to consider a particular n (by introducing it into the context) and then telling it to prove something about all numbers (by using induction). What Coq actually does in this situation, internally, is to "re-generalize" the variable we perform induction on. For example, in our original proof that plus is associative...

It also works to apply induction to a variable that is quantified in the goal.

Note that induction n leaves m still bound in the goal -- i.e., what we are proving inductively is a statement beginning with ∀ m. If we do induction on a variable that is quantified in the goal after some other quantifiers, the induction tactic will automatically introduce the variables bound by these quantifiers into the context.

Exercise: 1 star, standard, optional (plus_explicit_prop)

Rewrite both plus_assoc' and plus_comm' and their proofs in the same style as mult_0_r'' above -- that is, for each theorem, give an explicit Definition of the proposition being proved by induction, and state the theorem and proof in terms of this defined proposition.

Induction Principles in Prop

Earlier, we looked in detail at the induction principles that Coq generates for inductively defined sets. The induction principles for inductively defined propositions like even are a tiny bit more complicated. As with all induction principles, we want to use the induction principle on even to prove things by inductively considering the possible shapes that something in even can have. Intuitively speaking, however, what we want to prove are not statements about evidence but statements about numbers: accordingly, we want an induction principle that lets us prove properties of numbers by induction on evidence. For example: From what we've said so far, you might expect the inductive definition of even...
      Inductive even : nat → Prop :=
      | ev_0 : even 0
      | ev_SS : ∀ n : nat, even n → even (S (S n)).

...to give rise to an induction principle that looks like this...
    ev_ind_max : ∀ P : (∀ n : nat, even n → Prop),
         P O ev_0 →
         (∀ (m : nat) (E : even m),
            P m E →
            P (S (S m)) (ev_SS m E)) →
         ∀ (n : nat) (E : even n),
         P n E

... because:

• Since even is indexed by a number n (every even object E is a piece of evidence that some particular number n is even), the proposition P is parameterized by both n and E -- that is, the induction principle can be used to prove assertions involving both an even number and the evidence that it is even.
• Since there are two ways of giving evidence of evenness (even has two constructors), applying the induction principle generates two subgoals:
  • We must prove that P holds for O and ev_0.
  • We must prove that, whenever m is an even number and E is an evidence of its evenness, if P holds of m and E, then it also holds of S (S m) and ev_SS m E.
• If these subgoals can be proved, then the induction principle tells us that P is true for all even numbers n and evidence E of their evenness.

This is more flexibility than we normally need or want: it is giving us a way to prove logical assertions where the assertion involves properties of some piece of evidence of evenness, while all we really care about is proving properties of numbers that are even -- we are interested in assertions about numbers, not about evidence. It would therefore be more convenient to have an induction principle for proving propositions P that are parameterized just by n and whose conclusion establishes P for all even numbers n:
       ∀ P : nat → Prop,
         ... →
       ∀ n : nat,
         even n → P n

For this reason, Coq actually generates the following simplified induction principle for even:

In particular, Coq has dropped the evidence term E as a parameter of the the proposition P. In English, ev_ind says: Suppose P is a property of natural numbers (that is, P n is a Prop for every n). To show that P n holds whenever n is even, it suffices to show:

• P holds for 0,
• for any n, if n is even and P holds for n, then P holds for S (S n).

As expected, we can apply ev_ind directly instead of using induction. For example, we can use it to show that ev' (the slightly awkward alternate definition of evenness that we saw in an exercise in the \chap{IndProp} chapter) is equivalent to the cleaner inductive definition ev:

The precise form of an Inductive definition can affect the induction principle Coq generates.

This definition can be streamlined a little by observing that the left-hand argument n is the same everywhere in the definition, so we can actually make it a "general parameter" to the whole definition, rather than an argument to each constructor.

The second one is better, even though it looks less symmetric. Why? Because it gives us a simpler induction principle.

Formal vs. Informal Proofs by Induction

Question: What is the relation between a formal proof of a proposition P and an informal proof of the same proposition P? Answer: The latter should teach the reader how to produce the former. Question: How much detail is needed?? Unfortunately, there is no single right answer; rather, there is a range of choices. At one end of the spectrum, we can essentially give the reader the whole formal proof (i.e., the "informal" proof will amount to just transcribing the formal one into words). This may give the reader the ability to reproduce the formal one for themselves, but it probably doesn't teach them anything much. At the other end of the spectrum, we can say "The theorem is true and you can figure out why for yourself if you think about it hard enough." This is also not a good teaching strategy, because often writing the proof requires one or more significant insights into the thing we're proving, and most readers will give up before they rediscover all the same insights as we did. In the middle is the golden mean -- a proof that includes all of the essential insights (saving the reader the hard work that we went through to find the proof in the first place) plus high-level suggestions for the more routine parts to save the reader from spending too much time reconstructing these (e.g., what the IH says and what must be shown in each case of an inductive proof), but not so much detail that the main ideas are obscured. Since we've spent much of this chapter looking "under the hood" at formal proofs by induction, now is a good moment to talk a little about informal proofs by induction. In the real world of mathematical communication, written proofs range from extremely longwinded and pedantic to extremely brief and telegraphic. Although the ideal is somewhere in between, while one is getting used to the style it is better to start out at the pedantic end. Also, during the learning phase, it is probably helpful to have a clear standard to compare against. With this in mind, we offer two templates -- one for proofs by induction over data (i.e., where the thing we're doing induction on lives in Type) and one for proofs by induction over evidence (i.e., where the inductively defined thing lives in Prop).

Induction Over an Inductively Defined Set

Template:

• Theorem: <Universally quantified proposition of the form "For all n:S, P(n)," where S is some inductively defined set.>
  Proof: By induction on n.
  <one case for each constructor c of S...>
  • Suppose n = c a₁ ... ak, where <...and here we state the IH for each of the a's that has type S, if any>. We must show <...and here we restate P(c a₁ ... ak)>.
    <go on and prove P(n) to finish the case...>
  • <other cases similarly...> ☐

Example:

• Theorem: For all sets X, lists l : list X, and numbers n, if length l = n then index (S n) l = None.
  Proof: By induction on l.
  • Suppose l = []. We must show, for all numbers n, that, if length [] = n, then index (S n) [] = None.
    This follows immediately from the definition of index.
  • Suppose l = x :: l' for some x and l', where length l' = n' implies index (S n') l' = None, for any number n'. We must show, for all n, that, if length (x::l') = n then index (S n) (x::l') = None.
    Let n be a number with length l = n. Since
                length l = length (x::l') = S (length l'),
    it suffices to show that
                index (S (length l')) l' = None.
    But this follows directly from the induction hypothesis, picking n' to be length l'. ☐

Induction Over an Inductively Defined Proposition

Since inductively defined proof objects are often called "derivation trees," this form of proof is also known as induction on derivations. Template:

• Theorem: <Proposition of the form "Q → P," where Q is some inductively defined proposition (more generally, "For all x y z, Q x y z → P x y z")>
  Proof: By induction on a derivation of Q. <Or, more generally, "Suppose we are given x, y, and z. We show that Q x y z implies P x y z, by induction on a derivation of Q x y z"...>
  <one case for each constructor c of Q...>
  • Suppose the final rule used to show Q is c. Then <...and here we state the types of all of the a's together with any equalities that follow from the definition of the constructor and the IH for each of the a's that has type Q, if there are any>. We must show <...and here we restate P>.
    <go on and prove P to finish the case...>
  • <other cases similarly...> ☐

Example

• Theorem: The ≤ relation is transitive -- i.e., for all numbers n, m, and o, if n ≤ m and m ≤ o, then n ≤ o.
  Proof: By induction on a derivation of m ≤ o.
  • Suppose the final rule used to show m ≤ o is le_n. Then m = o and we must show that n ≤ m, which is immediate by hypothesis.
  • Suppose the final rule used to show m ≤ o is le_S. Then o = S o' for some o' with m ≤ o'. We must show that n ≤ S o'. By induction hypothesis, n ≤ o'.
    But then, by le_S, n ≤ S o'. ☐

Explicit Proof Objects for Induction (Optional)

Although tactic-based proofs are normally much easier to work with, the ability to write a proof term directly is sometimes very handy, particularly when we want Coq to do something slightly non-standard. Recall again the induction principle on naturals that Coq generates for us automatically from the Inductive declation for nat.

There's nothing magic about this induction lemma: it's just another Coq lemma that requires a proof. Coq generates the proof automatically too...

We can read this as follows: Suppose we have evidence f that P holds on 0, and evidence f₀ that ∀ n:nat, P n → P (S n). Then we can prove that P holds of an arbitrary nat n via a recursive function F (here defined using the expression form Fix rather than by a top-level Fixpoint declaration). F pattern matches on n:

• If it finds 0, F uses f to show that P n holds.
• If it finds S n₀, F applies itself recursively on n₀ to obtain evidence that P n₀ holds; then it applies f₀ on that evidence to show that P (S n) holds.

F is just an ordinary recursive function that happens to operate on evidence in Prop rather than on terms in Set. We can adapt this approach to proving nat_ind to help prove non-standard induction principles too. As a motivating example, suppose that we want to prove the following lemma, directly relating the ev predicate we defined in IndProp to the evenb function defined in Basics.

Attempts to prove this by standard induction on n fail in the case for S (S n), because the induction hypothesis only tells us something about S n, which is useless. There are various ways to hack around this problem; for example, we can use ordinary induction on n to prove this (try it!): Lemma evenb_ev' : ∀ n : nat, (evenb n = true → ev n) ∧ (evenb (S n) = true → ev (S n)). But we can make a much better proof by defining and proving a non-standard induction principle that goes "by twos":

Once you get the hang of it, it is entirely straightforward to give an explicit proof term for induction principles like this. Proving this as a lemma using tactics is much less intuitive. The induction ... using tactic variant gives a convenient way to utilize a non-standard induction principle like this.

The Coq Trusted Computing Base

One issue that arises with any automated proof assistant is "why trust it?": what if there is a bug in the implementation that renders all its reasoning suspect? While it is impossible to allay such concerns completely, the fact that Coq is based on the Curry-Howard correspondence gives it a strong foundation. Because propositions are just types and proofs are just terms, checking that an alleged proof of a proposition is valid just amounts to type-checking the term. Type checkers are relatively small and straightforward programs, so the "trusted computing base" for Coq -- the part of the code that we have to believe is operating correctly -- is small too. What must a typechecker do? Its primary job is to make sure that in each function application the expected and actual argument types match, that the arms of a match expression are constructor patterns belonging to the inductive type being matched over and all arms of the match return the same type, and so on. There are a few additional wrinkles:

• Since Coq types can themselves be expressions, the checker must normalize these (by using the computation rules) before comparing them.
• The checker must make sure that match expressions are exhaustive. That is, there must be an arm for every possible constructor. To see why, consider the following alleged proof object:
        Definition or_bogus : ∀ P Q, P ∨ Q → P :=
          fun (P Q : Prop) (A : P ∨ Q) ⇒
             match A with
             | or_introl H ⇒ H
             end.
  All the types here match correctly, but the match only considers one of the possible constructors for or. Coq's exhaustiveness check will reject this definition.
• The checker must make sure that each fix expression terminates. It does this using a syntactic check to make sure that each recursive call is on a subexpression of the original argument. To see why this is essential, consider this alleged proof:
            Definition nat_false : ∀ (n:nat), False :=
               fix f (n:nat) : False := f n.
  Again, this is perfectly well-typed, but (fortunately) Coq will reject it.

Note that the soundness of Coq depends only on the correctness of this typechecking engine, not on the tactic machinery. If there is a bug in a tactic implementation (and this certainly does happen!), that tactic might construct an invalid proof term. But when you type Qed, Coq checks the term for validity from scratch. Only lemmas whose proofs pass the type-checker can be used in further proof developments.