Library Coq.ZArith.Zorder


Binary Integers : results about order predicates Initial author : Pierre Crégut (CNET, Lannion, France)
THIS FILE IS DEPRECATED. It is now almost entirely made of compatibility formulations for results already present in BinInt.Z.

Require Import BinPos BinInt Decidable Zcompare.
Require Import Arith_base.
Local Open Scope Z_scope.

Properties of the order relations on binary integers

Trichotomy


Theorem Ztrichotomy_inf n m : {n < m} + {n = m} + {n > m}.

Theorem Ztrichotomy n m : n < m \/ n = m \/ n > m.

Decidability of equality and order on Z


Notation dec_eq := Z.eq_decidable (compat "8.3").
Notation dec_Zle := Z.le_decidable (compat "8.3").
Notation dec_Zlt := Z.lt_decidable (compat "8.3").

Theorem dec_Zne n m : decidable (Zne n m).

Theorem dec_Zgt n m : decidable (n > m).

Theorem dec_Zge n m : decidable (n >= m).

Theorem not_Zeq n m : n <> m -> n < m \/ m < n.

Relating strict and large orders


Notation Zgt_lt := Z.gt_lt (compat "8.3").
Notation Zlt_gt := Z.lt_gt (compat "8.3").
Notation Zge_le := Z.ge_le (compat "8.3").
Notation Zle_ge := Z.le_ge (compat "8.3").
Notation Zgt_iff_lt := Z.gt_lt_iff (compat "8.3").
Notation Zge_iff_le := Z.ge_le_iff (compat "8.3").

Lemma Zle_not_lt n m : n <= m -> ~ m < n.

Lemma Zlt_not_le n m : n < m -> ~ m <= n.

Lemma Zle_not_gt n m : n <= m -> ~ n > m.

Lemma Zgt_not_le n m : n > m -> ~ n <= m.

Lemma Znot_ge_lt n m : ~ n >= m -> n < m.

Lemma Znot_lt_ge n m : ~ n < m -> n >= m.

Lemma Znot_gt_le n m: ~ n > m -> n <= m.

Lemma Znot_le_gt n m : ~ n <= m -> n > m.

Lemma not_Zne n m : ~ Zne n m -> n = m.

Equivalence and order properties

Reflexivity

Notation Zle_refl := Z.le_refl (compat "8.3").
Notation Zeq_le := Z.eq_le_incl (compat "8.3").

Hint Resolve Z.le_refl: zarith.

Antisymmetry

Notation Zle_antisym := Z.le_antisymm (compat "8.3").

Asymmetry

Notation Zlt_asym := Z.lt_asymm (compat "8.3").

Lemma Zgt_asym n m : n > m -> ~ m > n.

Irreflexivity

Notation Zlt_irrefl := Z.lt_irrefl (compat "8.3").
Notation Zlt_not_eq := Z.lt_neq (compat "8.3").

Lemma Zgt_irrefl n : ~ n > n.

Large = strict or equal

Notation Zlt_le_weak := Z.lt_le_incl (compat "8.3").
Notation Zle_lt_or_eq_iff := Z.lt_eq_cases (compat "8.3").

Lemma Zle_lt_or_eq n m : n <= m -> n < m \/ n = m.

Dichotomy

Notation Zle_or_lt := Z.le_gt_cases (compat "8.3").

Transitivity of strict orders

Notation Zlt_trans := Z.lt_trans (compat "8.3").

Lemma Zgt_trans n m p : n > m -> m > p -> n > p.

Mixed transitivity

Notation Zlt_le_trans := Z.lt_le_trans (compat "8.3").
Notation Zle_lt_trans := Z.le_lt_trans (compat "8.3").

Lemma Zle_gt_trans n m p : m <= n -> m > p -> n > p.

Lemma Zgt_le_trans n m p : n > m -> p <= m -> n > p.

Transitivity of large orders

Notation Zle_trans := Z.le_trans (compat "8.3").

Lemma Zge_trans n m p : n >= m -> m >= p -> n >= p.

Hint Resolve Z.le_trans: zarith.

Compatibility of order and operations on Z

Successor

Compatibility of successor wrt to order

Lemma Zsucc_le_compat n m : m <= n -> Z.succ m <= Z.succ n.

Lemma Zsucc_lt_compat n m : n < m -> Z.succ n < Z.succ m.

Lemma Zsucc_gt_compat n m : m > n -> Z.succ m > Z.succ n.

Hint Resolve Zsucc_le_compat: zarith.

Simplification of successor wrt to order

Lemma Zsucc_gt_reg n m : Z.succ m > Z.succ n -> m > n.

