In the present paper the story is told of the brief and far from tranquil encounter of L.E.J. Brouwer and A. Fraenkel. The relationship which started in perfect harmony, ended in irritation and reproaches.

The mutual appreciation at the outset is beyond question. All the more deplorable is the sudden outbreak of an emotional disagreement in 1927. Looking at the Brouwer–Fraenkel episode, one should keep in mind that at that time the so-called Grundlagenstreit was in full swing. An emotional man like Brouwer, who easily suffered under stress, was already on edgewhen Fraenkel's book Zehn Vorlesungen Über die Grundlegung der Mengenlehre, [Fraenkel 1927] was about to appear.

With the Grundlagenstreit reaching (in print!) a level of personal abuse unusual in the quiet circles of pure mathematics, Brouwer was rather sensitive, where the expositions of his ideas were concerned. So when he thought that he detected instances of misconception and misrepresentation in the case of his intuitionism, he felt slighted. We will mainly look at Brouwer's reactions. since the Fraenkel letters have not been preserved.

The late Mrs. Fraenkel kindly put the Brouwer letters that were in her possession at my disposal. I am grateful to the Fraenkel family for the permission to use the material.

I am indebted to Andreas Blass for his valuable suggestions and corrections.

Abraham Fraenkel (then still called Adolf) was one of the first non-partisan mathematicians, if not the first, who developed a genuine interest in intuitionism.

An elementary theory of concatenation, QT+, is introduced and used to establish mutual interpretability of Robinson arithmetic, Minimal Predicative Set Theory, quantifier-free part of Kirby’s finitary set theory, and Adjunctive Set Theory, with or without extensionality. The most basic arithmetic and simplest set theory thus turn out to be variants of string theory.

We prove the triviality of the Grothendieck ring of a ℤ-valued field K under slight conditions on the logical language and on K. We construct a definable bijection from the plane K2 to itself minus a point. When we specialize to local fields with finite residue field, we construct a definable bijection from the valuation ring to itself minus a point.

In this paper we isolate a notion that we call “formalism freeness” from Gödel's 1946 Princeton Bicentennial Lecture, which asks for a transfer of the Turing analysis of computability to the cases of definability and provability. We suggest an implementation of Gödel's idea in the case of definability, via versions of the constructible hierarchy based on fragments of second order logic. We also trace the notion of formalism freeness in the very wide context of developments in mathematical logic in the 20th century.

The fundamental question in reverse mathematics is to determine which set existence axioms are required to prove particular theorems of mathematics. In addition to being interesting in their own right, answers to this question have consequences in both effective mathematics and the foundations of mathematics. Before discussing these consequences, we need to be more specific about the motivating question.

Reverse mathematics is useful for studying theorems of either countable or essentially countable mathematics. Essentially countable mathematics is a vague term that is best explained by an example. Complete separable metric spaces are essentially countable because, although the spaces may be uncountable, they can be understood in terms of a countable basis. Simpson (1985) gives the following list of areas which can be analyzed by reverse mathematics: number theory, geometry, calculus, differential equations, real and complex analysis, combinatorics, countable algebra, separable Banach spaces, computability theory, and the topology of complete separable metric spaces. Reverse mathematics is less suited to theorems of abstract functional analysis, abstract set theory, universal algebra, or general topology.

Section 2 introduces the major subsystems of second order arithmetic used in reverse mathematics: RCA0, WKL0, ACA0, ATR0 and – CA0. Sections 3 through 7 consider various theorems of ordered group theory from the perspective of reverse mathematics. Among the results considered are theorems on ordered quotient groups (including an equivalent of ACA0), groups and semigroup conditions which imply orderability (WKL0), the orderability of free groups (RCA0), Hölder's Theorem (RCA0), Mal'tsev's classification of the order types of countable ordered groups ( – CA0)

If we assume the axiom of choice, then every two cardinal numbers are comparable. In the absence of the axiom of choice, this is no longer so. For a few cardinalities related to an arbitrary infinite set, we will give all the possible relationships between them, where possible means that the relationship is consistent with the axioms of set theory. Further we investigate the relationships between some other cardinal numbers in specific permutation models and give some results provable without using the axiom of choice.

The prepositional μ-calculus is an extension of the modal system K with a least fixpoint operator. Kozen posed a question about completeness of the axiomatisation of the logic which is a small extension of the axiomatisation of the modal system K. It is shown that this axiomatisation is complete.

