Partial Order Relations

**Jacobpm64** · October 13th 2007, 10:38 AM

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.

**Plato** · October 13th 2007, 10:54 AM

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)<br />$

**Jacobpm64** · October 13th 2007, 10:58 AM

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

**Plato** · October 13th 2007, 11:01 AM

Is R antisymmetric?

**Jacobpm64** · October 13th 2007, 11:15 AM

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.

**Plato** · October 13th 2007, 11:21 AM

By George, you have.

**Jacobpm64** · October 13th 2007, 11:22 AM

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.

Thread: Partial Order Relations

LinkBack

Thread Tools

Display

Partial Order Relations

Similar Math Help Forum Discussions

Second order recurrence relations

Order Relations and Predecessors

Order relations

Special Relations and Partial Orders help

Equivalence Relations and Partial Orderings

Search Tags