(************************************************************************)
(*         *   The Coq Proof Assistant / The Coq Development Team       *)
(*  v      *   INRIA, CNRS and contributors - Copyright 1999-2018       *)
(* <O___,, *       (see CREDITS file for the list of authors)           *)
(*   \VV/  **************************************************************)
(*    //   *    This file is distributed under the terms of the         *)
(*         *     GNU Lesser General Public License Version 2.1          *)
(*         *     (see LICENSE file for the text of the license)         *)
(************************************************************************)

Require Import PeanoNat.
Local Open Scope nat_scope.

Fixpoint eq_nat n m : Prop :=
  match n, m with
    | O, O => True
    | O, S _ => False
    | S _, O => False
    | S n1, S m1 => eq_nat n1 m1
  end.

Theorem eq_nat_refl n : eq_nat n n.
n:nat
eq_nat n n
Proof.
n:nat
eq_nat n n
  induction n; simpl; auto.
Qed.
Hint Resolve eq_nat_refl: arith.

Theorem eq_nat_is_eq n m : eq_nat n m <-> n = m.
n, m:nat
eq_nat n m <-> n = m
Proof.
n, m:nat
eq_nat n m <-> n = m
  split.
n, m:nat
eq_nat n m -> n = m
n, m:nat
n = m -> eq_nat n m
  -
n, m:nat
eq_nat n m -> n = m revert m; induction n; destruct m; simpl; contradiction || auto.
  -
n, m:nat
n = m -> eq_nat n m intros <-; apply eq_nat_refl.
Qed.

Lemma eq_eq_nat n m : n = m -> eq_nat n m.
n, m:nat
n = m -> eq_nat n m
Proof.
n, m:nat
n = m -> eq_nat n m
 apply eq_nat_is_eq.
Qed.

Lemma eq_nat_eq n m : eq_nat n m -> n = m.
n, m:nat
eq_nat n m -> n = m
Proof.
n, m:nat
eq_nat n m -> n = m
 apply eq_nat_is_eq.
Qed.

Hint Immediate eq_eq_nat eq_nat_eq: arith.

Theorem eq_nat_elim :
  forall n (P:nat -> Prop), P n -> forall m, eq_nat n m -> P m.
forall (n : nat) (P : nat -> Prop),
P n -> forall m : nat, eq_nat n m -> P m
Proof.
forall (n : nat) (P : nat -> Prop),
P n -> forall m : nat, eq_nat n m -> P m
  intros; replace m with n; auto with arith.
Qed.

Theorem eq_nat_decide : forall n m, {eq_nat n m} + {~ eq_nat n m}.
forall n m : nat, {eq_nat n m} + {~ eq_nat n m}
Proof.
forall n m : nat, {eq_nat n m} + {~ eq_nat n m}
  induction n; destruct m; simpl.
{True} + {~ True}
m:nat
{False} + {~ False}
n:nat
IHn:forall m : nat, {eq_nat n m} + {~ eq_nat n m}
{False} + {~ False}
n:nat
IHn:forall m0 : nat, {eq_nat n m0} + {~ eq_nat n m0}
m:nat
{eq_nat n m} + {~ eq_nat n m}
  -
{True} + {~ True} left; trivial.
  -
m:nat
{False} + {~ False} right; intro; trivial.
  -
n:nat
IHn:forall m : nat, {eq_nat n m} + {~ eq_nat n m}
{False} + {~ False} right; intro; trivial.
  -
n:nat
IHn:forall m0 : nat, {eq_nat n m0} + {~ eq_nat n m0}
m:nat
{eq_nat n m} + {~ eq_nat n m} apply IHn.
Defined.

Notation beq_nat := Nat.eqb (only parsing).

Notation beq_nat_true_iff := Nat.eqb_eq (only parsing).
Notation beq_nat_false_iff := Nat.eqb_neq (only parsing).

Lemma beq_nat_refl n : true = (n =? n).
n:nat
true = (n =? n)
Proof.
n:nat
true = (n =? n)
 symmetry.
n:nat
(n =? n) = true apply Nat.eqb_refl.
Qed.

Lemma beq_nat_true n m : (n =? m) = true -> n=m.
n, m:nat
(n =? m) = true -> n = m
Proof.
n, m:nat
(n =? m) = true -> n = m
 apply Nat.eqb_eq.
Qed.

Lemma beq_nat_false n m : (n =? m) = false -> n<>m.
n, m:nat
(n =? m) = false -> n <> m
Proof.
n, m:nat
(n =? m) = false -> n <> m
 apply Nat.eqb_neq.
Qed.

Definition beq_nat_eq : forall n m, true = (n =? m) -> n = m.
forall n m : nat, true = (n =? m) -> n = m
Proof.
forall n m : nat, true = (n =? m) -> n = m
  induction n; destruct m; simpl.
true = true -> 0 = 0
m:nat
true = false -> 0 = S m
n:nat
IHn:forall m : nat, true = (n =? m) -> n = m
true = false -> S n = 0
n:nat
IHn:forall m0 : nat, true = (n =? m0) -> n = m0
m:nat
true = (n =? m) -> S n = S m
  -
true = true -> 0 = 0 reflexivity.
  -
m:nat
true = false -> 0 = S m discriminate.
  -
n:nat
IHn:forall m : nat, true = (n =? m) -> n = m
true = false -> S n = 0 discriminate.
  -
n:nat
IHn:forall m0 : nat, true = (n =? m0) -> n = m0
m:nat
true = (n =? m) -> S n = S m intros H.
n:nat
IHn:forall m0 : nat, true = (n =? m0) -> n = m0
m:nat
H:true = (n =? m)
S n = S m case (IHn _ H).
n:nat
IHn:forall m0 : nat, true = (n =? m0) -> n = m0
m:nat
H:true = (n =? m)
S n = S n reflexivity.
Defined.