PA theorem

[Mario Carneiro]

Yes. You can prove that by induction on z:

If P(z), then we are done by (ii). Otherwise, if z = 0, then by (i) the
P(x) that exists is > 0 because it is not z, and if z = w+1 then there
exists P(y) with y>w by the inductive hypothesis, which is not z, so in
fact y>z.

Mario Carneiro

On Sat, Jul 17, 2021 at 10:21 PM Giovanni Lagnese <giov.lagn at gmail.com>
wrote:

> It is true that, for any formula with a free variable P(x) in the language
> of first order arithmetic, it is a PA theorem that:
> If:
> i) an x exists such that P(x)
> ii) for each x such that P(x) there exists a y>x such that P(y)
> Then for every z there exists a k such that P(k) and k>z?
> Is this, for any formula with a free variable P(x), a theorem of PA?
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20210717/b39fdf0b/attachment-0001.html>