Applications of Strict Π11 predicates to infinitary logic
- 17 November 1969
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 34 (3) , 409-423
- https://doi.org/10.2307/2270906
Abstract
Consider the predicate of natural numbers defined by: where R is recursive. If, as usual, the variable ƒ ranges over ωω (the set of functions from natural numbers to natural numbers) then this is just the usual normal form for Π11 sets. If, however, ƒ ranges over 2ω (the set of functions from ω into {0, 1}) then every such predicate is recursively enumerable.3 Thus the second type of formula is generally ignored. However, the reduction just mentioned requires proof, and the proof uses some form of the Brower-König Infinity Lemma.Keywords
This publication has 5 references indexed in Scilit:
- Infinitary logic and admissible setsThe Journal of Symbolic Logic, 1969
- Elements of Mathematical Logic. Gy G. Kreisel and J. L. Krivine. Pp. 222. 64s. 1967.The Mathematical Gazette, 1969
- Implicit definability and infinitary languagesThe Journal of Symbolic Logic, 1968
- The Syntax and Semantics of Infinitary LanguagesPublished by Springer Nature ,1968
- Nonaxiomatizability results for infinitary systemsThe Journal of Symbolic Logic, 1967