Total order

Page issues

Binary relations 

Symmetric Antisymmetric Connex Well- Has Has

founded joins meets
Equivalence ✓ ✗ ✗ ✗ ✗ ✗
relation
Preorder ✗ ✗ ✗ ✗ ✗ ✗
(Quasiorder)
Partial order ✗ ✓ ✗ ✗ ✗ ✗
Total preorder ✗ ✗ ✓ ✗ ✗ ✗
Total order ✗ ✓ ✓ ✗ ✗ ✗
Prewellordering ✗ ✗ ✓ ✓ ✗ ✗
Well-quasi- ✗ ✗ ✗ ✓ ✗ ✗
ordering
Well-ordering ✗ ✓ ✓ ✓ ✗ ✗
Lattice ✗ ✓ ✗ ✗ ✓ ✓
Join-semilattice ✗ ✓ ✗ ✗ ✓ ✗
Meet-semilattice ✗ ✓ ✗ ✗ ✗ ✓

A "✓" indicates that the column property is required in the row definition.
For example, the definition of an equivalence relation requires it to be symmetric.
All definitions tacitly require transitivity and reflexivity.
In mathematics, a linear order, total order,
simple order, or (non-strict) ordering is a
binary relation on some set , which is
antisymmetric, transitive, and a connex
relation. A set paired with a total order is
called a totally ordered set, a linearly
ordered set, a simply ordered set, or a
chain.

Formally, a binary relation is a total

order on a set if the following
statements hold for all and in :

If and then
(antisymmetry);
 If and then
(transitivity);
or (connex property).

Antisymmetry eliminates uncertain cases

when both precedes and precedes
.[1]:325 A relation having the "connex"
property means that any pair of elements
in the set of the relation are comparable
under the relation. This also means that
the set can be diagrammed as a line of
elements, giving it the name linear.[1]:330
The connex property also implies
reflexivity, i.e., a ≤ a. Therefore, a total
order is also a (special case of a) partial
order, as, for a partial order, the connex
property is replaced by the weaker
reflexivity property. An extension of a given
partial order to a total order is called a
linear extension of that partial order.

Strict total order

For each (non-strict) total order ≤ there is
an associated asymmetric (hence
irreflexive) relation <, called a strict total
order, which can be defined in two
equivalent ways:

a < b if a ≤ b and a ≠ b
a < b if not b ≤ a (i.e., < is the inverse of
the complement of ≤)
Properties:

The relation is transitive: a < b and b < c

implies a < c.
The relation is trichotomous: exactly
one of a < b, b < a and a = b is true.
The relation is a strict weak order, where
the associated equivalence is equality.

We can work the other way and start by

choosing < as a transitive trichotomous
binary relation; then a total order ≤ can be
defined in two equivalent ways:

a ≤ b if a < b or a = b
a ≤ b if not b < a
Two more associated orders are the
complements ≥ and >, completing the
quadruple {<, >, ≤, ≥}.

We can define or explain the way a set is

totally ordered by any of these four
relations; the notation implies whether we
are talking about the non-strict or the strict
total order.

Examples
The letters of the alphabet ordered by
the standard dictionary order, e.g.,
A < B < C etc.
Any subset of a totally ordered set X is
totally ordered for the restriction of the
order on X.
The unique order on the empty set, ∅, is
a total order.
Any set of cardinal numbers or ordinal
numbers (more strongly, these are well-
orders).
If X is any set and f an injective function
from X to a totally ordered set then f
induces a total ordering on X by setting
x1 < x2 if and only if f(x1) < f(x2).
The lexicographical order on the
Cartesian product of a family of totally
ordered sets, indexed by a well ordered
set, is itself a total order.
The set of real numbers ordered by the
usual less than (<) or greater than (>)
relations is totally ordered, hence also
the subsets of natural numbers, integers,
and rational numbers. Each of these can
be shown to be the unique (to within
isomorphism) smallest example of a
totally ordered set with a certain
property, (a total order A is the smallest
with a certain property if whenever B
has the property, there is an order
isomorphism from A to a subset of B):
The natural numbers comprise the
smallest totally ordered set with no
upper bound.
The integers comprise the smallest
totally ordered set with neither an
upper nor a lower bound.
The rational numbers comprise the
smallest totally ordered set which is
dense in the real numbers. The
definition of density used here says
that for every a and b in the real
numbers such that a < b, there is a
q in the rational numbers such that
a < q < b.
The real numbers comprise the
smallest unbounded totally ordered
set that is connected in the order
topology (defined below).
 Ordered fields are totally ordered by
definition. They include the rational
numbers and the real numbers. Every
ordered field contains an ordered
subfield that is isomorphic to the
rational numbers. Any Dedekind-
complete ordered field is isomorphic to
the real numbers.

Further concepts
Chains

While chain is sometimes merely a

synonym for totally ordered set, it can also
refer to a totally ordered subset of some
partially ordered set. The latter definition
has a crucial role in Zorn's lemma. The
height of a poset denotes the cardinality
of its largest chain in this sense.

For example, consider the set of all

subsets of the integers partially ordered by
inclusion. Then the set { In : n is a natural
number}, where In is the set of natural
numbers below n, is a chain in this
ordering, as it is totally ordered under
inclusion: If n≤k, then In is a subset of Ik.

Lattice theory

One may define a totally ordered set as a

particular kind of lattice, namely one in
which we have

for all a, b.

