The only reflexive, symmetric, and antisymmetric relation on a set $X$ is $\{(x,x):x\in X\}$. Reason: If $(x,y)$ is in the relation, then by symmetry so is $(y,x)$, then by antisymmetry $x=y$. This shows that the relation is contained in $\{(x,x):x\in X\}$, and the other containment is the definition of reflexivity.
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$.
- 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$.
- 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.
Best Answer