Given a finite relational language L is there an algorithm that, given two finite sets and of structures in the language, determines how many homogeneous L structures there are omitting every structure in and embedding every structure in ?

For directed graphs this question reduces to: Is there an algorithm that, given a finite set of tournaments Γ, determines whether Γ, the class of finite tournaments omitting every tournament in Γ. is well-quasi-order?

First, we give a nonconstructive proof of the existence of an algorithm for the case in which Γ consists of one tournament. Then we determine explicitly the set of tournaments each of which does not have an antichain omitting it. Two antichains are exhibited and a summary is given of two structure theorems which allow the application of Kruskal's Tree Theorem. Detailed proofs of these structure theorems will be given elsewhere.

The case in which Γ consists of two tournaments is also discussed.

We prove that no computable tree of infinite height is computably categorical, and indeed that all such trees have computable dimension ω. Moreover, this dimension is effectively ω, in the sense that given any effective listing of computable presentations of the same tree, we can effectively find another computable presentation of it which is not computably isomorphic to any of the presentations on the list.

Let L[E] be an iterable tame extender model. We analyze to which extent L[E] knows fragments of its own iteration strategy. Specifically, we prove that inside L[E], for every cardinal κ which is not a limit of Woodin cardinals there is some cutpoint t < κ such that Jκ[E] is iterable above t with respect to iteration trees of length less than κ.

As an application we show L[E] to be a model of the following two cardinals versions of the diamond principle. If λ > κ > ω1 are cardinals, then holds true, and if in addition λ is regular, then holds true.

In this paper a class of simple theories, called the low theories is developed, and the following is proved.

Theorem. Let T be a low theory, A a set and a, b elements realizing the same strong type over A. Then, a and b realize the same Lasear strong type over A.

This note is concerned with the logical formalism with types recently introduced by Church [1] (and called (C) in this note) It was shewn in his paper (Theorem 26α) that if Yα stands for

(a form of the “axiom of infinity” for the type α), Yα can be proved formally, from Yι and the axioms 1 to 7, for all types α of the forms ι′, ι″, …. For other types the question was left open, but for the purposes of an intrinsic characterisation of the Church type-stratification given by one of us, it is desirable to have the remaining cases cleared up. A formal proof of Yα is now given for all types α containing ι, but the proof uses, in addition to Axioms 1 to 7 and Yι, also Axiom 9 (in connection with Def. 4), and Axiom 10 (in Theorem 9).

An impressive theory has been developed, largely by Shelah, around the notion of a stable theory. This includes detailed structure theorems for the models of such theories as well as a generalized notion of independence. The various stability properties can be defined in terms of the numbers of types over sets, or in terms of the complexity of definable sets. In the concrete examples of stable theories, however, one finds an important distinction between “positive” and “negative” information, such a distinction not being an a priori consequence of the general definitions. In the naive examples this may take the form of distinguishing between say a class of a definable equivalence relation and the complement of a class. In the more algebraic examples, this distinction may have a “topological” significance, for example with the Zariski topology on (the set of n-tuples of) an algebraically closed field, the “closed” sets being those given by sets of polynomial equalities. Note that in the latter case, every definable set is a Boolean combination of such closed sets (the definable sets are precisely the constructible sets). Similarly, stability conditions in practice reduce to chain conditions on certain “special” definable sets (e.g. in modules, stable groups). The aim here is to develop and present such notions in the general (model-theoretic) context. The basic notion is that of an “equation”. Given a complete theory T in a language L, an L-formula φ(x̄, ȳ) is said to be an equation (in x̄) if any collection Φ of instances of φ(i.e. of formulae φ(x̄, ā)) is equivalent to a finite subset Φ′ ⊂ Φ.

The Dedekind cuts in an ordered set form a set in the sense of constructive Zermelo–Fraenkel set theory. We deduce this statement from the principle of refinement, which we distill before from the axiom of fullness. Together with exponentiation, refinement is equivalent to fullness. None of the defining properties of an ordering is needed, and only refinement for two–element coverings is used.

