Introduction. In [Sh, Chapter IX], Shelah constructs a model of set theory in which Suslin's hypothesis is true, yet there is an Aronszajn tree which is not special. In his model, we have . He asks whether the same result could be obtained consistently with CH. In this paper, we answer his question in the affirmative.

Let us say that a tree T is S-st-special iff there is a function ƒ with dom(f) = {t ∈ T: rank(t) ∈ S} and for every t1 < t2 both in dom(t) we have f(t2) ≠ f(t1) < rank(t1). In Shelah's model, every tree is S-st-special for some fixed stationary costationary set S. Also, there is some tree T such that T is not S′-st-special whenever S′ – S is stationary. These properties, which are sufficient to ensure that Suslin's hypothesis holds and that T is not special, also hold in the model constructed in this paper. These properties also ensure that every Aronszajn tree has a stationary antichain (i.e., an antichain A such that {rank(t): t ∈ A} is stationary). Hence, it is natural to ask whether there is a model of Suslin's hypothesis in which some Aronszajn tree has no stationary antichain. We answer in the affirmative in [S].

The construction we use owes much to Shelah's approach to the theorem, due to Jensen (see [DJ]), that CH is consistent with Suslin's hypothesis. This is given in [Sh, Chapter V].

In this paper, we consider certain cardinals in ZF (set theory without AC, the axiom of choice). In ZFC (set theory with AC), given any cardinals and , either ≤ or ≤ . However, in ZF this is no longer so. For a given infinite set A consider seq1-1(A), the set of all sequences of A without repetition. We compare |seq1-1(A)|, the cardinality of this set, to ||, the cardinality of the power set of A. What is provable about these two cardinals in ZF? The main result of this paper is that ZF ⊢ ∀A(| seq1-1(A)| ≠ ||), and we show that this is the best possible result. Furthermore, it is provable in ZF that if B is an infinite set, then | fin(B)| < | (B*)| even though the existence for some infinite set B* of a function ƒ from fin(B*) onto (B*) is consistent with ZF.

Let T be an uncountable, superstable theory. In this paper we prove

Theorem A. If T has finite rank, then I(|T|, T) ≥ ℵ0.

Theorem B. If T is trivial, then I(|T|, T) ≥ ℵ0.

In analogy to the definition of the halting problem K, an r.e. set A is called a diagonal iff there is a computable numbering ψ of the class of all partial recursive functions such that A = {i ∈ ω: ψi(i)↓} (in that case we say that A is the diagonal of ψ). This notion has been introduced in [10]. It captures all r.e. sets that can be constructed by diagonalization.

It was shown that any nonrecursive r.e. T-degree contains a diagonal, that for any diagonal A there is an r.e. nonrecursive nondiagonal B ≤TA, and that there are r.e. degrees a such that any r.e. set from a is a diagonal.

In §2 of the present paper we show that the property “A is a diagonal” is elementary lattice theoretic (e.l.t.). This result complements and generalizes previous results of Harrington and Lachlan, respectively. Harrington (see [16, XV. 1]) proved that the property of being the diagonal of some Gödelnumbering (i.e., of being creative) is e.l.t., and Lachlan [12] proved that the property of being a simple diagonal (i.e., of being simple and not hh-simple [10]) is e.l.t.

In §§3 and 4 we study the position of diagonals and nondiagonals inside the lattice of r.e. sets. We concentrate on an important class of nondiagonals, generalizing the maximal and hemimaximal sets: the -maximal sets. Using the results from [6] we are able to classify the -maximal sets that can be obtained as halfs of splittings of hh-simple sets.

LK is a natural modification of Gentzen sequent calculus for propositional logic with connectives ¬ and ∧,∨ (both of bounded arity). Then for every d ≥ 0 and n ≥ 2, there is a set of depth d sequents of total size O(n3+d) which are refutable in LK by depth d + 1 proof of size exp(O(log2n)) but such that every depth d refutation must have the size at least exp(nΩ(1)). The sets express a weaker form of the pigeonhole principle.

