Documentation

Mathlib.Order.OmegaCompletePartialOrder

Omega Complete Partial Orders #

An omega-complete partial order is a partial order with a supremum operation on increasing sequences indexed by natural numbers (which we call ωSup). In this sense, it is strictly weaker than join complete semi-lattices as only ω-sized totally ordered sets have a supremum.

The concept of an omega-complete partial order (ωCPO) is useful for the formalization of the semantics of programming languages. Its notion of supremum helps define the meaning of recursive procedures.

Main definitions #

class OmegaCompletePartialOrder
ite, map, bind, seq as continuous morphisms

Instances of `OmegaCompletePartialOrder` #

Part
every CompleteLattice
pi-types
product types
OrderHom
ContinuousHom (with notation →𝒄)
- an instance of OmegaCompletePartialOrder (α →𝒄 β)
ContinuousHom.ofFun
ContinuousHom.ofMono
continuous functions:
- id
- ite
- const
- Part.bind
- Part.map
- Part.seq

References #

[Chain-complete posets and directed sets with applications][markowsky1976]
[Recursive definitions of partial functions and their computations][cadiou1972]
[Semantics of Programming Languages: Structures and Techniques][gunter1992]

@[simp]

theorem OrderHom.bind_coe {α : Type u_1} [inst : Preorder α] {β : Type u_2} {γ : Type u_2} (f : α →o Part β) (g : α →o β → Part γ) (x : α) :

↑(OrderHom.bind f g) x = ↑f x >>= ↑g x

def OrderHom.bind {α : Type u_1} [inst : Preorder α] {β : Type u_2} {γ : Type u_2} (f : α →o Part β) (g : α →o β → Part γ) :

α →o Part γ

Part.bind as a monotone function

Equations

