1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – bagMan Dec 13 '16 at 22:15
  • $\begingroup$ $(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. $\endgroup$ – JSchoone Dec 13 '16 at 22:19
  • $\begingroup$ OMG, I didn't realize that! thank you. the statement will be true if the if condition is false. $\endgroup$ – bagMan Dec 13 '16 at 22:31
  • $\begingroup$ You're very welcome. (: $\endgroup$ – JSchoone Dec 13 '16 at 22:37
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – bagMan Dec 13 '16 at 22:21
  • $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Dec 13 '16 at 22:25
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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