1
$\begingroup$

This is a question from Terry Tao's analysis. Here is the question:

Let $f: X \rightarrow Y$ be a function from one set $X$ to another set $Y$. Suppose that $Y$ is partially ordered with some ordering relation $\leq_Y$. Define a relation $\leq_X$ on X by defining $x \leq_X x'$ if and only if $f(x) \leq_Y f(x')$. Show that this relation $\leq_X$ turns $X$ into a partially ordered set. If we know in addition that the relation $\leq_Y$ makes $Y$ totally ordered, does this mean that the relation $\leq_X$ makes $X$ totally ordered also? If not, what additional assumptions need to be made on $f$ in order to ensure that $\leq_X$ makes $X$ totally ordered?

So to prove reflexivity of x we have:

$f(x) \leq_Y f(x) \Longleftrightarrow x \leq_X x$ and so reflexivity is proven as Y is partially ordered.

To prove transitivity:

If $f(x) \leq_Y f(y)$ and $f(y) \leq_Y f(z)$ then $f(x) \leq_Y f(z)$ by the definition of a partially ordered set. Hence, by the definition of the order on $X$, we obtain if $x \leq_X y$ and $y \leq_X z$ then $x \leq_X z$, proving transitivity.

However, I am having some trouble proving anti-symmetry.

We note that if $f(x) \leq_Y f(y)$ and $f(y) \leq_Y f(x)$ then $f(x) = f(y)$. However, this does not necessarily prove that $x=y$. Do we not have to assume that $f$ is an injective function?

So as a counterexample, consider $X = \{1,2,3\}$ and $Y=\{1,2\}$ (and let $Y$ have the normal ordering of the natural numbers), and let the function $f: X \rightarrow Y$ be defined as $f(1) = 1, f(2) = 2, f(3) = 1$. We then must have $1 \leq_X 3$ as $f(1) \leq_Y f(3)$, and similarly we must have $3 \leq_X 1$ as $f(3) \leq_Y f(1)$, but clearly $1 \neq 3$.

I'm especially confused as this proof from this SE question was said to be correct, but doesn't the counterexample show this to be false?

Then, once we have assumed the function to be injective, this makes X a totally ordered set when Y is a totally ordered set. Simply as either $f(x) \leq_Y f(y)$ or $f(y) \leq_Y f(x)$, which implies that either $x \leq_X y$ or $y \leq_X x$.

I feel as though I am missing something major though, just because I'm sure I'm not right against the textbook and the other question. I just can't see where I went wrong, and need some help with that. Thank you very much.

$\endgroup$
  • 1
    $\begingroup$ There is a difference between your problem and the linked one. The order in $X$ is defined as $x\leq y$ if and only if $f(x)<f(y)$ or $x=y$. $\endgroup$ – Hellen Oct 27 '17 at 10:46
1
$\begingroup$

$f(x) \leq_Y f(x) \Longleftrightarrow x \leq_X x$ and so reflexivity is proven as Y is partially ordered.

It would probably be more sensible to write $x\leq_X x\iff f(x)\leq_Y f(x)$, but technically, you're right.


If $f(x) \leq_Y f(y)$ and $f(y) \leq_Y f(z)$ then $f(x) \leq_Y f(z)$ by the definition of a partially ordered set. Hence, by the definition of the order on $X$, we obtain if $x \leq_X y$ and $y \leq_X z$ then $x \leq_X z$, proving transitivity.

Again, this sort of seems backward. I would write it so it is more clear that:

  • We start with $x\leq_X y$ and $y \leq_X z$
  • This, by definition, means that $f(x)\leq_Yf(y)$ and $f(y)\leq_Yf(z)$
  • This, because $\leq_Y$ is partial ordering, means that $f(x)\leq_Yf(z)$
  • This, by definition, means $x\leq_Xz$.

That way, you can clearly show how each step follows from the previous.


For anti-symmetry, you are entirely correct, if $f$ is not injective, then you cannot conclude that $\leq_X$ is a partial ordering. Your counterexample is sufficient.

I don't really know what's confusing you, since the linked question assumes that $x\leq_X x'$ if and only if $f(x)<_Y f(x')$ OR $x=x'$ which is different from the definition you are working with.

$\endgroup$
  • $\begingroup$ $<_Y$. With $\leq_Y$ his counter example still applies. $\endgroup$ – Hellen Oct 27 '17 at 10:48
  • $\begingroup$ @Hellen You're right, a typo. $\endgroup$ – 5xum Oct 27 '17 at 10:49
  • $\begingroup$ Oh sorry, I misread that as being identical to my question. I now understand and am no longer confused. Also, thank you for the help in proof technique. I have been self-teaching real analysis with not much experience in abstract math, so some of my technique may be slightly iffy. Thanks. $\endgroup$ – Cameron Eggins Oct 27 '17 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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