mathlibdocumentation

order.galois_connection

Galois connections, insertions and coinsertions #

Galois connections are order theoretic adjoints, i.e. a pair of functions u and l, such that ∀ a b, l a ≤ b ↔ a ≤ u b.

Main definitions #

• galois_connection: A Galois connection is a pair of functions l and u satisfying l a ≤ b ↔ a ≤ u b. They are special cases of adjoint functors in category theory, but do not depend on the category theory library in mathlib.
• galois_insertion: A Galois insertion is a Galois connection where l ∘ u = id
• galois_coinsertion: A Galois coinsertion is a Galois connection where u ∘ l = id

Implementation details #

Galois insertions can be used to lift order structures from one type to another. For example if α is a complete lattice, and l : α → β, and u : β → α form a Galois insertion, then β is also a complete lattice. l is the lower adjoint and u is the upper adjoint.

An example of a Galois insertion is in group theory. If G is a group, then there is a Galois insertion between the set of subsets of G, set G, and the set of subgroups of G, subgroup G. The lower adjoint is subgroup.closure, taking the subgroup generated by a set, and the upper adjoint is the coercion from subgroup G to set G, taking the underlying set of a subgroup.

Naively lifting a lattice structure along this Galois insertion would mean that the definition of inf on subgroups would be subgroup.closure (↑S ∩ ↑T). This is an undesirable definition because the intersection of subgroups is already a subgroup, so there is no need to take the closure. For this reason a choice function is added as a field to the galois_insertion structure. It has type Π S : set G, ↑(closure S) ≤ S → subgroup G. When ↑(closure S) ≤ S, then S is already a subgroup, so this function can be defined using subgroup.mk and not closure. This means the infimum of subgroups will be defined to be the intersection of sets, paired with a proof that intersection of subgroups is a subgroup, rather than the closure of the intersection.

def galois_connection {α : Type u} {β : Type v} [preorder α] [preorder β] (l : α → β) (u : β → α) :
Prop

A Galois connection is a pair of functions l and u satisfying l a ≤ b ↔ a ≤ u b. They are special cases of adjoint functors in category theory, but do not depend on the category theory library in mathlib.

Equations
• = ∀ (a : α) (b : β), l a b a u b
theorem order_iso.to_galois_connection {α : Type u} {β : Type v} [preorder α] [preorder β] (oi : α ≃o β) :
(oi.symm)

Makes a Galois connection from an order-preserving bijection.

theorem galois_connection.monotone_intro {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} (hu : monotone u) (hl : monotone l) (hul : ∀ (a : α), a u (l a)) (hlu : ∀ (a : β), l (u a) a) :
@[protected]
theorem galois_connection.dual {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} (gc : u) :
theorem galois_connection.le_iff_le {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} (gc : u) {a : α} {b : β} :
l a b a u b
theorem galois_connection.l_le {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} (gc : u) {a : α} {b : β} :
a u bl a b
theorem galois_connection.le_u {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} (gc : u) {a : α} {b : β} :
l a ba u b
theorem galois_connection.le_u_l {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} (gc : u) (a : α) :
a u (l a)
theorem galois_connection.l_u_le {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} (gc : u) (a : β) :
l (u a) a
theorem galois_connection.monotone_u {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} (gc : u) :
theorem galois_connection.monotone_l {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} (gc : u) :
theorem galois_connection.upper_bounds_l_image {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} (gc : u) (s : set α) :
theorem galois_connection.lower_bounds_u_image {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} (gc : u) (s : set β) :
theorem galois_connection.bdd_above_l_image {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} (gc : u) {s : set α} :
theorem galois_connection.bdd_below_u_image {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} (gc : u) {s : set β} :
theorem galois_connection.is_lub_l_image {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} (gc : u) {s : set α} {a : α} (h : a) :
is_lub (l '' s) (l a)
theorem galois_connection.is_glb_u_image {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} (gc : u) {s : set β} {b : β} (h : b) :
is_glb (u '' s) (u b)
theorem galois_connection.is_least_l {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} (gc : u) {a : α} :
is_least {b : β | a u b} (l a)
theorem galois_connection.is_greatest_u {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} (gc : u) {b : β} :
is_greatest {a : α | l a b} (u b)
theorem galois_connection.is_glb_l {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} (gc : u) {a : α} :
is_glb {b : β | a u b} (l a)
theorem galois_connection.is_lub_u {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} (gc : u) {b : β} :
is_lub {a : α | l a b} (u b)
theorem galois_connection.le_u_l_trans {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} (gc : u) {x y z : α} (hxy : x u (l y)) (hyz : y u (l z)) :
x u (l z)

