Partially ordered set Question : $A=\{1,2,3,4,5,6\}$ ,$R =\mathcal P(A) \times \mathcal P(A) $

Question

I`m trying to prove that this relation is partially ordered set:

1. $A=\{1,2,3,4,5,6\}$
2. $R =\mathcal P(A) \times \mathcal P(A) $
3. $(B,C)R(D,E) \Longleftrightarrow (B \subset D) \vee ((B=D)\wedge(C \subseteq E))$

the condition for partially ordered set are:

1. if for all $a \in A$(the functions set) implies $(a,a)\in R \rightarrow$ Reflexivity
2. for all $(a,b) \in R , (b,a) \in R \rightarrow a=b $ i.e. Anti - Symmetry
3. if for all $(a,b) \in R $ and $(b,c) \in R \rightarrow (a,c)\in R $ Transitivity

I need to prove the rhs and lhs that found in (3.)?
how I can find the minimal and maximal terms?
I would like to get some advice how to do that.
Thanks!

Answer 1

I am not sure if I understood your question correctly, so my answer might not apply (in case I guessed wrong). I suspect that you wished for $R \subseteq \mathcal{P}(A)^4$. If this is true, then let's start with something simpler:

$Q \subseteq \mathcal{P}(A) \times \mathcal{P}(A)$, where $(B)\ Q\ (C) \iff B \subseteq C$. It is quite straightforward to check that $\subseteq$ is a partial order.

Now, $R$ works on pairs rather than elements, and the general schema that $R$ follows is called the lexicographic order. The only thing we would like to do is check if it really is a partial order:

Let $\leq_X$ and $\leq_Y$ be partial orders on $X$ and $Y$ respectively. Then $\leq_{X \times Y}$ defined as $$(x_1,y_1) \leq_{X \times Y} (x_2,y_2) \iff x_1 \lneq_X x_2 \lor (x_1 = x_2 \land y_1 \leq_Y y_2)$$ is a partial order because

• It is reflexive: because $x_1 = x_1$ and $\leq_Y$ is reflexive.
• It is anti-symmetric: suppose that $(x_1,y_1) \neq (x_2,y_2)$ then $x_1 \neq x_2$ (and one of $\leq_X$ or $\geq_X$ does not hold) or $y_1 \neq y_2$ (and one of $\leq_Y$ or $\geq_Y$ does not hold).
• It is transitive: if $x_1 \neq x_2$ or $x_2 \neq x_3$, then it follows from transitivity of $\leq_X$ and if $x_1 = x_2 = x_3$, then it follows from transitivity of $\leq_Y$.

Now, $R$ is the lexicographic order constructed from two copies of $Q$ and so it is a partial order.

I hope this helps $\ddot\smile$

Answer 2

If I understood your question correctly, then we are to prove that (3). gives a partial order on $\mathcal P(A) \times \mathcal P(A)$. We will also find the maximal and minimal elements in the set $\mathcal P(A) \times \mathcal P(A)$ with respect to this order.

1. Reflexivity: true since if $a = (B,C)$ then $B=B$ and $ C \subseteq C$ so $(B,C)R(B,C)$.

2. Antisymmetry: If $(B,C)R(D,E)$ and $(D,E)R(B,C)$. Then $B \subset D \vee B = D \wedge (C \subseteq E)$ since we also have $D \subset B \vee D= B \wedge (E \subseteq C)$ we see that we must have $B = D$ and then also $C \subseteq E$ and $E \subseteq C$ so we conclude that $ B = D$ and $C = E$ hence we have antisymmetry.

3. Transitivity: If $(B,C)R(D,E)$ and $(D,E)R(F,G)$ then we look at what this means by (3). and split into cases. If $B \subset D$ then clearly $B \subset F$ and we are done. If $B = D$ then if $ D \subset F$ we are again done. If $B = D = F$ then it remains to show that $C \subseteq G$. Since $D = F$ we must have $E \subseteq G$ and since $B = D$ we must have $C \subseteq E$ then it follows by transitiviy of $\subseteq$ that $C \subseteq G$ hence we have transitibity.

We have now proved that we have a partial order on $\mathcal P(A) \times \mathcal P(A)$.

To find the maximal elements we notice that the order depends on inclusions so we look for large sets say $(A,A)$. And for minimal sets we look for small sets like $(\emptyset, \emptyset)$. I leave it as an exercise for you to show that these are infact the only maximal and minimal sets respectively.