IndPrinciplesInduction Principles
Basics
Check nat_ind.
(* ===> nat_ind :
forall P : nat -> Prop,
P 0 ->
(forall n : nat, P n -> P (S n)) ->
forall n : nat, P n *)
(* ===> nat_ind :
forall P : nat -> Prop,
P 0 ->
(forall n : nat, P n -> P (S n)) ->
forall n : nat, P n *)
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:
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
Basics chapter.
- P holds of 0
- for any n, if P holds of n, then P holds of S n.
Theorem mult_0_r' : ∀n:nat,
n * 0 = 0.
Proof.
apply nat_ind.
- (* n = O *) reflexivity.
- (* n = S n' *) simpl. intros n' IHn'. rewrite → IHn'.
reflexivity. Qed.
n * 0 = 0.
Proof.
apply nat_ind.
- (* n = O *) reflexivity.
- (* n = S n' *) simpl. intros n' IHn'. rewrite → IHn'.
reflexivity. Qed.
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.
Theorem plus_one_r' : ∀n:nat,
n + 1 = S n.
Proof.
(* FILL IN HERE *) Admitted.
☐
n + 1 = S n.
Proof.
(* FILL IN HERE *) Admitted.
t_ind : ∀P : t → Prop,
... case for c_{1} ... →
... case for c_{2} ... → ...
... case for cn ... →
∀n : t, P n
The specific shape of each case depends on the arguments to the
corresponding constructor.
... case for c_{1} ... →
... case for c_{2} ... → ...
... case for cn ... →
∀n : t, P n
Inductive time : Type :=
| day
| night.
Check time_ind.
(* ===> time_ind : forall P : time -> Prop,
P day ->
P night ->
forall t : time, P t *)
| day
| night.
Check time_ind.
(* ===> time_ind : forall P : time -> Prop,
P day ->
P night ->
forall t : time, P t *)
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.
Inductive rgb : Type :=
| red
| green
| blue.
Check rgb_ind.
☐
| red
| green
| blue.
Check rgb_ind.
Inductive natlist : Type :=
| nnil
| ncons (n : nat) (l : natlist).
Check natlist_ind.
(* ===>
natlist_ind :
forall P : natlist -> Prop,
P nnil ->
(forall (n : nat) (l : natlist),
P l -> P (ncons n l)) ->
forall n : natlist, P n *)
| nnil
| ncons (n : nat) (l : natlist).
Check natlist_ind.
(* ===>
natlist_ind :
forall P : natlist -> Prop,
P nnil ->
(forall (n : nat) (l : natlist),
P l -> P (ncons n l)) ->
forall n : natlist, P n *)
Exercise: 1 star, standard, optional (natlist1)
Suppose we had written the above definition a little differently:
Inductive natlist1 : Type :=
| nnil1
| nsnoc1 (l : natlist1) (n : nat).
| nnil1
| nsnoc1 (l : natlist1) (n : nat).
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_{1}:a_{1} ... xn:an, that case is:
"For all x_{1}:a_{1} ... xn:an,
if [P] holds of each of the arguments of type [t],
then [P] holds of [c x_{1} ... 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.)
Inductive booltree : Type :=
| bt_empty
| bt_leaf (b : bool)
| bt_branch (b : bool) (t_{1} t_{2} : booltree).
☐
| bt_empty
| bt_leaf (b : bool)
| bt_branch (b : bool) (t_{1} t_{2} : booltree).
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:
∀P : ExSet → Prop,
(∀b : bool, P (con1 b)) →
(∀(n : nat) (e : ExSet), P e → P (con2 n e)) →
∀e : ExSet, P e
Inductive ExSet : Type :=
(* FILL IN HERE *)
.
☐
(* FILL IN HERE *)
.
Polymorphism
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:
| nil : list X
| cons : X → list X → list 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.
∀(X : Type) (P : list X → Prop),
P [] →
(∀(x : X) (l : list X), P l → P (x :: l)) →
∀l : list X, P l
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.
Inductive tree (X:Type) : Type :=
| leaf (x : X)
| node (t_{1} t_{2} : tree X).
Check tree_ind.
☐
| leaf (x : X)
| node (t_{1} t_{2} : tree X).
Check tree_ind.
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
☐
∀(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_{1} : nat → foo X Y,
(∀n : nat, P (f_{1} n)) → P (quux X Y f_{1})) →
∀f_{2} : foo X Y, P f_{2}
☐
∀(X Y : Type) (P : foo X Y → Prop),
(∀x : X, P (bar X Y x)) →
(∀y : Y, P (baz X Y y)) →
(∀f_{1} : nat → foo X Y,
(∀n : nat, P (f_{1} n)) → P (quux X Y f_{1})) →
∀f_{2} : foo X Y, P f_{2}
Exercise: 1 star, standard, optional (foo')
Consider the following inductive definition:
Inductive foo' (X:Type) : Type :=
| C_{1} (l : list X) (f : foo' X)
| C_{2}.
| C_{1} (l : list X) (f : foo' X)
| C_{2}.
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, ________________________
∀(X : Type) (P : foo' X → Prop),
(∀(l : list X) (f : foo' X),
_______________________ →
_______________________ ) →
___________________________________________ →
∀f : foo' X, ________________________
Induction Hypotheses
∀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.
P 0 →
(∀n : nat, P n → P (S n)) →
∀n : nat, P n
Definition P_m0r (n:nat) : Prop :=
n * 0 = 0.
n * 0 = 0.
... or equivalently:
Definition P_m0r' : nat→Prop :=
fun n ⇒ n * 0 = 0.
fun n ⇒ n * 0 = 0.
Now it is easier to see where P_m0r appears in the proof.
Theorem mult_0_r'' : ∀n:nat,
P_m0r n.
Proof.
apply nat_ind.
- (* n = O *) reflexivity.
- (* n = S n' *)
(* Note the proof state at this point! *)
intros n IHn.
unfold P_m0r in IHn. unfold P_m0r. simpl. apply IHn. Qed.
P_m0r n.
Proof.
apply nat_ind.
- (* n = O *) reflexivity.
- (* n = S n' *)
(* Note the proof state at this point! *)
intros n IHn.
unfold P_m0r in IHn. unfold P_m0r. simpl. apply IHn. Qed.
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
- 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.
Theorem plus_assoc' : ∀n m p : nat,
n + (m + p) = (n + m) + p.
Proof.
(* ...we first introduce all 3 variables into the context,
which amounts to saying "Consider an arbitrary n, m, and
p..." *)
intros n m p.
(* ...We now use the induction tactic to prove P n (that
is, n + (m + p) = (n + m) + p) for _all_ n,
and hence also for the particular n that is in the context
at the moment. *)
induction n as [| n'].
- (* n = O *) reflexivity.
- (* n = S n' *)
simpl. rewrite → IHn'. reflexivity. Qed.
n + (m + p) = (n + m) + p.
Proof.
(* ...we first introduce all 3 variables into the context,
which amounts to saying "Consider an arbitrary n, m, and
p..." *)
intros n m p.
(* ...We now use the induction tactic to prove P n (that
is, n + (m + p) = (n + m) + p) for _all_ n,
and hence also for the particular n that is in the context
at the moment. *)
induction n as [| n'].
- (* n = O *) reflexivity.
- (* n = S n' *)
simpl. rewrite → IHn'. reflexivity. Qed.
It also works to apply induction to a variable that is
quantified in the goal.
Theorem plus_comm' : ∀n m : nat,
n + m = m + n.
Proof.
induction n as [| n'].
- (* n = O *) intros m. rewrite <- plus_n_O. reflexivity.
- (* n = S n' *) intros m. simpl. rewrite → IHn'.
rewrite <- plus_n_Sm. reflexivity. Qed.
n + m = m + n.
Proof.
induction n as [| n'].
- (* n = O *) intros m. rewrite <- plus_n_O. reflexivity.
- (* n = S n' *) intros m. simpl. rewrite → IHn'.
rewrite <- plus_n_Sm. reflexivity. Qed.
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.
Theorem plus_comm'' : ∀n m : nat,
n + m = m + n.
Proof.
(* Let's do induction on m this time, instead of n... *)
induction m as [| m']. (* n is already introduced into the context *)
- (* m = O *) simpl. rewrite <- plus_n_O. reflexivity.
- (* m = S m' *) simpl. rewrite <- IHm'.
rewrite <- plus_n_Sm. reflexivity. Qed.
n + m = m + n.
Proof.
(* Let's do induction on m this time, instead of n... *)
induction m as [| m']. (* n is already introduced into the context *)
- (* m = O *) simpl. rewrite <- plus_n_O. reflexivity.
- (* m = S m' *) simpl. rewrite <- IHm'.
rewrite <- plus_n_Sm. reflexivity. Qed.
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.
(* FILL IN HERE *)
☐
Induction Principles in Prop
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_0 : even 0
| ev_SS : ∀n : nat, even n → even (S (S n)).
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:
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
- 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.
- We must prove that P holds for O and ev_0.
- 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.
∀P : nat → Prop,
... →
∀n : nat,
even n → P n
For this reason, Coq actually generates the following simplified
induction principle for even:
... →
∀n : nat,
even n → P n
Print even.
(* ===>
Inductive even : nat -> Prop :=
| ev_0 : even 0
| ev_SS : forall n : nat, even n -> even (S (S n))
*)
Check even_ind.
(* ===> even_ind
: forall P : nat -> Prop,
P 0 ->
(forall n : nat, even n -> P n -> P (S (S n))) ->
forall n : nat,
even n -> P n *)
(* ===>
Inductive even : nat -> Prop :=
| ev_0 : even 0
| ev_SS : forall n : nat, even n -> even (S (S n))
*)
Check even_ind.
(* ===> even_ind
: forall P : nat -> Prop,
P 0 ->
(forall n : nat, even n -> P n -> P (S (S n))) ->
forall n : nat,
even n -> P n *)
In particular, Coq has dropped the evidence term E as a
parameter of the the proposition P.
In English, even_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:
As expected, we can apply even_ind directly instead of using
induction. For example, we can use it to show that even' (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 even:
- P holds for 0,
- for any n, if n is even and P holds for n, then P holds for S (S n).
Inductive even' : nat → Prop :=
| even'_0 : even' 0
| even'_2 : even' 2
| even'_sum n m (Hn : even' n) (Hm : even' m) : even' (n + m).
Theorem ev_ev' : ∀n, even n → even' n.
Proof.
apply even_ind.
- (* ev_0 *)
apply even'_0.
- (* ev_SS *)
intros m Hm IH.
apply (even'_sum 2 m).
+ apply even'_2.
+ apply IH.
Qed.
| even'_0 : even' 0
| even'_2 : even' 2
| even'_sum n m (Hn : even' n) (Hm : even' m) : even' (n + m).
Theorem ev_ev' : ∀n, even n → even' n.
Proof.
apply even_ind.
- (* ev_0 *)
apply even'_0.
- (* ev_SS *)
intros m Hm IH.
apply (even'_sum 2 m).
+ apply even'_2.
+ apply IH.
Qed.
The precise form of an Inductive definition can affect the
induction principle Coq generates.
Inductive le_{1} : nat → nat → Prop :=
| le1_n : ∀n, le_{1} n n
| le1_S : ∀n m, (le_{1} n m) → (le_{1} n (S m)).
Notation "m ≤1 n" := (le_{1} m n) (at level 70).
| le1_n : ∀n, le_{1} n n
| le1_S : ∀n m, (le_{1} n m) → (le_{1} n (S m)).
Notation "m ≤1 n" := (le_{1} m n) (at level 70).
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.
Inductive le_{2} (n:nat) : nat → Prop :=
| le2_n : le_{2} n n
| le2_S m (H : le_{2} n m) : le_{2} n (S m).
Notation "m ≤2 n" := (le_{2} m n) (at level 70).
| le2_n : le_{2} n n
| le2_S m (H : le_{2} n m) : le_{2} n (S m).
Notation "m ≤2 n" := (le_{2} m n) (at level 70).
The second one is better, even though it looks less symmetric.
Why? Because it gives us a simpler induction principle.
Check le1_ind.
(* ===> forall P : nat -> nat -> Prop,
(forall n : nat, P n n) ->
(forall n m : nat, n <=1 m -> P n m -> P n (S m)) ->
forall n n_{0} : nat, n <=1 n_{0} -> P n n_{0} *)
Check le2_ind.
(* ===> forall (n : nat) (P : nat -> Prop),
P n ->
(forall m : nat, n <=2 m -> P m -> P (S m)) ->
forall n_{0} : nat, n <=2 n_{0} -> P n_{0} *)
(* ===> forall P : nat -> nat -> Prop,
(forall n : nat, P n n) ->
(forall n m : nat, n <=1 m -> P n m -> P n (S m)) ->
forall n n_{0} : nat, n <=1 n_{0} -> P n n_{0} *)
Check le2_ind.
(* ===> forall (n : nat) (P : nat -> Prop),
P n ->
(forall m : nat, n <=2 m -> P m -> P (S m)) ->
forall n_{0} : nat, n <=2 n_{0} -> P n_{0} *)
Formal vs. Informal Proofs by Induction
Induction Over an Inductively Defined Set
- Theorem: <Universally quantified proposition of the form
"For all n:S, P(n)," where S is some inductively defined
set.>
- Suppose n = c a_{1} ... 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_{1} ... ak)>.
- <other cases similarly...> ☐
- Suppose n = c a_{1} ... 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_{1} ... ak)>.
- Theorem: For all sets X, lists l : list X, and numbers
n, if length l = n then index (S n) l = None.
- Suppose l = []. We must show, for all numbers n,
that, if length [] = n, then index (S n) [] =
None.
- 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.
length l = length (x::l') = S (length l'),it suffices to show thatindex (S (length l')) l' = None.But this follows directly from the induction hypothesis, picking n' to be length l'. ☐
- Suppose l = []. We must show, for all numbers n,
that, if length [] = n, then index (S n) [] =
None.
Induction Over an Inductively Defined Proposition
- 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")>
- 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>.
- <other cases similarly...> ☐
- 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>.
- Theorem: The ≤ relation is transitive — i.e., for all
numbers n, m, and o, if n ≤ m and m ≤ o, then
n ≤ 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'.
- 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.
(* Mon Mar 25 14:36:24 EDT 2019 *)