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.
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
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.
A forest in which any two elements have a common upper bound is totally ordered.
In a forest two principal up-sets are disjoint exactly when their generators are incomparable.
CovBy.le_of_lt in a forest.
CovBy.unique_left in a forest: an element covers at most one element.
CovBy.unique_right when the order dual is a forest: an element is covered by at most one
element.
In a forest, two elements covering the same element and lying below a common element are equal.
Flags #
A flag through a non-maximal element contains a strictly larger one; otherwise inserting the successor would extend the chain.
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
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.
When > is well-founded, quantifying over the flags through an element of a left-linear
order is quantifying over the maximal elements above it.