It is an open problem within the study of recursively enumerable classes of recursively enumerable sets to characterize those recursively enumerable classes which can be recursively enumerated without repetitions. This paper is concerned with a weaker property of r.e. classes, namely that of being recursively enumerable with at most finite repetitions.

This property is shown to behave more naturally: First we prove an extension theorem for classes satisfying this property. Then the analogous theorem for the property of recursively enumerable classes of being recursively enumerable with a bounded number of repetitions is shown not to hold. The index set of the property of recursively enumerable classes “having an enumeration with finite repetitions” is shown to be -complete.

Assume T is a superstable theory with < 2ℵ0 countable models. We prove that any *- algebraic type of -rank > 0 is m-nonorthogonal to a *-algebraic type of -rank 1. We study the geometry induced by m-dependence on a *-algebraic type p* of -rank 1. We prove that after some localization this geometry becomes projective over a division ring . Associated with p* is a meager type p. We prove that p is determined by p* up to nonorthogonality and that underlies also the geometry induced by forking dependence on any stationarization of p. Also we study some *-algebraic *-groups of -rank 1 and prove that any *-algebraic *-group of -rank 1 is abelian-by-finite.

A method of iteration of Prikry type forcing notions as well as a forcing for adding clubs is presented. It is applied to construct a model with a measurable cardinal containing a club of former regulars, starting with ο(κ) = κ + 1. On the other hand, it is shown that the strength of above is at least

ο(κ) = κ.

Aczel's theory of hypersets provides an interesting alternative to the standard view of sets as inductively constructed, well-founded objects, thus providing a convienent formalism in which to consider non-well-founded versions of classically well-founded constructions, such as the “circular logic” of [3], This theory and ZFC are mutually interpretable; in particular, any model of ZFC has a canonical “extension” to a non-well-founded universe. The construction of this model does not immediately generalize to weaker set theories such as the theory of admissible sets. In this paper, we formulate a version of Aczel's antifoundation axiom suitable for the theory of admissible sets. We investigate the properties of models of the axiom system KPU−, that is, KPU with foundation replaced by an appropriate strengthening of the extensionality axiom. Finally, we forge connections between “non-wellfounded sets over the admissible set A” and the fragment LA of the modal language L∞.

Effective model theory is the subject that analyzes the typical notions and results of model theory to determine their effective content and counterparts. The subject has been developed both in the former Soviet Union and in the west with various names (recursive model theory, constructive model theory, etc.) and divergent terminology. (We use “effective model theory” as the most general and descriptive designation. Harizanov [6] is an excellent introduction to the subject as is Millar [13].) The basic subjects of model theory include languages, structures, theories, models and various types of maps between these objects. There are many ways to introduce considerations of effectiveness into the area. The two most prominent derive from starting, on the one hand, with the notion of a theory and its models or, on the other, with just structures.

If one begins with theories, then a natural version of effectiveness is to consider decidable theories (i.e., ones with a decidable (equivalently, computable or recursive) set of theorems). When one moves to models and wants them to be effective, one might start with the requirement that the model (of any theory) have a decidable theory (i.e., Th (), the set of sentences true in , is decidable). Typically, however, one wants to be able to talk about the elements of the model as well as its theory in the given language. Thus one naturally considers the model as a structure for the language expanded by adding a constant ai, for each element ai of . Of course, one requires that the mapping from the constants to the corresponding elements of be effective (computable). We are thus lead to the following basic definition:

A structure or model is decidable if there is a computable enumeration ai of A, the domain of , such that Th(, ai,) is decidable. (Of course, ai, is interpreted as ai, for each i Є ω.)

A positive answer to a question of M. van Lambalgen and D. Zambella whether there exist nonrecursive sets that are low for the class of random sets is obtained. Here a set A is low for the class RAND of random sets if RAND = RANDA.

