Applying the seed concept to Prikry tree forcing ℙμ, I investigate how well ℙμ preserves the maximality property of ordinary Prikry forcing and prove that ℙμ, Prikry sequences are maximal exactly when μ admits no non-canonical seeds via a finite iteration. In particular, I conclude that if μ is a strongly normal supercompactness measure, then ℙμ Prikry sequences are maximal, thereby proving, for a large class of measures, a conjecture of W. Hugh Woodin's.

Let V∞ be a fixed, fully effective, infinite dimensional vector space. Let be the lattice consisting of the recursively enumerable (r.e.) subspaces of V∞, under the operations of intersection and weak sum (see §1 for precise definitions). In this article we examine the algebraic properties of .

Early research on recursively enumerable algebraic structures was done by Rabin [14], Frölich and Shepherdson [5], Dekker [3], Hamilton [7], and Guhl [6]. Our results are based upon the more recent work concerning vector spaces of Metakides and Nerode [12], Crossley and Nerode [2], Remmel [15], [16], and Kalantari [8].

In the main theorem below, we extend a result of Lachlan from the lattice of r.e. sets to . We define hyperhypersimple vector spaces, discuss some of their properties and show if A, B ∈ , and A is a hyperhypersimple subspace of B then there is a recursive space C such that A + C = B. It will be proven that if V ∈ and the lattice of superspaces of V is a complemented modular lattice then V is hyperhypersimple. The final section contains a summary of related results concerning maximality and simplicity.

In recent years, the Axiom of Determinateness (AD) has yielded numerous results concerning the size and properties of the first ω-many uncountable cardinals. Briefly, these results began with Solovay's discovery that ℵ1 and ℵ2 are measurable [8], [3], continued with theorems of Solovay, Martin, and Kunen concerning infinite-exponent partition relations [6], [3], Martin's proof that ℵn has confinality ℵ2 for 1 < n < ω, and very recently, Kleinberg's proof that the ℵn are Jonsson cardinals [4].

This paper was inspired by a very recent result of Martin from AD that ℵ1 is ℵ2-super compact. It was known for some time that AD implies ℵ1 is α-strongly compact for all ℵ < θ (where θ is the least cardinal onto which 2ω cannot be mapped, quite a large cardinal under AD), and that ADR implies that ℵ1, is α-super compact for all α < θ. A key open question had been whether or not ℵ1 is super compact under AD alone.

This paper comments on the method of Martin in several different ways. In §2, we will prove that ℵ1 is ℵ2-super compact, and then generalize the method to show that ℵ2 is ℵ3-strongly compact. In addition, we will demonstrate a limitation in the method by showing that the possible measures obtained on are not normal, and that the method cannot be extended to show that ℵ2 is ℵ4-strongly compact.

Although Brouwer became famous for his vehement attacks upon classical logic and set theory, his work did not develop in a vacuum and strongly depended on that of Cantor.

His mind bent on shifting aside nonconstructive arguments, he tried to rebuild Cantor's edifice along new, intuitionistic lines. The continuum hypothesis, lying at the core of set theory, also confronted Brouwer, and he had to face the farthest conclusion Cantor had been able to reach in trying to solve it: every nondenumerable closed subset of the real line has the power of the continuum.

Brouwer's thinking about it seems to have been subject to some development. In 1914 we hear him saying: “Wir sahen oben dass das Cantorsche Haupttheorem für den Intuitionisten keines Beweises bedarf” (“As we saw above, for us, being intuitionists, Cantor's Main Theorem does not need a proof”) [3]. Nevertheless, five years later, he publishes an essay: Theorie der Punktmengen, which might be described as an attempt to reconstruct Cantor's reasonings in detail [4].

This attempt was not entirely successful, as Brouwer comes to admit in 1952, probably having lost, now, some of his youthful rashness [10]. So the question of what the constructive content of Cantor's Main Theorem is, still awaits an answer.

We do not think the answer we will give can be considered a conclusive one, but, in any case, it is a beginning.

In this paper we show how the assumption of the generalized continuum hypothesis (GCH) can be removed or partially removed from proofs in Zermelo-Frankel set theory (ZF) of statements expressible in the simple theory of types. We assume the reader is familiar with the latter language, especially with the classification of formulas and sentences of that language into Σκη and Πκη form (cf. [1]) and with how that language can be relatively interpreted into the language of ZF.

This paper calculates, in a precise way. the complexity of the index sets for three classes of computable structures: the class of structures of Scott rank , the class , of structures of Scott rank , and the class K of all structures of non-computable Scott rank. We show that I(K) is m-complete is m-complete relative to Kleene's and is m-complete relative to .