In particular, the Dedekind reals form a set: whence we have also refined an earlier result by Aczel and Rathjen, who invoked the full form of fullness. To further generalise this, we look at Richman's method to complete an arbitrary metric space without sequences, which he designed to avoid countable choice. The completion of a separable metric space turns out to be a set even if the original space is a proper class: in particular, every complete separable metric space automatically is a set.

Let N be a transitive model of ZFC such that “N ⊂ N and P(ℝ) ⊂ N. Assume that both V and N satisfy “the core model K exists.” Then KN is an iterate of K, i.e., there exists an iteration tree F on K such that F has successor length and . Moreover, if there exists an elementary embedding π: V → N then the iteration map associated to the main branch of F equals π յ K. (This answers a question of W. H. Woodin, M. Gitik, and others.) The hypothesis that P(ℝ) ⊂ N is not needed if there does not exist a transitive model of ZFC with infinitely many Woodin cardinals.

Comparability of classes. Till now we tried to get along without the axioms Vc and Vd. We found that this is possible in number theory and analysis as well as in general set theory, even keeping in the main to the usual way of procedure.

For the considerations of the present section application of the axioms Vc, Vd is essential. Our axiomatic basis here consists of the axioms I—III, V*, Vc, and Vd. From V*, as we know, Va and Vb are derivable. We here take axiom V* in order to separate the arguments requiring the axiom of choice from the others. Instead of the two axioms V* and Vc, as was observed in Part II, V** may be taken as well.

We characterize, in terms of determinacy, the existence of 0## as well as the existence of each of the following: 0###, 0####, 0#####,…. For κ Є ω, we define two classes of sets, and , which lie strictly between and . We also define 01# as# and in general, 0(k+1)# as (0k#)#. We then show that the existence of 0(k + 1)# is equivalent to the determinacy of as well as the determinacy of .

The main purpose of this paper is to present a formal system P in which we enjoy a smooth-running technique and which countenances a universe of classes which is symmetrical as between large and small. More exactly, P is a system which differs from the inconsistent system of [1] only in the introduction of a rather natural new restrictive condition on the defining formulas of the elements (sets, membership-eligible classes). It will be proved that if the weaker system of [2] is consistent, then P is also consistent.

After the discovery of paradoxes, it may be recalled, Russell and Zermelo in the same year proposed two different ways of safeguarding logic against contradictions (see [3], [4]). Since then various simplifications and refinements of these systems have been made. However, in the resulting systems of Zermelo set theory, generation of classes still tends to be laborious and uncertain; and in the systems of Russell's theory of types, complications in the matter of reduplication of classes and meaningfulness of formulas remain. In [2], Quine introduced a system which seems to be free from all these complications. But later it was found out that in it there appears to be an unavoidable difficulty connected with mathematical induction. Indeed, we encounter the curious situation that although we can prove in it the existence of a class V of all classes, and we can also prove particular existence theorems for each of infinitely many classes, nobody has so far contrived to prove in it that V is an infinite class or that there exists an infinite class at all.

A set X is prime bounding if for every complete atomic decidable (CAD) theory T there is a prime model of T decidable in X. It is easy to see that X = 0′ is prime bounding. Denisov claimed that every X <T 0′ is not prime bounding, but we discovered this to be incorrect. Here we give the correct characterization that the prime bounding sets X ≤τ 0′ are exactly the sets which are not low2. Recall that X is low2 if X″ ≤τ 0″. To prove that a low2 set X is not prime bounding we use a 0′ -computable listing of the array of sets {Y : Y ≤τX } to build a CAD theory T which diagonalizes against all potential X-decidable prime models of T, To prove that any non-low2X is indeed prime bounding. we fix a function f ≤TX that is not dominated by a certain 0′-computable function that picks out generators of principal types. Given a CAD theory T. we use f to eventually find, for every formula φ(x̄) con sistent with T. a principal type which contains it. and hence to build an X-decidable prime model of T. We prove the prime bounding property equivalent to several other combinatorial properties, including some related to the limitwise monotonic functions which have been introduced elsewhere in computable model theory.

