Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $S = \{1,2,3\}$ and let the poset $(\wp(S)\setminus\{\emptyset\}, \sim)$ be defined as follows:

$$\begin{aligned} X \sim Y \Leftrightarrow X = Y \text{ or } \max(X) < \max(Y) \end{aligned}$$

Determine if $\sim$ is a total order relation and if $(\wp(S)\setminus\{\emptyset\}, \sim)$ is a lattice.

It's easy to show that $\sim$ is not a total order relation because if we consider $\{3\},\{1,3\} \in \wp(S)\setminus\{\emptyset\}$ then

$$\begin{aligned} \{3\} \neq \{1,3\} \text { and } 3 \nless 3 \Rightarrow \{3\} \nsim \{1,3\} \end{aligned}$$ $$\begin{aligned} \{1,3\} \neq \{3\} \text { and } 3 \nless 3 \Rightarrow \{1,3\} \nsim \{3\} \end{aligned}$$

What I really struggle with is showing if this poset is a lattice. By very definition, we know $(\wp(S)\setminus\{\emptyset\}, \sim)$ is a lattice $\Leftrightarrow \forall X,Y \in \wp(S)\setminus\{\emptyset\}$, $X \vee Y = \sup\{X,Y\}$ and $X \wedge Y = \inf\{X,Y\}$, but I can't figure out what $X \vee Y$ and $X \wedge Y$ pratically mean. Do I need to substitute $\sim$ for $\vee$ and $\wedge$?

share|cite|improve this question

By definition $X\lor Y=\sup\{X,Y\}$ and $X\land Y=\inf\{X,Y\}$ if such elements exist, so you have to determine whether $\sup\{X,Y\}$ and $\inf\{X,Y\}$ exist for all $X,Y\in\wp(S)\setminus\{\varnothing\}$. Take $X=\{3\}$ and $Y=\{1,3\}$, for example. Is there a $Z\in\wp(S)\setminus\{\varnothing\}$ such that $X\sim Z$, $Y\sim Z$? If not, $X$ and $Y$ don’t even have an upper bound in $\wp(S)\setminus\{\varnothing\}$, let alone a least upper bound. If you can find an upper bound $Z$, you still have to show that $Z\sim U$ whenever $U$ is an upper bound for $X$ and $Y$, i.e., whenever $X\sim U$ and $Y\sim U$.

Added: Take the example of $X=\{3\}$ and $Y=\{1,3\}$. $Z$ is an upper bound for $X$ and $Y$ if $X\sim Z$ and $Y\sim Z$. You already know that $X\not\sim Y$, so $Y$ is not an upper bound for $X$ and $Y$. Similarly, $Y\not\sim X$, so $X$ isn’t an upper bound for $X$ and $Y$. Suppose that there is some $Z$ that is an upper bound for $X$ and $Y$; we’ve just seen that it can’t be $X$, so the only way to have $X\sim Z$ is to have $\max(X)<\max(Z)$. Similarly, we have to have $\max(Y)<\max(Z)$. But $Z\subseteq\{1,2,3\}$, so $\max(Z)\le3=\max(X)=\max(Y)$: it’s impossible to find a $Z\in\wp(S)\setminus\{\varnothing\}$ such that $\max(X)<\max(Z)$. We’ve now shown that $X$ and $Y$ have no upper bound in $\wp(S)\setminus\{\varnothing\}$. Since they have no upper bound at all, they certainly have no least upper bound: $\sup\{X,Y\}$ doesn’t exist. That’s just another way of saying that $X\lor Y$ doesn’t exist. And this means that the poset is not a lattice.

Note that some pairs do have least upper bounds. For instance, let $X=\{1\}$ and $Y=\{1,2\}$. $X\sim Y$ and $Y\sim Y$, so $Y$ is an upper bound for $X$ and $Y$. Moreover, if $Z$ is any upper bound for $X$ and $Y$, then $Y\sim Z$, so $Y$ is the least upper bound for $X$ and $Y$: $\sup\{X,Y\}=Y$.

Here are three little exercises for you to try on the basis of the ideas above; I’ll be happy to answer questions about them.

  1. Do $X=\{2\}$ and $Y=\{2,3\}$ have a greatest lower bound? If so, what is $\inf\{X,Y\}$?

  2. What about $X=\{1\}$ and $Y=\{1,3\}?$

  3. Let $X=\{1\}$ and $Y=\{2\}$; what is $\sup\{X,Y\}$, if it exists? What about $\inf\{X,Y\}$?

share|cite|improve this answer
I'm sorry I am still quite confused, will you please break it down for me? – haunted85 Sep 3 '12 at 18:06
@haunted85: I’m adding some further discussion now. – Brian M. Scott Sep 3 '12 at 18:10

To prove that a partially ordered set is a lattice you just have to prove that every two-element subset of it has a supremum and infimum.

Thus you have to show that for every elements $x,y$ of your poset $x\wedge y=\inf\{x,y\}$ and $x\vee y=\sup\{x,y\}$ exists.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.