In this paper we investigate towers of normal filters. These towers were first used by Woodin (see [15]). Woodin proved that if δ is a Woodin cardinal and P is the full stationary tower up to δ (P<δ) or the countable version (Q<δ), then the generic ultrapower is closed under < δ sequences (so the generic ultrapower is well-founded) ([14]). We show that if ℙ is a tower of height δ, δ supercompact, and the filters generating ℙ are the club filter restricted to a stationary set, then the generic ultrapower is well-founded (ℙ is precipitous). We also give some examples of non-precipitous towers. We also show that every normal filter can be extended to a V-ultrafilter with well-founded ultrapower in some generic extension of V (assuming large cardinals). Similarly for any tower of inaccessible height. This is accomplished by showing that there is a stationary set that projects to the filter or the tower and then forcing with P<δ below this stationary set.

An important idea in our proof of precipitousness (Theorem 6.4) has the following form in Woodin's proof. If are maximal antichains (i Є ω and δ Woodin) then there is a κ < δ such that each Ai ∩ Vκ is semiproper, i.e.,

contains a club (relative to ∣ a∣ < κ).

Shoenfield [8] has shown that a hierarchy for the functions recursive in a type-2 object can be set up whenever E2 (the type-2 object that introduces numerical quantification) is recursive in that type-2 object. With a restriction that we will discuss in the next paragraph, Moschovakis [4, pp. 254–259] has solved the analogous problem for type-3 objects. His method seems to generalize for any type-n object, where n ≥ 2. We will solve this same problem of finding hierarchies based on type-n objects by a different method. Instead of using ordinal notations for indexing stages of hierarchies, as do Shoenfield and Moschovakis, we will define notation-independent stages.

Lachlan's nondiamond theorem [7, Theorem 5] asserts that there is no embedding of the four-element Boolean algebra (diamond) in the recursively enumerable degrees which preserves infima, suprema, and least and greatest elements. Lachlan observed that, essentially by relativization, the theorem can be extended to

Using the Sacks splitting theorem he concluded that there exists a pair of r.e. degrees which does not have an infimum, thus showing that the r.e. degrees do not form a lattice.

We will first prove the following extension of (1):

where an r.e. degree a is non-b-cappable if . From (2) we obtain more information about pairs of r.e. degrees without infima: For every nonzero low r.e. degree there exists an incomparable one such that the two degrees do not have an infimum and there is an r.e. degree which is not half of a pair of incomparable r.e. degrees which has an infimum in the low r.e. degrees. Probably the most interesting corollary of (2) is that the join of any cappable r.e. degree (i.e. half of a minimal pair) and any low r.e. degree is incomplete. Consequently there is an incomplete noncappable degree above every incomplete r.e. degree. Cooper's result [3] that ascending sequences of uniformly r.e. degrees can have minimal upper bounds in the set R of r.e. degrees is another corollary of (2).

We develop a Sylow theory for stable groups satisfying certain additional conditions (2- finiteness, solvability or smallness) and show that their maximal p-subgroups are locally finite and conjugate. Furthermore, we generalize a theorem of Baer-Suzuki on subgroups generated by a conjugacy class of p-elements.

In a previous paper—[17]—we characterized strong measure zero sets of reals in terms of a Ramseyan partition relation on certain subspaces of the Alexandroff duplicate of the unit interval. This framework gave only indirect access to the relevant sets of real numbers. We now work more directly with the sets in question, and since it costs little in additional technicalities, we consider the more general context of metric spaces and prove:

1. If a metric space has a covering property of Hurewicz and has strong measure zero, then its product with any strong measure zero metric space is a strong measure zero metric space (Theorem 1 and Lemma 3).

2. A subspace X of a σ-compact metric space Y has strong measure zero if, and only if, a certain Ramseyan partition relation holds for Y (Theorem 9).

3. A subspace X of a σ-compact metric space Y has strong measure zero in all finite powers if, and only if, a certain Ramseyan partition relation holds for Y (Theorem 12).

Then 2 and 3 yield characterizations of strong measure zeroness for σ-totally bounded metric spaces in terms of Ramseyan theorems.

It is well known that negation can be defined by postulating a fixed proposition F and specifying that

where “≡” indicates identity by definition. I propose to discuss this way of introducing negation in relation to the inferential systems of my Notre Dame lectures of 1948. Acquaintance with these lectures is presupposed; they will be referred to as TFD. The definition (1) was used there, essentially, in connection with the T-systems; but it was not used in connection with the L-systems because of a certain difficulty which I was not able to overcome at that time. This paper contains proofs of results concerning L-systems which have been announced elsewhere.

This paper shows that the interpolation theorem fails in the intuitionistic logic of constant domains. This result refutes two previously published claims that the interpolation property holds.

If F is a field, and α is an element of F, we say that α is arithmetically definable in F if there is a formula containing one free variable and any number of bound variables, involving only the concepts of elementary logic and the operations of addition and multiplication, which is satisfied by α and by no other element of F. The range of the bound variables is understood to be F. Without changing the sense of the above definition, we can allow in our formulas symbols for specific integers, or even (if F has characteristic zero) symbols for specific rational numbers, since these are arithmetically definable.

