Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-25T05:15:41.725Z Has data issue: false hasContentIssue false

Ordinal bounds for κ-consistency

Published online by Cambridge University Press:  12 March 2014

Warren D. Goldfarb*
Affiliation:
Society of Fellows, Harvard University Cambridge, Massachusetts 02138

Extract

In [1] the ω-consistency of arithmetic was proved by a method which yields fine ordinal bounds for κ-consistency, κ ≥ 1. In this paper these bounds are shown to be best possible. The ω-consistency of a number-theoretic system S can be expressed thus: for all sentences ∃xM,

where ProvS is the proof predicate for S, if n is a nonnegative integer then n is the formal numeral (of S) for n, and if G is a formula then ˹G˺ is the Gödel number of G. The κ-consistency of S is the restriction of (1) to Σκ0 sentences ∃xM. The proof in [1] establishes the no-counterexample interpretation of (1), that is, the existence of a constructive functional Φ such that, for all sentences ∃xM, all numbers p, and all functions f,

(see [1, §2]). A functional Φ is an ω-consistency functional for S if it satisfies (2) for all sentences ∃xM, and a κ-consistency functional for S if it satisfies (2) for all Σκ0 sentences ∃xM.

The systems considered in [1] are those obtained from classical first-order arithmetic Z, including the schema for definition of primitive recursive (p.r.) functions, by adjoining, for some p.r. well-founded ordering ≺ of the nonnegative integers, the axiom schema

that is, the least number principle on ≺; it is equivalent to the schema of transfinite induction on ≺.

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1974

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.)

References

REFERENCES

[1] Golofarb, W. D. and Scanlon, T. M., The ω-consistency of number theory via Herbrand's theorem, this Journal, vol 39 (1974), pp. 678692.Google Scholar
[2] Hilbert, D. and Bernays, P., Grundlagen der Mathematik, vol. 2, Springer, Berlin, 1970.CrossRefGoogle Scholar
[3] Kreisel, G., A survey of proof theory, this Journal, vol. 33 (1968), pp. 321388.Google Scholar
[4] Schütte, K., Beweistheorie, Springer, Berlin, 1960.Google Scholar
[5] Tait, W. W., Functionals defined by transfinite recursion, this Journal, vol. 30 (1965), pp. 155174.Google Scholar