Let ε stand for the set of nonnegative integers (numbers), V for the class of all subcollections of ε (sets), Λ for the set of isols, and for the set of mappings from a subset of ε into ε (functions). I f is a function we write δf and ρf for its domain and range respectively. The relation of inclusion is denoted by ⊂ and that of proper inclusion by ⊊. The sets α and β are recursively equivalent [written: α ≃ β], if δf = α and ρf = β for some function f with a one-to-one partial recursive extension f. We denote the recursive equivalence type of α, {σ ∈ V ∣ ≃ α}, by Req(α). Also R stands for Req(ε), while ΛR denotes the collection of all regressive isols. The reader is assumed to be familiar with the contents of [1] and [6].

We define the Scott complexity of a countable structure to be the least complexity of a Scott sentence for that structure. This is a finer notion of complexity than Scott rank: it distinguishes between whether the simplest Scott sentence is $\Sigma _{\alpha }$ , $\Pi _{\alpha }$ , or $\mathrm {d-}\Sigma _{\alpha }$ . We give a complete classification of the possible Scott complexities, including an example of a structure whose simplest Scott sentence is $\Sigma _{\lambda + 1}$ for $\lambda $ a limit ordinal. This answers a question left open by A. Miller.

We also construct examples of computable structures of high Scott rank with Scott complexities $\Sigma _{\omega _1^{CK}+1}$ and $\mathrm {d-}\Sigma _{\omega _1^{CK}+1}$ . There are three other possible Scott complexities for a computable structure of high Scott rank: $\Pi _{\omega _1^{CK}}$ , $\Pi _{\omega _1^{CK}+1}$ , $\Sigma _{\omega _1^{CK}+1}$ . Examples of these were already known. Our examples are computable structures of Scott rank $\omega _1^{CK}+1$ which, after naming finitely many constants, have Scott rank $\omega _1^{CK}$ . The existence of such structures was an open question.

Let K be an algebraically closed field and let L be its canonical language; that is, L consists of all relations on K which are definable from addition, multiplication, and parameters from K. Two sublanguages L 1 and L 2 of L are definably equivalent if each relation in L 1 can be defined by an L 2-formula with parameters in K, and vice versa. The equivalence classes of sublanguages of L form a quotient lattice of the power set of L about which very little is known. We will not distinguish between a sublanguage and its equivalence class.

Let L m denote the language of multiplication alone, and let L a denote the language of addition alone. Let f ∈ K [X, Y] and consider the algebraic function defined by f (x, y) = 0 for x, y ∈ K. Let L f denote the language consisting of the relation defined by f. The possibilities for L m ∨ L f are examined in §2, and the possibilities for L a ∨ L f are examined in §3. In fact the only comprehensive results known are under the additional hypothesis that f actually defines a rational function (i.e., when f is linear in one of the variables), and in positive characteristic, only expansions of addition by polynomials (i.e., when f is linear and monic in one of the variables) are understood. It is hoped that these hypotheses will turn out to be unnecessary, so that reasonable generalizations of the theorems described below to algebraic functions will be true. The conjecture is that L covers L m and that the only languages between L a and L are expansions of L a by scalar multiplications.

We note here, in answer to a question of Poizat, that the Morley and Lascar ranks need not coincide in differentially closed fields. We will approach this through the (perhaps) more fundamental issue of the variation of Morley rank in families. We will be interested here only in sets of finite Morley rank. Section 1 consists of some general lemmas relating the above issues. Section 2 points out a family of sets of finite Morley rank, whose Morley rank exhibits discontinuous upward jumps. To make the base of the family itself have finite Morley rank, we use a theorem of Buium.

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

The semantical account that Meyer and Lambert give in [7] of their quantificational calculus FQ can be considerably simplified, and—supposing as the authors do at the close of their paper that ‘ = ’ counts as a primitive sign—so can their axiom system for FQ.