If (l, u) is a Galois connection, then the relation x ≤ u (l y) is a transitive relation. If l is a closure operator (submodule.span, subgroup.closure, ...) and u is the coercion to set, this reads as "if U is in the closure of V and V is in the closure of W then U is in the closure of W".

theorem galois_connection.l_u_le_trans {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} (gc : u) {x y z : β} (hxy : l (u x) y) (hyz : l (u y) z) :
l (u x) z
theorem galois_connection.u_l_u_eq_u {α : Type u} {β : Type v} [preorder β] {l : α → β} {u : β → α} (gc : u) (b : β) :
u (l (u b)) = u b
theorem galois_connection.u_l_u_eq_u' {α : Type u} {β : Type v} [preorder β] {l : α → β} {u : β → α} (gc : u) :
u l u = u
theorem galois_connection.u_unique {α : Type u} {β : Type v} [preorder β] {l : α → β} {u : β → α} (gc : u) {l' : α → β} {u' : β → α} (gc' : u') (hl : ∀ (a : α), l a = l' a) {b : β} :
u b = u' b
theorem galois_connection.exists_eq_u {α : Type u} {β : Type v} [preorder β] {l : α → β} {u : β → α} (gc : u) (a : α) :
(∃ (b : β), a = u b) a = u (l a)

If there exists a b such that a = u a, then b = l a is one such element.

theorem galois_connection.u_eq {α : Type u} {β : Type v} [preorder β] {l : α → β} {u : β → α} (gc : u) {z : α} {y : β} :
u y = z ∀ (x : α), x z l x y
theorem galois_connection.l_u_l_eq_l {α : Type u} {β : Type v} [preorder α] {l : α → β} {u : β → α} (gc : u) (a : α) :
l (u (l a)) = l a
theorem galois_connection.l_u_l_eq_l' {α : Type u} {β : Type v} [preorder α] {l : α → β} {u : β → α} (gc : u) :
l u l = l
theorem galois_connection.l_unique {α : Type u} {β : Type v} [preorder α] {l : α → β} {u : β → α} (gc : u) {l' : α → β} {u' : β → α} (gc' : u') (hu : ∀ (b : β), u b = u' b) {a : α} :
l a = l' a
theorem galois_connection.exists_eq_l {α : Type u} {β : Type v} [preorder α] {l : α → β} {u : β → α} (gc : u) (b : β) :
(∃ (a : α), b = l a) b = l (u b)

If there exists an a such that b = l a, then a = u b is one such element.

theorem galois_connection.l_eq {α : Type u} {β : Type v} [preorder α] {l : α → β} {u : β → α} (gc : u) {x : α} {z : β} :
l x = z ∀ (y : β), z y x u y
theorem galois_connection.u_top {α : Type u} {β : Type v} [preorder β] [order_top α] [order_top β] {l : α → β} {u : β → α} (gc : u) :
theorem galois_connection.l_bot {α : Type u} {β : Type v} [preorder α] [order_bot α] [order_bot β] {l : α → β} {u : β → α} (gc : u) :
theorem galois_connection.l_sup {α : Type u} {β : Type v} {a₁ a₂ : α} {l : α → β} {u : β → α} (gc : u) :
l (a₁ a₂) = l a₁ l a₂
theorem galois_connection.u_inf {α : Type u} {β : Type v} {b₁ b₂ : β} {l : α → β} {u : β → α} (gc : u) :
u (b₁ b₂) = u b₁ u b₂
theorem galois_connection.l_supr {α : Type u} {β : Type v} {ι : Sort x} {l : α → β} {u : β → α} (gc : u) {f : ι → α} :
l (supr f) = ⨆ (i : ι), l (f i)
theorem galois_connection.l_supr₂ {α : Type u} {β : Type v} {ι : Sort x} {κ : ι → Sort u_1} {l : α → β} {u : β → α} (gc : u) {f : Π (i : ι), κ i → α} :
l (⨆ (i : ι) (j : κ i), f i j) = ⨆ (i : ι) (j : κ i), l (f i j)
theorem galois_connection.u_infi {α : Type u} {β : Type v} {ι : Sort x} {l : α → β} {u : β → α} (gc : u) {f : ι → β} :
u (infi f) = ⨅ (i : ι), u (f i)
theorem galois_connection.u_infi₂ {α : Type u} {β : Type v} {ι : Sort x} {κ : ι → Sort u_1} {l : α → β} {u : β → α} (gc : u) {f : Π (i : ι), κ i → β} :
u (⨅ (i : ι) (j : κ i), f i j) = ⨅ (i : ι) (j : κ i), u (f i j)
theorem galois_connection.l_Sup {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gc : u) {s : set α} :
l (has_Sup.Sup s) = ⨆ (a : α) (H : a s), l a
theorem galois_connection.u_Inf {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gc : u) {s : set β} :
u (has_Inf.Inf s) = ⨅ (a : β) (H : a s), u a
theorem galois_connection.lt_iff_lt {α : Type u} {β : Type v} [linear_order α] [linear_order β] {l : α → β} {u : β → α} (gc : u) {a : α} {b : β} :
b < l a u b < a
@[protected]
theorem galois_connection.id {α : Type u} [pα : preorder α] :
@[protected]
theorem galois_connection.compose {α : Type u} {β : Type v} {γ : Type w} [preorder α] [preorder β] [preorder γ] {l1 : α → β} {u1 : β → α} {l2 : β → γ} {u2 : γ → β} (gc1 : u1) (gc2 : u2) :
galois_connection (l2 l1) (u1 u2)
@[protected]
theorem galois_connection.dfun {ι : Type u} {α : ι → Type v} {β : ι → Type w} [Π (i : ι), preorder (α i)] [Π (i : ι), preorder (β i)] (l : Π (i : ι), α iβ i) (u : Π (i : ι), β iα i) (gc : ∀ (i : ι), galois_connection (l i) (u i)) :
galois_connection (λ (a : Π (i : ι), α i) (i : ι), l i (a i)) (λ (b : Π (i : ι), β i) (i : ι), u i (b i))
theorem galois_connection.l_comm_of_u_comm {X : Type u_1} [preorder X] {Y : Type u_2} [preorder Y] {Z : Type u_3} [preorder Z] {W : Type u_4} {lYX : X → Y} {uXY : Y → X} (hXY : uXY) {lWZ : Z → W} {uZW : W → Z} (hZW : uZW) {lWY : Y → W} {uYW : W → Y} (hWY : uYW) {lZX : X → Z} {uXZ : Z → X} (hXZ : uXZ) (h : ∀ (w : W), uXZ (uZW w) = uXY (uYW w)) {x : X} :
lWZ (lZX x) = lWY (lYX x)
theorem galois_connection.u_comm_of_l_comm {X : Type u_1} {Y : Type u_2} [preorder Y] {Z : Type u_3} [preorder Z] {W : Type u_4} [preorder W] {lYX : X → Y} {uXY : Y → X} (hXY : uXY) {lWZ : Z → W} {uZW : W → Z} (hZW : uZW) {lWY : Y → W} {uYW : W → Y} (hWY : uYW) {lZX : X → Z} {uXZ : Z → X} (hXZ : uXZ) (h : ∀ (x : X), lWZ (lZX x) = lWY (lYX x)) {w : W} :
uXZ (uZW w) = uXY (uYW w)
theorem galois_connection.l_comm_iff_u_comm {X : Type u_1} {Y : Type u_2} [preorder Y] {Z : Type u_3} [preorder Z] {W : Type u_4} {lYX : X → Y} {uXY : Y → X} (hXY : uXY) {lWZ : Z → W} {uZW : W → Z} (hZW : uZW) {lWY : Y → W} {uYW : W → Y} (hWY : uYW) {lZX : X → Z} {uXZ : Z → X} (hXZ : uXZ) :
(∀ (w : W), uXZ (uZW w) = uXY (uYW w)) ∀ (x : X), lWZ (lZX x) = lWY (lYX x)
theorem Sup_image2_eq_Sup_Sup {α : Type u} {β : Type v} {γ : Type w} {s : set α} {t : set β} {l : α → β → γ} {u₁ : β → γ → α} {u₂ : α → γ → β} (h₁ : ∀ (b : β), (u₁ b)) (h₂ : ∀ (a : α), galois_connection (l a) (u₂ a)) :
theorem Sup_image2_eq_Sup_Inf {α : Type u} {β : Type v} {γ : Type w} {s : set α} {t : set β} {l : α → β → γ} {u₁ : β → γ → α} {u₂ : α → γ → β} (h₁ : ∀ (b : β), (u₁ b)) (h₂ : ∀ (a : α), (order_dual.to_dual u₂ a)) :
theorem Sup_image2_eq_Inf_Sup {α : Type u} {β : Type v} {γ : Type w} {s : set α} {t : set β} {l : α → β → γ} {u₁ : β → γ → α} {u₂ : α → γ → β} (h₁ : ∀ (b : β), ) (h₂ : ∀ (a : α), galois_connection (l a) (u₂ a)) :
theorem Sup_image2_eq_Inf_Inf {α : Type u} {β : Type v} {γ : Type w} {s : set α} {t : set β} {l : α → β → γ} {u₁ : β → γ → α} {u₂ : α → γ → β} (h₁ : ∀ (b : β), ) (h₂ : ∀ (a : α), (order_dual.to_dual u₂ a)) :
theorem Inf_image2_eq_Inf_Inf {α : Type u} {β : Type v} {γ : Type w} {s : set α} {t : set β} {u : α → β → γ} {l₁ : β → γ → α} {l₂ : α → γ → β} (h₁ : ∀ (b : β), galois_connection (l₁ b) b)) (h₂ : ∀ (a : α), galois_connection (l₂ a) (u a)) :
theorem Inf_image2_eq_Inf_Sup {α : Type u} {β : Type v} {γ : Type w} {s : set α} {t : set β} {u : α → β → γ} {l₁ : β → γ → α} {l₂ : α → γ → β} (h₁ : ∀ (b : β), galois_connection (l₁ b) b)) (h₂ : ∀ (a : α), (u a order_dual.of_dual)) :
theorem Inf_image2_eq_Sup_Inf {α : Type u} {β : Type v} {γ : Type w} {s : set α} {t : set β} {u : α → β → γ} {l₁ : β → γ → α} {l₂ : α → γ → β} (h₁ : ∀ (b : β), ) (h₂ : ∀ (a : α), galois_connection (l₂ a) (u a)) :
theorem Inf_image2_eq_Sup_Sup {α : Type u} {β : Type v} {γ : Type w} {s : set α} {t : set β} {u : α → β → γ} {l₁ : β → γ → α} {l₂ : α → γ → β} (h₁ : ∀ (b : β), ) (h₂ : ∀ (a : α), (u a order_dual.of_dual)) :
@[simp]
theorem order_iso.bdd_above_image {α : Type u} {β : Type v} [preorder α] [preorder β] (e : α ≃o β) {s : set α} :
@[simp]
theorem order_iso.bdd_below_image {α : Type u} {β : Type v} [preorder α] [preorder β] (e : α ≃o β) {s : set α} :
@[simp]
theorem order_iso.bdd_above_preimage {α : Type u} {β : Type v} [preorder α] [preorder β] (e : α ≃o β) {s : set β} :
@[simp]
theorem order_iso.bdd_below_preimage {α : Type u} {β : Type v} [preorder α] [preorder β] (e : α ≃o β) {s : set β} :
theorem nat.galois_connection_mul_div {k : } (h : 0 < k) :
galois_connection (λ (n : ), n * k) (λ (n : ), n / k)
@[nolint]
structure galois_insertion {α : Type u_2} {β : Type u_3} [preorder α] [preorder β] (l : α → β) (u : β → α) :
Type (max u_2 u_3)
• choice : Π (x : α), u (l x) x → β
• gc :
• le_l_u : ∀ (x : β), x l (u x)
• choice_eq : ∀ (a : α) (h : u (l a) a), self.choice a h = l a

