Decidable classes of number-theoretic sentences
โ Scribed by I. J. Heath
- Publisher
- John Wiley and Sons
- Year
- 1969
- Tongue
- English
- Weight
- 507 KB
- Volume
- 15
- Category
- Article
- ISSN
- 0044-3050
No coin nor oath required. For personal study only.
โฆ Synopsis
DECIDABLE CLASSES OF NUMBER-THEORETIC SENTENCES by I. J. HEATH in Leicester (England) A. Method of Construction 1. Limited Constituents Terminology. Let h ' denote the class of natural numbers 0, 1 , 2 , . . . We say that P ( x l , . . . , x,) is a predicate if P : N" -+ ( 0 , l}, and that f(xl, . . . , x,) is a function if f : N n -+ N . We find it expedient to treat predicates and functions together under the single term Constituents. We usually denote a set of constituents in the form: P, Q , . . . ; f , g , . . ., where P, Q , . . . are the predicates in the set, and f , g , . . . are the functions in the set. The reader may consult [3] for omitted proofs and details. L i m i t e r s a n d t h e i r r e p r e s e n t a t i v e functions. Let B,,, . . . be an increasing sequence of finite Booman algebras of subsets of N , such that, for every positive integer 1, we have { I -1) E 8 1 . The B l are called limiters. Let B1x denote {BE B1: x E B } , and let p1x be any function which selects a unique element of B1x, i.e. Vx(,!lzx E Bzx) and V x , y ( B p = Bly + = Bly), then 812 is called a representative function for 231. I n particular, if minA denotes the least member of A , then minBzx is a representative function for BZ.
๐ SIMILAR VOLUMES
Characterizations of PTIME, PSPACE, the polynomial hierarchy and its elements are given, which are decidable (membership can be decided by syntactic inspection to the constructions), predicative (according to points of view by Leivant and others), and are obtained by means of increasing restrictions