The theory of objects recursive in functions of higher types was developed originally by Kleene [Kl 1,2]. The sets of objects of finite types are defined by Kleene as follows:

T0 = ω = the set of nonnegative integers,

and, for all i ∈ ω,

Ti+1 = Tiω = the set of total functions from Ti to ω.

In order to study and classify the functions recursive in Kolmogorov's R-operator, it is necessary to discuss recursion in partial functions of higher types. Accordingly, we define the partial objects of higher finite types by

and, for all i ∈ ω,

= the set of partial functions from Ti to ω.

In addition to considering the partial functions from Ti to ω, the “hereditary partial” functions also have to be considered. For example, Hinman has studied objects of type 2 which act on partial functions from ω to ω. In case of dealing with a function F which has partial functions in its domain, we usually require that F be consistent, i.e. if F(f) is defined and g is an object of the same type as f, defined at least at all points where f is defined (in short, g extends f—notation: g ⊇ f), then F(g) is defined and is equal to F(f). Now we can define the higher type partial objects which are consistent by

and, for all i ∈ ω,

= the set of consistent partial functions from to ω.

In [2], Carlson and Simpson proved a dualized version of Ramsey's theorem obtained by coloring partitions of ω instead of subsets of ω. It was at the suggestion of Simpson that the author undertook to study the notion dual to that of a Ramsey ultrafilter. After stating the basic terminology and notation used in the paper in §1, in §2 we establish some basic properties of the lattice of all partitions of a cardinal κ. §3 is devoted to the study of families of pairwise disjoint partitions of ω. §4 is concerned with descending sequences of partitions. In §5, we give some examples of filters of partitions. Properties of such filters are discussed in §6. Co-Ramsey filters are introduced in §7, and it is shown how they can be associated with Ramsey ultrafilters. The main result of §8 is Proposition 8.1, which asserts the existence of a co-Ramsey filter under the continuum hypothesis.

We use standard set theoretic conventions and notation. Let κ be a cardinal. We set κ* = κ − {0}. For every ordinal α ≤ κ, (κ)α denotes the set of those sequences X(ν), ν < α, of pairwise disjoint nonempty subsets of κ such that ⋃ν<αX(ν) = κ, and ⋂X(ν) < ⋂X(ν′) whenever ν < ν′. We also let (κ)≤α = ⋃β≤α(κ)β and (κ)<α = ⋃β<α(κ)β. Given X ∈ (κ)α, we put xν = ⋂X(ν) for every ν < α, and we denote by Ax the set of all xν, 0 < ν < α.

The concept of "partition relation" has proven to be extremely important in the development of the theory of large cardinals. This is due in good part to the fact that the ordinal numbers which appear as parameters in partition relations provide a natural way to define a detailed hierarchy of the corresponding large cardinal axioms. In particular, the study of cardinals satisfying Ramsey-Erdös-style partition relations has yielded a great number of very interesting large cardinal axioms which lie in strength strictly between inaccessibility and measurability. It is the purpose of this paper to show that this phenomenon does not occur if we use infinite exponent partition relations; no such partition relation has consistency strength strictly between inaccessibility and measurability. We also give a complete determination of which infinite exponent partition relations hold, assuming that there is no inner model of set theory with a measurable cardinal.

Our notation is standard. If F is a function and x is a set, then F″x denotes the range of F on x. If X is a set of ordinals and α is an ordinal, then [X]α is the collection of all subsets of X of order type α. We identify a member of [X]α with a strictly increasing function from α to X. If p ∈ [X]α and q ∈ [α]β, then the composition of p with q, which we denote pq, is a member of [X]β.

It has been considered desirable by many set theorists to find maximality properties which state that the universe has in some sense “many sets”. The properties isolated thus far have tended to be consistent with each other (as far as we know). For example it is a widely held view that the existence of a supercompact cardinal is consistent with the axiom of determinacy holding in L(R). This consistency has been held to be evidence for the truth of these properties. It is with this in mind that the first author suggested the following:

Maximality Principle If P is a partial ordering and G ⊆ P is a V-generic ultrafilter then either

• a) there is a real number r ∈ V [G] with r ∉ V, or

• b) there is an ordinal α such that α is a cardinal in V but not in V[G].

This maximality principle applied to garden variety partial orderings has startling results for the structure of V.

For example, if for some , then P = 〈{p: p ⊆ κ, ∣p∣ < κ}, ⊆〉 neither adds a real nor collapses a cardinal. Thus from the maximality principle we can deduce that the G. C. H. fails everywhere and there are no inaccessible cardinals. (Hence this principle contradicts large cardinals.) Similarly one can show that there are no Suslin trees on any cardinal κ. These consequences help justify the title “maximality principle”.

