2.2.5. Prove Proposition 2.2.14. (Hint: define \(Q(n)\) to be the property that \(P(m)\) is true for all \(m_0\leq m<n\); note that \(Q(n)\) is vacuously true when \(n\leq m_0\).)
- + Define \(Q(n)\): \(\forall m~ (m_0\leq m <n),~P(m)\)
-
\(\bullet\) Show that \((\forall m, Q(m) \implies P(m)) \implies \forall m\geq m_0,~P(m)\)
- \(\bullet\) Show that \(\forall m\geq m_0,~P(m)\)
- – \((\forall m, Q(m) \implies P(m))\)
- \(\Vdash\) \(\forall n,~ Q(n)\)
-
\(\Rightarrow\) { by Proof2 }
- \(\forall m\geq m_0,~P(m)\)
-
\(\equiv\) { by Proof1 and modus ponens }
- True
- \(\square\)
- \(\square\)
Proof1. \(\left(\forall n, Q(n) \implies P(n)\right) \implies \forall n,~ Q(n)\)
- \(\bullet\) Show that \(\forall n,~Q(n)\)
- – \(Q(n) \implies P(n)\)
-
\(\Vdash\) { proof by induction }
- \(\bullet\) base case: show that \(Q(0)\) is true when
- \(\Vdash\) \(\forall m~(m_0\leq m<0),~P(m)\) is true.
-
\(\equiv\) { Vacuously true since \(m<0\) is false }
- True
- \(\square\)
- \(\bullet\) Inductive step: show that \(Q(n\pp)\) is true when
- – \(Q(n)\) is true \(\left( Q(n) := \forall m~(m_0\leq m<n),~P(m)\right)\)
- – \(Q(n) \implies P(n)\)
- \(\Vdash\) \(\forall m~(m_0\leq m<n\pp),~P(m)\)
- \(\equiv\) { Proposition 2.2.12 (e): \(a<b\) iff \(a\pp\leq b\), \(m<n\pp\implies m\pp\leq n\pp\)
-
\(~~~~~\) Proposition 2.2.12 (d): \(a\geq b\) iff \(a+c\geq b+c\): \(m\pp\leq n\pp\implies m\leq b\) }
- \(\forall m~(m_0\leq m\leq n), ~P(m)\)
-
\(\equiv\) { by definition }
- \(Q(n) \land P(n)\)
-
\(\equiv\) { Inductive hypothesis \(Q(n)\) is true and \(Q(n) \implies P(n)\) }
- True
- \(\square\)
- \(\square\)
Proof2. \(\forall n,~Q(n)\implies \forall m\geq m_0,~P(m)\)
- \(\bullet\) Show that there is a contradiction, when
- (1) \(\left( \forall m\geq m_0,~P(m) \right)\) is false
- (2) \(\forall n,~Q(n)\)
- \(\Vdash\) \(m' > m_0 \land P(m')\)
-
\(\equiv\) { by assumption (1) }
- False
-
\(\equiv\) { by assumption (2) and \(\forall n, Q(n) \Rightarrow P(n)\) }
- True
-
\(\vdash\) { excluded middle }
- ⊥
- \(\square\)