Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to do a exercise from my book, but I don't understand how to solve it (many statements!)...

Here is the exercise:

Let $P$ and $Q$ be ordered sets. Prove that $(a_1, b_1)\prec (a_2,b_2)$ in $P\times Q$ if and only if ($a_1 = a_2$ and $b_1\prec b_2$) or ($a_1\prec a_2$ and $b_1 = b_2$).

$x\prec y$ means $x$ covers $y$: $x \le y$ and there does not exist $z$ such that $x\le z\le y$.

And $(a_1,b_1)\prec (a_2,b_2) \iff a_1\le a_2\text{ and }b_1 \le b_2$ with covering in each case.

The problem is that I don't know how to prove because of so many statements from left to right direction... Can anyone help me??

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

HINT: It’s very straightforward to prove that if $a_1=a_2$ and $b_1\prec b_2$, or if $a_1\prec a_2$ and $b_1=b_2$, then $\langle a_1,b_1\rangle\prec\langle a_2,b_2\rangle$; I’ll leave that to you. Now suppose that $\langle a_1,b_1\rangle\prec\langle a_2,b_2\rangle$; you need to show that either $a_1=a_2$ and $b_1\prec b_2$, or $a_1\prec a_2$ and $b_1=b_2$.

Certainly $\langle a_1,b_1\rangle\le\langle a_2,b_2\rangle$, so $a_1\le a_2$ and $b_1\le b_2$.

  • Suppose that $a_1=a_2$, and $b_1\le b_2$ but $b_1\nprec b_2$; then there is a $b\in B$ such that $b_1<b<b_2$, and clearly $\langle a_1,b_1\rangle<\langle a_1,b\rangle<\langle a_2,b_2\rangle$, contradicting the assumption that $\langle a_1,b_1\rangle\prec\langle a_2,b_2\rangle$.

  • Suppose that $b_1=b_2$, and $a_1\le a_2$ but $a_1\nprec b_1$; use a similar argument to get a contradiction.

  • Suppose that $a_1<a_2$ and $b_1<b_2$; get a contradiction by finding two members of $A\times B$ lying strictly between $\langle a_1,b_1\rangle$ and $\langle a_2,b_2\rangle$ in the product partial order on $A\times B$. You don’t have to look any further than the elements $a_1,a_2,b_1$, and $b_2$ to build these two members of $A\times B$.

  • Show that if neither ($a_1=a_2$ and $b_1\prec b_2$) nor ($a_1\prec a_2$ and $b_1=b_2$) is true, then we’re in one of the three cases above. Conclude that since they’re impossible, we must have either ($a_1=a_2$ and $b_1\prec b_2$) or ($a_1\prec a_2$ and $b_1=b_2$).

From this result it follows that it is not true that $\langle a_1,b_1\rangle\prec\langle a_2,b_2\rangle$ if and only if $a_\prec a_2$ and $b_1\prec b_2$, which is what your sentence starting with And seems to claim.

share|improve this answer
    
Thanks, I figured it out :) –  Edwardo Oct 1 '13 at 3:39
    
@Edwardo: Excellent! You’re welcome. –  Brian M. Scott Oct 1 '13 at 4:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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