OrderHom.bind f g = { toFun := fun x => ↑f x >>= ↑g x, monotone' := (_ : ∀ ⦃x y : α⦄, x ≤ y → ∀ (a : γ), a ∈ (fun x => ↑f x >>= ↑g x) x → a ∈ (fun x => ↑f x >>= ↑g x) y) }

def OmegaCompletePartialOrder.Chain (α : Type u) [inst : Preorder α] :

A chain is a monotone sequence.

See the definition on page 114 of [gunter1992].

Equations

OmegaCompletePartialOrder.Chain α = (ℕ →o α)

instance OmegaCompletePartialOrder.Chain.instCoeFunChainForAllNat {α : Type u} [inst : Preorder α] :

CoeFun (OmegaCompletePartialOrder.Chain α) fun x => ℕ → α

Equations

OmegaCompletePartialOrder.Chain.instCoeFunChainForAllNat = { coe := OrderHom.toFun }

instance OmegaCompletePartialOrder.Chain.instInhabitedChain {α : Type u} [inst : Preorder α] [inst : Inhabited α] :

Inhabited (OmegaCompletePartialOrder.Chain α)

Equations

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

instance OmegaCompletePartialOrder.Chain.instMembershipChain {α : Type u} [inst : Preorder α] :

Membership α (OmegaCompletePartialOrder.Chain α)

Equations

OmegaCompletePartialOrder.Chain.instMembershipChain = { mem := fun a c => ∃ i, a = ↑c i }

instance OmegaCompletePartialOrder.Chain.instLEChain {α : Type u} [inst : Preorder α] :

LE (OmegaCompletePartialOrder.Chain α)

Equations

OmegaCompletePartialOrder.Chain.instLEChain = { le := fun x y => ∀ (i : ℕ), ∃ j, ↑x i ≤ ↑y j }

@[simp]

theorem OmegaCompletePartialOrder.Chain.map_coe {α : Type u} {β : Type v} [inst : Preorder α] [inst : Preorder β] (c : OmegaCompletePartialOrder.Chain α) (f : α →o β) :

↑(OmegaCompletePartialOrder.Chain.map c f) = ↑f ∘ ↑c

def OmegaCompletePartialOrder.Chain.map {α : Type u} {β : Type v} [inst : Preorder α] [inst : Preorder β] (c : OmegaCompletePartialOrder.Chain α) (f : α →o β) :

OmegaCompletePartialOrder.Chain β

map function for Chain

Equations

OmegaCompletePartialOrder.Chain.map c f = OrderHom.comp f c

theorem OmegaCompletePartialOrder.Chain.mem_map {α : Type u} {β : Type v} [inst : Preorder α] [inst : Preorder β] (c : OmegaCompletePartialOrder.Chain α) {f : α →o β} (x : α) :

x ∈ c → ↑f x ∈ OmegaCompletePartialOrder.Chain.map c f

theorem OmegaCompletePartialOrder.Chain.exists_of_mem_map {α : Type u} {β : Type v} [inst : Preorder α] [inst : Preorder β] (c : OmegaCompletePartialOrder.Chain α) {f : α →o β} {b : β} :

b ∈ OmegaCompletePartialOrder.Chain.map c f → ∃ a, a ∈ c ∧ ↑f a = b

theorem OmegaCompletePartialOrder.Chain.mem_map_iff {α : Type u} {β : Type v} [inst : Preorder α] [inst : Preorder β] (c : OmegaCompletePartialOrder.Chain α) {f : α →o β} {b : β} :

b ∈ OmegaCompletePartialOrder.Chain.map c f ↔ ∃ a, a ∈ c ∧ ↑f a = b

@[simp]

theorem OmegaCompletePartialOrder.Chain.map_id {α : Type u} [inst : Preorder α] (c : OmegaCompletePartialOrder.Chain α) :

OmegaCompletePartialOrder.Chain.map c OrderHom.id = c

theorem OmegaCompletePartialOrder.Chain.map_comp {α : Type u} {β : Type v} {γ : Type u_1} [inst : Preorder α] [inst : Preorder β] [inst : Preorder γ] (c : OmegaCompletePartialOrder.Chain α) {f : α →o β} (g : β →o γ) :

OmegaCompletePartialOrder.Chain.map (OmegaCompletePartialOrder.Chain.map c f) g = OmegaCompletePartialOrder.Chain.map c (OrderHom.comp g f)

theorem OmegaCompletePartialOrder.Chain.map_le_map {α : Type u} {β : Type v} [inst : Preorder α] [inst : Preorder β] (c : OmegaCompletePartialOrder.Chain α) {f : α →o β} {g : α →o β} (h : f ≤ g) :

OmegaCompletePartialOrder.Chain.map c f ≤ OmegaCompletePartialOrder.Chain.map c g

@[simp]

theorem OmegaCompletePartialOrder.Chain.zip_coe {α : Type u} {β : Type v} [inst : Preorder α] [inst : Preorder β] (c₀ : OmegaCompletePartialOrder.Chain α) (c₁ : OmegaCompletePartialOrder.Chain β) (x : ℕ) :

↑(OmegaCompletePartialOrder.Chain.zip c₀ c₁) x = (↑c₀ x, ↑c₁ x)

def OmegaCompletePartialOrder.Chain.zip {α : Type u} {β : Type v} [inst : Preorder α] [inst : Preorder β] (c₀ : OmegaCompletePartialOrder.Chain α) (c₁ : OmegaCompletePartialOrder.Chain β) :

OmegaCompletePartialOrder.Chain (α × β)

chain.zip pairs up the elements of two chains that have the same index

Equations

OmegaCompletePartialOrder.Chain.zip c₀ c₁ = OrderHom.prod c₀ c₁

class OmegaCompletePartialOrder (α : Type u_1) extends PartialOrder :

Type u_1

The supremum of an increasing sequence
ωSup : OmegaCompletePartialOrder.Chain α → α
ωSup is an upper bound of the increasing sequence
le_ωSup : ∀ (c : OmegaCompletePartialOrder.Chain α) (i : ℕ), ↑c i ≤ ωSup c
ωSup is a lower bound of the set of upper bounds of the increasing sequence
ωSup_le : ∀ (c : OmegaCompletePartialOrder.Chain α) (x : α), (∀ (i : ℕ), ↑c i ≤ x) → ωSup c ≤ x

An omega-complete partial order is a partial order with a supremum operation on increasing sequences indexed by natural numbers (which we call ωSup). In this sense, it is strictly weaker than join complete semi-lattices as only ω-sized totally ordered sets have a supremum.

See the definition on page 114 of [gunter1992].

Instances

def OmegaCompletePartialOrder.lift {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : PartialOrder β] (f : β →o α) (ωSup₀ : OmegaCompletePartialOrder.Chain β → β) (h : ∀ (x y : β), ↑f x ≤ ↑f y → x ≤ y) (h' : ∀ (c : OmegaCompletePartialOrder.Chain β), ↑f (ωSup₀ c) = OmegaCompletePartialOrder.ωSup (OmegaCompletePartialOrder.Chain.map c f)) :

OmegaCompletePartialOrder β

Transfer a OmegaCompletePartialOrder on β to a OmegaCompletePartialOrder on α using a strictly monotone function f : β →o α, a definition of ωSup and a proof that f is continuous with regard to the provided ωSup and the ωCPO on α.

Equations

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

theorem OmegaCompletePartialOrder.le_ωSup_of_le {α : Type u} [inst : OmegaCompletePartialOrder α] {c : OmegaCompletePartialOrder.Chain α} {x : α} (i : ℕ) (h : x ≤ ↑c i) :

x ≤ OmegaCompletePartialOrder.ωSup c

theorem OmegaCompletePartialOrder.ωSup_total {α : Type u} [inst : OmegaCompletePartialOrder α] {c : OmegaCompletePartialOrder.Chain α} {x : α} (h : ∀ (i : ℕ), ↑c i ≤ x ∨ x ≤ ↑c i) :

OmegaCompletePartialOrder.ωSup c ≤ x ∨ x ≤ OmegaCompletePartialOrder.ωSup c

theorem OmegaCompletePartialOrder.ωSup_le_ωSup_of_le {α : Type u} [inst : OmegaCompletePartialOrder α] {c₀ : OmegaCompletePartialOrder.Chain α} {c₁ : OmegaCompletePartialOrder.Chain α} (h : c₀ ≤ c₁) :

OmegaCompletePartialOrder.ωSup c₀ ≤ OmegaCompletePartialOrder.ωSup c₁

theorem OmegaCompletePartialOrder.ωSup_le_iff {α : Type u} [inst : OmegaCompletePartialOrder α] (c : OmegaCompletePartialOrder.Chain α) (x : α) :

OmegaCompletePartialOrder.ωSup c ≤ x ↔ ∀ (i : ℕ), ↑c i ≤ x

def OmegaCompletePartialOrder.subtype {α : Type u_1} [inst : OmegaCompletePartialOrder α] (p : α → Prop) (hp : (c : OmegaCompletePartialOrder.Chain α) → ((i : α) → i ∈ c → p i) → p (OmegaCompletePartialOrder.ωSup c)) :

OmegaCompletePartialOrder (Subtype p)

A subset p : α → Prop of the type closed under ωSup induces an OmegaCompletePartialOrder on the subtype {a : α // p a}.

Equations

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

def OmegaCompletePartialOrder.Continuous {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (f : α →o β) :

A monotone function f : α →o β is continuous if it distributes over ωSup.

In order to distinguish it from the (more commonly used) continuity from topology (see topology/basic.lean), the present definition is often referred to as "Scott-continuity" (referring to Dana Scott). It corresponds to continuity in Scott topological spaces (not defined here).

Equations

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

def OmegaCompletePartialOrder.Continuous' {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (f : α → β) :

Continuous' f asserts that f is both monotone and continuous.

Equations

OmegaCompletePartialOrder.Continuous' f = ∃ hf, OmegaCompletePartialOrder.Continuous { toFun := f, monotone' := hf }

theorem OmegaCompletePartialOrder.Continuous'.to_monotone {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] {f : α → β} (hf : OmegaCompletePartialOrder.Continuous' f) :

theorem OmegaCompletePartialOrder.Continuous.of_bundled {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (f : α → β) (hf : Monotone f) (hf' : OmegaCompletePartialOrder.Continuous { toFun := f, monotone' := hf }) :

OmegaCompletePartialOrder.Continuous' f

theorem OmegaCompletePartialOrder.Continuous.of_bundled' {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (f : α →o β) (hf' : OmegaCompletePartialOrder.Continuous f) :

OmegaCompletePartialOrder.Continuous' ↑f

theorem OmegaCompletePartialOrder.Continuous'.to_bundled {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (f : α → β) (hf : OmegaCompletePartialOrder.Continuous' f) :

