C.2 Inequalities

\( \newcommand{\NOT}{\neg} \newcommand{\AND}{\wedge} \newcommand{\OR}{\vee} \newcommand{\XOR}{\oplus} \newcommand{\IMP}{\Rightarrow} \newcommand{\IFF}{\Leftrightarrow} \newcommand{\TRUE}{\text{True}\xspace} \newcommand{\FALSE}{\text{False}\xspace} \newcommand{\IN}{\,{\in}\,} \newcommand{\NOTIN}{\,{\notin}\,} \newcommand{\TO}{\rightarrow} \newcommand{\DIV}{\mid} \newcommand{\NDIV}{\nmid} \newcommand{\MOD}[1]{\pmod{#1}} \newcommand{\MODS}[1]{\ (\text{mod}\ #1)} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\Q}{\mathbb Q} \newcommand{\R}{\mathbb R} \newcommand{\C}{\mathbb C} \newcommand{\cA}{\mathcal A} \newcommand{\cB}{\mathcal B} \newcommand{\cC}{\mathcal C} \newcommand{\cD}{\mathcal D} \newcommand{\cE}{\mathcal E} \newcommand{\cF}{\mathcal F} \newcommand{\cG}{\mathcal G} \newcommand{\cH}{\mathcal H} \newcommand{\cI}{\mathcal I} \newcommand{\cJ}{\mathcal J} \newcommand{\cL}{\mathcal L} \newcommand{\cK}{\mathcal K} \newcommand{\cN}{\mathcal N} \newcommand{\cO}{\mathcal O} \newcommand{\cP}{\mathcal P} \newcommand{\cQ}{\mathcal Q} \newcommand{\cS}{\mathcal S} \newcommand{\cT}{\mathcal T} \newcommand{\cV}{\mathcal V} \newcommand{\cW}{\mathcal W} \newcommand{\cZ}{\mathcal Z} \newcommand{\emp}{\emptyset} \newcommand{\bs}{\backslash} \newcommand{\floor}[1]{\left \lfloor #1 \right \rfloor} \newcommand{\ceil}[1]{\left \lceil #1 \right \rceil} \newcommand{\abs}[1]{\left | #1 \right |} \newcommand{\xspace}{} \newcommand{\proofheader}[1]{\underline{\textbf{#1}}} \)

In this course we will deal heavily with the manipulation of inequalities. While many of these operations are very similar to manipulating equalities, there are enough differences to warrant a comprehensive list.

(Arithmetic manipulations) For all real numbers \(a\), \(b\), and \(c\), the following are true:

If \(a \leq b\) and \(b \leq c\), then \(a \leq c\).
If \(a \leq b\), then \(a + c \leq b + c\).
If \(a \leq b\) and \(c > 0\), then \(ac \leq bc\).
If \(a \leq b\) and \(c < 0\), then \(ac \geq bc\).
If \(0 < a \leq b\), then \(\frac{1}{a} \geq \frac{1}{b}\).
If \(a \leq b < 0\), then \(\frac{1}{a} \geq \frac{1}{b}\).

Moreover, if we replace any of the “if” inequalities with a strict inequality (i.e., change \(\leq\) to \(<\)), then the corresponding “then” inequality is also strict.For example, the following is true: “If \(a < b\), then \(a + c < b + c\).”

The previous theorem tells us that basic operations like adding a number or multiplying by a positive number preserves inequalities. However, other operations like multiplying by a negative number or taking reciprocals reverses the direction of the inequality, which is something we didn’t have to worry about when dealing with equalities. But it turns out that, at least for non-negative numbers, most of our familiar functions preserve inequalities.

Let \(f : \R^{\geq 0} \to \R^{\geq 0}\). We say that \(f\) is when for all \(x, y \in \R^{\geq 0}\), if \(x < y\) then \(f(x) < f(y)\).

Most common functions are strictly increasing:

Raising to a positive power, e.g., \(f(x) = x^2\) or \(f(x) = x^{3.14}\). Remember that we’re restricting ourselves to the \(\R^{\geq 0}\) for the domain of these functions! \(f(x) = x^2\) is not increasing on the domain \(\R\), for example.
Logarithms with a base greater than one, e.g., \(f(x) = \log_3(x + 1)\).
Exponential functions with a base greater than one, e.g., \(f(x) = 2^x\).

Moreover, adding two strictly increasing functions, or multiplying a strictly increasing function by a positive constant or another always-positive strictly increasing function, results in another strictly increasing function. So for example, we know that \(f(x) = 300x^2 + x \log_3 x + 2^{x+100}\) is also strictly increasing.

It should be clear from this definition that the following property holds, which enables us to manipulate inequalities using a host of common functions.

For all non-negative real numbers \(a\) and \(b\), and all strictly increasing functions \(f: \R^{\geq 0} \TO \R^{\geq 0}\), if \(a \leq b\), then \(f(a) \leq f(b)\).

Moreover, if \(a < b\), then \(f(a) < f(b)\).

It is this theorem that allows us to perform several common operations on inequalities as a “step” in a computation. For example, if we know \(0 < a \leq b\), then we can conclude that \(a^2 \leq b^2\), or \(\log_2(a) \leq \log_2(b)\), because both of the functions \(x^2\) and \(\log_2(x)\) are strictly increasing functions.