<p>Let $(P,\le)$ be a partially ordered set and $\preceq$ the Hoare pre-order on its subsets, i.e. for $X,Y\subseteq P$, $X\preceq Y$ iff $\forall x\in X:\exists y\in Y:x\le y$.</p>

<p>Let $\sim$ be the equivalence on the power set $2^P$ generated by $\preceq$, i.e. $X\sim Y$ iff $X\preceq Y$ and $Y\preceq X$.  Let $M=2^P/\mathord\sim$ be the quotient, then $\preceq$ passes to a partial order, also denoted $\preceq$, on $M$.</p>

<p>Is $(M,\preceq)$ a complete lattice?</p>

CC BY-SA 3.0
2015-05-05T13:58:52.307Z
As far as I can see, a union of a family of sets is its lub in $\preceq$, or am I missing something?
Emil Jeřábek
CC BY-SA 3.0
2015-05-05T14:03:40.273Z
In fact, $(M,\preceq)$ is apparently (isomorphic to) the complete lattice of downsets in $P$, as $X\preceq Y$ iff $X{\downarrow}\subseteq Y{\downarrow}$. This is an upside-down complete Heyting algebra.
Emil Jeřábek
CC BY-SA 3.0
2015-05-20T12:46:15.030Z
Thank you Emil, this looks right to me. But (next question) is it well-known? I'm not familiar with the old papers on domain theory, but it seems like something which should be in there.
Uli Fahrenberg
<partial-order><order-theory><lattice>
Completeness of the quotient of the power set lattice of a partial order induced by the Hoare pre-order
Uli Fahrenberg
# Completeness of the quotient of the power set lattice of a partial order induced by the Hoare pre-order

(Asked by: username_0 on 2015-05-05)

Let $(P,\le)$ be a partially ordered set and $\preceq$ the Hoare pre-order on its subsets, i.e. for $X,Y\subseteq P$, $X\preceq Y$ iff $\forall x\in X:\exists y\in Y:x\le y$.

Let $\sim$ be the equivalence on the power set $2^P$ generated by $\preceq$, i.e. $X\sim Y$ iff $X\preceq Y$ and $Y\preceq X$. Let $M=2^P/\mathord\sim$ be the quotient, then $\preceq$ passes to a partial order, also denoted $\preceq$, on $M$.

Is $(M,\preceq)$ a complete lattice?

**Tags:** partial-order, order-theory, lattice
> **Comments:**
> **username_1**: As far as I can see, a union of a family of sets is its lub in $\preceq$, or am I missing something?  
> **username_1**: In fact, $(M,\preceq)$ is apparently (isomorphic to) the complete lattice of downsets in $P$, as $X\preceq Y$ iff $X{\downarrow}\subseteq Y{\downarrow}$. This is an upside-down complete Heyting algebra.  
> **username_0**: Thank you Emil, this looks right to me. But (next question) is it well-known? I'm not familiar with the old papers on domain theory, but it seems like something which should be in there.  

---

## 0 answers

