Documentation

Linglib.Core.Order.Minimal

Minimality under a key and along a map #

Among elements none of which lies below another, minimality under a key depends only on the key's strict order between incomparable elements: when that order is an irreflexive relation r, the minimal elements are those that nothing is r-related to. A strictly monotone map along which lower elements lift carries the minimal elements of a preimage to the minimal elements of the set, whether or not the map is injective.

Main statements #

theorem minimalFor_iff_of_isAntichain {ι : Type u_1} {β : Type u_2} [Preorder ι] [Preorder β] {P : ι → Prop} {f : ι → β} {r : ι → ι → Prop} {i : ι} (hP : IsAntichain (fun (x1 x2 : ι) => x1 ≤ x2) {j : ι | P j}) (hr : ∀ (j : ι), ¬r j j) (h : ∀ ⦃j k : ι⦄, ¬j ≤ k → ¬k ≤ j → (f j < f k ↔ r j k)) :
MinimalFor P f i ↔ P i ∧ ∀ ⦃j : ι⦄, P j → ¬r j i

Among elements of P none of which lies below another, an element is minimal under a key whose strict order between incomparable elements is the irreflexive relation r exactly when no element of P is r-related to it.

theorem minimal_comp_iff_of_strictMono {β : Type u_2} [Preorder β] {α : Type u_3} [PartialOrder α] {g : α → β} {Q : β → Prop} {a : α} (hg : StrictMono g) (hlift : ∀ ⦃a : α⦄ ⦃b : β⦄, b ≤ g a → ∃ c ≤ a, g c = b) :
Minimal (fun (c : α) => Q (g c)) a ↔ Minimal Q (g a)

A strictly monotone map g such that every element below g a is the image of one below a reflects and preserves minimality: a is minimal among the elements whose image satisfies Q exactly when g a is minimal in Q.