1 files changed, 123 insertions, 0 deletions
diff --git a/theories/Arith/Minus.v b/theories/Arith/Minus.v
new file mode 100755
index 00000000..ba9a46ad
--- /dev/null
+++ b/theories/Arith/Minus.v
@@ -0,0 +1,123 @@
+(************************************************************************)
+(*  v      *   The Coq Proof Assistant  /  The Coq Development Team     *)
+(* <O___,, * CNRS-Ecole Polytechnique-INRIA Futurs-Universite Paris Sud *)
+(*   \VV/  **************************************************************)
+(*    //   *      This file is distributed under the terms of the       *)
+(*         *       GNU Lesser General Public License Version 2.1        *)
+(************************************************************************)
+
+(*i $Id: Minus.v,v 1.14.2.1 2004/07/16 19:31:00 herbelin Exp $ i*)
+
+(** Subtraction (difference between two natural numbers) *)
+
+Require Import Lt.
+Require Import Le.
+
+Open Local Scope nat_scope.
+
+Implicit Types m n p : nat.
+
+(** 0 is right neutral *)
+
+Lemma minus_n_O : forall n, n = n - 0.
+Proof.
+induction n; simpl in |- *; auto with arith.
+Qed.
+Hint Resolve minus_n_O: arith v62.
+
+(** Permutation with successor *)
+
+Lemma minus_Sn_m : forall n m, m <= n -> S (n - m) = S n - m.
+Proof.
+intros n m Le; pattern m, n in |- *; apply le_elim_rel; simpl in |- *;
+ auto with arith.
+Qed.
+Hint Resolve minus_Sn_m: arith v62.
+
+Theorem pred_of_minus : forall n, pred n = n - 1.
+intro x; induction x; simpl in |- *; auto with arith.
+Qed.
+
+(** Diagonal *)
+
+Lemma minus_n_n : forall n, 0 = n - n.
+Proof.
+induction n; simpl in |- *; auto with arith.
+Qed.
+Hint Resolve minus_n_n: arith v62.
+
+(** Simplification *)
+
+Lemma minus_plus_simpl_l_reverse : forall n m p, n - m = p + n - (p + m).
+Proof.
+  induction p; simpl in |- *; auto with arith.
+Qed.
+Hint Resolve minus_plus_simpl_l_reverse: arith v62.
+
+(** Relation with plus *)
+
+Lemma plus_minus : forall n m p, n = m + p -> p = n - m.
+Proof.
+intros n m p; pattern m, n in |- *; apply nat_double_ind; simpl in |- *;
+ intros.
+replace (n0 - 0) with n0; auto with arith.
+absurd (0 = S (n0 + p)); auto with arith.
+auto with arith.
+Qed.
+Hint Immediate plus_minus: arith v62.
+
+Lemma minus_plus : forall n m, n + m - n = m.
+symmetry  in |- *; auto with arith.
+Qed.
+Hint Resolve minus_plus: arith v62.
+
+Lemma le_plus_minus : forall n m, n <= m -> m = n + (m - n).
+Proof.
+intros n m Le; pattern n, m in |- *; apply le_elim_rel; simpl in |- *;
+ auto with arith.
+Qed.
+Hint Resolve le_plus_minus: arith v62.
+
+Lemma le_plus_minus_r : forall n m, n <= m -> n + (m - n) = m.
+Proof.
+symmetry  in |- *; auto with arith.
+Qed.
+Hint Resolve le_plus_minus_r: arith v62.
+
+(** Relation with order *)
+
+Theorem le_minus : forall n m, n - m <= n.
+Proof.
+intros i h; pattern i, h in |- *; apply nat_double_ind;
+ [ auto
+ | auto
+ | intros m n H; simpl in |- *; apply le_trans with (m := m); auto ].
+Qed.
+
+Lemma lt_minus : forall n m, m <= n -> 0 < m -> n - m < n.
+Proof.
+intros n m Le; pattern m, n in |- *; apply le_elim_rel; simpl in |- *;
+ auto with arith.
+intros; absurd (0 < 0); auto with arith.
+intros p q lepq Hp gtp.
+elim (le_lt_or_eq 0 p); auto with arith.
+auto with arith.
+induction 1; elim minus_n_O; auto with arith.
+Qed.
+Hint Resolve lt_minus: arith v62.
+
+Lemma lt_O_minus_lt : forall n m, 0 < n - m -> m < n.
+Proof.
+intros n m; pattern n, m in |- *; apply nat_double_ind; simpl in |- *;
+ auto with arith.
+intros; absurd (0 < 0); trivial with arith.
+Qed.
+Hint Immediate lt_O_minus_lt: arith v62.
+
+Theorem not_le_minus_0 : forall n m, ~ m <= n -> n - m = 0.
+intros y x; pattern y, x in |- *; apply nat_double_ind;
+ [ simpl in |- *; trivial with arith
+ | intros n H; absurd (0 <= S n); [ assumption | apply le_O_n ]
+ | simpl in |- *; intros n m H1 H2; apply H1; unfold not in |- *; intros H3;
+    apply H2; apply le_n_S; assumption ].
+Qed.
+\ No newline at end of file