Total order

	Email		Print
	Bookmark		Link

Total order

In mathematics

Mathematics

Mathematics is the study of quantity, structure, space, change, and related topics of pattern and form. Mathematicians seek out patterns whether found in numbers, space, natural science, computers, imaginary abstractions, or elsewhere....
and set theory

Set theory

Set theory is the branch of mathematics that studies Set , which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics....
, a total order, linear order, simple order, or (non-strict) ordering is a binary relation

Binary relation

In mathematics, a binary relation is an arbitrary association of elements within a set or with elements of another set.An example is the "divides" relation between the set of prime numbers P and the set of integers Z, in which every prime p is associated with every integer z that is a divisibility of p, and no othe...
(here denoted by infix

Infix notation

Infix notation is the common arithmetic and logical formula notation, in which operators are written infix-style between the operands they act on ....
=) on some set X. The relation is transitive

Transitive relation

In mathematics, a binary relation R over a Set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....
, antisymmetric

Antisymmetric relation

In mathematics, a binary relation R on a Set X is antisymmetric if, for all a and b in Xor, equivalently,In mathematical notation, this is:...
, and total

Total relation

In mathematics, a binary relation R over a Set X is total if it holds for all a and b in X that a is related to b or b is related to a ....
. A set paired with a total order is called a totally ordered set, a linearly ordered set, a simply ordered set, or a chain.

If X is totally ordered under =, then the following statements hold for all a, b and c in X:

If a = b and b = a then a = b (antisymmetry

Antisymmetric relation

In mathematics, a binary relation R on a Set X is antisymmetric if, for all a and b in Xor, equivalently,In mathematical notation, this is:...
);

If a = b and b = c then a = c (transitivity

Transitive relation

In mathematics, a binary relation R over a Set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....
);

a = b or

Logical disjunction

File:ORGate2.pngIn logic and mathematics, or, also known as logical disjunction or inclusive disjunction is a logical operator that results in true whenever one or more of its operands are true....
b = a (totality

Total relation

In mathematics, a binary relation R over a Set X is total if it holds for all a and b in X that a is related to b or b is related to a ....
).

Contrast with a partial order, which lacks the third condition. A relation having the property of "totality" means that any pair of elements in the set of the relation are mutually comparable under the relation.

Totality implies reflexivity

Reflexive relation

In set theory, a binary relation can have, among other properties, reflexivity or irreflexivity.At least in this context, relation always means a subset of X ? X....
, that is, a = a.

Discussion

Ask a question about 'Total order'

Start a new discussion about 'Total order'

Answer questions from other users

Full Discussion Forum

Encyclopedia

In mathematics

Mathematics

Set theory

Binary relation

Infix notation

Infix notation is the common arithmetic and logical formula notation, in which operators are written infix-style between the operands they act on ....
=) on some set X. The relation is transitive

Transitive relation

Antisymmetric relation

In mathematics, a binary relation R on a Set X is antisymmetric if, for all a and b in Xor, equivalently,In mathematical notation, this is:...
, and total

Total relation

If a = b and b = a then a = b (antisymmetry

Antisymmetric relation

In mathematics, a binary relation R on a Set X is antisymmetric if, for all a and b in Xor, equivalently,In mathematical notation, this is:...
);

If a = b and b = c then a = c (transitivity

Transitive relation

In mathematics, a binary relation R over a Set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....
);

a = b or

Logical disjunction

Total relation

In mathematics, a binary relation R over a Set X is total if it holds for all a and b in X that a is related to b or b is related to a ....
).

Reflexive relation

In set theory, a binary relation can have, among other properties, reflexivity or irreflexivity.At least in this context, relation always means a subset of X ? X....
, that is, a = a. Thus a total order is also a partial order, that is, a binary relation

Binary relation

Strict total order

For each (non-strict) total order = there is an associated asymmetric

Asymmetric relation

Asymmetry often means, simply: not symmetric. In this sense an asymmetric relation is a binary relation which is not a symmetric relation.In some texts the word is given the following stronger definition....
(hence irreflexive) relation <, called a strict total order, which can equivalently be defined in two ways:

a < b if and only if
If and only if