This note deals with a proof-theoretic characterisation of certain complexity classes of functions in fragments of intuitionistic bounded arithmetic. In this Introduction we survey the background and state our main result.

We follow Buss [B1] and consider a language for arithmetic whose nonlogical symbols are 0, S (the successor operation Sx = x + 1), +, ·, ∣ ∣ (∣x∣ being the number of digits in the binary notation for x), rounded down to the nearest integer), # (x#y = 2∣x∣∣y∣) and ≤. We define 1 = S0, 2 = S1, s0x = 2x and s1x = 2x + 1. In Buss's approach the functions s0 and s1 play a special role. Notice that six is the number obtained from x by suffixing the digit i to its binary representation, and thus the natural numbers are generated from 0 by repeated applications of the operations s0 and s1. This means that they satisfy the induction scheme

Using the fact that is x with its last binary digit deleted, this can be stated more compactly in the following form, called by Buss the polynomial induction or PIND schema:

Buss defined a theory S2 consisting of a finite set BASIC of open axioms and the PIND-schema restricted to bounded formulas ϕ. The topic of bounded arithmetic is concerned with S2 and its fragments.

Strengthening a theorem of D. W. Kueker, this paper completely charaterizes which countable structures do not admit uncountable Lω1ω-elementarily equivalent models. In particular, it is shown that if the automorphism group of a countable structure M is abelian, or even just solvable, then there is no uncountable model of the Scott sentence of M. These results arise as part of a study of Polish groups with compatible left-invariant complete metrics.

In this paper we show that there are “E0 many” orbit inequivalent free actions of the free groups , 2 ≤ n ≤ ∞ by measure preserving transformations on a standard Borel probability space. In particular, there are uncountably many such actions.

The present article is an attempt to bridge the gap between the researchers that work in the areas adjacent to Hilbert's Tenth Problem (for short, HTP), mainly, number theory and mathematical logic. It presents the main results that have been obtained and asks some of the open questions in the area, leading to the main unanswered question (at least in the opinion of the author)—the analogue of HTP for the rational numbers. In this respect, the article is a successor of [Da] where the reader can find more information on the solution of the initial problem. Most of the results that are presented are not new, but some of the proofs are. As the purpose of a survey article is the “unification” of the methods involved, we present a proof of the analogue of HTP in the case of polynomial rings which is more geometric in nature than the initial proof of Denef (although it uses essentially the same tools). This allows, in our opinion, an easy introduction to the utilisation of the concepts used in the more recent approaches, like that of elliptic curves. We must say that the approach to the subject that we suggest through the questions we ask (mostly consisting of generalisations of HTP to various algebraic and analytic domains) is not the only one.

Die vorliegenden Untersuchungen haben sich aus solchen entwickelt, die ich an andrer Stelle früher veröffentlichte. Die Kenntnis dieser früheren Arbeit wird in keiner Weise hier vorausgesetzt und ist für das folgende unwesentlich. Es sei mir jedoch gestattet, für den Kenner der früheren Arbeit einige Bemerkungen voraufzuschicken. In der genannten Arbeit hatte ich, angeregt ursprünglich durch Gedankengänge von Herrn Behmann, ein typenfreies System der Logik aufgebaut, das allein auf dem Gedanken fußte, daß der Definitionsbereich der Prädikate im allgemeinen beschränkt ist, sodaß nur bestimmte Zusammenstellungen von Prädikaten und Dingen sinnvolle, d.h. wahre oder falsche Aussagen ergeben, und das diesen Gesichtspunkt meiner Meinung nach konsequent durchführte. Eine anschließende Arbeit sollte dann die Widerspruchsfreiheit des Systems untersuchen. Diese Untersuchung ist inzwischen geschehen. Es zeigte sich, daß sich die Widerspruchsfreiheit des Systems nur dann beweisen ließ, falls die in ihm enthaltene Vollständigkeit von → die sich durch das Bestehen eines Deduktionstheorems zeigte, fallen gelassen wurde. Die Grundformeln (13) und (14) mußten wegbleiben. Die Widerspruchsfreiheit des restlichen Systems ließ sich dann durch eine dem System eigentümliche Methode der Beweistransformation zeigen.