A Galois insertion is a Galois connection where l ∘ u = id. It also contains a constructive choice function, to give better definitional equalities when lifting order structures. Dual to galois_coinsertion

Instances for galois_insertion
• galois_insertion.has_sizeof_inst
def galois_insertion.monotone_intro {α : Type u_1} {β : Type u_2} [preorder α] [preorder β] {l : α → β} {u : β → α} (hu : monotone u) (hl : monotone l) (hul : ∀ (a : α), a u (l a)) (hlu : ∀ (b : β), l (u b) = b) :

A constructor for a Galois insertion with the trivial choice function.

Equations
@[protected]
def order_iso.to_galois_insertion {α : Type u} {β : Type v} [preorder α] [preorder β] (oi : α ≃o β) :
(oi.symm)

Makes a Galois insertion from an order-preserving bijection.

Equations
def galois_connection.to_galois_insertion {α : Type u_1} {β : Type u_2} [preorder α] [preorder β] {l : α → β} {u : β → α} (gc : u) (h : ∀ (b : β), b l (u b)) :

Make a galois_insertion l u from a galois_connection l u such that ∀ b, b ≤ l (u b)

Equations
def galois_connection.lift_order_bot {α : Type u_1} {β : Type u_2} [preorder α] [order_bot α] {l : α → β} {u : β → α} (gc : u) :