In recent years there has been a proliferation of logics which extend first-order logic, e.g., logics with infinite sentences, logics with cardinal quantifiers such as “there exist infinitely many…” and “there exist uncountably many…”, and a weak second-order logic with variables and quantifiers for finite sets of individuals. It is well known that first-order logic has a limited ability to express many of the concepts studied by mathematicians, e.g., the concept of a wellordering. However, first-order logic, being among the simplest logics with applications to mathematics, does have an extensively developed and well understood model theory. On the other hand, full second-order logic has all the expressive power needed to do mathematics, but has an unworkable model theory. Indeed, the search for a logic with a semantics complex enough to say something, yet at the same time simple enough to say something about, accounts for the proliferation of logics mentioned above. In this paper, a number of proposed strengthenings of first-order logic are examined with respect to their relative expressive power, i.e., given two logics, what concepts can be expressed in one but not the other?

For the most part, the notation is standard. Most of the notation is either explained in the text or can be found in the book [2] of Chang and Keisler. Some notational conventions used throughout the text are listed below: the empty set is denoted by ∅.

We study extensions of Presburger arithmetic with a unary predicate R and we show that under certain conditions on R, R is sparse (a notion introduced by A. L. Semënov) and the theory of 〈ℕ, +, R〉 is decidable. We axiomatize this theory and we show that in a reasonable language, it admits quantifier elimination. We obtain similar results for the structure 〈ℚ, +, R〉.

It is known that every < ε0-recursive function is also a primitive recursive functional. Kreisel has proved this by means of Gödel's functional-interpretation, using that every < ε0-recursive function is provably recursive in Heyting's arithmetic [2, §3.4]. Parsons obtained a refinement of Kreisel's result by a further examination of Gödel's interpretation with regard to type levels [3, Theorem 5], [4, §4]. A quite different proof is provided by the research into extensions of the Grzegorczyk hierarchy as done by Schwichtenberg and Wainer: this yields another characterization of the < ε0-recursive functions from which easily appears that these are primitive recursive functionals (see [5] in combination with [6, Chapter II]).

However, these proofs are indirect and do not show how, in general, given a definition tree of an ordinal recursive functional, transfinite recursions can be replaced (in a straightforward way) by recursions over wellorderings of lower order types. The argument given by Tait in [9, pp. 189–191] seems to be an improvement in this respect, but the crucial step in it is (at least in my opinion) not very clear.

We study the relations between abelian groups B and C that every universal (resp. universal-existential) sentence true in B is also true in C, and give algebraic criteria for these relations to hold. As a consequence we characterize the inductive complete theories of abelian groups and prove that they are exactly the model-complete theories.

A narrow system is a combinatorial object introduced by Magidor and Shelah in connection with work on the tree property at successors of singular cardinals. In analogy to the tree property, a cardinal κ satisfies the narrow system property if every narrow system of height κ has a cofinal branch. In this paper, we study connections between the narrow system property, square principles, and forcing axioms. We prove, assuming large cardinals, both that it is consistent that ℵω+1 satisfies the narrow system property and $\square _{\aleph _\omega , < \aleph _\omega } $ holds and that it is consistent that every regular cardinal satisfies the narrow system property. We introduce natural strengthenings of classical square principles and show how they can be used to produce narrow systems with no cofinal branch. Finally, we show that the Proper Forcing Axiom implies that every narrow system of countable width has a cofinal branch but is consistent with the existence of a narrow system of width ω1 with no cofinal branch.

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.

This paper, a continuation of the series [22, 24], presents two methods for establishing the finite model property (FMP, for short) of normal modal logics containing K4. The methods are oriented mainly to logics represented by their canonical axioms and yield for such axiomatizations several sufficient conditions of FMP. We use them to obtain solutions to two well known open FMP problems. Namely, we prove that

• every normal extension of K4 with modal reduction principles has FMP and

• every normal extension of S4 with a formula of one variable has FMP.

These results are interesting not only from the technical point of view. Actually, they reveal important properties of a quite natural family of modal logics—formulas of one variable and, in particular, modal reduction principles are typical axioms in modal logic. Unfortunately, the technical apparatus developed in this paper is applicable only to logics with transitive frames, and the situation with FMP of extensions of K by modal reduction principles, even by axioms of the form □np → □mp still remains unclear. I think at present this is one of the major challenges in completeness theory.

