Orders on a sum type #
This file defines the disjoint sum and the linear (aka lexicographic) sum of two orders and provides
relation instances for sum.lift_rel
and sum.lex
.
We declare the disjoint sum of orders as the default set of instances. The linear order goes on a type synonym.
Main declarations #
sum.has_le
,sum.has_lt
: Disjoint sum of orders.sum.lex.has_le
,sum.lex.has_lt
: Lexicographic/linear sum of orders.
Notation #
α ⊕ₗ β
: The linear sum ofα
andβ
.
Unbundled relation classes #
theorem
sum.lift_rel.refl
{α : Type u_1}
{β : Type u_2}
(r : α → α → Prop)
(s : β → β → Prop)
[is_refl α r]
[is_refl β s]
(x : α ⊕ β) :
sum.lift_rel r s x x
@[protected, instance]
def
sum.lift_rel.is_refl
{α : Type u_1}
{β : Type u_2}
(r : α → α → Prop)
(s : β → β → Prop)
[is_refl α r]
[is_refl β s] :
is_refl (α ⊕ β) (sum.lift_rel r s)
@[protected, instance]
def
sum.lift_rel.is_irrefl
{α : Type u_1}
{β : Type u_2}
(r : α → α → Prop)
(s : β → β → Prop)
[is_irrefl α r]
[is_irrefl β s] :
is_irrefl (α ⊕ β) (sum.lift_rel r s)
theorem
sum.lift_rel.trans
{α : Type u_1}
{β : Type u_2}
(r : α → α → Prop)
(s : β → β → Prop)
[is_trans α r]
[is_trans β s]
{a b c : α ⊕ β} :
sum.lift_rel r s a b → sum.lift_rel r s b c → sum.lift_rel r s a c
@[protected, instance]
def
sum.lift_rel.is_trans
{α : Type u_1}
{β : Type u_2}
(r : α → α → Prop)
(s : β → β → Prop)
[is_trans α r]
[is_trans β s] :
is_trans (α ⊕ β) (sum.lift_rel r s)
@[protected, instance]
def
sum.lift_rel.is_antisymm
{α : Type u_1}
{β : Type u_2}
(r : α → α → Prop)
(s : β → β → Prop)
[is_antisymm α r]
[is_antisymm β s] :
is_antisymm (α ⊕ β) (sum.lift_rel r s)
@[protected, instance]
def
sum.lex.is_antisymm
{α : Type u_1}
{β : Type u_2}
(r : α → α → Prop)
(s : β → β → Prop)
[is_antisymm α r]
[is_antisymm β s] :
is_antisymm (α ⊕ β) (sum.lex r s)
@[protected, instance]
def
sum.lex.is_trichotomous
{α : Type u_1}
{β : Type u_2}
(r : α → α → Prop)
(s : β → β → Prop)
[is_trichotomous α r]
[is_trichotomous β s] :
is_trichotomous (α ⊕ β) (sum.lex r s)
@[protected, instance]
def
sum.lex.is_well_order
{α : Type u_1}
{β : Type u_2}
(r : α → α → Prop)
(s : β → β → Prop)
[is_well_order α r]
[is_well_order β s] :
is_well_order (α ⊕ β) (sum.lex r s)
Disjoint sum of two orders #
@[protected, instance]
Equations
@[protected, instance]
Equations
theorem
sum.le_def
{α : Type u_1}
{β : Type u_2}
[has_le α]
[has_le β]
{a b : α ⊕ β} :
a ≤ b ↔ sum.lift_rel has_le.le has_le.le a b
theorem
sum.lt_def
{α : Type u_1}
{β : Type u_2}
[has_lt α]
[has_lt β]
{a b : α ⊕ β} :
a < b ↔ sum.lift_rel has_lt.lt has_lt.lt a b
@[protected, instance]
Equations
- sum.preorder = {le := has_le.le sum.has_le, lt := has_lt.lt sum.has_lt, le_refl := _, le_trans := _, lt_iff_le_not_le := _}
@[protected, instance]
def
sum.partial_order
{α : Type u_1}
{β : Type u_2}
[partial_order α]
[partial_order β] :
partial_order (α ⊕ β)
Equations
- sum.partial_order = {le := preorder.le sum.preorder, lt := preorder.lt sum.preorder, le_refl := _, le_trans := _, lt_iff_le_not_le := _, le_antisymm := _}
@[protected, instance]
def
sum.no_min_order
{α : Type u_1}
{β : Type u_2}
[has_lt α]
[has_lt β]
[no_min_order α]
[no_min_order β] :
no_min_order (α ⊕ β)
@[protected, instance]
def
sum.no_max_order
{α : Type u_1}
{β : Type u_2}
[has_lt α]
[has_lt β]
[no_max_order α]
[no_max_order β] :
no_max_order (α ⊕ β)
@[simp]
theorem
sum.no_min_order_iff
{α : Type u_1}
{β : Type u_2}
[has_lt α]
[has_lt β] :
no_min_order (α ⊕ β) ↔ no_min_order α ∧ no_min_order β
@[simp]
theorem
sum.no_max_order_iff
{α : Type u_1}
{β : Type u_2}
[has_lt α]
[has_lt β] :
no_max_order (α ⊕ β) ↔ no_max_order α ∧ no_max_order β
@[protected, instance]
def
sum.densely_ordered
{α : Type u_1}
{β : Type u_2}
[has_lt α]
[has_lt β]
[densely_ordered α]
[densely_ordered β] :
densely_ordered (α ⊕ β)
@[simp]
theorem
sum.densely_ordered_iff
{α : Type u_1}
{β : Type u_2}
[has_lt α]
[has_lt β] :
densely_ordered (α ⊕ β) ↔ densely_ordered α ∧ densely_ordered β
Linear sum of two orders #
@[protected, instance]
Equations
- sum.lex.preorder = {le := has_le.le sum.lex.has_le, lt := has_lt.lt sum.lex.has_lt, le_refl := _, le_trans := _, lt_iff_le_not_le := _}
@[protected, instance]
def
sum.lex.partial_order
{α : Type u_1}
{β : Type u_2}
[partial_order α]
[partial_order β] :
partial_order (α ⊕ₗ β)
Equations
- sum.lex.partial_order = {le := preorder.le sum.lex.preorder, lt := preorder.lt sum.lex.preorder, le_refl := _, le_trans := _, lt_iff_le_not_le := _, le_antisymm := _}
@[protected, instance]
def
sum.lex.linear_order
{α : Type u_1}
{β : Type u_2}
[linear_order α]
[linear_order β] :
linear_order (α ⊕ₗ β)
Equations
- sum.lex.linear_order = {le := partial_order.le sum.lex.partial_order, lt := partial_order.lt sum.lex.partial_order, le_refl := _, le_trans := _, lt_iff_le_not_le := _, le_antisymm := _, le_total := _, decidable_le := sum.lex.decidable_rel (λ (a b : β), has_le.le.decidable a b), decidable_eq := sum.decidable_eq α β (λ (a b : β), eq.decidable a b), decidable_lt := decidable_lt_of_decidable_le sum.lex.decidable_rel, max := max_default (λ (a b : α ⊕ₗ β), sum.lex.decidable_rel a b), max_def := _, min := min_default (λ (a b : α ⊕ₗ β), sum.lex.decidable_rel a b), min_def := _}
@[protected, instance]
def
sum.lex.bounded_order
{α : Type u_1}
{β : Type u_2}
[has_le α]
[has_le β]
[order_bot α]
[order_top β] :
bounded_order (α ⊕ₗ β)
Equations
- sum.lex.bounded_order = {top := order_top.top sum.lex.order_top, le_top := _, bot := order_bot.bot sum.lex.order_bot, bot_le := _}
@[protected, instance]
def
sum.lex.no_min_order
{α : Type u_1}
{β : Type u_2}
[has_lt α]
[has_lt β]
[no_min_order α]
[no_min_order β] :
no_min_order (α ⊕ₗ β)
@[protected, instance]
def
sum.lex.no_max_order
{α : Type u_1}
{β : Type u_2}
[has_lt α]
[has_lt β]
[no_max_order α]
[no_max_order β] :
no_max_order (α ⊕ₗ β)
@[protected, instance]
def
sum.lex.no_min_order_of_nonempty
{α : Type u_1}
{β : Type u_2}
[has_lt α]
[has_lt β]
[no_min_order α]
[nonempty α] :
no_min_order (α ⊕ₗ β)
@[protected, instance]
def
sum.lex.no_max_order_of_nonempty
{α : Type u_1}
{β : Type u_2}
[has_lt α]
[has_lt β]
[no_max_order β]
[nonempty β] :
no_max_order (α ⊕ₗ β)
@[protected, instance]
def
sum.lex.densely_ordered_of_no_max_order
{α : Type u_1}
{β : Type u_2}
[has_lt α]
[has_lt β]
[densely_ordered α]
[densely_ordered β]
[no_max_order α] :
densely_ordered (α ⊕ₗ β)
@[protected, instance]
def
sum.lex.densely_ordered_of_no_min_order
{α : Type u_1}
{β : Type u_2}
[has_lt α]
[has_lt β]
[densely_ordered α]
[densely_ordered β]
[no_min_order β] :
densely_ordered (α ⊕ₗ β)
Order isomorphisms #
equiv.sum_comm
promoted to an order isomorphism.
Equations
- order_iso.sum_comm α β = {to_equiv := {to_fun := (equiv.sum_comm α β).to_fun, inv_fun := (equiv.sum_comm α β).inv_fun, left_inv := _, right_inv := _}, map_rel_iff' := _}
@[simp]
theorem
order_iso.sum_comm_apply
(α : Type u_1)
(β : Type u_2)
[has_le α]
[has_le β]
(ᾰ : α ⊕ β) :
⇑(order_iso.sum_comm α β) ᾰ = (equiv.sum_comm α β).to_fun ᾰ
@[simp]
theorem
order_iso.sum_comm_symm
(α : Type u_1)
(β : Type u_2)
[has_le α]
[has_le β] :
(order_iso.sum_comm α β).symm = order_iso.sum_comm β α
def
order_iso.sum_assoc
(α : Type u_1)
(β : Type u_2)
(γ : Type u_3)
[has_le α]
[has_le β]
[has_le γ] :
equiv.sum_assoc
promoted to an order isomorphism.
Equations
- order_iso.sum_assoc α β γ = {to_equiv := {to_fun := (equiv.sum_assoc α β γ).to_fun, inv_fun := (equiv.sum_assoc α β γ).inv_fun, left_inv := _, right_inv := _}, map_rel_iff' := _}
def
order_iso.sum_dual_distrib
(α : Type u_1)
(β : Type u_2)
[has_le α]
[has_le β] :
order_dual (α ⊕ β) ≃o order_dual α ⊕ order_dual β
order_dual
is distributive over ⊕
up to an order isomorphism.
Equations
- order_iso.sum_dual_distrib α β = {to_equiv := {to_fun := (equiv.refl (order_dual (α ⊕ β))).to_fun, inv_fun := (equiv.refl (order_dual (α ⊕ β))).inv_fun, left_inv := _, right_inv := _}, map_rel_iff' := _}
@[simp]
theorem
order_iso.sum_dual_distrib_inl
{α : Type u_1}
{β : Type u_2}
[has_le α]
[has_le β]
(a : α) :
⇑(order_iso.sum_dual_distrib α β) (⇑order_dual.to_dual (sum.inl a)) = sum.inl (⇑order_dual.to_dual a)
@[simp]
theorem
order_iso.sum_dual_distrib_inr
{α : Type u_1}
{β : Type u_2}
[has_le α]
[has_le β]
(b : β) :
⇑(order_iso.sum_dual_distrib α β) (⇑order_dual.to_dual (sum.inr b)) = sum.inr (⇑order_dual.to_dual b)
@[simp]
theorem
order_iso.sum_dual_distrib_symm_inl
{α : Type u_1}
{β : Type u_2}
[has_le α]
[has_le β]
(a : α) :
⇑((order_iso.sum_dual_distrib α β).symm) (sum.inl (⇑order_dual.to_dual a)) = ⇑order_dual.to_dual (sum.inl a)
@[simp]
theorem
order_iso.sum_dual_distrib_symm_inr
{α : Type u_1}
{β : Type u_2}
[has_le α]
[has_le β]
(b : β) :
⇑((order_iso.sum_dual_distrib α β).symm) (sum.inr (⇑order_dual.to_dual b)) = ⇑order_dual.to_dual (sum.inr b)
def
order_iso.sum_lex_assoc
(α : Type u_1)
(β : Type u_2)
(γ : Type u_3)
[has_le α]
[has_le β]
[has_le γ] :
equiv.sum_assoc
promoted to an order isomorphism.
Equations
- order_iso.sum_lex_assoc α β γ = {to_equiv := {to_fun := (equiv.sum_assoc α β γ).to_fun, inv_fun := (equiv.sum_assoc α β γ).inv_fun, left_inv := _, right_inv := _}, map_rel_iff' := _}
def
order_iso.sum_lex_dual_antidistrib
(α : Type u_1)
(β : Type u_2)
[has_le α]
[has_le β] :
order_dual (α ⊕ₗ β) ≃o order_dual β ⊕ₗ order_dual α
order_dual
is antidistributive over ⊕ₗ
up to an order isomorphism.
Equations
- order_iso.sum_lex_dual_antidistrib α β = {to_equiv := {to_fun := (equiv.sum_comm α β).to_fun, inv_fun := (equiv.sum_comm α β).inv_fun, left_inv := _, right_inv := _}, map_rel_iff' := _}
@[simp]
theorem
order_iso.sum_lex_dual_antidistrib_inl
{α : Type u_1}
{β : Type u_2}
[has_le α]
[has_le β]
(a : α) :
@[simp]
theorem
order_iso.sum_lex_dual_antidistrib_inr
{α : Type u_1}
{β : Type u_2}
[has_le α]
[has_le β]
(b : β) :
@[simp]
theorem
order_iso.sum_lex_dual_antidistrib_symm_inl
{α : Type u_1}
{β : Type u_2}
[has_le α]
[has_le β]
(b : β) :
⇑((order_iso.sum_lex_dual_antidistrib α β).symm) (sum.inl (⇑order_dual.to_dual b)) = ⇑order_dual.to_dual (sum.inr b)
@[simp]
theorem
order_iso.sum_lex_dual_antidistrib_symm_inr
{α : Type u_1}
{β : Type u_2}
[has_le α]
[has_le β]
(a : α) :
⇑((order_iso.sum_lex_dual_antidistrib α β).symm) (sum.inr (⇑order_dual.to_dual a)) = ⇑order_dual.to_dual (sum.inl a)