Since the maximality principle implies that the G. C. H. fails at strong singular limit cardinals it has consistency strength at least that of “many large cardinals”. (See [M].) On the other hand it is not known to be consistent, relative to any assumptions.

In this paper we consider various properties of Jensen's □ principles and use them to construct several examples concerning the so-called Novák number of partially ordered sets.

In §1 we give the relevant definitions and review some facts about □ principles. Apart from some simple observations most of the results in this section are known.

In §2 we consider the Novák number of partially ordered sets and, using □ principles, give counterexamples to the productivity of this cardinal function. We also formulate a principle, show by forcing that it is consistent and use it to construct an ℵ2-Suslin tree T such that forcing with T × T collapses ℵ1.

In §3 we briefly consider games played on partially ordered sets and relate them to the problems of the previous section. Using a version of □ we give an example of a proper partial order such that the game of length ω played on is undetermined.

In §4 we raise the question of whether the Novák number of a homogenous partial order can be singular, and show that in some cases the answer is no.

We assume familiarity with the basic techniques of forcing. In §1 some facts about large cardinals (e.g. weakly compact cardinals are -indescribable) and elementary properties of the constructible hierarchy are used. For this and all undefined terms we refer the reader to Jech [10].

We say that a first order theory T is locally finite if every finite part of T has a finite model. It is the purpose of this paper to construct in a uniform way for any consistent theory T a locally finite theory FIN(T) which is syntactically (in a sense) isomorphic to T.

Our construction draws upon the main idea of Paris and Harrington [6] (I have been influenced by some unpublished notes of Silver [7] on this subject) and generalizes the syntactic aspect of their result from arithmetic to arbitrary theories. (Our proof is syntactic, and it is simpler than the proofs of [5], [6] and [7]. This reminds me of the simple syntactic proofs of several variants of the Craig-Lyndon interpolation theorem, which seem more natural than the semantic proofs.)

The first mathematically strong locally finite theory, called FIN, was defined in [1] (see also [2]). Now we get much stronger ones, e.g. FIN(ZF).

From a physicalistic point of view the theorems of ZF and their FIN(ZF)-counterparts may have the same meaning. Therefore FIN(ZF) is a solution of Hilbert's second problem. It eliminates ideal (infinite) objects from the proofs of properties of concrete (finite) objects.

In [4] we will demonstrate that one can develop a direct finitistic intuition that FIN(ZF) is locally finite. We will also prove a variant of Gödel's second incompleteness theorem for the theory FIN and for all its primitively recursively axiomatizable consistent extensions.

The results of this paper were announced in [3].

Let L be a first order language containing a binary relation symbol <.

Definition. Suppose ℳ is an L-structure and < is a total ordering of the domain of ℳ. ℳ is ordered minimal (-minimal) if and only if any parametrically definable X ⊆ ℳ can be represented as a finite union of points and intervals with endpoints in ℳ.

