Proposition 2.2.13 (Trichotomy of order for natural numbers). Let \(a\) and \(b\) be natural numbers. Then excactly one of the following statements is true: \(a<b, a=b\), or \(a>b\).
\(Proof~by~Tao\) This is only sketch of the proof; the gaps will be filled in Exercise-2.2.4.
\(~~\) First, we show that we cannot have more than one of the statments \(a<b,~a=b,~ a>b\) holding at the same time. If \(a<b\) then \(a\neq b\) by definition, and if \(a>b\) then \(a\neq b\) by definition. If \(a>b\) and \(a<b\) then by Proposition 2.2.12 we have \(a=b\), a contradiction. Thus no more than one of the statements is true. \(~~\) Now we show that at least one of the statements is true. We keep \(b\) fixed and induct on \(a\). When \(a=0\) we have \(0\leq b\) for all \(b\) (why?), so we have either \(0=b\) or \(0<b\), which proves the base case. Now suppose we have proven the proposition for \(a\), and now we prove the proposition for \(a\pp\). Form the trichotomy for \(a\), there are three cases: \(a<b,~a=b\), and \(a>b\). If \(a>b\), then \(a\pp>b\) (why?). If \(a=b\), then \(a\pp>b\) (why?). Now suppose that \(a<b\). Then by Proposition 2.2.12, we have \(a\pp\leq b\). Thus either \(a\pp=b\) or \(a\pp<b\), and in either case we are done. This closes the induction. \(\square\)