Kripke recently suggested viewing the intuitionistic continuum as an expansion in time of a definite classical continuum. We prove the classical consistency of a three-sorted intuitionistic formal system IC, simultaneously extending Kleene’s intuitionistic analysis I and a negative copy C° of the classically correct part of I, with an “end of time” axiom ET asserting that no choice sequence can be guaranteed not to be pointwise equal to a definite (classical or lawlike) sequence. “Not every sequence is pointwise equal to a definite sequence” is independent of IC. The proofs are by Crealizability interpretations based on classical ω-models ${\cal M}$ = $\left( {\omega ,{\cal C}} \right)$ of C°.

It was questions about points on the real line that initiated the study of set theory. Points paved the way to point sets and these to ever more abstract sets. And there was more: Reflection on structural properties of point sets not only initiated the study of ordinary sets; it also supplied blueprints for defining extra-ordinary, “large” sets, transcending those provided by standard set theory. In return, the existence of such large sets turned out critical to settling open conjectures about point sets.

How to explain such action at a distance between the very large and the rather small? Rather than having an air of magic, could these results rest on deep structural similarities between the two superficially distant species of sets?

In this essay I dissect one group of such two-way results. Their linchpin is the notion of measure.

§1. Vitali's impossibility result. Our starting point is a problem in measure theory regarding the notion of “Lebesgue measure.” Before presenting the problem, I would like to review the notion of Lebesgue measure. Rather than listing its main properties, I would like to show how Lebesgue measure is born out of an attempt to generalize the notion of the length of an interval to arbitrary sets of reals. One tries to approximate arbitrary sets of reals by intervals, in the hope that the lengths of the intervals will induce a measure on these sets.

We discuss the typography of the notation used by Gottlob Frege in his Grundgesetze der Arithmetik.

We survey recent advances on the interface between computability theory and algorithmic randomness, with special attention on measures of relative complexity. We focus on (weak) reducibilities that measure (a) the initial segment complexity of reals and (b) the power of reals to compress strings, when they are used as oracles. The results are put into context and several connections are made with various central issues in modern algorithmic randomness and computability.

In an article published in 1974, Menas conjectured that any stationary subset of can be split in many pairwise disjoint stationary subsets. Even though the conjecture was shown long ago by Baumgartner and Taylor to be consistently false, it is still haunting papers on . In which situations does it hold? How much of it can be proven in ZFC? We start with an abridged history of the conjecture, then we formulate a new version of it, and finally we keep weakening this new assertion until, building on the work of Usuba, we hit something we can prove.

Goodstein’s principle is arguably the first purely number-theoretic statement known to be independent of Peano arithmetic. It involves sequences of natural numbers which at first appear to diverge, but eventually decrease to zero. These sequences are defined relative to a notation system based on exponentiation for the natural numbers. In this article, we provide a self-contained and modern analysis of Goodstein’s principle, obtaining some variations and improvements. We explore notions of optimality for notation systems and apply them to the classical Goodstein process and to a weaker variant based on multiplication rather than exponentiation. In particular, we introduce the notion of base-change maximality, and show how it leads to far-reaching extensions of Goodstein’s result. We moreover show that by varying the initial base of the Goodstein process, one readily obtains independence results for each of the fragments $\mathsf {I}\Sigma _n$ of Peano arithmetic.

This paper discusses certain problems arising within the treatment of the senses of functions in Alonzo Church's Logic of Sense and Denotation. Church understands such senses themselves to be “sense-functions,” functions from sense to sense. However, the conditions he lays out under which a sense-function is to be regarded as a sense presenting another function as denotation allow for certain undesirable results given certain unusual or “deviant” sense-functions. Certain absurdities result, e.g., an argument can be found for equating any two senses of the same type. An alternative treatment of the senses of functions is discussed, and is thought to do better justice to Frege's original theory.

We raise an issue of circularity in the argument for the completeness of first-order logic. An analysis of the problem sheds light on the development of mathematics, and suggests other possible directions for foundational research.

