Given two (positive) equivalence relations ~1, ~2 on the set ω of natural numbers, we say that ~1 is m-reducible to ~2 if there exists a total recursive function h such that for every x, y ∈ ω, we have x ~1y iff hx ~2hy. We prove that the equivalence relation induced in ω by a positive precomplete numeration is complete with respect to this reducibility (and, moreover, a “uniformity property” holds). This result allows us to state a classification theorem for positive equivalence relations (Theorem 2). We show that there exist nonisomorphic positive equivalence relations which are complete with respect to the above reducibility; in particular, we discuss the provable equivalence of a strong enough theory: this relation is complete with respect to reducibility but it does not correspond to a precomplete numeration.

From this fact we deduce that an equivalence relation on ω can be strongly represented by a formula (see Definition 8) iff it is positive. At last, we interpret the situation from a topological point of view. Among other things, we generalize a result of Visser by showing that the topological space corresponding to a partition in e.i. sets is irreducible and we prove that the set of equivalence classes of true sentences is dense in the Lindenbaum algebra of the theory.

The number of homogeneous models has been studied in [1] and other papers. But the number of countable homogeneous models of a countable theory T is not determined when dropping the GCH. Morley in [2] proves that if a countable theory T has more than ℵ1 nonisomorphic countable models, then it has such models. He conjectures that if a countable theory T has more than ℵ0 nonisomorphic countable models, then it has such models. In this paper we show that if a countable theory T has more than ℵ0 nonisomorphic countable homogeneous models, then it has such models.

We adopt the conventions in [1]–[3]. Throughout the paper T is a theory and the language of T is denoted by L which is countable.

Lemma 1. If a theory T has more than ℵ0types, then T hasnonisomorphic countable homogeneous models.

Proof. Suppose that T has more than ℵ0 types. From [2, Corollary 2.4] T has types. Let σ be a Ttype with n variables, and T′ = T ⋃ {σ(c1, …, cn)}, where c1, …, cn are new constants. T′ is consistent and has a countable model (, a1, …, an). From [3, Theorem 3.2.8] the reduced model has a countable homogeneous elementary extension . σ is realized in . This shows that every type σ is realized in at least one countable homogeneous model of T. But each countable model can realize at most ℵ0 types. Hence T has at least countable homogeneous models. On the other hand, a countable theory can have at most nonisomorphic countable models. Hence the number of nonisomorphic countable homogeneous models of T is .

In the following, we shall use the languages Lα (α = 0, 1, 2) defined in [2]. We give a brief description of them. For a countable theory T, let K be the class of all models of T. L = L0 is countable.

We prove that the logics of Magidor-Malitz and their generalization by Rubin are distinct even for PC classes.

Let M ⊨ Qnx1 … xnφ(x1 … xn) mean that there is an uncountable subset A of ∣M∣ such that for every a1 …, an ∈ A, M ⊨ φ[a1, …, an].

Theorem 1.1 (Shelah) (♢ℵ1). For every n ∈ ωthe classKn+1 = {‹A, R› ∣ ‹A, R› ⊨ ¬ Qn+1x1 … xn+1R(x1, …, xn+1)} is not an ℵ0-PC-class in the logic ℒn, obtained by closing first order logic underQ1, …, Qn. I.e. for no countable ℒn-theory T, isKn+1the class of reducts of the models of T.

Theorem 1.2 (Rubin) (♢ℵ1). Let M ⊨ QE x yφ(x, y) mean that there is A ⊆ ∣M∣ such thatEA, φ = {‹a, b› ∣ a, b ∈ A and M ⊨ φ[a, b]) is an equivalence relation on A with uncountably many equivalence classes, and such that each equivalence class is uncountable. Let KE = {‹A, R› ∣ ‹A, R› ⊨ ¬ QExyR(x, y)}. Then KE is not an ℵ0-PC-class in the logic gotten by closing first order logic under the set of quantifiers {Qn ∣ n ∈ ω) which were defined in Theorem 1.1.

In this paper some partial models for combinators with weak reduction are proposed. The underlying ideas are due to Church [1]. The results are extensions of the previous results of the author proved in [8].

The results in this paper were motivated by the following result due to R. Solovay.

Theorem 1 (Solovay). Let M be a nonstandard model of Peano's first order axioms P and let I ⊂e M (i.e. ϕ ≠ ⊂ M and I is closed under < and successor). Then for each of the functions we can define J ⊆e I in ‹M, I› such that J is closed under that function. (∣x∣ denotes [log2(x)].)

Proof. Just notice that the cuts defined by

are successively closed under

In view of Theorem 1, the following question was raised by R. Solovay: Can we define J ⊆ I in ‹M, I› such that J is closed under exponentiation? In Theorem 2 we show that the answer is “no”. Theorem 3 is based on Theorem 2 and extends the technique to cuts which are models of subsystems of P.

To prove both theorems we shall need an estimate due to R. Parikh (see [1], especially the proof of Theorem 2.2a). For the sake of completeness, and also to introduce some notation we shall sketch Parikh's estimate in the next section. At all times we shall give the easiest estimates which still work rather than the sharpest ones.

This is the first part of a series of papers on certain topics of model theory of modules, which will further consist of Part II. On stability and categoricity of flat modules and Part III. On infiniteness of sets definable in modules. Although these parts are only weakly connected, it is convenient to have common background and notation. The first part was written in Summer 1980, when I did not know about either footnote (3) appearing in the final version of [GA 2] or about the work of the “Bedford College Group” concerning stability theory of modules. I would like to thank Wilfrid Hodges and Mike Prest for their interest in this note, which encouraged me to include it as the first part of the present series, and for acquainting me with their unpublished work, to which I refer in footnotes. I should also like to thank the referee for his suggestions, in particular for correcting the argument in Remark (5) and for drawing my attention to [Z-H].

A syntactical analysis of Zimmermann's notion of “endlich matriziellen Untergruppen” of modules [ZI, p. 1087] shows that it coincides with the notion of subgroups definable by positive primitive formulae (without parameters) [GA 1, p. 80]. Then combination of [ZI, Folgerung 3.4] with [GA 1, Lemma 5] (or [GA 2, Theorem 1] for uncountable rings) yields purely algebraic criteria for total transcendence of modules. I present here a proof of this result using only the following facts.

(G1) A module M is totally transcendental iff it satisfies the minimal condition on subgroups definable by positive primitive formulae (without parameters) [GA 1, Lemma 5] (and [GA 2, Theorem 1] for uncountable rings).

In this paper we show that it is consistent with ZFC that for any set of reals of cardinality the continuum, there is a continuous map from that set onto the closed unit interval. In fact, this holds in the iterated perfect set model. We also show that in this model every set of reals which is always of first category has cardinality less than or equal to ω1.

In [1978] Harrington and MacQueen proved that if B is an (A, E)-semirecursive subset of A, such that the functions in BA can be coded as elements of A in an (A, E)-recursive way, then ENV(A, E) is closed under the existential quantifier ∃T ∈ B.

Later Moschovakis showed that if ENV(Vκ, ∈, E) is closed under the quantifier ∃t ∈ λ, where λ is the p-cofinality of κ, then

the p-cofinality of κ is the least ordinal λ for which there exists a (κ, <, E)-recursive partial function ƒ into κ, such that ƒ∣λ is total from λ onto an unbounded subset of κ.

In this paper we prove that for any infinite ordinal κ if p-card(κ) = κ, then ENV(κ, <, E) is closed under ∃t ∈ μ, for μ < p-cf(κ); p-cf(κ) is the “boldface” analog of p-cf((κ) and p-card(κ) is defined similarly.

From this follows that for any infinite ordinal κ the following two statements are equivalent.

(i) ENV(κ, <, E) is closed under bounded existential quantification.

(ii) ENV(κ, <, E) = ENV(κ, <, E#) or p-cf(κ) = κ.

We also show that we cannot omit any of the hypotheses in the above theorem.

We follow mainly the notation of Kechris and Moschovakis [1977].

It was brought to our attention by M. Fitting that Beth's semantic tableau system using the intuitionistic propositional rules and the classical quantifier rules produces a correct but incomplete axiomatization of the logic CD of constant domains. The formula

where T is a truth constant, being an instance of a formula which is valid in all Kripke models with constant domains but which is not provable without cut.

From the Fitting formula one can immediately obtain that the sequent

although provable in the system GD outlined in [3], does not have a cut-free proof (in the system GD).

If the only problem with GD were the sequent S0, then we could extend GD to the system GD+ by adding the following (correct) rule:

Since the new rule still satisfies the subformula property a cut elimination theorem for GD+ would be a step in the right direction for a syntactical proof for the interpolation theorem for the logic of constant domains (cf. Gabbay [2]; see also §4). Unfortunately, one can show that the sequent

where P is a propositional parameter (or formula without x free) has a derivation in GD+, but does not have a cut-free derivation (in GD+). Of course, we could extend GD+ to GD++ by adding the following correct (and with the subformula property) rule:

But then we can find a sequent S2 which, although provable with cut in GD++, does not have a cut-free derivation in GD++.

Let U and U′ be measures on a cardinal κ: that is, normal κ-complete ultrafilters on κ. The partial ordering ⊲ was defined in [M74]: we say U ⊲ U′ if U ∈ Vκ/U′. A model L(ℱ) was constructed in which this ordering was a well ordering, and it was shown that under proper assumptions the length of this well ordering could be any ordinal up to κ++L(ℱ). In this paper we will revisit this material and show that the coherence required in the construction of ℱ can be greatly weakened. This change simplifies some proofs, weakens the assumption needed for the results stated above (Theorem 1, below), and proves one new result (Theorem 5, below) which is suggestive although its significance is not clear.

We have tried to make this paper self-contained and to that end have repeated some material from [M74]. We begin with some definitions before stating Theorem 1.

The ordering ⊲ is well founded. This may be seen by assuming that it is not and letting κ be least such that ⊲ is not well founded on measures on κ. If U is a measure on κ with an infinite descending chain below it, then the measures on κ in VκU are still not well founded by ⊲, contradicting the fact that iU(κ) is the least cardinal in Vκ/U such that ⊲ is not well founded. Since ⊲ is well founded, we can define O(U) to be the rank of U in the partial ordering ⊲ of measures on κ, and O(κ) to be the rank of this partial ordering.

In [5], Metakides and Nerode introduced the study of recursively enumerable (r.e.) substructures of a recursively presented structure. The main line of study presented in [5] is to examine the effective content of certain algebraic structures. In [6], Metakides and Nerode studied the lattice of r.e. subspaces of a recursively presented vector space. This lattice was later studied by Kalantari, Remmel, Retzlaff and Shore. Similar studies have been done by Metakides and Nerode [7] for algebraically closed fields, by Remmel [10] for Boolean algebras and by Metakides and Remmel [8] and [9] for orderings. Kalantari and Retzlaff [4] introduced and studied the lattice of r.e. subsets of a recursively presented topological space. Kalantari and Retzlaff considered X, a topological space with ⊿, a countable basis. This basis is coded into integers and with the help of this coding, r.e. subsets of ω give rise to r.e. subsets of X. The notion of “recursiveness” of a topological space is the natural next step which gives rise to the question of what should be the “degree” of an r.e. open subset of X? It turns out that any r.e. open set partitions ⊿; into four sets whose Turing degrees become central in answering the question raised above.

In this paper we show that the degrees of the elements of the partition of ⊿ imposed by an r.e. open set can be “controlled independently” in a sense to be made precise in the body of the paper. In [4], Kalantari and Retzlaff showed that given A any r.e. set and any r.e. open subset of X, there exists an r.e. open set ℋ which is a subset of and is dense in (in a topological sense) and in which A is coded. This shows that modulo a nowhere dense set, an r.e. open set can become as complicated as desired. After giving the general technical and notational machinery in §1, and giving the particulars of our needs in §2, in §3 we prove that the set ℋ described above could be made to be precisely of degree of A. We then go on and establish various results (both existential and universal) on the mentioned partitioning of ⊿. One of the surprising results is that there are r.e. open sets such that every element of partitioning of ⊿ is of a different degree. Since the exact wording of the results uses the technical definitions of these partitioning elements, we do not summarize the results here and ask the reader to examine §3 after browsing through §§1 and 2.

In [6], Nadel showed that if is a recursively saturated model of Pr = Th(ω, +) of power at most ℵ1, then there is a model such that ≡ ∞ω and can be expanded to a recursively saturated model of P. For a fixed completion T of P, can be chosen to have a recursively saturated expansion to a model of T just in case is recursive in T-saturated. (“Recursive in T-saturation” is defined just like recursive saturation except that the sets of formulas considered are those that are recursive in T.)

Nadel also showed in [6] that for a fixed completion T of P, a countable nonstandard model of Pr can be expanded to a model of T (not necessarily recursively saturated) iff satisfies a condition called “exp(T)-saturation.” This condition is stronger than recursive saturation but weaker than recursive in T-saturation. Nadel left open the problem of characterizing the models of Pr of power ℵ1 such that for some , ≣ ∞ω and can be expanded to a model of T. The present paper gives such a characterization. The condition on is that it is recursively saturated, and for each n ∈ ω, the set Tn of Πn-sentences of T is recursive in some type realized in .

This result can be interpreted in various ways, just as the results from [6] were interpreted in various ways in [4]. Friedman [2] introduced the notion of a “standard system.”

In recent years higher recursion theory has experienced a deep interaction with other areas of logic, particularly set theory (fine structure, forcing, and combinatorics) and infinitary model theory. In this paper we wish to illustrate this interaction by surveying the progress that has been made in two areas: the global theory of the κ-degrees and the study of closure ordinals.

We discuss the problem of finding forcing posets which introduce closed unbounded subsets to a given stationary set.

ℵ2. One of the first examples of the forcing method is cardinal collapsing (A. Levy, see [5]), for example, collapsing ℵ2 to ℵ1: the poset P is the collection of all countable functions from a countable ordinal into ℵ2. As is well known, in VP, , and because P is closed under union of countable chains, remains a cardinal and, in fact, no new countable sets are added. But to prove that remains a cardinal we need to conclude ∣P∣ ≤ ℵ2 and hence ℵ3 is not collapsed. If it has been observed that is actually collapsed in VP. Hence the following theorem, which makes no assumptions on the continuum, is relevant.

1. Theorem. There is a poset R such that in VR ℵ2 becomes of cardinality ℵ1, but ℵ1 and the cardinals above ℵ2 are not collapsed.

It is known [4, Theorem 11-X(b)] that there is only one acceptable universal function up to recursive isomorphism. It follows from this that sets definable in terms of a universal function alone are specified uniquely up to recursive isomorphism. (An example is the set K, which consists of all n such that {n}(n) is defined, where λn, m{n}(m) is an acceptable universal function.) Many of the interesting sets constructed and studied by recursion theorists, however, have definitions which involve additional notions, such as a specific enumeration of the graph of a universal function. In particular, many of these definitions make use of the interplay between the purely number-theoretic properties of indices of partial recursive functions and their purely recursion-theoretic properties.

This paper concerns r.e. sets that can be defined using only a universal function and some purely number-theoretic concepts. In particular, we would like to know when certain recursion-theoretic properties of r.e. sets definable in this way are independent of the particular choice of universal function (equivalently, independent of the particular way in which godel numbers are identified with natural numbers).

We will first develop a suitable model-theoretic framework for discussing this question. This will enable us to classify the formulas defining r.e. sets by their logical complexity. (We use the number of alternations of quantifiers in the prenex form of a formula as a measure of logical complexity.) We will then be able to examine the question at each level.

This work is an approach to the question of when the recursion-theoretic properties of an r.e. set are independent of the particular parameters used in its construction. As such, it does not apply directly to the construction techniques most commonly used at this time for defining particular r.e. sets, e.g., the priority method. A more direct attack on this question for these techniques is represented by such works as [3] and [5]. However, the present work should be of independent interest to the logician interested in recursion theory.

It is shown how to define forcing semantics within metatheories not containing the power-set construction, in particular, how to construct exponents assuming only (a slightly strengthened form of) exponents in the metatheory. Some straightforward applications (consistency and independence results, and derived rules) are obtained for such systems.

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.

It will be shown that in the lattice of recursively enumerable sets all lattices L3(X) are elementarily definable with parameters, where X is and L3(X) consists of all sets containing X.

In this paper we give short proofs to the undecidability of the τ-theory for free groups and other relevant theories.