I am trying to solve the below problem from an MIT OCW course on real analysis.
Suppose that $S$ is a set and $\preceq$ is a relation on $S$ with the following properties:
- For all $x \in S$, $x \preceq x$.
- For all $x,y \in S$, if $x \preceq y$ and $y \preceq x$, then $x = y$.
- For all $x,y,z \in S$, if $x \preceq y$ and $y \preceq z$, then $x \preceq z$.
Define a new relation $\prec$ on $S$ by $x \prec y$ iff $x \preceq y$ and $x \neq y$. Does this define an order conforming to Definition 1.5 in Rudin? If so, prove it; if not, exhibit a counterexample.
If $\prec$ were an order on $S$, it has to satisfy both transitivity and trichotomy:
- If $x \prec y$ and $y \prec z$, then $x \prec z$.
- For any $x,y,z$, exactly one of the relations $x \prec y$, $y \prec x$, and $x = y$ holds.
I think I'm ok with proving transitivity. Suppose that $x \prec y$ and $y \prec z$. Then $x \preceq y$ and $x \neq y$ and $y \preceq z$ and $y \neq z$. As $\preceq$ is transitive (by the third property), that $x \preceq y$ and $y \preceq z$ implies that $x \preceq z$. So it suffices to show that $x \neq z$. Suppose for a contradiction that $x = z$ were true. Then I can substitute into the aforementioned statements to find that $z \leq y$ and $y \leq z$. The second property of $\preceq$ then implies that $y = z$, which is a contradiction. So $x \preceq z$ and $x \neq z$. So $x \prec z$.
I'm having much more trouble with proving trichotomy. There are two parts to this:
- At least one of the relations holds: my idea was to prove that if two of them fail, then the other is true. I tried to show that if both $x \prec y$ and $x =y$ fail, then $y \prec x$ is true. The first property states that $x \preceq y$ and $x \neq y$ (which seems redundant with this assumption, but I'm not sure if that matters). It would suffice to prove that $y \preceq x$ (since $y \neq x$ is already true: equality is symmetric, so "non-equality" also must be symmetric), but I can't find a way to do this since $\preceq$ doesn't include some notion of trichotomy in its axioms. I tried to assume that $y \preceq x$ and derive a contradiction, but I wasn't able to do this.
- Assuming that the above statement were true (and I'm not certain that it is), I'd want to show that only one of the properties can be true. If $x \prec y$, then $x \neq y$. So if $y \prec x$ as well, then both $x \preceq y$ and $y \preceq x$ hold, so $x = y$, which is a contradiction. A symmetric argument then shows that if $y \prec x$, then neither $x \prec x$ or $x = y$ hold. If $x = y$, then neither $x \prec y$ or $y \prec x$ can hold, as their definitions include that $x \neq y$.
So, based on my attempt so far, I think I can verify everything except for the fact that at least one of the relations $x \prec y$, $y \prec x$, or $x = y$ hold. I tried to think back to the construction of $\mathbb{R}$ by Dedekind cuts, but I believe this construction allowed me to use the fact that the rationals have an order and therefore satisfy trichotomy. I don't have an analagous order on $\preceq$ in order to work with. But because this order and the set itself is so abstract, I don't know what form a counterexample would even take.
Let $S= \Bbb N$ and define $x \preceq y$ as meaning $x \mid y$. Define $x \prec y$ as meaning $x \mid y \land x \neq y$. Now let $x=2, y=3$ and you have your counterexample.