Boris Zil'ber conjectured that all strongly minimal theories are bi-interpretable with one of the “classical” sorts: theories of algebraically closed fields, theories of infinite vector spaces over division rings and theories with trivial algebraic closure relations. Hrushovski produced the first two classes of counterexample to this conjecture in [10] and [9]. Subsequently, in [8], the author gave an explicit axiomatization of a special case of [9] from which model completeness could quickly be deduced. It was unclear at that writing whether the model completeness result was true in the general case or was due to peculiarities of the case under consideration. The main new result of this paper is model completeness, not only of the general case in [9], but also of the theories described in [10]. Specifically, we present a general framework in which producing a strongly minimal theory is reduced to finding an elementary class of theories satisfying certain requirements (see below). We present the theories of [10] and [9] as special instances of such theories, giving an explicit axiomatization from which model completeness immediately follows in each case.

We hope by presenting these constructions in parallel, using common language and extracting common elements, to make easier both the exploitation of the ideas involved in their making and their comparison with other recent constructions of a similar flavor. For a selection of such constructions, see [6], [1], [2] and [3]. For more general background, see [2], [4] and [11].

One of the early partition relation theorems which include ordinals was the observation of Erdös and Rado [7] that if κ = cf(κ) > ω then the Dushnik–Miller theorem can be sharpened to κ→(κ, ω + 1)2. The question on the possible further extension of this result was answered by Hajnal who in [8] proved that the continuum hypothesis implies ω1 ↛ (ω1, ω + 2)2. He actually proved the stronger result ω1 ↛ (ω: 2))2. The consistency of the relation κ↛(κ, (ω: 2))2 was later extensively studied. Baumgartner [1] proved it for every κ which is the successor of a regular cardinal. Laver [9] showed that if κ is Mahlo there is a forcing notion which adds a witness for κ↛ (κ, (ω: 2))2 and preserves Mahloness, ω-Mahloness of κ, etc. We notice in connection with these results that λ→(λ, (ω: 2))2 holds if λ is singular, in fact λ→(λ, (μ: n))2 for n < ω, μ < λ (Theorem 4).

In [11] Todorčević proved that if cf(λ) > ω then a ccc forcing can add a counter-example to λ→(λ, ω + 2)2. We give an alternative proof of this (Theorem 5) and extend it to larger cardinals: if GCH holds, cf (λ) > κ = cf (κ) then < κ-closed, κ+-c.c. forcing adds a counter-example to λ→(λ, κ + 2)2 (Theorem 6).

Erdös and Hajnal remarked in their problem paper [5] that Galvin had proved ω2→(ω1, ω + 2)2 and he had also asked if ω2→(ω1, ω + 3)2 is true. We show in Theorem 1 that the negative relation is consistent.

Let κℝ be the least ordinal κ such that Lκ (ℝ) is admissible. Let A = {x ϵ ℝ ∣ (∃α < κℝ) such that x is ordinal definable in Lα (ℝ)}. It is well known that (assuming determinacy) A is the largest countable inductive set of reals. Let T be the theory: ZFC − Replacement + “There exists ω Woodin cardinals which are cofinal in the ordinals.” T has consistency strength weaker than that of the theory ZFC + “There exists ω Woodin cardinals”, but stronger than that of the theory ZFC + “There exists n Woodin Cardinals”, for each n ϵ ω. Let M be the canonical, minimal inner model for the theory T. In this paper we show that A = ℝ ∩ M. Since M is a mouse, we say that A is a mouse set. As an application, we use our characterization of A to give an inner-model-theoretic proof of a theorem of Martin which states that for all n, every real is in A.

