Every system of signs that is defined in logical syntax may be called a formal language. It need not always be a language in the ordinary sense of the word. The rules of chess, e.g., can be expressed in the terminology of the syntax, but it would not occur to anybody to call chess a language.

A language in the ordinary sense has a meaning. That is to say that certain words in it are names of things or states or properties or relationships. In general it can be said that in any language having meaning all words subject to the rule of types are names. (Even sentences might be called names, i.e. names of facts, but we will not go so far.)

A syntax of a language L is a language with meaning, for the words of a definite type (in this paper of the type of individuals) contained in it are names of expressions of L.

If to a language we add its syntax, we get a language containing the syntax of one of its parts. If we formulate the syntax of a language L, in so far as its means allow, in the language L itself, we get a language containing a part of its syntax. We call such languages autosyntactic. It is well known that languages containing the whole of their own syntax do not exist.

Let λ denote a singular cardinal. Zeman, improving a previous result of Shelah, proved that together with 2λ = λ+ implies ⋄S for every S ⊆ λ+ that reflects stationarily often.

In this paper, for a set S ⊆ λ+, a normal subideal of the weak approachability ideal is introduced, and denoted by I[S; λ]. We say that the ideal is fat if it contains a stationary set. It is proved:

1. if I[S; λ] is fat, then NSλ + ∣ S is non-saturated;

2. if I[S; λ] is fat and 2λ = λ+, then ⋄S holds;

3. implies that I[S; λ] is fat for every S ⊆ λ+ that reflects stationarily often;

4. it is relatively consistent with the existence of a supercompact cardinal that fails, while I[S; λ] is fat for every stationary S ⊆ λ+ that reflects stationarily often.

The stronger principle is studied as well.

Large cardinal properties divide rather strikingly into two groups. “Small” large cardinal properties such as weak compactness always relativize to L, while in contrast “large” large cardinal properties such as Ramsey are incompatible with L. These properties seem to be similar otherwise and this sense of similarity is reinforced by the fact that many of the large cardinals do exist in the L-like model L(μ). This paper will show that the division is caused by an artificially restrictive class of “constructible” sets rather than an essential difference in the properties themselves. Specifically, we consider the class K of sets constructible from mice as defined by Dodd and Jensen [3] and prove

Theorem 1. If ρ is Ramsey then ρ is Ramsey in K.

A modification of the proof will show

Theorem 2. If ρ is Jonson, then ρ is Ramsey in K.

Since Ramsey implies Jonson this shows that the notions are equiconsistent. Theorem 2 was proved by Kunen [5] under the assumption that V = L(μ).

The proof of Theorems 1 and 2 depends heavily on results of Dodd and Jensen [3] about K and mice. These results are stated without proof in §2. §2 also contains elementary (to a reader familiar with the theory of iterated ultrapowers) proofs of special cases of some of these lemmas sufficient to give a self contained proof of the following corollary of Theorem 1:

Corollary. If ρ ≤ κ,ρ is Ramsey and L(μ) ⊨ μ is a measure on κ then L(μ) ⊨ ρ is Ramsey.

In this paper, we shall prove two theorems involving the construction of core models with infinitely many Woodin cardinals. We assume familiarity with [12], which develops core model theory the one Woodin level, and with [10] and [6], which extend the fine structure theory of [5] to mice having many Woodin cardinals. The most important new problem of a general nature which we must face here concerns the iterability of Kc with respect to uncountable iteration trees.

Our first result is the following theorem, a slightly stronger version of which was proved independently and earlier by Woodin. The theorem settles positively a conjecture of Feng, Magidor, and Woodin [2].

Theorem. Let Ω be measurable. Then the following are equivalent:

(a) for all posets,

(b) for every poset,

(c) for every poset ℙ ∈ VΩ, Vℙ ⊨ there is no uncountable sequence of distinct reals in L(ℝ)

(d) there is an Ω-iterable premouse of height Ω which satisfies “there are infinitely many Woodin cardinals”.

It is an immediate corollary that if every set of reals in L(ℝ) is weakly homogeneous, then ADL(ℝ) holds. We shall also indicate some extensions of the theorem to pointclasses beyond L(ℝ), and mice with more than ω Woodin cardinals.

The study of pseudo-algebraically closed fields (henceforth called PAC) started with the work of J. Ax on finite and pseudo-finite fields [1]. He showed that the infinite models of the theory of finite fields are exactly the perfect PAC fields with absolute Galois group isomorphic to , and gave elementary invariants for their first order theory, thereby proving the decidability of the theory of finite fields. Ax's results were then extended to a larger class of PAC fields by M. Jarden and U. Kiehne [21], and Jarden [19]. The final word on theories of PAC fields was given by G. Cherlin, L. van den Dries and A. Macintyre [10], see also results by Ju. Ershov [13], [14]. Let K be a PAC field. Then the elementary theory of K is entirely determined by the following data:

