InductionProof by Induction
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:
- CoqIDE:
- Command line:
Naming Cases
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". (* <----- here *)
reflexivity.
Case "b = false". (* <---- and here *)
rewrite ← H.
reflexivity.
Qed.
Case does something very straightforward: 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
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 (e.g., 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.
Proof by Induction
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.
Proof.
intros n.
simpl. (* Does nothing! *)
Abort.
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 like this we'll never be done.
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 *)
Abort.
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.
Exercise: 2 stars (basic_induction)
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.
Theorem plus_assoc : ∀n m p : nat,
n + (m + p) = (n + m) + p.
Proof.
(* FILL IN HERE *) Admitted.
Fixpoint double (n:nat) :=
match n with
| O => O
| S n' => S (S (double n'))
end.
Use induction to prove this simple fact about double:
Lemma double_plus : ∀n, double n = n + n .
Proof.
(* FILL IN HERE *) Admitted.
☐
(* FILL IN HERE *)
☐
Exercise: 1 star (destruct_induction)
Briefly explain the difference between the tactics destruct and induction.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! *)
Abort.
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 (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.
☐
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.
☐
Exercise: 2 stars, optional (beq_nat_refl)
Prove the following theorem. Putting true on the left-hand side of the equality may seem odd, but this is how the theorem is stated in the standard library, so we follow suit. Since rewriting works equally well in either direction, we will have no problem using the theorem no matter which way we state it.Theorem beq_nat_refl : ∀n : nat,
true = beq_nat n n.
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.
☐
(Before you start working on this exercise, please copy the
definitions from your solution to the binary exercise here so
that this file can be graded on its own. If you find yourself
wanting to change your original definitions to make the property
easier to prove, feel free to do so.)
Exercise: 3 stars (binary_commute)
Recall the increment and binary-to-unary functions that you wrote for the binary exercise in the Basics chapter. Prove that these 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.(* 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.
Again, feel free to change your earlier definitions if this helps
here.
Exercise: 5 stars, advanced (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 *)
☐
Advanced Material
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 might write it something like this:
The overall form of the proof is basically similar. This is
no accident: 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, advanced (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!☐
(* $Date: 2013-07-17 16:19:11 -0400 (Wed, 17 Jul 2013) $ *)