A total preorder or linear preorder or preference relation or (non-strict) weak order is a preorder whose posetal reflection is a total order, or equivalently it is a preorder which is also a total relation:
In category theory, a total preorder is a thin category $C$ for which given two objects $x \in C$ and $y \in C$, there exists a morphism in either $\mathrm{hom}(x, y)$ or $\mathrm{hom}(y, x)$. In fact, every total preorder is an unbounded prelattice, a thin locally cartesian category whose opposite category is also locally cartesian.
A cotransitive preorder on a set $S$ is a preorder $\leq$ which satisfies cotransitivity/weak linearity:
Cotransitive preorders are total preorders.
Cotransitivity of $\leq$ says that for all $x \in S$ and $y \in S$, $x \leq x$ implies that $x \leq y$ or $y \leq x$, and reflexivity says that for all $x$, $x \leq x$ is always true. This implies that for all $x$ and $y$, $x \leq y$ or $y \leq x$ is always true, which is precisely the condition of totality. Since cotransitive preorders are preorders, this implies that cotransitive preorders are total preorders.
Cotransitive partial orders are total orders.
[TBD: figure out if total preorders are cotransitive preorders.]
Total orders are cotransitive partial orders.
Similar to total orders, one could make a distinction between the usual notion of total preorder, and strict total preorders?, which are the irreflexive version of total preorders, and are defined as a strict preorder which is weakly linear and asymmetric.
Using excluded middle, one can move between total preorders and strict total preorders using negation; that is, the negation of a total preorder is a strict total preorder and vice versa. Actually one usually swaps the order too, as follows:
To prove this, it's enough to see that the properties of a strict total preorder are dual to the properties of a total preorder, as follows:
strict total preorder | total preorder | |
---|---|---|
irreflexivity | reflexivity | |
asymmetry | totality | |
transitivity | weak linearity | |
weak linearity | transitivity |
In classical mathematics, the distinction between total preorders and strict total preorders is merely a terminological technicality, which is not always observed; more precisely, there is a natural bijection between the set of total preorders on a given set $S$ and the set of strict total preorders on $S$, and one distinguishes them by their notation.
In constructive mathematics, however, they are irreducibly different. To be specific, if one starts with a total preorder $\leq$ and defines $\lt$ as above, then weak linearity does not follow; and if one starts with a strict total preorder $\lt$ and defines $\leq$ as above, then totality does not follow. Nevertheless, at least $\leq$ will be a preorder, and least $\lt$ will be a strict preorder.
An example of a set with a total preorder are the dual rational numbers $\mathbb{Q}[\epsilon]/\epsilon^2$. The dual rational numbers have a strict weak order $\lt$ given by
for rational numbers $a$, $b$, $c$, and $d$. This strict weak order is not connected because $0 \neq \epsilon$, and thus the negation of the strict weak order, $a \leq b \coloneqq \neg(b \lt a)$, is not antisymmetric. However, $\leq$ is a total preorder, because the strict weak order $\lt$ is irreflexive, weakly linear, transitive, and asymmetric, which implies that $\leq$ is reflexive, transitive, and total.
More generally, any ordered local ring with strict weak order $\lt$ has a total preorder $\leq$ defined by negation of $\lt$. The quotient ordered field by the ideal of non-invertible elements results in a total preorder $\leq$ which is also a total order. In constructive mathematics one has to make sure that $\lt$ is also decidable.
Wikipedia, Total preorder
Wikipedia, Weak order
Last revised on December 26, 2023 at 04:33:22. See the history of this page for a list of all contributions to it.