blob: 731219a6a18779eaeefece6f762f9b2aa711c140 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
(** * [Proper] morphisms for ℤ constants *)
Require Import Coq.omega.Omega.
Require Import Coq.micromega.Lia.
Require Import Coq.ZArith.ZArith.
Require Import Coq.Classes.Morphisms.
Require Import Coq.Classes.RelationPairs.
Require Import Crypto.Util.ZUtil.Definitions.
Local Open Scope Z_scope.
Module Z.
(** We prove a bunch of [Proper] lemmas, but do not make them
instances; making them instances would slow typeclass search
unacceptably. In files where we use these, we add them with
[Local Existing Instances]. *)
Lemma succ_le_Proper : Proper (Z.le ==> Z.le) Z.succ.
Proof. repeat (omega || intro). Qed.
Hint Resolve succ_le_Proper : zarith.
Lemma add_le_Proper : Proper (Z.le ==> Z.le ==> Z.le) Z.add.
Proof. repeat (omega || intro). Qed.
Hint Resolve add_le_Proper : zarith.
Lemma add_le_Proper' x : Proper (Z.le ==> Z.le) (Z.add x).
Proof. repeat (omega || intro). Qed.
Hint Resolve add_le_Proper' : zarith.
Lemma sub_le_ge_Proper : Proper (Z.le ==> Z.ge ==> Z.le) Z.sub.
Proof. repeat (omega || intro). Qed.
Hint Resolve sub_le_ge_Proper : zarith.
Lemma sub_le_flip_le_Proper : Proper (Z.le ==> Basics.flip Z.le ==> Z.le) Z.sub.
Proof. unfold Basics.flip; repeat (omega || intro). Qed.
Hint Resolve sub_le_flip_le_Proper : zarith.
Lemma sub_le_eq_Proper : Proper (Z.le ==> Logic.eq ==> Z.le) Z.sub.
Proof. repeat (omega || intro). Qed.
Hint Resolve sub_le_eq_Proper : zarith.
Lemma mul_Zpos_le_Proper p : Proper (Z.le ==> Z.le) (Z.mul (Z.pos p)).
Proof. repeat (nia || intro). Qed.
Hint Resolve mul_Zpos_le_Proper : zarith.
Lemma log2_up_le_Proper : Proper (Z.le ==> Z.le) Z.log2_up.
Proof. intros ???; apply Z.log2_up_le_mono; assumption. Qed.
Hint Resolve log2_up_le_Proper : zarith.
Lemma log2_le_Proper : Proper (Z.le ==> Z.le) Z.log2.
Proof. intros ???; apply Z.log2_le_mono; assumption. Qed.
Hint Resolve log2_le_Proper : zarith.
Lemma pow_Zpos_le_Proper x : Proper (Z.le ==> Z.le) (Z.pow (Z.pos x)).
Proof. intros ???; apply Z.pow_le_mono_r; try reflexivity; try assumption. Qed.
Hint Resolve pow_Zpos_le_Proper : zarith.
Lemma lt_le_flip_Proper_flip_impl
: Proper (Z.le ==> Basics.flip Z.le ==> Basics.flip Basics.impl) Z.lt.
Proof. unfold Basics.flip; repeat (omega || intro). Qed.
Hint Resolve lt_le_flip_Proper_flip_impl : zarith.
Lemma le_Proper_ge_le_flip_impl : Proper (Z.le ==> Z.ge ==> Basics.flip Basics.impl) Z.le.
Proof. intros ???????; omega. Qed.
Hint Resolve le_Proper_ge_le_flip_impl : zarith.
Lemma add_le_Proper_flip : Proper (Basics.flip Z.le ==> Basics.flip Z.le ==> Basics.flip Z.le) Z.add.
Proof. unfold Basics.flip; repeat (omega || intro). Qed.
Hint Resolve add_le_Proper_flip : zarith.
Lemma sub_le_ge_Proper_flip : Proper (Basics.flip Z.le ==> Basics.flip Z.ge ==> Basics.flip Z.le) Z.sub.
Proof. unfold Basics.flip; repeat (omega || intro). Qed.
Hint Resolve sub_le_ge_Proper_flip : zarith.
Lemma sub_flip_le_le_Proper_flip : Proper (Basics.flip Z.le ==> Z.le ==> Basics.flip Z.le) Z.sub.
Proof. unfold Basics.flip; repeat (omega || intro). Qed.
Hint Resolve sub_flip_le_le_Proper_flip : zarith.
Lemma sub_le_eq_Proper_flip : Proper (Basics.flip Z.le ==> Logic.eq ==> Basics.flip Z.le) Z.sub.
Proof. unfold Basics.flip; repeat (omega || intro). Qed.
Hint Resolve sub_le_eq_Proper_flip : zarith.
Lemma log2_up_le_Proper_flip : Proper (Basics.flip Z.le ==> Basics.flip Z.le) Z.log2_up.
Proof. intros ???; apply Z.log2_up_le_mono; assumption. Qed.
Hint Resolve log2_up_le_Proper_flip : zarith.
Lemma log2_le_Proper_flip : Proper (Basics.flip Z.le ==> Basics.flip Z.le) Z.log2.
Proof. intros ???; apply Z.log2_le_mono; assumption. Qed.
Hint Resolve log2_le_Proper_flip : zarith.
Lemma pow_Zpos_le_Proper_flip x : Proper (Basics.flip Z.le ==> Basics.flip Z.le) (Z.pow (Z.pos x)).
Proof. intros ???; apply Z.pow_le_mono_r; try reflexivity; try assumption. Qed.
Hint Resolve pow_Zpos_le_Proper_flip : zarith.
Lemma add_with_carry_le_Proper : Proper (Z.le ==> Z.le ==> Z.le ==> Z.le) Z.add_with_carry.
Proof. unfold Z.add_with_carry; repeat (omega || intro). Qed.
Hint Resolve add_with_carry_le_Proper : zarith.
Lemma sub_with_borrow_le_Proper : Proper (Basics.flip Z.le ==> Z.le ==> Basics.flip Z.le ==> Z.le) Z.sub_with_borrow.
Proof. unfold Z.sub_with_borrow, Z.add_with_carry, Basics.flip; repeat (omega || intro). Qed.
Hint Resolve sub_with_borrow_le_Proper : zarith.
End Z.
|