ABSOLUTE REALIZABILITY OF PREDICATE FORMULAS (Q3216644)

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 3882421
Language Label Description Also known as
default for all languages
No label defined
    English
    ABSOLUTE REALIZABILITY OF PREDICATE FORMULAS
    scientific article; zbMATH DE number 3882421

      Statements

      ABSOLUTE REALIZABILITY OF PREDICATE FORMULAS (English)
      0 references
      0 references
      1984
      0 references
      generalized predicate
      0 references
      realizers
      0 references
      Heyting's predicate calculus
      0 references
      absolutely realizable formulae
      0 references
      A ''generalized predicate'' of n variables is a function \(| P|\) from \(N^ m\) to the power set of N; thus \(| P(x_ 1,...,x_ n)|\) is a set of integers, thought of as the ''witnesses'' or realizers that \(P(x_ 1,...,x_ n)\) is true. Imitating the definition of realizability, we can then assign a set of realizers \(| \psi (x_ 1,...,x_ n)|\) whenever \(\psi\) is a formula of predicate calculus, the \(x_ i\) are integers, and the assignments \(| P|\) have been made. A closed formula A of predicate calculus is called absolutely realizable if for some number e, we have \(e\in | A|\) regardless of the assignments of \(| P|\). Every theorem of Heyting's predicate calculus is absolutely realizable, but there are more absolutely realizable formulae. The main theorem is that the set AR of absolutely realizable formulae is a complete \(\Pi^ 1_ 1\) set, recursively isomorphic to the set \({\mathcal O}\) of ordinal notations. Note that AR includes the set of formulae, all of whose arithmetical substitution instances are realizable. In previous publications the author has shown that this set is not arithmetical, and properly includes AR. [The reviewer points out that a formula A involving predicate letters \(Q_ 1,...,Q_ n\) is absolutely realized if and only if the formula \(\forall Q_ 1...\forall Q_ n\subset \omega A(Q_ 1,...,Q_ n)\) of set theory is realized in the usual sense of realizability for set theory, as explained e.g. in Chapter 8 of the reviewer's ''Foundations of Constructive Mathematics'' (1985). So the notion of absolute realizability is not really new.]
      0 references

      Identifiers