Derivability conditions on Rosser's provability predicates (Q2641298)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4189720
Language Label Description Also known as
default for all languages
No label defined
    English
    Derivability conditions on Rosser's provability predicates
    scientific article; zbMATH DE number 4189720

      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