The minimal e-degree problem in fragments of Peano arithmetic (Q705537)

From MaRDI portal
Revision as of 16:50, 7 June 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
The minimal e-degree problem in fragments of Peano arithmetic
scientific article

    Statements

    The minimal e-degree problem in fragments of Peano arithmetic (English)
    0 references
    31 January 2005
    0 references
    The paper presents several results concerning the e-degrees over models of fragments of Peano Arithmetic. By an unpublished result of \textit{L. Gutteridge} [Some results on enumeration reducibility. Ph.D. Thesis, Simon Fraser Univ. (1971)], there is no minimal e-degree for the standard model. The authors extend this to regular sets in models of \(B\Sigma_2\). A subset of a model \(M\) is called \textit{regular}, if its intersection with any interval \([0,a]\) in \(M\) is \(M\)-finite. An e-degree is regular, if it contains a regular set. It is shown that there are no \(\Delta_2\) minimal e-degrees in models of \(B\Sigma_2\), and that any regular minimal e-degree in a model of \(B\Sigma_2\) is \(\Delta_2\). Hence, if a model of \(B\Sigma_2\) has a minimal e-degree, it cannot be regular. If \(M\) is a model of \(I\Sigma_2\), then \(M\) has a minimal e-degree iff it is standard, and, if \(M\) is nonstandard, then every cut in \(M\) is of a minimal degree. The situation is different under \(B\Sigma_2\). A \(B\Sigma_2\) model is a model of \(B\Sigma_2+\lnot I\Sigma_2\). There is a \(B\Sigma_2\) model in which no \(\Sigma_2\) cut is of a minimal e-degree, and there is one whose all \(\Sigma_2\) cuts have a minimal e-degree. The paper concludes with a list of open problems and a conjecture that there is a minimal e-degree in every \(B\Sigma_2\) model.
    0 references
    0 references
    e-degrees
    0 references
    fragments of arithemtic
    0 references
    \(\Sigma_2\)-collection
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references