(************************************************************************)
(*         *   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)         *)
(************************************************************************)

Fixpoint sub (n m:nat) : nat :=
  match n, m with
  | S k, S l => k - l
  | _, _ => n
  end
where "n - m" := (sub n m) : nat_scope.

Require Import PeanoNat Lt Le.

Local Open Scope nat_scope.

Lemma minus_n_O n : n = n - 0.
n:nat
n = n - 0
Proof.
n:nat
n = n - 0
 symmetry.
n:nat
n - 0 = n apply Nat.sub_0_r.
Qed.

Lemma minus_Sn_m n m : m <= n -> S (n - m) = S n - m.
n, m:nat
m <= n -> S (n - m) = S n - m
Proof.
n, m:nat
m <= n -> S (n - m) = S n - m
 intros.
n, m:nat
H:m <= n
S (n - m) = S n - m symmetry.
n, m:nat
H:m <= n
S n - m = S (n - m) now apply Nat.sub_succ_l.
Qed.

Theorem pred_of_minus n : pred n = n - 1.
n:nat
Init.Nat.pred n = n - 1
Proof.
n:nat
Init.Nat.pred n = n - 1
 symmetry.
n:nat
n - 1 = Init.Nat.pred n apply Nat.sub_1_r.
Qed.

Register pred_of_minus as num.nat.pred_of_minus.

Notation minus_diag := Nat.sub_diag (only parsing). (* n - n = 0 *)

Lemma minus_diag_reverse n : 0 = n - n.
n:nat
0 = n - n
Proof.
n:nat
0 = n - n
 symmetry.
n:nat
n - n = 0 apply Nat.sub_diag.
Qed.

Notation minus_n_n := minus_diag_reverse.

Lemma minus_plus_simpl_l_reverse n m p : n - m = p + n - (p + m).
n, m, p:nat
n - m = p + n - (p + m)
Proof.
n, m, p:nat
n - m = p + n - (p + m)
 now rewrite Nat.sub_add_distr, Nat.add_comm, Nat.add_sub.
Qed.

Lemma plus_minus n m p : n = m + p -> p = n - m.
n, m, p:nat
n = m + p -> p = n - m
Proof.
n, m, p:nat
n = m + p -> p = n - m
 symmetry.
n, m, p:nat
H:n = m + p
n - m = p now apply Nat.add_sub_eq_l.
Qed.

Lemma minus_plus n m : n + m - n = m.
n, m:nat
n + m - n = m
Proof.
n, m:nat
n + m - n = m
 rewrite Nat.add_comm.
n, m:nat
m + n - n = m apply Nat.add_sub.
Qed.

Lemma le_plus_minus_r n m : n <= m -> n + (m - n) = m.
n, m:nat
n <= m -> n + (m - n) = m
Proof.
n, m:nat
n <= m -> n + (m - n) = m
 rewrite Nat.add_comm.
n, m:nat
n <= m -> m - n + n = m apply Nat.sub_add.
Qed.

Lemma le_plus_minus n m : n <= m -> m = n + (m - n).
n, m:nat
n <= m -> m = n + (m - n)
Proof.
n, m:nat
n <= m -> m = n + (m - n)
 intros.
n, m:nat
H:n <= m
m = n + (m - n) symmetry.
n, m:nat
H:n <= m
n + (m - n) = m rewrite Nat.add_comm.
n, m:nat
H:n <= m
m - n + n = m now apply Nat.sub_add.
Qed.

Notation minus_le_compat_r :=
  Nat.sub_le_mono_r (only parsing). (* n <= m -> n - p <= m - p. *)

Notation minus_le_compat_l :=
  Nat.sub_le_mono_l (only parsing). (* n <= m -> p - m <= p - n. *)

Notation le_minus := Nat.le_sub_l (only parsing). (* n - m <= n *)
Notation lt_minus := Nat.sub_lt (only parsing). (* m <= n -> 0 < m -> n-m < n *)

Lemma lt_O_minus_lt n m : 0 < n - m -> m < n.
n, m:nat
0 < n - m -> m < n
Proof.
n, m:nat
0 < n - m -> m < n
 apply Nat.lt_add_lt_sub_r.
Qed.

Theorem not_le_minus_0 n m : ~ m <= n -> n - m = 0.
n, m:nat
~ m <= n -> n - m = 0
Proof.
n, m:nat
~ m <= n -> n - m = 0
 intros.
n, m:nat
H:~ m <= n
n - m = 0 now apply Nat.sub_0_le, Nat.lt_le_incl, Nat.lt_nge.
Qed.

Hint Resolve minus_n_O: arith.
Hint Resolve minus_Sn_m: arith.
Hint Resolve minus_diag_reverse: arith.
Hint Resolve minus_plus_simpl_l_reverse: arith.
Hint Immediate plus_minus: arith.
Hint Resolve minus_plus: arith.
Hint Resolve le_plus_minus: arith.
Hint Resolve le_plus_minus_r: arith.
Hint Resolve lt_minus: arith.
Hint Immediate lt_O_minus_lt: arith.