Built with Alectryon, running Coq+SerAPI v8.10.0+0.7.0. Coq sources are in this panel; goals and messages will appear in the other. Bubbles () indicate interactive fragments: hover for details, tap to reveal contents. Use Ctrl+↑ Ctrl+↓ to navigate, Ctrl+🖱️ to focus.

(* -*- coding: utf-8 -*- *)
(************************************************************************)
(*         *   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)         *)
(************************************************************************)

Binary Integers (Pierre Crégut, CNET, Lannion, France)

Require Export Arith_base.
Require Import BinInt.
Require Import Zorder.
Require Import Decidable.
Require Import Peano_dec.
Require Export Compare_dec.

Local Open Scope Z_scope.

(***************************************************************)

Moving terms from one side to the other of an inequality

Theorem Zne_left n m : Zne n m -> Zne (n + - m) 0.n, m:Z
Zne n m -> Zne (n + - m) 0
Proof.n, m:Z
Zne n m -> Zne (n + - m) 0
 unfold Zne.n, m:Z
n <> m -> n + - m <> 0 now rewrite <- Z.sub_move_0_r.
Qed.

Theorem Zegal_left n m : n = m -> n + - m = 0.n, m:Z
n = m -> n + - m = 0
Proof.n, m:Z
n = m -> n + - m = 0
 apply Z.sub_move_0_r.
Qed.

Theorem Zle_left n m : n <= m -> 0 <= m + - n.n, m:Z
n <= m -> 0 <= m + - n
Proof.n, m:Z
n <= m -> 0 <= m + - n
 apply Z.le_0_sub.
Qed.

Theorem Zle_left_rev n m : 0 <= m + - n -> n <= m.n, m:Z
0 <= m + - n -> n <= m
Proof.n, m:Z
0 <= m + - n -> n <= m
 apply Z.le_0_sub.
Qed.

Theorem Zlt_left_rev n m : 0 < m + - n -> n < m.n, m:Z
0 < m + - n -> n < m
Proof.n, m:Z
0 < m + - n -> n < m
 apply Z.lt_0_sub.
Qed.

Theorem Zlt_left_lt n m : n < m -> 0 < m + - n.n, m:Z
n < m -> 0 < m + - n
Proof.n, m:Z
n < m -> 0 < m + - n
 apply Z.lt_0_sub.
Qed.

Theorem Zlt_left n m : n < m -> 0 <= m + -1 + - n.n, m:Z
n < m -> 0 <= m + -1 + - n
Proof.n, m:Z
n < m -> 0 <= m + -1 + - n
 intros.n, m:Z
H:n < m
0 <= m + -1 + - n rewrite Z.add_shuffle0.n, m:Z
H:n < m
0 <= m + - n + -1 change (-1) with (- Z.succ 0).n, m:Z
H:n < m
0 <= m + - n + - Z.succ 0
 now apply Z.le_0_sub, Z.le_succ_l, Z.lt_0_sub.
Qed.

Theorem Zge_left n m : n >= m -> 0 <= n + - m.n, m:Z
n >= m -> 0 <= n + - m
Proof.n, m:Z
n >= m -> 0 <= n + - m
 Z.swap_greater.n, m:Z
m <= n -> 0 <= n + - m apply Z.le_0_sub.
Qed.

Theorem Zgt_left n m : n > m -> 0 <= n + -1 + - m.n, m:Z
n > m -> 0 <= n + -1 + - m
Proof.n, m:Z
n > m -> 0 <= n + -1 + - m
 Z.swap_greater.n, m:Z
m < n -> 0 <= n + -1 + - m apply Zlt_left.
Qed.

Theorem Zgt_left_gt n m : n > m -> n + - m > 0.n, m:Z
n > m -> n + - m > 0
Proof.n, m:Z
n > m -> n + - m > 0
 Z.swap_greater.n, m:Z
m < n -> 0 < n + - m apply Z.lt_0_sub.
Qed.

Theorem Zgt_left_rev n m : n + - m > 0 -> n > m.n, m:Z
n + - m > 0 -> n > m
Proof.n, m:Z
n + - m > 0 -> n > m
 Z.swap_greater.n, m:Z
0 < n + - m -> m < n apply Z.lt_0_sub.
Qed.

Theorem Zle_mult_approx n m p :
  n > 0 -> p > 0 -> 0 <= m -> 0 <= m * n + p.n, m, p:Z
n > 0 -> p > 0 -> 0 <= m -> 0 <= m * n + p
Proof.n, m, p:Z
n > 0 -> p > 0 -> 0 <= m -> 0 <= m * n + p
 Z.swap_greater.n, m, p:Z
0 < n -> 0 < p -> 0 <= m -> 0 <= m * n + p intros.n, m, p:Z
H:0 < n
H0:0 < p
H1:0 <= m
0 <= m * n + p Z.order_pos.
Qed.

Theorem Zmult_le_approx n m p :
  n > 0 -> n > p -> 0 <= m * n + p -> 0 <= m.n, m, p:Z
n > 0 -> n > p -> 0 <= m * n + p -> 0 <= m
Proof.n, m, p:Z
n > 0 -> n > p -> 0 <= m * n + p -> 0 <= m
 Z.swap_greater.n, m, p:Z
0 < n -> p < n -> 0 <= m * n + p -> 0 <= m intros.n, m, p:Z
H:0 < n
H0:p < n
H1:0 <= m * n + p
0 <= m apply Z.lt_succ_r.n, m, p:Z
H:0 < n
H0:p < n
H1:0 <= m * n + p
0 < Z.succ m
 apply Z.mul_pos_cancel_r with n; trivial.n, m, p:Z
H:0 < n
H0:p < n
H1:0 <= m * n + p
0 < Z.succ m * n Z.nzsimpl.n, m, p:Z
H:0 < n
H0:p < n
H1:0 <= m * n + p
0 < m * n + n
 apply Z.le_lt_trans with (m*n+p); trivial.n, m, p:Z
H:0 < n
H0:p < n
H1:0 <= m * n + p
m * n + p < m * n + n
 now apply Z.add_lt_mono_l.
Qed.

Register Zegal_left as plugins.omega.Zegal_left.
Register Zne_left as plugins.omega.Zne_left.
Register Zlt_left as plugins.omega.Zlt_left.
Register Zgt_left as plugins.omega.Zgt_left.
Register Zle_left as plugins.omega.Zle_left.
Register Zge_left as plugins.omega.Zge_left.
Register Zmult_le_approx as plugins.omega.Zmult_le_approx.