We prove the elimination of Magidor-Malitz quantifiers for R-modules relative to certain -core sentences and positive primitive formulas. For complete extensions of the elementary theory of R-modules it follows that all Ramsey quantifiers (ℵ0-interpretation) are eliminable. By a result of Baldwin and Kueker [1] this implies that there is no R-module having the finite cover property.

In [1] two interesting invariance notions were introduced: the notions of a set of godel numbers being invariant to automorphisms of the structures (ω, ·) and (ω, E) respectively. Here, · and E are defined by n · m ≃ φn (m) and nEm if and only if n Є Wm, where {φn} and {Wn} are acceptable enumerations of the partial recursive functions and r.e. sets respectively. In this paper we continue the study of the invariant sets, and especially the invariant r.e. sets, of gödel numbers.

We start off with an easy result which characterizes the Turing degrees containing invariant sets. We then take a closer look at r.e. sets invariant with respect to automorphisms of (ω,E). Using the characterization [1, Theorem 4.2] of such sets, we will derive a somewhat different characterization (which was stated, but not proved, in [1, Proposition 4.4]) and, using it as a tool for constructing invariant sets, prove that the r.e. sets invariant with respect to automorphisms of (ω, E) cannot be effectively enumerated.

We will next discuss representations of r.e. sets invariant with respect to automorphisms of (ω, ·). Although these sets do not have as nice a characterization as the r.e. sets invariant with respect to automorphisms of (ω, E) do, the techniques of [1] can still profitably be used to investigate their structure. In particular, if f is a partial recursive function whose graph is invariant with respect to automorphisms of (ω, ·), then for every a in the domain of f, there is a term t(a) built up from a and · only such that f(a) ≃ t(a). This is an analog to [1, Corollary 4.3]. We will also prove an analog to a result mentioned in the previous paragraph: the r.e. sets invariant with respect to automorphisms of (ω, ·) cannot be effectively enumerated.

Several stepping up lemmas are proved which are then used to investigate the connection between definable partition relations and admissible ordinals.

This is the third and last part of an investigation in several topics of first order model theory of modules which I began in Some model theory of modules. I. On total transcendence of modules (this Journal, vol. 48 (1983), pp. 570–574) and continued in Some model theory of modules. II. On stability and categoricity of flat modules (this Journal, vol. 48 (1983), pp. 970–985). Throughout I refer to these papers as “Part I” and “Part II”.

Although these parts are only loosely connected, I will tacitly use the notation and preliminaries already introduced in the preceding ones. Further details are given in §0. Concerning Part II, the reader is assumed to be familiar with most of §1, a very small part of §4, and the criterion for elementary equivalence of modules over regular rings given in §3 (Lemma 20) of that part.

Using those tools in this paper I consider completeness of the (elementary) theory of all modules (and of some of its extensions) (§2), and eliminability of cardinality quantifiers in the elementary theories of modules (§3).

§2 is almost entirely devoted to a new short proof based on the technique developed in Part II of a theorem of Tukavkin which seems to be the first relevant result concerning the completeness of the theory of all modules (after the simple observation that any theory of infinite vector spaces is complete).

In [3] a definition of negation was presented for the system K′ of extended basic logic [1], but it has since been shown by Peter Päppinghaus (personal communication) that this definition fails to give rise to the law of double negation as I claimed it did. The purpose of this note is to revise this defective definition in such a way that it clearly does give rise to the law of double negation, as well as to the other negation rules of K′.

Although Päppinghaus's original letter to me was dated September 19, 1972, the matter has remained unresolved all this time. Only recently have I seen that there is a simple way to correct the definition. I am of course very grateful to Päppinghaus for pointing out my error in claiming to be able to derive the rule of double negation from the original form of the definition.

The corrected definition will, as before, use fixed-point operators to give the effect of the required kind of transfinite induction, but this time a double transfinite induction will be used, somewhat like the double transfinite induction used in [5] to define simultaneously the theorems and antitheorems of system CΓ.