The purpose of this communication is to announce some recent results on the computably enumerable sets. There are two disjoint sets of results; the first involves invariant classes and the second involves automorphisms of the computably enumerable sets. What these results have in common is that the guts of the proofs of these theorems uses a new form of definable coding for the computably enumerable sets.

We will work in the structure of the computably enumerable sets. The language is just inclusion, ⊆. This structure is called ε.

All sets will be computably enumerable non-computable sets and all degrees will be computably enumerable and non-computable, unless otherwise noted. Our notation and definitions are standard and follow Soare [1987]; however we will warm up with some definitions and notation issues so the reader need not consult Soare [1987]. Some historical remarks follow in Section 2.1 and throughout Section 3.

We will also consider the quotient structure ε modulo the ideal of finite sets, ε*. ε* is a definable quotient structure of ε since “Χ is finite” is definable in ε; “Χ is finite” iff all subsets of Χ are computable (it takes a little computability theory to show if Χ is infinite then Χ has an infinite non-computable subset). We use A* to denote the equivalent class of A under the ideal of finite sets.

The investigations on higher-order type theories and on the related notion of parametric polymorphism constitute the technical counterpart of the old foundational problem of the circularity (or impredicativity) of second and higher-order logic. However, the epistemological significance of such investigations has not received much attention in the contemporary foundational debate.

We discuss Girard’s normalization proof for second order type theory or System F and compare it with two faulty consistency arguments: the one given by Frege for the logical system of the Grundgesetze (shown inconsistent by Russell’s paradox) and the one given by Martin-Löf for the intuitionistic type theory with a type of all types (shown inconsistent by Girard’s paradox).

The comparison suggests that the question of the circularity of second order logic cannot be reduced to Russell’s and Poincaré’s 1906 “vicious circle” diagnosis. Rather, it reveals a bunch of mathematical and logical ideas hidden behind the hazardous idea of impredicative quantification, constituting a vast (and largely unexplored) domain for foundational research.

§1. The mission of axiomatic set theory. What is set theory needed for in the foundations of mathematics? Why cannot we transact whatever foundational business we have to transact in terms of our ordinary logic without resorting to set theory? There are many possible answers, but most of them are likely to be variations of the same theme. The core area of ordinary logic is by a fairly common consent the received first-order logic. Why cannot it take care of itself? What is it that it cannot do? A large part of every answer is probably that first-order logic cannot handle its own model theory and other metatheory. For instance, a first-order language does not allow the codification of the most important semantical concept, viz. the notion of truth, for that language in that language itself, as shown already in Tarski (1935). In view of such negative results it is generally thought that one of the most important missions of set theory is to provide the wherewithal for a model theory of logic. For instance Gregory H. Moore (1994, p. 635) asserts in his encyclopedia article “Logic and set theory” that

Set theory influenced logic, both through its semantics, by expanding the possible models of various theories and by the formal definition of a model; and through its syntax, by allowing for logical languages in which formulas can be infinite in length or in which the number of symbols is uncountable.

Edward Nelson published in 1986 a book defending an extreme formalist view of mathematics according to which there is an impassable barrier in the totality of exponentiation. On the positive side, Nelson embarks on a program of investigating how much mathematics can be interpreted in Raphael Robinson's theory of arithmetic . In the shadow of this program, some very nice logical investigations and results were produced by a number of people, not only regarding what can be interpreted in but also what cannot be so interpreted. We explain some of these results and rely on them to discuss Nelson's position.

The fact that Gödel's famous incompleteness theorem and the archetype of all logical paradoxes, that of the Liar, are related closely is, of course, not only well known, but is a part of the common knowledge of the community of logicians. Indeed, almost every more or less formal treatment of the theorem makes a reference to this connection. Gödel himself remarked in the paper announcing his celebrated result (cf. [7]):

The analogy between this result and Richard's antinomy leaps to the eye;

there is also a close relationship with the ‘liar’ antinomy, since … we are

… confronted with a proposition which asserts its own unprovability.

In the light of the fact that the existence of this connection is commonplace it is all the more surprising that very little can be learnt about its exact nature except perhaps that it is some kind of similarity or analogy. There is, however, a lot more to it than that. Indeed, as we shall try to show below, the general ideas underlying the three central theorems concerning internal limitations of formal deductive systems can be taken as different ways to resolve the Liar paradox. More precisely, it will turn out that an abstract formal variant of the Liar paradox, which can almost straightforwardly inferred from its original ordinary language version, is a possible common generalization of (both the syntactic and semantic versions of) Gödel's incompleteness theorem, the theorem of Tarski on the undefinability of truth, and that of Church concerning the undecidability of provability.

