We introduce a new hierarchy of computably enumerable degrees. This hierarchy is based on computable ordinal notations measuring complexity of approximation of ${\rm{\Delta }}_2^0$ functions. The hierarchy unifies and classifies the combinatorics of a number of diverse constructions in computability theory. It does so along the lines of the high degrees (Martin) and the array noncomputable degrees (Downey, Jockusch, and Stob). The hierarchy also gives a number of natural definability results in the c.e. degrees, including a definable antichain.

Leonid Levin showed that every algorithm computing a function has an optimal inverter. Recently, we applied his result in various contexts: existence of optimal acceptors, existence of hard sequences for algorithms and proof systems, proofs of Gödel’s incompleteness theorems, analysis of the complexity of the clique problem assuming the nonuniform Exponential Time Hypothesis. We present all these applications here. Even though a simple diagonalization yields Levin’s result, we believe that it is worthwhile to be aware of the explicit result. The purpose of this survey is to convince the reader of our view.

Vopěnka proved long ago that every set of ordinals is set-generic over HOD, Gödel's inner model of hereditarily ordinal-definable sets. Here we show that the entire universe V is class-generic over (HOD,S), and indeed over the even smaller inner model =(L[S],S), where S is the Stability predicate. We refer to the inner model as the Stable Core of V. The predicate S has a simple definition which is more absolute than any definition of HOD; in particular, it is possible to add reals which are not set-generic but preserve the Stable Core (this is not possible for HOD by Vopěnka's theorem).

We show that if $(M,{ \in _1},{ \in _2})$ satisfies the first-order Zermelo–Fraenkel axioms of set theory when the membership relation is ${ \in _1}$ and also when the membership relation is ${ \in _2}$, and in both cases the formulas are allowed to contain both ${ \in _1}$ and ${ \in _2}$, then $\left( {M, \in _1 } \right) \cong \left( {M, \in _2 } \right)$, and the isomorphism is definable in $(M,{ \in _1},{ \in _2})$. This extends Zermelo’s 1930 theorem in [6].

Alongside the analogy between maximal ideals and complete theories, the Jacobson radical carries over from ideals of commutative rings to theories of propositional calculi. This prompts a variant of Lindenbaum’s Lemma that relates classical validity and intuitionistic provability, and the syntactical counterpart of which is Glivenko’s Theorem. The Jacobson radical in fact turns out to coincide with the classical deductive closure. As a by-product we obtain a possible interpretation in logic of the axioms-as-rules conservation criterion for a multi-conclusion Scott-style entailment relation over a single-conclusion one.

Do there exist real numbers d with d2 = 0 (besides d = 0, of course)? The question is formulated provocatively, to stress a formalist view about existence: existence is consistency, or better, coherence.

Also, the provocation is meant to challenge the monopoly which the number system, invented by Dedekind et al., is claiming for itself as THE model of the geometric line. The Dedekind approach may be termed “arithmetization of geometry”.

