Preorder

In mathematics, order theory explores how different elements in a set relate to one another. A preorder, also known as a quasiorder, is a specific type of binary relation used to organize these elements. A binary relation is simply a rule that connects pairs of items from a set. To qualify as a preorder, this rule must satisfy two fundamental properties: reflexivity and transitivity. Reflexivity means that every element in the set must relate to itself. Transitivity means that if an element A relates to B, and B relates to C, then A must also relate to C.

The name preorder suggests that these relations are almost, but not quite, partial orders. The key difference lies in a property called antisymmetry. In a partial order, if A relates to B and B relates to A, then A and B must be the same element. Preorders do not require this. This allows for different elements to be related to each other in both directions without being identical. Because of this, preorders are more flexible than partial orders. They can describe relationships where items are distinct but share a similar status.

One natural way to understand this is through the "divides" relation between integers. We say $x$ divides $y$ if $y$ is a multiple of $x$. This is a preorder because every integer divides itself, satisfying reflexivity. It is also transitive because if $x$ divides $y$ and $y$ divides $z$, then $x$ must divide $z$. However, it is not antisymmetric. For example, $1$ divides $-1$, and $-1$ divides $1$, but $1$ and $-1$ are not the same number. This specific preorder is essential for defining the "least common multiple." In a standard number line, a "least" value might not exist for certain sets, but the preorder structure allows us to identify it.

Preorders are deeply connected to two other mathematical structures: equivalence relations and partial orders. An equivalence relation is a preorder that is symmetric, meaning if A relates to B, then B must relate to A. This creates groups of items that are treated as equal. A partial order is a preorder that is antisymmetric, which prevents circular relationships. Mathematically, any preorder can be broken down into a combination of these two ideas. You can take a preorder, group its elements into equivalence classes, and then apply a partial order to those groups. This creates a one-to-one correspondence between preorders and pairs consisting of a partition and a partial order.

We can visualize these relationships using directed graphs. In these diagrams, each element of the set is a vertex, or point, and each relation is a directed edge, or arrow, pointing from one vertex to another. A preorder can be drawn as a graph that may contain many disconnected components. If the preorder is symmetric, the graph behaves like an equivalence relation, where the direction of the arrows no longer matters. If the preorder is antisymmetric, the graph becomes a directed acyclic graph, meaning it contains no cycles or loops.

Preorders appear in many advanced fields, including logic and computer science. In formal logic, we can define a preorder based on consequence. If sentence A can be used to prove sentence B, we say A relates to B. This is reflexive because any sentence proves itself, and transitive because if A proves B and B proves C, then A proves C. The items that are related in both directions are called "logically equivalent." In computer science, preorders help experts study complexity. They use them to compare how much time or memory different programs require to complete a task.

In the study of topology, preorders help describe the structure of spaces. For example, every finite topological space creates a preorder on its points. This is known as the specialization preorder. In category theory, a specific type of category called a "thin category" is actually just a preorder. This shows how preorders serve as a foundational building block for much more complex mathematical systems. Whether studying the reachability of paths in a graph or the way functions grow, preorders provide a vital way to map the connections of the mathematical world.