Editing Total order (section)

==Further concepts==

===Lattice theory===

One may define a totally ordered set as a particular kind of [[Lattice (order)|lattice]], namely one in which we have
: <math>\{a\vee b, a\wedge b\} = \{a, b\}</math> for all ''a'', ''b''.

We then write ''a'' ≤ ''b'' [[if and only if]] <math>a = a\wedge b</math>. 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 number|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]] &omega; by natural numbers in a fashion which respects the ordering (either starting with zero or with one).

===Category theory===

Totally ordered sets form a [[subcategory|full subcategory]] of the [[category (mathematics)|category]] of [[partially ordered set]]s, with the [[morphism]]s being maps which respect the orders, i.e. maps ''f'' such that if ''a'' ≤ ''b'' then ''f''(''a'') ≤ ''f''(''b'').

A [[bijection|bijective]] [[map (mathematics)|map]] between two totally ordered sets that respects the two orders is an [[isomorphism]] in this category.

===Order topology===

For any totally ordered set {{mvar|X}} we can define the ''[[interval (mathematics)|open interval]]s'' 
* {{math|1=(''a'', ''b'') = {{mset|''x'' | ''a'' < ''x'' and ''x'' < ''b''}}}}, 
* {{math|1=(−∞, ''b'') = {{mset|''x'' | ''x'' < ''b''}}}}, 
* {{math|1=(''a'', ∞) = {{mset|''x'' | ''a'' < ''x''}}}}, and 
* {{math|1=(−∞, ∞) = ''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, {{char|<}} is less than and {{char|>}} greater than we might refer to the order topology on '''N''' induced by {{char|<}} and the order topology on '''N''' induced by {{char|>}} (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 space|normal]].

===Completeness===<!-- This section is linked from [[Completely distributive lattice]]. See [[WP:MOS#Section management]] -->

A totally ordered set is said to be '''[[Completeness (order theory)|complete]]''' if every nonempty subset that has an [[upper bound]], has a [[least upper bound]]. For example, the set of [[real number]]s '''R''' is complete but the set of [[rational number]]s '''Q''' is not. In other words, the various concepts of [[Completeness (order theory)|completeness]] (not to be confused with being "total") do not carry over to [[Binary relation|restrictions]]. For example, over the [[real number]]s a property of the relation {{char|≤}} is that every [[Empty set|non-empty]] subset ''S'' of '''R''' with an [[upper bound]] in '''R''' has a [[Supremum|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 {{char|≤}} 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]] is [[Compact space|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 [[homeomorphism]]s between these examples.

===Sums of orders===<!-- This section is linked from [[Scattered_order]]. See [[WP:MOS#Section management]] -->

For any two disjoint total orders <math>(A_1,\le_1)</math>  and <math>(A_2,\le_2)</math>, there is a natural order <math>\le_+</math> on the set <math>A_1\cup A_2</math>, which is called the sum of the two orders or sometimes just <math>A_1+A_2</math>: 
: For <math>x,y\in A_1\cup A_2</math>, <math>x\le_+ y</math> holds if and only if one of the following holds:
:# <math>x,y\in A_1</math> and <math>x\le_1 y</math>
:# <math>x,y\in A_2</math> and <math>x\le_2 y</math>
:# <math>x\in A_1</math> and <math>y\in A_2</math>
Intuitively, this means that the elements of the second set are added on top of the elements of the first set.

More generally, if <math>(I,\le)</math> is a totally ordered index set, and for each <math>i\in I</math> the structure <math>(A_i,\le_i)</math> is a linear order, where the sets <math>A_i</math> are pairwise disjoint, then the natural total order on <math>\bigcup_i A_i</math> is defined by 
: For <math>x,y\in \bigcup_{i\in I} A_i</math>, <math>x\le y</math> holds if: 
:# Either there is some <math>i\in I</math> with <math> x\le_i y </math>
:# or there are some <math>i<j</math> in <math>I</math>  with <math> x\in A_i</math>,  <math> y\in A_j</math>

=== Decidability ===
The [[first-order logic|first-order]] theory of total orders is [[decidability (logic) | decidable]], i.e. there is an algorithm for deciding which first-order statements hold for all total orders.  Using interpretability in [[S2S (mathematics)|S2S]], the [[monadic second-order logic|monadic second-order]] theory of [[countable set|countable]] total orders is also decidable.<ref>{{Cite book | last=Weyer | first=Mark | date=2002 | title=Automata, Logics, and Infinite Games |chapter=Decidability of S1S and S2S | series=Lecture Notes in Computer Science | volume=2500 | pages=207–230 |chapter-url=https://link.springer.com/chapter/10.1007/3-540-36387-4_12 | doi=10.1007/3-540-36387-4_12 | publisher=Springer| isbn=978-3-540-00388-5 }}</ref>