• The isomorphism type of the field of absolute numbers of K (the subfield of K of elements algebraic over the prime field).

• The degree of imperfection of K.

• The first-order theory, in a suitable ω-sorted language, of the inverse system of Galois groups al(L/K) where L runs over all finite Galois extensions of K.

They also showed that the theory of PAC fields is undecidable, by showing that any graph can be encoded in the absolute Galois group of some PAC field. It turns out that the absolute Galois group controls much of the behaviour of the PAC fields. I will give below some examples illustrating this phenomenon.

We prove that in the Solovay model, every OD equivalence relation, Ε, over the reals, either admits an OD reduction to the equality relation on the set of all countable (of length < ω1) binary sequences, or continuously embeds Ε0, the Vitali equivalence.

If Ε is a (resp. ) relation then the reduction above can be chosen in the class of all Δ1 (resp. Δ2) functions.

The proofs are based on a topology generated by OD sets.

An effective translation of the fact that any infinite ordered set contains an infinite ascending or descending sequence is that any infinite recursive set A ⊆ Q has a recursive subset with order type ω or ω*. Tennenbaum's theorem states that this translation is false, and there is a counterexample A with order type ω + ω*. Tennenbaum suggested that this counterexample is an infinite recursive linearly ordered set which is effectively finite, and that the collection of all such counterexamples could provide a concrete model of nonstandard arithmetic. The purpose of this paper is to determine the collection of order types for which there is a counterexample.

It is readily seen that any counterexample to the effective translation must have order type ω + Z · α + ω* for some α [2], [3]. Let be the collection of order types α for which there is a counterexample. As a test case, we have previously shown that contains the constructive scattered orderings [3], [4]. In this paper we determine exactly which order types are in . We easily show that if ω+ Z · α + ω* is recursive, then α is . The main result is that . Consequently, .

In the last years several research projects have been motivated by the problem of constructing the usual geometrical spaces by admitting “regions” and “inclusion” between regions as primitives and by defining the points as suitable sequences or classes of regions (for references see [2]).

In this paper we propose and examine a system of axioms for the pointless space theory in which “regions”, “inclusion”, “distance” and “diameter” are assumed as primitives and the concept of point is derived. Such a system extends a system proposed by K. Weihrauch and U. Schreiber in [5].

In the sequel R and N denote the set of real numbers and the set of natural numbers, and E is a Euclidean metric space. Moreover, if X is a subset of R, then ⋁X is the least upper bound and ⋀X the greatest lower bound of X.

The problem of characterizing the finite lattices which can be embedded into the recursively enumerable degrees has a long history, which is summarized in [AL]. This problem is an important one, as its solution is necessary if a decision procedure for the ∀∃-theory of the poset of recursively emumerable degrees is to be found. A recursive nonembeddability condition, NEC, which subsumes all known nonembeddability conditions was presented in [AL]. This paper focuses on embeddability. An embeddability condition, EC, is introduced, and we prove that every finite lattice having EC can be embedded (as a lattice) into . EC subsumes all known embeddability conditions.

EC is a Π3 condition which states that certain obstructions to proving embeddability do not exist. It seems likely that the recursive labeled trees used in EC can be replaced with trees which are effectively generated from uniformly defined finite trees, in which case EC would be equivalent to a recursive condition. We do not know whether EC and NEC are complementary. This problem seems to be combinatorial, rather than recursion-theoretic in nature. Our efforts to find a finite lattice satisfying neither EC nor NEC have, to this point, been unsuccessful. It is the second author's conjecture that the techniques for proving embeddability which are used in this paper cannot be refined very much to obtain new embeddability results.

EC is introduced in §2, and the various conditions and definitions are motivated by presenting examples of embeddable lattices and indicating how the embedding proof works in those particular cases. The embedding construction is presented in §3, and the proof in §4.

In [MP] Marker and Pillay showed that if X ⊂ Cn is constructible but (C, +, X) is not locally modular, then multiplication is definable in the structure (C, +,X). That result extended earlier results of Martin [M] and Rabinovich and Zil'ber [RZ]. Here we will examine additive reducts of R and Qp.

Definition. A subset X of Rn is called semialgebraic if it is definable in the structure (R, +,·). A subset X of Rn is called semilinear if it is definable in the structure (R, +, <,λr)r∈b, where λr is the function x ↦ rx [scalar multiplication by r].

