# Do I have to prove the base case in the baseless version of strong induction?

I'm currently studying mathematical induction and this is the definition for strong induction presented in Terrence Tao's Analysis book.

Proposotion 2.2.14 Let m0 be a natural number and let P(m) be a property pertaining to an arbitrary natural number m. Suppose that for each m≥m0, we have the following implication: if P(m′) is true for all natural numbers m0≤m′<m, then P(m) is also true. (In particular, this means that P(m0) is true, since in this case, the hypothesis is vacuous.) Then we can conclude that P(m) is true for all natural numbers m≥m0.

I've also seen this other definition for strong induction:

Let A⊆N such that for all n,m∈N we have (m<n ⟹ m∈A) ⟹ n∈A. Then A=N.

In both cases, it seems to be that these definitions do not include as a separate case the "base case". But my question is if I still need to show its truth.

So for example first looking at Terrence Tao's definition if we wanted to prove something by strong induction, we would let m0, m∈N with m≥m0 and assume ∀m' (m0≤ m'≤ m ⟹ P(m')) and we would want to show P(m).

In the case m' = m0, because the hypothesis is vacuously true, we must show P(m0) is true in order to have a true implication.

Now in the second definition, it happens the same, let n be the smallest element of the set, then the hypothesis would be vacuously true and we would have to prove P(n) is true in order to have a true implication.

Is my reasoning about our need to prove a base case correct?

• "$m_0$" and $"n"$ are the base cases! Nov 3, 2021 at 0:57
• @user247327 I think in the second definition, the base case is $n$ being the smallest natural number $($so $0$ or $1)$ Nov 3, 2021 at 1:11
• @MMMagician I think your reasoning is correct, that means that also the definitions you are analyzing are correct Nov 6, 2021 at 8:12