Order type

Order typeMain

Community hub

Order type

7 pages, 0 posts

0 subscribers

Recent from talks

Be the first to start a discussion here.

Recent from talks

Be the first to start a discussion here.

Contribute something

About hubMembersContent overviewUpdatesRules

Main reference articles

Order type

View on Wikipedia

from Wikipedia

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (February 2023) (Learn how and when to remove this message)

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.
Find sources: "Order type" – news · newspapers · books · scholar · JSTOR (March 2024)

In mathematics, especially in set theory, two ordered sets $X$ and $Y$ are said to have the same order type if they are order isomorphic, that is, if there exists a bijection (each element pairs with exactly one in the other set) $f\colon X\to Y$ such that both $f$ and its inverse are monotonic (preserving orders of elements).

In the special case when $X$ is totally ordered, monotonicity of $f$ already implies monotonicity of its inverse.

One and the same set may be equipped with different orders. Since order-equivalence is an equivalence relation, it partitions the class of all ordered sets into equivalence classes.

Notation

[edit]

If a set $X$ has order type denoted $\sigma$ , the order type of the reversed order, the dual of $X$ , is denoted $\sigma ^{*}$ .

The order type of a well-ordered set $X$ is sometimes expressed as $ord(X)$ .^[1]

Examples

[edit]

The order type of the integers and rationals is usually denoted $\pi$ and $\eta$ , respectively. The set of integers and the set of even integers have the same order type, because the mapping $n\mapsto 2n$ is a bijection that preserves the order. But the set of integers and the set of rational numbers (with the standard ordering) do not have the same order type, because even though the sets are of the same size (they are both countably infinite), there is no order-preserving bijective mapping between them. The open interval $(0, 1)$ of rationals is order isomorphic to the rationals, since, for example, $f(x)={\tfrac {2x-1}{1-\vert {2x-1}\vert }}$ is a strictly increasing bijection from the former to the latter. Relevant theorems of this sort are expanded upon below.

More examples can be given now: The set of positive integers (which has a least element), and that of negative integers (which has a greatest element). The natural numbers have order type denoted by ω, as explained below.

The rationals contained in the half-closed intervals [0,1) and (0,1], and the closed interval [0,1], are three additional order type examples.

Order type of well-orderings

[edit]

Every well-ordered set is order-equivalent to exactly one ordinal number, by definition. The ordinal numbers are taken to be the canonical representatives of their classes, and so the order type of a well-ordered set is usually identified with the corresponding ordinal. Order types thus often take the form of arithmetic expressions of ordinals.

Examples

[edit]

Firstly, the order type of the set of natural numbers is $ω$ . Any other model of Peano arithmetic, that is any non-standard model, starts with a segment isomorphic to ω but then adds extra numbers. For example, any countable such model has order type ω + (ω* + ω) ⋅ η.

Secondly, consider the set $V$ of even ordinals less than $ω \cdot 2 + 7$ :

V=\{0,2,4,\ldots ;\omega ,\omega +2,\omega +4,\ldots ;\omega \cdot 2,\omega \cdot 2+2,\omega \cdot 2+4,\omega \cdot 2+6\}.

As this comprises two separate counting sequences followed by four elements at the end, the order type is

\operatorname {ord} (V)=\omega \cdot 2+4=\{0,1,2,\ldots ;\omega ,\omega +1,\omega +2,\ldots ;\omega \cdot 2,\omega \cdot 2+1,\omega \cdot 2+2,\omega \cdot 2+3\},

Rational numbers

[edit]

With respect to their standard ordering as numbers, the set of rationals is not well-ordered. Neither is the completed set of reals, for that matter.

Any countable totally ordered set can be mapped injectively into the rational numbers in an order-preserving way. When the order is moreover dense and has no highest nor lowest element, there even exist a bijective such mapping.

External links

[edit]

Weisstein, Eric W. "Order Type". MathWorld.

References

[edit]

^ "Ordinal Numbers and Their Arithmetic". Archived from the original on 2009-10-27. Retrieved 2007-06-13.

