Orders with no anti-symmetry requirement?

Question

A ordered/partially ordered set is required to satisfy the $x \leqslant y$ and $y \leqslant x$, $\implies x=y$ (antisymmetry) axiom. Are there any viable theories where this condition is weakened? Clearly if it is just simply dropped, the $\leqslant$ relation can be anything (any function from a set to an ordered set induces such relationship). Any sensible way to do this? Conceptually perhaps $x=y$ can be replaced with "$x$ is close to $y$", but how?

Answer 1

A reflexive, transitive relation is known as a preorder or quasi-order. There are lots of examples:

• The divisibility relation on the integers is a preorder. Indeed, for all $x,y,z \in \mathbb{Z}$ we have $x \mid x$ and if $x \mid y$ and $y \mid z$ then $x \mid z$. But it is not antisymmetric, since for instance $1 \mid {-1}$ and ${-1} \mid 1$, but $1 \ne {-1}$.

• Given a logical theory $T$, the relation on the set of $T$-sentences defined by $p \le q$ if $T$ proves $p \Rightarrow q$ is a preorder. However it is not generally antisymmetric; since distinct sentences may be provably equivalent in $T$.

• Given a topological space $X$, the relation on $X$ defined by $x \le y$ if $x \in U$ for all open sets $U$ containing $y$, is a pre-order. Indeed, $x$ is contained in every neighbourhood containing $x$, so $x \le x$; and if $x \le y$ and $y \le z$, then any open set containing $z$ contains $y$, and hence contains $x$, so that $x \le z$.

If $\le$ is a pre-order relation on a set $X$ then the relation $\sim$ on $X$ defined by $$x \sim y \Leftrightarrow x \le y \text{ and } y \le x$$ defines an equivalence relation on $X$, and $\le$ descends to a partial order relation on the quotient $X / {\sim}$ (i.e. the set of equivalence classes), defined by $$[x]_{\sim} \le [y]_{\sim} \Leftrightarrow x \le y$$ You can check easily that this is a well-defined partial order. (I suppose this is where 'preorder' comes from: it can be made into a partial order by taking a quotient.) For example

• In the case of divisibility on the integers, $\mathbb{Z} / {\sim}$ is (order-isomorphic to) the set of natural numbers with the divisibility relation (which is a partial order on $\mathbb{N}$).

• In the case of $T$-sentences, the quotient is called the Lindenbaum algebra, which has lots of nice properties.

Answer 2

As an extension of something that Clive touched on - these 'preorders' are equivalent to $A$-spaces: topological spaces where open sets are closed under arbitrary (not just finite) intersections (as well as arbitrary unions, as usual).

Clive has already spelled out one direction - given any topological space $X$, we can define a preorder on it by $x\le y$ if $x\in\text{Cl}(\{y\})$. This is called the specialization preorder on the space $X$.

Now we have to ask - given a set $X$ and a preorder $\le$ on $X$, is there always a topological space such that $\le$ is the specialization preorder on $X$? The answer is yes: take the open sets to be upper sets; i.e., those subsets $U\subset X$ such that for all $x,y\in X$:

$$X\in U,x\le y\Rightarrow y\in U$$

This topology is called the order topology corresponding to the preorder $\le$.

Now if we start with a space $X$, take the specialization preorder $\le$ on $X$ and form the order topology, we don't always end up with $X$ again: indeed, if $X=\mathbb R$ with the usual topology, then the preorder $\le$ is the discrete ordering ($x\le y\Leftrightarrow x=y$), since $\mathbb R$ is a $T_1$ space (singletons are closed), and the corresponding order topology is the discrete topology on $\mathbb R$.

However, if we restrict ourselves to $A$-spaces, we do get an equivalence. Note that a set with an order topoogy is always an $A$-space; indeed, if we start with an $A$-space, take the specialization preorder and then take the order topology, we end up back where we started.

You might like to go back and prove all of these assertions. They're not hard.

---

Example: clearly all finite topological spaces are $A$-spaces. What does this tell you about finite topological spaces?

---

It's always useful to consider the case when $\le$ is a full partial order. The $A$-spaces corresponding to partial orders are the $T_0$ $A$-spaces. Recall that a topological space is $T_0$ if any two points $x,y$ are topologically distinguishable: either there is an open set containing $x$ and not $y$, or there is an open set containing $y$ and not $x$.

In fact, we needn't restrict ourselves to $A$-spaces here: a topological space is $T_0$ if and only if its specialization preorder is a partial order.

Non-$T_0$ spaces (with the exception of the indiscrete topology) don't come up a lot, but they do arise naturally when we talk about pseudometrics. A pseudometric is like a metric, but we omit the requirement that $d(x,y)=0\Rightarrow x=y$ (if you like, this is the antisymmetry law for metrics). We can form a topological space in he same way we usually would with a true metric, but this space will not be $T_0$.

An example of a pseudometric: let $X$ be the space of all integrable functions on $[0,1]$, and define a metric by $$ d(f,g)=\int_0^1|f(x)-g(x)|dx $$

Then if $f$ and $g$ agree on a set of measure $1$, we will have $d(f,g)=0$, even if $f\ne g$. Form the topology in the usual way, and take the specialization preorder, and you have a preorder that isn't a partial order, arising in a semi-natural manner!