The aim of this paper is to describe (without proofs) an analogue of the theory of nontrivial torsion-free divisible abelian groups for metabelian groups. We obtain illustrations for “old-fashioned” model theoretic algebra and “new” examples in the theory of stable groups. We begin this paper with general considerations about model theory. In the second section we present our results and we give the structure of the rest of the paper. Most parts of this paper use only basic concepts from model theory and group theory (see [14] and especially Chapters IV, V, VI and VIII for model theory, and see for example [23] and especially Chapters II and V for group theory). However, in Section 5, we need some somewhat elaborate notions from stability theory. One can find the beginnings of this theory in [14], and we refer the reader to [16] or [21] for stability theory and to [22] for stable groups.

§1. Some model theoretic considerations. Denote by the theory of torsion-free abelian groups in the language of groups ℒgp. A finitely generated group G satisfies iff G is isomorphic to a finite direct power of ℤ. It follows that axiomatizes the universal theory of free abelian groups and that the theory of nontrivial torsion-free abelian groups is complete for the universal sentences. Denote by the theory of nontrivial divisible torsion-free abelian groups.

We use Herbrand’s theorem to give a new proof that Euclid’s parallel axiom is not derivable from the other axioms of first-order Euclidean geometry. Previous proofs involve constructing models of non-Euclidean geometry. This proof uses a very old and basic theorem of logic together with some simple properties of ruler-and-compass constructions to give a short, simple, and intuitively appealing proof.

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}.

Julius König is famous for his mistaken attempt to demonstrate that the continuum hypothesis was false. It is also known that the only positive result that could have survived from his proof is the paradox which bears his name. Less famous is his 1914 book Neue Grundlagen der Logik, Arithmetik und Mengenlehre. Still, it contains original contributions to logic, like the concept of metatheory and the solution of paradoxes based on the refusal of the law of bivalence. We are going to discover them by analysing the content of the book.

Martin’s conjecture is an attempt to classify the behavior of all definable functions on the Turing degrees under strong set theoretic hypotheses. Very roughly it says that every such function is either eventually constant, eventually equal to the identity function or eventually equal to a transfinite iterate of the Turing jump. It is typically divided into two parts: the first part states that every function is either eventually constant or eventually above the identity function and the second part states that every function which is above the identity is eventually equal to a transfinite iterate of the jump. If true, it would provide an explanation for the unique role of the Turing jump in computability theory and rule out many types of constructions on the Turing degrees.

In this thesis, we will introduce a few tools which we use to prove several cases of Martin’s conjecture. It turns out that both these tools and these results on Martin’s conjecture have some interesting consequences both for Martin’s conjecture and for a few related topics.

The main tool that we introduce is a basis theorem for perfect sets, improving a theorem due to Groszek and Slaman. We also introduce a general framework for proving certain special cases of Martin’s conjecture which unifies a few pre-existing proofs. We will use these tools to prove three main results about Martin’s conjecture: that it holds for regressive functions on the hyperarithmetic degrees (answering a question of Slaman and Steel), that part 1 holds for order preserving functions on the Turing degrees, and that part 1 holds for a class of functions that we introduce, called measure preserving functions.

This last result has several interesting consequences for the study of Martin’s conjecture. In particular, it shows that part 1 of Martin’s conjecture is equivalent to a statement about the Rudin-Keisler order on ultrafilters on the Turing degrees. This suggests several possible strategies for working on part 1 of Martin’s conjecture, which we will discuss.

The basis theorem that we use to prove these results also has some applications outside of Martin’s conjecture. We will use it to prove a few theorems related to Sacks’ question about whether it is provable in $\mathsf {ZFC}$ that every locally countable partial order of size continuum embeds into the Turing degrees. We will show that in a certain extension of $\mathsf {ZF}$ (which is incompatible with $\mathsf {ZFC}$ ), this holds for all partial orders of height two, but not for all partial orders of height three. Our proof also yields an analogous result for Borel partial orders and Borel embeddings in $\mathsf {ZF}$ , which shows that the Borel version of Sacks’ question has a negative answer.

We will end the thesis with a list of open questions related to Martin’s conjecture, which we hope will stimulate further research.

Abstract prepared by Patrick Lutz.

E-mail: [email protected]

We describe a recent program from the study of definable groups in certain o-minimal structures. A central notion of this program is that of a (geometric) lattice. We propose a definition of a lattice in an arbitrary first-order structure. We then use it to describe, uniformly, various structure theorems for o-minimal groups, each time recovering a lattice that captures some significant invariant of the group at hand. The analysis first goes through a local level, where a pertinent notion of pregeometry and generic elements is each time introduced.