v t e Order theory
Topics Glossary Category
Key concepts	Binary relation Boolean algebra Cyclic order Lattice Partial order Preorder Total order Weak ordering
Results	Boolean prime ideal theorem Cantor–Bernstein theorem Cantor's isomorphism theorem Dilworth's theorem Dushnik–Miller theorem Hausdorff maximal principle Knaster–Tarski theorem Kruskal's tree theorem Laver's theorem Mirsky's theorem Szpilrajn extension theorem Zorn's lemma
Properties & Types (list)	Antisymmetric Asymmetric Boolean algebra topics Completeness Connected Covering Dense Directed (Partial) Equivalence Foundational Heyting algebra Homogeneous Idempotent Lattice Bounded Complemented Complete Distributive Join and meet Reflexive Partial order Chain-complete Graded Eulerian Strict Prefix order Preorder Total Semilattice Semiorder Symmetric Total Tolerance Transitive Well-founded Well-quasi-ordering (Better) (Pre) Well-order
Constructions	Composition Converse/Transpose Lexicographic order Linear extension Product order Reflexive closure Series-parallel partial order Star product Symmetric closure Transitive closure
Topology & Orders	Alexandrov topology & Specialization preorder Ordered topological vector space Normal cone Order topology Order topology Topological vector lattice Banach Fréchet Locally convex Normed
Related	Antichain Cofinal Cofinality Comparability Graph Duality Filter Hasse diagram Ideal Net Subnet Order morphism Embedding Isomorphism Order type Ordered field Positive cone of an ordered field Ordered vector space Partially ordered Positive cone of an ordered vector space Riesz space Partially ordered group Positive cone of a partially ordered group Upper set Young's lattice

Revisions and contributors Edit on Wikipedia Read on Wikipedia

View on Grokipedia

from Grokipedia

In order theory, the order type of a totally ordered set (or linear order) is the equivalence class of all such sets that are order-isomorphic to it, providing a complete isomorphism-invariant classification of the set's linear ordering structure.^[1] This concept generalizes the notion of ordinal numbers, which specifically denote the order types of well-ordered sets, where every nonempty subset has a least element.^[1] Key examples illustrate the diversity of order types: the order type of the natural numbers under the standard ordering is denoted ω, the smallest infinite ordinal, while the order type of the rational numbers is η, a countable dense linear order without endpoints, meaning that between any two distinct elements there exists another.^[1]^[2] For finite sets, the order type coincides with the cardinal number, such as n for a chain of n elements.^[1] Order types can be combined via operations like ordinal addition, multiplication, and exponentiation for well-orders, or more generally through order sums and products for arbitrary linear orders.^[1] Beyond well-orders, order types encompass dense orders like the reals (λ), which are complete and Dedekind-complete, and scattered orders, which contain no dense suborders and can be decomposed into well-ordered components.^[2] The study of order types is foundational in set theory, topology, and model theory, enabling the analysis of embeddability (where one order type embeds into another if a realization of the first can be order-embedded into the second) and universality, such as the rationals being universal for all countable linear orders.^[2] Under the generalized continuum hypothesis, the number of distinct order types of cardinality ℵ_α is exactly ℵ_{α+1}.^[2]

Basic Concepts

Definition

A linearly ordered set, also known as a totally ordered set, is a set equipped with a binary relation that is reflexive, antisymmetric, transitive, and total, meaning that for any two distinct elements, one precedes the other. This structure ensures a complete linear arrangement of the elements without ties or incomparabilities. The order type of a linearly ordered set is defined as the equivalence class of all linearly ordered sets that are order-isomorphic to it, where two sets are order-isomorphic if there exists a bijective function between them that preserves the order relation.^[3] In other words, an order type captures the intrinsic ordering structure up to relabeling of elements, serving as an abstract invariant that classifies linearly ordered sets based on their relational properties rather than their specific elements. This concept enables the comparison and enumeration of orderings beyond mere size, distinguishing, for instance, different infinite arrangements. Order types function as a fundamental tool for categorizing and studying ordered structures in set theory and order theory, facilitating the analysis of properties like density, discreteness, or well-foundedness in a uniform manner.^[4] They were introduced by Georg Cantor in the late 19th century, particularly in his 1895 paper on transfinite numbers, to extend the investigation of infinite orderings beyond cardinality alone.^[5]

Isomorphism

An order isomorphism between two linearly ordered sets

(A, <)

and

(B, <)

is a bijection

f: A \to B

such that for all

a, b \in A

a < b

if and only if

f(a) < f(b)

