The concern of this paper is with recursively enumerable and co-recursively enumerable subspaces of a recursively presented vector spaceV∞ over a (finite or infinite) recursive field F which is defined in [6] to consist of a recursive subset U of the natural numbers N and operations of vector addition and scalar multiplication which are partial recursive and under which V∞ becomes a vector space. Throughout this paper, we will identify V∞ with N, say via some fixed Gödel numbering, and assume V∞ is infinite dimensional and has a dependence algorithm, i.e., there is a uniform effective procedure which determines whether or not any given n-tuple v0, …, vn−1 from V∞ is linearly dependent. Various properties of V∞ and its sub-spaces have been studied by Dekker [1], Guhl [3], Metakides and Nerode [6], Kalantari and Retzlaff [4], and the author [7].

Given a subspace W of V∞, we say W is r.e. (co-r.e.) if W(V∞ − W) is an r.e. subset of N and write dim(V) for the dimension of V. Given subspaces V, W of V∞, V + W will denote the weak sum of V and W and if V ⋂ M = {0} (where 0 is the zero vector of V∞), we write V ⊕ Winstead of V + W. If W ⊇ V, we write Wmod V for the quotient space. An independent set A ⊆ V∞ is extendible if there is an r.e. independent set I ⊇ A such that I − A is infinite and A is nonextendible if it is not the case An is extendible. A r.e. subspace M ⊇ V∞ is maximal if dim(V∞ mod M) = ∞ and for any r.e. subspace W ⊇ Meither dim(W mod M) < ∞ or dim(V∞ mod W) < ∞.

This paper deals with Hilbert's substitution method for eliminating bound variables from first order proofs. With a first order system S framed in the ε-calculus [2] the problem is to associate a system S' without bound variables and an effective procedure for transforming derivations in S into derivations in S′. The transform of a formula A derived in S is to be an “ε-substitution instance” of A, i.e. it is obtained by replacing terms εxB(x) in A by terms of S′. In general the choice of these terms will depend on the particular derivation of A, and not on A alone. Cf. [4]. The present formulation sharpens Hilbert's original statement of the problem, i.e. that the transform of A should be finitistically verifiable, by making explicit the methods of verification used, namely those formalized in S′; on the other hand, it generalizes Hilbert's formulation since S′ need not be restricted to finitist systems.

The bound variable elimination procedure can always be taken to be primitive recursive in (the Gödel number of) the derivation of A. Constructions which transcend primitive recursion can simply be built into S′.

In this paper we show that if S′ is taken to be a second order system with constants for functionals, then the existence of suitable ε-substitution instances can be expressed by the solvability of certain functional equations in S′. We deal with two cases here. If S is number theory without induction, i.e. essentially predicate calculus with identity, then we can solve the equations in question by taking for S′ the free variable part S* of S with an added rule of definition of functionals by cases (recursive definition on finite ordinals), which is a conservative extension of S*.

Limiting identification of r.e. indexes for r.e. languages (from a presentation of elements of the language) and limiting identification of programs for computable functions (from a graph of the function) have served as models for investigating the boundaries of learnability. Recently, a new approach to the study of “intrinsic” complexity of identification in the limit has been proposed. This approach, instead of dealing with the resource requirements of the learning algorithm, uses the notion of reducibility from recursion theory to compare and to capture the intuitive difficulty of learning various classes of concepts. Freivalds, Kinber, and Smith have studied this approach for function identification and Jain and Sharma have studied it for language identification.

The present paper explores the structure of these reducibilities in the context of language identification. It is shown that there is an infinite hierarchy of language classes that represent learning problems of increasing difficulty. It is also shown that the language classes in this hierarchy are incomparable, under the reductions introduced, to the collection of pattern languages.

Richness of the structure of intrinsic complexity is demonstrated by proving that any finite, acyclic, directed graph can be embedded in the reducibility structure. However, it is also established that this structure is not dense. The question of embedding any infinite, acyclic, directed graph is open.

