1
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – fleablood Oct 7 '16 at 16:00
  • $\begingroup$ 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. $\endgroup$ – fleablood Oct 7 '16 at 16:22
4
$\begingroup$

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....

How about total order?

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.

$\endgroup$
0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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