^[6]. This relation preserves the order structure completely, ensuring that the sets are indistinguishable in terms of their ordering properties. The relation of order isomorphism is reflexive, as the identity function on any set is an order isomorphism to itself; symmetric, since the inverse of an order isomorphism is also an order isomorphism; and transitive, as the composition of two order isomorphisms is again an order isomorphism ^[1]. Consequently, order isomorphism partitions the class of all linearly ordered sets into equivalence classes, each corresponding to a unique order type. Order isomorphisms differ from order embeddings, which are injective functions

f: A \to B

satisfying

a < b

if and only if

f(a) < f(b)

, but need not be surjective ^[7]. Thus, while every order isomorphism is an order embedding, the converse holds only when the embedding is bijective. For example, the linearly ordered set of natural numbers and the set of integers both have cardinality

\aleph_0

but are not order isomorphic, since the natural numbers possess a least element while the integers do not.^[1]

Notation

Symbolic Representation

In order theory, order types are symbolically represented using a combination of Greek letters for archetypal examples and arithmetic operations for constructed types. The order type of the natural numbers under the standard ordering is denoted by

\omega

, introduced by Georg Cantor as the first infinite ordinal symbolizing the completed sequence of finite numbers. Similarly, the order type of the negative integers (ordered increasingly) is denoted by

^*\omega

\omega^*

, representing the reverse of

\omega

. The order type of the integers, which combines a copy of the negative integers followed by the non-negative integers, is denoted by

\zeta = \omega^* + \omega

. The order type of the rational numbers, characterized as the unique countable dense linear order without endpoints, is denoted by

\eta

. For finite totally ordered sets, the convention is to denote the order type simply by the positive integer

n

, where

n

indicates the number of elements in the chain. For well-ordered sets, order types coincide with ordinal numbers and are typically denoted by symbols such as

\alpha

\beta

, which can be expressed using transfinite arithmetic operations like addition, multiplication, and exponentiation. These notations draw from Cantor's foundational work on transfinite numbers. Symbolic representations of order types are generally non-unique, as the same type can be expressed through different combinations of sums, products, and other operations on basic types; however, canonical forms exist for specific classes, such as the Cantor normal form for ordinals, which uniquely decomposes them into increasing sums of powers of

\omega

Cantor's Back-and-Forth Method

Cantor's back-and-forth method is a constructive technique used to establish order isomorphisms between certain linear orders, particularly by building a bijection that preserves the order relation through iterative extensions. Developed by Georg Cantor in the late 19th century as part of his foundational work on transfinite numbers and order types, the method was employed to demonstrate that all countable dense linear orders without endpoints are isomorphic to the order type of the rational numbers

\mathbb{Q}

.^[8] The method applies primarily to countable dense linear orders without endpoints, where between any two elements there exists another, and there are no minimal or maximal elements. In such structures, denoted as

(A, \leq_A)

and

(B, \leq_B)

, both sets are countably infinite, and the density ensures that partial isomorphisms can always be extended. This makes the technique ideal for proving uniqueness up to isomorphism in this class, as seen in Cantor's theorem that any such order is order-isomorphic to

(\mathbb{Q}, <)

.^[9]^[8] To apply the method, enumerate the elements of

A

\{a_n \mid n \in \omega\}

and

B

\{b_n \mid n \in \omega\}

. Construct a sequence of finite partial isomorphisms

f_n: A \to B

(strictly increasing injections) such that

f_0 = \emptyset

, each

f_{n+1}

extends

f_n

, every

a_k

is in the domain of some

f_n

, and every

b_k

is in the range of some

f_m

. The union

f = \bigcup f_n

then yields a full order isomorphism. The construction alternates "forth" steps, which extend the partial map to include the next unused element from

A

by finding a suitable image in

B

using density (e.g., placing it between existing images if needed, or beyond the current range since there are no endpoints), and "back" steps, which include the next unused element from

B

into the domain by inverting the process and ensuring order preservation. For instance, at a forth step for

a_n

, if

a_n

lies between two domain elements

a_i < a_n < a_j

with

f_n(a_i) = b_p

and

f_n(a_j) = b_q

, density in

B

guarantees an unused

b_r

with

b_p < b_r < b_q

to map to. Similar reasoning applies to back steps and endpoint-free cases.^[9]^[8] While powerful for countable cases, the back-and-forth method does not extend to uncountable dense orders, such as the reals