Nous dirons qu'un corps (commutatif) K est un corps de courbe réelle sur le corps k si et seulement si c'est une extension de k, ordonnable, finiment engendrée et de degré de transcendance 1 sur k, telle que k soit relativement algébriquement clos dans K. Un tel corps est le corps d'une courbe (plane) définie sur k. De plus si k est réel-clos, toute courbe définie sur k dont K est le corps, a un point régulier rationnel sur k; en effet soit I ⊂ k[X0,…, Xn] l'idéal d'une telle courbe Γ; on a donc: K = k[x0,…, xn] où x0,…, xn sont les classes d'équivalence de X0,…, Xn; (x0,…, xn) est un point régulier de Γ dans la clôture réelle de K, et par modèle-complétude, Γ a un point régulier rationnel sur k.

Notre but est d'étendre les résultats de Raphael Robinson [6] sur l'indécidabilité des corps de fractions rationnelles sur un corps ordonnable (dans le langage des corps). Comme lui, nous donnerons une méthode qui ne s'applique que lorsque le corps de base k est réel-clos, et une seconde méthode générate.

We reduce to a standard circuit-size complexity problem a relativisation of the P=NP question that we believe to be connected with the same question in the model for computation over the reals defined by L. Blum. M. Shub, and S. Smale. On this occasion, we set the foundations of a general theory for computation over an arbitrary structure, extending what these three authors did in the case of rings.

In what follows, L is a recursive language. The structures to be considered are L-structures with universe named by constants from ω. A structure is recursive A if the open diagram D() is recursive. Lerman and Schmerl [L-S] proved the following result.

Let T be an ℵ0-categorical elementary first-order theory. Suppose that for all n, , and T is arithmetical. Then T has a recursive model.

The aim of this paper is to extend Theorem 0.1. Stating the extension requires some terminology. Consider finitary formulas with symbols from L and sometimes extra constants from ω. For each n ∈ ω, the Σn and Πn formulas are as usual. Then Bnformulas are Boolean combinations of Σn formulas. For an L-structure , Dn() denotes the set of Bn sentences in the complete diagram Dc(). A complete Σn theory is a maximal consistent set of ΣnL-sentences. We may write φ(x), or Γ(x), to indicate that the free variables of the formula φ, or the set Γ, are among those in x. A complete Bn type for x is a maximal consistent set Γ(x) of Bn formulas with just the free variables x.

If T is ℵ0-categorical, then for each x only finitely many complete types Γ(x) are consistent with T. While Lerman and Schmerl stated their result just for ℵ0-categorical theories, essentially the same proof yields the following.

Theorem 0.2. Let T be a consistent, complete theory such that for all n andx, only finitely many complete Bn types Γ(x) are consistent with T.

Let CKDT be the assertion that for every countably infinite bipartite graph G, there exist a vertex covering C of G and a matching M in G such that C consists of exactly one vertex from each edge in M. (This is a theorem of Podewski and Stefifens [12].) Let ATR0 be the subsystem of second-order arithmetic with arithmetical transfinite recursion and restricted induction. Let RCA0 be the subsystem of second-order arithmetic with recursive comprehension and restricted induction. We show that CKDT is provable in ATR0. Combining this with a result of Aharoni, Magidor, and Shore [2], we see that CKDT is logically equivalent to the axioms of ATR0, the equivalence being provable in RCA0.

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.

In [14] J. Hirschfeld established the close connection of models of the true AE sentences of Peano Arithmetic and homomorphic images of the semiring of recursive functions. This fragment of Arithmetic includes most of the familiar results of classical number theory. There are two nice ways that such models appear in the isols. One way was introduced by A. Nerode in [20] and is referred to in the literature as Nerode Semirings. The other way is called a tame model. It is very similar to a Nerode Semiring and was introduced in [6]. The model theoretic properties of Nerode Semirings and tame models have been widely studied by T. G. McLaughlin ([16], [17], and [18]).

