The dominical categories were introduced by Di Paola and Heller, as a first step toward a category-theoretic treatment of the generalized first Godel incompleteness theorem [1]. In his Ph.D. dissertation [7], Rosolini subsequently defined the closely related p-categories, which should prove pertinent to category-theoretic representations of incompleteness for intuitionistic systems. The precise relationship between these two concepts is as follows: every dominical category is a pointed p-category, but there are p-categories, indeed pointed p-isotypes (all pairs of objects being isomorphic) with a Turing morphism that are not dominical. The first of these assertions is an easy consequence of the fact that in a dominical category C by definition the near product functor when restricted to the subcategory Ct, of total morphisms of C (as “total” is defined in [1]) constitutes a bona fide product such that the derived associativity and commutativity isomorphisms are natural on C × C × C and C × C, respectively, as noted in [7]. As to the second, p-recursion categories (that is, pointed p-isotypes having a Turing morphism) that are not dominical were defined and studied by Montagna in [6], the syntactic p-categories ST and S′T associated with consistent, recursively enumerable extensions of Peano arithmetic, PA. These merit detailed investigation on several counts.

Dominical categories are categories in which the notions of partial morphisms and their domains become explicit, with the latter being endomorphisms rather than subobjects of their sources. These categories form the basis for a novel abstract formulation of recursion theory, to which the present paper is devoted. The abstractness has of course its usual concomitant advantage of generality: it is interesting to see that many of the fundamental results of recursion theory remain valid in contexts far removed from their classic manifestations. A principal reason for introducing this new formulation is to achieve an algebraization of the generalized incompleteness theorem, by providing a category-theoretic development of the concepts and tools of elementary recursion theory that are inherent in demonstrating the theorem. Dominical recursion theory avoids the commitment to sets and partial functions which is characteristic of other formulations, and thus allows for an intrinsic recursion theory within such structures as polyadic algebras. It is worthy of notice that much of elementary recursion theory can be developedwithout referencetoelements. By Gödel's generalized incompleteness theorem for consistent arithmetical systemTwe mean any statement of the following sort: (1) if every recursive set is definable inT, thenTis essentially undecidable [41]; or (2) if all recursive functions are definable inT, thenTis essentially undecidable [41]; or (3) if every recursive set is definable inT, thenT0andR0(the sets of Gödel numbers of the theorems and refutables ofT) are recursively inseparable [39]; or (4) if all re sets are representable inT, thenT0is creative [28], [39]; or (5) ifTis a Rosser theory (i.e., all disjoint re sets are strongly separable inT), thenT0andR0are effectively inseparable [39].

Abstract R. M. Friedberg demonstrated the existence of a recursive functional that agrees with no Banach-Mazur functional on the class of recursive functions. In this paper Friedberg's result is generalized to both α-recursive functionals and weak α-recursive functionals for all admissible ordinals α such that λ < α*, where α* is the Σ1-projectum of α and λ is the Σ2-cofinality of α. The theorem is also established for the metarecursive case, α = ω1, where α* = λ = ω.

This note is concerned with an aspect of the length of proof of formulas in recursively enumerable theories T adequate for recursive arithmetic. In particular, we consider the relative length of proof of formulas in the theories T and T(S), where F represents an r.e. set A in T and T(S) is the theory obtained from T by adjunction, as a new axiom, of a sentence S undecidable in T. Throughout the sequel T is a consistent, r.e. theory with standard formalization [7] in which all recursive functions of one variable are definable, and in which there is a binary formula x ≤ satisfying the well-known conditions [7]: Here is the constant term corresponding to the natural number n. Wn is the nth r.e. set in a standard enumeration of the r.e. sets. Also, we assume an a priori Gödel numbering of our formalism satisfying the usual conditions, so that all formulas are numbers ab initio. In the more common applications of the theorem below, if F is a k-ary formula of T, is a natural number that measures in some way the length of the shortest proof of in T.

