We extend an independence result proved in [1]. We show that for all n, there is a special set of Πn sentences {φa}a ∈ H corresponding to elements of a linear ordering (H, <H) of order type . These sentences allow us to build completions {Ta}a ∈ H of PA such that for a <H b, Ta ∩ Σn ⊂ Tb ∩ Σn, with φa ∈ Ta, ¬φa ∈ Th. Our method uses the Barwise-Kreisel Compactness Theorem.

The notion of quasi-minimal structures was denned by B. Zil'ber as a natural generalization of minimal structures. Inspired by his work, we study here basic model theoretic properties of quasi-minimal structures. Main result is the construction of ω-saturated quasi-minimal models under ω-stability assumption.

A Carter subgroup is a self-normalizing locally nilpotent subgroup. For studying these subgroups in groups of finite Morley rank, we introduce the new notion of a locally closed subgroup. We show that every solvable group of finite Morley rank has a unique conjugacy class of Carter subgroups.

A type analysable in one-based types in a simple theory is itself one-based.

We show that there is a structure of countably infinite signature with P = N2P and a structure of finite signature with P = N1P and N1P ≠ N2P. We give a further example of a structure of finite signature with P ≠ N1P and N1P ≠ N1P. Together with a result from [10] this implies that for each possibility of P versus NP over structures there is an example of countably infinite signature. Then we show that for some finite the class of -structures with P = N1P is not closed under ultraproducts and obtain as corollaries that this class is not ∆-elementary and that the class of -structures with P ≠ N1P is not elementary. Finally we prove that for all ƒ dominating all polynomials there is a structure of finite signature with the following properties: P ≠ N1P, N1P ≠ N2P, the levels N2TIME(ni) of N2P and the levels N1TIME(ni) of N1P are different for different i, indeed DTIME(ni′) ⊈ N2TIME(ni) if i ′ > i; DTIME(ƒ) ⊈ N2P, and N2P ⊈ DEC. DEC is the class of recognizable sets with recognizable complements. So this is an example where the internal structure of N2P is analyzed in a more detailed way. In our proofs we use methods in the style of classical computability theory to construct structures except for one use of ultraproducts.

Assuming CH. Hindman [2] showed that the existence of certain ultrafilters on the power set of the natural numbers is equivalent to Hindman's Theorem. Adapting this work to a countable setting formalized in RCA0, this article proves the equivalence of the existence of certain ultrafilters on countable Boolean algebras and an iterated form of Hindman's Theorem, which is closely related to Milliken's Theorem. A computable restriction of Hindman's Theorem follows as a corollary.

In this article we study the strength of absoluteness (with real parameters) in various types of generic extensions, correcting and improving some results from [3]. (In particular, see Theorem 3 below.) We shall also make some comments relating this work to the bounded forcing axioms BMM, BPFA and BSPFA.

The statement “ absoluteness holds for ccc forcing” means that if a formula with real parameters has a solution in a ccc set-forcing extension of the universe V, then it already has a solution in V. The analogous definition applies when ccc is replaced by other set-forcing notions, or by class-forcing.

Theorem 1. [1] absoluteness for ccc has no strength; i.e., if ZFC is consistent then so is ZFC + absoluteness for ccc.

The following results concerning (arbitrary) set-forcing and class-forcing can be found in [3].

Theorem 2 (Feng-Magidor-Woodin). (a) absoluteness for arbitrary set-forcing is equiconsistent with the existence of a reflecting cardinal, i.e., a regular cardinal κ such that H(κ) is ∑2-elementary in V.

(b) absoluteness for class-forcing is inconsistent.

We consider next the following set-forcing notions, which lie strictly between ccc and arbitrary set-forcing: proper, semiproper, stationary-preserving and ω1-preserving. We refer the reader to [8] for the definitions of these forcing notions.

Using a variant of an argument due to Goldstern-Shelah (see [6]), we show the following. This result corrects Theorem 2 of [3] (whose proof only shows that if absoluteness holds in a certain proper forcing extension, then in L either ω1 is Mahlo or ω2 is inaccessible).

