We study local strengthenings of the simplicity condition. In particular, we define and study a local Lascar rank, as well as short, low. supershort and superlow theories. An example of a low non supershort theory is given.

This paper is motivated by the question whether there exists a logic capturing polynomial time computation over unordered structures. We consider several algorithmic problems near the border of the known, logically defined complexity classes contained in polynomial time. We show that fixpoint logic plus counting is stronger than might be expected, in that it can express the existence of a complete matching in a bipartite graph. We revisit the known examples that separate polynomial time from fixpoint plus counting. We show that the examples in a paper of Cai, Fürer, and Immerman, when suitably padded, are in choiceless polynomial time yet not in fixpoint plus counting. Without padding, they remain in polynomial time but appear not to be in choiceless polynomial time plus counting. Similar results hold for the multipede examples of Gurevich and Shelah, except that their final version of multipedes is, in a sense, already suitably padded. Finally, we describe another possible candidate, involving determinants, for the task of separating polynomial time from choiceless polynomial time plus counting.

We give a model-theoretic proof of the fact that for all infinite Abelian groups P ≠ NP in the sense of binary nondeterminism. This result has been announced 1994 by Christine Gaßner.

Fibring is recognized as one of the main mechanisms in combining logics, with great significance in the theory and applications of mathematical logic. However, an open challenge to fibring is posed by the collapsing problem: even when no symbols are shared, certain combinations of logics simply collapse to one of them, indicating that fibring imposes unwanted interconnections between the given logics. Modulated fibring allows a finer control of the combination, solving the collapsing problem both at the semantic and deductive levels. Main properties like soundness and completeness are shown to be preserved, comparison with fibring is discussed, and some important classes of examples are analyzed with respect to the collapsing problem.

For every ring S with identity, the (right) Ziegler spectrum of S, Zgs, is the set of (isomorphism classes of) indecomposable pure injective (right) S-modules. The Ziegler topology equips Zgs with the structure of a topological space. A typical basic open set in this topology is of the form

where φ and ψ are pp-formulas (with at most one free variable) in the first order language Ls for S-modules; let [φ/ψ] denote the closed set Zgs - (φ/ψ). There is an alternative way to introduce the Ziegler topology on Zgs. For every choice of two f.p. (finitely presented) S-modules A, B and an S-module homomorphism f: A → B, consider the set (f) of the points N in Zgs such that some S-homomorphism h: A → N does not factor through f. Take (f) as a basic open set. The resulting topology on Zgs is, again, the Ziegler topology.

The algebraic and model-theoretic relevance of the Ziegler topology is discussed in [Z], [P] and in many subsequent papers, including [P1], [P2] and [P3], for instance. Here we are interested in the Ziegler spectrum ZgRG of a group ring RG, where R is a Dedekind domain of characteristic 0 (for example R could be the ring Z of integers) and G is a finite group. In particular we deal with the R-torsionfree points of ZgRG.

The main motivation for this is the study of RG-lattices (i.e., finitely generated R-torsionfree RG-modules).

We give a complete description of minimal groups infinitely definable in separably closed fields of finite degree of imperfection. In particular we answer positively the question of the existence of such a group with infinite transcendence degree (i.e., a minimal group with non thin generic).

Let K be a function field of one variable over a constant field C of finite transcendence degree over ℂ. Let M/K be a finite extension and let W be a set of primes of K such that all but finitely many primes of W do not split in the extension M/K. Then there exists a set W′ of K-primes such that Hilbert's Tenth Problem is not decidable over OK,W′ = {x ϵ K∣ordþx ≥ 0, ∀þ ∉ W′}, and the set (W′ ∖ W)∪{W ∖ W′) is finite.

Let K be a function field of one variable over a constant field C finitely generated over ℚ. Let M/K be a finite extension and let W be a set of primes of K such that all but finitely many primes of W do not split in the extension M/K and the degree of all the primes in W is bounded by b ϵ ℕ. Then there exists a set W′ of K-primes such that ℤ has a Diophantine definition over OK,W′, and the set (W′ ∖ W)∪(W ∖ W′) is finite.

Borovik proposed an axiomatic treatment of Morley rank in groups, later modified by Poizat, who showed that in the context of groups the resulting notion of rank provides a characterization of groups of finite Morley rank [2]. (This result makes use of ideas of Lascar, which it encapsulates in a neat way.) These axioms form the basis of the algebraic treatment of groups of finite Morley rank undertaken in [1].

There are, however, ranked structures, i.e., structures on which a Borovik-Poizat rank function is defined, which are not ℵ0-stable [1, p. 376]. In [2, p. 9] Poizat raised the issue of the relationship between this notion of rank and stability theory in the following terms: “… un groupe de Borovik est une structure stable, alors qu'un univers rangé n'a aucune raison de l'être …” (emphasis added). Nonetheless, we will prove the following:

Theorem 1.1. A ranked structure is superstable.

An example of a non-ℵ0-stable structure with Borovik-Poizat rank 2 is given in [1, p. 376]. Furthermore, it appears that this example can be modified in a straightforward way to give ℵ0-stable structures of Borovik-Poizat rank 2 in which the Morley rank is any countable ordinal (which would refute a claim of [1, p. 373, proof of C.4]). We have not checked the details. This does not leave much room for strenghthenings of our theorem. On the other hand, the proof of Theorem 1.1 does give a finite bound for the heights of certain trees of definable sets related to unsuperstability, as we will see in Section 5.