\mathbb{R}

, where no such universal isomorphism exists, nor to non-dense orders lacking the intermediate element property. It also requires the absence of endpoints; orders with minima or maxima, even if countable and dense in between, are not covered by this direct application.^[8]

Examples

Finite Orders

Finite order types are the order types of finite linearly ordered sets, representing the simplest cases in the classification of linear orders. For any natural number

n

, all linearly ordered sets with exactly

n

elements are order-isomorphic to each other, and this unique order type is denoted by

n

.^[1] This isomorphism holds because any two finite chains of the same length can be mapped bijectively while preserving the order relation.^[1] These order types exhibit key structural properties that distinguish them from infinite ones. Finite linear orders are discrete, meaning that for every element except the maximum, there is an immediate successor, and for every element except the minimum, there is an immediate predecessor.^[10] Every nonempty finite linear order has both a first element (the minimum) and a last element (the maximum).^[1] Additionally, they contain no infinite descending chains, as the finiteness of the set precludes any infinite sequence.^[1] A representative example is the order type

3

, which corresponds to any three-element set ordered as

a < b < c

, where

a

is the minimum,

c

is the maximum, and

b

is the immediate successor of

a

and predecessor of

c

.^[1] Finite order types are in direct correspondence with finite cardinal numbers, sharing the same notation

n

to denote both the cardinality of the set and its order type under any linear ordering.^[1]

Orders on Integers and Naturals

The natural numbers

\mathbb{N}

, equipped with the standard less-than-or-equal-to ordering, possess the order type

\omega

, which is the smallest infinite ordinal. This order type is well-ordered, meaning every nonempty subset has a least element, and consequently, there are no infinite descending chains in

\mathbb{N}

. As a discrete order, every element in

\omega

has an immediate successor, with 0 serving as the least element but no greatest element present. Furthermore,

\omega

is countable, admitting a bijection with itself via the identity mapping.^[11] The negative integers

\mathbb{Z}^- = \{\dots, -2, -1\}

, under the standard ordering, have the order type

{}^*\omega

, which is the reverse (or dual) of

\omega

. This structure is discrete, with every element having an immediate predecessor but no least element, instead featuring a greatest element at

-1

. Like

\omega

{}^*\omega

is countable, though it is not well-ordered due to the existence of infinite descending chains, such as

\dots < -3 < -2 < -1

. The notation

{}^*\omega

emphasizes its isomorphism to

\omega

under order reversal.^[11] The integers

\mathbb{Z}

, ordered standardly, exhibit the order type

\zeta

, expressible as

\dots + {}^*\omega + \omega

, forming a doubly infinite discrete chain without endpoints. This order is countable, bijective with

\mathbb{N}

, and discrete in the sense that every element has both an immediate successor and predecessor. Unlike

\omega

\zeta

is not well-ordered, permitting infinite descending chains like

\dots < -2 < -1 < 0

, and it lacks both least and greatest elements. Finite orders serve as building blocks for these structures through iterative summation in one or both directions.^[11]

Dense Orders: Rationals

A dense linear order is a linear order

(L, <)

in which, for any two distinct elements

a, b \in L

with

a < b

, there exists

c \in L

such that

a < c < b

.^[12] The rational numbers

\mathbb{Q}

under the standard ordering

<

provide the archetypal example of a countable dense linear order without endpoints, as between any two rationals there is always another rational.^[12] The order type of

(\mathbb{Q}, <)

, commonly denoted

\eta

, captures this structure and serves as the canonical representative for such orders.^[12] Cantor's theorem establishes the uniqueness of

\eta

up to isomorphism: any countable dense linear order without endpoints is order-isomorphic to

(\mathbb{Q}, <)

.^[13] The proof employs Cantor's back-and-forth method, which constructs the isomorphism by iteratively extending partial isomorphisms between finite subsets while preserving the density and lack of endpoints.^[13] The order type

\eta

exhibits key structural properties that underscore its centrality in the theory of linear orders. It is universal for countable linear orders, meaning every countable linear order embeds order-preservingly into

(\mathbb{Q}, <)

.^[12] Additionally,

\eta

is homogeneous: any order-isomorphism between finite suborders of

(\mathbb{Q}, <)

extends to an automorphism of the entire structure.^[14]

Orders on Reals

The order type of the real numbers

