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.

Hi guys my final exam is coming up, and I am given a few practice problems and I don't get how to do these questions on total ordering and partial ordering. Here are the question and here is how I did it.

1) On the set $\mathbb{N} \times \mathbb{N}$ define: $(x_1 , y_1) \leq (x_2,y_2)$ if either $x_1 < x_2$ or $x_1=x_2$ and $y_1\leq y_2$. Prove that this relation is a partial ordering.

2) Given a relation $<$ define a relation $\leq$ by setting $x \leq y$ if and only if $x<y$ or $x=y$. Prove that if $<$ satisfies transitivity and 'trichotomy' then $\leq$ is a total ordering

3) Given a relation $\leq$, define a relation $<$ by setting $x<y$ if and only if $x \leq y$ and $x \neq y$. Prove that if $\leq$ is a total ordering then $<$ satisfies transitivity and 'trichotomy'.

For (1) I know partial ordering means I have to show if it is reflexive, antisymmetric and transitivity.

I think I know how to do if it is reflexive and transitive but I am having trouble in how to do if it is anti symmetric.

For (2) and (3) I am having trouble understanding in what it means

share|improve this question
    
@vonbrand: It's considered just fine to have "thank you" and such lines in posts on this community. Removing them is borderline impolite. (You also removed the part about asking for hints, which seems like a strange thing to do.) –  Asaf Karagila Apr 12 '13 at 0:27

2 Answers 2

up vote 2 down vote accepted

The order in (1) is known as the lexicographic order on $\Bbb N\times\Bbb N$ and is actually a total order. To show that it’s antisymmetric, suppose that $\langle m_1,n_1\rangle\le\langle m_2,n_2\rangle$ and $\langle m_2,n_2\rangle\le\langle m_1,n_1\rangle$.

  1. Since $\langle m_1,n_1\rangle\le\langle m_2,n_2\rangle$, we know that either $m_1<m_2$, or $m_1=m_2$ and $n_1\le n_2$.
  2. Since $\langle m_2,n_2\rangle\le\langle m_1,n_1\rangle$, we know that either $m_2<m_1$, or $m_2=m_1$ and $n_2\le n_1$.

We cannot have $m_1<m_2$: that would imply that $m_2\not<m_1$ and $m_2\ne m_1$, contradicting (2). Thus, $m_1=m_2$, and $n_1\le n_2$. And from (2) we can then see that $n_2\le n_1$ as well, since $m_2=m_1$. Finally, the usual order on $\Bbb N$ is antisymmetric, so $n_1\le n_2$ and $n_2\le n_1$ imply that $n_1=n_2$. We’ve now shown that $m_1=m_2$ and $n_1=n_2$, i.e., that $\langle m_1,n_1\rangle=\langle m_2,n_2\rangle$, as desired.


In the second problem you’re given a transitive relation $<$ on some set $X$, and you’re further told that $<$ has the trichotomy property: for any $x,y\in X$, exactly one of the statements $x<y$, $x=y$, and $y<x$ is true. Now you’re to define a new relation, $\le$, on $X$ by setting $x\le y$ if and only if either $x<y$ or $x=y$. Finally, you’re to prove that this new relation $\le$ is a total order.

To do this you must show that $\le$ is reflexive, antisymmetric, transitive, and total. Reflexivity and transitivity are pretty straightforward, and I’ll leave them to you. For antisymmetry, suppose that $x\le y$ and $y\le x$. Since $x\le y$, we know that either $x<y$ or $x=y$. Suppose that $x\ne y$. Then $x<y$, and by the trichotomy property we know that it is not the case that $y<x$. But then we have $y\not<x$ and $y\ne x$, so be definition it’s not the case that $y\le x$. This contradiction shows that we cannot have $x\ne y$ and hence that $x=y$, as desired. Finally, to show that $\le$ is total, use trichotomy again: for any $x,y\in X$, either $x<y$, in which case $x\le y$; or $x=y$, in which case $x\le y$; or $y<x$, in which case $y\le x$.

This exercise shows how you can turn any so-called strict linear (or total) order $<$ on a set $X$ into an ordinary total order $\le$ in such a way that the $\le$ symbol has the obvious, expected meaning.


This is just the opposite of the previous problem: starting with a total order $\le$ on $X$, turn it into a strict linear order by ‘throwing away the equals part of it’. That is, given the total order $\le$ on $X$, define a new relation $<$ on $X$ by $x<y$ if and only if $x\le y$ and $x\ne y$. Now you’re to show that this new relation is transitive and has the trichotomy property: for any $x,y\in X$, exactly one of $x<y$, $x=y$, and $y<x$ holds. Proving transitivity is very straightforward, and I’ll leave it to you. Trichotomy isn’t much harder, but you do have to check two things: you must show that for any $x,y\in X$ at least one of $x<y$, $x=y$, and $y<x$ holds, and you must also show that it’s never the case that more than one holds. To see, for example, that it’s not possible to have both $x<y$ and $y<x$, note that $x<y$ implies that $x\le y$, and $y<x$ implies that $y\le x$. The relation $\le$ is antisymmetric, so $x=y$. But then by definition $x\not<y$, and we have a contradiction. I’ll leave the rest to you, but feel free to ask for help if you get stuck.

share|improve this answer

For $(2)$ and $(3)$ you are given a relation on some set, and you are defining a new relation from it. In $(2)$ you are given $<$ and you are defining $\leq$, which can be seen as a generalization for the case of the natural numbers "less than" and "less or equal".

Now you have to prove that if $<$ was transitive (which means that if $x<y$ and $y<z$ then $x<z$); and whenever we take $x,y$ either $x<y$ or $y<x$ or $x=y$; then in such case $\leq$ is a total order, which means it is a partial order which satisfies the trichotomy condition.

Similarly, in $(3)$ you are given "less or equal" and you define "less than" from it; and now you have to prove that if the relation $\leq$ was a total order, then $<$ is transitive and satisfies the trichotomy.

Important point, while I did make analogies to the natural numbers with "less than" and "less or equal", remember that $<$ and $\leq$ are just symbols and have no direct connection to the natural numbers, or real numbers, or anything. The analogy should only give you some idea what we are trying to prove, you should never stretch analogies too far as to assume that you are given a set of natural numbers and $<$ and $\leq$ are the usual orderings.

share|improve this answer

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.