# Partial Order Relations

• Oct 13th 2007, 11:38 AM
Jacobpm64
Partial Order Relations
Let R be a relation on $\bold{N}^2$ defined by $(x,y)R(u,v)$ if and only if $x \leq u$ or $y \leq v$. Is R a partial order? Prove your answer.

This is what I came up with so far.

So, just to be courteous to the people who read this, a relation on a set is called a partial ordering if the relation is reflexive, antisymmetric, and transitive.

Therefore, I tried to prove that R is reflexive, antisymmetric, and transitive.

Here's what I did.

Claim: R is a partial order.

Proof: For R to be a partial order, it must be reflexive, antisymmetric, and transitive.
In order to show R is reflexive, let $(x,y) \in \bold{N}^2$. Notice that $x \leq x$. Therefore, $(x,y)R(x,y)$, and hence, R is reflexive.
In order to show R is antisymmetric, let $(x,y) \in \bold{N}^2$ and $(u,v) \in \bold{N}^2$. Assume $(x,y)R(u,v)$ and $(u,v)R(x,y)$. Therefore, $x \leq u$ or $y \leq v$, and $u \leq x$ or $v \leq y$.

After this point, I am not sure how to continue. I am thinking that I would have to break this into cases, but I'm not sure how to break it into cases because I have two different statements that both involve "or". It's looking like the transitive proof will also have cases, but I'm not sure how to attempt those either. If I can clear up the antisymmetric one, the transitive one can probably follow pretty easily. I will post a continuation after I get some hints on how to go about continuing. Thanks.
• Oct 13th 2007, 11:54 AM
Plato
Are both of these true?
$\left( {1,2} \right)R\left( {2,1} \right)\quad \& \quad \left( {2,1} \right)R\left( {1,2} \right)
$
• Oct 13th 2007, 11:58 AM
Jacobpm64
Yes they are, because...

In the first statement, the first elements in the ordered pairs work. $1 \leq 2$. In the second case, the second elements work. $1 \leq 2$. I guess I'm still not seeing how that's going to help me prove this :-(. (we just started relations, so i'm having trouble getting used to the idea right now).
• Oct 13th 2007, 12:01 PM
Plato
Is R antisymmetric?
• Oct 13th 2007, 12:15 PM
Jacobpm64
Oh, let's see.

I'll show you what i'm thinking. Critique it and/or confirm it.

Here you go. (i'll put comments in blue.)

So, your example was. Consider the ordered pairs $(x,y) = (1,2)$ and $(u,v) = (2,1)$ in $\bold{N}^2$.So for R to be antisymmetric, if x ~ y and y ~ x, then x = y. So, for a counterexample, we find x and y such that the hypothesis is true and the conclusion is false. Notice that x = 1 < 2 = u; therefore, (1,2)R(2,1). Also, notice that $v = 1 \leq 2 = y$; therefore, (2,1)R(1,2). Since 1 $\not= 2$ and $2 \not= 1$, $(1,2) \not= (2, 1)$. Thus, R is not antisymmetric, and hence, R is not a partial order.
• Oct 13th 2007, 12:21 PM
Plato
By George, you have.
• Oct 13th 2007, 12:22 PM
Jacobpm64
Ha, thanks a lot.

Disproofs are so much easier than proofs most of the time.

Thanks a lot man. I'll click the thanks button.