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

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!

-
Your first (2) and (3) are incompatible. What you mean is that $R$ is the relation on $\wp(A)\times\wp(A)$ defined by (3), and this relation is definitely not $\wp(A)\times\wp(A)$. – Brian M. Scott Aug 1 '13 at 8:01
Can you tell me which of the following statements are true? $$\big\langle\{1,3\},\{2,3,4\}\big\rangle\mathbin{R}\big\langle\{1,2,3\}, \varnothing \big\rangle$$ $$\big\langle\{1,3\},\{2,3,4\}\big\rangle\mathbin{R}\big\langle\{1,3\}, \varnothing \big\rangle$$ $$\big\langle\{1,3\},\{2,3,4\}\big\rangle\mathbin{R}\big\langle\{1,3\},\{1,2,3,6‌​\}\big\rangle$$ $$\big\langle\{1,3\},\{2,3,4\}\big\rangle\mathbin{R}\big\langle\{1\},\{1,2,3,4,5‌​,6\}\big\rangle$$ – Brian M. Scott Aug 1 '13 at 8:09
the reason I asked this question is because I dont know how to prove it, In addition I dont know if there is counter example – Evyatar Elmaliah Aug 1 '13 at 8:23
It is a partial order, so there’s no counterexample. I asked my question because I want to make sure that you understand what the relation is before we worry about why it’s a partial order. – Brian M. Scott Aug 1 '13 at 8:28
1 - false, 2 - true, 3- true, 4 - false – Evyatar Elmaliah Aug 1 '13 at 8:41

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$

-

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.

-
$((\{1,2,3,4,5,6\}),(\{1,2,3,4,5,6\}))$ can be maximal? – Ofir Attia Aug 2 '13 at 9:27