Lattice theory One may define a totally ordered set as a particular kind of
lattice, namely one in which we have : \{a\vee b, a\wedge b\} = \{a, b\} for all
a,
b. We then write
a ≤
b if and only if a = a\wedge b. 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 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. 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 numbers 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 For any two disjoint total orders (A_1,\le_1) and (A_2,\le_2), there is a natural order \le_+ on the set A_1\cup A_2, which is called the sum of the two orders or sometimes just A_1+A_2: : For x,y\in A_1\cup A_2, x\le_+ y holds if and only if one of the following holds: :# x,y\in A_1 and x\le_1 y :# x,y\in A_2 and x\le_2 y :# x\in A_1 and y\in A_2 Intuitively, this means that the elements of the second set are added on top of the elements of the first set. More generally, if (I,\le) is a totally ordered index set, and for each i\in I the structure (A_i,\le_i) is a linear order, where the sets A_i are pairwise disjoint, then the natural total order on \bigcup_i A_i is defined by : For x,y\in \bigcup_{i\in I} A_i, x\le y holds if: :# Either there is some i\in I with x\le_i y :# or there are some i in I with x\in A_i, y\in A_j
Decidability The
first-order theory of total orders is
decidable, i.e. there is an algorithm for deciding which first-order statements hold for all total orders. Using interpretability in
S2S, the
monadic second-order theory of
countable total orders is also decidable. ==Orders on the Cartesian product of totally ordered sets==