# Definition:Totally Ordered Set

## Definition

Let $\struct {S, \preceq}$ be a relational structure.

Then $\struct {S, \preceq}$ is a **totally ordered set** if and only if $\preceq$ is a total ordering.

### Totally Ordered Class

The concept carries naturally over into class theory:

Let $V$ be a basic universe.

Let $\RR \subseteq V \times V$ be a relation.

Let $A$ be a subclass of the field of $\RR$.

Let the restriction of $\RR$ to $A$ be a total ordering on $A$.

Then $A$ is described as being **totally ordered under $\RR$**.

## Partial vs. Total Ordering

It is not demanded of an ordering $\preceq$, defined in its most general form on a set $S$, that *every* pair of elements of $S$ is related by $\preceq$.

They may be, or they may not be, depending on the specific nature of both $S$ and $\preceq$.

If it *is* the case that $\preceq$ is a connected relation, that is, that every pair of distinct elements is related by $\preceq$, then $\preceq$ is called a total ordering.

If it is *not* the case that $\preceq$ is connected, then $\preceq$ is called a partial ordering.

Beware that some sources use the word **partial** for an ordering which **may or may not** be connected, while others insist on reserving the word **partial** for one which is specifically **not** connected.

It is wise to be certain of what is meant.

As a consequence, on $\mathsf{Pr} \infty \mathsf{fWiki}$ we resolve any ambiguity by reserving the terms for the objects in question as follows:

**Partial ordering**: an ordering which is specifically**not**total

**Total ordering**: an ordering which is specifically**not**partial.

## Also known as

A **totally ordered set** is also called a **simply ordered set** or **linearly ordered set**.

It is also known as a **toset**. This term may be encountered on $\mathsf{Pr} \infty \mathsf{fWiki}$.

Some sources refer to a **totally ordered set** as an **ordered set**, using the term **partially ordered set** for what goes as an ordered set on $\mathsf{Pr} \infty \mathsf{fWiki}$.

Some sources use the term **chain**, but this word is generally restricted to mean specifically a **totally ordered subset** of a given ordered set.

The term **permutation** is an older term for **totally ordered set**, but has since been changed to mean the bijection that can be applied on such a **totally ordered set** in order to redefine its **ordering**.

## Examples

### Example Ordering on Integers

Let $\preccurlyeq$ denote the relation on the set of integers $\Z$ defined as:

- $a \preccurlyeq b$ if and only if $0 \le a \le b \text { or } b \le a < 0 \text { or } a < 0 \le b$

where $\le$ is the usual ordering on $\Z$.

Then $\struct {\Z, \preccurlyeq}$ is a totally ordered set.

## Also see

- Definition:Strictly Ordered Set
- Definition:Strictly Partially Ordered Set
- Definition:Strictly Totally Ordered Set
- Definition:Strictly Well-Ordered Set

- Results about
**total orderings**can be found**here**.

## Sources

- 1951: Nathan Jacobson:
*Lectures in Abstract Algebra: Volume $\text { I }$: Basic Concepts*... (previous) ... (next): Introduction $\S 4$: The natural numbers - 1955: John L. Kelley:
*General Topology*... (previous) ... (next): Chapter $0$: Orderings - 1960: Paul R. Halmos:
*Naive Set Theory*... (previous) ... (next): $\S 14$: Order - 1964: A.M. Yaglom and I.M. Yaglom:
*Challenging Mathematical Problems With Elementary Solutions: Volume $\text { I }$*... (previous) ... (next): Problems - 1968: A.N. Kolmogorov and S.V. Fomin:
*Introductory Real Analysis*... (previous) ... (next): $\S 3.3$: Ordered sets. Order types - 1972: A.G. Howson:
*A Handbook of Terms used in Algebra and Analysis*... (previous) ... (next): $\S 4$: Number systems $\text{I}$: Peano's Axioms - 1975: T.S. Blyth:
*Set Theory and Abstract Algebra*... (previous) ... (next): $\S 7$ - 1993: Keith Devlin:
*The Joy of Sets: Fundamentals of Contemporary Set Theory*(2nd ed.) ... (previous) ... (next): $\S 1$: Naive Set Theory: $\S 1.5$: Relations - 1996: Winfried Just and Martin Weese:
*Discovering Modern Set Theory. I: The Basics*... (previous) ... (next): Part $1$: Not Entirely Naive Set Theory: Chapter $2$: Partial Order Relations - 2008: Paul Halmos and Steven Givant:
*Introduction to Boolean Algebras*... (previous) ... (next): Appendix $\text{A}$: Set Theory: Order