A calculus of the absurd
6.7 Uniqueness proofs
-
Technique 6.7.1 The basic method is to assume that there are two objects, e.g. \(a\) and \(b\) which are distinct (i.e. \(a \ne b\)) and show that from this we can derive that \(a = b\) (i.e. a contradiction).
-
Example 6.7.1 Show that if \(r\) is an irrational number, there is a unique integer \(n\) such that the distance between \(r\) and \(n\) is less than \(\frac {1}{2}\).
There are two parts to this proof; the first is to prove that “there exists” some object with the desired properties and the second is to show that this object is unique (it is of course possible to prove these in the opposite order, but I personally prefer to first prove existence as this can shine light on how to carry out the uniqueness proof).
- Existence
-
It helps to first consider the problem informally. Usually with problems about numbers, it’s useful to draw a number line, such as this one.
We must plot \(r\) somewhere. We know that \(r\) is irrational, so anywhere between two integers will do (this is a sketch). For example, we might have
It would be nice to show that the distance between \(r\) and one of the integer neighbours is less than \(\frac {1}{2}\). We first need to a little intuition to mathematics translation. In our diagram we can label \(a\) where \(a\) is the greatest integer which is less than or equal to \(r\), i.e.
We can then construct the inequality
\(\seteqnumber{0}{6.}{30}\)\begin{align} a \leqq r < a + 1 \end{align}
As \(r\) is irrational we cannot have \(r = a\) as \(a\) is rational, so
\(\seteqnumber{0}{6.}{31}\)\begin{align} a < r < a+1 \end{align}
Then, all that remains to show is that either
\(\seteqnumber{0}{6.}{32}\)\begin{equation} |a - r| < \frac {1}{2} \text { or } |(a + 1) - r| < \frac {1}{2} \end{equation}
The only way that both of these can be false is if \(r = \frac {a + (a+1)}{2} = \frac {2a+1}{2}\), but this is rational, so \(r\) cannot be equal to this. Therefore, such an \(n\) (either \(n=a\) or \(n=a+1\)) does exist.
- Uniqueness
-
This proof is by contradiction. First let us assume that there are two integer \(x \ne y\) which exist, and are different (i.e. \(x \ne y\)), and that
\(\seteqnumber{0}{6.}{33}\)\begin{equation} \abs {x - r} < \frac {1}{2} \text { and } \abs {y - r} < \frac {1}{2} \label {x, y both satisfy less than 1/2 from r} \end{equation}
We would like to show that \(x = y\). A standard technique to apply in such cases is to note that this is equivalent to \(x - y = 0\), and as we are interested in distances, we can show that
\(\seteqnumber{0}{6.}{34}\)\begin{align} |x - y| &= |x - a + a -y| \\ &\leqq |x - a| + |a - y| & \text {By the triangle inequality} \\ &< \frac {1}{2} + \frac {1}{2} & \text {By assumption in Equation \ref {x, y both satisfy less than 1/2 from r}} \\ &< 1 \end{align}
As \(x, y\) are integers, it must therefore be that \(x = y\), which contradicts our earlier hypothesis that \(x \ne y\), so any such \(n\) is unique.