(1) As the authors remark, axiom schema 102 can be simplified to read : A ⊃ (∀Χ)A, where Χ does not occur free in A. Following Tarski's [9], it can be further simplified: A ⊃ (∀Χ)A, where Χ does not occur in A.

Let be the class of atomic models of a countable first order theory. We prove that if is excellent and categorical in some uncountable cardinal, then each model is prime and minimal over the basis of a definable pregeometry given by a quasiminimal set. This implies that is categorical in all uncountable cardinals. We also introduce a U-rank to measure the complexity of complete types over models. We prove that the U-rank has the usual additivity properties, that quasiminimal types have U-rank 1, and that the U-rank of any type is finite in the uncountably categorical, excellent case. However, in contrast to the first order case, the supremum of the U-rank over all types may be ω (and is not achieved). We illustrate the theory with the example of free groups, and Zilber's pseudo analytic structures.

Answering a special case of a question of Chernikov and Simon, we show that any non-dividing formula over a model M in a distal NIP theory is a member of a consistent definable family, definable over M.

We study the measure independent character of Gödel speed-up theorems, in particular, we strengthen Arbib's necessary condition for the occurrence of a Gödel speed-up [2, p. 13] to an equivalence result and generalize Di Paola's speed-up theorem [4]. We also characterize undecidable theories as precisely those theories which possess consistent measure independent Gödel speed-ups and show that a theory τ2 is a measure independent Gödel speed-up of a theory τ1 if and only if the set of undecidable sentences of τ1 which are provable in τ2 is not recursively enumerable.

We consider a set generic over the arithmetic sets. A subset A of the natural numbers is called n-generic if it is Cohen-generic for n-quantifier arithmetic. This is equivalent to saying that for every -set of strings S, there is a string σ ⊂ A such that σ ∈ S or no extension of σ is in S. By degree we mean Turing degree (of unsolvability). We call a degree n-generic if it has an n-generic representative. For a degree a, let D(≤ a) denote the set of degrees which are recursive in a.

We say a is a strong minimal cover of g if every degree strictly below a is less than or equal to g. In this paper we show that there are a degree a and a 1-generic degree g < a such that a is a strong minimal cover of g. This easily implies that there is a 1-generic degree without the cupping property. Jockusch [7] showed that every 2-generic degree has the cupping property. Slaman and Steel [17] and independently Cooper [3] showed that there are recursively enumerable degrees a and b < a such that no degree c < a joins b above a. Take a 1-generic degree g below b. Then g does not have the cupping property.

We prove that a countable complete theory whose prime model has an infinite definable subset, all of whose elements are named, has at least four countable models up to isomorphism. The motivation for this is the conjecture that a countable theory with a minimal model has infinitely many countable models. In this connection we first prove that a minimal prime model A has an expansion by a finite number of constants A′ such that the set of algebraic elements of A′ contains an infinite definable subset.

We note that our main conjecture strengthens the Baldwin–Lachlan theorem. We also note that due to Vaught's result that a countable theory cannot have exactly two countable models, the weakest possible nontrivial result for a non-ℵ0-categorical theory is that it has at least four countable models.

§1. Notation and preliminaries. Our notation follows Chang and Keisler [1], except that we denote models by A, B, etc. We use the same symbol to refer to the universe of a model. Models we refer to are always in a countable language. For T a countable complete theory we let n(T) be the number of countable models of T up to isomorphism. ∃n means ‘there are exactly n’.

Assuming that every set is constructible, we find a ${\text{\Pi }}_1^1 $ maximal cofinitary group of permutations of $\mathbb{N}$ which is indestructible by Cohen forcing. Thus we show that the existence of such groups is consistent with arbitrarily large continuum. Our method also gives a new proof, inspired by the forcing method, of Kastermans’ result that there exists a ${\text{\Pi }}_1^1 $ maximal cofinitary group in L.

