Coq beginner - Prove a basic lemma

Question

I'm a beginner with Coq so maybe my question will seems to be a dumb question, but here is my problem :

I defined a simple module in which I defined a type T and a function "my_custom_equal" :

  Definition T := nat.

  Fixpoint my_custom_equal (x y : T) :=
    match x, y with
      | O, O => true
      | O, S _ => false
      | S _, O => false
      | S sub_x, S sub_y => my_custom_equal sub_x sub_y
    end.

  Lemma my_custom_reflex : forall x : T, my_custom_equal x x = true.
  Proof.
    intros.
    induction x.
    simpl.
    reflexivity.
    simpl.
    rewrite IHx.
    reflexivity.
  Qed.

  Lemma my_custom_unicite : forall x y : T, my_custom_equal x y = true -> x = y.
  Proof.
    intros.
    induction x.
    induction y.
    reflexivity.
    discriminate.

  Qed.

As you can see, it is not really complicated but I still got stuck on the my_custom_unicite proof, I always reach the point where I need to prove that "S x = y" and my hypothesis are only :

y : nat
H : my_custom_equal 0 (S y) = true
IHy : my_custom_equal 0 y = true -> 0 = y
______________________________________(1/1)
S x = y

I don't understand how to achieve this proof, could you help me ?

Thanks!

Answer 1

This is a typical trap for beginners. The problem is that you performed induction on x when y was already introduced in your context. Because of that, the induction hypothesis that you obtain is not sufficiently general: what you really want is to have something like

forall y, my_custom_equal x y = true -> x = y

Notice the extra forall. The solution is to put y back into your goal:

Lemma my_custom_unicite : forall x y, my_custom_equal x y = true -> x = y.
Proof.
intros x y. revert y.
induction x as [|x IH].
- intros []; easy.
- intros [|y]; try easy.
  simpl.
  intros H.
  rewrite (IH y H).
  reflexivity.
Qed.

Try running this proof interactively and check how the induction hypothesis changes when you reach the second case.