# On preorders

Paul Brunet

► To cite this version:

Paul Brunet. On preorders. 2025. hal-05188725

HAL Id: hal-05188725

https://hal.science/hal-05188725v1

Preprint submitted on 27 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On preorders

Paul Brunet

July 27, 2025

**Notations** A binary relation $x : A \to B$ is a subset of $A \times B$. We denote the set-theoretic inclusion of relations by $\to$, writing $x \to y$ instead of $x \subseteq y$. Similarly, equality of relations is denoted by $\leftrightarrow$. Given sets A, B, C, and relations $x, x'$ : $A \to B$ and $y : B \to C$, we define the following constants and operations: $l_A : A \to A$ is the identity (diagonal) relation over A, $x' : B \to A$ is the converse of $x$, $x + x' : A \to B$ is the set-theoretic union of $x$ and $x'$, and $x ; y : A \to C$ is the sequential composition of $x$ and $y$, containing all pairs $(a, c)$ such that there is some $b \in B$ such that $(a, b) \in x$ and $(b, c) \in y$. If $s : A \to A$ is a relation, its reflexive-transitive closure is written $s^*$. Given $z : A \to C$, the (left-)residual of $z$ by $x$, written $x \setminus z : B \to C$, is the set of pairs $(b, c)$ such that for every $a \in A$, $(a, b) \in x$ entails $(a, c) \in z$. This operator has can also be defined by the following equivalence:

$$ \forall x, y, z, y \to x \setminus z \Leftrightarrow x ; y \to z. \qquad (1) $$

A dual operator $z / y$, satisfying $x \to z / y$ iff $x ; y \to z$ can be defined by $z / y := ((y^-) \setminus (z^-))^-$.

A preorder is a reflexive and transitive relation $x : A \to A$, over some set A. In relation algebra, this is captured by the following axioms:

$$ l_A \to x \qquad (\text{reflexivity}) $$

$$ x ; x \to x \qquad (\text{transitivity}) $$

The class of preorders is stable by converse, and for any relation $x : A \to B$, both $x \setminus x$ and $x / x$ are preorders, respectively over B and A. We may further observe that for any preorder $y : A \to A$, the relation $y$ is equivalent to $y \setminus y$ (and to $y / y$). Therefore this may be used as an alternative axiomatisation of preorders: a relation $x$ is a preorder iff $x \leftrightarrow x \setminus x$.

A similar axiomatisation already exists: preorders may be defined in terms of reflexive transitive closure: a relation $x : A \to A$ is a preorder iff $x \leftrightarrow x^*$. Therefore, in the case of preorders, $x^* \leftrightarrow x \setminus x \leftrightarrow x / x$. This is remarkable, given that for arbitrary relations $x : A \to B$, the preorders $x \setminus x$ and $x / x$ have different types, and $x^*$ is undefined unless $A = B$.

Consider now the question of composing preorders: is the result a preorder itself? It turns out this question is equivalent to a form of commutativity between the orders. Indeed, the composite $x ; y$ of two preorders $x, y$ over the same set A is a preorder if and only if $y ; x \to x ; y$. Further, we can prove that it is also equivalent to the following identity:

$$ x ; y \leftrightarrow (x + y)^*. $$
# Proofs

**Lemma 1.** *The converse of a preorder is a preorder.*

*Proof.* Let $x: A \to A$ be some preorder. We check that $x^-$ satisfies the two axioms:

*   **reflexivity:** since $1_A \to x$ and $1_A \leftrightarrow 1_A$, we get by monotonicity of $\to$ that

$$1_A \leftrightarrow 1_A \to x^-.$$

*   **transitivity:** since $x; x \to x$ by monotonicity of $\to$ and the fact that for any relations $y, z$ we have $y^-; z^- \leftrightarrow (z; y)^-$, we get:

$$x^-; x^- \leftrightarrow (x; x)^- \to x^-.$$

☐

## Preorders and residuals

**Lemma 2.** *For any relation $x: A \to B$, $x \setminus x$ and $x / x$ are preorders.*

*Proof.* We check both axioms:

*   **reflexivity of $x \setminus x$: $1 \to x \setminus x \Leftrightarrow x \to x$**