Let E be a computably enumerable (c.e.) equivalence relation on the set ω of natural numbers. We say that the quotient set $\omega /E$ (or equivalently, the relation E) realizes a linearly ordered set ${\cal L}$ if there exists a c.e. relation ⊴ respecting E such that the induced structure ($\omega /E$; ⊴) is isomorphic to ${\cal L}$. Thus, one can consider the class of all linearly ordered sets that are realized by $\omega /E$; formally, ${\cal K}\left( E \right) = \left\{ {{\cal L}\,|\,{\rm{the}}\,{\rm{order}}\, - \,{\rm{type}}\,{\cal L}\,{\rm{is}}\,{\rm{realized}}\,{\rm{by}}\,E} \right\}$. In this paper we study the relationship between computability-theoretic properties of E and algebraic properties of linearly ordered sets realized by E. One can also define the following pre-order $ \le _{lo} $ on the class of all c.e. equivalence relations: $E_1 \le _{lo} E_2 $ if every linear order realized by E1 is also realized by E2. Following the tradition of computability theory, the lo-degrees are the classes of equivalence relations induced by the pre-order $ \le _{lo} $. We study the partially ordered set of lo-degrees. For instance, we construct various chains and anti-chains and show the existence of a maximal element among the lo-degrees.

Retraceable sets were denned in Dekker and Myhill [5]. In that paper it was pointed out that if A is a retraceable set, then A is recursive in each of its infinite subsets, i.e. A is introreducible. We would like to know to what extent theorems on retraceable sets also hold for introreducible sets; however, we have made very little progress in this direction. On the other hand, “uniformly introreducible” sets (which will be defined in §2) are more tractable, and it turns out that some results on retraceable sets extend to uniformly introreducible sets while others fail.

In this paper I shall show that no one of the four primitive symbols of Heyting's calculus of propositions is definable in terms of the other three. So as to make the paper self-contained, I begin by stating the rules and primitive sentences given by Heyting.

The primitive symbols of the calculus are “⅂”, “∨”, “∧”, and “⊃”, which may be read, respectively, as “not,” “either…or,” “and,” and “if…then.” The symbol “⊃⊂”, which may be read “if and only if,” is defined in terms of these as follows:

The rule of substitution is assumed, and the rule that S2 follows from S1 and S1⊃S2; in addition it is assumed that S1∧S2 follows from S1 and S2. The primitive sentences are as follows:

We show the consistency, relative to a supercompact cardinal, of the least measurable cardinal being both strongly compact and fully Laver indestructible. We also show the consistency, relative to a supercompact cardinal, of the least strongly compact cardinal being somewhat supercompact yet not completely supercompact and having both its strong compactness and degree of supercompactness fully Laver indestructible.

We revisit the foundations of positive model theory, introducing h-inductive sentences. These allow a considerably simplified presentation of positive model theory, as well as a characterisation of Hausdorffcats by an amalgamation property of their h-inductive theory.

By induction for a formula φ we mean the schema

(where the terms in brackets are implicitly substituted for some fixed variable, with the usual restrictions). Let be the schema IAφ for φ in Πn (i.e. ); similarly for . Each instance of is Δn+2, and each instance of is Σn+1 Thus the universal closure of an instance α is Πn+2 in either case. Charles Parsons [72] proved that and are equivalent over Z0, where Z0 is essentially Primitive Recursive Arithmetic augmented by classical First Order Logic [Parsons 70].

Theorem. For each n > 0 there is a Πn formula π for whichis not derivable in Z0from

(i) true Πn+1sentences; nor even

(ii) Πn+1sentences consistent withZ0.

A structure is recursive if the set of quantifier-free sentences in the complete diagram ⊿() of is recursive. It has been known for some time that every decidable theory has a recursive model. In fact, every decidable theory has a decidable model (that is a model such that ⊿() is recursive). In this paper we find other conditions which imply that a theory have a recursive model.

In §1 we study the relation between an ℵ0-categorical theory T having a recursive model and the complexity of the quantificational hierarchy of that theory. We let ∃0 denote the set of quantifier-free sentences, and let ∃n÷1 denote the set of sentences beginning with an existential quantifier and having n alternations of quantifiers. (∀n is defined analogously.) Then we show that if T is an arithmetical ℵ0-categorical theory such that T ⋂ ∃n÷2 is Σn÷10 for each n < ω, then T has a recursive model. We show that this is a best possible result by giving an example of a ⊿n÷20 ℵ0-categorical theory T such that T ⋂ ∃n÷1 is recursive yet T has no recursive model.