OmegaCompletePartialOrder.Continuous { toFun := f, monotone' := (_ : Monotone f) }

@[simp]

theorem OmegaCompletePartialOrder.continuous'_coe {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] {f : α →o β} :

OmegaCompletePartialOrder.Continuous' ↑f ↔ OmegaCompletePartialOrder.Continuous f

theorem OmegaCompletePartialOrder.continuous_id {α : Type u} [inst : OmegaCompletePartialOrder α] :

OmegaCompletePartialOrder.Continuous OrderHom.id

theorem OmegaCompletePartialOrder.continuous_comp {α : Type u} {β : Type v} {γ : Type u_1} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] [inst : OmegaCompletePartialOrder γ] (f : α →o β) (g : β →o γ) (hfc : OmegaCompletePartialOrder.Continuous f) (hgc : OmegaCompletePartialOrder.Continuous g) :

OmegaCompletePartialOrder.Continuous (OrderHom.comp g f)

theorem OmegaCompletePartialOrder.id_continuous' {α : Type u} [inst : OmegaCompletePartialOrder α] :

OmegaCompletePartialOrder.Continuous' id

theorem OmegaCompletePartialOrder.continuous_const {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (x : β) :

OmegaCompletePartialOrder.Continuous (↑(OrderHom.const α) x)

theorem OmegaCompletePartialOrder.const_continuous' {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (x : β) :

OmegaCompletePartialOrder.Continuous' (Function.const α x)

theorem Part.eq_of_chain {α : Type u} {c : OmegaCompletePartialOrder.Chain (Part α)} {a : α} {b : α} (ha : Part.some a ∈ c) (hb : Part.some b ∈ c) :

a = b

noncomputable def Part.ωSup {α : Type u} (c : OmegaCompletePartialOrder.Chain (Part α)) :

The (noncomputable) ωSup definition for the ω-CPO structure on part α.

Equations

Part.ωSup c = if h : ∃ a, Part.some a ∈ c then Part.some (Classical.choose h) else Part.none

theorem Part.ωSup_eq_some {α : Type u} {c : OmegaCompletePartialOrder.Chain (Part α)} {a : α} (h : Part.some a ∈ c) :

Part.ωSup c = Part.some a

theorem Part.ωSup_eq_none {α : Type u} {c : OmegaCompletePartialOrder.Chain (Part α)} (h : ¬∃ a, Part.some a ∈ c) :

Part.ωSup c = Part.none

theorem Part.mem_chain_of_mem_ωSup {α : Type u} {c : OmegaCompletePartialOrder.Chain (Part α)} {a : α} (h : a ∈ Part.ωSup c) :

Part.some a ∈ c

noncomputable instance Part.omegaCompletePartialOrder {α : Type u} :

OmegaCompletePartialOrder (Part α)

Equations

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

theorem Part.mem_ωSup {α : Type u} (x : α) (c : OmegaCompletePartialOrder.Chain (Part α)) :

x ∈ OmegaCompletePartialOrder.ωSup c ↔ Part.some x ∈ c

instance Pi.instOmegaCompletePartialOrderForAll {α : Type u_1} {β : α → Type u_2} [inst : (a : α) → OmegaCompletePartialOrder (β a)] :

OmegaCompletePartialOrder ((a : α) → β a)

Equations

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

theorem Pi.OmegaCompletePartialOrder.flip₁_continuous' {α : Type u_2} {β : α → Type u_3} {γ : Type u_1} [inst : (x : α) → OmegaCompletePartialOrder (β x)] [inst : OmegaCompletePartialOrder γ] (f : (x : α) → γ → β x) (a : α) (hf : OmegaCompletePartialOrder.Continuous' fun x y => f y x) :

