Chains and flags

This file defines chains for an arbitrary relation and flags for an order and proves Hausdorff's Maximality Principle.

Main declarations

• IsChain s: A chain s is a set of comparable elements.
• maxChain_spec: Hausdorff's Maximality Principle.
• Flag: The type of flags, aka maximal chains, of an order.

Notes

Originally ported from Isabelle/HOL. The original file was written by Jacques D. Fleuriot, Tobias Nipkow, Christian Sternagel.

Chains

def IsChain {α : Type u_1} (r : α → α → Prop) (s : Set α) : Prop

A chain is a set s satisfying x ≺ y ∨ x = y ∨ y ≺ x for all x y ∈ s.

Equations

• IsChain r s = Set.Pairwise s fun x y => r x y ∨ r y x

def SuperChain {α : Type u_1} (r : α → α → Prop) (s : Set α) (t : Set α) : Prop

SuperChain s t means that t is a chain that strictly includes s.

Equations

• SuperChain r s t = (IsChain r t ∧ s ⊂ t)

def IsMaxChain {α : Type u_1} (r : α → α → Prop) (s : Set α) : Prop

A chain s is a maximal chain if there does not exists a chain strictly including s.

Equations

• IsMaxChain r s = (IsChain r s ∧ ∀ ⦃t : Set α⦄, IsChain r t → s ⊆ t → s = t)

theorem isChain_empty {α : Type u_1} {r : α → α → Prop} : IsChain r ∅

theorem Set.Subsingleton.isChain {α : Type u_1} {r : α → α → Prop} {s : Set α} (hs : Set.Subsingleton s) : IsChain r s

theorem IsChain.mono {α : Type u_1} {r : α → α → Prop} {s : Set α} {t : Set α} : s ⊆ t → IsChain r t → IsChain r s

theorem IsChain.mono_rel {α : Type u_1} {r : α → α → Prop} {s : Set α} {r' : α → α → Prop} (h : IsChain r s) (h_imp : (x y : α) → r x y → r' x y) : IsChain r' s

theorem IsChain.symm {α : Type u_1} {r : α → α → Prop} {s : Set α} (h : IsChain r s) : IsChain (flip r) s

This can be used to turn IsChain (≥) into IsChain (≤) and vice-versa.

theorem isChain_of_trichotomous {α : Type u_1} {r : α → α → Prop} [IsTrichotomous α r] (s : Set α) : IsChain r s

theorem IsChain.insert {α : Type u_1} {r : α → α → Prop} {s : Set α} {a : α} (hs : IsChain r s) (ha : ∀ (b : α), b ∈ s → a ≠ b → r a b ∨ r b a) : IsChain r (insert a s)

theorem isChain_univ_iff {α : Type u_1} {r : α → α → Prop} : IsChain r Set.univ ↔ IsTrichotomous α r

theorem IsChain.image {α : Type u_1} {β : Type u_2} (r : α → α → Prop) (s : β → β → Prop) (f : α → β) (h : (x y : α) → r x y → s (f x) (f y)) {c : Set α} (hrc : IsChain r c) : IsChain s (f '' c)

theorem Monotone.isChain_range {α : Type u_1} {β : Type u_2} [LinearOrder α] [Preorder β] {f : α → β} (hf : Monotone f) : IsChain (fun x x_1 => x ≤ x_1) (Set.range f)

theorem IsChain.lt_of_le {α : Type u_1} [PartialOrder α] {s : Set α} (h : IsChain (fun x x_1 => x ≤ x_1) s) : IsChain (fun x x_1 => x < x_1) s

theorem IsChain.total {α : Type u_1} {r : α → α → Prop} {s : Set α} {x : α} {y : α} [IsRefl α r] (h : IsChain r s) (hx : x ∈ s) (hy : y ∈ s) : r x y ∨ r y x

theorem IsChain.directedOn {α : Type u_1} {r : α → α → Prop} {s : Set α} [IsRefl α r] (H : IsChain r s) : DirectedOn r s

