In the early eighties, answering a question of A. Macintyre, J. H. Schmerl ([13]) proved that every countable recursively saturated structure, equipped with a function β encoding the finite functions, is the β-closure of an infinite indiscernible sequence. This result implies that every countably saturated structure, in a countable but not necessarily recursive language, is an Ehrenfeucht-Mostowski model, by which we mean that the structure expands, in a countable language, to the Skolem hull of an infinite indiscernible sequence (in the new language).

More recently, D. Lascar ([5]) showed that the saturated model of cardinality ℵ1 of an ω-stable theory is also an Ehrenfeucht-Mostowski model.

These results naturally raise the following problem: which (countable) complete theories have an uncountably saturated Ehrenfeucht-Mostowski model. We study a generalization of this question. Namely, we call ACI-model a structure which can be expanded, in a countable language L′, to the algebraic closure (in L′) of an infinite indiscernible sequence (in L′). And we try to characterize the λ-saturated structures which are ACI-models.

The main results are the following. First it is enough to restrict ourselves to ℵ1-saturated structures: if T has an ℵ1-saturated ACI-model then, for every infinite λ, T has a λ-saturated ACI-model. We obtain a complete answer in the case of stable theories: if T is stable then the three following properties are equivalent: (a) T is ω-stable, (b) T has an ℵ1-saturated ACI-model, (c) every saturated model of T is an Ehrenfeucht-Mostowski model. The unstable case is more complicated, however we show that if T has an ℵ1-saturated ACI-model then T doesn't have the independence property.

We continue the study of the theories of Baldwin–Shi hypergraphs from [5]. Restricting our attention to when the rank δ is rational valued, we show that each countable model of the theory of a given Baldwin–Shi hypergraph is isomorphic to a generic structure built from some suitable subclass of the original class used in the construction. We introduce a notion of dimension for a model and show that there is a an elementary chain $\left\{ {\mathfrak{M}_\beta :\beta \leqslant \omega } \right\}$ of countable models of the theory of a fixed Baldwin–Shi hypergraph with $\mathfrak{M}_\beta \preccurlyeq \mathfrak{M}_\gamma $ if and only if the dimension of $\mathfrak{M}_\beta $ is at most the dimension of $\mathfrak{M}_\gamma $ and that each countable model is isomorphic to some $\mathfrak{M}_\beta $. We also study the regular types that appear in these theories and show that the dimension of a model is determined by a particular regular type. Further, drawing on a large body of work, we use these structures to give an example of a pseudofinite, ω-stable theory with a nonlocally modular regular type, answering a question of Pillay in [11].

Let P be the set of prime numbers. Theorem 1 of [1] shows that the linear case of Schinzel's Hypothesis (H) implies that multiplication is definable in 〈ω,+,P〉 and therefore that the first-order theory of this structure is undecidable. Let m be any fixed natural number >2, let R be the set of natural numbers <m which are prime to m, and let r be any fixed element of R. The set

is infinite (Dirichlet). Theorem 1 of [1] can be improved as follows:

Proposition. The linear case of Schinzel's Hypothesis (H) implies that multiplication is definable in 〈ω,+,Pm,r〉 and therefore that the first-order theory of this structure is undecidable.

Proof. We follow [1] with the following new ingredients. Let k be the number of elements of R, i.e. k = ϕ(m) where ϕ is Euler's totient function. Since k is even, the polynomial g(n) = nk + n satisfies g(0) = g(−1) = 0, so (by Lemma 1 of [1]) it follows from the linear case of (H) that there are natural numbers al (l ϵ ω) such that al+g(0), al+g(1),…, al+g(l) are consecutive primes. Since R is finite, we may assume that all the al's have the same residue t in R, so that al+g(i) ≡ t+1+i (mod m) for i ϵ R. This implies that the function t+1+i (reduced mod m) gives a permutation of R, so we can find s ϵ R such that al+g(s) ≡ r (mod m). Consider the polynomial h(n) = g(s + mn) and let bl = as+ml. Then bl + h(0), bl + h(1),…, bl + h(l) are elements of Pm,r. They are not necessarily consecutive elements of Pm,r, but they are separated by a fixed number of elements of Pm,r. This implies that {h(n) ∣ n ϵ ω} is definable in 〈ω,+,Pm,r〉(by adapting the proof of Theorem 1 of [1]), and the result follows.

