PA theorem

[Richard Kimberly Heck]

On 7/17/21 8:42 PM, Giovanni Lagnese 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?

Proof (for fixed P(x)): Reason in PA. Prove (**) by induction on z.

Basis, z = 0. By (i), for some x, P(x). Obviously, x >= 0. By (ii), for
some k>x, P(y), and k>x>=0. So K>0, done.

Induction. Suppose (**) holds for z. We show it holds for z+1. By the
IH, for some y>z, P(y). So y>=z+1. So by (ii), for some k>y, P(y), and
k>y>=z+1, so k>z+1. Done.

As you note, this is a proof schema: One proof for each P(x).

Note that, if P(x) is \Sigma_n, then so is the inductive formula; if
P(x) it is \Pi_n, then the inductive formula is \Sigma_{n+1}. So e.g.
for P(x) that are \Sigma_1, the various instances of the schema are
provable in I\Sigma_1.

Riki


-- 
----------------------------
Richard Kimberly (Riki) Heck
Professor of Philosophy
Brown University

Pronouns: they/them/their

Email:           rikiheck at brown.edu
Website:         http://rkheck.frege.org/
Blog:            http://rikiheck.blogspot.com/
Amazon:          http://amazon.com/author/richardgheckjr
Google Scholar:  https://scholar.google.com/citations?user=QUKBG6EAAAAJ
ORCID:           http://orcid.org/0000-0002-2961-2663
Research Gate:   https://www.researchgate.net/profile/Richard_Heck