I am studying Hrbacek and Jech's Introduction to Set Theory (3 Ed) and have a couple of questions about the induction principle. Specifically I would like to know if the following solutions are correct. I feel confident they are, but the solution's guide I am following has very different solutions (and I mean wildly different). Any comment or suggestion is welcome.
Update: I am assuming the induction principle in the following form:
Let $P(x)$ be a property. Assume that:
- $P(0)$ holds.
- For all $n \in \mathbb{N}$, $P(n)$ implies $P(n+1)$.
Then $P(n)$ holds for all $n \in \mathbb{N}$.
- Let $P(x)$ be a property. Assume that $k \in \mathbb{N}$ and that
- (a) $P(k)$ holds.
- (b) For all $n \geq k$, if $P(n)$ then $P(n+1)$.
Then $P(n)$ holds for all $n \geq k$.
Solution:
If $k = 0$ then (a) and (b) are just the conditions of the induction principle, so $P(n)$ holds for all $n$. Let us assume $k > 0$ and take $Q(n)$ as the property 'if $n \geq k$ then $P(n)$ holds'. We prove this is true for all $n \in \mathbb{N}$ by induction on $n$:
- For $n = 0$, we have 'if $0 \geq k$ then $P(0)$ holds', which is clearly true as '$0 \geq k$' is false.
- Assume 'if $n \geq k$ then $P(n)$ holds' for $n \in \mathbb{N}$ (we want to show 'if $n+1 \geq k$ then $P(n+1)$ holds'). If $n+1 \geq k$ then $n+1 > k$ or $n+1 = k$. In the first case ($n+1 > k$), we have $n \geq k$, which by the induction hypothesis implies $P(n)$ is true; but then, by (b), we conclude $P(n+1)$ is true as desired. In the second case ($n+1 = k$), $P(k) = P(n+1)$ is true by (a).
- By the induction principle we have that, for all $n \in \mathbb{N}$, if $n \geq k$ then $P(n)$ holds.
- Let $P(x)$ be a property. Assume that $k \in \mathbb{N}$ and that
- (a) $P(0)$ holds.
- (b) For all $n < k$, if $P(n)$ then $P(n+1)$.
Then $P(n)$ holds for all $n \leq k$.
Solution:
Let $Q(n)$ be the property 'if $n \leq k$ then $P(n)$ holds'. We prove this is true for all $n \in \mathbb{N}$ by induction on $n$:
- For $n = 0$ we have 'if $0 \leq k$ then $P(0)$ holds' is true, because $P(0)$ is true already by (a).
- Assume '$n \leq k$ then $P(n)$ holds' for $n \in \mathbb{N}$ (we want to show 'if $n+1 \leq k$ then $P(n+1)$ holds'). Let $n+1 \leq k$. Since $n < n+1$ (for any $n \in \mathbb{N}$), then $n < k$ in any case. By the induction hypothesis, $P(n)$ is true; but then, applying (b) we obtain $P(n+1)$ true as well.
- By the induction principle we have that, for all $n \in \mathbb{N}$, if $n \leq k$ then $P(n)$ holds.