The language of the canonical formulas, introduced in [22] (I'll refer to that paper as Part I), is a way of describing the “geometry and topology” of formulas' refutation (general) frames by means of some finite refutation patterns.

We propose a probabilistic interpretation of Propositional Dynamic Logic (PDL). We show that logical and behavioral equivalence are equivalent over general measurable spaces. This is done first for the fragment of straight line programs and then extended to cater for the nondeterministic nature of choice and iteration, expanded to PDL as a whole. Bisimilarity is also discussed and shown to be equivalent to logical and behavioral equivalence, provided the base spaces are Polish spaces. We adapt techniques from coalgebraic stochastic logic and point out some connections to Souslin's operation from descriptive set theory. This leads to a discussion of complete stochastic Kripke models and model completion, which permits an adequate treatment of the test operator.

Any logical system, if its use is to be carried beyond a rather elementary stage, needs powerful conventions about abbreviations: in particular one usually wants to modify the bracketing so as to make the formulae more readable, and also possibly shorter. The present note has been written in the belief that Church's formulation of the simple theory of types is particularly suitable as a basis for work on that theory, and that it is therefore worth while introducing special conventions which take into account the needs of this particular system. The conventions which I shall describe are ones which I have used a good deal myself, and have always found adequate. I intend to make use of them in forthcoming papers. They may be regarded as an extension of Curry's conventions.

I shall begin with a general discussion of punctuation by means of groups of dots. This general theory is applicable, with some modifications, to Russell's, Quine's, and Curry's bracketing systems as well as to the present one.

Since the discovery of forcing in the early sixties, it has been clear that many natural and interesting mathematical questions are not decidable from the classical axioms of set theory, ZFC. Therefore some mathematicians have been studying the consequences of stronger set theoretic assumptions. Two new types of axioms that have been the subject of much research are large cardinal axioms and axioms asserting the determinacy of definable games. The two appear at first glance to be unrelated; one of the most surprising discoveries of recent research is that this is not the case.

In this paper we will be assuming the axiom of determinacy (AD) plus the axiom of dependent choice (DC). AD is false, since it contradicts the axiom of choice. However every set in L[R] is ordinal definable from a real. Our axiom that definable games are determined implies that every game in L[R] is determined (in V), and since a strategy is a real, it is determined in L[R]. That is, L[R] ⊨ AD. The axiom of choice implies L[R] ⊨ DC. So by embedding ourselves in L[R], we can assume AD + DC and begin proving theorems. These theorems true in L[R] imply corresponding theorems in V, by e.g. changing “every set” to “every set in L[R]”. For more information on AD as an axiom, and on some of the points touched on here, the reader should consult [14], particularly §§7D and 8I. In this paper L[R] will no longer even be mentioned. We just assume AD for the rest of the paper.

In this note it is shown that in explicit mathematics the strong power type axiom is inconsistent with (uniform) elementary comprehension and discuss some general aspects of power types in explicit mathematics.

Originally generalized quantifiers were introduced to specify that a given formula was true for “many x's” e.g. ⊨ Qxφ(x) iff card{x ∈ ∣∣ ∣ ⊨ φ[x]} ≥ ℵ0, ℵ1, or some fixed cardinal κ. In this paper we formalize the notion that φ{x) is true “for almost all x”. This is accomplished by referring to structures = (′, μ) where ′ is a first-order structure and μ is a measure of a suitable type on the universe of ′. We will prove that the language Lμ obtained from first-order logic by adjoining a quantifier Qμ, which ranges over the measure μ, is fully compact if we assume the existence of a proper class of measurable cardinals. As a corollary to the compactness theorem we obtain the recursive enumerability of the validities of Lμ. Finally, the Magidor-Malitz quantifiers Qkn (n ∈ ω) will be added to Lμ together with analogous quantifiers Qμm (m ∈ ω) to form Lκμ<ω,<ω, which is compact for sets of sentences of cardinality < κ, where κ is a measurable cardinal > ℵ0.

An alternate approach to formalizing “for almost all” has been recently developed by Barwise, Kaufmann and Makkai [1] who follow a suggestion of Shelah [5].

This paper is the first of several works: the matter is the systematic rewriting of usual results of ordinal notations, using Π½-logic. The purpose of these articles is already realized in Π½-logic, in a relatively abstract form; also, they are examples for Π½-logic. The first and second articles in this series are complete versions of unpublished results that one of authors had announced in 1976.

Veblen introduced his hierarchy in 1908. The hierarchy has since been widely used in proof theory; in fact, what is actually needed is the more natural hierarchy: , with (not necessarily a Cantor normal form) and K the Veblen hierarchy.

We shall show:

i) φ is in fact a two-variables functor (denoted by V in the text) commuting with direct limits and with pull-backs.

ii) The property of commutation with pull-backs permits one to give a representation of each ordinal x < φα(0) by means of a finite sequence of ordinals < α. This representation is independent of α it is ⊆ x, and can be used in the building up of notations systems. This representation is the “blowing-up” of the Cantor normal form, and it corresponds exactly to the denotation of ordinals < φα(0) by means of the functions (φβ)β<α.