Let $A$ and $B$ be totally ordered sets. I just realized that:
The following are equivalent:
- $x \leq y$ implies $f(x) \leq f(y)$.
- $f(x) < f(y)$ implies $x < y$.
Proof: (1) fails precisely if there exist $x,y \in A$ with $x \leq y$ and $f(x) > f(y)$. Since the $x$ and $y$ in the preceding sentence are necessarily distinct, we actually have that (1) fails if and only if there exist $x,y \in A$ such that $x < y$ and $f(x) > f(y)$.
(2) fails precisely if there exist $x,y \in A$ with $f(x) < f(y)$ and $x \geq y$. Since the $x$ and $y$ of the preceding sentence are necessarily distinct, we actually have that (2) fails if and only if there exist $x,y \in A$ with $f(x) < f(y)$ and $x > y$.
Thus, (1) fails if and only if (2) fails if and only if $f$ changes the order of two distinct elements.
OK, so (1) is the standard definition of an increasing map (in the non-strict sense of the word). But (2)... well at first glance I thought it was not the same notion, but I was wrong! Can someone try to give a concise reason why these two conditions are the same? I know there are very few steps in the above argument, but somehow the equivalence still does not jump out at me.
By the way, there is also a (even more strange perhaps) strict version of this:
The following are equivalent:
- $x < y$ implies $f(x) < f(y)$.
- $f(x) \leq f(y)$ implies $x \leq y$.
Proof: It's straightforward to see that (4) implies (2), so, if (4) holds, then $f$ is increasing in the non-strict sense. But, if ever $f(x) = f(y)$ for $x \neq y$, then one of the implications $f(x) \leq f(y) \rightarrow x \leq y$ and $f(y) \leq f(x) \rightarrow y \leq x$ fails. Thus, (4) implies that $f$ is increasing in the strict sense.
It's easy, I think, to see (3) implies (4).
(2) is the contrapositive of (1) - that is, they are equivalent for exactly the same reason that "$A\implies B$" and "$\neg B\implies \neg A$" are equivalent. This might be easier to see if we rewrite (2) as $$f(y)\not\le f(x)\implies y\not\le x,$$ so that the connection is clearer.
Note that a crucial part of this equivalence is that, on both sides, "$<$" is a total order, so that e.g. "$y\not\le x$" is equivalent to "$x<y$"; if we were to look at partial orders, then the two expressions would no longer be equivalent.