In any ordered structure every finite union of points and intervals is definable. Thus the -minimal structures are the ones with no unnecessary definable sets. If T is a complete L-theory we say that T is strongly (-minimal if and only if every model of T is -minimal.

The theory of real closed fields is the canonical example of a strongly -minimal theory. Strongly -minimal theories were introduced (in a less general guise which we discuss in §6) by van den Dries in [1]. Extending van den Dries' work, Pillay and Steinhorn (see [3], [4] and [2]) developed an extensive structure theory for definable sets in strongly -minimal theories, generalizing the results for real closed fields. They also established several striking analogies between strongly -minimal theories and ω-stable theories (most notably the existence and uniqueness of prime models). In this paper we will examine the construction of models of strongly -minimal theories emphasizing the problems involved in realizing and omitting types. Among other things we will prove that the Hanf number for omitting types for a strongly -minimal theory T is at most (2∣T∣)+, and characterize the strongly -minimal theories with models order isomorphic to (R, <).

It is proved that for a variety of groups in which the relatively free groups are solvable, the relatively free groups of distinct finite rank are not elementarily equivalent.

In this paper a general method of proving the undecidability of a property P, for finite sets Σ of equations of a countable algebraic language, is presented. The method is subsequently applied to establish the undecidability of the following properties, in almost all nontrivial such languages:

1. 1. The first-order theory generated by the infinite models of Σ is complete.

2. 2. The first-order theory generated by the infinite models of Σ is model-complete.

3. 3. Σ has the joint-embedding property.

4. 4. The first-order theory generated by the models of Σ with more than one element has the joint-embedding property.

5. 5. The first-order theory generated by the infinite models of Σ has the joint-embedding property.

A countable algebraic language ℒ is a first-order language with equality, with countably many nonlogical symbols but without relation symbols, ℒ is trivial if it has at most one operation symbol, and this is of rank one. Otherwise, ℒ is nontrivial. An ℒ-equation is a sentence of the form , where φ and ψ are ℒ-terms. The set of ℒ-equations is denoted by Eqℒ. A set of sentences is said to have the joint-embedding property if any two models of it are embeddable in a third model of it.

If P is a property of sets of ℒ-equations, the decision problem of P for finite sets of ℒ-equations is the problem of the existence or not of an algorithm for deciding whether, given a finite Σ ⊂ Eqℒ, Σ has P or not.

A pair of r.e. sets A1, A2 are said to split an r.e. set A (written A1 Δ A2 = A) if A1 ∩ A2 = ∅ and A1 ∪ A2 = A. In the literature there are various results asserting certain splitting properties hold for all r.e. sets. For example Sacks' splitting theorem (cf. [So]) asserts that an r.e. nonrecursive set A may be split into a pair of Turing incomparable r.e. sets A1, A2, and Lachlan's splitting theorem [La5] asserts that A may be split into a pair of r.e. sets A1, A2 for which there exists an r.e. set B with B ⊕ A1, B ⊕ A2 <TA and with the infinum of the Turing degrees of B ⊕ A1 and B ⊕ A2 existing in the upper semilattice of r.e. degrees.

Two of the earliest observations establishing that splitting properties possessed by some r.e. sets are not possessed by others, are Lachlan's nondiamond theorem [La1] (and so, in particular, no complete r.e. set can be split nontrivially with degree theoretic inf 0) and the Yates-Lachlan construction of a minimal pair (a pair of nonzero r.e. degrees with inf 0). Other examples of this phenomenon, which are not obtained by interpreting degree theoretic results in the r.e. sets, are Lachlan's construction of nonmitotic r.e. sets [La2] (sets which cannot be split into a pair of r.e. sets of the same degree) and, later, Ladner's [Ld1, 2] and Ingrassia's [In] analysis of their degrees.

Let X be any infinite, coinfinite r.e. set. We show that the index set {e: We ≡1X) is -complete, answering a question posed by Odifreddi in [2].

wtt-reducibility has become of some importance in the last years through the works of Ladner and Sasso [1975], Stob [1983] and Ambos-Spies [1984]. It differs from Turing reducibility by a recursive bound on the use of the reduction. This makes some proofs easier in the wtt degrees than in the Turing degrees. Certain proofs carry over directly from the Turing to the wtt degrees, especially those based on permitting. But the converse is also possible. There are some r.e. Turing degrees which consist of a single r.e. wtt degree (the so-called contiguous degrees; see Ladner and Sasso [1975]). Thus it suffices to prove a result about contiguous wtt degrees using an easier construction, and it carries over to the corresponding Turing degrees.

In this work we prove some results on pairs of r.e. wtt degrees which have no infimum. The existence of such a pair has been shown by Ladner and Sasso. Here we use a different technique of Jockusch [1981] to prove this result (Theorem 1) together with some stronger ones. We show that a pair without infimum exists above a given incomplete wtt degree (Theorem 5) and below any promptly simple wtt degree (Theorem 12). In Theorem 17 we prove, however, that there are r.e. wtt degrees such that any pair below them has an infimum. This shows that certain initial segments of the wtt degrees are lattices. Thus there is a structural difference between the wtt and Turing degrees where the pairs without infimum are dense (Ambos-Spies [1984]).

We investigate the set S2 of “quickly sharped” reals:

in the manner of [K] defining a natural hierarchy and quasi-hierarchy of constructibility degrees and identifying their termination points.

This paper is a continuation of the authors' paper [7]; in particular, we give a sharper and more useful criterion for the approximate elementary equivalence of Cσ(K) spaces, where K is a totally disconnected compact Hausdorff space. (See Theorem 2 below.) As an application, we obtain a complete description of the Banach spaces X which are approximately equivalent to c0. Namely, X ≡ Ac0 iff X = Cσ(K) where K is a totally disconnected compact Hausdorff space which has a dense set of isolated points and σ is an involutory homeomorphism on K which has a unique fixed point t, and t is not an isolated point. (See Theorem 7.)

These results are derived from an analysis which we give of the elementary theories of structures (B, σ), where B is a Boolean algebra and σ is an involutory automorphism of B which leaves at most one nontrivial ultrafilter invariant. Let U(σ) denote this ultrafilter, if it exists; let U(σ) = B in case σ leaves no nontrivial ultrafilter invariant. We show that the elementary theory of (B, σ) is completely determined by the theory of (B, U(σ)) (and conversely, because U(σ) is definable in (B, σ)). This makes possible the use of the explicit invariants given by Éršov [4] for structures (B, U) where U is an ultrafilter on B. (These generalize the Tarski invariants for Boolean algebras [15].) We also use the Éršov invariants in the proof of our main result.

It was J. E. Baumgartner who in [1] proved that when a weakly compact cardinal is Lévy-collapsed to ω2 the new ω2 inherits some of the large cardinal properties; e.g. if S is a stationary set of ω-limits in ω2 then for some α < ω2, S ∩ α is stationary in α. Later S. Shelah extended this to the following theorem: if a supercompact cardinal κ is Lévy-collapsed to ω2, then in the resulting model the following holds: if S ⊆ λ is a stationary set of ω-limits and cf(λ) ≥ ω2 then there is an α. < λ such that S ∩ α is stationary in α, i.e. stationary reflection holds for countable cofinality (see [1] and [3]). These theorems are important prototypes of small cardinal compactness theorems; many applications and generalizations can be found in the literature. One might think that these results are true for sets with an uncountable cofinality μ as well, i.e. when an appropriate large cardinal is collapsed to μ++. Though this is true for Baumgartner's theorem, there remains a problem with Shelah's result. The point is that the lemma stating that a stationary set of ω-limits remains stationary after forcing with an ω2-closed partial order may be false in the case of μ-limits in a cardinal of the form λ+ with cf(λ) < μ, as was shown in [8] by Shelah. The problem has recently been solved by Baumgartner, who observed that if a universal box-sequence on the class of those ordinals with cofinality ≤ μ exists, the lemma still holds, and a universal box-sequence of the above type can be added without destroying supercompact cardinals beyond μ.

The aim of this paper is to give, using the Kripke semantics for intuitionism, a representation of finitely generated free Heyting algebras. By means of the representation we determine in a constructive way some set of “special elements” of such algebras. Furthermore, we show that many algebraic properties which are satisfied by the free algebra on one generator are not satisfied by free algebras on more than one generator.

In this article we shall construct intuitionistic analogues to the main systems of classical tense logic. Since each classical modal logic can be gotten from some tense logic by one of the definitions

• (i) □ p ≡ p ∧ Gp ∧ Hp, ◇p ≡ p ∨ Fp ∨ Pp; or,

• (ii) □ p ≡ p ∧ Gp, ◇p = p ∨ Fp

(see [5]), we shall find that our intuitionistic tense logics give us analogues to the classical modal logics as well.

We shall not here discuss the philosophical issues raised by our logics. Readers interested in the intuitionistic view of time and modality should see [2] for a detailed discussion.

In §2 we define the Kripke models for IKt, the intuitionistic analogue to Lemmon's system Kt. We then prove the completeness and decidability of this system (§§3–5). Finally, we extend our results to other sorts of tense logic and to modal logic.

In the language of IKt, we have: sentence-letters p, q, r, etc.; the (intuitionistic) connectives ∧, ∨, →, ¬; and unary operators P (“it was the case”), F (it will be the case”), H (“it has always been the case”) and G (“it will always be the case”). Formulas are defined inductively: all sentence-letters are formulas; if X is a formula, so are ¬X, PX, FX, HX, and GX; if X and Y are formulas, so are X ∧ Y, X ∨ Y, and X → Y. We shall see that, in contrast to classical tense logic, F and P cannot be defined in terms of G and H.

Forcing extensions yield models of ZFC in which a long sequence of club subsets of ω1, has the following property: every subsequence of size ℵ1, has a finite intersection.

We will give a simple philosophical “proof” of the negation of Cantor's continuum hypothesis (CH). (A formal proof for or against CH from the axioms of ZFC is impossible; see Cohen [1].) We will assume the axioms of ZFC together with intuitively clear axioms which are based on some intuition of Stuart Davidson and an old theorem of Sierpiński and are justified by the symmetry in a thought experiment throwing darts at the real number line. We will in fact show why there must be an infinity of cardinalities between the integers and the reals. We will also show why Martin's Axiom must be false, and we will prove the extension of Fubini's Theorem for Lebesgue measure where joint measurability is not assumed. Following the philosophy—if you reject CH you are only two steps away from rejecting the axiom of choice (AC)—we will point out along the way some extensions of our intuition which contradict AC.