Lemma Zsucc_le_reg n m : Z.succ m <= Z.succ n -> m <= n.

Lemma Zsucc_lt_reg n m : Z.succ n < Z.succ m -> n < m.

Special base instances of order

Notation Zlt_succ := Z.lt_succ_diag_r (compat "8.3").
Notation Zlt_pred := Z.lt_pred_l (compat "8.3").

Lemma Zgt_succ n : Z.succ n > n.

Lemma Znot_le_succ n : ~ Z.succ n <= n.

Relating strict and large order using successor or predecessor

Notation Zlt_succ_r := Z.lt_succ_r (compat "8.3").
Notation Zle_succ_l := Z.le_succ_l (compat "8.3").

Lemma Zgt_le_succ n m : m > n -> Z.succ n <= m.

Lemma Zle_gt_succ n m : n <= m -> Z.succ m > n.

Lemma Zle_lt_succ n m : n <= m -> n < Z.succ m.

Lemma Zlt_le_succ n m : n < m -> Z.succ n <= m.

Lemma Zgt_succ_le n m : Z.succ m > n -> n <= m.

Lemma Zlt_succ_le n m : n < Z.succ m -> n <= m.

Lemma Zle_succ_gt n m : Z.succ n <= m -> m > n.

Weakening order

Notation Zle_succ := Z.le_succ_diag_r (compat "8.3").
Notation Zle_pred := Z.le_pred_l (compat "8.3").
Notation Zlt_lt_succ := Z.lt_lt_succ_r (compat "8.3").
Notation Zle_le_succ := Z.le_le_succ_r (compat "8.3").

Lemma Zle_succ_le n m : Z.succ n <= m -> n <= m.

Hint Resolve Z.le_succ_diag_r: zarith.
Hint Resolve Z.le_le_succ_r: zarith.

Relating order wrt successor and order wrt predecessor

Lemma Zgt_succ_pred n m : m > Z.succ n -> Z.pred m > n.

Lemma Zlt_succ_pred n m : Z.succ n < m -> n < Z.pred m.

Relating strict order and large order on positive

Lemma Zlt_0_le_0_pred n : 0 < n -> 0 <= Z.pred n.

Lemma Zgt_0_le_0_pred n : n > 0 -> 0 <= Z.pred n.

Special cases of ordered integers

Notation Zlt_0_1 := Z.lt_0_1 (compat "8.3").
Notation Zle_0_1 := Z.le_0_1 (compat "8.3").

Lemma Zle_neg_pos : forall p q:positive, Zneg p <= Zpos q.

Lemma Zgt_pos_0 : forall p:positive, Zpos p > 0.

Lemma Zle_0_pos : forall p:positive, 0 <= Zpos p.

Lemma Zlt_neg_0 : forall p:positive, Zneg p < 0.

Lemma Zle_0_nat : forall n:nat, 0 <= Z.of_nat n.

Hint Immediate Z.eq_le_incl: zarith.

Derived lemma

Lemma Zgt_succ_gt_or_eq n m : Z.succ n > m -> n > m \/ m = n.

Addition

Compatibility of addition wrt to order

Notation Zplus_lt_le_compat := Z.add_lt_le_mono (compat "8.3").
Notation Zplus_le_lt_compat := Z.add_le_lt_mono (compat "8.3").
Notation Zplus_le_compat := Z.add_le_mono (compat "8.3").
Notation Zplus_lt_compat := Z.add_lt_mono (compat "8.3").

Lemma Zplus_gt_compat_l n m p : n > m -> p + n > p + m.

Lemma Zplus_gt_compat_r n m p : n > m -> n + p > m + p.

Lemma Zplus_le_compat_l n m p : n <= m -> p + n <= p + m.

Lemma Zplus_le_compat_r n m p : n <= m -> n + p <= m + p.

Lemma Zplus_lt_compat_l n m p : n < m -> p + n < p + m.

Lemma Zplus_lt_compat_r n m p : n < m -> n + p < m + p.

Compatibility of addition wrt to being positive

Notation Zplus_le_0_compat := Z.add_nonneg_nonneg (compat "8.3").

Simplification of addition wrt to order

Lemma Zplus_le_reg_l n m p : p + n <= p + m -> n <= m.

Lemma Zplus_le_reg_r n m p : n + p <= m + p -> n <= m.

Lemma Zplus_lt_reg_l n m p : p + n < p + m -> n < m.

Lemma Zplus_lt_reg_r n m p : n + p < m + p -> n < m.

Lemma Zplus_gt_reg_l n m p : p + n > p + m -> n > m.

Lemma Zplus_gt_reg_r n m p : n + p > m + p -> n > m.

Multiplication

