Powered by OpenAIRE graph
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Journal of Symbolic ...arrow_drop_down
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Journal of Symbolic Logic
Article . 2001 . Peer-reviewed
License: Cambridge Core User Agreement
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article
Data sources: zbMATH Open
versions View all 2 versions

Minimality and completions of PA

Authors: Knight, Julia F.;
Abstract

The results in this paper say that natural upper bounds for sets of degrees associated with theories and models of arithmetic cannot be minimal. The basic new result says that for any completion T of PA, there is another completion S such that S<TT and Rep(S) = Rep(T). This immediately implies that deg(T) is not minimal over {deg(X): X ∈ Rep(T)}. As an application of the basic result, we obtain the fact that if is a non-standard model of TA (true arithmetic), then deg () cannot be minimal over {deg(X): X is arithmetical}. More generally, if is a non-standard model of an arbitrary completion T of PA, then deg() cannot be minimal over {deg(): X ∈ Rep(T)}. We vary the basic result, making S′ ≡TT′. As an application of the variant, we obtain the fact that if is a non-standard model of PA, then {deg(): ≅ } has no minimal element.The remainder of the present section gives a brief account of the background needed for the basic new result and the variant. These two results are proved in Section 2. The applications are given in Section 3, along with further background needed for the applications. One important source of ideas used in the present paper is a paper of Scott [9]. In addition, there are ideas taken from Tennenbaum [12], Feferman [3], Marker [6], [7], and Solovay. Chapter 19 of [1] gathers together most of this material. In fact, it contains all that is really essential. In one application, we appeal to Solovay's result on degrees of models of an arbitrary completion of PA, a result which is not completely proved in [1]. However, for the best application, which implies all the others, we use only some ideas from the proof of Solovay's theorem. These are given in lemmas that are proved in Section 3, where they are needed, or taken from [1], While the proof of Solovay's result requires an infinitely nested priority construction, our best application rests on nothing more than finite-injury constructions.

Related Organizations
Keywords

First-order arithmetic and fragments, Models of arithmetic and set theory, Nonstandard models of arithmetic, Other Turing degree structures, Turing degrees, Undecidability and degrees of sets of sentences, Scott sets, nonstandard models

  • BIP!
    Impact byBIP!
    citations
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    2
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
citations
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
2
Average
Average
Average