nLab
order-type

Contents

Contents

Idea

The order type of a partially ordered set (poset) PP is an invariant ot(P)ot(P) of the poset which is finer than its cardinal number |P||P|. The cardinal numbers classify sets according to how many elements they contain, however they don’t pay attention to any potential order-theoretic properties on the sets in question – for example

ω+1ω\omega+1\cong\omega

in Set but not in Pos since the bijections in Set all send ω\omega to some finite ordinal and thusly don’t preserve ordering. This is expressed in terms of cardinalities and order types by observing that |ω+1|=|ω|=ω|\omega+1|=|\omega|=\omega but ot(ω+1)=ω+1ω=ot(ω)ot(\omega+1)=\omega+1\neq\omega=ot(\omega) since each ordinal is its own order type but generally not its own cardinal number.

Definition

Let PP be a poset. We say that another poset QQ has the same order type as PP iff there exists an order preserving bijection PQP\cong Q. We define an equivalence relation \sim on posets by

PQf:PQ(f is an order-preserving bijection)P\sim Q\iff \exists f:P\cong Q(\text{f is an order-preserving bijection}),

and we define the order type of PP, denoted ot(P)ot(P), to be either the equivalence class /P\sim/P or an arbitrary representative of the equivalence class /P\sim/P depending on context.

Examples

We have that ot(α)αot(\alpha)\cong\alpha in Pos for each ordinal α\alpha by definition, and further the order type of any well-ordered set ‘is’ the ordinal one would expect (up to iso):

ot({0,1,4,5})4,ot(\{0,1,4,5\})\cong4,
ot({0,2,4,6,ω,ω+2,ω+4,ω+6})ω+4,ot(\{0,2,4,6,\dots\omega,\omega+2,\omega+4,\omega+6\})\cong\omega+4,
\vdots

For well-ordered posets it seems natural to take the order type to be the ordinal representative of the equivalence class, yielding the literal equalities in the idea section above, however this is not strictly necessary.

The order type of the negative integers is denoted by *ω^*\omega and the order type of the rationals is denoted by η\eta, and neither of these order types have representatives in the ordinals since they aren’t well-ordered.

Discussion

The notion of cardinality for a set XX can be defined using the bijection equivalence relation \sim in Set

XYf:XYHom SetX\sim Y\iff \exists f:X\cong Y\in Hom_{Set},

so |X||X| is the cardinal number member of the equivalence class of all sets in bijection with XX. Since all sets are in bijection with some cardinal number (assuming the axiom of foundation via Scott’s trick) and cardinal numbers are just particular ordinals (assuming the axiom of choice, otherwise more care must be taken) we do not encounter the phenomenon above where some equivalence classes don’t have ordinal representatives in a universe with choice.

The order type equivalence relation \sim in Pos above is a finer parsing of the universe of partially ordered sets which doesn’t admit an ordinal in each of its equivalence classes, and each ordinal defines its own unique equivalence class under this relation instead of only the cardinal numbers as with the bijection equivalence relation.

The increased ‘fineness’ of this parsing can be attributed to the fact that we effectively restricted the iso equivalence relation in Set to the subcategory Pos where there are fewer isos between objects and thusly more equivalence classes.

References

Last revised on March 28, 2019 at 22:26:57. See the history of this page for a list of all contributions to it.