Documentation

Linglib.Core.Order.ForestOrder

Forest orders #

An order is a forest when the elements below any element are pairwise comparable, a ≤ c → b ≤ c → a ≤ b ∨ b ≤ a, which is to say that every principal down-set is a chain: the order may branch upward but never downward. A forest in which any two elements have a common upper bound is totally ordered. Linear orders are forests, as is every PredOrder with archimedean predecessor, such as the rooted trees of Mathlib/Order/SuccPred/Tree.lean, and the property pulls back along an order embedding.

The flags of a forest are its branches. A flag contains everything below each of its elements, the down-set of a maximal element is a flag, and when > is well-founded every flag arises this way, so that quantifying over flags is quantifying over maximal elements.

[UPSTREAM] candidate for Mathlib/Order/Forest.lean. The class states what mathlib proves separately as le_total_of_directed and Part.le_total_of_le_of_le, and IsForestOrder.le_total is the totality behind IsPredArchimedean.linearOrder.

class IsForestOrder (α : Type u_3) [LE α] :

An order is a forest when the elements below any element are pairwise comparable, so that it never branches downward.

  • le_total_of_le_of_le ⦃a b c : α⦄ : a ≤ c → b ≤ c → a ≤ b ∨ b ≤ a

    The elements below any element are pairwise comparable.

Instances
    @[instance 100]
    instance LinearOrder.toIsForestOrder {α : Type u_1} [LinearOrder α] :
    @[instance 100]
    instance IsPredArchimedean.toIsForestOrder {α : Type u_1} [Preorder α] [PredOrder α] [IsPredArchimedean α] :
    theorem OrderEmbedding.isForestOrder {α : Type u_1} {β : Type u_2} [LE α] [LE β] [IsForestOrder β] (f : α ↪o β) :
    instance Subtype.instIsForestOrder {α : Type u_1} [LE α] [IsForestOrder α] (p : α → Prop) :
    IsForestOrder (Subtype p)
    theorem isForestOrder_orderDual_iff {α : Type u_1} [LE α] :
    IsForestOrder αᵒᵈ ↔ ∀ ⦃a b c : α⦄, c ≤ a → c ≤ b → a ≤ b ∨ b ≤ a

    The order dual of an order is a forest exactly when the elements above any element are pairwise comparable, so that the order never branches upward.

    theorem IsForestOrder.le_total {α : Type u_1} [Preorder α] [IsForestOrder α] [IsDirectedOrder α] (a b : α) :
    a ≤ b ∨ b ≤ a

    A forest in which any two elements have a common upper bound is totally ordered.

    theorem IsForestOrder.isChain_Iic {α : Type u_1} [Preorder α] [IsForestOrder α] (a : α) :
    IsChain (fun (x1 x2 : α) => x1 ≤ x2) (Set.Iic a)
    theorem IsForestOrder.disjoint_Ici_iff {α : Type u_1} [Preorder α] [IsForestOrder α] {a b : α} :
    Disjoint (Set.Ici a) (Set.Ici b) ↔ IncompRel (fun (x1 x2 : α) => x1 ≤ x2) a b

    In a forest two principal up-sets are disjoint exactly when their generators are incomparable.

    theorem IsForestOrder.le_of_lt_of_covBy {α : Type u_1} [Preorder α] [IsForestOrder α] {a b c : α} (hab : a ⋖ b) (hcb : c < b) :
    c ≤ a

    CovBy.le_of_lt in a forest.

    theorem IsForestOrder.covBy_unique_left {α : Type u_1} [PartialOrder α] {a b c : α} [IsForestOrder α] (ha : a ⋖ c) (hb : b ⋖ c) :
    a = b

    CovBy.unique_left in a forest: an element covers at most one element.

    theorem IsForestOrder.covBy_unique_right {α : Type u_1} [PartialOrder α] {a b c : α} [IsForestOrder αᵒᵈ] (hb : a ⋖ b) (hc : a ⋖ c) :
    b = c

    CovBy.unique_right when the order dual is a forest: an element is covered by at most one element.

    theorem IsForestOrder.eq_of_covBy_of_le {α : Type u_1} [PartialOrder α] {a c d x : α} [IsForestOrder α] (hc : a ⋖ c) (hd : a ⋖ d) (hcx : c ≤ x) (hdx : d ≤ x) :
    c = d

    In a forest, two elements covering the same element and lying below a common element are equal.

    theorem isForestOrder_iff_forall_isChain_Iic {α : Type u_1} [Preorder α] :
    IsForestOrder α ↔ ∀ (a : α), IsChain (fun (x1 x2 : α) => x1 ≤ x2) (Set.Iic a)

    Flags #

    theorem Flag.exists_mem_gt_of_lt {α : Type u_1} [PartialOrder α] {m x : α} {h : Flag α} (hm : m ∈ h) (hx : m < x) :
    ∃ y ∈ h, m < y

    A flag through a non-maximal element contains a strictly larger one; otherwise inserting the successor would extend the chain.

    theorem Flag.Iic_subset {α : Type u_1} [PartialOrder α] {m : α} {h : Flag α} [IsForestOrder α] (hm : m ∈ h) :
    Set.Iic m ⊆ ↑h
    def Flag.ofIsMax {α : Type u_1} [PartialOrder α] {x : α} [IsForestOrder α] (hx : IsMax x) :
    Flag α

    The down-set of a maximal element of a forest, as a flag.

    Equations
    • Flag.ofIsMax hx = { carrier := Set.Iic x, Chain' := ⋯, max_chain' := ⋯ }
    Instances For
      @[simp]
      theorem Flag.coe_ofIsMax {α : Type u_1} [PartialOrder α] {x : α} [IsForestOrder α] (hx : IsMax x) :
      ↑(ofIsMax hx) = Set.Iic x
      @[simp]
      theorem Flag.mem_ofIsMax {α : Type u_1} [PartialOrder α] {x y : α} [IsForestOrder α] {hx : IsMax x} :
      y ∈ ofIsMax hx ↔ y ≤ x
      theorem Flag.eq_ofIsMax_of_mem {α : Type u_1} [PartialOrder α] {x : α} {h : Flag α} [IsForestOrder α] (hx : IsMax x) (hxh : x ∈ h) :
      h = ofIsMax hx
      theorem Flag.exists_isMax_eq_ofIsMax {α : Type u_1} [PartialOrder α] [IsForestOrder α] [WellFoundedGT α] [Nonempty α] (h : Flag α) :
      ∃ (x : α) (hx : IsMax x), h = ofIsMax hx

      When > is well-founded, as on a finite order, every flag of a forest is the down-set of a maximal element: the flag has a greatest element, which a strict successor would contradict.

      theorem Flag.forall_mem_iff {α : Type u_1} [PartialOrder α] {m : α} [IsForestOrder α] [WellFoundedGT α] {P : Flag α → Prop} :
      (∀ (h : Flag α), m ∈ h → P h) ↔ ∀ (x : α) (hx : IsMax x), m ≤ x → P (ofIsMax hx)

      When > is well-founded, quantifying over the flags through an element of a left-linear order is quantifying over the maximal elements above it.