\mathbb{R}

under the standard ordering

\leq

is a dense linear order without endpoints, meaning that between any two distinct elements

a < b

, there exists another element

c

such that

a < c < b

, and for every element, there are elements both less than and greater than it.^[15] This order is also complete, or Dedekind-complete, in the sense that every nonempty subset of

\mathbb{R}

that is bounded above has a least upper bound (supremum) in

\mathbb{R}

, and similarly for infima of bounded-below subsets.^[9] Unlike countable dense orders, the cardinality of

\mathbb{R}

is uncountable, specifically

2^{\aleph_0}

, which distinguishes it from structures like the rationals.^[16] This order type is commonly denoted by

\lambda

, representing the Dedekind completion of the countable dense order type

\eta

of the rationals

\mathbb{Q}

.^[1] It is distinct from

\eta

not only due to its uncountability but also because of its completeness, as

\mathbb{Q}

lacks suprema for many bounded subsets (e.g., the set of rationals less than

\sqrt{2}

).^[15] A fundamental uniqueness result, analogous to Cantor's theorem for countable dense orders, states that any two dense, complete linear orders without endpoints that are separable (i.e., contain a countable dense subset) are order-isomorphic; thus, $\lambda$ is the unique such order type up to isomorphism.^[17]^[15] Key properties of $\lambda$ include separability, as $\mathbb{Q}$ forms a countable dense subset of $\mathbb{R}$ , ensuring that the order is "approximable" by countably many points.^[15] In the order topology—where basic open sets are intervals—the space is connected, meaning it cannot be partitioned into two nonempty disjoint open sets, which aligns with its completeness and density.^[9] Furthermore, $\lambda$ serves as the universal model for separable complete linear orders without endpoints, in that any such order is isomorphic to an interval within $\mathbb{R}$ , highlighting its foundational role in order theory.^[15]

Well-Orders

Definition of Well-Ordering

A well-ordering on a set

A

is a total order

\leq

such that every nonempty subset of

A

has a least element with respect to

\leq

.^[18] This property ensures that descending progressions cannot continue indefinitely.^[1] This least element condition is equivalent to the absence of infinite strictly descending chains in the order. That is, there do not exist elements

a_1, a_2, a_3, \dots \in A

such that

a_1 > a_2 > a_3 > \dots

.^[1] To see the equivalence, suppose there is an infinite descending chain; then the set

\{a_1, a_2, a_3, \dots\}

would be a nonempty subset without a least element, contradicting the well-ordering property. Conversely, if a nonempty subset

S \subseteq A

lacks a least element, then by repeatedly selecting elements smaller than previous ones (possible in a total order), one can construct an infinite descending chain within

S

.^[1] Well-orderings form a subclass of total orders, which are linear orders where any two distinct elements are comparable. The distinguishing feature of well-orderings is the minimal element property for subsets, which total orders lack in general—for instance, the integers under the standard order are totally ordered but not well-ordered, as the negative integers form a subset without a least element.^[18] This additional structure makes well-orderings particularly useful in inductive arguments and foundational mathematics. In set theory, the well-ordering theorem asserts that every nonempty set admits a well-ordering, though the proof is non-constructive and relies on the axiom of choice.^[19] Ernst Zermelo proved this theorem in 1904 by showing that the axiom of choice implies the existence of such an ordering for any set, without providing an explicit construction.^[20] The theorem's validity thus depends on accepting the axiom of choice, and it plays a central role in establishing cardinal and ordinal comparisons.

Order Types of Well-Orders

In the theory of ordered sets, the order types of well-ordered sets are precisely the ordinal numbers, providing a canonical classification for all such structures. Every well-ordered set admits a unique order type, denoted by an ordinal α, which captures the "shape" of the ordering up to isomorphism. This uniqueness arises from the fact that any two well-ordered sets are isomorphic if and only if they have the same ordinal order type, ensuring that ordinals serve as complete invariants for well-orderings. Ordinals can be formally realized as transitive sets that are well-ordered by the membership relation ∈, though the primary focus here is on their role as abstract order types rather than specific set-theoretic constructions. The finite ordinals correspond exactly to the order types of finite well-ordered sets, coinciding with the natural numbers under the standard ordering; for instance, the ordinal 0 is the type of the empty set, 1 of a singleton, and n inductively built as the successor of n-1. Transfinite ordinals extend this beyond the finite, encompassing both successor ordinals, which are of the form β + 1 for some ordinal β, and limit ordinals, which are not successors and represent suprema of increasing sequences of smaller ordinals, such as the first infinite ordinal ω. This framework, originating with Cantor's foundational work on transfinite numbers, establishes that the collection of all ordinal order types forms a proper class, mirroring the hierarchy of all possible well-orderings. The distinction between successor and limit ordinals highlights the structural richness of transfinite well-orders, where successors add a maximal element to a previous type, while limits capture convergence without a largest predecessor.

