Prove (by induction?): If $A \subset \mathbb{N}$, $4 \in A$ and $n+1 \in A$ whenever $n \in A$, then $\left\{n \mid n \geq 4 \right\} \subset A$.

Question

Prove: If $A \subset \mathbb{N}$, $4 \in A$ and $n+1 \in A$ whenever $n \in A$, then $\left\{n \mid n \geq 4 \right\} \subset A$.

So for the base case, I did $n = 4$, so we have $4 \in A$ by definition and thus $4 + 1 \in A$, and $4 + 1 \geq 4$ so the base case works.

For the second part, we want to show if $(n + 1) \in A$, and $4 \in A$ and $(n+1)+1 \in A$, then $(n+1) \geq 4$. So by the induction hypothesis, we know $4 \in A$ and we showed in the base case that $(n + 1) \in A$. So I just said $(4 + 1) + 1 \geq 4$ and concluded the proof, but the entire problem was marked incorrect.

I think I don't have a grasp on proof by induction, so what am I doing wrong?

Answer 1

Let $S = \{n \in \mathbb{N}~|~n \geq 4\}$. We want to show that $S \subseteq A$.

Suppose otherwise. Then the set $T = \{n \in \mathbb{N}~|~n \geq 4~\text{and}~x \notin A\}$ is non-empty. Any non-empty subset of the natural numbers has a least element. Let $n_0$ be the least element in $T$.

Observe that $n_0 \neq 4$ since $4 \in A$. Hence, $n_0 > 4$. Thus, $n_0 - 1 \geq 4$. By assumption, $n_0$ is the least positive integer $n \geq 4$ such that $n \notin A$. Hence, $n_0 - 1 \in A$. However, if $n \in A$, then $n + 1 \in A$. Therefore, $n_0 - 1 + 1 = n_0 \in A$, contrary to our assumption that $n_0 \notin A$. Thus, $T = \emptyset$ and $S \subseteq A$.

Answer 2

Let $S = \{n \in \mathbb N \mid n \geq 4\} = \{4, 5, 6, 7, \ldots\}$. We want to show that $S \subseteq A$. To see this, we will prove by induction on $n \in S$ that:

$$ n \in A \tag{$\star$} $$

Base Case: For $n = 4 \in S$, we know that $n = 4 \in A$ (since it's given).

Induction Hypothesis: Assume that $(\star)$ holds for $n' = n$, where $n \geq 4$.

It remains to show that $(\star)$ holds for $n' = n + 1$. But since by the induction hypothesis $n \in A$ and since we're given that $n \in A \implies n+1 \in A$, this immediately follows by Modus Ponens.

Hence, by induction, we conclude that $n \in A$ for all $n \in S$ so that $S \subseteq A$, as desired. $~~\blacksquare$