What Quantifier is Used When Assuming P(n) for some n, in the Induction Hypothesis?

Question

In the induction step, we (usually) want to prove that

$$\forall n\in \mathbb{N}, P(n) \implies P(n+1)$$

so we assume $P(n)$ for "some" natural $n$, and show that it implies $P(n+1)$.

My question of this: what sort of quantifier are we applying to $n$ when we say, "For some $n$"?

Initially, It seems like it is just the existential quantifier, since $\exists$ is often translated to "for some."

But this doesn't seem to make much sense in the context of an induction hypothesis, because the "some" $n$ for which $P(n)$ is true could very well not include the base case.

It also couldn't be that "some" here means "for all," since that begs the question.

Instead of just "some," I have also seen the word "arbitrary" used, as in "Assume $P(n)$ for some arbitrary $n$," and this seems to make more sense to me. It feels like we are not taking any particular $n$, nor every $n$, but just something that represents $n$ in an abstract way and using that to prove the implication.

But I would be interested to hear a proper explanation of this.

Answer 1

In the induction step, we (usually) want to prove that

$$\forall n{\in} \mathbb{N},\; P(n) \implies P(n+1)$$

This is correct. (But $(1)$ below is clearer.)

so we assume $P(n)$ for "some" natural $n$, and show that it implies $P(n+1)$.

My question of this: what sort of quantifier are we applying to $n$ when we say, "For some $n$"?

I've seen authors write this too; here's an excerpt (emphasis mine):

• For the induction step, suppose that $P(k)$ is true for some natural number $k;$ we want to show that $P(k+1)$ is true.

So, this mistake isn't uncommon, and yes, it is a mistake: what we are supposing, rather, is that $P(k)$ is true for an arbitrary natural number $k,$ so that we can conclude (implicitly invoking Universal Introduction) at the end of this section that $$\forall k{\in} \mathbb{N}\; \Big(P(k) \implies P(k+1)\Big).\tag1$$

Instead of just "some," I have also seen the word "arbitrary" used, as in "Assume $P(n)$ for some arbitrary $n$," and this seems to make more sense to me.

Yes indeed. However, to more clearly distinguish this from existential quantification, I'd write "for an arbitrary $n$" instead of "for some arbitrary $n$".