Showing that $(P(X),\subseteq)$ is a partial order,total order or lattice.

Question

Given $X$ a set, Take $(P(X),\subseteq)$ Where $P(X)$ is the power set of $X$, My question is how would i show if the above is a partial order, and when is it a total order? and is it a lattice, how could i determine the max and min of $P(X)$ for a general set $X$.

My attempt for the first part would be to test that $X$ itself is reflexive, anti-symmetric and transitive, however i don't know if i'm to apply this to the set $X$ or $P(X)$ and how to do this for a set which is just as general as the one above.

Answer 1

It may help if we first define what "$\subseteq$" means exactly. Given two sets $A$ and $B$, we say $A \subseteq B$ if for all $x \in A$, we have $x \in B$.

Try to do each part without looking at my answer, and then see how we compare.

We need to show three conditions for it to be a partial ordering: $\subseteq$ is reflexive, antisymmetric, and transitive. We must show this on the subsets of $X$.

Reflexive: Let $A \subseteq X$ be some subset. Is it true that $A \subseteq A$?

We proceed by definition. Let $x \in A$ arbitrarily; then clearly $x \in A$ and so we have $A \subseteq A$.

Antisymmetric: Let $A, B \subseteq X$. If $A \subseteq B$ and $B \subseteq A$, then does $A = B$?

By definition, we have for all $x \in A$, $x \in B$, and likewise for all $x \in B$, $x \in A$, and so it follows that $A = B$.

Transitive: Let $A, B, C \subseteq X$. Then if $A \subseteq B$, and $B \subseteq C$, do we have $A \subseteq C$?

Notice if $A \subseteq B$, then we have for all $x \in A$, $x \in B$. Also notice that since $B \subseteq C$, for all $x \in B$ we have $x \in C$. Thus, for all $x \in A$, we have that $x \in C$. Hence, $A \subseteq C$.

For total order, we require a third property; that is, for all $A, B \in \mathcal{P}(X)$, we have $A \subseteq B$ or $B \subseteq A$. Try to first construct a counterexample.

Take the example that I gave in the comments; let $X = \{0, 1, 2\}$. Then we have $\{0,1\}$ is one such subset and $\{0,2\}$ is another such subset. Per definition of $\subseteq$, do we have that $\{0,1\} \subseteq \{0,2\}$ or $\{0,2\} \subseteq \{0,1\}$? Clearly not.

Can you construct an example?

Let $X = \varnothing$. Then we have $\mathcal{P}(X) = \{\varnothing\}$. This is clearly totally ordered.

What can you then say about these two examples? Can you construct a claim from this?

Claim: $X$ is totally ordered if it is the empty set or the singleton set.

How would you prove this claim?

Proof: The case where $X = \varnothing$ is clear. The case where it's a singleton is also pretty trivial; If $X = \{a\}$, then $\mathcal{P}(X) = \{\varnothing, \{x\}\}$. Notice that the empty set is contained in $x$, and so it follows that this is totally ordered. Now, consider when it is not the singleton set or trivial. Then we have that there are two elements, $a$ and $b$ which are in $X$ such that $a \neq b$. Hence, $\{a\}$ and $\{b\}$ in our power set do not satisfy our total ordering criteria.

How would you show its a lattice?

You would need to establish that the union is the smallest set which contains the two sets, and the intersection is the largest set which is contained in both sets. This is clear by the definition of union and intersection. Hence, the union is the supremum of the two sets and the intersection is the infimum of the two sets.

How would you determine a max and a min?

Clearly, $\varnothing \in A$ for all sets $A$, and so we have $\{\varnothing\} \subseteq A$ for all sets. This is our min. For our max, consider the power set $\mathcal{P}(X)$. Let $A \in \mathcal{P}(X)$. Then we have for all $x \in A$, $x \in X$. Notice this holds true for all elements in our power set. Hence, it follows that our max will just be $X$. You could also find them by taking the union over all elements in our power set and taking the intersection over all elements in our power set.

What can we then say about our lattice $\mathcal{P}(X)$?

We say then our power set is a complete lattice.