Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-22T20:36:24.568Z Has data issue: false hasContentIssue false
  • English
  • Français

A sharp version of the bounded Matijasevich conjecture and the end-extension problem

Published online by Cambridge University Press:  12 March 2014

Zofia Adamowicz
Zofia Adamowicz*
Affiliation:
Institute of Mathematics, Polish Academy of Sciences, 00-950 Warsaw, Poland
Get access Rights & Permissions [Opens in a new window]

Extract

Under a sharp version of the assumption I∆0 ⊢ ¬ ∆0H we characterize models of I∆0 + BΣ1 having a proper end extension to a model of I∆0.

In [WP] Wilkie and Paris study the relationship between the existence of a proper end extension of a model and its “fullness”, which is related to a certain weak overspill principle (we recall the definition of fullness in §3). Let M be a countable nonstandard model of I∆0 + BΣ1. Under the hypothesis I∆0 ⊢ ¬ ∆0H they prove the following (Corollaries 7 and 8):

The following are equivalent:

  1. 1) M has a proper end extension to a model of I∆0 + BΣ1.

  2. 2) M is (I∆0 + BΣ1)-full.

Moreover, assuming that there is no t ∈ M such that for v ∈ M, 2[t/v]exists if and only if v < N, the following are equivalent:

  1. 1) M has a proper end extension to a model of I∆0.

  2. 2) M is I∆0-full.

Wilkie and Paris ask whether the assumption on the structure of the model can be eliminated from the second equivalence.

We eliminate it, but we sharpen the assumption I∆0 ⊢ ¬ ∆0H. So we partially answer their question.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 57 , Issue 2 , June 1992 , pp. 597 - 616
Copyright
Copyright © Association for Symbolic Logic 1992

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

[A]Adamowicz, Z., End extending models of I∆ 0 + exp + BΣ1, Fundamenta Mathematicae, vol. 136 (1990), pp. 133–145.CrossRefGoogle Scholar
[D]Davis, M., Hilbert's tenth problem is unsolvable, American Mathematical Monthly, vol. 80 (1973), pp. 233–269.CrossRefGoogle Scholar
[DG]Dimitracopoulos, C. and Gaifman, H., Fragments of Peano's arithmetic and the MRDP theorem, Logic and algorithmic: an international symposium held in honour of Ernst Specker, Monographies de l'Enseignement Mathématique, no. 30, Université de Genève, Geneva, 1982, pp. 187–206.Google Scholar
[DP]Dimitracopoulos, C. and Paris, J., Truth definitions for ∆ 0 formulae, Logic and algorithmic: an international symposium held in honour of Ernst Specker, Monographies de l'Enseignement Mathématique, no. 30, Université de Genève, Geneva, 1982, pp. 317–329.Google Scholar
[P]Parikh, R., Existence and feasibility in arithmetic, this Journal, vol. 36 (1971), pp. 494–508.Google Scholar
[WP]Wilkie, A. and Paris, J., On the existence of end extensions of models of bounded induction, Logic, methodology and philosophy of science (proceedings of the eighth international congress, Moscow, 1987), North-Holland, Amsterdam, 1989, pp. 143–161.CrossRefGoogle Scholar