theorem IsChain.directed {α : Type u_1} {β : Type u_2} {r : α → α → Prop} [IsRefl α r] {f : β → α} {c : Set β} (h : IsChain (f ⁻¹'o r) c) : Directed r fun x => f ↑x

theorem IsChain.exists3 {α : Type u_1} {r : α → α → Prop} {s : Set α} [IsRefl α r] (hchain : IsChain r s) [IsTrans α r] {a : α} {b : α} {c : α} (mem1 : a ∈ s) (mem2 : b ∈ s) (mem3 : c ∈ s) : ∃ z x, r a z ∧ r b z ∧ r c z

theorem IsMaxChain.isChain {α : Type u_1} {r : α → α → Prop} {s : Set α} (h : IsMaxChain r s) : IsChain r s

theorem IsMaxChain.not_superChain {α : Type u_1} {r : α → α → Prop} {s : Set α} {t : Set α} (h : IsMaxChain r s) : ¬SuperChain r s t

theorem IsMaxChain.bot_mem {α : Type u_1} {s : Set α} [LE α] [OrderBot α] (h : IsMaxChain (fun x x_1 => x ≤ x_1) s) : ⊥ ∈ s

theorem IsMaxChain.top_mem {α : Type u_1} {s : Set α} [LE α] [OrderTop α] (h : IsMaxChain (fun x x_1 => x ≤ x_1) s) : ⊤ ∈ s

def SuccChain {α : Type u_1} (r : α → α → Prop) (s : Set α) : Set α

Given a set s, if there exists a chain t strictly including s, then SuccChain s is one of these chains. Otherwise it is s.

Equations

• SuccChain r s = if h : ∃ t, IsChain r s ∧ SuperChain r s t then Classical.choose h else s

theorem succChain_spec {α : Type u_1} {r : α → α → Prop} {s : Set α} (h : ∃ t, IsChain r s ∧ SuperChain r s t) : SuperChain r s (SuccChain r s)

theorem IsChain.succ {α : Type u_1} {r : α → α → Prop} {s : Set α} (hs : IsChain r s) : IsChain r (SuccChain r s)

theorem IsChain.superChain_succChain {α : Type u_1} {r : α → α → Prop} {s : Set α} (hs₁ : IsChain r s) (hs₂ : ¬IsMaxChain r s) : SuperChain r s (SuccChain r s)

theorem subset_succChain {α : Type u_1} {r : α → α → Prop} {s : Set α} : s ⊆ SuccChain r s

inductive ChainClosure {α : Type u_1} (r : α → α → Prop) : Set α → Prop

• succ: ∀ {α : Type u_1} {r : α → α → Prop} {s : Set α}, ChainClosure r s → ChainClosure r (SuccChain r s)
• union: ∀ {α : Type u_1} {r : α → α → Prop} {s : Set (Set α)}, (∀ (a : Set α), a ∈ s → ChainClosure r a) → ChainClosure r (⋃₀ s)

Predicate for whether a set is reachable from ∅ using SuccChain and ⋃₀.

def maxChain {α : Type u_1} (r : α → α → Prop) : Set α

An explicit maximal chain. maxChain is taken to be the union of all sets in ChainClosure.

Equations

• maxChain r = ⋃₀ setOf (ChainClosure r)

theorem chainClosure_empty {α : Type u_1} {r : α → α → Prop} : ChainClosure r ∅

theorem chainClosure_maxChain {α : Type u_1} {r : α → α → Prop} : ChainClosure r (maxChain r)

theorem ChainClosure.total {α : Type u_1} {r : α → α → Prop} {c₁ : Set α} {c₂ : Set α} (hc₁ : ChainClosure r c₁) (hc₂ : ChainClosure r c₂) : c₁ ⊆ c₂ ∨ c₂ ⊆ c₁

theorem ChainClosure.succ_fixpoint {α : Type u_1} {r : α → α → Prop} {c₁ : Set α} {c₂ : Set α} (hc₁ : ChainClosure r c₁) (hc₂ : ChainClosure r c₂) (hc : SuccChain r c₂ = c₂) : c₁ ⊆ c₂

theorem ChainClosure.succ_fixpoint_iff {α : Type u_1} {r : α → α → Prop} {c : Set α} (hc : ChainClosure r c) : SuccChain r c = c ↔ c = maxChain r

theorem ChainClosure.isChain {α : Type u_1} {r : α → α → Prop} {c : Set α} (hc : ChainClosure r c) : IsChain r c

theorem maxChain_spec {α : Type u_1} {r : α → α → Prop} : IsMaxChain r (maxChain r)

Hausdorff's maximality principle

There exists a maximal totally ordered set of α. Note that we do not require α to be partially ordered by r.

Flags

structure Flag (α : Type u_3) [LE α] : Type u_3

• carrier : Set α

  The carrier of a flag is the underlying set.

• Chain' : IsChain (fun x x_1 => x ≤ x_1) s.carrier

  By definition, a flag is a chain

• max_chain' : ∀ ⦃s_1 : Set α⦄, IsChain (fun x x_1 => x ≤ x_1) s_1 → s.carrier ⊆ s_1 → s.carrier = s_1

  By definition, a flag is a maximal chain

The type of flags, aka maximal chains, of an order.

instance Flag.instSetLikeFlag {α : Type u_1} [LE α] : SetLike (Flag α) α

Equations

• Flag.instSetLikeFlag = { coe := Flag.carrier, coe_injective' := (_ : ∀ (s t : Flag α), s.carrier = t.carrier → s = t) }

theorem Flag.ext {α : Type u_1} [LE α] {s : Flag α} {t : Flag α} : ↑s = ↑t → s = t

theorem Flag.mem_coe_iff {α : Type u_1} [LE α] {s : Flag α} {a : α} : a ∈ ↑s ↔ a ∈ s

@[simp]

theorem Flag.coe_mk {α : Type u_1} [LE α] (s : Set α) (h₁ : IsChain (fun x x_1 => x ≤ x_1) s) (h₂ : ∀ ⦃s : Set α⦄, IsChain (fun x x_1 => x ≤ x_1) s → s ⊆ s → s = s) : ↑{ carrier := s, Chain' := h₁, max_chain' := h₂ } = s

@[simp]

theorem Flag.mk_coe {α : Type u_1} [LE α] (s : Flag α) : { carrier := ↑s, Chain' := (_ : IsChain (fun x x_1 => x ≤ x_1) s.carrier), max_chain' := (_ : ∀ ⦃s : Set α⦄, IsChain (fun x x_1 => x ≤ x_1) s → s.carrier ⊆ s → s.carrier = s) } = s

theorem Flag.chain_le {α : Type u_1} [LE α] (s : Flag α) : IsChain (fun x x_1 => x ≤ x_1) ↑s

theorem Flag.maxChain {α : Type u_1} [LE α] (s : Flag α) : IsMaxChain (fun x x_1 => x ≤ x_1) ↑s

theorem Flag.top_mem {α : Type u_1} [LE α] [OrderTop α] (s : Flag α) : ⊤ ∈ s

theorem Flag.bot_mem {α : Type u_1} [LE α] [OrderBot α] (s : Flag α) : ⊥ ∈ s

theorem Flag.le_or_le {α : Type u_1} [Preorder α] {a : α} {b : α} (s : Flag α) (ha : a ∈ s) (hb : b ∈ s) : a ≤ b ∨ b ≤ a

instance Flag.instOrderTopSubtypeMemFlagToLEInstMembershipInstSetLikeFlagLe {α : Type u_1} [Preorder α] [OrderTop α] (s : Flag α) : OrderTop { x // x ∈ s }

Equations

• Flag.instOrderTopSubtypeMemFlagToLEInstMembershipInstSetLikeFlagLe s = Subtype.orderTop (_ : ⊤ ∈ s)

instance Flag.instOrderBotSubtypeMemFlagToLEInstMembershipInstSetLikeFlagLe {α : Type u_1} [Preorder α] [OrderBot α] (s : Flag α) : OrderBot { x // x ∈ s }

Equations

• Flag.instOrderBotSubtypeMemFlagToLEInstMembershipInstSetLikeFlagLe s = Subtype.orderBot (_ : ⊥ ∈ s)

instance Flag.instBoundedOrderSubtypeMemFlagToLEInstMembershipInstSetLikeFlagLe {α : Type u_1} [Preorder α] [BoundedOrder α] (s : Flag α) : BoundedOrder { x // x ∈ s }

Equations

• Flag.instBoundedOrderSubtypeMemFlagToLEInstMembershipInstSetLikeFlagLe s = Subtype.boundedOrder (_ : ⊥ ∈ s) (_ : ⊤ ∈ s)

theorem Flag.chain_lt {α : Type u_1} [PartialOrder α] (s : Flag α) : IsChain (fun x x_1 => x < x_1) ↑s

instance Flag.instLinearOrderSubtypeMemFlagToLEToPreorderInstMembershipInstSetLikeFlag {α : Type u_1} [PartialOrder α] [DecidableRel fun x x_1 => x ≤ x_1] [DecidableRel fun x x_1 => x < x_1] (s : Flag α) : LinearOrder { x // x ∈ s }

Equations

• One or more equations did not get rendered due to their size.

instance Flag.instUniqueFlagToLEToPreorderToPartialOrderToSemilatticeInfToLatticeInstDistribLattice {α : Type u_1} [LinearOrder α] : Unique (Flag α)

Equations

• One or more equations did not get rendered due to their size.