Lift the bottom along a Galois connection

Equations
theorem galois_insertion.l_u_eq {α : Type u} {β : Type v} {l : α → β} {u : β → α} [preorder α] (gi : u) (b : β) :
l (u b) = b
theorem galois_insertion.left_inverse_l_u {α : Type u} {β : Type v} {l : α → β} {u : β → α} [preorder α] (gi : u) :
theorem galois_insertion.l_surjective {α : Type u} {β : Type v} {l : α → β} {u : β → α} [preorder α] (gi : u) :
theorem galois_insertion.u_injective {α : Type u} {β : Type v} {l : α → β} {u : β → α} [preorder α] (gi : u) :
theorem galois_insertion.l_sup_u {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) (a b : β) :
l (u a u b) = a b
theorem galois_insertion.l_supr_u {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) {ι : Sort x} (f : ι → β) :
l (⨆ (i : ι), u (f i)) = ⨆ (i : ι), f i
theorem galois_insertion.l_bsupr_u {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) {ι : Sort x} {p : ι → Prop} (f : Π (i : ι), p i → β) :
l (⨆ (i : ι) (hi : p i), u (f i hi)) = ⨆ (i : ι) (hi : p i), f i hi
theorem galois_insertion.l_Sup_u_image {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) (s : set β) :
l (has_Sup.Sup (u '' s)) =
theorem galois_insertion.l_inf_u {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) (a b : β) :
l (u a u b) = a b
theorem galois_insertion.l_infi_u {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) {ι : Sort x} (f : ι → β) :
l (⨅ (i : ι), u (f i)) = ⨅ (i : ι), f i
theorem galois_insertion.l_binfi_u {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) {ι : Sort x} {p : ι → Prop} (f : Π (i : ι), p i → β) :
l (⨅ (i : ι) (hi : p i), u (f i hi)) = ⨅ (i : ι) (hi : p i), f i hi
theorem galois_insertion.l_Inf_u_image {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) (s : set β) :
l (has_Inf.Inf (u '' s)) =
theorem galois_insertion.l_infi_of_ul_eq_self {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) {ι : Sort x} (f : ι → α) (hf : ∀ (i : ι), u (l (f i)) = f i) :
l (⨅ (i : ι), f i) = ⨅ (i : ι), l (f i)
theorem galois_insertion.l_binfi_of_ul_eq_self {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) {ι : Sort x} {p : ι → Prop} (f : Π (i : ι), p i → α) (hf : ∀ (i : ι) (hi : p i), u (l (f i hi)) = f i hi) :
l (⨅ (i : ι) (hi : p i), f i hi) = ⨅ (i : ι) (hi : p i), l (f i hi)
theorem galois_insertion.u_le_u_iff {α : Type u} {β : Type v} {l : α → β} {u : β → α} [preorder α] [preorder β] (gi : u) {a b : β} :
u a u b a b
theorem galois_insertion.strict_mono_u {α : Type u} {β : Type v} {l : α → β} {u : β → α} [preorder α] [preorder β] (gi : u) :
theorem galois_insertion.is_lub_of_u_image {α : Type u} {β : Type v} {l : α → β} {u : β → α} [preorder α] [preorder β] (gi : u) {s : set β} {a : α} (hs : is_lub (u '' s) a) :
(l a)
theorem galois_insertion.is_glb_of_u_image {α : Type u} {β : Type v} {l : α → β} {u : β → α} [preorder α] [preorder β] (gi : u) {s : set β} {a : α} (hs : is_glb (u '' s) a) :
(l a)
@[reducible]
def galois_insertion.lift_semilattice_sup {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) :