Versions of Laver sequences are known to exist for supercompact and strong cardinals. Assuming very strong axioms of infinity, Laver sequences can be constructed for virtually any globally defined large cardinal not weaker than a strong cardinal; indeed, under strong hypotheses. Laver sequences can be constructed for virtually any regular class of embeddings. We show here that if there is a regular class of embeddings with critical point κ, and there is an inaccessible above κ, then it is consistent for there to be a regular class that admits no Laver sequence. We also show that extendible cardinals are Laver-generating, i.e., that assuming only that κ is extendible, there is an extendible Laver sequence at κ. We use the method of proof to answer a question about Laver-closure of extendible cardinals at inaccessibles. Finally, we consider Laver sequences for super-almost-huge cardinals. Assuming slightly more than super-almost-hugeness, we show that there are super-almost-huge Laver sequences, improving the previously known upper bound for such Laver sequences. We also describe conditions under which the canonical construction of a Laver sequence fails for super-almost-huge cardinals.

We prove that Rado's Conjecture implies that the nonstationary ideal on ω1 is presaturated.

Let {We}e∈ω be a standard enumeration of the recursively enumerable (r.e.) subsets of ω = {0,1,2,…}. The lattice of recursively enumerable sets, , is the structure ({We}e∈ω,∪,∩). ≡ is a congruence relation on if ≡ is an equivalence relation on and if for all U, U′ ∈ and V, V′ ∈ , if U ≡ U′ and V ≡ V′, then U ∪ V ≡ U′ ∪ V′ and U ∩ V ≡ U′ ∩ V′. [U] = {V ∈ | V ≡ U} is the equivalence class of U. If ≡ is a congruence relation on , the elements of the quotient lattice / ≡ are the equivalence classes of ≡. [U] ∪ [V] is defined as [U ∪ V], and [U] ∩ [V] is defined as [U ∩ V]. We say that a congruence relation ≡ on is if {(i, j)| Wi ≡ Wj} is . Define =* by putting Wi, =* Wj if and only if (Wi − Wj)∪ (Wj − Wi) is finite. Then =* is a congruence relation. If D is any set, then we can define a congruence relation by putting Wi Wj if and only if Wi ∩ D =* Wj ∩D. By Hammond [2], a congruence relation ≡ ⊇ =* is if and only if ≡ is equal to for some set D.

The Friedberg splitting theorem [1] asserts that if A is any recursively enumerable set, then there exist disjoint recursively enumerable sets A0 and A1 such that A = A0∪ A1 and such that for any recursively enumerable set B

In classical recursion theory, the jump operator is an important concept fundamental in the study of degrees. In particular, it provides a way of defining the hyperarithmetic hierarchy by iterating over Kleene's O. In subrecursion theories, hierarchies (variants of the fast growing hierarchy) are also important in underlying the central concepts, e.g. in classifying provably recursive functions and associated independence results for given theories (see, e.g. [BW87], [HW96], [R84] and [Z77]). A major difference with the hyperarithmetic hierarchy is in the way each level of a subrecursive hierarchy is crucially dependent upon the system of ordinal notations used (see [F62]). This has been perhaps the major stumbling block in finding a classification of all general recursive functions using such hierarchies.

Here we present a natural subrecursive analogue of the jump operator and prove that the hierarchy based on the ”subrecursive jump” is elementarily equivalent to the fast growing hierarchy.

The paper is organised as follows. First the preliminary definitions are given together with a statement of the main theorem and a brief outline of its proof. The proof of the theorem is then given, with the more technical parts separated out as facts which are proven afterwards.

We let {e}g(x) denote computation of the e-th partial recursion with oracle g, on input x. Furthermore [e] denotes the e-th elementary recursive function, defined so that

Similarly, for a given oracle g the e-th relativized elementary function is denoted by [e]g.

We investigate the modal logic of interpretability over Peano arithmetic. Our main result is a compactness theorem that extends the arithmetical completeness theorem for the interpretability logic ILMω. This extension concerns recursively enumerable sets of formulas of interpretability logic (rather than single formulas). As corollaries we obtain a uniform arithmetical completeness theorem for the interpretability logic ILM and a partial answer to a question of Orey from 1961. After some simplifications, we also obtain Shavrukov's embedding theorem for Magari algebras (a.k.a. diagonalizable algebras).

