It is shown, assuming the existence of a Woodin cardinal δ, that every tree ordering on some limit ordinal λ < δ with a cofinal branch is the tree ordering of some iteration tree on V.

At the source of what is now known as “geometric stability theory” was Zil'ber's intuition that the essential properties of an aleph-one-categorical theory were controlled by the geometries of its minimal types. (However, the situation is much more complex than was assumed in Zil'ber [1984], since the main conjecture of that paper has been disproved by Hrushovski.) This is not unnatural in this unidimensional case, where all these geometries have isomorphic contractions, but it was even realized later, in Cherlin, Harrington and Lachlan [1985] and Buechler [1986], that, for any superstable theory with finite ranks, a certain “local” property, i.e. a property satisfied by the geometry of each type of rank one (namely: to have a projective contraction), was equivalent to a “global” one (the theory is one-based, hence satisfies a coordinatization lemma). Then it was shown, in Pillay [1986], that this situation does not generalize to the infinite rank case, that, even for a theory of rank omega, the (local) assumption of projectivity for all the regular types of the theory does not have an exact global counterpart.

To clarify this kind of phenomena, I suggest here the elimination of their geometrical aspect, considering only the case where all of the geometries are degenerate. I will study various notions of triviality, which make sense in a stable context, and turn out to be equivalent in the finite rank case; some of them have a definite global flavour, others are of local character.

Let G be a stable abelian group with regular modular generic. We show that either

1. there is a definable nongeneric K ≤ G such that G/K has definable connected component and so strongly regular generics, or

2. distinct elements of the division ring yielding the dependence relation are represented by subgroups of G × G realizing distinct strong types (when regarded as elements of Geq).

In the latter case one can choose almost 0-definable subgroups representing the elements of the division ring. We find a bound ((G: G0)) for the size of the division ring in case G has no definable subgroup K so that G/K is infinite with definable connected component. We show in case (2) that the group G/H, where H consists of all nongeneric points of G, inherits a weakly minimal group structure from G naturally, and Th(G/H) is independent of the particular model G as long as G/H is infinite.

Cherlin introduced the concept of bad groups (of finite Morley rank) in [Ch1]. The existence of such groups is an open question. If they exist, they will contradict the Cherlin-Zil'ber conjecture that states that an infinite simple group of finite Morley rank is a Chevalley group over an algebraically closed field. In this paper, we prove that bad groups of finite Morley rank 3 act on a natural geometry Γ (namely on a special pseudoplane; see Corollary 20) sharply flag-transitively.We show that Γ is not very far from being a projective plane and when it is so rk(Γ) = 2 and Γ is not Desarguesian (Theorem 2). Baldwin [Ba] recently discovered non-Desarguesian projective planes of Morley rank 2. This discovery, together with this paper, makes the existence of bad groups (also of bad fields) more plausible. A bad field is a pair (K, A) of finite Morley rank, where K is an algebraically closed field, A <≠ K* and A is infinite. There existence is also unknown.

In this paper, we define the concept of a sharp-field as a pair (K, A), where K is a field, A < K*and

1. K = A − A,

2. If a + b − 1 ∈ A, a ∈ A, b ∈ A, then either a = 1 or b = 1.

If K is finite this is equivalent to 1 and

2.′ ∣K∣ = ∣A∣2 ∣A∣ + 1.

Finite sharp-fields are special cases of difference sets [De]

The paper continues [1]. Let S be a complete theory of ultraflat (e.g. planar) graphs as introduced in [4]. We show a strong form of NOTOP for S: The union of two models M1 and M2, independent over a common elementary submodel M0, is the primary model over M1 ∪ M2 of S. Then by results of [1] Mekler's construction [6] gives for such a theory S of nice ultraflat graphs a superstable 2-step-nilpotent group of exponent p (> 2) with NDOP and NOTOP.

Here we give short and direct proofs of the Feferman-Vaught theorem and other preservation theorems in products of structures. In 1952, Mostowski [5] first showed the preservation of ≡ωω by direct powers of structures. Subsequently, in 1959, Feferman and Vaught [2] proved the preservation of ≡ωω by arbitrary direct products and also by reduced products with respect to cofinite filters. In 1962, Frayne, Morel and Scott [3] noticed that the results extend to arbitrary reduced products. In 1970, Barwise and Eklof [1] showed the preservation of ≡∞λ by products and in 1971 Malitz [4] showed the preservation of ≡κλ with κ strongly inaccessible (or ∞) by products. Below, we give short proofs of the above results. The ideas used here have initiated, in [7], [8], [9], [10], [11], the introduction of several new methods in the theory of products, which on the one hand give new, direct proofs of the known results in the area, including generalizations or strengthenings of some of those, and, on the other hand, give several new results as well in the theory of products and related areas.

Below, L denotes a (first order) language, and by a structure we mean an L-structure. 0 and 1 denote the logically valid and false sentence, respectively. We may write ā ∈ A for ā ∈ An for some n. Also, the values 1 and 2 of a parameter l in the definitions below express a duality corresponding to disjunctive and conjunctive forms.

Sometimes it is said that mathematics talks only about truths that are invariant under isomorphisms. Thus, a syntactical characterization of sentences preserved under isomorphisms seems to be important to understand what mathematics is.

The importance of such sentences is underlined, for instance, by Bourbaki's requirement in [1, Chapter IV] that all axioms for mathematical structures satisfy the condition of being what they call transportable, that is, preserved under isomorphisms. In [2, §1], a formalization of Bourbaki's notion of mathematical structure and of the notion of transportable sentence was given and discussed. We adopt here, as in [2], Bourbaki's terminology, and call a sentence φ transportable if φ is true in a structure E if and only if φ is true in any structure F isomorphic to E.

An alternative formulation for Bourbaki's notion of structure is offered in [2, §3], which is also intended as a formalization of Suppes' notion of set-theoretical predicate, as formulated, for instance, in [3]. It is this alternative formulation that we adopt here.

In [2, p. 106], it was conjectured that a set-theoretical sentence is transportable if and only if it is equivalent to a sentence of type theory. One direction of the conjecture is obvious, namely, that any sentence of type theory is transportable. It is also clear that there are sentences of set theory which are not transportable. The main purpose of the present paper is to prove the rest of the conjecture. That is, we prove here that any transportable set-theoretical sentence is equivalent to a sentence of type theory.

Assuming AD + (V = L(R)), it is shown that for κ an admissible Suslin cardinal, o(κ) (= the order type of the stationary subsets of κ) is “essentially” regular and closed under ultrapowers in a manner to be made precise. In particular, o(κ) ≫ κ+, κ++, etc. It is conjectured that this characterizes admissibility for L(R).

We define a characteristic and definable subgroup F*(G) of any group G of finite Morley rank that behaves very much like the generalized Fitting subgroup of a finite group. We also prove that semisimple subnormal subgroups of G are all definable and that there are finitely many of them.

Let = {0,1, +,·,<} be the usual first-order language of arithmetic. We show that Peano arithmetic is the least first-order -theory containing IΔ0 + exp such that every complete extension T of it has a countable model K satisfying

(i) K has no proper elementary substructures, and

(ii) whenever L ≻ K is a countable elementary extension there is and such that .

Other model-theoretic conditions similar to (i) and (ii) are also discussed and shown to characterize Peano arithmetic.

We give a simple proof characterizing the complexity of Presburger arithmetic augmented with additional predicates. We show that Presburger arithmetic with additional predicates is complete. Adding one unary predicate is enough to get hardness, while adding more predicates (of any arity) does not make the complexity any worse.

Many-valued logics in general and 3-valued logic in particular is an old subject which had its beginning in the work of Łukasiewicz [Łuk]. Recently there is a revived interest in this topic, both for its own sake (see, for example, [Ho]), and also because of its potential applications in several areas of computer science, such as proving correctness of programs [Jo], knowledge bases [CP] and artificial intelligence [Tu]. There are, however, a huge number of 3-valued systems which logicians have studied throughout the years. The motivation behind them and their properties are not always clear, and their proof theory is frequently not well developed. This state of affairs makes both the use of 3-valued logics and doing fruitful research on them rather difficult.

Our first goal in this work is, accordingly, to identify and characterize a class of 3-valued logics which might be called natural. For this we use the general framework for characterizing and investigating logics which we have developed in [Av1]. Not many 3-valued logics appear as natural within this framework, but it turns out that those that do include some of the best known ones. These include the 3-valued logics of Łukasiewicz, Kleene and Sobociński, the logic LPF used in the VDM project, the logic RM3 from the relevance family and the paraconsistent 3-valued logic of [dCA]. Our presentation provides justifications for the introduction of certain connectives in these logics which are often regarded as ad hoc. It also shows that they are all closely related to each other. It is shown, for example, that Łukasiewicz 3-valued logic and RM3 (the strongest logic in the family of relevance logics) are in a strong sense dual to each other, and that both are derivable by the same general construction from, respectively, Kleene 3-valued logic and the 3-valued paraconsistent logic.

It is consistent that there exists a set mapping F: [ω2]2 → [ω2]<ω such that F(α,β) ⊆ α for α < β < ω2 and there is no infinite free subset for F. This solves a problem of A. Hajnal and A. Máté.

A basic goal in model-theoretic algebra is to obtain the classification of the complete extensions of a given (first-order) algebraic theory.

Results of this type, for the theory of totally ordered abelian groups, were obtained first by A. Robinson and E. Zakon [5] in 1960, later extended by Yu. Gurevich [4] in 1964, and further clarified by P. Schmitt in [6].

Within this circle of ideas, we give in this paper an axiomatization of the first-order theory of the class of all direct products of totally ordered abelian groups, construed as lattice-ordered groups (l-groups)—see the theorem below. We think of this result as constituing a first step—undoubtedly only a small one—towards the more general goal of classifying the first-order theory of abelian l-groups.

We write groups for abelian l-groups construed as structures in the language 〈 ∨, ∧, +, −, 0〉 (“−” is an unary operation). For unproved statements and unexplicated definitions, the reader is referred to [1].

F. Richman raised the question of whether the following principle of second order arithmetic is valid in intuitionistic higher order arithmetic HAH:

and if not, whether assuming Church's Thesis CT and Markov's Principle MP would help. Blass and Scedrov gave models of HAH in which this principle, which we call RP, is not valid, but their models do not satisfy either CT or MP.

In this paper a realizability topos Lif is constructed in which CT and MP hold, but RP is false. (It is shown, however, that RP is derivable in HAH + CT + MP + ECT0, so RP holds in the effective topos.) Lif is a generalization of a realizability notion invented by V. Lifschitz. Furthermore, Lif is a subtopos of the effective topos.

The dominical categories were introduced by Di Paola and Heller, as a first step toward a category-theoretic treatment of the generalized first Godel incompleteness theorem [1]. In his Ph.D. dissertation [7], Rosolini subsequently defined the closely related p-categories, which should prove pertinent to category-theoretic representations of incompleteness for intuitionistic systems. The precise relationship between these two concepts is as follows: every dominical category is a pointed p-category, but there are p-categories, indeed pointed p-isotypes (all pairs of objects being isomorphic) with a Turing morphism that are not dominical. The first of these assertions is an easy consequence of the fact that in a dominical category C by definition the near product functor when restricted to the subcategory Ct, of total morphisms of C (as “total” is defined in [1]) constitutes a bona fide product such that the derived associativity and commutativity isomorphisms are natural on C × C × C and C × C, respectively, as noted in [7]. As to the second, p-recursion categories (that is, pointed p-isotypes having a Turing morphism) that are not dominical were defined and studied by Montagna in [6], the syntactic p-categories ST and S′T associated with consistent, recursively enumerable extensions of Peano arithmetic, PA. These merit detailed investigation on several counts.

A well-known question of Feferman asks whether there is a logic which extends the logic , is ℵ0-compact and satisfies the interpolation theorem. (Cf. Makowsky [M] for background and terminology.)

The same question was open when ℵ1 in is replaced by any other uncountable cardinal κ. We shall show that when κ is an uncountable strongly compact cardinal and there is a strongly compact cardinal > κ, then there is such a logic. It is impossible to prove the existence of uncountable strongly compact cardinals in ZFC. However, the logic that we describe has a simple and natural definition, together with several other pleasant properties. For example it satisfies Robinson's lemma, PPP (pair preservation property, viz. the theory of the sum of two models is the sum of their theories), versions of the elementary chain lemma for chains of length < λ, and isomorphism of (suitable) ultralimits.

This logic is described in §2 below; we call it 1. It is not a new logic—it was introduced in [Sh, Part II, §3] as an example of a logic which has the amalgamation and joint embedding properties. See the transparent presentation in [M]. But we shall repeat all the definitions. In [HS] we presented a logic with some of the same properties as 1, also based on a strongly compact cardinal λ; but unlike 1, it was not a sublogic of λ,λ.

A paradigm of scientific discovery is defined within a first-order logical framework. It is shown that within this paradigm there exists a formal scientist that is Turing computable and universal in the sense that it solves every problem that any scientist can solve. It is also shown that universal scientists exist for no regular logics that extend first-order logic and satisfy the Löwenheim-Skolem condition.

The linear logic introduced in [3] by J.-Y. Girard keeps one of the so-called structural rules of the sequent calculus: the exchange rule. In a one-sided sequent calculus this rule can be formulated as

The exchange rule allows one to disregard the order of the assumptions and the order of the conclusions of a proof, and this means, when the proof corresponds to a logically correct program, to disregard the order in which the inputs and the outputs occur in a program.

In the linear logic introduced in [3], the exchange rule allows one to prove the commutativity of the multiplicative connectives, conjunction (⊗) and disjunction (⅋). Due to the presence of the exchange rule in linear logic, in the phase semantics for linear logic one starts with a commutative monoid. So, the usual linear logic may be called commutative linear logic.

The aim of the investigations underlying this paper was to see, first, what happens when we remove the exchange rule from the sequent calculus for the linear propositional logic at all, and then, how to recover the strength of the exchange rule by means of exponential connectives (in the same way as by means of the exponential connectives ! and ? we recover the strength of the weakening and contraction rules).

We study the structures (K ⊂ K r), where K is an ordered field and K r its real closure, in the language of ordered fields with an additional unary predicate for the subfield K. Two such structures (K ⊂ K r) and (L ⊂ L r) are not necessarily elementary equivalent when K and L are. But with some saturation assumption on K and L, then the two structures become equivalent, and we give a description of the complete theory.