Lift the suprema along a Galois insertion

Equations
@[reducible]
def galois_insertion.lift_semilattice_inf {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) :

Lift the infima along a Galois insertion

Equations
@[reducible]
def galois_insertion.lift_lattice {α : Type u} {β : Type v} {l : α → β} {u : β → α} [lattice α] (gi : u) :

Lift the suprema and infima along a Galois insertion

Equations
@[reducible]
def galois_insertion.lift_order_top {α : Type u} {β : Type v} {l : α → β} {u : β → α} [preorder α] [order_top α] (gi : u) :

Lift the top along a Galois insertion

Equations
@[reducible]
def galois_insertion.lift_bounded_order {α : Type u} {β : Type v} {l : α → β} {u : β → α} [preorder α] (gi : u) :

Lift the top, bottom, suprema, and infima along a Galois insertion

Equations
@[reducible]
def galois_insertion.lift_complete_lattice {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) :

Lift all suprema and infima along a Galois insertion

Equations
@[nolint]
structure galois_coinsertion {α : Type u} {β : Type v} [preorder α] [preorder β] (l : α → β) (u : β → α) :
Type (max u v)
• choice : Π (x : β), x l (u x) → α
• gc :
• u_l_le : ∀ (x : α), u (l x) x
• choice_eq : ∀ (a : β) (h : a l (u a)), self.choice a h = u a

