# Showing a power set as, partial order, well ordering, total ordering

Let $X$ be a set with more than two elements. Define a relation $R$ on $P (X)$, the power set of X, by $(A, B) \in R$ if and only if $A \subseteq B$. Show that $R$ is a partial order on $P (X)$. Is it a well ordering? Is it a total ordering?

So there is a set $X$, that has more than 2 elements. The power set of $X$ has $(A,B)\in R$ if and only if $A \subseteq B$. How would I show if it is partial order on $P(X)$? Or if it is well and/or total ordering? If I am correct, partial ordering is when reflexive, anti symmetric, and transitive. I am not to sure about total ordering. Well ordering = a set having a least element, if I am not mistaken.

(Discrete Mathematics)

• Well what are the definitions of partial and total orders? Start off with transitivity if $A \subset B$ and $B \subset C$ does that mean $A \subset C$. Yes it does. So this satisfies transitivity. Try exclusivity given the three choices $A \subsetneq B$, $B \subsetneq A$, and $A = B$ is there any fourth option? Can it ever be that two are more of these options are true? Go through all the definitions of total and partial order in this way. – fleablood Oct 7 '16 at 16:00
• You are correct about partial ordering. And $\subset$ should be very easy to show. Total ordering means either $a \subset b$ or $b \subset a$ or $a = b$ and one and only one of those must be. This should be very easy to show to be false. Well order means not just that there is a smallest element but that every non-empty set has a smallest element. This may seem tougher but if the elements of a set can't even compare then there can't be a smallest. Make a list of subsets of which none are subsets of any other. – fleablood Oct 7 '16 at 16:22

If you really understand the definitions this should be easy: (and it is. There moral to this story is going to be "trust yourself"...)

Reflexive: Is $A \subset A$ for all $A \subset X$? Well, ... obviously.

Antisymmetric: Does $A \subset B; B \subset A \implies A = B$? Well, .... obviously.

Transitivity: If $A \subset B; B \subset C \implies A \subset C$? Well....

So is it a partial order? Well....

Must any two sets be such that either $A \subset B$ or $B \subset A$? In other words, is it impossible for $A \not \subset B$ and $B \not \subset A$? What about $\{0,1\}$ and$\{1,2\}$? Must one be a subset of the other?

Is it well-ordered? Let $X = \mathbb N$. Does {even numbers, odd numbers, prime numbers, square numbers} have a least element? As I listed above $\{0,1\}$ and $\{1,2\}$ which of those two are smaller?

====

Note by definition, to be well-ordered an ordering must be a total order. Otherwise if $a \not \le b$ and $b \not \le a$ then $\{a,b\}$ can't have a smallest element because $a$ and $b$ can't even be compared.

So if $\subset$ is not a total ordering, it can't be a well ordering.

A total ordering is a partial ordering that also has that for all $a$ and $b$, either $(a,b)\in R$ or $(b,a)\in R$. A well ordering is a total ordering with the property that every subset of $X$ has a least element.

To show each of these properties, you have to answer the following questions for all $A, B, C$, where they are subsets of $X$:

Reflexivity: Is every set a subset of itself?

Antisymmetry: If $A\subseteq B$ and $B\subseteq A$, is $A=B$?

Transitivity: If $A\subseteq B$ and $B\subseteq C$, is $A\subseteq C$?

To be totally ordered (if you proved partial ordering): For any subsets of $X$, $A$ and $B$, is $A\subseteq B$ or $B\subseteq A$?

To be well ordered (if you proved total ordering): For any set of subsets of $X$, is there always one that is a subset of all of the other subsets?