I see model theory as becoming increasingly detached from set theory, and the Tarskian notion of set-theoretic model being no longer central to model theory. In much of modern mathematics, the set-theoretic component is of minor interest, and basic notions are geometric or category-theoretic. In algebraic geometry, schemes or algebraic spaces are the basic notions, with the older “sets of points in affine or projective space” no more than restrictive special cases. The basic notions may be given sheaf-theoretically, or functorially. To understand in depth the historically important affine cases, one does best to work with more general schemes. The resulting relativization and “transfer of structure” is incomparably more flexible and powerful than anything yet known in “set-theoretic model theory”.

It seems to me now uncontroversial to see the fine structure of definitions as becoming the central concern of model theory, to the extent that one can easily imagine the subject being called “Definability Theory” in the near future.

Tarski's set-theoretic foundational formulations are still favoured by the majority of model-theorists, and evolution towards a more suggestive language has been perplexingly slow. None of the main texts uses in any nontrivial way the language of category theory, far less sheaf theory or topos theory. Given that the most notable interactions of model theory with geometry are in areas of geometry where the language of sheaves is almost indispensable (to the geometers), this is a curious situation, and I find it hard to imagine that it will not change soon, and rapidly.

The Euclidean algorithm on the natural numbers ℕ = {0,1,…} can be specified succinctly by the recursive program

where rem(a, b) is the remainder in the division of a by b, the unique natural number r such that for some natural number q,

It is an algorithm from (relative to) the remainder function rem, meaning that in computing its time complexity function cε (a, b), we assume that the values rem(x, y) are provided on demand by some “oracle” in one “time unit”. It is easy to prove that

Much more is known about cε(a, b), but this simple-to-prove upper bound suggests the proper formulation of the Euclidean's (worst case) optimality among its peers—algorithms from rem:

Conjecture. If an algorithm α computes gcd (x,y) from rem with time complexity cα (x,y), then there is a rational number r > 0 such that for infinitely many pairs a > b > 1, cα (a,b) > r log2a.

In his 1967 paper Vaught used an ingenious argument to show that every recursively enumerable first order theory that directly interprets the weak system VS of set theory is axiomatizable by a scheme. In this paper we establish a strengthening of Vaught's theorem by weakening the hypothesis of direct interpretability of VS to direct interpretability of the finitely axiomatized fragment VS2 of VS. This improvement significantly increases the scope of the original result, since VS is essentially undecidable, but VS2 has decidable extensions. We also explore the ramifications of our work on finite axiomatizability of schemes in the presence of suitable comprehension principles.

We study algorithmic randomness notions via effective versions of almost-everywhere theorems from analysis and ergodic theory. The effectivization is in terms of objects described by a computably enumerable set, such as lower semicomputable functions. The corresponding randomness notions are slightly stronger than Martin–Löf (ML) randomness.

We establish several equivalences. Given a ML-random real z, the additional randomness strengths needed for the following are equivalent.

1. (1) all effectively closed classes containing z have density 1 at z.

2. (2) all nondecreasing functions with uniformly left-c.e. increments are differentiable at z.

3. (3) z is a Lebesgue point of each lower semicomputable integrable function.

We also consider convergence of left-c.e. martingales, and convergence in the sense of Birkhoff’s pointwise ergodic theorem. Lastly, we study randomness notions related to density of ${\rm{\Pi }}_n^0$ and ${\rm{\Sigma }}_1^1$ classes at a real.

We use the category of presheaves over PTIME-functions in order to show that Cook and Urquhart's higher-order function algebra PVω defines exactly the PTIME-iunctions. As a byproduct we obtain a syntax-free generalisation of PTIME-computability to higher types.

By restricting to sheaves for a suitable topology we obtain a model for intuitionistic predicate logic with -induction over PVω and use this to re-establish that the provably total functions in this system are polynomial time computable. Finally, we apply the category-theoretic approach to a new higher-order extension of Bellantoni-Cook's system BC of safe recursion.

Ramsey’s theorem states that for any coloring of the n-element subsets of ℕ with finitely many colors, there is an infinite set H such that all n-element subsets of H have the same color. The strength of consequences of Ramsey’s theorem has been extensively studied in reverse mathematics and under various reducibilities, namely, computable reducibility and uniform reducibility. Our understanding of the combinatorics of Ramsey’s theorem and its consequences has been greatly improved over the past decades. In this paper, we state some questions which naturally arose during this study. The inability to answer those questions reveals some gaps in our understanding of the combinatorics of Ramsey’s theorem.