A Galois coinsertion is a Galois connection where u ∘ l = id. It also contains a constructive choice function, to give better definitional equalities when lifting order structures. Dual to galois_insertion

Instances for galois_coinsertion
• galois_coinsertion.has_sizeof_inst
def galois_coinsertion.dual {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} :

Make a galois_insertion between αᵒᵈ and βᵒᵈ from a galois_coinsertion between α and β.

Equations
def galois_insertion.dual {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} :

Make a galois_coinsertion between αᵒᵈ and βᵒᵈ from a galois_insertion between α and β.

Equations
def galois_coinsertion.of_dual {α : Type u} {β : Type v} [preorder α] [preorder β] {l : αᵒᵈ → βᵒᵈ} {u : βᵒᵈ → αᵒᵈ} :

Make a galois_insertion between α and β from a galois_coinsertion between αᵒᵈ and βᵒᵈ.

Equations
def galois_insertion.of_dual {α : Type u} {β : Type v} [preorder α] [preorder β] {l : αᵒᵈ → βᵒᵈ} {u : βᵒᵈ → αᵒᵈ} :

Make a galois_coinsertion between α and β from a galois_insertion between αᵒᵈ and βᵒᵈ.

Equations
@[protected]
def order_iso.to_galois_coinsertion {α : Type u} {β : Type v} [preorder α] [preorder β] (oi : α ≃o β) :
(oi.symm)

Makes a Galois coinsertion from an order-preserving bijection.

Equations
def galois_coinsertion.monotone_intro {α : Type u} {β : Type v} [preorder α] [preorder β] {l : α → β} {u : β → α} (hu : monotone u) (hl : monotone l) (hlu : ∀ (b : β), l (u b) b) (hul : ∀ (a : α), u (l a) = a) :

A constructor for a Galois coinsertion with the trivial choice function.

Equations
def galois_connection.to_galois_coinsertion {α : Type u_1} {β : Type u_2} [preorder α] [preorder β] {l : α → β} {u : β → α} (gc : u) (h : ∀ (a : α), u (l a) a) :

Make a galois_coinsertion l u from a galois_connection l u such that ∀ b, b ≤ l (u b)

Equations
def galois_connection.lift_order_top {α : Type u_1} {β : Type u_2} [preorder β] [order_top β] {l : α → β} {u : β → α} (gc : u) :

Lift the top along a Galois connection