In connection with the development of an actual question-answering system, the Relational Data File of The Rand Corporation, a class of formulas of the predicate calculus, the definite formulas of Kuhns, was proposed as the class of symbolic representations of the “reasonable” questions to put to this retrieval system. Roughly speaking, the definite formulas are those formulas F such that the set of true substitution instances of F in a finite interpretation I are preserved on passage to a certain special extension I ′ of I . The proper formulas are those definite formulas which are supposedly especially suitable for machine processing. It has previously been shown by the author that the decision problem for the class of definite formulas is recursively unsolvable. In this paper, however, it is shown that the decision problem for various classes of proper formulas is solvable. Thus, for each of these classes there is a mechanical procedure to decide of an arbitrary formula whether it is a member of the class. It follows that for each of these classes there is no effective transformation @@@@ which takes an arbitrary definite formula F into a proper equivalent @@@@( F ). In addition, it is shown that the decision problems for a number of classes of formulas which bear a structural similarity to any class of proper formulas are recursively unsolvable.

The Relational Data File (RDF) of The Rand Corporation is among the most developed of question-answering systems. The "information language" of this system is an applied predicate calculus. The atomic units of information are binary relational sentences. The system has an inference-making capacity.As part of the actual construction and implementation of the RDF, a theory was developed by J. L. Kuhns to identify those formulas of the predicate calculus which represent the "reasonable" inquiries to put to this system. Accordingly, the classes of definite and proper formulus were defined, and their properties studied. The definite formulas share a semantic property Kuhns judged as necessarily possessed by a reasonable question to be processed by the RDF. The author has previously shown that the decision problem for the class of definite formulas is recursively unsolvable. The proper formulas are definite, and satisfy additional syntactic conditions intended to make them especially suitable for machine processing. The class of proper formulas depends on which logical primitives are employed. Different primitives give rise to different classes of formulas. A formula which can be effectively transformed into a proper equivalent is admissible. Kuhns conjectures that with respect to one particular class of proper formulas, all definite formulas are admissible. In the paper it is shown that the decision problem for several classes of proper formulas is solvable. The following results are established. Theorem 1: The class of proper formulas in prenex form on any complete set of connectives is recursive. Theorem 2: The class of proper formulas on ¬, ∨, ∃ is recursive. Theorem 3: The class of proper formulas on ¬, ⊃, ∃ is recursive. Theorem 4: The class of proper formulas on ¬, ⊃, ∨, ∃, is recursive. Thus, there is a mechanical decision procedure which determines whether an arbitrary formula is a member of the class. It follows that the analogues of Kuhns' conjecture for these classes are false.

A class of formulas of the first-order predicate calculus, the definite formulas has recently been proposed as the formal representation of the “reasonable” questions to put to a computer in the context of an actual data retrieval system, the Relational Data File of Levien and Maron. It is shown here that the decision problem for the class of definite formulas is recursively unsolvable. Hence there is no algorithm to decide whether a given formula is definite.

Successive modifications of Church's definition of a random sequence are considered in terms of their relative position in the Ritchie hierarchy of Kalmar elementary functions. A general result is derived governing the classification of Church random sequences in subrecursive hierarchies which include the elementary functions, such as the Grzegorczyk and Kleene subrecursive hierarchies.

In this paper we study some of the consequences of adding as new axioms to consistent re (recursively enumerable) extensions T of Peano arithmetic P sentences undecidable in T of the Π10 variety, as are those one naturally comes upon. The question arises: how much can two extensions “differ” when each is obtained by adding just once distinct Π10 sentences undecidable in T? We shall show that if T is as stated above, we can find extensions T1 and T2, constructed very simply from T, having the property that if (A, B) is any pair of re sets with recursive intersection, there can be found a Π10 formula of P which represents A in T1 and B in T2.

Following [1] we write {n} for the nth recursively enumerable (re) set; that is, {n} = {x|VyT(n, x, y)}. By a “pair (T, α)” we mean a consistent re extension T of Peano arithmetic P and an RE-formula α which numerates the non-logical axioms of T in P [4]. Given a pair (T, α) and a particular formula which binumerates the Kleene T predicate in P, there can be defined a primitive recursive function Nα such that and which has the additional property that {Nα(Nα(n))} = ø for all n.