Built with Alectryon, running Coq+SerAPI v8.18.0+0.18.3. Bubbles () indicate interactive fragments: hover for details, tap to reveal contents. Use Ctrl+βCtrl+β to navigate, Ctrl+π±οΈ to focus. On Mac, use β instead of Ctrl.
[Loading ML file number_string_notation_plugin.cmxs (using legacy method) ... done]
Generalizable VariablesA.(*In this file we describe interfaces for ordered structures. Since we are in aconstructive setting we use a pseudo order instead of a total order. Thereforewe also have to include an apartness relation.Obviously, in case we consider decidable structures these interfaces are quiteinconvenient. Hence we will, later on, provide means to go back and forthbetween the usual classical notions and these constructive notions.On the one hand, if we have an ordinary (total) partial order (β€) with acorresponding strict order (<), we will prove that we can construct aFullPartialOrder and PseudoPartialOrder, respectively.On the other hand, if equality is decidable, we will prove that we have theusual properties like Trichotomy (<) and TotalRelation (β€).*)ClassPartialOrder `(Ale : Le A) :=
{ po_hset : IsHSet A
; po_hprop : is_mere_relation A Ale
; po_preorder : PreOrder (β€)
; po_antisym : AntiSymmetric (β€) }.#[export] Existing Instances
po_hset
po_hprop
po_preorder
po_antisym.ClassTotalOrder `(Ale : Le A) :=
{ total_order_po : PartialOrder (β€)
; total_order_total : TotalRelation (β€) }.#[export] Existing Instances
total_order_po
total_order_total.(*We define a variant of the order theoretic definition of meet and joinsemilattices. Notice that we include a meet operation instead of themore common: forall x y, exists m, m β€ x /\ m β€ y /\ forall z, z β€ x -> z β€ y -> m β€ zOur definition is both stronger and more convenient than the above.This is needed to prove equavalence with the algebraic definition. Wedo this in orders.lattices.*)ClassMeetSemiLatticeOrder `(Ale : Le A) `{Meet A} :=
{ meet_sl_order : PartialOrder (β€)
; meet_lb_l : forallxy, x β y β€ x
; meet_lb_r : forallxy, x β y β€ y
; meet_glb : forallxyz, z β€ x -> z β€ y -> z β€ x β y }.#[export] Existing Instances meet_sl_order.ClassJoinSemiLatticeOrder `(Ale : Le A) `{Join A} :=
{ join_sl_order : PartialOrder (β€)
; join_ub_l : forallxy, x β€ x β y
; join_ub_r : forallxy, y β€ x β y
; join_lub : forallxyz, x β€ z -> y β€ z -> x β y β€ z }.#[export] Existing Instances join_sl_order.ClassLatticeOrder `(Ale : Le A) `{Meet A} `{Join A} :=
{ lattice_order_meet : MeetSemiLatticeOrder (β€)
; lattice_order_join : JoinSemiLatticeOrder (β€) }.#[export] Existing Instances lattice_order_meet lattice_order_join.ClassStrictOrder `(Alt : Lt A) :=
{ strict_order_mere : is_mere_relation A lt
; strictorder_irrefl : Irreflexive (<)
; strictorder_trans : Transitive (<) }.#[export] Existing Instances strict_order_mere strictorder_irrefl strictorder_trans.(* The constructive notion of a total strict total order. We will prove that (<) is in fact a StrictOrder. *)ClassPseudoOrder `{Aap : Apart A} (Alt : Lt A) :=
{ pseudo_order_apart : IsApart A
; pseudo_order_mere_lt : is_mere_relation A lt
; pseudo_order_antisym : forallxy, ~(x < y /\ y < x)
; pseudo_order_cotrans : CoTransitive (<)
; apart_iff_total_lt : forallxy, x βΆ y <-> x < y |_| y < x }.#[export] Existing Instances pseudo_order_mere_lt pseudo_order_cotrans.(* A partial order (β€) with a corresponding (<). We will prove that (<) is in fact a StrictOrder *)ClassFullPartialOrder `{Aap : Apart A} (Ale : Le A) (Alt : Lt A) :=
{ strict_po_apart : IsApart A
; strict_po_mere_lt : is_mere_relation A lt
; strict_po_po : PartialOrder (β€)
; strict_po_trans : Transitive (<)
; lt_iff_le_apart : forallxy, x < y <-> x β€ y /\ x βΆ y }.#[export] Existing Instances strict_po_po strict_po_trans.(* A pseudo order (<) with a corresponding (β€). We will prove that (β€) is in fact a PartialOrder. *)ClassFullPseudoOrder `{Aap : Apart A} (Ale : Le A) (Alt : Lt A) :=
{ fullpseudo_le_hprop : is_mere_relation A Ale
; full_pseudo_order_pseudo : PseudoOrder Alt
; le_iff_not_lt_flip : forallxy, x β€ y <-> ~(y < x) }.#[export] Existing Instances fullpseudo_le_hprop full_pseudo_order_pseudo.Sectionorder_maps.Context {AB : Type} {Ale: Le A} {Ble: Le B}(f : A -> B).ClassOrderPreserving := order_preserving : forallxy, (x β€ y -> f x β€ f y).ClassOrderReflecting := order_reflecting : forallxy, (f x β€ f y -> x β€ y).ClassOrderEmbedding :=
{ order_embedding_preserving : OrderPreserving
; order_embedding_reflecting : OrderReflecting }.#[export] Existing Instances order_embedding_preserving order_embedding_reflecting.Endorder_maps.Sectionsrorder_maps.Context {AB : Type} {Alt: Lt A} {Blt: Lt B} (f : A -> B).ClassStrictlyOrderPreserving := strictly_order_preserving
: forallxy, (x < y -> f x < f y).ClassStrictlyOrderReflecting := strictly_order_reflecting
: forallxy, (f x < f y -> x < y).ClassStrictOrderEmbedding :=
{ strict_order_embedding_preserving : StrictlyOrderPreserving
; strict_order_embedding_reflecting : StrictlyOrderReflecting }.#[export] Existing Instances strict_order_embedding_preserving strict_order_embedding_reflecting.Endsrorder_maps.#[export]
Hint Extern4 (?f _ β€ ?f _) => apply (order_preserving f) : core.#[export]
Hint Extern4 (?f _ < ?f _) => apply (strictly_order_preserving f) : core.(*We define various classes to describe the order on the lower part of thealgebraic hierarchy. This results in the notion of a PseudoSemiRingOrder, whichspecifies the order on the naturals, integers, rationals and reals. This notionis quite similar to a strictly linearly ordered unital commutative protoring inDavorin LeΕ‘nik's PhD thesis.*)ClassSemiRingOrder `{Plus A} `{Mult A}
`{Zero A} `{One A} (Ale : Le A) :=
{ srorder_po : PartialOrder Ale
; srorder_partial_minus : forallxy, x β€ y -> existsz, y = x + z
; srorder_plus : forallz, OrderEmbedding (z +)
; nonneg_mult_compat : forallxy, PropHolds (0 β€ x) -> PropHolds (0 β€ y) ->
PropHolds (0 β€ x * y) }.#[export] Existing Instances srorder_po srorder_plus.ClassStrictSemiRingOrder `{Plus A} `{Mult A}
`{Zero A} `{One A} (Alt : Lt A) :=
{ strict_srorder_so : StrictOrder Alt
; strict_srorder_partial_minus : forallxy, x < y -> existsz, y = x + z
; strict_srorder_plus : forallz, StrictOrderEmbedding (z +)
; pos_mult_compat : forallxy, PropHolds (0 < x) -> PropHolds (0 < y) ->
PropHolds (0 < x * y) }.#[export] Existing Instances strict_srorder_so strict_srorder_plus.ClassPseudoSemiRingOrder `{Apart A} `{Plus A}
`{Mult A} `{Zero A} `{One A} (Alt : Lt A) :=
{ pseudo_srorder_strict : PseudoOrder Alt
; pseudo_srorder_partial_minus : forallxy, ~(y < x) -> existsz, y = x + z
; pseudo_srorder_plus : forallz, StrictOrderEmbedding (z +)
; pseudo_srorder_mult_ext : StrongBinaryExtensionality (.*.)
; pseudo_srorder_pos_mult_compat : forallxy, PropHolds (0 < x) -> PropHolds (0 < y) ->
PropHolds (0 < x * y) }.#[export] Existing Instances pseudo_srorder_strict pseudo_srorder_plus pseudo_srorder_mult_ext.ClassFullPseudoSemiRingOrder `{Apart A} `{Plus A}
`{Mult A} `{Zero A} `{One A} (Ale : Le A) (Alt : Lt A) :=
{ full_pseudo_srorder_le_hprop : is_mere_relation A Ale
; full_pseudo_srorder_pso : PseudoSemiRingOrder Alt
; full_pseudo_srorder_le_iff_not_lt_flip : forallxy, x β€ y <-> ~(y < x) }.#[export] Existing Instances full_pseudo_srorder_le_hprop full_pseudo_srorder_pso.(* Due to bug #2528 *)#[export]
Hint Extern7 (PropHolds (0 < _ * _)) =>
eapply @pos_mult_compat : typeclass_instances.#[export]
Hint Extern7 (PropHolds (0 β€ _ * _)) =>
eapply @nonneg_mult_compat : typeclass_instances.(*Alternatively, we could have defined the standard notion of a RingOrder:Class RingOrder `{Equiv A} `{Plus A} `{Mult A} `{Zero A} (Ale : Le A) := { ringorder_po :> PartialOrder Ale ; ringorder_plus :> forall z, OrderPreserving (z +) ; ringorder_mult : forall x y, 0 β€ x -> 0 β€ y -> 0 β€ x * y }.Unfortunately, this notion is too weak when we consider semirings (e.g. thenaturals). Moreover, in case of rings, we prove that this notion is equivalentto our SemiRingOrder class (see orders.rings.from_ring_order). Hence we omitdefining such a class.Similarly we prove that a FullSemiRingOrderand a FullPseudoRingOrder are equivalent.Class FullPseudoRingOrder `{Apart A} `{Plus A} `{Mult A} `{Zero A} (Ale : Le A) (Alt : Lt A) := { pseudo_ringorder_spo :> FullPseudoOrder Ale Alt ; pseudo_ringorder_mult_ext :> StrongSetoid_BinaryMorphism (.*.) ; pseudo_ringorder_plus :> forall z, StrictlyOrderPreserving (z +) ; pseudo_ringorder_mult : forall x y, 0 < x -> 0 < y -> 0 < x * y }.*)(* Next, a constructive definition of fields - the ordered fields fromHoTT book chapter 11. *)ClassOrderedField (A : Type) {Alt : Lt A} {Ale : Le A} {Aap : Apart A} {Azero : Zero A}
{Aone : One A} {Aplus : Plus A} {Anegate : Negate A} {Amult : Mult A}
{Arecip : Recip A} {Ajoin : Join A} {Ameet : Meet A} :=
{ ordered_field_field : @IsField A Aplus Amult Azero Aone Anegate Aap Arecip
; ordered_field_lattice : LatticeOrder Ale
; ordered_field_fssro : @FullPseudoSemiRingOrder A _ _ _ Azero _ _ _
}.#[export] Existing Instances
ordered_field_field
ordered_field_lattice
ordered_field_fssro.