Derivability conditions on Rosser's provability predicates (Q2641298)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Derivability conditions on Rosser's provability predicates
scientific article

    Statements

    Derivability conditions on Rosser's provability predicates (English)
    0 references
    0 references
    1990
    0 references
    As the author states, this is a complement to a paper by \textit{D. Guaspari} and \textit{R. M. Solovay} [Ann. Math. Logic 16, 81-99 (1979; Zbl 0426.03062)]: the author considers Rosser sentences in the milieu of PRA \((=\) open induction with parameters for primitive recursive functions), while Guaspari and Solvay did so in Peano arithmetic. For a provability predicate \(P(a):=\exists y\theta (y,a)\), the associated Rosser predicate R(a) is defined to be \(\exists y(\theta (y,a)\&\forall z\leq y\neg \theta (z,\neg a))\). [Here and below, Gödel numbering and the like are suppressed.] Given a provability predicate P(a) that satisfies (*) \(\vdash \forall formula x,y[P(x\to y)\to P(x)\to P(y)]\) (`\(\vdash '\) for `PRA\(\vdash ')\), and two other reasonable conditions, the author constructs other predicates \(P_ 1\) and \(P_ 2\) that are equivalent to P, i.e. \(\vdash \forall formula P(x)\leftrightarrow P_ 1(x)\leftrightarrow P_ 2(x)\), and such that their Rosser versions \(R_ 1\) and \(R_ 2\) have the following properties: (*) holds for \(R_ 1\) in place of P, and for \(R_ 2\) (**) \(\vdash \forall formula x[R_ 2(x)\to R_ 2(R_ 2(x))]\). (Of course, neither \(R_ 1\) nor \(R_ 2\) can satisfy both (*) and (**).) The author's construction of these predicates is intricate, but straightforward. Unlike Guaspari and Solovay, he does not go into modality considerations.
    0 references
    primitive recursive arithmetic
    0 references
    Rosser sentences
    0 references
    PRA
    0 references
    open induction
    0 references
    provability predicate
    0 references
    Rosser predicate
    0 references

    Identifiers