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).

We will show that there is a nontrivial strongly minimal expansion of (ω, s), the natural numbers with successor. Pillay and Steinhorn [1] proved that there is no -minimal expansion of (ω, ≤). This result provides an interesting contrast.

The strongly minimal expansion of (ω, s) is very easy to describe. Consider the order-two permutation of ω, π recursively defined by

Let T be Th(ω, s, π, 0).

A set A is m-reducible (or Karp-reducible) to B if and only if there is a polynomial-time computable function f such that, for all x, x ∈ A if and only if f(x) ∈ B. Two sets are:

• 1-equivalent if and only if each is m-reducible to the other by one-one reductions;

• p-invertible equivalent if and only if each is m-reducible to the other by one-one, polynomial-time invertible reductions; and

• p-isumorphic if and only if there is an m-reduction from one set to the other that is one-one, onto, and polynomial-time invertible.

In this paper we show the following characterization.

Theorem. The following are equivalent:

(a) P = PSPACE.

(b) Every two 1-equivalent sets are p-isomorphic.

(c) Every two p-invertible equivalent sets are p-isomorphic.

For any group satisfying a suitable chain condition, we construct a finitely additive measure on it that is invariant under certain actions.

A fairly quotable special, but still representative, case of our main result is that for 2 ≤ n < ω, there is a natural number m(n) such that, the following holds. Assume GCH: If λ < μ are regular, there is a cofinality preserving forcing extension in which 2λ = μ and, for all σ < λ ≤ κ < η such that η(+m(n)−+) ≤ μ,

This generalizes results of [3], Section 1. and the forcing is a “many cardinals” version of the forcing there.

By inequation is meant an expression of the form,

where a, b are terms taken from any first-order formal language. An inequation is consistent iff it cannot be brought to the form,

by substitution.

In the present paper we are interested in simple forcing notions and Forcing Axioms. A starting point for our investigations was the article [4] in which several problems were posed. We answer some of those problems here.

In the first section we deal with the problem of adding Cohen reals by simple forcing notions. Here we interpret simple as of small size. We try to establish as weak as possible versions of Martin Axiom sufficient to conclude that some forcing notions of size less than the continuum add a Cohen real. For example we show that MA(σ-centered) is enough to cause that every small σ-linked forcing notion adds a Cohen real (see Theorem 1.2) and MA(Cohen) implies that every small forcing notion adding an unbounded real adds a Cohen real (see Theorem 1.6). A new almost ωω-bounding σ-centered forcing notion ℚ⊚ appears naturally here. This forcing notion is responsible for adding unbounded reals in this sense, that MA(ℚ⊚) implies that every small forcing notion adding a new real adds an unbounded real (see Theorem 1.13).

In the second section we are interested in Anti-Martin Axioms for simple forcing notions. Here we interpret simple as nicely definable. Our aim is to show the consistency of AMA for as large as possible class of ccc forcing notions with large continuum. It has been known that AMA(ccc) implies CH, but it has been (rightly) expected that restrictions to regular (simple) forcing notions might help.

Ever since Cohen invented forcing in 1963, people have studied the properties that cardinals can have in generic extensions of the ground model. A very early result of Lévy shows that if κ is a regular cardinal and λ > κ is strongly inaccessible, then there is a notion of forcing which collapses every cardinal strictly between κ and λ yet preserves every other cardinal. This, of course, answers one question of the genre “What properties can a cardinal have in a generic extension?”

Another question of the same genre that can be asked is the following: Is it possible to have a generic extension of the ground model in which all cardinals are preserved and yet the cofinalities of some cardinals are different? This question was first answered in the affirmative by Prikry, who proved the following theorem.

Theorem 1.1 (Prikry [5]). Assume that V ⊨ “ZFC + κ is measurable”. Then there is a notion of forcing, P, such that for G V-generic over P:

(1) V and V[G] have the same cardinals.

(2) V and V[G] have the same bounded subsets of κ.

(3) V[G], i.e, V[G] ⊨ “κ is Rowbottom”.

(4) V[G] ⊨ “cof(κ) = ω”.

Prikry's result naturally raises the following question: Is it possible to get a generic extension in which cardinals are preserved and yet the cofinalities of certain cardinals are different from the ground model's but are uncountable? This question was first answered in the affirmative by Magidor, who proved the following theorem.

First order properties of direct products and direct sums (weak direct products) of relational systems have been studied extensively. For example, in Feferman and Vaught [3] an effective procedure is given for reducing such properties of the product to properties of the factors, and thus in particular elementary equivalence is preserved. We consider here two-sorted relational systems, with the direct product and sum operations keeping one of the sorts stationary. (See Feferman [4] for a similar definition of extensions.)

These considerations are motivated by the example of direct products and sums of modules [8], [9]. In [9] examples are given to show that the direct product of two modules (even having only a finite number of module elements) does not preserve two-sorted (even universal) equivalence for any finite or infinitary language Lκ, λ. So we restrict attention here to direct powers and multiples (many copies of one structure). Also in [9] it is shown (for modules, but the proofs generalize immediately to two-sorted structures with a finite number of relations) that the direct multiple operation preserves first order ∀E-equivalence and the direct power operation preserves first order ∀-equivalence. We show here that these results for general two-sorted structures in a finite first order language are, in a sense, best-possible. Examples are given to show that does not imply , and that does not imply .

We will study some aspects of the local structure of models of certain C-minimal theories. We will prove (theorem 19) that, in a sufficiently saturated C-minimal structure in which the algebraic closure has the exchange property and which is locally modular, we can construct an infinite type-definable group around any non trivial point (a term to be defined later).

Let (M, )⊨ ACA0 be such that , the collection of all unbounded sets in , admits a definable complete ultrafilter and let T be a theory extending first order arithmetic coded in such that M thinks T is consistent. We prove that there is an end-extension N ⊨ T of M such that the subsets of M coded in N are precisely those in . As a special case we get that any Scott set with a definable ultrafilter coding a consistent theory T extending first order arithmetic is the standard system of a recursively saturated model of T.