Is a proof by induction considered an exhaustive proof?

Question

Say we use induction to prove a statement P(n). In my mind, induction covers every possibility for all values n, and that somewhat seems like exhaustion.

Would it be wrong to say induction is some sort of abstract exhaustive proof?

Answer 1

These terms for "types" of proofs are not particularly well-defined and don't tend to be particularly helpful, in my experience. Many proofs involve a variety of different techniques. While some people may find it helpful to use these terms, it's not particularly important that you get them exactly correct.

That said, induction proof doesn't seem like exhaustion to me. You are not expected to directly write down a proof for all cases (such a "proof" would have to be infinitely long, and would not count as a proof).

Instead, you must establish the first case, and prove the general fact that if one case is true, then the next must be true. While this proves every case, and for any given case, the proof could be "unpacked" to provide a proof for that case (in the sense that, to prove case $n$, you could repeat the induction step $n - 1$ times), this doesn't seem like exhaustion to me, as the proof does not explicitly contain a proof for this case, in that you couldn't leave out some lines and be left with a proof of the $n$th case.

Think about a different example: if $a, b \in \mathbb{R}$ and $a < b$, then there exists some $c \in \mathbb{R}$ such that $a < c < b$. You prove this by supposing that $a < b$ and showing that $c = \frac{a + b}{2}$ satisfies the conditions above.

Is this a proof by exhaustion? Most would say "no". However, you can also "unpack" this proof to prove any case. For example, if you need to know a number between $3.14$ and $3.141$, the proof shows you can take $3.1405$. You can do this for any case! But this is not a proof by exhaustion.