In this paper we introduce a new variety of tame model called a torre model. It has as a generator an infinite regressive isol with a nice structural property relative to recursively enumerable sets and their extensions to the isols. What is then obtained is a nonstandard model in the isols of the fragment of Peano Arithmetic with the following property: Let T be a torre model. Let f be any recursive function, and let fΛ be its extension to the isols. If there is an isol A with fΛ(A) ϵ T, then there is also an isol B ϵ T with fΛ(B) = fΛ(A).

In this paper we study nonmultidimensional superstable theories T, possibly in an uncountable language, and develop some techniques permitting the generalisation of certain results from the finite rank (and/or countable language) context to the general case.

We prove, among other things, the following: there is a set A0 of parameters, which has cardinality at most ∣T∣, and in the finite-dimensional case is finite, such that over any B ⊇ A0 there is a locally atomic model. One of the consequences of this is that if C is the monster model of T, φ(x) is a formula over A0, φC ⊇ X and (X, φC) satisfies the Tarski-Vaught condition after adding names for A0, then there is an elementary substructure M of C containing A0 such that φM = X. Applications to the spectrum problem will appear in [Ch-P].

In fact, all the components of the machinery we develop are already present in the general theory. One such component involves a stratification of the regular types of T using a generalized notion of weakly minimal formula. This appears in [Sh, Chapter V and the proof of IX.2.4] and also in [P2]. A second component involves definable groups which arise as ‘binding” groups. The existence of such groups, under certain hypotheses on the behavior of nonorthogonality, is due to Hrushovski [Hr1], and our use of them to help obtain “j-constructible” models is similar to their use in [Bu-Sh].

In this paper we define and study conditional problems and their degrees. The main result is that the class of conditional degrees is a lattice extending the ordinary Turing degrees and it is dense. These properties are not shared by ordinary Turing degrees. We show that the class of conditional many-one degrees is a distributive lattice. We also consider properties of semidecidable problems and their degrees, which are analogous to r.e. sets and degrees.

In this paper we show that if there is a weakly normal ideal on κ then for each fails. This greatly improves a theorem of C. A. Johnson.

Let L be a first order language. If M is an L-structure, let LM be the expansion of L obtained by adding constants for the elements of M.

Definition. A type is definable if and only if for any L-formula , there is an LM-formula so that for all iff M ⊨ dθ(¯). The formula dθ is called the definition of θ.

Definable types play a central role in stability theory and have also proven useful in the study of models of arithmetic. We also remark that it is well known and easy to see that for M ≺ N, the property that every M-type realized in N is definable is equivalent to N being a conservative extension of M, where

Definition. If M ≺ N, we say that N is a conservative extension of M if for any n and any LN -definable S ⊂ Nn, S ∩ Mn is LM-definable in M.

Van den Dries [Dl] studied definable types over real closed fields and proved the following result.

0.1 (van den Dries), (i) Every type over (R, +, -,0,1) is definable.

(ii) Let F and K be real closed fields and F ⊂ K. Then, the following are equivalent:

(a) Every element of K that is bounded in absolute value by an element of F is infinitely close (in the sense of F) to an element of F.

(b) K is a conservative extension of F.

We obtain a p-adic semilinear cell decomposition theorem using methods developed by Denef in [Journal für die Reine und Angewandte Mathematik, vol. 369 (1986), pp. 154–166]. We also prove that any set definable with quantifiers in (0,1, +, —, λq, Pn){n∈ℕ,q∈ℚp} may be defined without quantifiers, where λq is scalar multiplication by q and Pn is a unary predicate which denotes the nonzero nth powers in the p-adic field ℚp. Such a set is called a p-adic semilinear set in this paper. Some further considerations are discussed in the last section.

