Total Order
In mathematics, a binary relation r on a set S is aTotal Order IfAndOnlyIf for every pair of elements A and B, in S, exactly one of the following is true:
- A r B, or
- B r A, or
- A = B.
(where = means equality)
Note that this relationship must be transitive and non-reflexive. In other words:
-
A < B and B < C
A < C
- It is never true that A < A
-
A
B and B 
A 
A = B.
Loosely speaking, there together imply that there are no cycles in the directed graph where each element points at those that are smaller than in.
Note that calling something a TotalOrder requires that both the relation r and the set S be specified. A common sloppy shortcut is the assumption that r corresponds to the greater-than (or less-than) operator. When it is said that a set S is totally-ordered, that is shorthand for "there exists some binary relation r which makes a TotalOrder on S."
Examples of TotalOrders:
- The "less than" operator over the integers, the rationals, and the reals. (But NOT the complex numbers).
- strcmp() over the set of ASCII string (note that there are several interesting TotalOrders over ASCII strings
See also PartialOrder and WellOrdered.
Note that = means equality above. There are many set for which a looser set of rules applies; one can define two relations r and x and have that exactly one of A r B, B r A, or A x B is true. If x is an EquivalenceRelation, then such an ordering is isomorphic to a TotalOrder; however I'm not aware of a special name for this sort of ordering. The < operator over the complex numbers is such a set; none of 5 < 3+4j, 5 = 3+4j, or 3+4j < 5 is true. However, by mapping each complex number onto its magnitude (a set equal to the nonnegative reals) and then applying <, a TotalOrder is realized.
Someone wrote:
- Also, the three operators <, >, and = are all transitive. A < B implies B > A, A = B implies B = A, A = A is always true, and A < A and A > A are both always false.
This is not transitivity. Transitivity is: a a
As the original author of the above, I agree; sorry if I was unclear. What I was trying to say is that the operators are transitive; 'and in addition' < and > are anti-reflexive and anti-symmetric, whereas = is both reflexive and symmetric.
If 'x is an EquivalenceRelation, such an ordering is isomorphic to a TotalOrder; however I'm not aware of a special name for this sort of ordering. (text quoted from comment two sections above)
- This makes it sound like any set with an equivalence relationship defined over it is totally ordered under that relation, which is false. In any case, why the hell does this page exist when anyone halfway serious about math knows to check wolfram (http://mathworld.wolfram.com/TotallyOrderedSet.html)?
- Sorry for causing confusion; I was commenting on, and quoting from the comment two sections above where there is discussion of a kind of trichotomy involving an ordering relationship "r" and an equivalence relation "x". The author of that comment seemed to imply that such an ordering was somehow different from a total ordering because the symbol "x" was used for the equivalence relation instead of the symbol "="; I merely pointed out that the particular notation does not matter for this purpose. I agree that wolfram should be checked, and that it is authoritative. I also do not know why the h___ this page exists; however, since it does, and since the page gratuitously refers to *EquivalenceRelation* I thought it might be useful to define that term. (And the citation you give in wolfram, while it defines TotalOrder quite admirably, does not define equivalence at all.) For a standard and authoritative definition of EquivalenceRelation, please see:
http://mathworld.wolfram.com/EquivalenceRelation.html which is superior to the definition which I gave previously (and which I have now deleted).
By an EquivalenceRelation is usually meant a dyadic relation which is reflexive, symmetric and transitive. Please see the definition given above [previous definition deleted].
Substituting the EquivalenceRelation "x" for "=" in the definition of TotalOrder yields an ordering which is isomorphic to a TotalOrder. Since the only difference seems to be in the notation (using "x" instead of "=") why would it not be correct simply to call it a TotalOrder? The definitions of mathematics are formal and abstract, and do not depend on the meta-linguistic meanings which we attach to primitives such as "x" or "=". -- JohnReynoldsTheStudent