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
1984
0 references
generalized predicate
0 references
realizers
0 references
Heyting's predicate calculus
0 references
absolutely realizable formulae
0 references
0.8255330920219421
0 references
0.8086477518081665
0 references
0.7981409430503845
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