# Proof of necessary condition of injection without strict monotonicity

According to the proof details in Continuous Injection of Interval is Strictly Monotone, I deduce a statement:

Statement: if an injective function f:D⊂R→Rf \colon D\subset \mathbb{R}\to \mathbb{R} is not strictly monotone, then
there exist x,y,zâˆˆDx,y,zâˆˆD with xf(z),f(y)>f(z), or f(x)>f(y)f(x)>f(y) and f(y)f(y) \lor f(y)f(z)).
\end{align*}\begin{align*}
\forall x, y, z\in D: xf(y) \lor f(y)f(z)).
\end{align*}
Because
\begin{align*}
&(f(x)>f(y) \lor f(y)f(z))\\
\iff&(f(x)>f(y)\land f(x)f(y)\land f(y)>f(z))\lor (f(y)f(z))\\
\iff &(f(x)>f(z))\lor (f(z)>f(x)),
\end{align*}\begin{align*}
&(f(x)>f(y) \lor f(y)f(z))\\
\iff&(f(x)>f(y)\land f(x)f(y)\land f(y)>f(z))\lor (f(y)f(z))\\
\iff &(f(x)>f(z))\lor (f(z)>f(x)),
\end{align*}
and for all statements P, Q, R,P, Q, R,
\begin{gather*}
P\implies (Q\lor R) \text{ is logically equivalent to } (P\implies Q) \lor (P\implies R),
\end{gather*}\begin{gather*}
P\implies (Q\lor R) \text{ is logically equivalent to } (P\implies Q) \lor (P\implies R),
\end{gather*}
we have
\forall x, y, z\in D: xf(y) \lor f(y)f(z))\forall x, y, z\in D: xf(y) \lor f(y)f(z)) is logically equivalent to
\begin{gather*}
\forall x,z\in D: (xf(z)) \lor (xf(z)) \lor (xf(z)) \lor (xf(z)) \lor (xf(z)) \lor (\forall x,z\in D: xf(z)) \lor (\forall x,z\in D: x f(d)f(c) > f(d).

Case 1: a < b < c < da < b < c < d. If f(b) < f(c)f(b) < f(c), set (x,y,z) := (b,c,d)(x,y,z) := (b,c,d). Otherwise, set (x,y,z) := (a,b,c)(x,y,z) := (a,b,c). Case 2: a < b = c < da < b = c < d. Set (x,y,z) := (a,b,c)(x,y,z) := (a,b,c). Case 3: a < c < b < da < c < b < d. If f(a) < f(c)f(a) < f(c), set (x,y,z):=(a,c,d)(x,y,z):=(a,c,d). Otherwise, set (x,y,z):=(a,c,b)(x,y,z):=(a,c,b). Case 4: a < c < b = da < c < b = d. Set (x,y,z):=(a,c,b)(x,y,z):=(a,c,b). Case 5: a < c < d < ba < c < d < b. If f(a) < f(c)f(a) < f(c), set (x,y,z):=(a,c,d)(x,y,z):=(a,c,d). Otherwise, set (x,y,z):=(a,c,b)(x,y,z):=(a,c,b). Case 6: a = c < b < da = c < b < d. Set (x,y,z):=(a,b,d)(x,y,z):=(a,b,d). Case 7: a=c < b = da=c < b = d. Impossible! Case 8: a=c < d < ba=c < d < b. Set (x,y,z):=(a,d,b)(x,y,z):=(a,d,b). Case 9: c < a < b < dc < a < b < d. If f(c) < f(a)f(c) < f(a), set (x,y,z):=(c,a,d)(x,y,z):=(c,a,d). Otherwise, set (x,y,z):=(c,a,b)(x,y,z):=(c,a,b). Case 10: c < a < b = dc < a < b = d. Set (x,y,z):=(c,a,b)(x,y,z):=(c,a,b). Case 11: c < a < d < bc < a < d < b. If f(c) < f(a)f(c) < f(a), set (x,y,z):=(c,a,d)(x,y,z):=(c,a,d). Otherwise, set (x,y,z):=(c,a,b)(x,y,z):=(c,a,b). Case 12: c < a = d < bc < a = d < b. Set (x,y,z):=(c,a,b)(x,y,z):=(c,a,b). Case 13: c < d < a < bc < d < a < b. If f(d) < f(a)f(d) < f(a), set (x,y,z):=(c,d,a)(x,y,z):=(c,d,a). Otherwise, set (x,y,z):=(d,a,b)(x,y,z):=(d,a,b). 1   Thanks a lot! I've got it. – azc 2 days ago Here's a simple proof that avoids all those mind-numbing cases! Lemma: Let D\subseteq \mathbb{R}.D\subseteq \mathbb{R}. If g\colon D\to\mathbb{R}g\colon D\to\mathbb{R} is strictly monotonic on every 3-element subset of D,D, then gg is strictly monotonic on every subset of DD of cardinality \le4.\le4. Proof of Lemma: It's sufficient to prove the conclusion for subsets of cardinality exactly 4,4, since it's trivially true for sets of size 33 or less. So let a \lt b \lt c\lt da \lt b \lt c\lt d be elements of D.D. Then gg is strictly monotonic on both \lbrace a, b, c \rbrace\lbrace a, b, c \rbrace and \lbrace b, c, d \rbrace.\lbrace b, c, d \rbrace. In fact, if g(b)\lt g(c),g(b)\lt g(c), then gg is strictly increasing on both those 3-3-element sets; and if g(b)\gt g(c),g(b)\gt g(c), then gg is strictly decreasing on both those 3-3-element sets. It follows that gg is either strictly increasing or strictly decreasing on the 44-element set \lbrace a, b, c,d \rbrace.\lbrace a, b, c,d \rbrace. The problem now follows immediately: Assume ff is injective and not strictly monotonic. Then: \bullet\bullet There exist aa and bb such that a\lt ba\lt b and f(a) \gt f(b)f(a) \gt f(b) (since ff isn't strictly increasing). \bullet\bullet There exist cc and dd such that c\lt dc\lt d and f(c) \lt f(d)f(c) \lt f(d) (since ff isn't strictly decreasing). But now \lbrace a, b, c, d \rbrace\lbrace a, b, c, d \rbrace is a subset of DD of cardinality at most 44 on which ff isn't strictly monotonic. So, applying the lemma, there's some 33-element subset of DD on which ff is not strictly monotonic, which is exactly what we need to prove.