We do a quantitative analysis of modal logic. For example, for each Kripke structure M, we study the least ordinal μ such that for each state of M, the beliefs up to level μ characterize the agents' beliefs (that is, there is only one way to extend these beliefs to higher levels). As another example, we show the equivalence of three conditions, that on the face of it look quite different, for what it means to say that the agents' beliefs have a countable description, or putting it another way, have a “countable amount of information”. The first condition says that the beliefs of the agents are those at a state of a countable Kripke structure. The second condition says that the beliefs of the agents can be described in an infinitary language, where conjunctions of arbitrary countable sets of formulas are allowed. The third condition says that countably many levels of belief are sufficient to capture all of the uncertainty of the agents (along with a technical condition). The fact that all of these conditions are equivalent shows the robustness of the concept of the agents' beliefs having a “countable description”.

The modal predicate logic of provability identifies the “□” of modal logic with the “Bew” of proof theory, so that, where “Bew” is a formula representing, in the usual way, provability in a consistent, recursively axiomatized theory Γ extending Peano arithmetic (PA), an interpretation of a language for the modal predicate calculus is a map * which associates with each modal formula an arithmetical formula with the same free variables which commutes with the Boolean connectives and the quantifiers and which sets (□ϕ)* equal to Bew(⌈ϕ*⌉). Where Δ is an extension of PA (all the theories we discuss will be extensions of PA), MPL(Δ) will be the set of modal formulas ϕ such that, for every interpretation *, ϕ* is a theorem of Δ. Most of what is currently known about the modal predicate logic of provability consists in demonstrations that MPL(Δ) must be computationally highly complex. Thus Vardanyan [11] shows that, provided that Δ is 1-consistent and recursively axiomatizable, MPL(Δ) will be complete , and Boolos and McGee [5] show that MPL({true arithmetical sentences}) is complete in {true arithmetical sentences}. All of these results take as their starting point Artemov's demonstration in [1] that {true arithmetical sentences} is 1-reducible to MPL({true arithmetical sentences}).

The aim here is to consolidate these results by providing a general theorem which yields all the other results as special cases. These results provide a striking contrast with the situation in modal sentential logic (MSL); according to fundamental results of Solovay [8], provided Γ does not entail any falsehoods, MSL({true arithmetical sentences}) and MSL(PA) (which is the same as MSL(Γ)) are both decidable.

Laver [L] and others [G-S] have shown how to make the supercompactness or strongness of κ indestructible by a wide class of forcing notions. We show, alternatively, how to make these properties fragile. Specifically, we prove that it is relatively consistent that any forcing which preserves κ<κ and κ+, but not P(κ), destroys the measurability of κ, even if κ is initially supercompact, strong, or if I1(κ) holds. Obtained as an application of some general lifting theorems, this result is an “inner model” type of theorem proved instead by forcing.

One of the purposes of this paper is to prove a partial Schur-Zassenhaus Theorem for groups of finite Morley rank.

Theorem 2. Let G be a solvable group of finite Morley rank. Let π be a set of primes, and let H ⊲ G a normal π-Hall subgroup. Then H has a complement in G.

This result has been proved in [1] with the additional assumption that G is connected, and thought to be generalized in [2] by the authors of the present article. Unfortunately in the last section of the latter paper there is an irrepairable mistake. Here we give a new proof of the Schur-Zassenhaus Theorem using the results of [2] up to the last section and a new result that we are going to state below.

The second author has shown in [11] that a nilpotent ω-stable group is the central product of a divisible subgroup and a subgroup of bounded exponent, generalizing a well-known result of Angus Macintyre about abelian groups [8]. One could ask a similar question for solvable groups: are they a product of two subgroups, one divisible, one of bounded exponent? One is allowed to be hopeful because of the well-known decomposition of the connected solvable algebraic groups over algebraically closed fields as the product of the unipotent radical and a torus.