As an example, consider the field F = R(2¼), obtained by adjoining the positive fourth root of 2 to the field R of rationals. Notice that 2¼ is not defined arithmetically by the formula x2 = 2, since this equation has two roots in F.

However, 2¼ may be defined arithmetically by the equivalence

where we have used the logical symbols ↔ (if and only if), ∨ (there exists), and ∧ (and). For the equation y4 = 2 is satisfied by no elements of F except y = ±2¼, and in both cases y2 = 2¼. On the other hand, 2¼ is not arithmetically definable in F, since there is an automorphism of F which takes 2¼ into −2¼, so that every arithmetical condition satisfied by 2¼ is also satisfied by −2¼.

In any field F, a necessary condition for the arithmetical definability of an element α is that α should be fixed for all automorphisms of F. That this condition is not always sufficient is shown by considering the field of real numbers. Here there is no automorphism but the identity, but there can of course be but a denumerable infinity of arithmetically definable real numbers. Tarski has shown that only the algebraic numbers are arithmetically definable.

In this article we study the systems KF and VF of truth over set theory as well as related systems and compare them with the corresponding systems over arithmetic.

The main point of this paper is a further development of some aspects of the recent theory of recursively enumerable (r.e.) algebraic structures. Initial work in this area is due to Frölich and Shepherdson [4] and Rabin [10]. Here we are only concerned with vector space structure. The previous work on r.e. vector spaces is due to Dekker [2], [3], Metakides and Nerode [8], Remmel [11], Retzlaff [13], and the author [5].

Our object of study is V∞ a countably infinite dimensional fully effective vector space over a countable recursive field . By fully effective we mean that V∞. under a fixed Godel numbering has the following properties:

(i) Operations of vector addition and scalar multiplication on V∞ are presented by partial recursive functions on the Gödel numbers of elements of V∞.

(ii) V∞ has a dependence algorithm, i.e., there is a uniform effective procedure which applied to any n vectors of V∞ determines whether or not they are linearly independent.

We also study , the lattice of r.e. subspaces of V∞ (under the operations of intersection, ⋂ and (weak) sum, +). We note that if is not distributive and is merely modular (see [1]). This fact indicates the essential difference between the lattice of r.e. sets and .

We investigate the property of strict coherence in the setting of many-valued logics. Our main results read as follows: (i) a map from an MV-algebra to [0,1] is strictly coherent if and only if it satisfies Carnap’s regularity condition, and (ii) a [0,1]-valued book on a finite set of many-valued events is strictly coherent if and only if it extends to a faithful state of an MV-algebra that contains them. Remarkably this latter result allows us to relax the rather demanding conditions for the Shimony-Kemeny characterisation of strict coherence put forward in the mid 1950s in this Journal.

We consider ${\cal S}$, the class of finite semilattices; ${\cal T}$, the class of finite treeable semilattices; and ${{\cal T}_m}$, the subclass of ${\cal T}$ which contains trees with branching bounded by m. We prove that ${\cal E}{\cal S}$, the class of finite lattices with linear extensions, is a Ramsey class. We calculate Ramsey degrees for structures in ${\cal S}$, ${\cal T}$, and ${{\cal T}_m}$. In addition to this we give a topological interpretation of our results and we apply our result to canonization of linear orderings on finite semilattices. In particular, we give an example of a Fraïssé class ${\cal K}$ which is not a Hrushovski class, and for which the automorphism group of the Fraïssé limit of ${\cal K}$ is not extremely amenable (with the infinite universal minimal flow) but is uniquely ergodic.

This article reports that some robustness of the notions of predicativity and of autonomous progression is broken down if as the given infinite total entity we choose some mathematical entities other than the traditional ω. Namely, the equivalence between normal transfinite recursion scheme and new dependent transfinite recursion scheme, which does hold in the context of subsystems of second order number theory, does not hold in the context of subsystems of second order set theory where the universe V of sets is treated as the given totality (nor in the contexts of those of n+3-th order number or set theories, where the class of all n+2-th order objects is treated as the given totality).

A first-order sentence Φ is Σ2 if there is a quantifier-free formula Θ such that Φ has the form . The Σ2-theory of a structure for a language ℒis the set of Σ2-sentences of ℒ true in . It was shown independently by Lerman and Shore (see [Le, Theorem VII.4.4]) that the Σ2-theory of the structure = 〈D, ≤ 〉 is decidable, where D is the set of degrees of unsolvability and ≤ is the standard ordering of D. This result is optimal in the sense that the Σ3-theory of is undecidable, a result due to J. Schmerl. (For a proof, see [Le, Theorem VII.4.5]. As Lerman has pointed out, this proof should be corrected by defining θσ to be ∀xσ1(x) rather than ∀x(ψ(x)→ σ1(x)).) Nonetheless, in this paper we extend the decidability result of Lerman and Shore by showing that the Σ2-theory of is decidable, where ⋃ is the least upper bound operator and 0 is the least degree. Of course ⋃ is definable in , but many interesting degree-theoretic results are expressible as Σ2-sentences in the language of ∪ but not as Σ2-sentences in the language of . For instance, Simpson observed that the Posner-Robinson cupping theorem could be used to show that for any nonzero degrees a, b, there is a degree g such that b ≤ a ⋃ g, and b ⋠ g (see [PR, Corollary 6]). However, the Posner-Robinson technique does not seem to suffice to decide the Σ2-theory of ∪. We introduce instead a new method for coding a set into the join of two other sets and use it to decide this theory.