We know that one may construct a number system out of synthetic geometry, as Euclid and followers did (completed in Hilbert's Grundlagen der Geometrie, [2, Chapter 3]): “geometrization of arithmetic”. (Picking two distinct points on the geometric line, geometric constructions in an ambient Euclidean plane provide structure of a commutative ring on the line, with the two chosen points as 0 and 1).

Starting from the geometric side, nilpotent elements are somewhat reasonable, although Euclid excluded them. The sophist Protagoras presented a picture of a circle and a tangent line; the apparent little line segment D which tangent and circle have in common, are, by Pythagoras' Theorem, precisely the points, whose abscissae d (measured along the tangent) have d2 = 0. Protagoras wanted to use this argument for destructive reasons: to refute the science of geometry.

A couple of millenia later, the Danish geometer Hjelmslev revived the Protagoras picture. His aim was more positive: he wanted to describe Nature as it was. According to him (or extrapolating his position), the Real Line, the Line of Sensual Reality, had many nilpotent infinitesimals, which we can see with our naked eyes.

§ 1. Introduction. Perhaps the most surprising recent development in complexity theory is the discovery that the class NP can be characterized using a form of randomized proof checker that only examines a constant number of bits of the “proof” that a string is in a language [6, 5, 31, 3, 4]. More specifically, writing ∣x∣ for the length of a string x, a language L in the class NP of languages recognizable in Nondeterministic polynomial time is traditionally given by a polynomial p and a polynomial-time predicate P such that a string x is in L iff there is some string y satisfying P(x, y), where ∣y∣ ≤ p (∣x∣). Intuitively, we can think of a string y as a possible proof that x ϵ L, with the predicate P some kind of proof checker that distinguishes good proofs from bad ones. A string x is therefore in a language L ϵ NP if there is a short proof that x ϵ L, and not in L otherwise. The surprising discovery is that the deterministic proof checker that reads the entire input and proof can be replaced by a probabilistic verifier that on input x and possible proof y, where y is presented in a certain way, flips at most O (log ∣x∣) coins and reads at most a constant number of bits of x and y. Obviously, a probabilistic verifier that does not read the whole proof will sometimes make mistakes. However, the surprising and essentially non-intuitive mathematical fact is that for each language L in NP, it is possible to find a polynomial q and verifier V flipping a logarithmic number of coins and reading a constant number of bits such that, for any x ϵ L, there exists y with ∣y∣ ≤ q(∣x∣) and with V (x, y) accepting with probability 1 and, for x ∉ L, there is no y with ∣y∣ ≤ q(∣x∣) and with V (x, y) accepting with probability ≥ 1/4. This idea canalsobeextended to PSPACE [10, 9], using a game that alternates between two players instead of a proof presented by a “single player.”

The goal of this paper is to announce there is a single orbit of the c.e. sets with inclusion, ε, such that the question of membership in this orbit is complete. This result and proof have a number of nice corollaries: the Scott rank of ε is + 1; not all orbits are elementarily definable; there is no arithmetic description of all orbits of ε; for all finite α ≥ 9, there is a properly orbit (from the proof).

We propose a criterion to regard a property of a theory (in first or second order logic) as virtuous: the property must have significant mathematical consequences for the theory (or its models). We then rehearse results of Ajtai, Marek, Magidor, H. Friedman and Solovay to argue that for second order logic, ‘categoricity’ has little virtue. For first order logic, categoricity is trivial; but ‘categoricity in power’ has enormous structural consequences for any of the theories satisfying it. The stability hierarchy extends this virtue to other complete theories. The interaction of model theory and traditional mathematics is examined by considering the views of such as Bourbaki, Hrushovski, Kazhdan, and Shelah to flesh out the argument that the main impact of formal methods on mathematics is using formal definability to obtain results in ‘mainstream’ mathematics. Moreover, these methods (e.g., the stability hierarchy) provide an organization for much mathematics which gives specific content to dreams of Bourbaki about the architecture of mathematics.

Here, we analyse some recent applications of set theory to topology and argue that set theory is not only the closed domain where mathematics is usually founded, but also a flexible framework where imperfect intuitions can be precisely formalized and technically elaborated before they possibly migrate toward other branches. This apparently new role is mostly reminiscent of the one played by other external fields like theoretical physics, and we think that it could contribute to revitalize the interest in set theory in the future.

Frege explained the notion of generality by stating that each its instance is a fact, and added only later the crucial observation that a generality can be inferred from an arbitrary instance. The reception of Frege’s quantifiers was a fifty-year struggle over a conceptual priority: truth or provability. With the former as the basic notion, generality had to be faced as an infinite collection of facts, whereas with the latter, generality was based on a uniformity with a finitary sense: the provability of an arbitrary instance.

The symmetries between points and lines in planar projective geometry and between points and planes in solid projective geometry are striking features of these geometries that were extensively discussed during the nineteenth century under the labels “duality” or “reciprocity.” The aims of this article are, first, to provide a systematic analysis of duality from a modern point of view, and, second, based on this, to give a historical overview of how discussions about duality evolved during the nineteenth century. Specifically, we want to see in which ways geometers’ preoccupation with duality was shaped by developments that lead to modern logic towards the end of the nineteenth century, and how these developments in turn might have been influenced by reflections on duality.

The class of all recursive functions fails to possess a natural hierarchical structure, generated predicatively from “within”. On the other hand, many (proof-theoretically significant) sub-recursive classes do. This paper attempts to measure the limit of predicative generation in this context, by classifying and characterizing those (predictably terminating) recursive functions which can be successively defined according to an autonomy condition of the form: allow recursions only over well-orderings which have already been “coded” at previous levels. The question is: how can a recursion code a well-ordering? The answer lies in Girard's theory of dilators, but is reworked here in a quite different and simplified framework specific to our purpose. The “accessible” recursive functions thus generated turn out to be those provably recursive in ( –CA)0.