Varying the Induction Hypothesis

Sometimes it is important to control the exact form of the induction hypothesis when carrying out inductive proofs in Coq. In particular, we need to be careful about which of the assumptions we move (using intros) from the goal to the context before invoking the induction tactic. For example, suppose we want to show that the double function is injective -- i.e., that it maps different arguments to different results:
    Theorem double_injective: ∀ n m,
      double n = double m → n = m. The way we start this proof is a bit delicate: if we begin with
      intros n. induction n. all is well. But if we begin it with
      intros n m. induction n. we get stuck in the middle of the inductive case... The strategy of doing fewer intros before an induction to obtain a more general IH doesn't always work by itself; sometimes some rearrangement of quantified variables is needed. Suppose, for example, that we wanted to prove double_injective by induction on m instead of n.

At this point, the induction hypothesis, IHn', does not give us n' = m' -- there is an extra S in the way -- so the goal is not provable.

What went wrong? The problem is that, at the point we invoke the induction hypothesis, we have already introduced m into the context -- intuitively, we have told Coq, "Let's consider some particular n and m..." and we now have to prove that, if double n = double m for these particular n and m, then n = m. The next tactic, induction n says to Coq: We are going to show the goal by induction on n. That is, we are going to prove, for all n, that the proposition

• P n = "if double n = double m, then n = m"

holds, by showing

• P O
  (i.e., "if double O = double m then O = m") and
• P n → P (S n)
  (i.e., "if double n = double m then n = m" implies "if double (S n) = double m then S n = m").

If we look closely at the second statement, it is saying something rather strange: it says that, for a particular m, if we know

• "if double n = double m then n = m"

then we can prove

• "if double (S n) = double m then S n = m".

To see why this is strange, let's think of a particular m -- say, 5. The statement is then saying that, if we know

• Q = "if double n = 10 then n = 5"

then we can prove

• R = "if double (S n) = 10 then S n = 5".

But knowing Q doesn't give us any help at all with proving R! (If we tried to prove R from Q, we would start with something like "Suppose double (S n) = 10..." but then we'd be stuck: knowing that double (S n) is 10 tells us nothing about whether double n is 10, so Q is useless.) Trying to carry out this proof by induction on n when m is already in the context doesn't work because we are then trying to prove a relation involving every n but just a single m. The successful proof of double_injective leaves m in the goal statement at the point where the induction tactic is invoked on n:

Notice that both the goal and the induction hypothesis are different this time: the goal asks us to prove something more general (i.e., to prove the statement for every m), but the IH is correspondingly more flexible, allowing us to choose any m we like when we apply the IH.

Now we've chosen a particular m and introduced the assumption that double n = double m. Since we are doing a case analysis on n, we also need a case analysis on m to keep the two "in sync."

The 0 case is trivial:

At this point, since we are in the second branch of the destruct m, the m' mentioned in the context is the predecessor of the m we started out talking about. Since we are also in the S branch of the induction, this is perfect: if we instantiate the generic m in the IH with the current m' (this instantiation is performed automatically by the apply in the next step), then IHn' gives us exactly what we need to finish the proof.

What you should take away from all this is that we need to be careful about using induction to try to prove something too specific: To prove a property of n and m by induction on n, it is sometimes important to leave m generic. In an informal proof, you should simply be careful about what is given and what isn't. If you're deliberately delaying introducing a variable, it's good to be explicit. For example, in an informal analogue of the above, we might say, "by induction on n, leaving m general". A brief pause, for a theorem that'll come in handy. The injectivity of constructors allows us to reason that ∀ (n m : nat), S n = S m → n = m. The converse of this implication is an instance of a more general fact about both constructors and functions, which we will find convenient in a few places below:

The following exercise requires the same pattern.

Exercise: 2 stars, standard (eqb_true)

Having proved eqb_true, we can use eqb_refl to show that eqb computes equality.

Exercise: 1 star, standard, optional (eqb_false_iff)

