Library Coq.Arith.Minus

Properties of subtraction between natural numbers.

This file is mostly OBSOLETE now, see module PeanoNat.Nat instead.

minus is now an alias for Nat.sub, which is defined in Init/Nat.v as:

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.

0 is right neutral

Lemma minus_n_O n : n = n - 0.

Permutation with successor

Lemma minus_Sn_m n m : m <= n -> S (n - m) = S n - m.

Theorem pred_of_minus n : pred n = n - 1.

Diagonal

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

Notation minus_n_n := minus_diag_reverse.

Simplification

Lemma minus_plus_simpl_l_reverse n m p : n - m = p + n - (p + m ).

Relation with plus

Lemma plus_minus n m p : n = m + p -> p = n - m.

Lemma minus_plus n m : n + m - n = m.

Lemma le_plus_minus_r n m : n <= m -> n + (m - n ) = m.

Lemma le_plus_minus n m : n <= m -> m = n + (m - n ).

Relation with order

Notation minus_le_compat_r :=
Nat.sub_le_mono_r (only parsing).
Notation minus_le_compat_l :=
Nat.sub_le_mono_l (only parsing).
Notation le_minus := Nat.le_sub_l (only parsing). Notation lt_minus := Nat.sub_lt (only parsing).
Lemma lt_O_minus_lt n m : 0 < n - m -> m < n.

Theorem not_le_minus_0 n m : ~ m <= n -> n - m = 0.

Hints

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