Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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$

share|cite|improve this answer

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.

share|cite|improve this answer
$((\{1,2,3,4,5,6\}),(\{1,2,3,4,5,6\}))$ can be maximal? – Ofir Attia Aug 2 '13 at 9:27

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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