The following theorem is an alternate "negative" formulation of eqb_true_iff that is more convenient in certain situations (we'll see examples in later chapters). Hint: look at not_P__P_true.

When to Vary

To better understand general IHs, let's look back to plus_n_Sm.

Both eqb_true and plus_n_Sm are functions involving two variables and equality, so why does the former need a general hypothesis and not the latter? The general rule is that you need a general IH when:

• There is more than one variable.
• Variables other than the IH will have different values in different cases.

The problem with general rules is that they are, well, general. We can be more specific about when you'll need a general IH:

• When more than one variable changes during recursion in one of your definitions.

That's very specific! Let's look.

The only problem with the more specific explanation is that it's, well, clearly not right! Looking back at double_injective, our definition of double only has one argument, but we needed to vary our hypothesis! What gives?

Look closely at eqb_true_iff. We could have equivalently stated double_injecive as:
Theorem double_injective_eqb
     : ∀ n m : nat, eqb (double n) (double m) = true → eqb n m = true. A proof that n = m on nats n and m is low key also about eqb. But then why don't we need for plus_n_Sm, which is also about equality on numbers?
Theorem plus_n_Sm : ∀ n m : nat,
  eqb (S (n + m)) (n + (S m)) = true. While it's true that both sides of eqb change here, a change in n without a change in m is enough for eqb to make a recursive call. So: only one variable changes during recursion! Whew: that was a lot. There's another, more practical, way to figure out when you need to generalize your IH: you get to the inductive case and the IH and your goal are 'incompatible' because your IH is about a specific variable.

Exercise: 3 stars, standard (eqb_sym)

Exercise: 1 star, standard, optional (eqb_trans)

Generalizing the IH Explicitly

The strategy of doing fewer intros before an induction to obtain a more general IH doesn't always work by itself; sometimes some rearrangement of quantified variables is needed. Suppose, for example, that we wanted to prove double_injective by induction on m instead of n.

The problem is that, to do induction on m, we must first introduce n. (If we simply say induction m without introducing anything first, Coq will automatically introduce n for us!) What can we do about this? One possibility is to rewrite the statement of the lemma so that m is quantified before n. This works, but it's not nice: We don't want to have to twist the statements of lemmas to fit the needs of a particular strategy for proving them! Rather we want to state them in the clearest and most natural way. What we can do instead is to first introduce all the quantified variables and then re-generalize one or more of them, selectively taking variables out of the context and putting them back at the beginning of the goal. The generalize dependent tactic does this.

Let's look at an informal proof of this theorem. Note that the proposition we prove by induction leaves n quantified, corresponding to the use of generalize dependent in our formal proof. Theorem: For any nats n and m, if double n = double m, then n = m. Proof: Let m be a nat. We prove by induction on m that, for any n, if double n = double m then n = m.

• First, suppose m = 0, and suppose n is a number such that double n = double m. We must show that n = 0.
  Since m = 0, by the definition of double we have double n = 0. There are two cases to consider for n. If n = 0 we are done, since m = 0 = n, as required. Otherwise, if n = S n' for some n', we derive a contradiction: by the definition of double, we can calculate double n = S (S (double n')), but this contradicts the assumption that double n = 0.
• Second, suppose m = S m' and that n is again a number such that double n = double m. We must show that n = S m', with the induction hypothesis that for every number s, if double s = double m' then s = m'.
  By the fact that m = S m' and the definition of double, we have double n = S (S (double m')). There are two cases to consider for n.
  If n = 0, then by definition double n = 0, a contradiction.
  Thus, we may assume that n = S n' for some n', and again by the definition of double we have S (S (double n')) = S (S (double m')), which implies injectivity of constructors that double n' = double m'. Instantiating the induction hypothesis with n' thus allows us to conclude that n' = m', and it follows immediately that S n' = S m'. Since S n' = n and S m' = m, this is just what we wanted to show. ☐

Exercise: 3 stars, standard, especially useful (gen_dep_practice)

Prove this by induction on l.

To vary or not to vary

One of the following theorems doesn't need a varied hypothesis; the others do. Which? Why? (These are rhetorical questions---but do try to build up a mental model of when you need varied hypotheses.

Exercise: 2 stars, standard (complementary_complementary')

Let's prove that two versions of the complementary predicate are equivalent.

You defined this yourself, but let's prove things about our definition.

Exercise: 1 star, standard, optional (complement_correct)

It's always good to check that your functions do what you think they do! Does our complementary predicate agree with our definition of complement?

Exercise: 2 stars, standard (eq_strand_iff)

Prove an equality-iff theorem for DNA strand equality.

Programming with Propositions

The logical connectives that we have seen provide a rich vocabulary for defining complex propositions from simpler ones. To illustrate, let's look at how to express the claim that an element x occurs in a list l. Notice that this property has a simple recursive structure:

• If l is the empty list, then x cannot occur on it, so the property "x appears in l" is simply false.

• Otherwise, l has the form x' :: l'. In this case, x occurs in l if either it is equal to x' or it occurs in l'.

We can translate this directly into a straightforward recursive function taking an element and a list and returning a proposition:

When In is applied to a concrete list, it expands into a concrete sequence of nested disjunctions.

(Notice the use of the empty pattern to discharge the last case en passant.) We can also prove more generic, higher-level lemmas about In. Note, in the next, how In starts out applied to a variable and only gets expanded when we do case analysis on this variable:

This way of defining propositions recursively, though convenient in some cases, also has some drawbacks. In particular, it is subject to Coq's usual restrictions regarding the definition of recursive functions, e.g., the requirement that they be "obviously terminating." In the next chapter, we will see how to define propositions inductively, a different technique with its own set of strengths and limitations.

Exercise: 2 stars, standard (In_map_iff)

Exercise: 2 stars, standard, optional (In_app_iff)

Exercise: 2 stars, standard, optional (In_flat_map)

Exercise: 3 stars, standard, especially useful (All)

Recall that functions returning propositions can be seen as properties of their arguments. For instance, if P has type nat → Prop, then P n states that property P holds of n. Drawing inspiration from In, write a recursive function All stating that some property P holds of all elements of a list l. To make sure your definition is correct, prove the All_In lemma below. (Of course, your definition should not just restate the left-hand side of All_In.)

Exercise: 2 stars, standard, especially useful (All_forallb)

Recall the function forallb::

Prove the theorem below, which relates forallb to the All property of the above exercise.

Are there any important properties of the function forallb which are not captured by this specification? That is, if we take All as a given, would it be possible to define a version of forallb that (a) allowed us to prove the theorem above, but (b) was 'bad' in some other way? That is, the forallb function would be 'correct' according to All, but people would agree that it wasn't a 'good' function in some sense.

We've now seen many of Coq's most fundamental tactics. We'll introduce just one or two more in the coming days. But basically we've got what we need to get work done. Here are the ones we've seen:

• intros: move hypotheses/variables from goal to context
• reflexivity: finish the proof (when the goal looks like e = e)
• apply: prove goal using a hypothesis, lemma, or constructor
• apply... in H: apply a hypothesis, lemma, or constructor to a hypothesis in the context (forward reasoning)
• apply... with...: explicitly specify values for variables that cannot be determined by pattern matching
• simpl: simplify computations in the goal
• simpl in H: ... or a hypothesis
• rewrite: use an equality hypothesis (or lemma) to rewrite the goal
• rewrite ... in H: ... or a hypothesis
• symmetry: changes a goal of the form t=u into u=t
• symmetry in H: changes a hypothesis of the form t=u into u=t
• unfold: replace a defined constant by its right-hand side in the goal
• unfold ... in H: ... or a hypothesis
• fold: replace a defined constant's right hand side with the constant in the goal
• fold ... in ...: ... or a hypothesis
• step ...: A convenience for our one-two unfold/fold trick.
• step ... in ...: ... in an hypothesis.
• destruct... as...: case analysis on values of inductively defined types
• destruct... eqn:...: specify the name of an equation to be added to the context, recording the result of the case analysis
• induction... as...: induction on values of inductively defined types
• injection: reason by injectivity of constructors
• discriminate: reason by disjointness of constructors
• assert (H: e) (or assert (e) as H): introduce a "local lemma" e and call it H
• generalize dependent x: move the variable x (and anything else that depends on it) from the context back to an explicit hypothesis in the goal formula

That's a lot! We'll learn just a few more in the next day of class when we learn a final, critical concept; then we'll do some small case studies; then we'll finally transition to informal proof.