In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a total or linear order is a
partial order
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
in which any two elements are comparable. That is, a total order is a
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and in ...
on some
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
, which satisfies the following for all
and
in
:
#
(
reflexive).
# If
and
then
(
transitive).
# If
and
then
(
antisymmetric).
#
or
(
strongly connected, formerly called total).
Total orders are sometimes also called simple, connex, or full orders.
A set equipped with a total order is a totally ordered set; the terms simply ordered set, linearly ordered set, and loset are also used. The term ''chain'' is sometimes defined as a synonym of ''totally ordered set'', but refers generally to some sort of totally ordered subsets of a given partially ordered set.
An extension of a given partial order to a total order is called a
linear extension
In order theory, a branch of mathematics, a linear extension of a partial order is a total order (or linear order) that is compatible with the partial order. As a classic example, the lexicographic order of totally ordered sets is a linear ext ...
of that partial order.
Strict and non-strict total orders
A on a set
is a
strict partial order on
in which any two distinct elements are comparable. That is, a total order is a
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and in ...
on some
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
, which satisfies the following for all
and
in
:
# Not
(
irreflexive
In mathematics, a binary relation ''R'' on a set ''X'' is reflexive if it relates every element of ''X'' to itself.
An example of a reflexive relation is the relation " is equal to" on the set of real numbers, since every real number is equal ...
).
# If
then not
(
asymmetric).
# If
and
then
(
transitive).
# If
, then
or
(
connected).
Asymmetry follows from transitivity and irreflexivity; moreover, irreflexivity follows from asymmetry.
For each (non-strict) total order
there is an associated relation
, called the ''strict total order'' associated with
that can be defined in two equivalent ways:
*
if
and
(
reflexive reduction
In mathematics, a binary relation ''R'' on a set ''X'' is reflexive if it relates every element of ''X'' to itself.
An example of a reflexive relation is the relation " is equal to" on the set of real numbers, since every real number is equal t ...
).
*
if not
(i.e.,
is the
complement of the
converse of
).
Conversely, the
reflexive closure of a strict total order
is a (non-strict) total order.
Examples
* Any
subset
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
of a totally ordered set is totally ordered for the restriction of the order on .
* The unique order on the empty set, , is a total order.
* Any set of
cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. ...
s or
ordinal number
In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets.
A finite set can be enumerated by successively labeling each element with the leas ...
s (more strongly, these are
well-order
In mathematics, a well-order (or well-ordering or well-order relation) on a set ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together with the well-or ...
s).
* If is any set and an
injective function
In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositi ...
from to a totally ordered set then induces a total ordering on by setting if and only if .
* The
lexicographical order
In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of ...
on the
Cartesian product
In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\t ...
of a family of totally ordered sets,
indexed by a
well ordered set, is itself a total order.
* The set of
real numbers
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every re ...
ordered by the usual "less than or equal to" (≤) or "greater than or equal to" (≥) relations is totally ordered. Hence each subset of the real numbers is totally ordered, such as the
natural numbers,
integers, and
rational numbers
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ra ...
. Each of these can be shown to be the unique (up to an
order isomorphism) "initial example" of a totally ordered set with a certain property, (here, a total order is ''initial'' for a property, if, whenever has the property, there is an order isomorphism from to a subset of ):
** The natural numbers form an initial non-empty totally ordered set with no
upper bound.
** The integers form an initial non-empty totally ordered set with neither an upper nor a
lower bound
In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of .
Dually, a lower bound or minorant of is defined to be an elemen ...
.
** The rational numbers form an initial totally ordered set which is
dense in the real numbers. Moreover, the reflexive reduction < is a
dense order on the rational numbers.
** The real numbers form an initial 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.
* The letters of the alphabet ordered by the standard
dictionary order, e.g., etc., is a strict total order.
Chains
The term chain is sometimes defined as a synonym for a totally ordered set, but it is generally used for referring to a
subset
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
of a
partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
that is totally ordered for the induced order. Typically, the partially ordered set is a set of subsets of a given set that is ordered by inclusion, and the term is used for stating properties of the set of the chains. This high number of nested levels of sets explains the usefulness of the term.
A common example of the use of ''chain'' for referring to totally ordered subsets is
Zorn's lemma which asserts that, if every chain in a partially ordered set has an upper bound in , then contains at least one maximal element. Zorn's lemma is commonly used with being a set of subsets; in this case, the upperbound is obtained by proving that the union of the elements of a chain in is in . This is the way that is generally used to prove that a
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
has
Hamel bases and that a
ring has
maximal ideals.
In some contexts, the chains that are considered are order isomorphic to the natural numbers with their usual order or its
opposite order. In this case, a chain can be identified with a
monotone sequence, and is called an ascending chain or a descending chain, depending whether the sequence is increasing or decreasing.
A partially ordered set has the
descending chain condition if every descending chain eventually stabilizes. For example, an order is
well founded if it has the descending chain condition. Similarly, the
ascending chain condition In mathematics, the ascending chain condition (ACC) and descending chain condition (DCC) are finiteness properties satisfied by some algebraic structures, most importantly ideals in certain commutative rings.Jacobson (2009), p. 142 and 147 These c ...
means that every ascending chain eventually stabilizes. For example, a
Noetherian ring is a ring whose
ideals satisfy the ascending chain condition.
In other contexts, only chains that are
finite sets are considered. In this case, one talks of a ''finite chain'', often shortened as a ''chain''. In this case, the length of a chain is the number of inequalities (or set inclusions) between consecutive elements of the chain; that is, the number minus one of elements in the chain. Thus a
singleton set is a chain of length zero, and an
ordered pair
In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...
is a chain of length one. The
dimension
In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coord ...
of a space is often defined or characterized as the maximal length of chains of subspaces. For example, the
dimension of a vector space is the maximal length of chains of
linear subspace
In mathematics, and more specifically in linear algebra, a linear subspace, also known as a vector subspaceThe term ''linear subspace'' is sometimes used for referring to flats and affine subspaces. In the case of vector spaces over the reals, l ...
s, and the
Krull dimension of a
commutative ring
In mathematics, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring properties that are not ...
is the maximal length of chains of
prime ideal
In algebra, a prime ideal is a subset of a ring that shares many important properties of a prime number in the ring of integers. The prime ideals for the integers are the sets that contain all the multiples of a given prime number, together wi ...
s.
"Chain" may also be used for some totally ordered subsets of
structures that are not partially ordered sets. An example is given by
regular chain In computer algebra, a regular chain is a particular kind of triangular set in a multivariate polynomial ring over a field. It enhances the notion of characteristic set.
Introduction
Given a linear system, one can convert it to a triangular ...
s of polynomials. Another example is the use of "chain" as a synonym for a
walk in a
graph.
Further concepts
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
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bic ...
. 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
In the mathematical field of order theory, an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets (posets). Whenever two posets are order isomorphic, they can be ...
to an
ordinal one may show that every finite total order is
order isomorphic
In the mathematical field of order theory, an order isomorphism is a special kind of monotone function that constitutes a suitable notion of isomorphism for partially ordered sets (posets). Whenever two posets are order isomorphic, they can be ...
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
In mathematics, especially in set theory, two ordered sets and 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 suc ...
ω 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
In mathematics, specifically category theory, a subcategory of a category ''C'' is a category ''S'' whose objects are objects in ''C'' and whose morphisms are morphisms in ''C'' with the same identities and composition of morphisms. Intuitively, ...
of the
category of
partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
s, 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 mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word i ...
in this category.
Order topology
For any totally ordered set ''X'' we can define the ''
open interval
In mathematics, a (real) interval is a set of real numbers that contains all real numbers lying between any two numbers of the set. For example, the set of numbers satisfying is an interval which contains , , and all numbers in between. Other ...
s'' (''a'', ''b'') = , (−∞, ''b'') = , (''a'', ∞) = and (−∞, ∞) = ''X''. We can use these open intervals to define a
topology
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...
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
Complete may refer to:
Logic
* Completeness (logic)
* Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable
Mathematics
* The completeness of the real numbers, which implies t ...
if every nonempty subset that has an
upper bound, has a
least upper bound. For example, the set of
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s R is complete but the set of
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ra ...
s Q is not. In other words, the various concepts of
completeness (not to be confused with being "total") do not carry over to
restrictions. For example, over the
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s a property of the relation ≤ is that every
non-empty subset ''S'' of R with an
upper bound in R has a
least upper bound (also called supremum) in R. However, for the rational numbers this supremum is not necessarily rational, so the same property does not hold on the restriction of the relation ≤ to the rational numbers.
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
In mathematics, a complete lattice is a partially ordered set in which ''all'' subsets have both a supremum (join) and an infimum (meet). A lattice which satisfies at least one of these properties is known as a ''conditionally complete lattice.'' ...
is
compact
Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to:
* Interstate compact
* Blood compact, an ancient ritual of the Philippines
* Compact government, a type of colonial rule utilized in Britis ...
. Examples are the closed intervals of real numbers, e.g. the
unit interval
In mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1. It is often denoted ' (capital letter ). In addition to its role in real analysis ...
,1 and the
affinely extended real number system (extended real number line). There are order-preserving
homeomorphism
In the mathematical field of topology, a homeomorphism, topological isomorphism, or bicontinuous function is a bijective and continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isom ...
s 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:
:#
and
:#
and
:#
and
Intuitively, 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:
:# Either there is some
with
:# or there are some