Subset relation ⊆ on all subsets of ℤ is a partial order, not a total order.

Question

I need to prove that the subset relation “⊆” on all subsets of ℤ is a partial order but not a total order. I'm not experienced in these kind of proofs and was hoping to see an example of an easier one so I could attempts other ones.

Answer 1

Remember that the difference between a partial order and a total order is that in a partial order, you can have incomparable elements. Can you think of sets $A$ and $B$ such that $A\not\subseteq B$ and $B\not\subseteq A$?

---

To clarify: such an example will merely show that $(\mathcal{P}(\mathbb{Z}), \subseteq)$ is not a total order. You still need to show that it is a partial order. To do this, you need to show that the following properties hold:

• $\subseteq$ is transitive: if $A\subseteq B\subseteq C$, then $A\subseteq C$.

• $\subseteq$ is reflexive: $A\subseteq A$.

• $\subseteq$ is antisymmetric: if $A\subseteq B$ and $B\subseteq A$, then $A=B$.

Although the proofs of these are short, they can seem odd at first glance. Let me give as an example the proof of transitivity:

Suppose $A\subseteq B$ and $B\subseteq C$. I want to show $A\subseteq C$. So let $a\in A$; we need to show that $a\in C$. Since $A\subseteq B$, we know $a\in B$. And since $B\subseteq C$, every element of $B$ is an element of $C$; so $a\in C$. So we're done.

Does this make sense? If not, what is the sticking point? If so, can you do the other two?