Proposition 2.2.12

Propostion 2.2.12 (Basic properties of order for natural numbers) let \(a,b,c\) be natural numbers. Then

  • (a) (Order is reflexive) \(a\geq a\).

  • (b) (Order is transitive) If \(a\geq b\) and \(b\geq c\), then \(a\geq c\).

  • (c) (Order is anti-symmetric) If \(a\geq b\) and \(b\geq a\), then \(a=b\).

  • (d) (Addition preserves order) \(a\geq b\) only and only if \(a+c\geq b+c\).

  • (e) \(a<b\) if and only if \(a\pp\leq b\).

  • (f) \(a<b\) if and only if \(b=a+d\) for some positive number \(a\).

\(Proof\) See Exercise 2.2.3.

Links to this page
  • Proposition 2.2.13

    \(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\)

  • Exercise 2.3.5 (Proposition 2.3.9)
    \(=\) { Proof by cases: \(r'<q'\implies r'\pp=r'+1\leq q'\) by Proposition 2.2.12 (e) }
  • Exercise 2.2.4 (Propostion 2.2.13)
    \(\equiv\) { properties of order (f): \(a<b\) iff \(b=a+d\) for some positive number \(d\) }

    \(\equiv\) { properties of order (d): \(a\geq b\) iff \(a+c\geq b+c\) }

    \(\equiv\) { properties of order (e): \(a<b\) iff \(a\pp\leq b\) }

  • Exercise 2.2.3 (Propostion 2.2.12)

    Prove Propostion 2.2.12 (Hint: you will need many of the preceding propositions, colloraries, and lemmas.)

  • Chapter2

    Exercise 2.2.3. Prove Propostion 2.2.12