If and only if, in logic and fields that rely on it such as mathematics and philosophy, is a biconditional logical connective between statements....
a = b and a ? b
a < b if and only if not b = a (i.e., < is the of the 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 equivalently be defined in two ways:

a = b if and only if a < b or a = b
a = b if and only if not b < a

Two more associated orders are the complements = and >, completing the quadruple

Quadruple

In mathematics, a quadruple or quadruplet is an Tuple with n being 4. This means it depicts four element s, with the ordering of the elements carrying meaning....
.

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, with the restriction of the order on the whole set.

Any partially ordered set X where every two elements are comparable (i.e. if a,b are members of X either a = b or b = a or both).

Any set of cardinal number
Cardinal number

In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of Set ....
s or ordinal numbers (more strongly, these are well-order
Well-order

In mathematics, a 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....
s).

If X is any set and f an injective function
Injective function

In mathematics, an injective function is a function which associates distinct arguments with distinct values.An injective function is called an injection, and is also said to be a one-to-one function ....
from X to a totally ordered set then f induces a total ordering on X by setting x₁ < x₂ if and only if f(x₁) < f(x₂).

The lexicographical order
Lexicographical order

In mathematics, the lexicographic or lexicographical order, , is a natural order theory structure of the Cartesian product of two ordered sets....
on the Cartesian product
Cartesian product

In mathematics, the Cartesian product is a direct product of sets. The Cartesian product is named after Ren? Descartes, whose formulation of analytic geometry gave rise to this concept....
of a set of totally ordered sets indexed by an ordinal, is itself a total order. For example, any set of words ordered alphabetically is a totally ordered set, viewed as a subset of a Cartesian product of a countable number of copies of a set formed by adding the space symbol to the alphabet (and defining a space to be less than any letter).

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
Upper bound

In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element of P which is greater than or equal to every element of S....
.
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 with no upper or lower bound, which is dense
Dense order

In mathematics, a partial order ≤ on a set X is said to be dense if, for all x and y in X for which x < y, there is a z in X such that x < z < y....
in the sense that for every a and b such that a < b there is a c such that a < c < b.
The real numbers comprise the smallest unbounded connected
Connectedness

In mathematics, connectedness is used to refer to various properties meaning, in some sense, "all one piece". When a mathematical object has such a property, we say it is connected; otherwise it is disconnected....
totally ordered set. (See below for the definition of the topology.)

Further concepts

Chains

While chain is sometimes merely a synonym for totally ordered set, it can also refer to a totally ordered subset

Subset

In mathematics, especially in set theory, a Set A is a subset of a set B if A is "contained" inside B. Notice that A and B may coincide....
of some partially ordered set

Partially ordered set

In mathematics, especially order theory, a partially ordered set formalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set ....
. The prevalence of the latter definition most likely stems from the crucial role chains so defined play in Zorn's lemma

Zorn's lemma

Zorn's lemma, also known as the Kuratowski?Zorn lemma, is a proposition of set theory that states:Every partially ordered set in which every Total order has an upper bound contains at least one maximal element....
.

Thus the reals

Real number

In mathematics, the real numbers may be described informally in several different ways. The real numbers include both rational numbers, such as 42 and −23/129, and irrational numbers, such as pi and the square root of two; or, a real number can be given by an infinite decimal representation, such as 2.4871773339...., where the digits co...
R are a totally ordered set. However, if we consider all subsets of the integer

Integer

The integers are natural numbers including 0 and their negative and non-negative numberss . They are numbers that can be written without a fractional or decimal component, and fall within the set ....
s partially ordered by inclusion

Inclusion

selfref|For inclusion and exclusion of Wikipedia templates, see...
, then the set , where I_n is the set of natural numbers below n, would often be called a chain, as it is totally ordered under inclusion: If n≤k, then I_n is a subset of I_k.

Lattice theory

One may define a totally ordered set as a particular kind of lattice

Lattice (order)

In mathematics, a lattice is a partially ordered set in which subsets of any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain Axiom identity ....
, namely one in which we have

for all a, b.

We then write a = b if and only if

If and only if

If and only if, in logic and fields that rely on it such as mathematics and philosophy, is a biconditional logical connective between statements....
. Hence a totally ordered set is a distributive lattice

Distributive lattice

In mathematics, distributive lattices are lattice for which the operations of join and meet distributivity over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection ....
; here is the proof

Distributive lattice/Proofs

Lemma 1Every totally ordered set is a distributive lattice with max as join and min as meet....
.

Finite total orders

A simple counting

Counting

Counting is the mathematics action of repeatedly adding one, usually to find out how many objects there are or to set aside a desired number of objects , or for well-ordered objects, to find the ordinal number of a particular object, or to find the object with a particular ordinal number....
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

Order type

In mathematics, especially in set theory, two ordered sets X,Y are said to have the same order type just when they are order isomorphic, that is, when there exists a bijection f: X → Y such that both f and its inverse are monotone ....
ω 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

Subcategory

In mathematics, 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....
of the category

Category (mathematics)

In mathematics, a category is a fundamental and abstract way to describe mathematical entities and their relationships. A category is composed of a collection of abstract "objects" of any kind, linked together by a collection of abstract "morphism" of any kind that have a few basic properties ....
of partially ordered sets, with the morphism

Morphism

In mathematics, a morphism is an Abstraction derived from structure-preserving map between two mathematical structures.The study of morphisms and of the structures over which they are defined, is central to category theory....
s being maps which respect the orders, i.e. maps f such that if a = b then f(a) = f(b).

A bijective

Bijection

In mathematics, a bijection, or a bijective function is a function f from a set X to a set Y with the property that, for every y in Y, there is exactly one x in X such that f = y....
map

Map (mathematics)

In mathematics and related technical fields, the term map or mapping is often a synonym for Function . Thus, for example, a partial map is a partial function, and a total map is a total function....
between two totally ordered sets that respects the two orders is an isomorphism

Isomorphism

In abstract algebra, an isomorphism is a bijection map f such that both f and its inverse function f −1 are homomorphisms, i.e., structure-preserving mappings....
in this category.

Order topology

For any totally ordered set X we can define the open interval
Interval (mathematics)

In mathematics, a interval is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set....
s (a, b) = , (-8, b) = , (a, 8) = and (-8, 8) = X. We can use these open intervals to define a topology

Topology

Topology is a major area of mathematics that has emerged through the development of concepts from geometry and set theory, such as those of space, dimension, shape, transformation and others....
on any ordered set, the order topology

Order topology

In mathematics, an order topology is a certain topology that can be defined on any totally ordered set. It is a natural generalization of the topology of the real numbers to arbitrary totally ordered sets....
.

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

Normal space

In topology and related branches of mathematics, normal spaces, T4 spaces, T5 spaces, and T6 spaces are particularly nice kinds of topological spaces....
.

Completeness

A totally ordered set is said to be complete if every nonempty subset that has an upper bound

Upper bound

In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element of P which is greater than or equal to every element of S....
, has a least upper bound. For example, the set of real number

Real number

Rational number

In mathematics, a rational number is a number which can be expressed as a quotient of two integers. Non-integer rational numbers are usually written as the vulgar fraction , where b is not 0 ....
s 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

Complete lattice

In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum and an infimum . Complete lattices appear in many applications in mathematics and computer science....
is compact

Compact space

In mathematics, a topological space is called compact if each of its open covers has a finite set subcover.Note: Some authors such as Nicolas Bourbaki use the term "quasi-compact" for this instead, and reserve the term "compact" for topological spaces that are both Hausdorff spaces and "quasi-compact"....
. Examples are the closed intervals of real numbers, e.g. the unit interval

Unit interval

In mathematics, the unit interval is the interval [0,1], that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1....
[0,1], and the affinely extended real number system (extended real number line). There are order-preserving homeomorphism

Homeomorphism

In the mathematics field of topology, a homeomorphism or topological isomorphism is a continuous function between two topological spaces....
s between these examples.

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

Cartesian product

In mathematics, the Cartesian product is a direct product of sets. The Cartesian product is named after Ren? Descartes, whose formulation of analytic geometry gave rise to this concept....
of two totally ordered sets are:

Lexicographical order
Lexicographical order

In mathematics, the lexicographic or lexicographical order, , is a natural order theory structure of the Cartesian product of two ordered sets....
: (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
Product order

In mathematics, given two ordered sets A and B, one can induce an ordering on the Cartesian product A × B. Giventwo pairs and in A × B, one sets...
). 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 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

Vector space

File:Vector addition ans scaling.pngA vector space is a mathematical structure formed by a collection of vectors: objects that may be Vector addition together and Scalar multiplication by numbers, called scalar s in this context....
Rⁿ, each of these make it an ordered vector space

Ordered vector space

In mathematics an ordered vector space or partially ordered vector space is a vector space equipped with a partial order which is compatible with the vector space operations....
.

See also .

A real function of n real variables defined on a subset of Rⁿ on that subset.