What is the problem with this proof of the PMI?

185 Views Asked by At

Principle of Mathematical Induction (PMI). Let $P(n)$ be a statement depending on some $n\in \mathbb{N}$. Suppose that $P(1)$ is true and that $P(n)$ true implies $P(n+1)$ true for each $n\in \mathbb{N}$. Then $P(n)$ is true for all $n\in \mathbb{N}$.

Proof. Let $n\in \mathbb{N}$. Since $P(1)$ is true and $P(1)$ true implies $P(2)$ true we deduce that $P(2)$ is true. Similarly, since $P(2)$ true implies $P(3)$ true we deduce that $P(3)$ is true. Hence after $n$ applications of modus ponens we get that $P(n)$ is true. As $n$ is arbitrary we conclude that $P(n)$ is true for all $n\in \mathbb{N}$.

What is the problem with this proof? I would like to write the proof in formal logic language and see clearly which rule of deduction it violates.

EDIT: Based on the constructive comments I formulated what I think is a decent answer below. Any feedback is greatly appreciated.

1

There are 1 best solutions below

0
On BEST ANSWER

After reading the comments and thinking about it for some time I believe my confusion comes from not distinguishing between the object language and the metalanguage.

In FOL proofs can be any finite sequence of formulas, so in particular I can apply modus ponens $n$ times for any finite $n$.

But in the proof $n$ denotes a term of the in the object language, which has nothing to do with the $n$ I mentioned before.

In other words there are really two $n$'s. The first is a term in the object language FOL and the second is a positive integer in the metalanguage.