Compatibility of multiplication by a positive wrt to order

Lemma Zmult_le_compat_r n m p : n <= m -> 0 <= p -> n * p <= m * p.

Lemma Zmult_le_compat_l n m p : n <= m -> 0 <= p -> p * n <= p * m.

Lemma Zmult_lt_compat_r n m p : 0 < p -> n < m -> n * p < m * p.

Lemma Zmult_gt_compat_r n m p : p > 0 -> n > m -> n * p > m * p.

Lemma Zmult_gt_0_lt_compat_r n m p : p > 0 -> n < m -> n * p < m * p.

Lemma Zmult_gt_0_le_compat_r n m p : p > 0 -> n <= m -> n * p <= m * p.

Lemma Zmult_lt_0_le_compat_r n m p : 0 < p -> n <= m -> n * p <= m * p.

Lemma Zmult_gt_0_lt_compat_l n m p : p > 0 -> n < m -> p * n < p * m.

Lemma Zmult_lt_compat_l n m p : 0 < p -> n < m -> p * n < p * m.

Lemma Zmult_gt_compat_l n m p : p > 0 -> n > m -> p * n > p * m.

Lemma Zmult_ge_compat_r n m p : n >= m -> p >= 0 -> n * p >= m * p.

Lemma Zmult_ge_compat_l n m p : n >= m -> p >= 0 -> p * n >= p * m.

Lemma Zmult_ge_compat n m p q :
  n >= p -> m >= q -> p >= 0 -> q >= 0 -> n * m >= p * q.

Lemma Zmult_le_compat n m p q :
  n <= p -> m <= q -> 0 <= n -> 0 <= m -> n * m <= p * q.

Simplification of multiplication by a positive wrt to being positive

Lemma Zmult_gt_0_lt_reg_r n m p : p > 0 -> n * p < m * p -> n < m.

Lemma Zmult_lt_reg_r n m p : 0 < p -> n * p < m * p -> n < m.

Lemma Zmult_le_reg_r n m p : p > 0 -> n * p <= m * p -> n <= m.

Lemma Zmult_lt_0_le_reg_r n m p : 0 < p -> n * p <= m * p -> n <= m.

Lemma Zmult_ge_reg_r n m p : p > 0 -> n * p >= m * p -> n >= m.

Lemma Zmult_gt_reg_r n m p : p > 0 -> n * p > m * p -> n > m.

Lemma Zmult_lt_compat n m p q :
  0 <= n < p -> 0 <= m < q -> n * m < p * q.

Lemma Zmult_lt_compat2 n m p q :
  0 < n <= p -> 0 < m < q -> n * m < p * q.

Compatibility of multiplication by a positive wrt to being positive

Notation Zmult_le_0_compat := Z.mul_nonneg_nonneg (compat "8.3").
Notation Zmult_lt_0_compat := Z.mul_pos_pos (compat "8.3").
Notation Zmult_lt_O_compat := Z.mul_pos_pos (compat "8.3").

Lemma Zmult_gt_0_compat n m : n > 0 -> m > 0 -> n * m > 0.


Lemma Zmult_gt_0_le_0_compat n m : n > 0 -> 0 <= m -> 0 <= m * n.

Simplification of multiplication by a positive wrt to being positive

Lemma Zmult_le_0_reg_r n m : n > 0 -> 0 <= m * n -> 0 <= m.

Lemma Zmult_lt_0_reg_r n m : 0 < n -> 0 < m * n -> 0 < m.

Lemma Zmult_gt_0_lt_0_reg_r n m : n > 0 -> 0 < m * n -> 0 < m.

Lemma Zmult_gt_0_reg_l n m : n > 0 -> n * m > 0 -> m > 0.

Square

Simplification of square wrt order

Lemma Zlt_square_simpl n m : 0 <= n -> m * m < n * n -> m < n.

Lemma Zgt_square_simpl n m : n >= 0 -> n * n > m * m -> n > m.

Equivalence between inequalities


Notation Zle_plus_swap := Z.le_add_le_sub_r (compat "8.3").
Notation Zlt_plus_swap := Z.lt_add_lt_sub_r (compat "8.3").
Notation Zlt_minus_simpl_swap := Z.lt_sub_pos (compat "8.3").

Lemma Zeq_plus_swap n m p : n + p = m <-> n = m - p.

Lemma Zlt_0_minus_lt n m : 0 < n - m -> m < n.

Lemma Zle_0_minus_le n m : 0 <= n - m -> m <= n.

Lemma Zle_minus_le_0 n m : m <= n -> 0 <= n - m.

For compatibility
Notation Zlt_O_minus_lt := Zlt_0_minus_lt (only parsing).