3
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Alas, the first two of these examples -- taking $\mu$ to be diameter or volume of compact subsets of $\mathbb{R}^n$ -- are hardly ones that avoid "other less basic ideas in math". (In fact, I'm writing about order relations as preparation for an exposition of topology.) And even the example with $\mu$ being the number of distinct divisors of a positive integer requires knowing that "number of elements" is a well-defined concept for finite sets (whose proof is not entirely trivial!). $\endgroup$ – murray Apr 4 '17 at 18:54
  • 1
    $\begingroup$ OK, so probably the simplest example of this kind would be for $X = \mathbb{R}$ and $\mu(x) = x^2$; or the same but restricted to $X = \mathbb{Z}$. $\endgroup$ – murray Apr 4 '17 at 19:05
  • $\begingroup$ @murray Yes, that works, too. $\endgroup$ – yo' Apr 5 '17 at 8:27
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Since I'm trying to write about preorders before getting to partial orders, this kind of example rather begs the question, I'm afraid. $\endgroup$ – murray Apr 4 '17 at 18:57
  • $\begingroup$ This answer overlaps to some extent with that of @yo', although for the latter the function need not be surjective. $\endgroup$ – murray Apr 4 '17 at 19:08
0
$\begingroup$

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)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Isometry of subsets of the plane is already a pretty sophisticated notion. $\endgroup$ – murray Jul 4 '17 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.