This paper uses the framework of reverse mathematics to investigate the strength of two recurrence theorems of topological dynamics. It establishes that one of these theorems, the existence of an almost periodic point, lies strictly between WKL and ACA (working over RCA0). This is the first example of a theorem with this property. It also shows the existence of an almost periodic point is conservative over RCA0 for ${\rm{\Pi }}_1^1$ -sentences.

This paper is a contribution to the project of determining which set existence axioms are needed to prove various theorems of analysis. For more on this project and its history we refer the reader to [1] and [2].

We work in a weak subsystem of second order arithmetic. The language of second order arithmetic includes the symbols 0, 1, =, <, +, ·, and ∈, together with number variables x, y, z, … (which are intended to stand for natural numbers), set variables X, Y, Z, … (which are intended to stand for sets of natural numbers), and the usual quantifiers (which can be applied to both kinds of variables) and logical connectives. We write ∀x < t φ and ∃x < t φ as abbreviations for ∀x(x < t → φ) and ∃x{x < t ∧ φ) respectively; these are called bounded quantifiers. A formula is said to be if it has no quantifiers applied to set variables, and all quantifiers applied to number variables are bounded. It is if it has the form ∃xθ and it is if it has the form ∀xθ, where in both cases θ is .

The theory RCA0 has as axioms the usual Peano axioms, with the induction scheme restricted to formulas, and in addition the comprehension scheme, which consists of all formulas of the form

where φ is , ψ is , and X does not occur free in φ(n). (“RCA” stands for “Recursive Comprehension Axiom.” The reason for the name is that the comprehension scheme is only strong enough to prove the existence of recursive sets.) It is known that this theory is strong enough to allow the development of many of the basic properties of the real numbers, but that certain theorems of elementary analysis are not provable in this theory. Most relevant for our purposes is the fact that it is impossible to prove in RCA0 that every continuous function on the closed interval [0, 1] attains maximum and minimum values (see [1]).

Since the most common proof of the Mean Value Theorem makes use of this theorem, it might be thought that the Mean Value Theorem would also not be provable in RCA0. However, we show in this paper that the Mean Value Theorem can be proven in RCA0. All theorems stated in this paper are theorems of RCA0, and all of our reasoning will take place in RCA0.

The provability logic of a theory T captures the structural behavior of formalized provability in T as provable in T itself. Like provability, one can formalize the notion of relative interpretability giving rise to interpretability logics. Where provability logics are the same for all moderately sound theories of some minimal strength, interpretability logics do show variations.

The logic IL (All) is defined as the collection of modal principles that are provable in any moderately sound theory of some minimal strength. In this article we raise the previously known lower bound of IL (All) by exhibiting two series of principles which are shown to be provable in any such theory. Moreover, we compute the collection of frame conditions for both series.

We produce counterexamples to the unique and cofinal branches hypotheses, assuming (slightly less than) the existence of a cardinal which is strong past a Woodin cardinal.

We show a model construction for a system of higher-order illative combinatory logic thus establishing its strong consistency. We also use a variant of this construction to provide a complete embedding of first-order intuitionistic predicate logic with second-order propositional quantifiers into the system of Barendregt, Bunder and Dekkers, which gives a partial answer to a question posed by these authors.

In the paper we prove the following theorem:

Theorem. There is a model N of open induction in which the set of primes is bounded and N is such that its field of fractions 〈N*, +, ·, <〉 is elementarily equivalent to 〈Q, +, ·, <〉 (the standard rationals).

We fix an ω 1-saturated model 〈M, +, ·, <〉 of PA. Let 〈M*, +, ·, <〉 denote the field of fractions of M. The model N that we are looking for will be a substructure of 〈M*, +, ·, <〉.

If A ⊆ M* then let Ā denote the ring generated by A within M*, Ậ the real closure of A, and A* the field of fractions generated by A. We have

Let J ⊆ M. Then 〈M*, +, ·〉 is a linear space over J*. If x 1,…,xk ∈ M*, we shall say that x 1,…,xk are J-independent if 〈1, x 1,…, xk 〉 are J*-independent in the usual sense. As usual, we extend the notion of J-independence to the case of infinite sets.

If A ⊆ M* and X ⊆ A, then we say that X is a J-basis of A if X is a maximal subset of A which is J-independent.

We show that all the projective ordinals are supercompact through their supremum and a ways beyond.

A previous paper proposed a finitary system of logic which was surmised to be basic in the sense that every finitary system of logic could be defined within it. In the present paper this anticipated result, or rather its syntactical counterpart, is definitely established as Theorem VI. The calculus K is a formalization of the basic logic. Its main features were described in the previous paper, acquaintance with which is presupposed here. Attention is called to the fact that from now on the class Y of atomic U-expressions will be assumed to be finite instead of infinite. This is a relatively minor change and does not affect the previously established results. The account of the nature of calculi, as given in the other paper, is to be made more precise by stating that a calculus is any class of expressions having as a Gödel representation a recursively enumerable class of integers. A system of logic is regarded as being finitary if it is capable of formalization by means of an appropriate calculus.