This paper contributes to the question of under which conditions recursively enumerable sets with isomorphic lattices of recursively enumerable-supersets are automorphic in the lattice of all recursively enumerable sets. We show that hyperhypersimple sets (i.e. sets where the recursively enumerable supersets form a Boolean algebra) are automorphic if there is a -definable isomorphism between their lattices of supersets. Lerman, Shore and Soare have shown that this is not true if one replaces by .

We say that the Boolean algebra B is λ-compact, where λ is a cardinal number, if for every family Z ⊆ B∖{0} of power at most λ, if inf Z = 0 then for some finite subfamily Z0 ⊆ Z we have inf Z0 = 0.

On the set of all finite subsets of a cardinal number κ, which is denoted [κ]<ω, the sets of the form for any p Є [κ]<ω generate the filter Tκ.

This filter is a standard example of a κ-regular filter (see [2]). Because of the importance of κ-regular filters in studying the saturatedness of ultraproducts and reduced products by model-theoretic methods, the question of compactness of the algebra Bκ = P([κ]<ω/Tκ was natural. This question in the most optimistical way was formulated by M. Benda [1, Problem 5c]: is the algebra Bκω-compact for every uncountable κ?

In this paper we show that for most of the cardinal numbers which are greater or equal to 2ω the algebra Bκ is not ω-compact. Hence, in view of obtained results, the following question appears: does there exist an uncountable κ such that the algebra Bκ is κ-compact?

We use standard set-theoretical notations. CH denotes the Continuum Hypothesis, GCH denotes the General Continuum Hypothesis and MA denotes Martin's Axiom.

In an earlier paper we proved that a universal Horn class generated by finitely many finite structures has a model companion. If the language has only finitely many fundamental operations then the theory of the model companion admits a primitive recursive elimination of quantifiers and is primitive recursive. The theory of the model companion is ℵ0-categorical iff it is complete iff the universal Horn class has the joint embedding property iff the universal Horn class is generated by a single finite structure. In the last section we look at structure theorems for the model companions of universal Horn classes generated by functionally complete algebras, in particular for the cases of rings and groups.

There is a distinction between semantical paradoxes on the one hand and logical or mathematical paradoxes on the other, going back to Ramsey [1925]. Those falling under the first heading have to do with such notions as truth, assertion (or proposition), definition, etc., while those falling under the second have to do with membership, class, relation, function (and derivative notions such as cardinal and ordinal number), etc. There are a number of compelling reasons for maintaining this separation but, as we shall see, there are also many close parallels from the logical point of view.

The initial solutions to the paradoxes on each side—namely Russell's theory of types for mathematics and Tarski's hierarchy of language levels for semantics— were early recognized to be excessively restrictive. The first really workable solution to the mathematical paradoxes was provided by Zermelo's theory of sets, subsequently improved by Fraenkel. The informal argument that the paradoxes are blocked in ZF is that its axioms are true in the cumulative hierarchy of sets where (i) unlike the theory of types, a set may have members of various (ordinal) levels, but (ii) as in the theory of types, the level of a set is greater than that of each of its members. Thus in ZF there is no set of all sets, nor any Russell set {x∣x∉x} (which would be universal since ∀x(x∉x) holds in ZF). Nor is there a set of all ordinal numbers (and so the Burali-Forti paradox is blocked).

In this paper we consider various generalizations of the notion of hugeness. We remind the reader that a cardinal κ is huge if there exist a cardinal λ > κ, an inner model M which is closed under λ-sequences, and an elementary embedding i: V → M with critical point κ such that i(κ) = λ. We shall call λ a target for κ and shall write κ → (λ) to express this fact. Equivalently, κ is huge with target λ if and only if there exists a normal ultrafilter on P=κ(λ) = {X ⊆ λ:X has order type κ}. For the proof and additional facts on hugeness, see [3].

We assume that the reader is familiar with the notions of measurability and supercompactness. If κ is γ-supercompact for each γ < λ, we shall say that κ is < λ-supercompact. We note that if κ → (λ), it follows immediately that κ is < λ-supercompact.

Throughout the paper, n shall be used to denote a positive integer, the letters α, β, and δ shall denote ordinals, while κ, λ, γ, and η shall be reserved for cardinals. All addition is ordinal addition. V denotes the universe of all sets.

All results except for Theorems 6b and 6c and Lemma 6d can be formalized in ZFC.

This paper was written while the first named author was at Rochester Institute of Technology, Rochester, New York. We wish to thank the department of mathematics at R.I.T. for secretarial time and facilities.

In this paper, we remark on some properties of equality that tend to be neglected and use them to give a proof of an extension of Lyndon's interpolation theorem. Let LK be a first order classical predicate calculus and LK= a first order classical predicate calculus with equality. We assume that LK and LK= have the propositional constant Τ (truth). For each formula F in LK=, let Rel+ (F), Rel− (F), Rel(F), and Fun(F) be the set of all the predicate symbols which occur in F positively, the set of all the predicate symbols which occur in F negatively, the set of all the predicate symbols which occur in F, and the set of all the function symbols which occur in F.

Theorem A (Lyndon [5]). Suppose that A and B are sentences in LK such that A ⊃ B is provable in LK. Then there is a sentence C in LK such that:

(i) A ⊃ C and C ⊃ B are provable in LK;

(ii) and

(iii) .

The sentence C which satisfies (i), (ii), (iii) in Theorem A is said to be an interpolant for A ⊃ B in Theorem A. Note that condition (iii) is not included in the original form of Lyndon's interpolation theorem (cf. [5]), but we can easily add this condition. Also, there is some obscurity in the original formulation with regard to the equality symbol. For example, Lyndon writes: “The theorem takes the same form whether or not we admit a predicate denoting identity, with suitable axioms, to the predicate calculus” [5, p. 129].

An r.e. set A is nowhere simple if for every r.e. set We such that We − A is infinite, there is an infinite r.e. set W such that W ⊆ We − A. The definition of nowhere simple sets is due to R. Shore in [4]. In [4], Shore studied various properties of nowhere simple sets and showed that they could be used to give an elegant and simple proof of the fact that every nontrivial class of r.e. sets C closed under recursive isomorphisms is an automorphism base for , the lattice of r.e. sets modulo finite sets, (that is, an automorphism α of is completely determined by its action on C; see Theorem 8 of [4]). Shore also defined the notion of effectively nowhere simple sets.

Definition. An r.e. set A is effectively nowhere simple if there is a recursive function f such that for every i, Wf(i) ⊆ Wi − A and Wf(i) is infinite iff Wi − A is infinite. f is called a witness function for A.

Other than to produce examples of effectively nowhere simple sets and nowhere simple sets that are not effectively nowhere simple, Shore did not concern himself with the properties of effectively nowhere simple sets since he felt that effectively nowhere simple sets were unlikely to be lattice invariant in either E, the lattice of r.e. sets, or in .

We say that a pair of r.e. sets B and C split an r.e. set A if B ∩ C = ∅ and B ∪ C = A. Friedberg [F] was the first to study the degrees of splittings of r.e. sets. He showed that every nonrecursive r.e. set A has a splitting into nonrecursive sets. Generalizations and strengthenings of Friedberg's result were obtained by Sacks [Sa2], Owings [O], and Morley and Soare [MS].

The question which motivated both [LR] and this paper is the determination of possible degrees of splittings of A. It is easy to see that if B and C split A, then both B and C are Turing reducible to A (written B ≤TA and C ≤TA). The Sacks splitting theorem [Sa2] is a result in this direction, as are results by Lachlan and Ladner on mitotic and nonmitotic sets. Call an r.e. set A mitotic if there is a splitting B and C of A such that both B and C have the same Turing degree as A; A is nonmitotic otherwise. Lachlan [Lac] showed that nonmitotic sets exist, and Ladner [Lad1], [Lad2] carried out an exhaustive study of the degrees of mitotic sets.

The Sacks splitting theorem [Sa2] shows that if A is r.e. and nonrecursive, then there are r.e. sets B and C splitting A such that B <TA and C <TA. Since B is r.e. and nonrecursive, we can now split B and continue in this manner to produce infinitely many r.e. degrees below the degree of A which are degrees of sets forming part of a splitting of A. We say that an r.e. set A has the universal splitting property (USP) if for any r.e. set D ≤T A, there is a splitting B and C of A such that B and D are Turing equivalent (written B ≡TD).

There has been much work in developing the interconnections between model theory and algebra. Here we look at a particular example, the divisible ordered abelian groups, and show how the indiscernibles are related to the algebraic structure. Now a divisible ordered abelian group is a model of Th (Q, +, 0, <) and so is linearly ordered by <. Thus the theory is unstable and has a large number of models. It is therefore unrealistic to expect that a simple condition will completely determine a model. Instead we would just like to obtain nice algebraic invariants.

Definition. A subset C of a divisible ordered abelian group is a set of (order) indiscernibles iff for every sequence of integers n1,…,nk and for every c1 < … < ck and d1 < … < dk in C

Note that this simplified form of indiscernibility is an immediate consequence of quantifier elimination for the theory. The above definition could be formulated in the language of +, 0, < but we have used subtraction as a matter of convenience. Similarly we may also use rational coefficients. Also note that a set of order indiscernibles is usually defined with respect to some external order. But in this case there are only two possibilities: the ordering inherited from or its reverse. So we will always assume that a set of order indiscernibles has the ordering inherited from . We may sometimes refer to a set of indiscernibles as a sequence of indiscernibles if we want to explicitly mention the ordering associated with the set.

We prove the following Main Theorem: ZF + AD + V ⇒ L(R) ⇒ DC. As a corollary we have that Con(ZF + AD) ⇒ Con(ZF + AD + DC). Combined with the result of Woodin that Con(ZF + AD) ⇒ Con(ZF + AD + ¬ ACω) it follows that DC (as well as ACω) is independent relative to ZF + AD. It is finally shown (jointly with H. Woodin) that ZF + AD + ¬DCR, where DCR is DC restricted to reals, implies the consistency of ZF + AD + DC, in fact implies R# (i.e. the sharp of L(R)) exists.

In this paper, we establish an extended joint consistency theorem for an infinite family of free modal logics with equality. The extended joint consistency theorem incorporates the Craig and Lyndon interpolation lemmas and the Robinson joint consistency theorem. In part, the theorem states that two theories which are jointly unsatisfiable are separated by a sentence in the vocabulary common to both theories.

Our family of free modal logics includes the free versions of I, M, and S4 studied by Leblanc [5, Chapters 8 and 9], supplemented with equality as in [3]. In the relational semantics for these logics, there is no restriction on the accessibility relation in I, while in M(S4) the restriction is reflexivity (refiexivity and transitivity). We say that a restriction on the accessibility relation countenances backward-looping if it implies a sentence of the form ∀x1 …xn(x1Rx2 &…&xn ⊃ xkRxj) (1 ≤ j < k ≤ n ≥ 2), where the xi (1 ≤ i ≤ n) are distinct individual variables. Just as reflexivity and transitivity do not countenance backward-looping, neither do any of the restrictions in our family of free modal logics. (The above terminology is derived from the effect of such restrictions on Kripke tableaux constructions.) The Barcan formula, its converse, the Fitch formula, and the formula T ≠ T′ ⊃ □T ≠ T′ do not hold in our logics.

By the word problem for some class of algebraic structures we mean the problem of determining, given a finite set E of equations between words (i.e. terms) and an additional equation x = y, whether x = y must hold in all structures satisfying each member of E. In 1947 Post [P] showed the word problem for semigroups to be undecidable. This result was strengthened in 1950 by Turing, who showed the word problem to be undecidable for cancellation semigroups,i.e. semigroups satisfying the cancellation property

Novikov [N] eventually showed the word problem for groups to be undecidable.

(Many flaws in Turing's proof were corrected by Boone [B]. Even after his corrections, at least one problem remains; the sentence on line 16 of p. 502 of [T] does not follow if one relation is principal and the other is a commutation relation. A corrected and somewhat simplified version of Turing's proof can be built on the construction given here.)

In 1966 Gurevich [G] showed the word problem to be undecidable for finite semigroups. However, this result on finite structures has not been extended to cancellation semigroups or groups; indeed it is easy to see that a finite cancellation semigroup is a group, so both questions are the same. We do not here settle the word problem for finite groups, but we do show that the word problem is undecidable for finite semigroups with zero (that is, having an element 0 such that x0 = 0x = 0 for all x) satisfying an approximation to the cancellation property (1).

Questions about the constructive or effective character of particular arguments arise in several areas of classical mathematics, such as in the theory of recursive functions and in numerical analysis. Some philosophers have advocated Lewis's S4 as the proper logic in which to formalize such epistemic notions. (The fundamental work on this is Hintikka [4].) Recently there have been studies of mathematical theories formalized with S4 as the underlying logic so that these epistemic notions can be expressed. (See Shapiro [7], Myhill [5], and Goodman [2]. The motivation for this work is discussed in Goodman [3].) The present paper is a contribution to the study of the simplest of these theories, namely first-order arithmetic as formalized in S4. Following Shapiro, we call this theory epistemic arithmetic (EA). More specifically, we show that EA is a conservative extension of Hey ting's arithmetic HA (ordinary first-order intuitionistic arithmetic). The question of whether EA is conservative over HA was raised but left open in Shapiro [7].

The idea of our proof is as follows. We interpret EA in an infinitary propositional S4, pretty much as Tait, for example, interprets classical arithmetic in his infinitary classical propositional calculus in [8]. We then prove a cut-elimination theorem for this infinitary propositional S4. A suitable version of the cut-elimination theorem can be formalized in HA. For cut-free infinitary proofs, there is a reflection principle provable in HA. That is, we can prove in HA that if there is a cut-free proof of the interpretation of a sentence ϕ then ϕ is true. Combining these results shows that if the interpretation of ϕ is provable in EA, then ϕ is provable in HA.

There are two concepts of standard/nonstandard models in simple type theory.

The first concept—we might call it the pragmatical one—interprets type theory as a first order logic with countably many sorts of variables: the variables for the urelements of type 0,…, the n-ary relational variables of type (τ1, …, τn) with arguments of type (τ1,…,τn), respectively. If A ≠ ∅ then 〈Aτ〉 is called a model of type logic, if A0 = A and . 〈Aτ〉 is called full if, for every τ = (τ1,…,τn), . The variables for the urelements range over the elements of A and the variables of type (τ1,…, τn) range over those subsets of which are elements of . The theory Th(〈Aτ〉) is the set of all closed formulas in the language which hold in 〈Aτ〉 under natural interpretation of the constants. If 〈Bτ〉 is a model of Th(〈Aτ〉), then there exists a sequence 〈fτ〉 of functions fτ: Aτ → Bτ such that 〈fτ〉 is an elementary embedding from 〈Aτ〉 into 〈Bτ〉. 〈Bτ〉 is called a nonstandard model of 〈Aτ〉, if f0 is not surjective. Otherwise 〈Bτ〉 is called a standard model of 〈Aτ〉.

This first concept of model theory in type logic seems to be preferable for applications in model theory, for example in nonstandard analysis, since all nice properties of first order model theory (completeness, compactness, and so on) are preserved.

We denote by and the classes of torsion-free nilpotent groups of nilpotency class at most two and three, respectively. In this paper we show that most of the known results about existentially closed (e.c.) groups in remain true in : Up to isomorphism, there exist only countably many countable e.c. groups and they are distinguished by the ranks of their centers. An e.c. group is finitely (infinitely) generic if and only if the center has dimension one (≥ω). Apart from trivial exceptions, e.c, algebraically closed, and “closed with respect to systems of equations in one unknown” are equivalent.

Let K be a class of groups. A group G ϵ K is called existentially closed in K if G contains a solution of any finite system Σ of equations and inequations with constants in G and one or more unknowns, provided that Σ has a solution in some in K. If Σ may contain equations (in at most n unknowns) only, G is called algebraically closed (n-unknown closed [1]). We use the abbreviations e.c, a.c and n-u.c. throughout. For more background on these terms the reader is referred to [3] and [4]. We also assume a basic knowledge of generic structures. The main group theoretic notions needed here are explained in §2; [2] and [11] are the general references for this field.