Let E be an infinite set, and [E]ω the set of all countably infinite subsets of E. A family ⊂ [E]ω is said to be almost disjoint (respectively, pairwise disjoint) provided for A, B ∈ , if A ≠ B then A ∩ B is finite (respectively, A ∩ B is empty). Moreover, an infinite family A is said to be a maximal almost disjoint family provided it is an infinite almost disjoint family not properly contained in any almost disjoint family. In this paper we are concerned with the following set of topological spaces defined from (maximal) almost disjoint families of infinite subsets of the natural numbers ω.

The Marker-Steinhorn Theorem (cf. [2] and [3]), says the following. If T is an o-minimal theory and M ≺ N is an elementary extension of models of T such that M is Dedekind complete in N, then for every N-definable subset X of Nk, the trace X ∩ Mk is M-definable. The original proof in [2] gives an explicit method how to construct a defining formula of X ∩ Mk out of a defining formula of X. A geometric reformulation of the Marker-Steinhorn Theorem is the definability of Hausdorff limits of families of definable sets. An explicit construction of these Hausdorff limits for expansions of the real field has recently been achieved in [1]. Both proofs and also the treatment [3] are technically involved.

Here we give a short algebraic, but not constructive proof, if T is an expansion of real closed fields. In fact we'll identify the statement of the Theorem with a valuation theoretic property of models of T (namely condition (†) below). Therefore our proof might be applicable to other elementary classes which expand fields, if a notion of dimension and a reasonable valuation theory are available.

From now on, let T be an o-minimal expansion of real closed fields. We have to show the following (cf. [2], Th. 2.1. for this formulation). If M is a model of T and p is a tame n-type over M (i.e., M is Dedekind complete in M ⟨ᾱ⟩ := dcl(Mᾱ) for some realization ᾱ of p), then p is a definable type (cf. [4], 11 .b).

We use a κ+-Mahlo cardinal to give a forcing construction of a model in which there is no sequence ⟨ Aβ : β < ω2 ⟩ of sets of cardinality ω1 such that

is stationary.

A family A ⊆ (ω) is called countably splitting if for every countable F ⊆ [ω]ω, some element of A splits every member of F. We define a notion of a splitting tree, by means of which we prove that every analytic countably splitting family contains a closed countably splitting family. An application of this notion solves a problem of Blass. On the other hand we show that there exists an Fσ splitting family that does not contain a closed splitting family.

This paper studies the expressive power that an extra first order quantifier adds to a fragment of monadic second order logic, extending the toolkit of Janin and Marcinkowski [JM01].

We introduce an operation existsn (S) on properties S that says “there are n components having S”. We use this operation to show that under natural strictness conditions, adding a first order quantifier word u to the beginning of a prefix class V increases the expressive power monotonically in u. As a corollary, if the first order quantifiers are not already absorbed in V, then both the quantifier alternation hierarchy and the existential quantifier hierarchy in the positive first order closure of V are strict.

We generalize and simplify methods from Marcinkowski [Mar99] to uncover limitations of the expressive power of an additional first order quantifier, and show that for a wide class of properties S, S cannot belong to the positive first order closure of a monadic prefix class W unless it already belongs to W.

We introduce another operation alt(S) on properties which has the same relationship with the Circuit Value Problem as reach(S) (defined in [JM01]) has with the Directed Reachability Problem. We use alt(S) to show that Πn ⊈ FO(Σn), Σn ⊈ FO(∆n). and ∆n+1 ⊈ FOB(Σn), solving some open problems raised in [Mat98].

The purpose of this paper is to establish some basic points in the model theory of comodules over a coalgebra. It is not even immediately apparent that there is a model theory of comodules since these are not structures in the usual sense of model theory. Let us give the definitions right away so that the reader can see what we mean.

Fix a field k. A k-coalgebra C is a k-vector space equipped with a k-linear map Δ: C → C ⊗ C, called the comultiplication (by ⊗ we always mean tensor product over k), and a k-linear map ε: C → k, called the counit, such that Δ⊗1C = 1C ⊗ Δ (coassociativity) and (1C ⊗ ε)Δ = 1C = (ε ⊗ 1C)Δ, where we identify C with both k ⊗ C and C ⊗ k. These definitions are literally the duals of those for a k-algebra: express the axioms for C′ to be a k-algebra in terms of the multiplication map μ: C′ ⊗ C′ → C′ and the “unit” (embedding of k into C′), δ: k → C′ in the form that certain diagrams commute and then just turn round all the arrows. See [5] or more recent references such as [7] for more.