There is an analogy between concepts such as end-extension types and minimal types in the model theory of Peano arithmetic and concepts such as P-points and selective ultrafilters in the theory of ultrafilters on N. Using the notion of conservative extensions of models, we prove some theorems clarifying the relation between these pairs of analogous concepts. We also use the analogy to obtain some model-theoretic results with techniques originally used in ultrafilter theory. These results assert that every countable nonstandard model of arithmetic has a bounded minimal extension and that some types in arithmetic are not 2-isolated.

Sets of postulates for at least three different combinatory logics have been given ([2], [3], [4], [5], [6], [7]). The logics and their sets of postulates are quite similar. In all cases it is the proof of the completeness of the set of postulates which causes the difficulty and makes the main papers so long ([3], [7]). It is the purpose of this paper to present a method of writing down sets of postulates for combinatory logics for which the proof of completeness will be fairly simple. We assume acquaintance with certain descriptive portions of [1], namely sections 1–6, 12, 13, 15. Otherwise the present paper is self-contained.

We first solve our problem for the particular logic studied by Rosser ([7]) and then indicate how the method would apply to other logics.

We start with a set, s, of primitive terms. We define s-combination as in [1], p. 43. The precise contents of s need not concern us. It suffices that there be s-combinations I, J, and Q, with no variables in them, and having properties as described below. I and J are to have the same meaning as in [1], p. 43, namely IA is the same as A and JABCD is the same as AB(ADC). QAB is to have the meaning that A and B, considered as functions, are the same.

Theorem 1. (◊ℵ1,) If B is an infinite Boolean algebra (BA), then there is B1, such that ∣ Aut (B1) ≤∣B1∣ = ℵ1 and 〈B1, Aut (B1)〉 ≡ 〈B, Aut(B)〉.

Theorem 2. (◊ℵ1) There is a countably compact logic stronger than first-order logic even on finite models.

This partially answers a question of H. Friedman. These theorems appear in §§1 and 2.

Theorem 3. (a) (◊ℵ1) If B is an atomic ℵ-saturated infinite BA, Ψ Є Lω1ω and 〈B, Aut (B)〉 ⊨Ψ then there is B1, Such that ∣Aut(B1)∣ ≤ ∣B1∣ =ℵ1, and 〈B1, Aut(B1)〉⊨Ψ. In particular if B is 1-homogeneous so is B1. (b) (a) holds for B = P(ω) even if we assume only CH.

Gentzen's sequential system LJ of intuitionistic logic has two symbols of implication. One is the logical symbol → and the other is the metalogical symbol ⇒ in sequents

Considering the logical system LJ as a mathematical object, we understand that the logical symbols ∧, ∨, →, ¬, ∀, ∃ are operators on formulas, and ⇒ is a relation. That is, φ ⇒ Ψ is a metalogical sentence which is true or false, on the understanding that our metalogic is a classical logic. In other words, we discuss the logical system LJ in the classical set theory ZFC, in which φ ⇒ Ψ is a sentence.

The aim of this paper is to formulate an intuitionistic set theory together with its metatheory. In Takeuti and Titani [6], we formulated an intuitionistic set theory together with its metatheory based on intuitionistic logic. In this paper we postulate that the metatheory is based on classical logic.

Let Ω be a cHa. Ω can be a truth value set of a model of LJ. Then the logical symbols ∧, ∨, →, ¬, ∀x, ∃x are interpreted as operators on Ω, and the sentence φ ⇒ Ψ is interpreted as 1 (true) or 0 (false). This means that the metalogical symbol ⇒ also can be expressed as a logical operators such that φ ⇒ Ψ is interpreted as 1 or 0.

In an earlier article, I proposed a way of determining the relative simplicity of different sets of extralogical primitives. The calculations assumed a fully platonistic logic, committed to an indefinite hierarchy of classes, with sequences and relations defined as classes. Recently it has been shown that a nominalistic logic, countenancing no entities other than individuals, can be made to serve many of the purposes for which a platonistic logic had been thought necessary. The question naturally arises how we are to determine the simplicity of extralogical bases of systems founded upon a nominalistic logic. In such bases, the only extralogical predicates will be predicates (of one or more places) of individuals. The present paper offers a general method of measuring the simplicity of such bases.

Gödel's Second Incompleteness Theorem states axiom systems of sufficient strength are unable to verify their own consistency. We will show that axiomatizations for a computer's floating point arithmetic can recognize their cut-free consistency in a stronger respect than is feasible under integer arithmetics. This paper will include both new generalizations of the Second Incompleteness Theorem and techniques for evading it.