2.1: Well Ordering Proofs

Last updated
Save as PDF

Page ID: 48300

Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer
Google and Massachusetts Institute of Technology via MIT OpenCourseWare

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

We actually have already taken the Well Ordering Principle for granted in proving that \(\sqrt{2}\) is irrational. That proof assumed that for any positive integers \(m\) and \(n\), the fraction \(m/n\) can be written in lowest terms, that is, in the form \(m'/n'\) where \(m'\) and \(n'\) are positive integers with no common prime factors. How do we know this is always possible?

Suppose to the contrary that there are positive integers \(m\) and \(n\) such that the fraction \(m/n\) cannot be written in lowest terms. Now let \(C\) be the set of positive integers that are numerators of such fractions. Then \(m \in C\), so \(C\) is nonempty. Therefore, by Well Ordering, there must be a smallest integer, \(m' \in C\). So by definition of \(C\), there is an integer \(n_0 > 0\) such that

\[\nonumber \text{the fraction } m_0 / n_0 \text{ cannot be written in lowest terms.}\]

This means that \(m_0\) and \(n_0\) must have a common prime factor, \(p > 1\). But

\[\nonumber \frac{m_{0} / p}{n_{0} / p}=\frac{m_{0}}{n_{0}},\]

so any way of expressing the left hand fraction in lowest terms would also work for \(m_0 / n_0\), which implies

\[\nonumber \text{the fraction } \frac{m_{0} / p}{n_{0} / p} \text{ cannot be in written in lowest terms either.}\]

So by definition of \(C\), the numerator, \(m_0/ p\), is in \(C\). But \(m_0 / p < m_0\), which contradicts the fact that \(m_0\) is the smallest element of \(C\).

Since the assumption that \(C\) is nonempty leads to a contradiction, it follows that \(C\) must be empty. That is, that there are no numerators of fractions that can’t be written in lowest terms, and hence there are no such fractions at all.

We’ve been using the Well Ordering Principle on the sly from early on!