InductionProof by Induction
(* $Date: 2012-12-26 16:12:50 -0500 (Wed, 26 Dec 2012) $ *)
The next line imports all of our definitions from the
previous chapter.
Require Export Basics.
For it to work, you need to use coqc to compile Basics.v
into Basics.vo. (This is like making a .class file from a .java
file, or a .o file from a .c file.)
Here are two ways to compile your code:
In this file, we again use the Module feature to wrap all of the
definitions for pairs and lists of numbers in a module so that,
later, we can reuse the same names for improved (generic) versions
of the same operations.
- CoqIDE:
- Command line:
Naming Cases
Require String. Open Scope string_scope.
Ltac move_to_top x :=
match reverse goal with
| H : _ ⊢ _ => try move x after H
end.
Tactic Notation "assert_eq" ident(x) constr(v) :=
let H := fresh in
assert (x = v) as H by reflexivity;
clear H.
Tactic Notation "Case_aux" ident(x) constr(name) :=
first [
set (x := name); move_to_top x
| assert_eq x name; move_to_top x
| fail 1 "because we are working on a different case" ].
Tactic Notation "Case" constr(name) := Case_aux Case name.
Tactic Notation "SCase" constr(name) := Case_aux SCase name.
Tactic Notation "SSCase" constr(name) := Case_aux SSCase name.
Tactic Notation "SSSCase" constr(name) := Case_aux SSSCase name.
Tactic Notation "SSSSCase" constr(name) := Case_aux SSSSCase name.
Tactic Notation "SSSSSCase" constr(name) := Case_aux SSSSSCase name.
Tactic Notation "SSSSSSCase" constr(name) := Case_aux SSSSSSCase name.
Tactic Notation "SSSSSSSCase" constr(name) := Case_aux SSSSSSSCase name.
Here's an example of how Case is used. Step through the
following proof and observe how the context changes.
Theorem andb_true_elim1 : ∀b c : bool,
andb b c = true → b = true.
Proof.
intros b c H.
destruct b.
Case "b = true".
reflexivity.
Case "b = false".
rewrite ← H. reflexivity. Qed.
Case does something very trivial: It simply adds a string
that we choose (tagged with the identifier "Case") to the context
for the current goal. When subgoals are generated, this string is
carried over into their contexts. When the last of these subgoals
is finally proved and the next top-level goal (a sibling of the
current one) becomes active, this string will no longer appear in
the context and we will be able to see that the case where we
introduced it is complete. Also, as a sanity check, if we try to
execute a new Case tactic while the string left by the previous
one is still in the context, we get a nice clear error message.
For nested case analyses (i.e., when we want to use a destruct
to solve a goal that has itself been generated by a destruct),
there is an SCase ("subcase") tactic.
Exercise: 2 stars (andb_true_elim2)
Prove andb_true_elim2, marking cases (and subcases) when you use destruct.Theorem andb_true_elim2 : ∀b c : bool,
andb b c = true → c = true.
Proof.
(* FILL IN HERE *) Admitted.
☐
There are no hard and fast rules for how proofs should be
formatted in Coq — in particular, where lines should be broken
and how sections of the proof should be indented to indicate their
nested structure. However, if the places where multiple subgoals
are generated are marked with explicit Case tactics placed at
the beginning of lines, then the proof will be readable almost no
matter what choices are made about other aspects of layout.
This is a good place to mention one other piece of (possibly
obvious) advice about line lengths. Beginning Coq users sometimes
tend to the extremes, either writing each tactic on its own line
or entire proofs on one line. Good style lies somewhere in the
middle. In particular, one reasonable convention is to limit
yourself to 80-character lines. Lines longer than this are hard
to read and can be inconvenient to display and print. Many
editors have features that help enforce this.
Theorem plus_0_r_firsttry : ∀n:nat,
n + 0 = n.
... cannot be proved in the same simple way. Just applying
reflexivity doesn't work: the n in n + 0 is an arbitrary
unknown number, so the match in the definition of + can't be
simplified. And reasoning by cases using destruct n doesn't get
us much further: the branch of the case analysis where we assume n
= 0 goes through, but in the branch where n = S n' for some n'
we get stuck in exactly the same way. We could use destruct n' to
get one step further, but since n can be arbitrarily large, if we
try to keep on going this way we'll never be done.
Proof.
intros n.
simpl. (* Does nothing! *)
Admitted.
Case analysis gets us a little further, but not all the way:
Theorem plus_0_r_secondtry : ∀n:nat,
n + 0 = n.
Proof.
intros n. destruct n as [| n'].
Case "n = 0".
reflexivity. (* so far so good... *)
Case "n = S n'".
simpl. (* ...but here we are stuck again *)
Admitted.
To prove such facts — indeed, to prove most interesting
facts about numbers, lists, and other inductively defined sets —
we need a more powerful reasoning principle: induction.
Recall (from high school) the principle of induction over 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:
In Coq, the steps are the same but the order is backwards: we
begin with the goal of proving P(n) for all n and break it
down (by applying the induction tactic) into two separate
subgoals: first showing P(O) and then showing P(n') → P(S
n'). Here's how this works for the theorem we are trying to
prove at the moment:
- show that P(O) holds;
- show that, for any n', if P(n') holds, then so does P(S n');
- conclude that P(n) holds for all n.
Theorem plus_0_r : ∀n:nat, n + 0 = n.
Proof.
intros n. induction n as [| n'].
Case "n = 0". reflexivity.
Case "n = S n'". simpl. rewrite → IHn'. reflexivity. Qed.
Like destruct, the induction tactic takes an as...
clause that specifies the names of the variables to be introduced
in the subgoals. In the first branch, n is replaced by 0 and
the goal becomes 0 + 0 = 0, which follows by simplification. In
the second, n is replaced by S n' and the assumption n' + 0 =
n' is added to the context (with the name IHn', i.e., the
Induction Hypothesis for n'). The goal in this case becomes (S
n') + 0 = S n', which simplifies to S (n' + 0) = S n', which in
turn follows from the induction hypothesis.
Theorem minus_diag : ∀n,
minus n n = 0.
Proof.
(* WORKED IN CLASS *)
intros n. induction n as [| n'].
Case "n = 0".
simpl. reflexivity.
Case "n = S n'".
simpl. rewrite → IHn'. reflexivity. Qed.
Theorem mult_0_r : ∀n:nat,
n * 0 = 0.
Proof.
(* FILL IN HERE *) Admitted.
Theorem plus_n_Sm : ∀n m : nat,
S (n + m) = n + (S m).
Proof.
(* FILL IN HERE *) Admitted.
Theorem plus_comm : ∀n m : nat,
n + m = m + n.
Proof.
(* FILL IN HERE *) Admitted.
n * 0 = 0.
Proof.
(* FILL IN HERE *) Admitted.
Theorem plus_n_Sm : ∀n m : nat,
S (n + m) = n + (S m).
Proof.
(* FILL IN HERE *) Admitted.
Theorem plus_comm : ∀n m : nat,
n + m = m + n.
Proof.
(* FILL IN HERE *) Admitted.
☐
Fixpoint double (n:nat) :=
match n with
| O => O
| S n' => S (S (double n'))
end.
Lemma double_plus : ∀n, double n = n + n .
Proof.
(* FILL IN HERE *) Admitted.
Proof.
(* FILL IN HERE *) Admitted.
☐
(* FILL IN HERE *)
☐
Exercise: 1 star (destruct_induction)
Briefly explain the difference between the tactics destruct and induction.Formal vs. Informal Proof
Theorem plus_assoc' : ∀n m p : nat,
n + (m + p) = (n + m) + p.
Proof. intros n m p. induction n as [| n']. reflexivity.
simpl. rewrite → IHn'. reflexivity. Qed.
Coq is perfectly happy with this as a proof. For a human,
however, it is difficult to make much sense of it. If you're used
to Coq you can probably step through the tactics one after the
other in your mind and imagine the state of the context and goal
stack at each point, but if the proof were even a little bit more
complicated this would be next to impossible. Instead, a
mathematician mighty write it like this:
The overall form of the proof is basically similar. This is
no accident, of course: Coq has been designed so that its
induction tactic generates the same sub-goals, in the same
order, as the bullet points that a mathematician would write. But
there are significant differences of detail: the formal proof is
much more explicit in some ways (e.g., the use of reflexivity)
but much less explicit in others; in particular, the "proof state"
at any given point in the Coq proof is completely implicit,
whereas the informal proof reminds the reader several times where
things stand.
Here is a formal proof that shows the structure more
clearly:
- Theorem: For any n, m and p,
n + (m + p) = (n + m) + p.Proof: By induction on n.
- First, suppose n = 0. We must show
0 + (m + p) = (0 + m) + p.This follows directly from the definition of +.
- Next, suppose n = S n', where
n' + (m + p) = (n' + m) + p.We must show(S n') + (m + p) = ((S n') + m) + p.By the definition of +, this follows fromS (n' + (m + p)) = S ((n' + m) + p),which is immediate from the induction hypothesis. ☐
- First, suppose n = 0. We must show
Theorem plus_assoc : ∀n m p : nat,
n + (m + p) = (n + m) + p.
Proof.
intros n m p. induction n as [| n'].
Case "n = 0".
reflexivity.
Case "n = S n'".
simpl. rewrite → IHn'. reflexivity. Qed.
Exercise: 2 stars (plus_comm_informal)
Translate your solution for plus_comm into an informal proof.☐
Exercise: 2 stars, optional (beq_nat_refl_informal)
Write an informal proof of the following theorem, using the informal proof of plus_assoc as a model. Don't just paraphrase the Coq tactics into English!☐
Exercise: 1 star, optional (beq_nat_refl)
Theorem beq_nat_refl : ∀n : nat,
true = beq_nat n n.
Proof.
(* FILL IN HERE *) Admitted.
true = beq_nat n n.
Proof.
(* FILL IN HERE *) Admitted.
☐
Proofs Within Proofs
Theorem mult_0_plus' : ∀n m : nat,
(0 + n) * m = n * m.
Proof.
intros n m.
assert (H: 0 + n = n).
Case "Proof of assertion". reflexivity.
rewrite → H.
reflexivity. Qed.
The assert tactic introduces two sub-goals. The first is
the assertion itself; by prefixing it with H: we name the
assertion H. (Note that we could also name the assertion with
as just as we did above with destruct and induction, i.e.,
assert (0 + n = n) as H. Also note that we mark the proof of
this assertion with a Case, both for readability and so that,
when using Coq interactively, we can see when we're finished
proving the assertion by observing when the "Proof of assertion"
string disappears from the context.) The second goal is the same
as the one at the point where we invoke assert, except that, in
the context, we have the assumption H that 0 + n = n. That
is, assert generates one subgoal where we must prove the
asserted fact and a second subgoal where we can use the asserted
fact to make progress on whatever we were trying to prove in the
first place.
Actually, assert will turn out to be handy in many sorts of
situations. For example, suppose we want to prove that (n + m)
+ (p + q) = (m + n) + (p + q). The only difference between the
two sides of the = is that the arguments m and n to the
first inner + are swapped, so it seems we should be able to
use the commutativity of addition (plus_comm) to rewrite one
into the other. However, the rewrite tactic is a little stupid
about where it applies the rewrite. There are three uses of
+ here, and it turns out that doing rewrite → plus_comm
will affect only the outer one.
Theorem plus_rearrange_firsttry : ∀n m p q : nat,
(n + m) + (p + q) = (m + n) + (p + q).
Proof.
intros n m p q.
(* We just need to swap (n + m) for (m + n)...
it seems like plus_comm should do the trick! *)
rewrite → plus_comm.
(* Doesn't work...Coq rewrote the wrong plus! *)
Admitted.
To get plus_comm to apply at the point where we want it, we can
introduce a local lemma stating that n + m = m + n (for
the particular m and n that we are talking about here), prove
this lemma using plus_comm, and then use this lemma to do the
desired rewrite.
Theorem plus_rearrange : ∀n m p q : nat,
(n + m) + (p + q) = (m + n) + (p + q).
Proof.
intros n m p q.
assert (H: n + m = m + n).
Case "Proof of assertion".
rewrite → plus_comm. reflexivity.
rewrite → H. reflexivity. Qed.
Exercise: 4 stars, recommended (mult_comm)
Use assert to help prove this theorem. You shouldn't need to use induction.Theorem plus_swap : ∀n m p : nat,
n + (m + p) = m + (n + p).
Proof.
(* FILL IN HERE *) Admitted.
Now prove commutativity of multiplication. (You will probably
need to define and prove a separate subsidiary theorem to be used
in the proof of this one.) You may find that plus_swap comes in
handy.
Theorem mult_comm : ∀m n : nat,
m * n = n * m.
Proof.
(* FILL IN HERE *) Admitted.
Theorem evenb_n__oddb_Sn : ∀n : nat,
evenb n = negb (evenb (S n)).
Proof.
(* FILL IN HERE *) Admitted.
evenb n = negb (evenb (S n)).
Proof.
(* FILL IN HERE *) Admitted.
☐
More Exercises
Exercise: 3 stars, optional (more_exercises)
Take a piece of paper. For each of the following theorems, first think about whether (a) it can be proved using only simplification and rewriting, (b) it also requires case analysis (destruct), or (c) it also requires induction. Write down your prediction. Then fill in the proof. (There is no need to turn in your piece of paper; this is just to encourage you to reflect before hacking!)Theorem ble_nat_refl : ∀n:nat,
true = ble_nat n n.
Proof.
(* FILL IN HERE *) Admitted.
Theorem zero_nbeq_S : ∀n:nat,
beq_nat 0 (S n) = false.
Proof.
(* FILL IN HERE *) Admitted.
Theorem andb_false_r : ∀b : bool,
andb b false = false.
Proof.
(* FILL IN HERE *) Admitted.
Theorem plus_ble_compat_l : ∀n m p : nat,
ble_nat n m = true → ble_nat (p + n) (p + m) = true.
Proof.
(* FILL IN HERE *) Admitted.
Theorem S_nbeq_0 : ∀n:nat,
beq_nat (S n) 0 = false.
Proof.
(* FILL IN HERE *) Admitted.
Theorem mult_1_l : ∀n:nat, 1 * n = n.
Proof.
(* FILL IN HERE *) Admitted.
Theorem all3_spec : ∀b c : bool,
orb
(andb b c)
(orb (negb b)
(negb c))
= true.
Proof.
(* FILL IN HERE *) Admitted.
Theorem mult_plus_distr_r : ∀n m p : nat,
(n + m) * p = (n * p) + (m * p).
Proof.
(* FILL IN HERE *) Admitted.
Theorem mult_assoc : ∀n m p : nat,
n * (m * p) = (n * m) * p.
Proof.
(* FILL IN HERE *) Admitted.
☐
Use the replace tactic to do a proof of plus_swap', just like
plus_swap but without needing assert (n + m = m + n).
Exercise: 2 stars, optional (plus_swap')
The replace tactic allows you to specify a particular subterm to rewrite and what you want it rewritten to. More precisely, replace (t) with (u) replaces (all copies of) expression t in the goal by expression u, and generates t = u as an additional subgoal. This is often useful when a plain rewrite acts on the wrong part of the goal.Theorem plus_swap' : ∀n m p : nat,
n + (m + p) = m + (n + p).
Proof.
(* FILL IN HERE *) Admitted.
☐
(a) First, write an inductive definition of the type bin
corresponding to this description of binary numbers.
(Hint: recall that the definition of nat from class,
(b) Next, write an increment function for binary numbers, and a
function to convert binary numbers to unary numbers.
(c) Finally, prove that your increment and binary-to-unary
functions commute: that is, incrementing a binary number and
then converting it to unary yields the same result as first
converting it to unary and then incrementing.
Exercise: 4 stars, recommended (binary)
Consider a different, more efficient representation of natural numbers using a binary rather than unary system. That is, instead of saying that each natural number is either zero or the successor of a natural number, we can say that each binary number is either- zero,
- twice a binary number, or
- one more than twice a binary number.
Inductive nat : Type :=
| O : nat
| S : nat → nat.
says nothing about what O and S "mean". It just says "O is
a nat (whatever that is), and if n is a nat then so is S n".
The interpretation of O as zero and S as successor/plus one
comes from the way that we use nat values, by writing functions to
do things with them, proving things about them, and so on. Your
definition of bin should be correspondingly simple; it is the
functions you will write next that will give it mathematical
meaning.)
| O : nat
| S : nat → nat.
(* FILL IN HERE *)
☐
(a) First, write a function to convert natural numbers to binary
numbers. Then prove that starting with any natural number,
converting to binary, then converting back yields the same
natural number you started with.
(b) You might naturally think that we should also prove the
opposite direction: that starting with a binary number,
converting to a natural, and then back to binary yields the
same number we started with. However, it is not true!
Explain what the problem is.
(c) Define a function normalize from binary numbers to binary
numbers such that for any binary number b, converting to a
natural and then back to binary yields (normalize b). Prove
it.
Exercise: 5 stars (binary_inverse)
This exercise is a continuation of the previous exercise about binary numbers. You will need your definitions and theorems from the previous exercise to complete this one.(* FILL IN HERE *)
Exercise: 2 stars, optional (decreasing)
The requirement that some argument to each function be "decreasing" is a fundamental feature of Coq's design: In particular, it guarantees that every function that can be defined in Coq will terminate on all inputs. However, because Coq's "decreasing analysis" is not very sophisticated, it is sometimes necessary to write functions in slightly unnatural ways.(* FILL IN HERE *)
☐