For a poset $(X,R)$, where $R$ is a partial order on $X$,

  • let $\operatorname{Inf}(R)$ be the set of all $A\subseteq X$ which have an infimum in $(X,R)$.
  • let $\operatorname{Sup}(R)$ be the set of all $A\subseteq X$ which have a supremum in $(X,R)$.

Suppose $X$ is a set. Is there any better way to charaterize the set $$\Xi=\{(\operatorname{Inf}(R),\operatorname{Sup}(R))\mid R\text{ is a partial order on }X\}$$? (better means more set theoretic, less order-theoretic)

  • $\begingroup$ user47958. Writing $(X,R)$ for a partially ordered set is not a standard practice. I do not recall ever seeing a mathematician use $R$ for a partial ordering relation. Usually one writes $\leq$ or maybe even $\preceq$ for a partially ordering. $\endgroup$ Apr 8 '15 at 22:31
  • $\begingroup$ yes, but it seems ugly and ambiguous to write $\operatorname{Inf}(\le)$ and $\le$ rarely is a variable as above. $\endgroup$ Apr 9 '15 at 2:40
  • $\begingroup$ If you don't like writing $\textrm{Inf}(\leq)$, then you could write $\textrm{Inf}(X,\leq)$ instead. And writing $\textrm{Inf}(\leq)$ is not any more ambiguous than writing $\textrm{Inf}(R)$. $\endgroup$ Apr 9 '15 at 3:16
  • $\begingroup$ I have seen $R$ used as a partial order, but also I have used $\leq$ as a variable. $\endgroup$ Apr 9 '15 at 11:46

I do not believe that there is a nice way to characterize $\Xi$. Furthermore, I do not see any reason to separate sets with least upper bounds or greatest lower bounds from the underlying partial ordering. In this answer, I will give cases of where the partial ordering $\leq$ is completely determined by $\mathcal{A}$ and $\mathcal{B}$. In particular, since $\mathcal{A}$ and $\mathcal{B}$ sometimes completely determine the partial order $X$, we do not obtain a simpler structure when we observe the sets $\mathcal{A}$ and $\mathcal{B}$ as opposed to the partial ordering $\leq$.

Suppose that $X$ is a poset. Let $\preceq^{\circ}$ be the ordering on $X$ where $x\preceq^{\circ}y$ if and only if $A\cup\{x\}\in\mathcal{A}$ implies $A\cup\{y\}\in\mathcal{A}$. Notice how $\preceq^{\circ}$ only depends on $\mathcal{A}$ and not the partial ordering. It is clear that $\preceq^{\circ}$ is a preordering on $X$. Furthermore, if $X$ is a join-semilattice, then $x\preceq^{\circ}y$ whenever $x\leq y$. Define $\preceq$ to be the relation where $x\preceq y$ if and only if $x\preceq^{\circ}y$ and $x\preceq_{\circ}y$. If $X$ is a lattice, then $x\preceq y$ whenever $x\leq y$. In fact, as the following proposition shows, there are some lattices such that $x\preceq y$ if and only if $x\leq y$.

$\mathbf{Proposition}$. Suppose $X$ is a Heyting algebra such that if $x<y$, then there is some non-empty set $R\subseteq\{z\in X|x\leq z\leq y\}$ that does not have a least upper bound. Then $x\leq y$ if and only if $x\preceq^{\circ}y$.

$\mathbf{Proof}$. We only need to show that if $x\not\leq y$, then $\neg(x\preceq^{\circ}y)$. To prove this result, we will need a simple fact about Heyting algebras. In a Heyting algebra, if $\bigvee R$ exists and $a\in X$, then $\bigvee_{r\in R}(a\wedge r)$ exists and $a\wedge\bigvee R=\bigvee_{r\in R}(a\wedge r)$. Suppose that $x\not\leq y$. Then $y\wedge x<x$, so there is some non-empty set $R\subseteq\{z\in X|y\wedge x\leq z\leq x\}$ with no least upper bound. Then $\bigvee(R\cup\{x\})=x$, so $R\cup\{x\}\in\mathcal{A}$. However, $R\cup\{y\}\not\in\mathcal{A}$. Otherwise, if $R\cup\{y\}\in\mathcal{A}$, then $\bigvee_{a\in R\cup\{y\}}(a\wedge x)$ exists. However, it is clear that if $\bigvee_{a\in R\cup\{y\}}(a\wedge x)$ exists, then $\bigvee_{a\in R}(a\wedge x)=\bigvee R$ exists, a contradiction. Therefore we conclude that $\neg(x\preceq^{\circ}y)$.


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.