How can I rewrite "+ 1" (plus one) to "S" (succ) in Coq?
Asked Answered
C

1

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?

Caylacaylor answered 28/10, 2016 at 21:55 Comment(0)
L
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
Leeward answered 28/10, 2016 at 23:2 Comment(5)
Amazing, I really need to get to know SearchAbout better! Thank you again!Caylacaylor
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".Marcelina
also, I get that Nat.add_comm doesn't exist: Nat.add_comm not a defined object.. How do you fix this?Marcelina
@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.Leeward
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?Furnivall

© 2022 - 2024 — McMap. All rights reserved.