I survey the syntactic technique of tiering which can be used to restrict the power of a recursion scheme. I show how various results can be obtained entirely proof theoretically without the use of a model of computation.

Despite some discomfort with this grandly philosophical topic, I do in fact hope to address a venerable pair of philosophical chestnuts: mathematical truth and existence. My plan is to set out three possible stands on these issues, for an exercise in compare and contrast. A word of warning, though, to philosophical purists (and perhaps of comfort to more mathematical readers): I will explore these philosophical positions with an eye to their interconnections with some concrete issues of set theoretic method.

Let me begin with a brief look at what to count as ‘philosophy’. To some extent, this is a matter of usage, and mathematicians sometimes classify as ‘philosophical’ any considerations other than outright proofs. So, for example, discussions of the propriety of particular mathematical methods would fall under this heading: should we prefer analytic or synthetic approaches in geometry? Should elliptic functions be treated in terms of explicit representations (as in Weierstrass) or geometrically (as in Riemann)? Should we allow impredicative definitions? Should we restrict ourselves to a logic without bivalence or the law of the excluded middle? Also included in this category would be the trains of thought that shaped our central concepts: should a function always be defined by a formula? Should a group be required to have an inverse for every element? Should ideal divisors be defined contextually or explicitly, treated computationally or abstractly? In addition, there are more general questions concerning mathematical values, aims and goals: Should we strive for powerful theories or low-risk theories? How much stress should be placed on the fact or promise of physical applications? How important are interconnections between the various branches of mathematics? These philosophical questions of method naturally include several peculiar to set theory: should set theorists focus their efforts on drawing consequences for areas of interest to mathematicians outside mathematical logic? Should exploration of the standard axioms of ZFC be preferred to the exploration and exploitation of new axioms? How should axioms for set theory be chosen? What would a solution to the Continuum Problem look like?

We define the notion of ordinal computability by generalizing standard Turing computability on tapes of length ω to computations on tapes of arbitrary ordinal length. We show that a set of ordinals is ordinal computable from a finite set of ordinal parameters if and only if it is an element of Gödel's constructible universe L. This characterization can be used to prove the generalized continuum hypothesis in L.

When attempting to generalize recursion theory to admissible ordinals, it may seem as if all classical priority constructions can be lifted to any admissible ordinal satisfying a sufficiently strong fragment of the replacement scheme. We show, however, that this is not always the case. In fact, there are some constructions which make an essential use of the notion of finiteness which cannot be replaced by the generalized notion of α-finiteness. As examples we discuss both codings of models of arithmetic into the recursively enumerable degrees, and non-distributive lattice embeddings into these degrees. We show that if an admissible ordinal α is effectively close to ω (where this closeness can be measured by size or by cofinality) then such constructions may be performed in the α-r.e. degrees, but otherwise they fail. The results of these constructions can be expressed in the first-order language of partially ordered sets, and so these results also show that there are natural elementary differences between the structures of α-r.e. degrees for various classes of admissible ordinals α. Together with coding work which shows that for some α, the theory of the α-r.e. degrees is complicated, we get that for every admissible ordinal α, the α-r.e. degrees and the classical r.e. degrees are not elementarily equivalent.

The connections between mathematical logic and combinatorics have a rich history. This paper focuses on one aspect of this relationship: understanding the strength, measured using the tools of computability theory and reverse mathematics, of various partition theorems. To set the stage, recall two of the most fundamental combinatorial principles, König's Lemma and Ramsey's Theorem. We denote the set of natural numbers by ω and the set of finite sequences of natural numbers by ω<ω. We also identify each n ∈ ω with its set of predecessors, so n = {0, 1, 2, …, n − 1}.

We prove that the two-variable fragment of first-order intuitionistic logic is undecidable, even without constants and equality. We also show that the two-variable fragment of a quantified modal logic L with expanding first-order domains is undecidable whenever there is a Kripke frame for L with a point having infinitely many successors (such are, in particular, the first-order extensions of practically all standard modal logics like K, K4, GL, S4, S5, K4.1, S4.2, GL.3, etc.). For many quantified modal logics, including those in the standard nomenclature above, even the monadic two-variable fragments turn out to be undecidable.