PA theorem
Richard Kimberly Heck
richard_heck at brown.edu
Sun Jul 18 03:13:49 EDT 2021
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
More information about the FOM
mailing list