Definition:Totally Ordered Set

From ProofWiki
Jump to navigation Jump to search

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:

Ordering: an ordering whose nature (total or partial) is not specified
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

Real Numbers under Usual Ordering

Let $\struct {\R, \le}$ denote the real numbers under the usual ordering on $\R$.


Then $\struct {\R, \le}$ is a totally ordered set.


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.


Divisor Relation

Let $\struct {\Z_{>0}, \divides}$ denote the order structure consisting of the (strictly) positive integers under the divisor relation $\divides$.

Then $\struct {\Z_{>0}, \divides}$ is specifically not a totally ordered set.


Also see

  • Results about total orderings can be found here.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Totally_Ordered_Set&oldid=708318"