We extend Solovay’s theorem about definable subsets of the Baire space to the generalized Baire space λλ, where λ is an uncountable cardinal with λ<λ= λ. In the first main theorem, we show that the perfect set property for all subsets of λλ that are definable from elements of λOrd is consistent relative to the existence of an inaccessible cardinal above λ. In the second main theorem, we introduce a Banach–Mazur type game of length λ and show that the determinacy of this game, for all subsets of λλ that are definable from elements of λOrd as winning conditions, is consistent relative to the existence of an inaccessible cardinal above λ. We further obtain some related results about definable functions on λλ and consequences of resurrection axioms for definable subsets of λλ.

The category of enumerations over P1 is investigated. Objects are the enumerations of the set of partial recursive functions in one variable φ: N → P1 where φ is a total effective function from the natural numbers N onto P1.

To each a ∈ P1 we call φ−1(a) the set of all indices for a, the fibre over a.

Morphisms from one enumeration φ to another one ψ are (partial) recursive functions f, for which φ(n) = ψ(f(n)) holds for all n where f is denned, i.e. f is fibrepreserving. They are also called translators if f is total. The existence of a translator induces a partial ordering on the enumerations:

Let φ ≤ ψ, iff there exists a translator f with φ = ψ·f; φ ≡ ψ iff φ ≤ ψ and ψ ≤ φ. Two enumerations are called incomparable iff φ ≰,ψ and ψ ≰ φ.

Given a recursively enumerable family of enumerations {φi}i∈ω then their direct sum = π is defined by a bijective recursive pairing function g(i, n) (e.g. g(i, n) = (i + n)(i + n + 1)/2 + i) summing up the φi by φi(n) = = πg(i, n) into π. We also say π decomposes into .

Direct sums satisfy the universal property of sums in categories.

We want to operate decompositiontheory on special kinds of objects in our category, the Gödelnumberings and the Friedbergnumberings.

A Gödelnumbering φ is defined by (a) enumeration theorem (i.e. φ is object of our category) and (b) -theorem, which means that each m + n-place p.r. function can be effectively replaced by an enumeration of n-place p.r. functions given by means of the total -function (see Rogers [3]).

In § 1 of this paper, we characterize the isomorphism property of nonstandard universes in terms of the realization of some second-order types in model theory. In §2, several applications are given. One of the applications answers a question of D. Ross in [this Journal, vol. 55 (1990), pp. 1233–1242] about infinite Loeb measure spaces.

Let L be a finite relational language. The age of a structure over L is the set of isomorphism types of finite substructures of . We classify those ages for which there are less than 2ω countably infinite pairwise nonisomorphic L-structures of age .

The logical flow graphs of sequent calculus proofs might contain oriented cycles. For the predicate calculus the elimination of cycles might be non-elementary and this was shown in [Car96]. For the propositional calculus, we prove that if a proof of k lines contains n cycles then there exists an acyclic proof with (kn+1) lines. In particular, there is a polynomial time algorithm which eliminates cycles from a proof. These results are motivated by the search for general methods on proving lower bounds on proof size and by the design of more efficient heuristic algorithms for proof search.

We introduce the notion of finitary computable reducibility on equivalence relations on the domain ω. This is a weakening of the usual notion of computable reducibility, and we show it to be distinct in several ways. In particular, whereas no equivalence relation can be ${\rm{\Pi }}_{n + 2}^0$ -complete under computable reducibility, we show that, for every n, there does exist a natural equivalence relation which is ${\rm{\Pi }}_{n + 2}^0$ -complete under finitary reducibility. We also show that our hierarchy of finitary reducibilities does not collapse, and illustrate how it sharpens certain known results. Along the way, we present several new results which use computable reducibility to establish the complexity of various naturally defined equivalence relations in the arithmetical hierarchy.

We study relationships between certain algebraic properties of groups and rings definable in a first order structure or *-closed in a compact G-space. As a consequence, we obtain a few structural results about ω-categorical rings as well as about small, nm-stable compact G-rings, and we also obtain surprising relationships between some conjectures concerning small profinite groups.