Examples of Ordinal Order Types

The order type

\omega

represents the simplest infinite well-ordering, corresponding to the natural numbers

\mathbb{N} = \{0, 1, 2, \dots\}

ordered by the standard less-than relation, where every nonempty subset has a least element, and there is no largest element.^[21] This ordinal is the smallest infinite ordinal, serving as the foundation for constructing larger ordinals through successor and limit operations.^[21] The ordinal

\omega + 1

extends

\omega

by adjoining a single element greater than all natural numbers, resulting in a well-ordering isomorphic to

\{0, 1, 2, \dots\} \cup \{\infty\}

with the usual order on

\mathbb{N}

and

\infty > n

for all

n \in \mathbb{N}

.^[21] This introduces a largest element absent in

\omega

, illustrating how successor ordinals modify the structure by adding a new maximum.^[21] The order type

\omega \cdot 2

consists of two disjoint copies of

\omega

placed in sequence, equivalent to the ordering on

\mathbb{N} \times \{0, 1\}

where

(n, 0) < (m, 0)

n < m

(n, 1) < (m, 1)

n < m

, and all elements with second coordinate 0 precede those with 1.^[21] This construction demonstrates ordinal multiplication, yielding a countable well-order with two limit points at the "ends" of each

\omega

segment.^[21] Higher ordinals like

\omega^2

arise as the supremum of

\omega \cdot n

for all finite

n \in \mathbb{N}

. Specifically,

\omega^2

is the order type of

\mathbb{N} \times \mathbb{N}

under the antilexicographic order

(m, n) < (m', n')

n < n'

n = n'

and

m < m'

, capturing a countable infinity of copies of

\omega

.^[21] The first uncountable ordinal

\omega_1

is the smallest ordinal not bijectable with

\mathbb{N}

, representing the order type of the set of all countable ordinals under the membership relation, with every proper initial segment countable.^[21] This ordinal marks the transition to uncountable well-orderings, where the continuum hypothesis concerns its cardinality relative to the real numbers.^[21]

Properties and Operations

Embeddings and Extensions

An order embedding of one linearly ordered set

(A, \leq_A)

into another

(B, \leq_B)

is an injective function

f: A \to B

such that for all

x, y \in A

x \leq_A y

if and only if

f(x) \leq_B f(y)

.^[22] This condition ensures that the order structure is preserved and reflected, distinguishing it from a mere order-preserving map, which need not reflect the order.^[1] An order extension occurs when such an embedding maps into a strictly larger set, with the image forming a proper suborder isomorphic to the original.^[1] Order isomorphisms, which are bijective order embeddings, represent a special case where the structures are equivalent up to relabeling.^[22] A canonical example is the embedding of the rational numbers

\mathbb{Q}

with their standard order into the real numbers

\mathbb{R}

, via the inclusion map, which preserves the dense linear order while expanding the continuum.^[1] Finite linear orders also embed readily into the integers

\mathbb{Z}

; for instance, a three-element chain

a < b < c

maps to

0 < 1 < 2

\mathbb{Z}

, allowing indefinite extension in both directions.^[1] Under the axiom of choice, Zorn's lemma implies the existence of maximal order extensions for any linear order type.^[23] Form the partially ordered set consisting of all linear orders into which the original embeds, ordered by the existence of an order embedding between them. Every chain in this poset admits an upper bound via the direct limit construction, yielding a linear order that extends all in the chain.^[1] Thus, a maximal element exists: a linear order containing the original as a suborder, with no proper superorder into which it embeds.^[23]

Sums and Products of Order Types

In order theory, the sum of two order types

\alpha

and

\beta

, denoted

\alpha + \beta

, is defined as the order type of the disjoint union of ordered sets representing

\alpha

and

\beta

