Partial order proof problem?

Question

proof or disproof

1) If R and R' are partial orders on A, then R U R' is a partial order on A

2) If R and R' are equivalence relations on A, then R U R' is an equivalence relation on A

For the first question, I think it is true but not sure how to prove it. Since R and R' are partial orders on A, then that means every element in A is reflexive, asymmetric and transitive with each other in A.

For the second question, I can't think of anything yet.

Please help me out. Thanks

Answer 1

Alright, I want to be clear about notation.

R = { (x,y) : x≤y for x and y in A}
R' = the same (but it might define a different ≤ of course)

Well, look at R∪R'. What do we need?

Reflexivity: Since R (or R') contains all the pairs { (x,x) : x in A}, we know this union does. Thus R∪R' is reflexive. That set of (x,x) elements is called Δ, or the diagonal of A.

Transitivity: Take x≤y and y≤z in R∪R'. How do we know x≤y is from R and y≤z isn't from R'? There's nothing guaranteeing that we have x≤z.

Asymmetry: For all we know, x≤y in R and y≤x in R'. That would be the complete opposite of asymetry - symmetry (for those two elements, at least).

Here is a counter-example.

A = { 0, 1 }
R = { (0,0), (0,1), (1,1) }
R' = { (0,0), (1,0), (1,1) }

R is the normal ordering, R' is the normal ordering backwards.

That means that R∪R' =

{ (0,0), (0,1), (1,0), (1,1) }

This is not a partial ordering - it can't have 0≤1 and 1≤0. This violates the definition of a partial ordering because this is not asymmetric.

Now, if your question was about R∩ R', you WOULD have a new partial ordering. That is much easier to see:

Because each is a partial ordering:
Δ ⊂ R
Δ ⊂ R'
Thus Δ ⊂ R∩R'

If x≤y and y≤z in R∩R' then:

(x,y) ∈ R and (x,y) ∈ R'
AND
(y,z) ∈ R and (y,z) ∈ R'
THUS
(x,z) ∈ R∩R'

Thus x≤z in R∩R'

Antisymmetry is similar:
If x
(x,y) in R and (x,y) in R'

Thus x
Thus x is not > y in R or R'

Thus x is not > y in R∩R' since it isn't even the in R∪ R'.

########### ###########

Take two relations R and S (R' is messy in this part of my answer, so call it S), and define xRSy whenever xRy or xSy. Then RS = R∪S.

Reflexivity. For any x, xRx, therefore xRSx.

Transitivity: For any x, say xRSy and yRSz. There is nothing that ensures that xRy and yRz, or that xSy and ySz. So how would we know that xRSz?

Symmetry: For any x and y, say xRSy. Then xRy, thus yRx, and thus yRSx.

Think of the following equivalence relation:

{a,b} {c,d}
ordered pairs:
(a,b), (c,d), (b,a), (d,c), (a,a), (b,b), (c,c), (d,d)

{b,c} {a} {d}
ordered pairs:
(b,c), (c,b), (a,a), (b,b), (c,c), (d,d)

Now think of their union:
(a,b), (c,d), (b,a), (d,c), (b,c), (c,b) (a,a), (b,b), (c,c), (d,d)

Could that be an equivalence relation?
(a,b) and (b,c) are in there, but (a,c) is not. It is not transitive. This is not an equivalence relation. It fails transitivity.


Again, like before, if you did R ∩ R', you WOULD get a new equivalence relation.