Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-17T05:49:53.591Z Has data issue: false hasContentIssue false

A modified sentence unprovable in PA

Published online by Cambridge University Press:  12 March 2014

L. Gordeev*
Affiliation:
WSI fur Informatik, Mathematische Logik, Universitat Tubingen, D-72076 Tubingen, Germany, E-mail: gordeew@chapelle.informatik.uni-tuebingen.de

Extract

H. Friedman proved that the following sentence SWQO() is true but not provable in the theory ATR0 (cf. [S]; ≔ the set of finite rooted trees, ∣T∣ ≔ the cardinality of T ∈ ).

For every k > 0 there is an n so large that for any T0, T1,…, Tn ∈ with ∀i ≤ n(∣Ti∣ ≤ k · (i + 1)) there are i < j ≤ n such that Ti is homeomorphically embeddable into Tj.

Since ATR0 is stronger than PA, SWQO() is not provable in PA, either. Furthermore, SWQO() is proof-theoretically stronger than PA. A similar sentence whose proof-theoretical strength is exactly that of PA was obtained by replacing finite trees by finite sequences of bounded natural numbers under the embeddability with H. Friedman's asymmetrical gap-condition (see [SS]). The latter sentence was modified by using the weaker symmetrical gap-condition (see the corresponding particular case in [Gl]). Further improvement is indicated in [G2, Corollary 4.5]. Namely, the assertion ∣Xi∣ ≤ k · (i + 1) as in SWQO(J), above, can be weakened to

.

(in fact, to wt(Xi) ≤ k + ε · i for an arbitrary fixed ε = l−1, l < 0, where wt(X) is the weight of the “word” X).

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable