We construct a strongly minimal set which is not a finite cover of one with DMP. We also show that for a strongly minimal theory T, generic automorphisms exist iff T has DMP, thus proving a conjecture of Kikyo and Pillay.

L denotes a fixed finitary similarity type, B, respectively P a new relation symbol, an L-structure in the usual sense, and (, σ) a topological L-structure, where σ is a topology on A. (, σ) is countable if is countable and σ has a countable base. The formal language for our study of topological structures is . is the least fragment of the (monadic) second-order, infinitary language closed under negation (⇁), countable disjunction (∨), countable conjunction (∧), quantification over individual variables (∃ν, ∀ν), and quantification over set variables in the form ∃V(t ∈ V → φ) [respectively ∃V(t ∈ V → φ] where t is an L-term and each free occurrence of V in φ is negative [respectively positive]. We abbreviate ∃V(t ∈ V ∧ φ) and ∀V(t ∈ V → φ) by ∃V ∈ ν φ respectively ∀V ∈ ν φ. (For detailed information on we reIer to [1].)

i, j, … m, n range over ω. a, x, etc. denote finite tuples; a ∈ A means that all members of a are in A. IdA denotes the identity on A, Perm(A) the set of all permutations of A, and Aut() (respectively Aut(, σ)) the set of all automorphisms of (respectively (σ)). Let F ⊆ Perm(A), B ⊆ Am(m ≥ 1), and μ be a system of subsets of A. B (respectively μ) is called invariant under F if for all ƒ ∈ F, ƒ(B) = B (respectively ƒ(μ) = μ). denotes the least system of subsets of A which contains μ and which is closed under arbitrary union, .

For the rest of this paragraph let A be a countable nonempty set.

A hierarchy of systems of quantifier-free elementary recursive arithmetics, based on the Grzegorczyk hierarchy of functions, was set up in [2] and some meta-mathematical properties of these systems were developed. The Grzegorczyk hierarchy has been extended recently, mainly by Löb and Wainer [5], and our metamathematical developments may be similarly extended; the αth member of this hierarchy of formal systems will be denoted -arithmetic throughout. The main result in [2] was: For α > 1, -arithmetic can be proved consistent in -arithmetic. In this paper we shall continue this work in particular, beginning with this consistency result, we shall find (for α > 1) the order type of the weakest simple transfinite induction scheme which is independent of -arithmetic, thus giving a ‘measure of the complexity of derivations’ of these systems. For example we shall show that transfinite induction on a sequence of type ωω is a nonderivable rule of primitive recursive arithmetic (-arithmetic). This particular result was proved by Guard in [4] by a specialisation of a version of Gentzen's proof that ∈0-transfinite induction is independent of some standard formal systems of arithmetic with quantifiers. These methods can be adapted to our hierarchy but require what we might term an ‘ωω-jump’—that is if β is the largest ordinal for which transfinite induction up to β is derivable in the system in question then a scheme of transfinite induction up to β·ωω is independent. The proof presented in this paper requires only an ‘ω-jump’ and allows more precise results to be obtained for the systems in the extended Grzegorczyk hierarchy; it is also more direct and less proof-theoretic in character. We show that the consistency of -arithmetic (for α > 1) can be proved in a system obtained by adding to -arithmetic a transfinite induction scheme up to ω2, and that this induction scheme can be adapted to obtain the required result by increasing the ordinal and simultaneously decreasing the complexity of the functions involved in the induction scheme (detailed definitions of these concepts will be given in the next section).

The p-adic semianalytic sets are defined, locally, as boolean combinations of sets of the form over the p-adic fields ℚp, where f is an analytic function. A well-know example due to Osgood showed the projection of a semianalytic set need not be a semianalytic set. We call those sets that are, locally, the projections of p-adic semianalytic sets p-adic subanalytic sets. The theory of p-adic subanalytic sets was presented by Denef and Van den Dries in [5]. The basic tools are the quantifier elimination techniques together with the ultrametric Weierstrass Preparation Theorem. Simultaneously with their developments of the p-adic subanalytic sets, they established some basic properties of p-adic semianalytic sets.

In this paper, we prove that the closure of any p-adic semianalytic set is also a semianalytic set. The analogous property for real semianalytic sets was proved in [12] and that for rigid semianalytic sets, informed by the referee, has been proved recently by a quite different method in [14] (cf. [9]). The keys to the proof are a separation lemma (Lemma 2) and an analytic cell decomposition theorem (Theorem 2) which is an analytic version of Denef's cell decomposition theorem (see [3, 4]; A total different form of anayltic cells appeared in [13]). The analytic cell decomposition theorem allows us to partition certain kinds of basic subsets into analytic cells that possess the closure property (see §1 for the definition).

Let R be a commutative integral unital domain and L a free noncommutative Lie algebra over R. In this article we show that the ring R and its action on L are 0-interpretable in L, viewed as a ring with the standard ring language $+ , \cdot ,0$. Furthermore, if R has characteristic zero then we prove that the elementary theory $Th\left( L \right)$ of L in the standard ring language is undecidable. To do so we show that the arithmetic ${\Bbb N} = \langle {\Bbb N}, + , \cdot ,0\rangle $ is 0-interpretable in L. This implies that the theory of $Th\left( L \right)$ has the independence property. These results answer some old questions on model theory of free Lie algebras.

This paper was inspired by Lerman [14] in which he proved various properties of upper bounds for the arithmetical degrees. The degrees which are upper bounds for the arithmetical degrees were first studied by Hodes [5] and Enderton and Putnam [5]. Enderton and Putnam [5] showed that if a is an upper bound for the arithmetical degrees, then a(2) ≥ 0(ω). This area was further studied by Hodes [5], Knight, Lachlan and Soare [12], Jockusch and Simpson [12], and Sacks [17].

Enderton and Putnam [5] and Sacks [17] have combined to show that 0(ω) is the least degree in {a(2): a is an upper bound for the arithmetical degrees}. So there seem to be some analogies between the degrees of upper bounds for the arithmetical degrees and the degrees below 0(2). But Sacks [17] showed an important difference between these two structures; namely, the Turing jumps of upper bounds for the arithmetical degrees have no least element. In Lerman [14], a systematic investigation of properties of the jumps of upper bounds for the arithmetical degrees was suggested, which could lead to a definition of the jump operator over the elementary theory of the partial ordering of the degrees. Although Cooper [5] found a degree-theoretic definition of the jump operator, Lerman's plan is still interesting.

We say a degree a is generic if there is a representative A of a such that A is Cohen generic for the arithmetical sentences. By Jockusch [5], the statement that A is Cohen generic for the arithmetical sentences is equivalent to saying that for any arithmetical set S of binary strings, there is a σ extended by A such that σ is in S or no extension of σ is in S. First, we investigate the relation between generic degrees and upper bounds for the arithmetical degrees. In the case D(≤ 0′), the set of degrees below 0′, it is well known that any nonrecursive r.e. degree bounds a 1-generic degree (Cohen generic for Σ1 sentences). Jockusch and Ponser [12] showed that any degree a with a″ >T (a ∪ 0′)′ bounds a 1-generic degree.

In this paper we define and study conditional problems and their degrees. The main result is that the class of conditional degrees is a lattice extending the ordinary Turing degrees and it is dense. These properties are not shared by ordinary Turing degrees. We show that the class of conditional many-one degrees is a distributive lattice. We also consider properties of semidecidable problems and their degrees, which are analogous to r.e. sets and degrees.

For a model of Peano Arithmetic, let Lt() be the lattice of its elementary substructures, and let Lt+ () be the equivalenced lattice (Lt(),≅), where ≅ is the equivalence relation of isomorphism on Lt(). It is known that Lt+() is always a reasonable equivalenced lattice.

Theorem. Let L be a finite distributive lattice and let (L, E) be reasonable. If 0 is a nonstandard prime model of PA, then 0 has a cofinal extension such that Lt+() ≅ (L,E).

A general method for proving such theorems is developed which, hopefully, will be able to be applied to some nondistributive lattices.

Let T be a positive L1-L∞ contraction. We prove that the following statements are equivalent in constructive mathematics.

(1) The projection in L2, on the space of invariant functions exists:

(2) The sequence (Tn)n∈N Cesáro-converges in the L2 norm:

(3) The sequence (Tn)n∈N Cesáro-converges almost everywhere.

Thus, we find necessary and sufficient conditions for the Mean Ergodic Theorem and the Dunford-Schwartz Pointwise Ergodic Theorem.

As a corollary we obtain a constructive ergodic theorem for ergodic measure-preserving transformations.

This answers a question posed by Bishop.

The Löwenheim–Skolem theorem states that if a theory has an infinite model it has models of all cardinalities greater than or equal to the cardinality of the language in which the theory is defined. A natural question is what happens if there is a model whose cardinality is less than that of the language.

If κ is an infinite cardinal less than the first measurable cardinal and κ < κω, the Rabin–Keiler theorem [1, p. 139] gives an example of a theory which has a model of cardinality κ in which every element is the interpretation of a constant and all other models have cardinality μ ≥ κω. Keisler has also shown that if a theory has a model of cardinality κ it has models of all cardinalities μ ≥ κω. We will show that within the bounds of the above theorems anything can happen.

The main result is as follows.

In this article, we study an analogue of tt-reducibility for points in computable metric spaces. We characterize the notion of the metric tt-degree in the context of first-level Borel isomorphism. Then, we study this concept from the perspectives of effective topological dimension theory and of effective fractal dimension theory.

We analyze the models $L[T_{2n} ]$, where $T_{2n}$ is a tree on $\omega \times \kappa _{2n + 1}^1 $ projecting to a universal ${\rm{\Pi }}_{2n}^1 $ set of reals, for $n > 1$. Following Hjorth’s work on $L[T_2 ]$, we show that under ${\rm{Det}}\left( {{\rm{}}_{2n}^1 } \right)$, the models $L[T_{2n} ]$ are unique, that is they do not depend of the choice of the tree $T_{2n}$. This requires a generalization of the Kechris–Martin theorem to all pointclasses${\rm{\Pi }}_{2n + 1}^1$. We then characterize these models as constructible models relative to the direct limit of all countable nondropping iterates of${\cal M}_{2n + 1}^\# $. We then show that the GCH holds in $L[T_{2n} ]$, for every $n < \omega $, even though they are not extender models. This analysis localizes the HOD analysis of Steel and Woodin at the even levels of the projective hierarchy.

It is proved that all groups of finite U-rank that have the descending chain condition on definable subgroups are totally transcendental. A corollary is that any stable group that is definable in an o -minimal structure is totally transcendental of finite Morley rank.

In this paper we prove some theorems concerning measures on complete Boolean algebras. Among other things, in §I of this paper, we construct a counterexample to the following conjecture of W. Luxemburg: Every measure on a nonatomic hyperstonian Boolean algebra is normal. (See [3, p. 57].) This result is expressed by Theorem 1, §I. In order to construct this example we have to suppose that a real-valued measurable cardinal exists. This hypothesis is independent of the usual axioms of set theory. Luxemburg proved that our assumption is necessary. Our second result is stated in Theorem 2 near the end of the paper.

It is known from work of P. Young that there are recursively enumerable sets which have optimal orders for enumeration, and also that there are sets which fail to have such orders in a strong sense. It is shown that both these properties are widespread in the class of recursively enumerable sets. In fact, any infinite recursively enumerable set can be split into two sets each of which has the property under consideration. A corollary to this result is that there are recursive sets with no optimal order of enumeration.