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
Best Answer
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$.
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.