A computably enumerable Turing degree a is called contiguous iff it contains only a single computably enumerable weak truth table degree (Ladner and Sasso [2]). In [1], the authors proved that a nonzero computably enumerable degree a is contiguous iff it is locally distributive, that is, for all a1, a2, c with a1 ∪a2 = a and c ≤ a, there exist ci, ≤ ai with c1 ∪ c2 = c.

To do this we supposed that W was a computably enumerable set and ∪ a computably set with a Turing functional Φ such that ΦW = U. Then we constructed computably enumerable sets A0, A1 and B together with functionals Γ0, Γ1, Γ, and Δ so that

and so as to satisfy all the requirements below.

That is, we built a degree-theoretical splitting A0, A1 of W and a set B ≤TW such that if we cannot beat all possible degree-theoretical splittings V0, V1 of B then we were able to witness the fact that U ≤WW (via Λ).

After the proof it was observed that the set U of the proof (page 1222, paragraph 4) needed only to be Δ20. It was then claimed that a consequence to the proof was that every contiguous computably enumerable degree was, in fact, strongly contiguous, in the sense that all (not necessarily computably enumerable) sets of the degree had the same weak truth table degree.

We prove that a form of the Erdӧs property (consistent with V = L[Hω2] and strictly weaker than the Weak Chang's Conjecture at ω1), together with Bounded Martin's Maximum implies that Woodin's principle ψAC holds, and therefore . We also prove that ψAC implies that every function f: ω1 → ω1 is bounded by some canonical function on a club and use this to produce a model of the Bounded Semiproper Forcing Axiom in which Bounded Martin's Maximum fails.

In this article we provide wellordering proofs for metapredicative systems of explicit mathematics and admissible set theory featuring suitable axioms about the Mahloness of the underlying universe of discourse. In particular, it is shown that in the corresponding theories EMA of explicit mathematics and KPm0 of admissible set theory, transfinite induction along initial segments of the ordinal φω00, for φ being a ternary Veblen function, is derivable. This reveals that the upper bounds given for these two systems in the paper Jäger and Strahm [11] are indeed sharp.

Let K be a computable field. Let ℱ be a collection of recursive functions over K, possibly including field operations. We investigate the following question. Given an r.e. degree . is there an injective map j : K → ℕ such that j(K) is of degree a and all the functions in ℱ are translated by restrictions of total recursive functions.

In this paper we present some metapredicative subsystems of analysis. We deal with reflection principles, ω-model existence axioms (limit axioms) and axioms asserting the existence of hierarchies. We show several equivalences among the introduced subsystems. In particular we prove the equivalence of Σ11 transfinite dependent choice and Π21 reflection on ω-models of Σ11-DC.

Can a supercompact cardinal κ be Laver indestructible when there is a level-by-level agreement between strong compactness and supercompactness? In this article, we show that if there is a sufficiently large cardinal above κ, then no, it cannot. Conversely, if one weakens the requirement either by demanding less indestructibility, such as requiring only indestructibility by stratified posets. or less level-by-level agreement, such as requiring it only on measure one sets, then yes. it can.

We develop the theory of germs of generic functions in simple theories. Starting with an algebraic quadrangle (or other similar hypotheses), we obtain an “almost” generic group chunk, where the product is defined up to a bounded number of possible values. This is the first step towards the proof of the group configuration theorem for simple theories, which is completed in [3].

We consider equational theories for functions denned via recursion involving equations between closed terms with natural rules based on recursive definitions of the function symbols. We show that consistency of such equational theories can be proved in the weak fragment of arithmetic S21. In particular this solves an open problem formulated by Takeuti (c.f. [5, p.5 problem 9.]).

Using the description of the Ziegler spectrum we characterise modules with various stability-theoretic properties (ω-stability, superstability, categoricity) over certain classes of finite-dimensional algebras. We also show that, for modules over the algebras we consider, having few types is equivalent to being ω-stable.

We consider a small supersimple theory with a property (CS) (close to stability). We prove that if in such a theory T there is a type p ∈ S(A) (where A is finite) with SU(p) = 1 and infinitely many extensions over acleq(A), then in T there is a modular such type. Also, if T is supersimple with (CS) and p ∈ S(∅) is isolated, SU(p) = 1 and p has infinitely many extensions over acleq (∅), then p is modular.

We prove the consistency result from the title. By forcing we construct a model of g = ℵ1, b = cf(Sym(ω)) = ℵ2.

Assume (ℵ0, ℵ1) → (λ, λ+). Assume M is a model of a first order theory T of cardinality at most λ+ in a language of cardinality ≤ λ. Let N be a model with the same language. Let Δ be a set of first order formulas in and let D be a regular filter on λ. Then M is Δ-embeddable into the reduced power Nλ/D, provided that every Δ-existential formula true in M is true also in N. We obtain the following corollary: for M as above and D a regular ultrafilter over λ, Mλ/D is λ++-universal. Our second result is as follows: For i < μ let Mi, and Ni, be elementarily equivalent models of a language which has cardinality ≤ λ. Suppose D is a regular filter on λ and (ℵ0, ℵ1) → (λ, λ+) holds. We show that then the second player has a winning strategy in the Ehrenfeucht-Fraïssé game of length λ+ on ΠiMi/D and ΠiNi/D. This yields the following corollary: Assume GCH and λ regular (or just (ℵ0, ℵ1) → (λ, λ+) and 2λ = λ+. For L, Mi and Ni be as above, if D is a regular filter on λ, then ΠiMi/D ≅ ΠiNi/D.