Lattice from Preorder

Question

I have seen many examples defining a lattice over a partially ordered set $(P, \sqsubseteq)$ together with a greatest lower bound $\sqcap$, a least upper bound $\sqcup$ and a top $\top$, and bottom element $\bot$.

The relation $\sqsubseteq$ is a partial ordering, hence it is reflexive, transitive and anti-symmetric.

I have another ordering operator $\preceq$ that is only reflexive and transitive. It is therefore a preorder, $(Q, \preceq)$.

1) Can I build a lattice from the preorder $(Q, \preceq)$? (assuming I do have $\top$, $\bot$, GLB and LUB)

2) What properties of the ordering operator does the lattice depend on?

Answer 1

Some suggestions:

• If you have antisymmetry, then your preorder is actually a partial order and it's easy to construct a corresponding lattice.
• If you don't have antisymmetry, then there exists a pair $a,b$ such that $a \preceq b$ and $b \preceq a$. How would you define $\{a,b\}$? In fact $\preceq$ could be the full relation $Q \times Q$ (i.e. it is reflexive and transitive).
• One way is to define $x \sim y$ if and only if $x \preceq y \land y \preceq x$. Then $\preceq$ indicates a partial order on $Q/\sim$, and then you can form a lattice.
• Another way is to modify the preorder, e.g. for $a\preceq b$ and $b\preceq a$ you can pick which one of $\{a,b\}$ will be the upper bound. However, you need to do it consistently. The best way is to construct a partial order from your preorder:
  1. Define $\sim$ as above.
  2. Let $\sqsubseteq$ be any total order on $Q$ (in fact we only want total order inside any equivalence class of $\sim$).
  3. Set $f : Q \to (Q/\sim)\times Q$ to $$f(x) = \big\langle [x]_\sim, x \big\rangle.$$
  4. Create a lexicographic order $\preceq_\mathsf{lex}$ on $(Q/\sim)\times Q$ from $(\preceq/\sim)$ and $\sqsubseteq$.
  5. Define $x \preceq_\mathsf{PO} y$ as $f(x) \preceq_\mathsf{lex} f(y)$.
  6. Be aware that $x \preceq_\mathsf{PO} y$ is a different thing than $\preceq$, e.g. there might be some issues with completeness, etc.

I hope this helps $\ddot\smile$

Answer 2

For 1)

You can view a preorder as a category where there is at most one arrow between any two objects. Equivalently, this is a category enriched in the monoidal category $\textbf{2}$ (itself a partial order), which looks like $0 \rightarrow 1$, where the product is $\wedge$. For this preorder to be a 'lattice' would mean that it has all finite products (GLB) and coproducts (LUB). Each preorder is equivalent (as a category) to a partial order; given a preorder $(Q, \preceq)$, form a partial order $(Q/\sim, \leq)$, where $a \sim b \iff a \preceq b$ and $b \preceq a$. Since equivalences preserve products and coproducts, if $Q$ was a 'lattice', then $Q/\sim$ will be a lattice in the usual sense.

Answer 3

There is another way not mentioned of completing a preorder (or any binary relation for that matter) to form a lattice. The main ingredient in this construction is the notion of an (antitone) Galois connection.

Definition: suppose $(P, \leq)$ and $(Q, \sqsubseteq)$ are partial orders. Then, an antitone Galois connnection is a pair of maps $$ f_\ast: P \leftrightarrows Q: f^\ast $$ such that $f_\ast(x) \sqsupseteq y$ if and only if $f^\ast(y) \geq x$.

Given a relation $R \subseteq X \times Y$ there is a Galois connection between the powersets $2^X$ and $2^Y$, $$ R_\ast: 2^X \leftrightarrows 2^Y: R^\ast $$ given by $$ R_\ast(\sigma) = \{y \in Y: (x,y) \in R~\forall~x \in \sigma \}, $$ and $$ R^\ast(\tau) = \{x \in X: (x,y) \in R~\forall y \in \tau \}. $$

Then, it follows (some work needed) that $$ L(R):=Fix(R^\ast R_\ast) $$ is a lattice.

As a special case, if $X=Y= P$, a preorder $\leq$, then $L(\leq)$ is a lattice. I believe in this case $P$ order embeds into $L(\leq)$.

This type of construction appears over and over again in certain corners mathematics. In the case of a general relation, it’s called a formal concept lattice. If the relation is a poset, it’s the Dedekind-MacNeille completion. More general still is a analogous construction in category theory where relations are replaced with gadgets called profunctors. Then, it’s Isbell completion.