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$?
Best Answer
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.
Do $X=\{2\}$ and $Y=\{2,3\}$ have a greatest lower bound? If so, what is $\inf\{X,Y\}$?
What about $X=\{1\}$ and $Y=\{1,3\}?$
Let $X=\{1\}$ and $Y=\{2\}$; what is $\sup\{X,Y\}$, if it exists? What about $\inf\{X,Y\}$?