Simple examples of preorders that are not partial orders?

Question

What are some simple examples of preorders — that is, binary relations that are reflexive and transitive — that are not partial orders (and hence not total orders, either)?

I'm looking for a couple of examples that do not involve graph theory or other less basic ideas in math. And preferably examples simpler than the relation $\preccurlyeq$ on the power set of a given set that declares $A \preccurlyeq B$ iff there exists an injection from $A$ to $B$.

Answer 1

Any real function (let's say a "measure") $\mu:X\to\mathbb{R}$ defines a preorder on $X$ by $x\preceq y$ iff $\mu(x)\leq\mu(y)$. For this not to be a partial order, your measure must not be injective.

This can be almost anything. Couple examples:

• diameter of compact subsets of $\mathbb{R}^n$ is a preorder on them.
• volume of compact measurable subsets of $\mathbb{R}^n$ is a preorder on them.
• number of distinct divisors is a preorder on $\mathbb{N}$ (well, any arithmetic function defines a preorder);
• ...

In general, preorder is a very generic notion, so thinking out preorders is very easy.

Answer 2

Let $X$ denote the set of squares on a fixed plane. You can define the following preoder on $X$: $qRq'$ if and only if there exists an isometry $i$ such that $q'\supseteq i(q)$.

Answer 3

In this answer I do not provide simple examples of preorders, but enable you to find them on base of simple examples of partial orders.

You can just start with a partial order $\langle B,\leq\rangle$ and a surjective function $\nu:A\to B$.

---

Then $\preceq$ defined by: $$x\preceq y\iff \nu(x)\leq \nu(y)$$ is a preorder on $A$.

---

Actually every preorder can be described this way. If you start with some preorder $\langle A,\preceq\rangle$ then you can take $B:=A/\sim$ where $\sim$ is the equivalence relation on $A$ characterized by: $$x\sim y\iff x\preceq y\ \wedge y\preceq x$$ For $\nu:A\to B$ you take the natural function prescribed by $a\mapsto[a]$.

---

This preorder is not a partial order if and only if $\nu$ is not injective.