1 Definition and basic properties
A total preorder on a set \(X\) is a binary relation \(\le\) on \(X\) that is reflexive and transitive, and that is total in the weak sense: for any \(x,y\in X\), at least one of \(x\le y\) or \(y\le x\) holds. The relation is therefore capable of expressing “no worse than” or “at least as good as,” even when some elements must be treated as indistinguishable.
A central consequence is that the relation groups elements into equivalence classes—subsets whose members are mutually comparable in both directions. On the level of these classes, the totality condition yields a linear order, so the structure resembles an ordinary total order, except that ties are allowed.
1.1 Reflexivity
Reflexivity requires that every element compares to itself: \[ \forall x\in X,\quad x\le x. \] This property ensures that the preorder never contradicts the idea that an item is at least as good as itself, and it also underpins the construction of equivalence classes.
1.2 Transitivity
Transitivity means that comparisons propagate: \[ \forall x,y,z\in X,\quad (x\le y \ \text{and}\ y\le z)\Rightarrow x\le z. \] With transitivity, “no worse than” behaves consistently across chains of elements, which is crucial for reasoning about rankings and for ensuring that the induced ordering of classes is well-defined.
1.3 Totality (comparability)
The totality (sometimes called weak comparability) condition is: \[ \forall x,y\in X,\quad x\le y \ \text{or}\ y\le x. \] It guarantees that any two elements can be compared in at least one direction. Unlike antisymmetric orders, total preorders permit the possibility that both comparisons hold simultaneously, leading to ties.
1.4 Induced equivalence relation
From \(\le\), define a relation \(\sim\) by \[ x\sim y \quad\text{iff}\quad (x\le y \ \text{and}\ y\le x). \] In a total preorder, \(\sim\) is an equivalence relation: it is reflexive (from reflexivity of \(\le\)), symmetric by definition, and transitive (using transitivity of \(\le\) in both directions). Thus, the set \(X\) splits into equivalence classes representing ties.
1.5 Order on equivalence classes
Let \(X/{\sim}\) be the set of equivalence classes. Define an order \(\preceq\) on these classes by \[ [x]\preceq [y]\quad \text{iff}\quad x\le y, \] where \([x]\) denotes the equivalence class of \(x\). This is well-defined: if \(x\sim x'\) and \(y\sim y'\), transitivity shows that \(x\le y\) implies \(x'\le y'\). The totality condition ensures that any two classes are comparable, and transitivity ensures that \(\preceq\) is transitive. Consequently, \((X/{\sim},\preceq)\) forms a linear order.
1.6 Relationship to antisymmetry
A total order requires antisymmetry in addition to reflexivity and transitivity. Antisymmetry states: \[ x\le y \ \text{and}\ y\le x \Rightarrow x=y. \] Total preorders generally do not satisfy antisymmetry; when both directions hold for distinct elements, they are tied in the sense captured by \(\sim\). Antisymmetry therefore corresponds to the special case where every equivalence class is a singleton.
2 Equivalent characterizations
Total preorders can be described in multiple, mutually reinforcing ways. These characterizations clarify how the preorder relates to equivalence classes, quotient constructions, and “weak” versions of linear orders.
2.1 Quotient construction
The preorder \(\le\) determines an equivalence relation \(\sim\) (mutual reachability under \(\le\)), and the quotient \(X/{\sim}\) carries a linear order \(\preceq\). Conversely, given a partition of \(X\) into classes indexed by a linearly ordered set, one can define a preorder by declaring \(x\le y\) precisely when the class of \(x\) is not higher than the class of \(y\). Under these translations, total preorders correspond exactly to “linearly ordered tiers with possible internal ties.”
2.2 “Weak order” viewpoint
A “weak order” perspective views a total preorder as an ordering that is complete but may not distinguish tied elements. It is “weak” because it allows indifference: two elements may be mutually at least-as-good without being forced equal. This matches common ranking interpretations where only relative position among tiers matters.
2.3 Compatibility with strict order
From \(\le\), define a strict relation \(<\) by \[ x<y \quad\text{iff}\quad x\le y \ \text{and not}\ (y\le x). \] In a total preorder, this strict part is transitive and forms a strict total order on equivalence classes. The preorder and its strict part fit together: every non-indifferent comparison is witnessed by the strict relation.
2.4 Complementary relation forms
One can also use complementary formulations that separate “less than,” “equal-tier/indifferent,” and “greater than.” For instance, totality ensures that for any \(x,y\), exactly one of the following holds:
- \(x<y\),
- \(x\sim y\), or
- \(y<x\).
This trichotomy is at the level of strict vs indifferent comparisons and reflects how equivalence classes line up in a chain.
2.5 Alternative totality notions
Some texts express totality as: \[ \forall x,y,\quad (x\le y)\lor (y\le x) \] or equivalently in terms of the strict part: \[ \forall x,y,\quad x<y \ \lor\ x\sim y \ \lor\ y<x. \] These are equivalent consequences of the preorder axioms and the way \(\sim\) and \(<\) are defined.
3 Strict and non-strict variants
Preorders distinguish between non-strict comparisons (at least as good) and strict comparisons (strictly better). Examining these variants clarifies what kind of ordering information is present.
3.1 Defining the strict part
Given a total preorder \(\le\), define \[ x<y \iff (x\le y)\land \neg(y\le x). \] This strict relation captures genuine precedence between elements: \(x<y\) means \(x\) is not merely no worse than \(y\), but actually better in the sense that the reverse comparison fails.
3.2 Defining the indifference part
The indifference relation is exactly the equivalence relation \(\sim\): \[ x\sim y \iff (x\le y)\land (y\le x). \] It models tied items: each is at least as good as the other.
3.3 Properties of the strict relation
In a total preorder, \(<\) is:
- irreflexive (no element is strictly better than itself),
- transitive (strict improvements chain consistently),
- and forms a strict total order on equivalence classes.
Within one equivalence class, strict comparisons do not occur in either direction.
3.4 Relationship between strict and preorder
The relations \(<\), \(\sim\), and \(\le\) determine each other. For example: \[ x\le y \iff (x<y)\lor (x\sim y). \] Thus, the preorder can be reconstructed from its strict and indifference components, while totality ensures the reconstruction is complete for every pair.
3.5 When strict part becomes a strict total order
The strict part becomes a strict total order on elements precisely when antisymmetry holds for \(\le\). Equivalently, when every equivalence class is a singleton, there is no indifference between distinct elements, and \(x<y\), \(x=y\), or \(y<x\) account for all pairs.
4 Examples and non-examples
Studying examples shows how total preorders encode rankings with ties, while non-examples highlight the role of each axiom.
4.1 Simple numerical comparisons with ties
Let \(X=\mathbb{R}\) and define \(x\le y\) by comparing rounded scores, for instance: \[ x\le y \iff \lfloor x\rfloor \le \lfloor y\rfloor. \] Then any two real numbers can be compared by their floor values (totality), and the relation is reflexive and transitive because the usual \(\le\) is. Distinct numbers with the same floor become equivalent under \(\sim\), producing ties.
4.2 Lexicographic preorders
Consider \(X=\mathbb{R}^n\). A preorder can be defined lexicographically but with ties allowed at some coordinates. For example, define \[ (x_1,\dots,x_n)\le (y_1,\dots,y_n) \] if the first coordinate where they differ has \(x_i\le y_i\) in the usual sense, while coordinates after the decisive one are irrelevant. If comparisons are designed so that some blocks may be treated as equal-tier, the resulting relation remains reflexive and transitive and can satisfy weak totality.
4.3 Preorders from scoring functions
Let \(s:X\to \mathbb{R}\) be a scoring function. Define \[ x\le y \iff s(x)\le s(y). \] Reflexivity and transitivity follow from the corresponding properties of \(\le\) on \(\mathbb{R}\). Totality holds because real numbers are totally ordered. Elements with equal scores form equivalence classes.
4.4 Non-transitive relations
A common failure mode is losing transitivity. For instance, define a relation on three elements \(a,b,c\) by \(a\le b\) and \(b\le c\) but not \(a\le c\). Even if totality and reflexivity hold, the structure is not a preorder because transitivity fails, and the quotient/linear-order picture breaks down.
4.5 Relations that fail totality
Another failure mode is incomparability: define a relation that is reflexive and transitive but leaves some pairs unconnected, such as allowing neither \(x\le y\) nor \(y\le x\) for certain elements. Then equivalence classes cannot be arranged into a linear chain, since the “weak comparability” requirement is missing.
5 Order-theoretic structure
Total preorders impose a characteristic order-theoretic architecture: equivalence classes form a chain, while within-class elements are mutually indifferent.
5.1 Factor posets from total preorders
Although a total preorder may not be antisymmetric, the factor structure obtained by collapsing equivalent elements yields a genuine partially ordered set (indeed a linear order). This is the poset viewpoint behind the quotient construction: the “poset” is not on the original elements but on the equivalence classes.
5.2 Chains of equivalence classes
Because the preorder is total, any two equivalence classes are comparable. As a result, the classes form a chain: moving “upward” or “downward” in the chain is unambiguous at the class level.
5.3 Comparability within classes
Within a class \([x]\), every pair satisfies \(u\le v\) and \(v\le u\). Therefore, no strict relation distinguishes members of the same tier. The preorder’s informational content lies in how classes relate, not in the relative positions of individuals inside one class.
5.4 Limits of refinement to total orders
One might try to refine a preorder into a total order by breaking ties. However, multiple refinements may exist, and there is no canonical choice without extra information. Mathematically, a total preorder corresponds to a set of total orders that all agree on the ordering of equivalence classes but may differ inside each class.
5.5 Connection to rankings and tiers
This structure matches ranking systems with ties, such as “tier lists” in games or ordered categories in decision procedures. The equivalence classes correspond to tiers, and the induced linear order gives the global arrangement from best to worst.
6 Algebraic and logical connections
Total preorders appear naturally in logic and computation as semantic comparison relations. Their behavior under operations and transformations determines whether totality and transitivity are preserved.
6.1 Preorders vs orders
An order is a preorder plus antisymmetry. The distinction matters when reasoning about identity: under a preorder, mutual reachability does not force equality of elements; it forces only that they belong to the same equivalence class.
6.2 Total preorder in logic as a semantic relation
In semantics, total preorders can represent relative strength, likelihood, or preference of statements under a model. Indifference corresponds to semantic indistinguishability with respect to the chosen measure: two formulas may not be ranked apart even if they are different objects syntactically.
6.3 Closure properties under operations
If a preorder is induced from a monotone construction—such as composing a scoring function with an order-preserving map—certain closure properties follow. For example, applying a strictly increasing transformation to scores preserves the preorder structure, because it does not alter comparisons.
6.4 Composition and transformation of total preorders
A common transformation is to map elements via \(f:X\to Y\) and compare in \(Y\). If one defines \[ x\le_X x' \iff f(x)\le_Y f(x'), \] then reflexivity and transitivity are inherited. Totality holds if the target relation is total and the comparison in \(Y\) yields comparability for all images.
6.5 Constraints ensuring totality after transformations
Not every transformation preserves totality. If comparisons are made through a function that loses information (e.g., mapping multiple distinct values into a partially ordered subset without totality), totality may fail. Ensuring totality after transformation typically requires that the induced comparison can still decide at least one direction for every pair.
7 Applications in ranking and preference-like settings
Total preorders provide a formal language for systems where “better than” may only be stated up to ties, such as score-based ranking, preference statements, or decision rules.
7.1 Modeling scores with ties
When items are rated by a numeric or computable measure, identical (or effectively indistinguishable) scores yield ties. The resulting relation “no worse than” is naturally a total preorder: every pair of items can be compared, but equal scores create equivalence classes.
7.2 Reasoning with “at least as good as”
In preference reasoning, statements often take the form “\(x\) is at least as good as \(y\).” Such phrasing aligns directly with reflexive and transitive behavior, while allowing that two options can be mutually at least as good without asserting strict superiority.
7.3 Preference aggregation at a high level
Aggregation mechanisms in decision-making frequently produce a global ranking after combining multiple criteria. Even when individual criteria are comparable, the aggregate may treat several candidates as equally good, yielding a total preorder rather than an order.
7.4 Stable sorting intuition for tied groups
A practical intuition is stable sorting: items with equal keys keep their relative order, and a complete ordering is obtained only after tie handling. Conceptually, stable sorting corresponds to working with a preorder on keys (tiers) and optionally refining within each tied group.
7.5 Tie-breaking as a refinement step
If additional tie-breakers are introduced—such as a secondary score or deterministic rule—one can refine the total preorder into a total order. The refinement preserves the relative order of tiers while selecting a definite order between previously indifferent elements.
8 Verification and computation
Total preorders can be checked algorithmically by testing reflexivity, transitivity, and totality, and then constructing equivalence classes and their induced ordering.
8.1 Checking reflexivity
To verify reflexivity on a finite set, confirm that \(x\le x\) holds for every \(x\in X\). For representation formats such as adjacency matrices or comparator functions, this is typically straightforward.
8.2 Checking transitivity efficiently
| For finite \(X\), transitivity requires that whenever \(x\le y\) and \(y\le z\), then \(x\le z\). Naively this is cubic in \( | X | \). More efficient approaches depend on how the relation is stored (e.g., using matrix operations, transitive-closure algorithms, or exploiting structure of the generating rule). |
|---|
8.3 Checking totality
Totality on finite \(X\) can be checked by iterating over all pairs \((x,y)\) and verifying that \(x\le y\) or \(y\le x\). This is quadratic time in the worst case and often dominates only when other checks are optimized.
8.4 Building equivalence classes
Once \(\sim\) is defined by mutual comparisons, equivalence classes can be computed by grouping elements connected through the symmetric condition \(x\le y\) and \(y\le x\). Operationally, one may build a graph of mutual reachability and compute connected components under the appropriate criterion.
8.5 Producing an ordered list of classes
After classes are formed, the induced order on classes can be obtained by comparing representative elements from each class. Totality guarantees that classes can be arranged into a chain without ambiguity at the class level, enabling the output of an ordered tier list.
9 Common pitfalls
Several misconceptions recur when working with total preorders. Clarifying these helps prevent incorrect conclusions about ordering, identity, and comparison logic.
9.1 Confusing total preorder with total order
A frequent error is treating mutual comparability as equality. In a preorder, \(x\le y\) and \(y\le x\) imply only that \(x\sim y\), not that \(x=y\). Assuming antisymmetry leads to incorrect inferences.
9.2 Mistaking equivalence classes for single points
Equivalence classes can contain multiple elements. Treating each class as if it were a single abstract point is correct only after quotienting; operations on original elements may still depend on which representative is chosen unless all computations respect equivalence.
9.3 Forgetting that antisymmetry may fail
Antisymmetry failure is not an exception but a feature of preorders. When reasoning requires identifying elements, one must either refine the relation to an order or explicitly use the equivalence relation \(\sim\).
9.4 Using strict comparisons incorrectly
Strict comparisons require care: \(x<y\) means \(x\le y\) and not \(y\le x\). Confusing strict and non-strict parts can result in incorrect transitivity assumptions or faulty case distinctions in proofs.
9.5 Overlooking the quotient viewpoint
Many structural properties become clearer after collapsing equivalent elements. Ignoring the quotient perspective can lead to cumbersome reasoning about ties, whereas the class-level linear order provides a clean organizing principle.