In §2 we consider the theory of trees. Ershov [1] had proved that every Σ10 theory of trees has a recursive model. We show this to be best possible by giving an example of a ⊿20 theory of trees which has no recursive model.

Cherlin and Dickmann [2] proved that the theory RCVR of real closed (valuation) rings admits quantifier-elimination (q.e.) in the language ℒ = {+, −, ·, 0, 1, <, ∣} for ordered rings augmented by the divisibility relation “∣”. The purpose of this paper is to prove a form of converse of this result:

Theorem. Let T be a theory of ordered commutative domains (which are not fields), formulated in the language ℒ. In addition we assume that:

• (1) The symbol “∣” is interpreted as the honest divisibility relation:

• (2) The following divisibility property holds in T:

• 

If T admits q.e. in ℒ, then T = RCVR.

We do not know at present whether the restriction imposed by condition (2) can be weakened.

The divisibility property (DP) has been considered in the context of ordered valued fields; see [4] for example. It also appears in [2], and has been further studied in Becker [1] from the point of view of model theory. Ordered domains in which (DP) holds are called in [1] convexly ordered valuation rings, for reasons which the proposition below makes clear. The following summarizes the basic properties of these rings:

Proposition I [2, Lemma 4]. (1) Let A be a linearly ordered commutative domain. The following are equivalent:

• (a) A is a convexly ordered valuation ring.

• (b) Every ideal (or, equivalently, principal ideal) is convex in A.

• (c) A is a valuation ring convex in its field of fractions quot(A).

• (d) A is a valuation ring and its maximal ideal MA is convex (in A or, equivalently, in quot (A)).

• (e) A is a valuation ring and its maximal ideal is bounded by ± 1.

A set S of natural numbers is called recursively enumerable if there is a general recursive function F(x, y) such that

In other words, S is the projection of a two-dimensional general recursive set. Actually, it is no restriction on S to assume that F(x, y) is primitive recursive. If S is not empty, it is the range of the primitive recursive function

where a is a fixed element of S. Using pairing functions, we see that any non-empty recursively enumerable set is also the range of a primitive recursive function of one variable.

We use throughout the logical symbols ⋀ (and), ⋁ (or), → (if…then…), ↔ (if and only if), ∧ (for every), and ∨(there exists); negation does not occur explicitly. The variables range over the natural numbers, except as otherwise noted.

Martin Davis has shown that every recursively enumerable set S of natural numbers can be represented in the form

where P(y, b, w, x1 …, xλ) is a polynomial with integer coefficients. (Notice that this would not be correct if we replaced ≤ by <, since the right side of the equivalence would always be satisfied by b = 0.) Conversely, every set S represented by a formula of the above form is recursively enumerable. A basic unsolved problem is whether S can be defined using only existential quantifiers.

It is known that a countable $\omega $ -categorical structure interprets all finite structures primitively positively if and only if its polymorphism clone maps to the clone of projections on a two-element set via a continuous clone homomorphism. We investigate the relationship between the existence of a clone homomorphism to the projection clone, and the existence of such a homomorphism which is continuous and thus meets the above criterion.

Fried and Kollár constructed a fully faithful functor from the category of graphs to the category of fields. We give a new construction of such a functor and use it to resolve a longstanding open problem in computable model theory, by showing that for every nontrivial countable structure ${\cal S}$, there exists a countable field ${\cal F}$ of arbitrary characteristic with the same essential computable-model-theoretic properties as ${\cal S}$. Along the way, we develop a new “computable category theory”, and prove that our functor and its partially defined inverse (restricted to the categories of countable graphs and countable fields) are computable functors.

We give examples of calculi that extend Gentzen’s sequent calculus LK by unsound quantifier inferences in such a way that (i) derivations lead only to true sequents, and (ii) proofs therein are nonelementarily shorter than LK-proofs.

In this paper I am going to set forth a formal system based on five inter-class relations. These relations exist respectively between a class of a's and a class of b's.

(i) if and only if every a is a b and every b is an a,

(ii) if and only if every a is a b and not every b is an a,

