๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

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


A predicative and decidable characteriza
โœ S. Caporaso; M. Zito; N. Galesi ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 149 KB

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