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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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$

Answer 4

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

Answer 5

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.