1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Don't you think that category theory is a little bit overkill here? You should keep in mind that we are not on Math Overflow, here. Many users in this forum are not familiar with category theory. I'd think it would be helpful to answer the question in the language of order relations and lattices first. Afterwards you may provide the category theoretical point of view. $\endgroup$
    – Keinstein
    May 16 '14 at 5:39

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.