Preorder
In mathematics, particularly in the field of order theory, a preorder (also known as a quasiorder) is a binary relation on a set that is reflexive and transitive.[1] This structure generalizes the notion of a partial order by omitting the requirement of antisymmetry, allowing distinct elements to be mutually related without being identical.[2] A preordered set consists of a set equipped with such a relation, often denoted by ≤.[3] Every preorder induces an equivalence relation defined by a ~ b if and only if a ≤ b and b ≤ a; the quotient of the set by this equivalence forms a partial order, illustrating how preorders can be refined into stricter ordering structures.[2] Preorders are foundational in various mathematical domains: in category theory, they correspond to thin categories, where there is at most one morphism between any two objects.[2] In economics and decision theory, they model preference relations that permit indifference between options.[4] Notable examples include the divisibility relation on the integers, where m ≤ n if m divides n, which is reflexive and transitive but fails antisymmetry for cases like 2 and -2.[5] Another is the alphabetical ordering on the set of humans with English names, where p ≤ q if p's name comes before or equals q's alphabetically; this is a preorder but not a partial order, as distinct individuals with identical names satisfy mutual comparability without equality.[6] The standard ordering on the real numbers also forms a preorder (in fact, a total order).[7]Fundamentals
Definition
A preorder, also known as a quasiorder, is a binary relation on a set that satisfies two fundamental properties: reflexivity and transitivity.[1][8] Formally, given a set X, a relation \leq on X is a preorder if, for all x, y, z \in X,- reflexivity: x \leq x,
- transitivity: if x \leq y and y \leq z, then x \leq z.
Basic properties
A preorder on a set X is a binary relation \leq that satisfies reflexivity and transitivity for all x, y, z \in X. Reflexivity ensures that x \leq x holds for every element, which permits the relation to model non-strict comparisons, such as in the natural numbers where n \leq m includes equality alongside proper ordering.[2] This property implies that the identity relation on X is contained within any preorder, allowing elements to be trivially related to themselves without imposing additional structure. Transitivity requires that if x \leq y and y \leq z, then x \leq z, ensuring the relation is closed under composition of paths in the associated directed graph. This closure property facilitates the formation of preorder ideals, defined as downward-closed subsets I \subseteq X where x \in I and y \leq x imply y \in I, and filters, which are upward-closed subsets F \subseteq X where x \in F and x \leq y imply y \in F. These structures capture "small" and "large" elements relative to the preorder, generalizing notions from partial orders. Preorders induce a natural topology known as the Alexandroff topology (or specialization topology), where the open sets are precisely the upper sets U \subseteq X satisfying x \in U and x \leq y imply y \in U. This topology is T_0 if and only if the preorder is antisymmetric, but in general, it provides a coarsest topology compatible with the preorder's structure.[10][11] Monotone functions between preordered sets preserve the relation: a map f: (X, \leq_X) \to (Y, \leq_Y) is monotone if x \leq_X x' implies f(x) \leq_Y f(x'). Such functions are compatible with set operations like unions and intersections when restricted to ideals or filters, maintaining the closedness properties. If \leq is a reflexive relation on X, its transitive closure \leq^+—the smallest transitive relation containing \leq—forms a preorder on X.[12] This construction ensures reflexivity is inherited and transitivity is enforced, yielding the minimal preorder extension.[12]Relations to other order structures
Connection to partial orders
A partial order on a set X is a preorder that additionally satisfies antisymmetry: if x \leq y and y \leq x, then x = y.[13] Thus, every partial order is a preorder, but the converse does not hold in general, as preorders need not be antisymmetric./01%3A_Generative_Effects_-_Orders_and_Adjunctions/1.01%3A_What_is_Order) In a preorder (X, \leq), the relation of indifference defined by x \sim y if and only if x \leq y and y \leq x is an equivalence relation on X./01%3A_Generative_Effects_-_Orders_and_Adjunctions/1.01%3A_What_is_Order) This equivalence arises because reflexivity and transitivity of \leq imply that \sim is reflexive, symmetric, and transitive.[13] The quotient set X / \sim, consisting of the equivalence classes = \{ z \in X \mid z \sim x \}, inherits a partial order from the preorder via \leq if and only if x \leq y.[13] This induced relation is reflexive and transitive, as these properties lift from the original preorder./01%3A_Generative_Effects_-_Orders_and_Adjunctions/1.01%3A_What_is_Order) Moreover, it is antisymmetric: if \leq and \leq, then x \leq y and y \leq x, so x \sim y and thus =.[13] A concrete example is the preorder on the set H of all humans on Earth, ordered by their English names alphabetically: p \leq q if the name of p precedes or equals that of q in dictionary order.[6] This relation is reflexive (every name equals itself) and transitive (alphabetical order preserves transitivity), but not antisymmetric, as distinct people can share the same name (e.g., two individuals named "John Smith" satisfy mutual comparability but are unequal).[6] The indifference relation identifies people with identical names, so the equivalence classes are the sets of individuals sharing a name; the quotient H / \sim is the set of distinct names, partially ordered by alphabetical precedence, which is antisymmetric.[6]Connection to strict partial orders
A strict partial order on a set is a binary relation that is irreflexive and transitive.[14] Irreflexivity ensures that no element is related to itself (x \not< x for all x), while transitivity requires that if x < y and y < z, then x < z. Such relations are also asymmetric, meaning that if x < y, then it cannot be that y < x.[14] Given a preorder \leq on a set, a corresponding strict partial order < can be induced by defining x < y if and only if x \leq y and not y \leq x.[15] This construction yields a relation that is irreflexive, since reflexivity of \leq implies x \not< x (as y \leq x holds when y = x), and transitive, because if x < y and y < z, then x \leq z follows from transitivity of \leq, while the negation of z \leq x arises from the chain of negations and transitivity preventing cycles.[16] The induced strict partial order is not necessarily total, as pairs of elements may remain incomparable if neither direction holds under the strict definition. It avoids cycles due to the underlying transitivity of the preorder, ensuring acyclicity. However, when the preorder features non-trivial equivalence classes—where elements x and y satisfy x \leq y and y \leq x but x \neq y—the strict order collapses these classes, rendering such elements incomparable under <. For instance, in a preorder where all elements are equivalent, the induced strict order relates no pairs at all.[16]Inducement and correspondence
Given a strict partial order < on a set X, the relation \leq defined by x \leq y if and only if x < y or x = y is a preorder on X, as it is reflexive and transitive.[17] This construction adds reflexivity to the irreflexive strict partial order while preserving transitivity.[17] Conversely, every preorder \leq on X induces an equivalence relation \sim defined by x \sim y if and only if x \leq y and y \leq x.[18] The quotient set X/{\sim} consists of the equivalence classes under \sim, and these classes form a partition of X.[18] On this quotient, the relation defined by \leq if and only if x \leq y (where and denote equivalence classes) is a partial order.[18] The strict partial order on the quotient is then given by < if and only if \leq and \neq.[18] This establishes a bijection between the set of all preorders on X and the set of pairs consisting of an equivalence relation \sim on X together with a strict partial order < on the quotient X/{\sim}.[18] The map sending a preorder \leq to the pair (\sim, <), where \sim is the induced equivalence and < is the induced strict partial order on X/{\sim}, is this bijective correspondence.[18] A preorder on X is order-isomorphic to a partial order if and only if it is antisymmetric, in which case the equivalence relation \sim consists of singleton classes and the quotient map is an order-isomorphism to the partial order itself.[18]Structural representations
Preorders as partial orders on partitions
A fundamental representation of preorders identifies them with partial orders defined on partitions of the underlying set. Specifically, for a preorder \leq on a set X, define the indifference relation \sim by x \sim y if and only if x \leq y and y \leq x; this \sim is an equivalence relation on X. The quotient set X / \sim consists of the equivalence classes = \{ y \in X \mid y \sim x \}, forming a partition of X. There exists a bijection between the set of all preorders on X and the set of pairs ( \sim, \preceq ), where \sim is an equivalence relation on X and \preceq is a partial order on the quotient X / \sim.[19] The construction proceeds by lifting the preorder to the quotient. Define \preceq if and only if x \leq y. This relation \preceq is well-defined because if [x'] = and [y'] = , then x' \sim x and y' \sim y, so x' \leq y holds if and only if x \leq y (by transitivity and reflexivity of \leq, combined with symmetry of \sim). Moreover, the original preorder recovers via x \leq y if and only if \preceq . Conversely, given an equivalence \sim and partial order \preceq on X / \sim, the preorder on X is induced by setting x \leq y if and only if \preceq ; this is reflexive and transitive due to the properties of \sim and \preceq.[19] This decomposition is unique up to isomorphism: the equivalence relation \sim is uniquely determined as the symmetric kernel of \leq, and the partial order \preceq is the unique relation on the quotient making the quotient map a preorder homomorphism. Any other pair ( \sim', \preceq' ) yielding the same preorder must satisfy \sim = \sim' and an isomorphism between (X / \sim, \preceq) and (X / \sim', \preceq') preserving the induced preorder. To confirm \preceq is a partial order, reflexivity follows since x \leq x implies \preceq , and transitivity holds because if \preceq and \preceq , then x \leq y and y \leq z, so x \leq z by transitivity of \leq, yielding \preceq . Antisymmetry is verified using transitivity of \leq: suppose \preceq and \preceq ; then x \leq y and y \leq x, so x \sim y and thus = .[19]Equivalence classes and quotients
In a preorder (X, \leq), the relation \sim defined by x \sim y if and only if x \leq y and y \leq x is an equivalence relation on X.[20] The equivalence class of an element x \in X is the set = \{ y \in X \mid x \sim y \}, and these classes form a partition of X.[20] Each equivalence class $$ is convex in the preorder, meaning that if a, b \in and a \leq z \leq b for some z \in X, then z \in . The set of equivalence classes X / \sim inherits a partial order from the preorder on X, defined by \leq if and only if x \leq y. This relation is well-defined because if x' \sim x and y' \sim y, then x' \leq y' follows from the reflexivity and transitivity of \leq.[20] The resulting structure (X / \sim, \leq) is antisymmetric, as \leq and \leq imply x \sim y, so =, and it preserves the monotonicity properties of the original preorder.[20] This quotient construction represents the preorder as a partial order on its partition into equivalence classes.[21] Common operations on preorders include the product preorder and subspace preorders. For preorders (X, \leq_X) and (Y, \leq_Y), the product preorder on X \times Y is defined componentwise: (x_1, y_1) \leq (x_2, y_2) if and only if x_1 \leq_X x_2 and y_1 \leq_Y y_2.[22] This ensures the product is reflexive and transitive, inheriting monotonicity from the factors. A subspace preorder arises by restricting the original preorder to a subset S \subseteq X, yielding the induced relation S \times S where a \leq_S b if and only if a \leq b in X.[20] For subsets A, B \subseteq X, one may induce a preorder on the power set by declaring A \leq B if and only if a \leq b for all a \in A and b \in B; this construction parallels Dedekind cuts in ordered fields and extends naturally to quotient structures where subsets represent equivalence classes.[20]Examples
Set theory and logic
In set theory, the power set of a set X, denoted \mathcal{P}(X), equipped with the subset inclusion relation A \leq B if and only if A \subseteq B, forms a partial order and thus a preorder. This relation is reflexive, since every set is a subset of itself; transitive, as the subset relation preserves inclusion under composition; and antisymmetric, ensuring that if A \subseteq B and B \subseteq A, then A = B. For example, if X = \{1, 2\}, then \emptyset \leq \{1\} \leq \{1, 2\}, illustrating a chain within this structure.[23] In logic, the set of logical formulas in a given formal system can be preordered by semantic entailment, where \phi \leq \psi if and only if \phi logically entails \psi, denoted \phi \models \psi. This relation is reflexive, as every formula entails itself, and transitive, since if \phi \models \psi and \psi \models \chi, then \phi \models \chi. However, it is generally not antisymmetric, as distinct formulas may be equivalent under entailment in both directions, such as tautologically equivalent statements. This preorder captures the hierarchical structure of implications in deductive reasoning.[24]Graph theory
In graph theory, a preorder on a set of vertices can be represented by a directed graph (digraph) that is both reflexive and transitive. Reflexivity corresponds to the presence of self-loops at every vertex, ensuring that each element is related to itself, while transitivity means that if there is a directed path from vertex u to v and from v to w, then there is a direct edge from u to w. Such a digraph is sometimes called a transitive reflexive digraph. If the preorder is total, the corresponding digraph is a transitive tournament, where every pair of distinct vertices is connected by exactly one directed edge, and the structure remains reflexive and transitive.[25] A fundamental example of a preorder arising in digraphs is the reachability preorder, defined on the vertices of any directed graph G = (V, E). For vertices u, v \in V, u \leq v if there exists a directed path from u to v in G, including the trivial path of length zero for reflexivity (where u \leq u). This relation is reflexive by the empty path and transitive because the concatenation of paths forms a longer path. The reachability preorder captures the structural connectivity of the graph and is equivalent to the transitive closure of the adjacency relation augmented with self-loops. In finite digraphs, computing this preorder involves finding the transitive closure, which can be done efficiently using algorithms like Warshall's, though the focus here is on its order-theoretic properties rather than computation. The preorder dimension of a preorder \leq on a finite set is defined as the smallest number d such that \leq is the intersection of d total preorders (linear extensions) on the same set. A total preorder is a reflexive and transitive relation that is also total, meaning any two elements are comparable. This dimension measures the "complexity" of the preorder in terms of how many total preorders are needed to reconstruct it via intersection, analogous to the order dimension for partial orders but adapted to allow equivalence classes. For instance, if the preorder is already total, its dimension is 1. In general, the dimension is at most the square of the size of the set, providing an upper bound, though computing it exactly is NP-hard for many cases. Seminal work in decision theory and order theory has explored this concept, particularly in representing preferences without full antisymmetry. An illustrative example occurs in tournament graphs, which model pairwise comparisons such as competition outcomes. A tournament is a directed graph on n vertices where every pair of distinct vertices has exactly one directed edge between them. The "beats" relation, given by the edges (where an edge from u to v means u beats v), is a total irreflexive relation. Its transitive closure, augmented with reflexivity (self-beats via empty path), yields a total preorder on the vertices, ranking them by dominance: u \leq v if there is a directed path from u to v, indicating u can "reach" or dominate v through a chain of victories. In a transitive tournament (a linear hierarchy with no cycles), this preorder is a total order. However, in general tournaments with cycles, equivalence classes emerge for mutually reachable players, forming a total preorder structure. This construction highlights how preorders generalize rankings in competitive settings beyond strict orders.Computer science
In computer science, preorders provide a foundational structure for modeling reflexive and transitive relationships in various computational domains, such as dependency resolution, type systems, and program analysis. Unlike strict partial orders, preorders allow for equivalence classes where elements are indistinguishable under the relation, enabling flexible approximations of real-world constraints like task indifference or type compatibility. This reflexivity and transitivity make preorders suitable for scenarios where exact antisymmetry is unnecessary or computationally burdensome.[26] Topological sorting extends naturally to preorders by first quotienting the preorder into an induced partial order on equivalence classes, then computing a linear extension that respects the dependencies. In scheduling applications, this models task dependencies where a task may depend on itself (reflexively) or form indifferent groups; for instance, in build systems like Make, a preorder captures compilation orders where equivalent modules can be processed in any order within their class, ensuring prerequisites complete before dependents. Algorithms like Kahn's or DFS-based topological sort, adapted via quotienting, yield valid execution sequences, preventing cycles and optimizing parallel execution where possible.[26][27] In type inference for programming languages, subtyping relations are often formalized as preorders to capture reflexive subtype compatibility (every type subtypes itself) and transitive inheritance hierarchies. Width subtyping exemplifies this in record types: a record with additional fields subtypes one with a subset of matching fields, as the narrower record can "forget" extraneous data without violating safety. For example, in languages like OCaml or Scala, the type{name: [String](/page/String), age: [Int](/page/Int)} subtypes {name: [String](/page/String)}, allowing functions expecting the simpler record to accept the richer one via subsumption. This preorder structure supports sound type checking during inference, ensuring compatibility without requiring full antisymmetry.[28]
Abstract interpretation leverages preorders to approximate program semantics over abstract domains, where the relation defines sound over-approximations of concrete behaviors. Widening operators, designed within this framework, accelerate convergence by inflating approximations monotonically along the preorder, ensuring fixed-point computation terminates despite infinite state spaces. For instance, in analyzing loop invariants, a preorder on numerical domains (e.g., intervals) allows widening to bound unstable values, as in polyhedral analysis for detecting buffer overflows. Seminal work formalizes these preorders for trace semantics, using prefix orders to relate partial execution sequences and guarantee that abstract transformers preserve concrete reachability.[29]
File system directories illustrate preorders concretely under path inclusion, where a directory path p relates to q if p is a prefix of q (reflexive for equal paths, transitive via concatenation). This preorder models the hierarchical structure: the root "/" includes all subpaths, and equivalence classes group paths with identical contents (e.g., symlinks). In POSIX systems, path resolution respects this relation for operations like traversal or mounting, enabling efficient querying of nested dependencies without enforcing strict uniqueness.[30][31]
Category theory
In category theory, a preorder on a set X can be viewed as a category where the objects are the elements of X, and there is a unique morphism from x to y if and only if x \leq y; the composition of morphisms corresponds to the transitivity of the preorder relation.[32][33] Such categories are known as thin categories, characterized by having at most one morphism between any pair of objects; preorders are precisely the thin categories arising from preordered sets.[32][2] Functors between these categories induced by preorders correspond exactly to monotone maps, which are functions that preserve the preorder relation: if x \leq y, then f(x) \leq f(y).[34][35] For example, in the category associated to a poset (a preorder satisfying antisymmetry), the hom-sets consist of either a single morphism (when x \leq y) or are empty (otherwise), reflecting the partial order structure.[32][2]Constructions
Extending preorders
One method to extend a preorder is through the Dedekind–MacNeille completion, which embeds the preorder into the smallest complete lattice containing an isomorphic copy of it while preserving the order. For a preorder (X, \leq), this involves first forming the quotient poset X / \sim, where \sim is the equivalence relation x \sim y if and only if x \leq y and y \leq x, and then constructing the Dedekind–MacNeille completion of this poset. The resulting lattice has all suprema and infima, and the original preorder embeds order-reflectively into it via the quotient map followed by the canonical embedding.[36] Linear extensions provide another way to enlarge a preorder to a total preorder compatible with the original relation. A total preorder \leq' on X is a linear extension of (X, \leq) if x \leq y implies x \leq' y for all x, y \in X. The generalized Szpilrajn extension theorem guarantees that every preorder admits such an extension, obtained constructively using Zorn's lemma on chains of total preorders. In choice theory, linear extensions model complete and transitive preference relations that refine incomplete or partial preferences, facilitating representation theorems for utility functions and social choice mechanisms.[37] Free completions generate the minimal extension of a preorder closed under specified operations, such as forming unions or joins. For instance, the free join-completion of a preorder (X, \leq) is the smallest join-semilattice containing X as a subposet, where new elements represent formal finite joins, and the order extends the original by defining a \leq b if every generator of a is below some generator of b. This construction preserves existing joins in the preorder and is universal among join-preserving extensions.[38] The upset completion specifically adds formal joins to a preorder while structuring the extension around upsets. For a preorder (X, \leq), the upset completion consists of elements from X augmented by formal join symbols j(S) for subsets S \subseteq X, with the order defined such that x \leq j(S) if x belongs to the upset generated by S, and j(S) \leq y if the upset of y contains S. This yields a join-complete extension where: j(S) = \bigvee_{s \in S} s with the upset \uparrow j(S) coinciding with the upset generated by S.[38]Generating preorders
One common method to generate a preorder from a binary relation is by taking its transitive closure, provided the original relation is reflexive. A binary relation R on a set X is reflexive if x R x for all x \in X; the transitive closure of R, denoted R^+, is the smallest transitive relation containing R. Since reflexivity is preserved under transitive closure, R^+ is both reflexive and transitive, hence a preorder.[4][39] Another construction involves the lexicographic product of preorders. Given preorders (A, \leq_A) and (B, \leq_B), the lexicographic product preorder on the Cartesian product A \times B is defined by (a_1, b_1) \leq (a_2, b_2) if either a_1 <_A a_2 (where <_A is the strict part of \leq_A), or a_1 =_A a_2 and b_1 \leq_B b_2 (with =_A denoting the equivalence induced by \leq_A). This extends naturally to finite products of preorders, yielding a preorder on the resulting product set that prioritizes the first coordinate.[40] Certain preorders, known as interval orders, can be generated via interval representations. Interval orders are partial orders; a preorder is representable as an interval order if its quotient poset (by the equivalence relation) is an interval order. To each element x in the set, assign a closed interval I(x) = [l(x), r(x)] on the real line such that x \leq y if and only if x = y or r(x) \leq l(y). This ensures reflexivity and transitivity under the interval condition. Not all preorders admit such representations, but those that do are precisely the interval preorders.[41] Preorders can also be generated from strict partial orders by adding reflexivity. A strict partial order < on a set X is irreflexive and transitive; the corresponding preorder \leq is obtained by setting x \leq y if x < y or x = y. This ensures reflexivity while preserving transitivity.[39]Interval orders
An interval order is a partial order that can be represented by assigning to each element an interval on the real line such that the order relation corresponds to the precedence of intervals. Specifically, a partial order \leq on a set X is an interval order if there exists a family of intervals \{I_x = [\inf(I_x), \sup(I_x)] \mid x \in X\} with \inf(I_x) \leq \sup(I_x) for all x, such that for all distinct x, y \in X, x < y if and only if \sup(I_x) \leq \inf(I_y). The full relation includes equality for reflexivity. For preorders, this extends by quotienting to the associated partial order. This representation captures orders where incomparability arises from overlapping intervals. A variant known as unit interval orders restricts the representation to intervals of fixed unit length, corresponding to semiorders.[41] Interval orders admit a forbidden subposet characterization due to Fishburn's theorem, which states that a partial order is an interval order if and only if it contains no induced $2+2 subposet. The $2+2 configuration consists of four distinct elements a, b, c, d such that a < b, c < d, and there are no other comparability relations among them, forming two disjoint incomparable 2-chains.[42] This characterization highlights the structural avoidance of certain incomparable pairs that cannot be realized by interval representations. The incomparability graph of an interval order is an interval graph.[43] Key properties of interval orders include their connection to order dimension: they coincide with posets of interval dimension 1, meaning the poset can be realized as a single interval order without intersection of multiple linear extensions in that form. These properties make interval orders particularly amenable to algorithmic recognition and representation, often via constructing the intervals from the order relations. A representative application of interval orders arises in scheduling problems, where tasks are modeled as intervals representing their start times and durations on a timeline, and the precedence relation x \leq y holds if the end of task x does not exceed the start of task y, ensuring no overlap violations in resource allocation.[44] This setup allows for efficient precedence constraint satisfaction in non-preemptive scheduling.Applications
Mathematical uses
In choice theory, preference relations are commonly modeled as preorders, which are reflexive and transitive binary relations on a set of alternatives or lotteries.[45] A key result is the von Neumann-Morgenstern expected utility theorem, which states that if a preference relation ≽ on the set of probability distributions over outcomes is a complete preorder (i.e., total, satisfying completeness alongside reflexivity and transitivity) and fulfills the independence axiom—where mixing a preferred option with a third option preserves the preference—and continuity axiom, then there exists a utility function u such that the expected utility \mathbb{E} represents the preferences: p \succsim q if and only if \sum u(x_i) p_i \geq \sum u(x_i) q_i for distributions p, q.[45] This framework underpins rational choice axioms, ensuring that choices are consistent with maximizing expected utility under uncertainty.[46] In topology, preorders induce structures like the Scott topology on directed complete partial orders (dcpos), which are posets (antisymmetric preorders) that are complete for directed suprema.[47] The Scott topology on a dcpo D has as open sets the upper subsets U \subseteq D (i.e., x \in U, y \geq x implies y \in U) that are inaccessible by directed sups: if a directed subset S \subseteq D has \sup S \in U, then S \cap U \neq \emptyset.[48] This topology, introduced by Dana Scott in the context of domain theory for denotational semantics of computation, equips dcpos with a T_0 structure where the specialization preorder coincides with the original order: x \leq y if and only if every Scott-open neighborhood of x contains y.[49] It facilitates continuous function spaces and fixed-point constructions essential for solving domain equations in semantics.[50] In algebra, congruence relations on algebraic structures can be viewed through the lens of compatible preorders, particularly in ordered or quasiordered varieties.[13] A preorder \leq on an algebra is compatible if it preserves operations: for a binary operation f, a \leq a', b \leq b' implies f(a,b) \leq f(a',b'). Such preorders generalize standard congruences (which are equivalences) to ordered settings, like in ordered groups or lattices, where they induce quotient structures that retain algebraic properties; for instance, in lattice theory, a compatible preorder determines join-irreducible elements and preserves meet-join operations in quotients.[51] This approach is crucial for studying congruence extension properties and modular varieties. Recent advancements in homotopy type theory (HoTT), a foundational framework developed since the 2010s, incorporate preorders to synthetically model domain-theoretic concepts without relying on classical axioms. In univalent foundations, preorders serve as a basis for directed complete posets, enabling constructive proofs of Scott continuity for functions and existence of least fixed points via the Knaster-Tarski theorem in a synthetic setting. For weak orders (total preorders), HoTT's higher inductive types allow encoding of homotopy-invariant notions, such as paths representing equivalences between ordered elements, facilitating applications in synthetic topology and guarded recursion.[52] This integration bridges order theory with homotopy, supporting predicative mathematics in type-theoretic proofs.Computational uses
In constraint satisfaction problems (CSPs), preorders are employed to model preferences over solution assignments, guiding variable ordering heuristics during backtracking search to prioritize more preferred partial solutions. For instance, in conditional preference networks (CP-nets), which induce a preorder on the set of possible outcomes based on user-specified preferences, variable ordering strategies propagate constraints while respecting the preorder to efficiently explore the search space and avoid suboptimal branches. This approach enhances the efficiency of backtracking by selecting variables that minimize the violation of preference orders, as demonstrated in constrained CP-nets where preorder-aware propagation reduces the computational overhead compared to standard CSP solvers.[53][54] In machine learning, particularly clustering tasks, preorders capture similarity relations among data points by combining clustering structures with partial orders, enabling robust grouping under uncertainty or incomplete information. A notable method is preordering, which hybridizes correlation clustering—where data points are partitioned based on pairwise similarities—with partial ordering to form a preorder that refines clusters by imposing transitive preferences on intra-cluster similarities. This is particularly useful in kernel-based methods, where the kernel function defines a similarity measure that can be extended to a preorder via reflexive and transitive closure, facilitating hierarchical or preference-aware clustering in high-dimensional spaces. For example, tree-based similarity learning algorithms leverage preorders derived from subtree structures to rank pairwise similarities, improving clustering accuracy on datasets with ordinal relationships.[55][56] Database query optimization utilizes preorders to evaluate and select efficient join orderings, especially for acyclic queries, by defining a partial order on possible execution plans based on cost estimates. In this framework, a relation ≥_r over join trees is established as a preorder (reflexive and transitive), allowing dynamic programming algorithms to prune dominated plans and focus on minimal-cost orderings that respect join dependencies. This preorder-based optimization reduces the exponential complexity of enumerating all possible join sequences, with empirical results showing significant speedups in query execution times for multi-table joins in relational databases.[57] In AI planning, action preconditions often induce a preorder on feasible action sequences, where one action precedes another if its effects satisfy the preconditions of the successor, ensuring plan validity and feasibility. This preorder structure supports partial-order planning by identifying causally linked actions without enforcing a total linearization early in the process, allowing for more flexible plan generation. For example, in preference-based planning, the preorder over plans incorporates precondition satisfaction to rank feasible sequences, enabling the synthesis of optimal plans under resource constraints.[58][59]Other domains
In economics, preorders model indifference relations in utility theory, extending beyond strict preferences to capture incomplete or partial comparisons between alternatives. An incomplete preference relation, which forms a preorder, can be represented by a vector-valued utility function where indifference holds if the utility vectors are equal, and one alternative is preferred if its utility dominates the other componentwise. This representation is possible for "near-complete" preorders with finite width, allowing economic agents to express uncertainty or incomparability without violating transitivity. In linguistics and natural language processing, semantic entailment is conceptualized as a preorder on sentences, where one sentence entails another if its meaning implies the latter, ensuring reflexivity (a sentence entails itself) and transitivity (if A entails B and B entails C, then A entails C). This framework uses model-theoretic semantics with a partial order on truth values, defining entailment as the premise's denotation being less than or equal to the hypothesis's in all intended models. Such modeling supports annotation schemes for textual entailment tasks, achieving high coverage (over 80%) in datasets like RTE corpora by linking natural language constructions to an interpreted lexicon.[60] In social sciences, ranking systems aggregate individual preorders into collective decisions, with the Kemeny-Young method extended to partial rankings by minimizing a distance metric between voter preferences and a consensus ranking. This generalization handles incomplete preferences common in group decision-making, such as surveys where respondents provide partial orders, by optimizing agreement on comparable pairs while accounting for incomparabilities through deviation penalties. Applications include employer branding assessments, where aggregating partial rankings yields stable consensus hierarchies.[61]Enumeration
Counting preorders on finite sets
The number of preorders on an n-element set, denoted P(n), counts the distinct reflexive and transitive binary relations on that set. Every preorder arises from partitioning the set into equivalence classes (where elements are mutually related) and imposing a partial order on the quotient set of these classes. Consequently, P(n) can be expressed as P(n) = \sum_{k=1}^n S(n,k) \, Q(k), where S(n,k) is the Stirling number of the second kind (counting the ways to partition n labeled elements into k nonempty unlabeled subsets) and Q(k) is the number of partial orders on a k-element labeled set.[62] This summation leverages the set partition representation of preorders, with the product term accounting for the linear extensions within classes (via the partition) and the ordering of classes (via the poset). An alternative recursive approach derives from Möbius inversion applied to the incidence algebra of the lattice of equivalence relations or transitive relations, though the partition sum provides the primary enumerative tool. Computed values of P(n) for small n are as follows:| n | P(n) |
|---|---|
| 1 | 1 |
| 2 | 4 |
| 3 | 29 |
| 4 | 355 |
| 5 | 6,942 |
| 6 | 209,527 |
| 7 | 9,535,241 |
| 8 | 642,779,354 |