# Prove or Disprove, if R and S are partial order relations on a set A, then $R \cup S$ is a partial order relation on A

Prove or Disprove, if R and S are partial order relations on a set A, then $R \cup S$ is a partial order relation on A

Proof. We must show $R \cup S$ is reflexive, antisymmetry and transitive.

Let $a \in A$ be arbitrary. Since R and S are partial order relations, so they are reflexive. So that $(a,a) \in R$ or $(a,a) \in S$. Hence $(a,a) \in R \cup S$. Hence $R \cup S$ is reflexive.

Let $a,b \in A$, suppose $(a,b),(b,a) \in R \cup S$. Then $(a,b), (b,a) \in R$ or $(a,b), (b,a) \in S$. Since R and S are antisymmetry, so we have a = b for both $(a,b),(b,a) \in R$ and $(a,b),(b,a) \in S$. Therefore $R \cup S$ is antisymmetry.

Let $a,b,c \in A$, suppose $(a,b),(b.c) \in R \cup S$. Then $(a,b),(b,c) \in R$ or $(a,b),(b,c) \in S$. Since R and S are transitive, $(a,b),(b,c) \in R$ implies that $(a,c) \in R$. Similarly, for $(a,b), (b,c) \in S$ we have $(a,c) \in S$. Thus we have $(a,c) \in R$ or $(a,c) in S$. Hence $R \cup S$ is transitive, since $(a,c) \in R\cup S$.

Since $R \cup S$ is reflexive, antisymmetry and transitive, hence $R \cup S$ is partial order relation. $\blacksquare$

I can't figure out a counterexample to show this not holds, but if R and S are equivalence relation, then $R \cup S$ is not an equivalence relation.

I think this is because partial order relation is antisymmetry rather than symmetry, if $(xRy)$ and $(yRx)$, then $x = y$.

Like if A = {1,2,3}, then R must be {(1,1),(2,2),(3,3)}, if R = {(1,1),(2,2),(3,3),(1,2)} then it's wrong, the antisymmetry does not holds.

My question is that is there any counterexample to show this should be a disproof, or my proof is in right approach?

The example $A=\{1,2,3\}$, $R=\{(1,1),(2,2),(3,3),(1,2)\}$ and $S=\{(1,1),(2,2),(3,3)(2,3)\}$ works, as $R\cup S$ is not transitive anymore.

Your proof goes wrong in the transitivity step where you conclude from $(a,b),(c,d) \in R\cup S$, then $(a,b),(c,d) \in R$ or $(a,b),(c,d)\in S$. It may well be that $(a,b) \in R$ and $(c,d)\in S$, while $(c,d)\not\in R$ and $(a,b)\not\in S$.

Actually, your proof is wrong in some others steps as well. For reflexivity you have $(a,a)\in R$ as well as in $S$, hence $(a,a) \in R \cup S$.

At the anti-symmetric part you make the same (wrong) conclusion as in the transitivity part.

• I am a little bit confuse, R are S are partial order relations, so they should be antisymmetry, like element (1,2) in R, how does R hold for antisymmetry? – bagMan Dec 13 '16 at 22:15
• $(1,2) \in R$, but $(2,1)\not \in R$. The property antisymmetric here reads: If $(1,2) \in R$ and $(2,1) \in R$, then $1=2$. But $(2,1)$ is not in $R$, hence the premise is false. The statement: If $A$, then $B$ is true if $A$ is false or $B$ is true. – JSchoone Dec 13 '16 at 22:19
• OMG, I didn't realize that! thank you. the statement will be true if the if condition is false. – bagMan Dec 13 '16 at 22:31
• You're very welcome. (: – JSchoone Dec 13 '16 at 22:37

Your proof is wrong. Suppose $A=\{*,\circ\}$, $R=\{(*,*),(*,\circ),(\circ,\circ)\}$ and $S=\{(*,*),(\circ,*),(\circ,\circ)\}$. Also, you seem to work with total instead o partial order.

The problem is that your arguments for antisymmetry and transitivity of $R\cup S$ are incorrect.

HINT: These questions should help you to see what’s wrong with your arguments and where to look for counterexamples.

• For antisymmetry, what if $\langle a,b\rangle\in R\setminus S$ and $\langle b,a\rangle\in S\setminus R$? Can that happen? Is there any guarantee then that $a=b$?

• For transitivity, what if $\langle a,b\rangle\in R$, and $\langle b,c\rangle\in S\setminus R$? Can that happen? Is there any guarantee then that $\langle a,c\rangle$

• The first situation could happen, but still if $(a,b) \in R$ and $(b,a) \in S$, still can get a = b (since antisymmetry for R and S). And for transitivity, I think it could be a problem if $(a,b) \in R$ and $(b,c) \in S$. Meanwhile, I just a bit confuse, the counterexample given by other post, if (1,2) is an element of R, how does R holds for antisymmetry? I suppose in order to hold antisymmetric, if xRy and yRx, then x = y. – bagMan Dec 13 '16 at 22:21
• @bagMan: It can happen that $a=b$, but that’s not the point. The point is that it doesn’t have to happen. Let $R$ be the relation $\le$ on $\Bbb Z$, and let $S$ be the relation $\ge$; $R$ and $S$ are both partial orders on $\Bbb Z$, and $\langle 1,2\rangle\in R\subseteq R\cup S$, and $\langle 2,1\rangle\in S\subseteq R\cup S$, but $1\ne 2$. – Brian M. Scott Dec 13 '16 at 22:25

You goofed in your second step. You cuold have $(a,b) \in R$ and $(b,a)\in S$ in which case $(a,b)$ and $(b,a)$ are both in $R\cup S$.

In fact, this gives a way to constrict a counterexample.

Let $A = \{1,2,3\}$ and $R$ be $\{1<2,1<3\}$ and $S$ be $\{1<2,3<1,3<2\}$.

Both are partial order relations. Yet there union contains both $1<2$ and $2<1$.

There is (at least) one logical error in your proof for antisymmetry

$(a,b),(b,a) \in R \cup S$ doesn't imply that $(a,b),(b,a) \in R$ or $(a,b),(b,a) \in S$. You could have $(a,b) \in R$ and $(b,a) \in S$.

This is what is highlighted in the counterexamples provided in the other responses.