, where every element of the set for

\alpha

precedes every element of the set for

\beta

.^[1] This operation corresponds to concatenating the two orders, preserving their internal structures while placing one entirely after the other. The sum is associative, meaning

(\alpha + \beta) + \gamma = \alpha + (\beta + \gamma)

for any order types

\alpha, \beta, \gamma

, but it is not commutative in general.^[1] For example, consider

\omega

, the order type of the natural numbers under the usual ordering. Then

\omega + 1

is the order type of the naturals followed by an additional element, which has a maximum but no immediate predecessor for that maximum. In contrast,

1 + \omega

places a single element before the naturals, resulting in an order with a minimum but no largest element, and these are not order-isomorphic since one has a greatest element while the other does not. This illustrates the non-commutativity of the sum:

\omega + 1 \neq 1 + \omega

. The product of order types

\alpha \cdot \beta

is defined as the order type of the Cartesian product of sets representing

\beta

and

\alpha

, equipped with the lexicographic order where the coordinate from

\beta

(the second factor) varies most significantly:

(b, a) < (b', a')

b <_{\beta} b'

or if

b = b'

and

a <_{\alpha} a'

.^[1] This construction yields

\beta

many copies of

\alpha

, ordered successively. Like the sum, the product is associative but generally non-commutative. For instance, with

\omega

, we have

\omega \cdot 2 = \omega + \omega

, consisting of two successive copies of the naturals, while

2 \cdot \omega

is order-isomorphic to

\omega

itself, as it can be represented by pairs

(n, i)

for

n \in \mathbb{N}

i \in \{0,1\}

under the lexicographic order, which absorbs the finite factor on the left.^[1] A notable absorption property appears in dense orders, such as

\eta

, the order type of the rational numbers under the standard ordering. Here,

\eta + \eta \cong \eta

, since two dense countable linear orders without endpoints can be concatenated and still yield a single dense countable linear order without endpoints, as the rationals admit a dense interleaving. Similarly,

\eta \cdot 2 = \eta + \eta \cong \eta

, and more generally

\eta \cdot \eta \cong \eta

, reflecting the self-similar structure of the rationals under these operations. These properties highlight how sums and products can preserve or simplify certain order types, particularly in infinite cases.

Dense and Scattered Orders

In order theory, a linear order is classified as dense if, for any two distinct elements

a < b

, there exists an element

c

such that

a < c < b

.^[13] This property ensures no two elements are adjacent, generalizing the structure observed in the rational numbers but applying to any such order type. Dense orders lack immediate successors or predecessors between elements, allowing for infinite subdivision in every interval. Examples include the order type of the real numbers

\mathbb{R}

, where the density axiom holds universally.^[13] In contrast, a scattered order is a linear order that does not contain a suborder isomorphic to the order type

\eta

of the rational numbers

\mathbb{Q}

.^[24] This absence of a dense rational substructure distinguishes scattered orders, which encompass all well-orders—such as ordinal types—and discrete orders like the integers

\mathbb{Z}

, where elements have immediate successors and predecessors.^[24] Scattered orders form a broad class closed under certain constructions, excluding any embedding of the dense, countable

\eta

. Hausdorff's theorem provides a foundational dichotomy by characterizing scattered orders as the smallest class containing well-orders and their reverses, closed under lexicographic sums indexed by elements of this class.^[25] A key consequence is a canonical decomposition: every countable linear order is isomorphic to a lexicographic sum of scattered orders indexed by a dense linear order (or a singleton if the original order is scattered).^[26] This decomposition highlights how arbitrary orders blend scattered and dense components, with the dense index set capturing the "non-scattered" aspect. For instance, while the reals represent a pure dense order type, ordinals exemplify pure scattered types, illustrating the theorem's partitioning.^[24]

History

Order type

Recent from talks

Recent from talks

Contribute something

Contribute something

Media Pages

Timelines

Articles

Notes collections

Notes

Notes

Days in Chronicle

Order type

Notation

Examples

Order type of well-orderings

Examples

Rational numbers

See also

External links

References

Order type

Basic Concepts

Definition

Isomorphism

Notation

Symbolic Representation

Cantor's Back-and-Forth Method

Examples

Finite Orders

Orders on Integers and Naturals

Dense Orders: Rationals

Orders on Reals

Add your contribution

Related Hubs

Contribute something