OmegaCompletePartialOrder.Continuous' (f a)

theorem Pi.OmegaCompletePartialOrder.flip₂_continuous' {α : Type u_3} {β : α → Type u_2} {γ : Type u_1} [inst : (x : α) → OmegaCompletePartialOrder (β x)] [inst : OmegaCompletePartialOrder γ] (f : γ → (x : α) → β x) (hf : ∀ (x : α), OmegaCompletePartialOrder.Continuous' fun g => f g x) :

OmegaCompletePartialOrder.Continuous' f

@[simp]

theorem Prod.ωSup_fst {α : Type u_1} {β : Type u_2} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (c : OmegaCompletePartialOrder.Chain (α × β)) :

(Prod.ωSup c).fst = OmegaCompletePartialOrder.ωSup (OmegaCompletePartialOrder.Chain.map c OrderHom.fst)

@[simp]

theorem Prod.ωSup_snd {α : Type u_1} {β : Type u_2} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (c : OmegaCompletePartialOrder.Chain (α × β)) :

(Prod.ωSup c).snd = OmegaCompletePartialOrder.ωSup (OmegaCompletePartialOrder.Chain.map c OrderHom.snd)

def Prod.ωSup {α : Type u_1} {β : Type u_2} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (c : OmegaCompletePartialOrder.Chain (α × β)) :

α × β

The supremum of a chain in the product ω-CPO.

Equations

Prod.ωSup c = (OmegaCompletePartialOrder.ωSup (OmegaCompletePartialOrder.Chain.map c OrderHom.fst), OmegaCompletePartialOrder.ωSup (OmegaCompletePartialOrder.Chain.map c OrderHom.snd))

@[simp]

theorem Prod.instOmegaCompletePartialOrderProd_ωSup_fst {α : Type u_1} {β : Type u_2} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (c : OmegaCompletePartialOrder.Chain (α × β)) :

(OmegaCompletePartialOrder.ωSup c).fst = OmegaCompletePartialOrder.ωSup (OmegaCompletePartialOrder.Chain.map c OrderHom.fst)

@[simp]

theorem Prod.instOmegaCompletePartialOrderProd_ωSup_snd {α : Type u_1} {β : Type u_2} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (c : OmegaCompletePartialOrder.Chain (α × β)) :

(OmegaCompletePartialOrder.ωSup c).snd = OmegaCompletePartialOrder.ωSup (OmegaCompletePartialOrder.Chain.map c OrderHom.snd)

instance Prod.instOmegaCompletePartialOrderProd {α : Type u_1} {β : Type u_2} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] :

OmegaCompletePartialOrder (α × β)

Equations

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

theorem Prod.ωSup_zip {α : Type u_1} {β : Type u_2} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (c₀ : OmegaCompletePartialOrder.Chain α) (c₁ : OmegaCompletePartialOrder.Chain β) :

OmegaCompletePartialOrder.ωSup (OmegaCompletePartialOrder.Chain.zip c₀ c₁) = (OmegaCompletePartialOrder.ωSup c₀, OmegaCompletePartialOrder.ωSup c₁)

instance CompleteLattice.instOmegaCompletePartialOrder (α : Type u) [inst : CompleteLattice α] :

OmegaCompletePartialOrder α

Any complete lattice has an ω-CPO structure where the countable supremum is a special case of arbitrary suprema.

Equations

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

theorem CompleteLattice.supₛ_continuous {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : CompleteLattice β] (s : Set (α →o β)) (hs : ∀ (f : α →o β), f ∈ s → OmegaCompletePartialOrder.Continuous f) :

OmegaCompletePartialOrder.Continuous (supₛ s)

theorem CompleteLattice.supᵢ_continuous {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : CompleteLattice β] {ι : Sort u_1} {f : ι → α →o β} (h : ∀ (i : ι), OmegaCompletePartialOrder.Continuous (f i)) :

OmegaCompletePartialOrder.Continuous (⨆ i, f i)

theorem CompleteLattice.supₛ_continuous' {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : CompleteLattice β] (s : Set (α → β)) (hc : ∀ (f : α → β), f ∈ s → OmegaCompletePartialOrder.Continuous' f) :

OmegaCompletePartialOrder.Continuous' (supₛ s)

theorem CompleteLattice.sup_continuous {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : CompleteLattice β] {f : α →o β} {g : α →o β} (hf : OmegaCompletePartialOrder.Continuous f) (hg : OmegaCompletePartialOrder.Continuous g) :

OmegaCompletePartialOrder.Continuous (f ⊔ g)

theorem CompleteLattice.top_continuous {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : CompleteLattice β] :

OmegaCompletePartialOrder.Continuous ⊤

theorem CompleteLattice.bot_continuous {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : CompleteLattice β] :

OmegaCompletePartialOrder.Continuous ⊥

theorem CompleteLattice.inf_continuous {α : Type u_1} {β : Type u_2} [inst : OmegaCompletePartialOrder α] [inst : CompleteLinearOrder β] (f : α →o β) (g : α →o β) (hf : OmegaCompletePartialOrder.Continuous f) (hg : OmegaCompletePartialOrder.Continuous g) :

OmegaCompletePartialOrder.Continuous (f ⊓ g)

