3

Can one write principle of mathematical induction formally in the following way ($ P $ and $ S $ are a predicate and the successor function, respectively)?

$$(\exists x\in\mathbb {N}(P (x))\wedge \forall y\in \mathbb {N}_{\geq x}(P (y)\Rightarrow P (S (y))))\Leftrightarrow \forall z\in \mathbb{N}_{\geq x}(P (z))$$

Andrés E. Caicedo
  • 79,201
Constantine
  • 1,429
  • Yes that is one way to write it, although it seems this would be the induction principle for one particular predicate $P$. Add a quantification $\forall P$ at the beginning of your formula and you get the full principle of induction. – walcher Sep 08 '13 at 14:01
  • (1) No, do not add a quantifier for $P$ if your attempt is to write the principle in first order logic. In that case, you must fix a vocabulary first, and rather than $P$ you use an arbitrary formula in that language. The formula may have additional (number) parameters, that you should quantify over. This gives you the principle as a schema (infinitely many statements, one for each possible formula), and one can do no better. (Cont.) – Andrés E. Caicedo Sep 08 '13 at 14:56
  • (2) However, if your intention is to describe the principle in a second order setting, then yes, quantify over $P$, and this one statement suffices. – Andrés E. Caicedo Sep 08 '13 at 14:57
  • 1
    I'm worried that $x$ isn't quantified on the right hand side. – Julian Rosen Sep 08 '13 at 15:02
  • 1
    Writing it down that way is not right. There is an attempt to allow the induction to start anywhere. But then the $x$ should be universally quantified, and then other changes are needed. Better to simplify the statement of induction, and leave the start at $x$ burden to the "property" $P$. Particularly if the more complicated statement is not correct. – André Nicolas Sep 08 '13 at 15:19
  • 1
    The incorrectness had been noted earlier by Pink Elephants. As things are written, the part before the $\land$ is a sentence, $x$ is bound. But then $x$ occurs freely later, and it is clear that the writer intends the later $x$ to be the same as the $x$ that was earlier asserted to exist. The logic is not correct. Also, when fixing things, one should remove the biconditional towards the end, replace by implication. – André Nicolas Sep 08 '13 at 15:33

0 Answers0