9

I have the following Lemma with an incomplete proof:

Lemma s_is_plus_one : forall n:nat, S n = n + 1.
Proof.
  intros.
  reflexivity.
Qed.

This proof fails with

Unable to unify "n + 1" with "S n".

It seems like eq_S would be the way to prove this, but I can't apply it (it doesn't recognize n + 1 as S n: Error: Unable to find an instance for the variable y.). I've also tried ring, but it can't find a relation. When I use rewrite, it just reduces to the same final goal.

How can I finish this proof?

Charlie Parker
  • 5,884
  • 57
  • 198
  • 323
Langston
  • 1,083
  • 10
  • 26

1 Answers1

14

This is related to the way (+) is defined. You can access (+)'s underlying definition by turning notations off (in CoqIDE that's in View > Display notations), seeing that the notation (+) corresponds to the function Nat.add and then calling Print Nat.add which gives you:

Nat.add = 
fix add (n m : nat) {struct n} : nat :=
  match n with
  | O => m
  | S p => S (add p m)
  end

You can see that (+) is defined by matching on its first argument which in n + 1 is the variable n. Because n does not start with either O or S (it's not "constructor-headed"), the match cannot reduce. Which means you won't be able to prove the equality just by saying that the two things compute to the same normal form (which is what reflexivity claims).

Instead you need to explain to coq why it is the case that for any n the equality will hold true. A classic move in the case of a recursive function like Nat.add is to proceed with a proof by induction. And it does indeed do the job here:

Lemma s_is_plus_one : forall n:nat, S n = n + 1.
Proof.
intros. induction n.
 - reflexivity.
 - simpl. rewrite <- IHn. reflexivity.
Qed.

Another thing you can do is notice that 1 on the other hand is constructor-headed which means that the match would fire if only you had 1 + n rather than n + 1. Well, we're in luck because in the standard library someone already has proven that Nat.add is commutative so we can just use that:

Lemma s_is_plus_one : forall n:nat, S n = n + 1.
Proof.
intros.
rewrite (Nat.add_comm n 1).
reflexivity.
Qed.

A last alternative: using SearchAbout (?n + 1), we can find all the theorems talking about the pattern ?n + 1 for some variable ?n (the question mark is important here). The first result is the really relevant lemma:

Nat.add_1_r: forall n : nat, n + 1 = S n
gallais
  • 11,823
  • 2
  • 30
  • 63
  • Amazing, I really need to get to know SearchAbout better! Thank you again! – Langston Oct 29 '16 at 00:46
  • your first proof does not work. It gets stuck and gives this error: `In environment n : nat IHn : n.+1 = n + 1 Unable to unify "n + 1 + 1" with "(n + 1).+1".` – Charlie Parker Mar 08 '22 at 23:25
  • also, I get that `Nat.add_comm` doesn't exist: `Nat.add_comm not a defined object.`. How do you fix this? – Charlie Parker Mar 08 '22 at 23:32
  • @CharlieParker I guess Coq's stdlib has changed since I wrote this post. I have however explained my process disabling notations, using Search, etc. so you should hopefully be able to find the new lemma by following a similar approach. – gallais Mar 09 '22 at 16:09
  • Regarding the `s_is_plus_one` lemma (the first version): I'm curious as to why the `simpl.` step even works. Isn't the transformation of `S n + 1` to `S (n + 1)` kind of the whole point of the proof? How can we use that property inside the proof? – jimkokko5 Jun 13 '23 at 11:38