We then write a ≤ b if and only if

. Hence a totally ordered set is
a distributive lattice.

Finite total orders

A simple counting argument will verify that

any non-empty finite totally ordered set
(and hence any non-empty subset thereof)
has a least element. Thus every finite total
order is in fact a well order. Either by direct
proof or by observing that every well order
is order isomorphic to an ordinal one may
show that every finite total order is order
isomorphic to an initial segment of the
natural numbers ordered by <. In other
words, a total order on a set with k
elements induces a bijection with the first
k natural numbers. Hence it is common to
index finite total orders or well orders with
order type ω by natural numbers in a
fashion which respects the ordering (either
starting with zero or with one).

Category theory

Totally ordered sets form a full

subcategory of the category of partially
ordered sets, with the morphisms being
maps which respect the orders, i.e. maps f
such that if a ≤ b then f(a) ≤ f(b).

A bijective map between two totally

ordered sets that respects the two orders
is an isomorphism in this category.

Order topology

For any totally ordered set X we can define

the open intervals (a, b) = {x : a < x and x <
b}, (−∞, b) = {x : x < b}, (a, ∞) = {x : a < x}
and (−∞, ∞) = X. We can use these open
intervals to define a topology on any
ordered set, the order topology.
When more than one order is being used
on a set one talks about the order topology
induced by a particular order. For instance
if N is the natural numbers, < is less than
and > greater than we might refer to the
order topology on N induced by < and the
order topology on N induced by > (in this
case they happen to be identical but will
not in general).

The order topology induced by a total

order may be shown to be hereditarily
normal.

Completeness
A totally ordered set is said to be complete
if every nonempty subset that has an
upper bound, has a least upper bound. For
example, the set of real numbers R is
complete but the set of rational numbers Q
is not.

There are a number of results relating

properties of the order topology to the
completeness of X:

If the order topology on X is connected,

X is complete.
X is connected under the order topology
if and only if it is complete and there is
no gap in X (a gap is two points a and b
 in X with a < b such that no c satisfies a
< c < b.)
X is complete if and only if every
bounded set that is closed in the order
topology is compact.

A totally ordered set (with its order

topology) which is a complete lattice is
compact. Examples are the closed
intervals of real numbers, e.g. the unit
interval [0,1], and the affinely extended real
number system (extended real number
line). There are order-preserving
homeomorphisms between these
examples.
Sums of orders

For any two disjoint total orders

and , there is a natural order
on the set , which is called the
sum of the two orders or sometimes just
:

For , holds if
and only if one of the following holds:
1. and
2. and
3. and

Intutitively, this means that the elements

of the second set are added on top of the
elements of the first set.
More generally, if is a totally
ordered index set, and for each the
structure is a linear order, where
the sets are pairwise disjoint, then the

natural total order on is defined by

For , holds if:

1. Either there is some with

2. or there are some in with

,

Orders on the Cartesian

product of totally ordered
sets
In order of increasing strength, i.e.,
decreasing sets of pairs, three of the
possible orders on the Cartesian product
of two totally ordered sets are:

Lexicographical order: (a,b) ≤ (c,d) if and

only if a < c or (a = c and b ≤ d). This is a
total order.
(a,b) ≤ (c,d) if and only if a ≤ c and b ≤ d
(the product order). This is a partial
order.
(a,b) ≤ (c,d) if and only if (a < c and b < d)
or (a = c and b = d) (the reflexive closure
of the direct product of the
corresponding strict total orders). This
is also a partial order.
All three can similarly be defined for the
Cartesian product of more than two sets.

Applied to the vector space Rn, each of

these make it an ordered vector space.

See also examples of partially ordered

sets.

A real function of n real variables defined

on a subset of Rn defines a strict weak
order and a corresponding total preorder
on that subset.

Related structures
A binary relation that is antisymmetric,
transitive, and reflexive (but not
necessarily total) is a partial order.

A group with a compatible total order is a

totally ordered group.

There are only a few nontrivial structures

that are (interdefinable as) reducts of a
total order. Forgetting the orientation
results in a betweenness relation.
Forgetting the location of the ends results
in a cyclic order. Forgetting both data
results in a separation relation.[2]

See also
Order theory
Well-order
 Suslin's problem
Countryman line
Prefix order – a downward total partial
order

Notes
1. Nederpelt, Rob (2004). Logical
Reasoning: A First Course. Texts in
Computing. 3 (3rd, Revised ed.). King's
College Publications. ISBN 0-9543006-7-X.
2. Macpherson, H. Dugald (2011), "A survey
of homogeneous structures" , Discrete
Mathematics,
doi:10.1016/j.disc.2011.01.024 , retrieved
28 April 2011
References
George Grätzer (1971). Lattice theory:
first concepts and distributive lattices. W.
H. Freeman and Co. ISBN 0-7167-0442-0
John G. Hocking and Gail S. Young
(1961). Topology. Corrected reprint,
Dover, 1988. ISBN 0-486-65676-4

External links
Hazewinkel, Michiel, ed. (2001) [1994],
"Totally ordered set" , Encyclopedia of
Mathematics, Springer
Science+Business Media B.V. / Kluwer
Academic Publishers, ISBN 978-1-
55608-010-4
Retrieved from
"https://en.wikipedia.org/w/index.php?
title=Total_order&oldid=871944097"

Last edited 2 months ago by Jochen…

Content is available under CC BY-SA 3.0 unless

otherwise noted.