Every semilinear set is a Boolean combination of sets of the form {: p () = 0} and {: q() > 0}, where p() and q() are linear polynomials.

Van den Dries asked the following question: if X is semialgebraic but not semilinear, can we define multiplication in (R, +, <,X)? This was answered negatively by Pillay, Scowcroft and Steinhorn.

Theorem 1.1 [PSS]. Suppose X ⊂ Rnis semialgebraic and X ⊂ Infor some bounded interval I. Then multiplication is not definable in (R, +, <,X,λr)r∈R.

In particular if X = · ∣ [0, l ]2, the graph of multiplication restricted to the unit interval, then X is not semilinear so we have a negative answer to van den Dries' question. Peterzil showed that this is the only restriction.

We prove some restrictions on the possible cofinalities of ultrapowers of the natural numbers with respect to ultrafilters on the natural numbers. The restrictions involve three cardinal characteristics of the continuum, the splitting number s, the unsplitting number r, and the groupwise density number g. We also prove some related results for reduced powers with respect to filters other than ultrafilters.

For Gentzen's natural deduction, a formalized method of deduction in quantification theory dating from 1934, these important advantages may be claimed: it corresponds more closely than other methods of formalized quantification theory to habitual unformalized modes of reasoning, and it consequently tends to minimize the false moves involved in seeking to construct proofs. The object of this paper is to present and justify a simplification of Gentzen's method, to the end of enhancing the advantages just claimed. No acquaintance with Gentzen's work will be presupposed.

A further advantage of Gentzen's method, also somewhat enhanced in my revision of the method, is relative brevity of proofs. In the more usual systematizations of quantification theory, theorems are derived from axiom schemata by proofs which, if rendered in full, would quickly run to unwieldy lengths. Consequently an abbreviative expedient is usually adopted which consists in preserving and numbering theorems for reference in proofs of subsequent theorems. Further brevity is commonly gained by establishing metatheorems, or derived rules, for reference in proving subsequent theorems. In natural deduction, on the other hand, proofs tend to be so short that the abbreviative expedients just now mentioned may conveniently be dispensed with—at least until theorems of extraordinary complexity are embarked upon. In natural deduction accordingly it is customary to start each argument from scratch, without benefit of accumulated theorems or derived rules.

Recently, Lincoln, Scedrov and Shankar showed that the multiplicative fragment of second order intuitionistic linear logic is undecidable, using an encoding of second order intuitionistic logic. Their argument applies to the multiplicative-additive fragment, but it does not work in the classical case, because second order classical logic is decidable. Here we show that the multiplicative-additive fragment of second order classical linear logic is also undecidable, using an encoding of two-counter machines originally due to Kanovich. The faithfulness of this encoding is proved by means of the phase semantics.

We investigate ideals of the form {A ⊆ ω: Σn∈Axn is unconditionally convergent} where (xn)n∈ω is a sequence in a Polish group or in a Banach space. If an ideal on ω can be seen in this form for some sequence in X, then we say that it is representable in X.

After numerous examples we show the following theorems: (1) An ideal is representable in a Polish Abelian group iff it is an analytic P-ideal. (2) An ideal is representable in a Banach space iff it is a nonpathological analytic P-ideal.

We focus on the family of ideals representable in c0. We characterize this property via the defining sequence of measures. We prove that the trace of the null ideal, Farah’s ideal, and Tsirelson ideals are not representable in c0, and that a tall Fσ P-ideal is representable in c0 iff it is a summable ideal. Also, we provide an example of a peculiar ideal which is representable in ℓ1 but not in ℝ.

Finally, we summarize some open problems of this topic.

A subset X of a structure S is called free in S if ∀x ∈ Xx ∉ S[X − {x}]; here, S[Y] is the substructure of S generated from Y by the functions of S. For κ, λ, μ cardinals, let Frμ(κ, λ) be the assertion:

We show that Frω(ωω, ω), the free-subset property for ωω, is equiconsistent with the existence of a measurable cardinal (2.2,4.4). This answers a question of Devlin [De].

In the first section of this paper we prove some combinatorial facts about Frμ(κ, λ); in particular the first cardinal κ such that Frω(κ, ω) is weakly inaccessible or of cofinality ω (1.2). The second section shows that, under Frω(ωω, ω), ωω is measurable in an inner model. For the convenience of readers not acquainted with the core model κ, we first deduce the existence of 0# (2.1) using the inner model L. Then we adapt the proof to the core model and obtain that ωω is measurable in an inner model. For the reverse direction, we essentially apply a construction of Shelah [Sh] who forced Frω(ωω, ω) over a ground model which contains an ω-sequence of measurable cardinals. We show in §4 that indeed a coherent sequence of Ramsey cardinals suffices. In §3 we obtain such a sequence as an endsegment of a Prikry sequence.