A model is called minimal if it does not contain a proper elementary submodel. A class of models is called Σ11(Π11 resp. elementary) if it is axiomatized by a sentence with σ in and some string of predicate symbols. All languages considered are assumed to be countable. For each model we shall define in a natural way its rank, denoted by rk (), which is an ordinal or ∞. Intuitively speaking, rk () is the least upper bound for the number of steps needed to define the elements of by first order formulas; e.g. we shall have rk((ω, <)) = 1 (each element is f.o. definable), rk ((Z, <)) = 2 (no element is f.o. definable, each element is f.o. definable using any other element as a parameter), rk ((Q, <) ) = ∞ (no element is f.o. definable by any number of steps). This notion of rank leads to a useful game theoretic characterization of minimal models which we apply to show that the Π11 class of minimal models is not Σ11.

In [1], the principle of semisubstitutivity of implication (SSI) was introduced for ordinary PC and quantification theory. This metatheorem generalizes the notions of “antecedent” and “consequent” to cover all wf subformulas of a given formula; each such subformula will be classified as being either in “antecedental position” (A-pos) or “consequential position” (C-pos). It is simplest to check these positions in a conjunction-negation primitive system: reduce a formula φ to primitive notation (K—N) ; choose a subformula ψ of φ; count the negation signs in φ within whose scope ψ falls.

When restricted to proving formulas, the quantified propositional proof system is closely related to the theorems of Buss's theory . Namely, has polynomial-size proofs of the translations of theorems of , and proves that is sound. However, little is known about when proving more complex formulas. In this paper, we prove a witnessing theorem for similar in style to the KPT witnessing theorem for . This witnessing theorem is then used to show that proves is sound with respect to formulas. Note that unless the polynomial-time hierarchy collapses is the weakest theory in the S2 hierarchy for which this is true. The witnessing theorem is also used to show that is p-equivalent to a quantified version of extended-Frege for prenex formulas. This is followed by a proof that Gi, p-simulates with respect to all quantified propositional formulas. We finish by proving that S2 can be axiomatized by plus axioms stating that the cut-free version of is sound. All together this shows that the connection between and does not extend to more complex formulas.

If * is a binary partial function which happens to be a group law on some infinite subset of some model of a stable theory, then this subset can be embedded into a definable group such that * becomes the group operation.

The Genericity Conjecture, as stated in Beller-Jensen-Welch [1], is the following:

(*) If O# ∉ L[R], R ⊆ ω, then R is generic over L.

We must be precise about what is meant by “generic”.

Definition (Stated in Class Theory). A generic extension of an inner model M is an inner model M[G] such that for some forcing notion ⊆ M:

(a) 〈M, 〉 is amenable and ⊩ is 〈M, 〉-definable for sentences.

(b) G ⊆ is compatible, closed upwards, and intersects every 〈M, 〉-definable dense D ⊆ .

A set x is generic over M if it is an element of a generic extension of M. And x is strictly generic over M if M[x] is a generic extension of M.

Though the above definition quantifies over classes, in the special case where M = L and O# exists, these notions are in fact first order, as all L-amenable classes are definable over L[O#]. From now on assume that O# exists.

Theorem A. The Genericity Conjecture is false.

The proof is based upon the fact that every real generic over L obeys a certain definability property, expressed as follows.

Fact. If R is generic over L, then for some L-amenable class A, Sat〈L, A〉 is not definable over 〈L[R],A〉, where Sat〈L,A〉 is the canonical satisfaction predicate for 〈L,A〉.