We affirm a conjecture of Sacks [1972] by showing that every countable distributive lattice is isomorphic to an initial segment of the hyperdegrees, . In fact, we prove that every sublattice of any hyperarithmetic lattice (and so, in particular, every countable, locally finite lattice) is isomorphic to an initial segment of . Corollaries include the decidability of the two quantifier theory of , and the undecidability of its three quantifier theory. The key tool in the proof is a new lattice representation theorem that provides a notion of forcing for which we can prove a version of the fusion lemma in the hyperarithmetic setting and so the preservation of ω1 ck . Somewhat surprisingly, the set theoretic analogof this forcing does not preserve ω1. On the other hand, we construct countable lattices that are not isomorphic to any initial segment of .

In this note two independent comments are offered concerning nominalistic syntax.

If one has a nominalistic theory of natural numbers (or positive integers) at one's disposal, one can of course readily formulate a nominalistic syntax by the familiar method of arithmetization. A nominalistic theory of natural numbers is formulated in a previous paper by the author, and thus a basis for a nominalistic syntax is already provided. (The objection that this theory is infinitistic would appear without force, because it provides the only known nominalistic basis for the theory of general recursive functions. On a finitistic basis one merely throws out this vital domain of mathematical theory.)

The second comment is concerned with nominalistic syntax as formulated by Goodman and Quine. The nominalistic construction of natural numbers alluded to above owes much of its power to a primitive device of ancestral quantification. This device is somewhat more powerful than the notions Goodman and Quine allow themselves. Now nominalistic syntax in their somewhat narrower sense can be formulated by utilizing a relation akin to the relation L of the theory of ordered individuals developed elsewhere by the author. ‘L’ here is to designate the relation between inscriptions of being wholly to the left of.

The Goodman-Quine primitive ‘C’, designating a relation of concatenation, and their primitive ‘Part’ with its field confined to inscriptions, can be defined in terms of ‘L’. Thus:

.

(This definition is essentially that of ‘P’ in O.I.)

We show that a cardinal κ is a (strongly) Mahlo cardinal if and only if there exists a nontrivial κ-complete κ-normal ideal on κ. Also we show that if κ is Mahlo and λ ≧ κ and λ<κ = λ then there is a nontrivial κ-complete κ-normal fine ideal on Pκ(λ). If κ is the successor of a cardinal, we consider weak κ-normality and prove that if κ = μ+ and μ is a regular cardinal then (1) μ< μ = μ if and only if there is a nontrivial κ-complete weakly κ-normal ideal on κ, and (2) if μ< μ = μ < λ<μ = λ then there is a nontrivial κ-complete weakly κ-normal fine ideal on Pκ(λ).

We determine exact consistency strengths for various failures of the Singular Cardinals Hypothesis (SCH) in the setting of the Zermelo-Fraenkel axiom system ZF without the Axiom of Choice (AC). By the new notion of parallel Prikry forcing that we introduce, we obtain surjective failures of SCH using only one measurable cardinal, including a surjective failure of Shelah's pcf theorem about the size of the power set of ℵω. Using symmetric collapses to ℵω, , or , we show that injective failures at ℵω, , or can have relatively mild consistency strengths in terms of Mitchell orders of measurable cardinals. Injective failures of both the aforementioned theorem of Shelah and Silver's theorem that GCH cannot first fail at a singular strong limit cardinal of uncountable cofinality are also obtained. Lower bounds are shown by core model techniques and methods due to Gitik and Mitchell.

We prove that the definition of supersimplicity in metric structures from [7] is equivalent to an a priori stronger variant. This stronger variant is then used to prove that if T is a supersimple Hausdorff cat then so is its theory of lovely pairs.

We study the values of the higher dimensional cardinal characteristics for sets of functions $f:\omega ^\omega \to \omega ^\omega $ introduced by the second author in [8]. We prove that while the bounding numbers for these cardinals can be strictly less than the continuum, the dominating numbers cannot. We compute the bounding numbers for the higher dimensional relations in many well known models of $\neg \mathsf {CH}$ such as the Cohen, random and Sacks models and, as a byproduct show that, with one exception, for the bounding numbers there are no $\mathsf {ZFC}$ relations between them beyond those in the higher dimensional Cichoń diagram. In the case of the dominating numbers we show that in fact they collapse in the sense that modding out by the ideal does not change their values. Moreover, they are closely related to the dominating numbers $\mathfrak {d}^\lambda _\kappa $.

Let be a finite relational language and α = (αR: R ∈ ) a tuple with 0 < αR ≤ 1 for each R ∈ . Consider a dimension function

where each eR(A) is the number of realizations of R in A. Let Kα be the class of finite structures A such that δα (X) ≥ 0 for any substructure X of A. We show that the theory of the generic model of Kα is AE-axiomatizable for any α.