Equations
theorem galois_coinsertion.u_l_eq {α : Type u} {β : Type v} {l : α → β} {u : β → α} [preorder β] (gi : u) (a : α) :
u (l a) = a
theorem galois_coinsertion.u_l_left_inverse {α : Type u} {β : Type v} {l : α → β} {u : β → α} [preorder β] (gi : u) :
theorem galois_coinsertion.u_surjective {α : Type u} {β : Type v} {l : α → β} {u : β → α} [preorder β] (gi : u) :
theorem galois_coinsertion.l_injective {α : Type u} {β : Type v} {l : α → β} {u : β → α} [preorder β] (gi : u) :
theorem galois_coinsertion.u_inf_l {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) (a b : α) :
u (l a l b) = a b
theorem galois_coinsertion.u_infi_l {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) {ι : Sort x} (f : ι → α) :
u (⨅ (i : ι), l (f i)) = ⨅ (i : ι), f i
theorem galois_coinsertion.u_Inf_l_image {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) (s : set α) :
u (has_Inf.Inf (l '' s)) =
theorem galois_coinsertion.u_sup_l {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) (a b : α) :
u (l a l b) = a b
theorem galois_coinsertion.u_supr_l {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) {ι : Sort x} (f : ι → α) :
u (⨆ (i : ι), l (f i)) = ⨆ (i : ι), f i
theorem galois_coinsertion.u_bsupr_l {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) {ι : Sort x} {p : ι → Prop} (f : Π (i : ι), p i → α) :
u (⨆ (i : ι) (hi : p i), l (f i hi)) = ⨆ (i : ι) (hi : p i), f i hi
theorem galois_coinsertion.u_Sup_l_image {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) (s : set α) :
u (has_Sup.Sup (l '' s)) =
theorem galois_coinsertion.u_supr_of_lu_eq_self {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) {ι : Sort x} (f : ι → β) (hf : ∀ (i : ι), l (u (f i)) = f i) :
u (⨆ (i : ι), f i) = ⨆ (i : ι), u (f i)
theorem galois_coinsertion.u_bsupr_of_lu_eq_self {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) {ι : Sort x} {p : ι → Prop} (f : Π (i : ι), p i → β) (hf : ∀ (i : ι) (hi : p i), l (u (f i hi)) = f i hi) :
u (⨆ (i : ι) (hi : p i), f i hi) = ⨆ (i : ι) (hi : p i), u (f i hi)
theorem galois_coinsertion.l_le_l_iff {α : Type u} {β : Type v} {l : α → β} {u : β → α} [preorder α] [preorder β] (gi : u) {a b : α} :
l a l b a b
theorem galois_coinsertion.strict_mono_l {α : Type u} {β : Type v} {l : α → β} {u : β → α} [preorder α] [preorder β] (gi : u) :
theorem galois_coinsertion.is_glb_of_l_image {α : Type u} {β : Type v} {l : α → β} {u : β → α} [preorder α] [preorder β] (gi : u) {s : set α} {a : β} (hs : is_glb (l '' s) a) :
(u a)
theorem galois_coinsertion.is_lub_of_l_image {α : Type u} {β : Type v} {l : α → β} {u : β → α} [preorder α] [preorder β] (gi : u) {s : set α} {a : β} (hs : is_lub (l '' s) a) :
(u a)
@[reducible]
def galois_coinsertion.lift_semilattice_inf {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) :

Lift the infima along a Galois coinsertion

Equations
@[reducible]
def galois_coinsertion.lift_semilattice_sup {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) :

Lift the suprema along a Galois coinsertion

Equations
@[reducible]
def galois_coinsertion.lift_lattice {α : Type u} {β : Type v} {l : α → β} {u : β → α} [lattice β] (gi : u) :

Lift the suprema and infima along a Galois coinsertion

Equations
@[reducible]
def galois_coinsertion.lift_order_bot {α : Type u} {β : Type v} {l : α → β} {u : β → α} [preorder β] [order_bot β] (gi : u) :

Lift the bot along a Galois coinsertion

Equations
@[reducible]
def galois_coinsertion.lift_bounded_order {α : Type u} {β : Type v} {l : α → β} {u : β → α} [preorder β] (gi : u) :

Lift the top, bottom, suprema, and infima along a Galois coinsertion

Equations
@[reducible]
def galois_coinsertion.lift_complete_lattice {α : Type u} {β : Type v} {l : α → β} {u : β → α} (gi : u) :

Lift all suprema and infima along a Galois coinsertion

Equations
def with_bot.gi_get_or_else_bot {α : Type u} [preorder α] [order_bot α] :

If α is a partial order with bottom element (e.g., ℕ, ℝ≥0), then λ o : with_bot α, o.get_or_else ⊥ and coercion form a Galois insertion.

Equations