Library Stdlib.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.

From Stdlib Require Import BinPos BinInt Decidable Zcompare.
From Stdlib 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



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



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


#[global]
Hint Resolve Z.le_refl: zarith.

Antisymmetry


Asymmetry


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

Irreflexivity


Lemma Zgt_irrefl n : ~ n > n.

Large = strict or equal


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

Dichotomy


Transitivity of strict orders

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

Mixed transitivity

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

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

#[global]
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.

#[global]
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


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

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


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

#[global]
Hint Resolve Z.le_succ_diag_r: zarith.
#[global]
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

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.

#[global]
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


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


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


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



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