Diese anschließienden Untersuchungen, die ihrer Zeit nicht mehr veröffentlicht werden konnten, sind inzwischen durch die vorliegenden überholt. Es war das Unbefriedigende bei dem genannten Aufbau, daß hinterher doch wieder eine Einschränkung gemacht werden mußte, die sich nicht aus den zugrunde gelegten Prinzipien ergab, sondern von ihnen aus unvorhergesehen war. Diese Einschränkung bewirkte übrigens, daß keine volle Zahlentheorie in dem System zu gewinnen war.

Let D be a strongly minimal set in the language L, and D′ ⊃ D an elementary extension with infinite dimension over D. Add to L a unary predicate symbol D and let T′ be the theory of the structure (D′, D), where D interprets the predicate D. It is known that T′ is ω-stable. We prove

Theorem A. If D is not locally modular, then T′ has Morley rank ω.

We say that a strongly minimal set D is pseudoprojective if it is nontrivial and there is a k < ω such that, for all a, b ∈ D and closed X ⊂ D, a ∈ cl(Xb) ⇒ there is a Y ⊂ X with a ∈ cl(Yb) and ∣Y∣ ≤ k. Using Theorem A, we prove

Theorem B. If a strongly minimal set D is pseudoprojective, then D is locally projective.

The following result of Hrushovski's (proved in §4) plays a part in the proof of Theorem B.

Theorem C. Suppose that D is strongly minimal, and there is some proper elementary extension D1 of D such that the theory of the pair (D1, D) is ω1-categorical. Then D is locally modular.

We consider the question of when an expansion of a first-order topological structure has the property that every open set definable in the expansion is definable in the original structure. This question has been investigated by Dolich, Miller and Steinhorn in the setting of ordered structures as part of their work on the property of having o-minimal open core. We answer the question in a fairly general setting and provide conditions which in practice are often easy to check. We give a further characterisation in the special case of an expansion by a generic predicate.

The classification of algebraic structures which can be embedded into ℛ, the uppersemilattice of recursively enumerable degrees, is the key to answering certain questions about Th(ℛ), the elementary theory of ℛ. In particular, these classification problems are important for answering decidability questions about fragments of Th(ℛ). Thus the solutions of Fried berg [F] and Mučnik [M] to Post's problem were easily extended to show that all finite partially ordered sets are embeddable into ℛ, and hence that ∃1 ∩ Th(ℛ), the existential theory of ℛ, is decidable. (The language used is ℒ′, the pure predicate calculus together with a binary relation symbol ≤ to be interpreted as the ordering of ℛ) The problem of determining which finite lattices are embeddable into ℛ has been a long-standing open problem, and is one of the major obstacles to determining whether ∀2 ∩ Th(ℛ), the universal-existential theory of ℛ, is decidable. Shore has obtained some nice partial results in this direction. Embeddings also played a central role in showing that Th(ℛ) is not ℵ0-categorical (Lerman, Shore and Soare [LeShSo]), thus resolving a problem posed by Jockusch. Harrington and Shelah [HS] embedded all 0′-presentable partially ordered sets into ℛ in such a way that the partially ordered sets can be uniformly recovered from four parameters. They used these embeddings to show that Th(ℛ) is undecidable.

The first nontrivial extension of the embeddings of Friedberg and Mučnik to lattice embeddings was obtained independently by Lachlan [La1] and Yates [Y] who showed that the four-element Boolean algebra can be embedded into ℛ. Thomason [T] and Lerman independently extended this result to include all finite distributive lattices. The nondistributive case, however, was much more difficult. Lachlan [La2] embedded the two five-element nondistributive lattices M 5 and N 5 (see Figures 1 and 2) into ℛ, and his proof could easily have been extended to include a larger class of lattices.