This paper investigates the algebraic structure of the Medvedev lattice . We prove that is not a Heyting algebra. We point out some relations between and the Dyment lattice and the Mučnik lattice. Some properties of the degrees of enumerability are considered. We give also a result on embedding countable distributive lattices in the Medvedev lattice.

In a paper on combinatorial properties and large cardinals [2], Jech extended several combinatorial properties of a cardinal κ to analogous properties of the set of all subsets of λ of cardinality less than κ, denoted by “p κλ”, where λ is any cardinal ≤κ. We shall consider in this paper one of these properties which is historically rooted in a theorem of Ramsey [10] and in work of Rowbottom [12].

As in [2], define [p κλ]2 = {{x, y}: x, y ∈ p κλ and x ≠ y}. An unbounded subset A of p κλ is homogeneous for a function F: [p κλ]2 → 2 if there is a k < 2 so that for all x, y ∈ A with either x ⊊ y or y ⊊ x, F({x, y}) = k. A two-valued measure ü on p κλ is fine if it is κ-complete and if for all α < λ, ü({x ∈ p κλ: α ∈ x}) = 1, and ü is normal if, in addition, for every function f: p κλ → λsuch that ü({x ∈ p κλ: f(x) ∈ x}) = 1, there is an α < λ such that ü({x ∈ p κλ: f(x) = α}) = 1. Finally, a fine measure on p κλ has the partition property if every F: [p κλ]2 → 2 has a homogeneous set of measure one.

In a recent paper by Mostowski [1] we find an investigation of those formulas of quantification theory which are valid in all domains of individuals, including the empty domain. Mostowski gives a complete set of axioms for such a first order functional calculus (the system is called “”) and a comparison is made with a form of the usual calculus, Church's in [2]. It is pointed out that is much less elegant; in particular, the distributivity laws for quantifiers (e.g., (x){A . B) .{x)A . (x)B) do not hold in general, and likewise the rule of modus ponens does not preserve validity in all cases.

In this paper we show that a not inelegant system is obtained if one modifies Mostowski's approach in two respects; and once this is done a somewhat neater proof of completeness can be given.

The first respect in which we diverge from Mostowski is in the treatment of vacuous quantifiers. For him if p has no free x, then (x)p and (∃x)p are both to have the same value (interpretation) as p1. But this is not the only way to assign values to vacuous quantifications. For when universal quantification is viewed as a generalized conjunction, the formula (x)Fx has the significance of Fa . Fb…. for as many conjunctands as there are individuals in the domain, and if Fx should have the “constant” value p, then (x)p is to mean the conjunction of p with itself for as many times as there are individuals in the domain (compare the arithmetical ).

In recent work, Cooper [3, 1990] has extended results of Jockusch and Shore [6, 1984] to show that the Turing jump is definable in the structure given by the Turing degrees and the ordering of Turing reducibility. In his definition of x′ from x, Cooper identifies an order-theoretic property shared by all of the degrees that are recursively enumerable in x and above x. He then shows that x′ is the least upper bound of all the degrees with this property. Thus, the jump of x is identified by comparing the recursively enumerable degrees with other degrees which are not recursively enumerable. Of course, once the jump operator is known to be definable, the relation of jump equivalence x′ = y′ is also known to be a definable relation on x and y. If we consider how much of the global theory of the Turing degrees is sufficient for Cooper's methods, it is immediately clear that his methods can be implemented to show that the jump operator and its weakening to the relation of jump equivalence are definable in any ideal closed under the Turing jump. However, his methods do not localize to , the degrees, or to the recursively enumerable degrees.

This paper fits, as do Shore and Slaman [16, 1990] and [17, to appear], within the general project to develop an understanding of the relationship between the local degree-theoretic properties of a recursively enumerable set A and its jump class. For an analysis of the possibility of defining jump equivalence in , consult Shore [15, to appear] who shows that the relation x(3) = y(3) is definable. In this paper, we will restrict our attention to definitions expressed completely in ℛ (Note: All sets and degrees discussed for the remainder of this paper will be recursively enumerable.) Ultimately, one would like to find some degree-theoretic properties definable in terms of the ordering of Turing reducibility and quantifiers over the recursively enumerable degrees that would define the relation of jump equivalence or define one or more of the jump classes Hn = {w∣ wn = 0n+1} or Ln = {w ∣ wn = 0n}. Such a result could very likely then be used as a springboard to other general definability results for the recursively enumerable degrees. It would be especially interesting to know whether every recursively enumerable degree is definable and whether every arithmetical degree-invariant property of the recursively enumerable sets is definable in .