We prove that a computably enumerable set A is effectively speedable (effectively levelable) if and only if there exists a splitting (A0, A1) of A such that both A0 and A1 are effectively speedable (effectively levelable). These results answer two questions raised by J. B. Remmel.

We prove, in ZFC, the existence of a definable, countably saturated elementary extension of the reals.

We prove that Standardization fails in every nontrivial universe definable in the nonstandard set theory BST, and that a natural characterization of the standard universe is both consistent with and independent of BST. As a consequence we obtain a formulation of nonstandard class theory in the ∈-language.

The paper discusses the notion of finite model truth definitions (or FM-truth definitions), introduced by M. Mostowski as a finite model analogue of Tarski's classical notion of truth definition.

We compare FM-truth definitions with Vardi's concept of the combined complexity of logics, noting an important difference: the difficulty of defining FM-truth for a logic does not depend on the syntax of , as long as it is decidable. It follows that for a natural there exist FM-truth definitions whose evaluation is much easier than the combined complexly of would suggest.

We apply the general theory to give a complexity-theoretical characterization of the logics for which the classes (prenex classes of higher order logics) define FM-truth. For any d ≥ 2, m ≥ 1 we construct a family of syntactically defined fragments of which satisfy this characterization. We also use the classes to give a refinement of known results on the complexity classes captured by .

We close with a few simple corollaries, one of which gives a sufficient condition for the existence, given a vocabulary σ, of a fixed number k such that model checking for all first order sentences over σ can be done in deterministic time nk.

We define the notion of approximate Euler characteristic of definable sets of a first order structure. We show that a structure admits a non-trivial approximate Euler characteristic if it satisfies weak pigeonhole principle : two disjoint copies of a non-empty definable set A cannot be definably embedded into A, and principle CC of comparing cardinalities: for any two definable sets A, B either A definably embeds in B or vice versa. Also, a structure admitting a non-trivial approximate Euler characteristic must satisfy .

Further we show that a structure admits a non-trivial dimension function on definable sets if and only if it satisfies weak pigeonhole principle : for no definable set A with more than one element can A2 definably embed into A.

In the following we try to answer a simple question, “what does forking look like in an o-minimal theory”, or more generally, “what kinds of notions of independence with what kinds of properties are admissible in an o-minimal theory?” The motivation of these question begin with the study of simple theories and generalizations of simple theories. In [3] Kim and Pillay prove that the class of simple theories may be described exactly as those theories bearing a notion of independence satisfying various axioms. Thus it is natural to ask, if we weaken the assumptions as to which axioms must hold, what kind of theories do we get? Another source of motivation, also stemming from the study of simple theories, comes from the work of Shelah in [8] and [7]. Here Shelah addresses a “classification” type problem for class of models of a theory, showing that a theory will have the appropriate “structure” type property if one can construct a partially ordered set, satisfying various properties, of models of the theory. Using this criterion Shelah shows that the class of simple theories has this “structure” property, yet also that several non-simple examples do as well (though it should be pointed out that o-minimal theories can not be among these since any theory with the strict order property will have the corresponding “non-structure” property [8]). Thus one is lead to ask, what are the non-simple theories meeting this criterion, and one is once again led to study the types of independence relation a theory might bear. Finally, Shelah in [6] provides some possible definitions of what axioms for a notion of independence one should possibly look for in order to hope that theories bearing such a notion of independence should be amenable closer analysis. In studying all of the above mentioned situations it readily becomes clear that dividing and forking play a central role in all of them, even though we are no longer dealing with the simple case where we know that dividing and forking are very well behaved. All of these considerations lead one to look for classes of non-simple theories of which something is known where one can construct interesting notions of independence and consequently also say something about the nature of forking and dividing in these contexts. Given this one is naturally lead to one of the most well behaved classes of non-simple theories, namely the o-minimal theories.

A compact complex space X is viewed as a 1-st order structure by taking predicates for analytic subsets of X, X x X, … as basic relations. Let f: X → Y be a proper surjective holomorphic map between complex spaces and set Xy ≔ f−1(y). We show that the set

is analytically constructible, i.e.. is a definable set when X and Y are compact complex spaces and f: X → Y is a holomorphic map. The analogous result in the context of algebraic geometry gives rise to the definability of Morley degree.