theorem CompleteLattice.inf_continuous' {α : Type u_1} {β : Type u_2} [inst : OmegaCompletePartialOrder α] [inst : CompleteLinearOrder β] {f : α → β} {g : α → β} (hf : OmegaCompletePartialOrder.Continuous' f) (hg : OmegaCompletePartialOrder.Continuous' g) :

OmegaCompletePartialOrder.Continuous' (f ⊓ g)

@[simp]

theorem OmegaCompletePartialOrder.OrderHom.ωSup_coe {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (c : OmegaCompletePartialOrder.Chain (α →o β)) (a : α) :

↑(OmegaCompletePartialOrder.OrderHom.ωSup c) a = OmegaCompletePartialOrder.ωSup (OmegaCompletePartialOrder.Chain.map c (OrderHom.apply a))

def OmegaCompletePartialOrder.OrderHom.ωSup {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (c : OmegaCompletePartialOrder.Chain (α →o β)) :

α →o β

The ωSup operator for monotone functions.

Equations

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

@[simp]

theorem OmegaCompletePartialOrder.OrderHom.omegaCompletePartialOrder_ωSup_coe {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (c : OmegaCompletePartialOrder.Chain (α →o β)) (a : α) :

↑(OmegaCompletePartialOrder.ωSup c) a = OmegaCompletePartialOrder.ωSup (OmegaCompletePartialOrder.Chain.map c (OrderHom.apply a))

instance OmegaCompletePartialOrder.OrderHom.omegaCompletePartialOrder {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] :

OmegaCompletePartialOrder (α →o β)

Equations

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

structure OmegaCompletePartialOrder.ContinuousHom (α : Type u) (β : Type v) [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] extends OrderHom :

Type (maxuv)

The underlying function of a ContinuousHom is continuous, i.e. it preserves ωSup
cont : ∀ {Monotone' : Monotone ↑toOrderHom}, OmegaCompletePartialOrder.Continuous { toFun := ↑toOrderHom, monotone' := Monotone' }

A monotone function on ω-continuous partial orders is said to be continuous if for every chain c : chain α, f (⊔ i, c i) = ⊔ i, f (c i). This is just the bundled version of OrderHom.continuous.

Instances For

def OmegaCompletePartialOrder.«term_→𝒄_» :

Lean.TrailingParserDescr

A monotone function on ω-continuous partial orders is said to be continuous if for every chain c : chain α, f (⊔ i, c i) = ⊔ i, f (c i). This is just the bundled version of OrderHom.continuous.

Equations

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

todo: should we make this a OrderHomClass instead of a CoeFun?

instance OmegaCompletePartialOrder.instCoeFunContinuousHomForAll (α : Type u) (β : Type v) [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] :

CoeFun (α →𝒄 β) fun x => α → β

Equations

OmegaCompletePartialOrder.instCoeFunContinuousHomForAll α β = { coe := fun f => ↑f.toOrderHom }

instance OmegaCompletePartialOrder.instCoeContinuousHomOrderHomToPreorderToPartialOrderToPreorderToPartialOrder (α : Type u) (β : Type v) [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] :

Coe (α →𝒄 β) (α →o β)

Equations

OmegaCompletePartialOrder.instCoeContinuousHomOrderHomToPreorderToPartialOrderToPreorderToPartialOrder α β = { coe := OmegaCompletePartialOrder.ContinuousHom.toOrderHom }

instance OmegaCompletePartialOrder.instPartialOrderContinuousHom (α : Type u) (β : Type v) [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] :

PartialOrder (α →𝒄 β)

Equations

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

def OmegaCompletePartialOrder.ContinuousHom.Simps.apply {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (h : α →𝒄 β) :

α → β

See Note [custom simps projection]. We specify this explicitly because we don't have a FunLike instance.

Equations

OmegaCompletePartialOrder.ContinuousHom.Simps.apply h = ↑h.toOrderHom

theorem OmegaCompletePartialOrder.ContinuousHom.congr_fun {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] {f : α →𝒄 β} {g : α →𝒄 β} (h : f = g) (x : α) :

↑f.toOrderHom x = ↑g.toOrderHom x

theorem OmegaCompletePartialOrder.ContinuousHom.congr_arg {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (f : α →𝒄 β) {x : α} {y : α} (h : x = y) :

↑f.toOrderHom x = ↑f.toOrderHom y

theorem OmegaCompletePartialOrder.ContinuousHom.monotone {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (f : α →𝒄 β) :

Monotone ↑f.toOrderHom

theorem OmegaCompletePartialOrder.ContinuousHom.apply_mono {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] {f : α →𝒄 β} {g : α →𝒄 β} {x : α} {y : α} (h₁ : f ≤ g) (h₂ : x ≤ y) :

↑f.toOrderHom x ≤ ↑g.toOrderHom y

theorem OmegaCompletePartialOrder.ContinuousHom.ite_continuous' {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] {p : Prop} [hp : Decidable p] (f : α → β) (g : α → β) (hf : OmegaCompletePartialOrder.Continuous' f) (hg : OmegaCompletePartialOrder.Continuous' g) :

OmegaCompletePartialOrder.Continuous' fun x => if p then f x else g x

theorem OmegaCompletePartialOrder.ContinuousHom.ωSup_bind {α : Type u} [inst : OmegaCompletePartialOrder α] {β : Type v} {γ : Type v} (c : OmegaCompletePartialOrder.Chain α) (f : α →o Part β) (g : α →o β → Part γ) :

OmegaCompletePartialOrder.ωSup (OmegaCompletePartialOrder.Chain.map c (OrderHom.bind f g)) = OmegaCompletePartialOrder.ωSup (OmegaCompletePartialOrder.Chain.map c f) >>= OmegaCompletePartialOrder.ωSup (OmegaCompletePartialOrder.Chain.map c g)

theorem OmegaCompletePartialOrder.ContinuousHom.bind_continuous' {α : Type u} [inst : OmegaCompletePartialOrder α] {β : Type v} {γ : Type v} (f : α → Part β) (g : α → β → Part γ) :

OmegaCompletePartialOrder.Continuous' f → OmegaCompletePartialOrder.Continuous' g → OmegaCompletePartialOrder.Continuous' fun x => f x >>= g x

theorem OmegaCompletePartialOrder.ContinuousHom.map_continuous' {α : Type u} [inst : OmegaCompletePartialOrder α] {β : Type v} {γ : Type v} (f : β → γ) (g : α → Part β) (hg : OmegaCompletePartialOrder.Continuous' g) :

OmegaCompletePartialOrder.Continuous' fun x => f <$> g x

theorem OmegaCompletePartialOrder.ContinuousHom.seq_continuous' {α : Type u} [inst : OmegaCompletePartialOrder α] {β : Type v} {γ : Type v} (f : α → Part (β → γ)) (g : α → Part β) (hf : OmegaCompletePartialOrder.Continuous' f) (hg : OmegaCompletePartialOrder.Continuous' g) :

OmegaCompletePartialOrder.Continuous' fun x => Seq.seq (f x) fun x_1 => g x

theorem OmegaCompletePartialOrder.ContinuousHom.continuous {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (F : α →𝒄 β) (C : OmegaCompletePartialOrder.Chain α) :

↑F.toOrderHom (OmegaCompletePartialOrder.ωSup C) = OmegaCompletePartialOrder.ωSup (OmegaCompletePartialOrder.Chain.map C F.toOrderHom)

def OmegaCompletePartialOrder.ContinuousHom.ofFun {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (f : α → β) (g : α →𝒄 β) (h : f = ↑g.toOrderHom) :

Construct a continuous function from a bare function, a continuous function, and a proof that they are equal.

Equations

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

@[simp]

theorem OmegaCompletePartialOrder.ContinuousHom.ofMono_toOrderHom {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (f : α →o β) (h : ∀ (c : OmegaCompletePartialOrder.Chain α), ↑f (OmegaCompletePartialOrder.ωSup c) = OmegaCompletePartialOrder.ωSup (OmegaCompletePartialOrder.Chain.map c f)) :

(OmegaCompletePartialOrder.ContinuousHom.ofMono f h).toOrderHom = f

def OmegaCompletePartialOrder.ContinuousHom.ofMono {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (f : α →o β) (h : ∀ (c : OmegaCompletePartialOrder.Chain α), ↑f (OmegaCompletePartialOrder.ωSup c) = OmegaCompletePartialOrder.ωSup (OmegaCompletePartialOrder.Chain.map c f)) :

Construct a continuous function from a monotone function with a proof of continuity.

Equations

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

@[simp]

theorem OmegaCompletePartialOrder.ContinuousHom.id_apply {α : Type u} [inst : OmegaCompletePartialOrder α] (a : α) :

↑OmegaCompletePartialOrder.ContinuousHom.id.toOrderHom a = a

def OmegaCompletePartialOrder.ContinuousHom.id {α : Type u} [inst : OmegaCompletePartialOrder α] :

The identity as a continuous function.

Equations

OmegaCompletePartialOrder.ContinuousHom.id = OmegaCompletePartialOrder.ContinuousHom.ofMono OrderHom.id (_ : OmegaCompletePartialOrder.Continuous OrderHom.id)

@[simp]

theorem OmegaCompletePartialOrder.ContinuousHom.comp_apply {α : Type u} {β : Type v} {γ : Type u_1} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] [inst : OmegaCompletePartialOrder γ] (f : β →𝒄 γ) (g : α →𝒄 β) :

∀ (a : α), ↑(OmegaCompletePartialOrder.ContinuousHom.comp f g).toOrderHom a = ↑f.toOrderHom (↑g.toOrderHom a)

def OmegaCompletePartialOrder.ContinuousHom.comp {α : Type u} {β : Type v} {γ : Type u_1} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] [inst : OmegaCompletePartialOrder γ] (f : β →𝒄 γ) (g : α →𝒄 β) :

The composition of continuous functions.

Equations

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

theorem OmegaCompletePartialOrder.ContinuousHom.ext {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (f : α →𝒄 β) (g : α →𝒄 β) (h : ∀ (x : α), ↑f.toOrderHom x = ↑g.toOrderHom x) :

f = g

theorem OmegaCompletePartialOrder.ContinuousHom.coe_inj {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (f : α →𝒄 β) (g : α →𝒄 β) (h : ↑f.toOrderHom = ↑g.toOrderHom) :

f = g

@[simp]

theorem OmegaCompletePartialOrder.ContinuousHom.comp_id {β : Type v} {γ : Type u_1} [inst : OmegaCompletePartialOrder β] [inst : OmegaCompletePartialOrder γ] (f : β →𝒄 γ) :

OmegaCompletePartialOrder.ContinuousHom.comp f OmegaCompletePartialOrder.ContinuousHom.id = f

@[simp]

theorem OmegaCompletePartialOrder.ContinuousHom.id_comp {β : Type v} {γ : Type u_1} [inst : OmegaCompletePartialOrder β] [inst : OmegaCompletePartialOrder γ] (f : β →𝒄 γ) :

OmegaCompletePartialOrder.ContinuousHom.comp OmegaCompletePartialOrder.ContinuousHom.id f = f

@[simp]

theorem OmegaCompletePartialOrder.ContinuousHom.comp_assoc {α : Type u} {β : Type v} {γ : Type u_1} {φ : Type u_2} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] [inst : OmegaCompletePartialOrder γ] [inst : OmegaCompletePartialOrder φ] (f : γ →𝒄 φ) (g : β →𝒄 γ) (h : α →𝒄 β) :

OmegaCompletePartialOrder.ContinuousHom.comp f (OmegaCompletePartialOrder.ContinuousHom.comp g h) = OmegaCompletePartialOrder.ContinuousHom.comp (OmegaCompletePartialOrder.ContinuousHom.comp f g) h

def OmegaCompletePartialOrder.ContinuousHom.const {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (x : β) :

Function.const is a continuous function.

Equations

OmegaCompletePartialOrder.ContinuousHom.const x = OmegaCompletePartialOrder.ContinuousHom.ofMono (↑(OrderHom.const α) x) (_ : OmegaCompletePartialOrder.Continuous (↑(OrderHom.const α) x))

@[simp]

theorem OmegaCompletePartialOrder.ContinuousHom.const_apply {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (f : β) (a : α) :

↑(OmegaCompletePartialOrder.ContinuousHom.const f).toOrderHom a = f

instance OmegaCompletePartialOrder.ContinuousHom.instInhabitedContinuousHom {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] [inst : Inhabited β] :

Inhabited (α →𝒄 β)

Equations

OmegaCompletePartialOrder.ContinuousHom.instInhabitedContinuousHom = { default := OmegaCompletePartialOrder.ContinuousHom.const default }

@[simp]

theorem OmegaCompletePartialOrder.ContinuousHom.toMono_coe {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (f : α →𝒄 β) :

↑OmegaCompletePartialOrder.ContinuousHom.toMono f = f.toOrderHom

def OmegaCompletePartialOrder.ContinuousHom.toMono {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] :

(α →𝒄 β) →o α →o β

The map from continuous functions to monotone functions is itself a monotone function.

Equations

OmegaCompletePartialOrder.ContinuousHom.toMono = { toFun := fun f => f.toOrderHom, monotone' := (_ : ∀ (x x_1 : α →𝒄 β), x ≤ x_1 → x ≤ x_1) }

@[simp]

theorem OmegaCompletePartialOrder.ContinuousHom.forall_forall_merge {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (c₀ : OmegaCompletePartialOrder.Chain (α →𝒄 β)) (c₁ : OmegaCompletePartialOrder.Chain α) (z : β) :

(∀ (i j : ℕ), ↑(↑c₀ i).toOrderHom (↑c₁ j) ≤ z) ↔ ∀ (i : ℕ), ↑(↑c₀ i).toOrderHom (↑c₁ i) ≤ z

When proving that a chain of applications is below a bound z, it suffices to consider the functions and values being selected from the same index in the chains.

This lemma is more specific than necessary, i.e. c₀ only needs to be a chain of monotone functions, but it is only used with continuous functions.

@[simp]

theorem OmegaCompletePartialOrder.ContinuousHom.forall_forall_merge' {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (c₀ : OmegaCompletePartialOrder.Chain (α →𝒄 β)) (c₁ : OmegaCompletePartialOrder.Chain α) (z : β) :

(∀ (j i : ℕ), ↑(↑c₀ i).toOrderHom (↑c₁ j) ≤ z) ↔ ∀ (i : ℕ), ↑(↑c₀ i).toOrderHom (↑c₁ i) ≤ z

@[simp]

theorem OmegaCompletePartialOrder.ContinuousHom.ωSup_apply {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (c : OmegaCompletePartialOrder.Chain (α →𝒄 β)) (a : α) :

↑(OmegaCompletePartialOrder.ContinuousHom.ωSup c).toOrderHom a = OmegaCompletePartialOrder.ωSup (OmegaCompletePartialOrder.Chain.map (OmegaCompletePartialOrder.Chain.map c OmegaCompletePartialOrder.ContinuousHom.toMono) (OrderHom.apply a))

def OmegaCompletePartialOrder.ContinuousHom.ωSup {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (c : OmegaCompletePartialOrder.Chain (α →𝒄 β)) :

The ωSup operator for continuous functions, which takes the pointwise countable supremum of the functions in the ω-chain.

Equations

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

@[simp]

theorem OmegaCompletePartialOrder.ContinuousHom.instOmegaCompletePartialOrderContinuousHom_ωSup {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (c : OmegaCompletePartialOrder.Chain (α →𝒄 β)) :

OmegaCompletePartialOrder.ωSup c = OmegaCompletePartialOrder.ContinuousHom.ωSup c

instance OmegaCompletePartialOrder.ContinuousHom.instOmegaCompletePartialOrderContinuousHom {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] :

OmegaCompletePartialOrder (α →𝒄 β)

Equations

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

@[simp]

theorem OmegaCompletePartialOrder.ContinuousHom.Prod.apply_apply {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (f : (α →𝒄 β) × α) :

↑OmegaCompletePartialOrder.ContinuousHom.Prod.apply.toOrderHom f = ↑f.fst.toOrderHom f.snd

def OmegaCompletePartialOrder.ContinuousHom.Prod.apply {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] :

(α →𝒄 β) × α →𝒄 β

The application of continuous functions as a continuous function.

Equations

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

theorem OmegaCompletePartialOrder.ContinuousHom.ωSup_def {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (c : OmegaCompletePartialOrder.Chain (α →𝒄 β)) (x : α) :

↑(OmegaCompletePartialOrder.ωSup c).toOrderHom x = ↑(OmegaCompletePartialOrder.ContinuousHom.ωSup c).toOrderHom x

theorem OmegaCompletePartialOrder.ContinuousHom.ωSup_apply_ωSup {α : Type u} {β : Type v} [inst : OmegaCompletePartialOrder α] [inst : OmegaCompletePartialOrder β] (c₀ : OmegaCompletePartialOrder.Chain (α →𝒄 β)) (c₁ : OmegaCompletePartialOrder.Chain α) :

↑(OmegaCompletePartialOrder.ωSup c₀).toOrderHom (OmegaCompletePartialOrder.ωSup c₁) = ↑OmegaCompletePartialOrder.ContinuousHom.Prod.apply.toOrderHom (OmegaCompletePartialOrder.ωSup (OmegaCompletePartialOrder.Chain.zip c₀ c₁))

@[simp]

theorem OmegaCompletePartialOrder.ContinuousHom.flip_apply {β : Type v} {γ : Type u_1} [inst : OmegaCompletePartialOrder β] [inst : OmegaCompletePartialOrder γ] {α : Type u_2} (f : α → β →𝒄 γ) (x : β) (y : α) :

↑(OmegaCompletePartialOrder.ContinuousHom.flip f).toOrderHom x y = ↑(f y).toOrderHom x

def OmegaCompletePartialOrder.ContinuousHom.flip {β : Type v} {γ : Type u_1} [inst : OmegaCompletePartialOrder β] [inst : OmegaCompletePartialOrder γ] {α : Type u_2} (f : α → β →𝒄 γ) :

β →𝒄 α → γ

A family of continuous functions yields a continuous family of functions.

Equations

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

@[simp]

theorem OmegaCompletePartialOrder.ContinuousHom.bind_apply_Dom {α : Type u} [inst : OmegaCompletePartialOrder α] {β : Type v} {γ : Type v} (f : α →𝒄 Part β) (g : α →𝒄 β → Part γ) (x : α) :

(↑(OmegaCompletePartialOrder.ContinuousHom.bind f g).toOrderHom x).Dom = ∃ h, (↑g.toOrderHom x (Part.get (↑f.toOrderHom x) h)).Dom

@[simp]

theorem OmegaCompletePartialOrder.ContinuousHom.bind_apply_get {α : Type u} [inst : OmegaCompletePartialOrder α] {β : Type v} {γ : Type v} (f : α →𝒄 Part β) (g : α →𝒄 β → Part γ) (x : α) (ha : ∃ h, ((fun b => ↑g.toOrderHom x (Part.get (↑f.toOrderHom x) b)) h).Dom) :

Part.get (↑(OmegaCompletePartialOrder.ContinuousHom.bind f g).toOrderHom x) ha = Part.get (↑g.toOrderHom x (Part.get (↑f.toOrderHom x) (_ : (↑f.toOrderHom x).Dom))) (_ : (↑g.toOrderHom x (Part.get (↑f.toOrderHom x) (_ : (↑f.toOrderHom x).Dom))).Dom)

noncomputable def OmegaCompletePartialOrder.ContinuousHom.bind {α : Type u} [inst : OmegaCompletePartialOrder α] {β : Type v} {γ : Type v} (f : α →𝒄 Part β) (g : α →𝒄 β → Part γ) :

α →𝒄 Part γ

Part.bind as a continuous function.

Equations

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

@[simp]

theorem OmegaCompletePartialOrder.ContinuousHom.map_apply {α : Type u} [inst : OmegaCompletePartialOrder α] {β : Type v} {γ : Type v} (f : β → γ) (g : α →𝒄 Part β) (x : α) :

↑(OmegaCompletePartialOrder.ContinuousHom.map f g).toOrderHom x = f <$> ↑g.toOrderHom x

noncomputable def OmegaCompletePartialOrder.ContinuousHom.map {α : Type u} [inst : OmegaCompletePartialOrder α] {β : Type v} {γ : Type v} (f : β → γ) (g : α →𝒄 Part β) :

α →𝒄 Part γ

Part.map as a continuous function.

Equations

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

@[simp]

theorem OmegaCompletePartialOrder.ContinuousHom.seq_apply {α : Type u} [inst : OmegaCompletePartialOrder α] {β : Type v} {γ : Type v} (f : α →𝒄 Part (β → γ)) (g : α →𝒄 Part β) (x : α) :

↑(OmegaCompletePartialOrder.ContinuousHom.seq f g).toOrderHom x = Seq.seq (↑f.toOrderHom x) fun x => ↑g.toOrderHom x

noncomputable def OmegaCompletePartialOrder.ContinuousHom.seq {α : Type u} [inst : OmegaCompletePartialOrder α] {β : Type v} {γ : Type v} (f : α →𝒄 Part (β → γ)) (g : α →𝒄 Part β) :

α →𝒄 Part γ

Part.seq as a continuous function.

Equations

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