*   **transitivity of $x \setminus x$: $(x \setminus x); (x \setminus x) \to x \setminus x \Leftrightarrow x; (x \setminus x); (x \setminus x) \to x$**

So for any relation $x$, $x \setminus x$ is a preorder, meaning in particular $x^- \setminus x^-$ is a preorder. Since the converse of a preorder is a preorder, the relation

$$(x^- \setminus x^-)^- \leftrightarrow (x^-)^- / (x^-)^- \leftrightarrow x / x.$$

is a preorder.

☐

**Lemma 3.** *For every preorder $x: A \to A$, we have*

$$x \setminus x \leftrightarrow x \leftrightarrow x / x.$$

*Proof.* First, we show $x \leftrightarrow x \setminus x$ by proving both inclusions:

*   $x \to x \setminus x \Leftrightarrow x; x \to x$ which is transitivity;

*   $x \setminus x \leftrightarrow 1; x \setminus x \to x; x \setminus x \to x$ holds because $1 \to x$ is reflexivity.

So for every preorder $x \leftrightarrow x \setminus x$. Since the converse of a preorder is a preorder, it means that $x^- \leftrightarrow x^- \setminus x^-$. If we apply the converse to both sides we obtain $(x^-)^- \leftrightarrow (x^- \setminus x^-)^-$, therefore:

$$x \leftrightarrow (x^-)^- \leftrightarrow (x^- \setminus x^-)^- \leftrightarrow (x^-)^- / (x^-)^- \leftrightarrow x / x.$$

☐

## Preorders and reflexive transitive closures

**Lemma 4.** *For every $x: A \to A$, the relation $x^*$ is a preorder.*

*Proof.* Both implications:

*   $1_A \to 1_A + x; x^* \to x^*$

*   $x; x^* \to 1_A + x; x^* \to x^*$ therefore $x^*; x^* \to x^*.$

☐

**Lemma 5.** *A relation $x: A \to A$ is a preorder iff $x \leftrightarrow x^*$.*

*Proof.* First, observe that $x \to x^*$ always holds. We then proceed as usual:

*   If $x$ is a preorder, then $x; x \to x$, meaning $x; x^* \to x$. As such we derive $x^* \leftrightarrow 1; x^* \to x; x^* \to x$.

*   Assume $x \leftrightarrow x^*$. Then $x^*$ being a preorder means $x$ is a preorder.

☐
## Composition of preorders

**Lemma 6.** Given a pair of preorders $x, y$ over the same set $A$, $x$; $y$ is a preorder iff $y; x \to x; y$.

*Proof.* First, notice that $x$; $y$ is always reflexive, given that both $x$ and $y$ are:

$$1_A \leftrightarrow 1_A; 1_A \to x; y.$$

We now (hopefully) prove both implications.

* Right to left: since $x$; $y$ is reflexive, we only need to check transitivity:

$$x; y; x; y \to x; x; y; y \to x; y.$$

* Left to right: since $x$ and $y$ are reflexive and $x$; $y$ is transitive:

$$y; x \leftrightarrow 1_A; y; x; 1_A \to x; y; x; y \to x; y.$$

□

**Lemma 7.** Given a pair of preorders $x, y: A \to \mathcal{A}$, $x$; $y$ is a preorder iff $x$; $y \leftrightarrow (x+y)^*$.

*Proof.* We prove both implications.

* Assume $x$; $y$ is a preorder.

- $x$; $y \to (x+y)$; $(x+y) \to (x+y)^*$.

- First, we observe that $x+y \leftrightarrow (x;1)+(1;y) \to (x;y)$; $(x;y)$, so by transitivity $x+y \to x;y$. By monotonicity of $\to^*$ we obtain $(x+y)^* \to (x;y)^*$.

We now prove that $(x;y)^* \to x;y$. This is entailed by $(x;y)$; $(x;y) \to x;y$, which is transitivity.

* Assume $x$; $y \leftrightarrow (x+y)^*$. Since for any $z$, $z^*$ is a preorder, in particular $(x+y)^* \leftrightarrow x$; $y$ is a preorder. □