(iii) if and only if it is not the case that either every a is a b or every b is an a or no a is a b,

(iv) if and only if every b is an a and not every a is a b,

(v) if and only if no a is a b.

These relations between classes, which correspond, as will be seen, to the five relations between two circles a and b shown in the well-known Eulerian diagrams,

are of course connected in an intimate way with the four forms of proposition, A, E, I, O, of the traditional syllogistic logic. The French mathematician, J. D. Gergonne, seems to have been the first to recognize these relations explicitly and to understand their importance in syllogistic theory. It is therefore appropriate that they should be called by his name.

Gergonne first of all showed with reference to these relations what are the sufficient and necessary conditions of the truth of propositions of each of the four traditional forms: for example, an A proposition, ‘All a is b’ is true if and only if either the first or the second relation exists between the class of a's and the class of b's.

The Rainbow Ramsey Theorem is essentially an “anti-Ramsey” theorem which states that certain types of colorings must be injective on a large subset (rather than constant on a large subset). Surprisingly, this version follows easily from Ramsey's Theorem, even in the weak system RCA0 of reverse mathematics. We answer the question of the converse implication for pairs, showing that the Rainbow Ramsey Theorem for pairs is in fact strictly weaker than Ramsey's Theorem for pairs over RCA0. The separation involves techniques from the theory of randomness by showing that every 2-random bounds an ω-model of the Rainbow Ramsey Theorem for pairs. These results also provide as a corollary a new proof of Martin's theorem that the hyperimmune degrees have measure one.

We study the strictness of the modal μ-calculus hierarchy over some restricted classes of transition systems. First, we prove that over transitive systems the hierarchy collapses to the alternation-free fragment. In order to do this the finite model theorem for transitive transition systems is proved. Further, we verify that if symmetry is added to transitivity the hierarchy collapses to the purely modal fragment. Finally, we show that the hierarchy is strict over reflexive frames. By proving the finite model theorem for reflexive systems the same results holds for finite models.

Contents: Introduction. §1: Computable rings and modules. §2: Ideal membership relation. §3: Effective structured domains. §4: Completion of a local ring as a domain. §5: The recursive completion. Epilogue. References.

Introduction. Completion is an important general mathematical device. Often, but not always, a completion takes the following form. Let A be a topological algebraic structure whose topology is derived from a metric. For A, a topological algebra  and an embedding i: A →  are constructed such that  is a complete metric space in which A is densely embedded by i. The long list of structures for which such completions exist begins with Cantor's construction of the real number field and includes objects like the p-adic integers, Baire space, and Boolean algebras. In Bourbaki [6] a careful and thorough account of completions for arbitrary topological groups and fields is given, for which it is important to note that the topological structures need not be metrizable, but must possess a uniformity.

The effectiveness of the completion process of a computable structure A cannot be readily studied using the tools of computable algebra, simply because the resulting structure  is almost invariably uncountable. However, in particular cases, it has been possible to define and study the substructure Ak of computable elements of Â; this has been done for the structures mentioned above, starting with the field of recursive real numbers.

In this paper we analyse the effectivity of the completion of a local ring R. We do this using structured Scott-Ershov domains. Our study may be considered as a prototype containing methods applicable to a broad class of completions, including all the examples mentioned above, except for the real number field, which needs a generalisation of the domain concept.

A Scott-Ershov domain D formalises how a set Dt of possibly “infinite” elements, called total elements, is constructed from a set Dc of “finite” elements, called compact elements. This is achieved by means of an approximation ordering which determines a topology on D and, in particular, on Dt . Our methodology is to associate to a given topological algebra A a structured domain D(A) such that the total elements D(A)t form a topological algebra topologically isomorphic to A. In such circumstances A is said to be domain definable by D(A). The theory of computability for domains is now applied to study the effectivity of the topological algebra A.

We show that for every computable limit ordinal α, there is a computable structure that is categorical, but not relatively categorical (equivalently, it does not have a formally Scott family). We also show that for every computable limit ordinal α, there is a computable structure with an additional relation R that is intrinsically on , but not relatively intrinsically on (equivalently, it is not definable by a computable Σα formula with finitely many parameters). Earlier results in [7], [10], and [8] establish the same facts for computable successor ordinals α.