We show that there is a computable Boolean algebra and a computably enumerable ideal I of such that the quotient algebra /I is of Cantor-Bendixson rank 1 and is not isomorphic to any computable Boolean algebra. This extends a result of L. Feiner and is deduced from Feiner's result even though Feiner's construction yields a Boolean algebra of infinite Cantor-Bendixson rank.

We prove that for a natural class of first-order formulas the validity problem is -complete.

An Ax-Kochen-Ershov principle for intermediate structures between valued groups and valued fields.

We will consider structures that we call valued B-groups and which are of the form 〈G, B, *, υ〉 where

– G is an abelian group,

– B is an ordered group,

– υ is a valuation denned on G taking its values in B,

– * is an action of B on G satisfying: ∀x ϵ G ∀ b ∈ B υ(x * b) = ν(x) · b.

The analysis of Kaplanski for valued fields can be adapted to our context and allows us to formulate an Ax-Kochen-Ershov principle for valued B-groups: we axiomatise those which are in some sense existentially closed and also obtain many of their model-theoretical properties. Let us mention some applications:

1. Assume that υ(x) = υ(nx) for every integer n ≠ 0 and x ϵ G, B is solvable and acts on G in such a way that, for the induced action, Z[B] ∖ {0} embeds in the automorphism group of G. Then 〈G, B, *, υ〉 is decidable if and only if B is decidable as an ordered group.

2. Given a field k and an ordered group B, we consider the generalised power series field k((B)) endowed with its canonical valuation. We consider also the following structure:

where k((B))+ is the additive group of k((B)), S is a unary predicate interpreting {Tb ∣ b ϵB}, and ×↾k((B))×S is the multiplication restricted to k((B)) × S, structure which is a reduct of the valued field k((B)) with its canonical cross section. Then our result implies that if B is solvable and decidable as an ordered group, then M is decidable.

3. A valued B–group has a residual group and our Ax-Kochen-Ershov principle remains valid in the context of expansions of residual group and value group. In particular, by adding a residual order we obtain new examples of solvable ordered groups having a decidable theory.

Two countable filters on ω are incompatible if they have no common infinite pseudointersection. Letting (Pf) denote the minimal size of a maximal uncountable family of pairwise incompatible countable filters on ω, we prove the consistency of t < a(Pf).

D'après Lascar et Poizat [10], la déviation pour une théorie stable est associée à un préordre partiel sur l'ensemble des types. L'ordre induit a été nommé par Poizat ordre fondamental. Il mesure combien un type est loin d'être réalisé et il donne un certain nombre d'informations sur la théorie. Une question naturelle, est de décrire completément tous les ordres fondamentaux [13]. Il semble que cela soit difficile. Un problème moins ambitieux est de trouver des conditions pour qu'un ordre soit l'ordre fondamental d'une théorie, ou bien de trouver des exemples.

Le but de cet article est de trouver de nouveaux exemples d'ordres fondamentaux. Nous nous concentrons principalement sur les théories stables et 1-basées car, comme nous allons voir dans la Section 2, avec cette hypothèse, il y a une représentation simple de l'ordre fondamental grâce aux ensembles algébriquement clos d'éléments des modèles de la thé;orie considégrée. Dans la Section 3, nous généralisons une idée de Baldwin et Berman [2] pour construire de “nouveaux” exemples d'ordres fondamentaux. En combinant cette construction avec les résultats de la Section 2, on caractérise de manière complete les ordres fondamentaux de theories triviales et 1-basées: les blocs des ordres fondamentaux d'une théorie triviale et 1-basée sont les inverses des posets de la forme I(L)/G où L est un treillis distributif borné et G un groupe compact d'automorphismes localement fini de L. De plus, tout ordre partiel de cette forme est l'ordre fondamental d'une théorie triviale et 1-basá. En particulier, l'ordre fondamental n'est pas toujours un treillis.

This article provides the proof-theoretic analysis of the transfinitely iterated fixed point theories and ; the exact proof-theoretic ordinals of these systems are presented.