Arithmetic on OrderTypes #
We define addition and multiplication of OrderTypes, the isomorphism classes of linear orders,
via the lexicographic sum and the lexicographic product. These make OrderType into a monoid.
We also define the cardinality of an order type.
Note that, as for ordinals, multiplication is "reversed": type α * type β := type (Lex (β × α))
(see OrderType.type_lex_prod).
Main definitions #
OrderType.card o: the cardinality of an OrderTypeo.o₁ + o₂: the lexicographic sum of order types, which forms anAddMonoid.o₁ * o₂: the lexicographic product of order types, which forms aMonoidWithZero.
Notation #
The following are notations in the OrderType namespace:
ηis a notation for the order type ofℚwith its natural order.θis a notation for the order type ofℝwith its natural order.
References #
- https://en.wikipedia.org/wiki/Order_type
- Dauben, J. W., Georg Cantor: His Mathematics and Philosophy of the Infinite. Princeton, NJ: Princeton University Press, 1990.
- Enderton, Herbert B., Elements of Set Theory. United Kingdom: Academic Press, 1977.
Tags #
order type, order isomorphism, linear order
Equations
- One or more equations did not get rendered due to their size.
Equations
- OrderType.instAdd = { add := fun (o₁ o₂ : OrderType.{?u.1}) => o₁ + o₂ }
Equations
- One or more equations did not get rendered due to their size.
Equations
- One or more equations did not get rendered due to their size.
Equations
- OrderType.instMul = { mul := fun (o₁ o₂ : OrderType.{?u.1}) => o₁ * o₂ }
Equations
- One or more equations did not get rendered due to their size.
The cardinal of an OrderType is the cardinality of any type on which a relation
with that order type is defined.
Equations
- o.card = o.liftOn (fun (α : Type ?u.1) (x : LinearOrder α) => Cardinal.mk α) OrderType.card._proof_1✝
Instances For
Equations
- OrderType.instOfNat n = { ofNat := OrderType.type (Fin n) }
The order type of the rational numbers.
Conventions for notations in identifiers:
- The recommended spelling of
ηin identifiers iseta.
Equations
Instances For
The order type of the real numbers.
Conventions for notations in identifiers:
- The recommended spelling of
θin identifiers istheta.
Equations
Instances For
The order type of the rational numbers.
Conventions for notations in identifiers:
- The recommended spelling of
ηin identifiers iseta.
Equations
- OrderType.termη = Lean.ParserDescr.node `OrderType.termη 1024 (Lean.ParserDescr.symbol "η")
Instances For
The order type of the real numbers.
Conventions for notations in identifiers:
- The recommended spelling of
θin identifiers istheta.
Equations
- OrderType.termθ = Lean.ParserDescr.node `OrderType.termθ 1024 (Lean.ParserDescr.symbol "θ")