Library UniMath.OrderTheory.Lattice.Lattice
Lattice
Catherine Lelay. Nov. 2016 -- min and max are associative
- min and max are commutative
- ∏ x y : X, min x (max x y) = x
- ∏ x y : X, max x (min x y) = x
- le := λ (x y : X), min lat x y = x
- ∏ (x y : X), (¬ gt x y) <-> le x y
- ∏ x y z : X, gt x z → gt y z → gt (min x y) z
- ∏ x y z : X, gt z x → gt z y → gt z (max lat x y)
- le is total and decidable
- it is a lattice with a strong order
- compatibility and cancelation of addition for le
- a function minus such that: ∏ (x y : X), (minus x y) + y = max x y
- weq
- abmonoidfrac
Require Import UniMath.MoreFoundations.All.
Require Import UniMath.Algebra.Monoids.
Require Import UniMath.Algebra.Groups.
Definition islatticeop {X : hSet} (min max : binop X) : UU :=
((isassoc min) × (iscomm min))
× ((isassoc max) × (iscomm max))
× (isabsorb min max)
× (isabsorb max min).
Lemma isaprop_islatticeop {X : hSet} (min max : binop X) :
isaprop (islatticeop min max).
Proof.
apply isapropdirprod ;
[ | apply isapropdirprod] ;
apply isapropdirprod.
apply isapropisassoc.
apply isapropiscomm.
apply isapropisassoc.
apply isapropiscomm.
apply isapropisabsorb.
apply isapropisabsorb.
Definition lattice (X : hSet) :=
∑ min max : binop X, islatticeop min max.
Definition make_lattice {X : hSet} {min max : binop X} : islatticeop min max → lattice X :=
λ (is : islatticeop min max), min,, max ,, is.
Definition Lmin {X : hSet} (lat : lattice X) : binop X := pr1 lat.
Definition Lmax {X : hSet} (lat : lattice X) : binop X := pr1 (pr2 lat).
Section lattice_pty.
Context {X : hSet}
(lat : lattice X).
Definition isassoc_Lmin : isassoc (Lmin lat) :=
pr1 (pr1 (pr2 (pr2 lat))).
Definition iscomm_Lmin : iscomm (Lmin lat) :=
pr2 (pr1 (pr2 (pr2 lat))).
Definition isassoc_Lmax : isassoc (Lmax lat) :=
pr1 (pr1 (pr2 (pr2 (pr2 lat)))).
Definition iscomm_Lmax : iscomm (Lmax lat) :=
pr2 (pr1 (pr2 (pr2 (pr2 lat)))).
Definition Lmin_absorb : isabsorb (Lmin lat) (Lmax lat) :=
pr1 (pr2 (pr2 (pr2 (pr2 lat)))).
Definition Lmax_absorb : isabsorb (Lmax lat) (Lmin lat) :=
pr2 (pr2 (pr2 (pr2 (pr2 lat)))).
Lemma Lmin_id :
∏ x : X, Lmin lat x x = x.
Show proof.
intros x.
intermediate_path (Lmin lat x (Lmax lat x (Lmin lat x x))).
- apply maponpaths, pathsinv0, Lmax_absorb.
- apply Lmin_absorb.
Lemma Lmax_id :intermediate_path (Lmin lat x (Lmax lat x (Lmin lat x x))).
- apply maponpaths, pathsinv0, Lmax_absorb.
- apply Lmin_absorb.
∏ x : X, Lmax lat x x = x.
Show proof.
intros x.
intermediate_path (Lmax lat x (Lmin lat x (Lmax lat x x))).
- apply maponpaths, pathsinv0, Lmin_absorb.
- apply Lmax_absorb.
intermediate_path (Lmax lat x (Lmin lat x (Lmax lat x x))).
- apply maponpaths, pathsinv0, Lmin_absorb.
- apply Lmax_absorb.
End lattice_pty.