We give a survey of current research on Gödel’s incompleteness theorems from the following three aspects: classifications of different proofs of Gödel’s incompleteness theorems, the limit of the applicability of Gödel’s first incompleteness theorem, and the limit of the applicability of Gödel’s second incompleteness theorem.

We carry out some of Galois' work in the setting of an arbitrary first-order theory T. We replace the ambient algebraically closed field by a large model M of T, replace fields by definably closed subsets of M, assume that T codes finite sets, and obtain the fundamental duality of Galois theory matching subgroups of the Galois group of L over F with intermediate extensions F ≤ K ≤ L. This exposition of a special case of [10] has the advantage of requiring almost no background beyond familiarity with fields, polynomials, first-order formulae, and automorphisms.

Osvald Demuth (1936–1988) studied constructive analysis from the viewpoint of the Russian school of constructive mathematics. In the course of his work he introduced various notions of effective null set which, when phrased in classical language, yield a number of major algorithmic randomness notions. In addition, he proved several results connecting constructive analysis and randomness that were rediscovered only much later.

In this paper, we trace the path that took Demuth from his constructivist roots to his deep and innovative work on the interactions between constructive analysis, algorithmic randomness, and computability theory. We will focus specifically on (i) Demuth’s work on the differentiability of Markov computable functions and his study of constructive versions of the Denjoy alternative, (ii) Demuth’s independent discovery of the main notions of algorithmic randomness, as well as the development of Demuth randomness, and (iii) the interactions of truth-table reducibility, algorithmic randomness, and semigenericity in Demuth’s work.

A cofinitary group is a subgroup of Sym(ℕ) where all nonidentity elements have finitely many fixed points. A maximal cofinitary group is a cofinitary group, maximal with respect to inclusion. We show that a maximal cofinitary group cannot have infinitely many orbits. We also show, using Martin's Axiom, that no further restrictions on the number of orbits can be obtained. We show that Martin's Axiom implies there exist locally finite maximal cofinitary groups. Finally we show that there exists a uniformly computable sequence of permutations generating a cofinitary group whose isomorphism type is not computable.

A cornerstone of modern mathematical logic is the diagonal lemma of Gödel and Carnap. It is used in, for example, the classical proofs of the theorems of Gödel, Rosser, and Tarski. From its first explication in 1934, just essentially one proof has appeared for the diagonal lemma in the literature; a proof that is so tricky and hard to relate that many authors have tried to avoid the lemma altogether. As a result, some so-called diagonal-free proofs have been given for the above-mentioned fundamental theorems of logic. In this paper, we provide new proofs for the semantic formulation of the diagonal lemma, and for a weak version of the syntactic formulation of it.

The final two volumes, numbers IV and V, of the Oxford University Press edition of the Collected Works of Kurt Gödel [3]–[7] appeared in 2003, thus completing a project that started over twenty years earlier. What I mainly want to do here is trace, from the vantage point of my personal involvement, the at some times halting and at other times intense development of the Gödel editorial project from the first initiatives following Gödel's death in 1978 to its completion last year. It may be useful to scholars mounting similar editorial projects for other significant figures in our field to learn how and why various decisions were made and how the work was carried out, though of course much is particular to who and what we were dealing with.

My hope here is also to give the reader who is not already familiar with the Gödel Works a sense of what has been gained in the process, and to encourage dipping in according to interest. Given the absolute importance of Gödel for mathematical logic, students should also be pointed to these important source materials to experience first hand the exercise of his genius and the varied ways of his thought and to see how scholarly and critical studies help to expand their significance.

Though indeed much has been gained in our work there is still much that can and should be done; besides some indications below, for that the reader is referred to [2].

In 1934 Alonzo Church, Kurt Gödei, S. C. Kleene, and J. B. Rosser were all to be found in Princeton, New Jersey. In 1936 Church founded The Journal of Symbolic Logic. Shortly thereafter Alan Turing arrived for a two year visit. The United States had become a world center for cutting-edge research in mathematical logic. In this brief survey1 we shall examine some of the writings of American logicians during the 1920s, a period of important beginnings and remarkable insights as well as of confused gropings.

The publication of Whitehead and Russell's monumental Principia Mathematica [18] during the years 1910-1913 provided the basis for much of the research that was to follow. It also provided the basis for confusion that remained a factor during the period we are discussing. In 1908, Henri Poincaré, a famous skeptic where mathematical logic was concerned, wrote pointedly ([13]):

It is difficult to admit that the word if acquires, when written ⊃, a virtue it did not possess when written if.

Principia provided no very convincing answer to Poincaré. Indeed the fact that the authors of Principia saw fit to place their first two “primitive propositions”

*1.1: Anything implied by a true proposition is true.

*1.2: ⊢ p ⋁ p ⊃ p

under one and the same heading suggest that they had thought of what they were doing as just such a translation as Poincare had derided.

We show that the universal theory of the hyperfinite II$_1$ factor is not computable. The proof uses the recent result that MIP*=RE. Combined with an earlier observation of the authors, this yields a proof that the Connes Embedding Problem has a negative solution that avoids the equivalences with Kirchberg’s QWEP Conjecture and Tsirelson’s Problem.

Recent results on initial segments of the Turing degrees are presented, and some conjectures about initial segments that have implications for the existence of nontrivial automorphisms of the Turing degrees are indicated.

The isomorphism invariance criterion of logical nature has much to commend it. It can be philosophically motivated by the thought that logic is distinctively general or topic neutral. It is capable of precise set-theoretic formulation. And it delivers an extension of ‘logical constant’ which respects the intuitively clear cases. Despite its attractions, the criterion has recently come under attack. Critics such as Feferman, MacFarlane and Bonnay argue that the criterion overgenerates by incorrectly judging mathematical notions as logical. We consider five possible precisifications of the overgeneration argument and find them all unconvincing.

We establish, generalizing Di Nola and Lettieri’s categorical equivalence, a Morita-equivalence between the theory of lattice-ordered abelian groups and that of perfect MV-algebras. Further, after observing that the two theories are not bi-interpretable in the classical sense, we identify, by considering appropriate topos-theoretic invariants on their common classifying topos, three levels of bi-interpretability holding for particular classes of formulas: irreducible formulas, geometric sentences, and imaginaries. Lastly, by investigating the classifying topos of the theory of perfect MV-algebras, we obtain various results on its syntax and semantics also in relation to the cartesian theory of the variety generated by Chang’s MV-algebra, including a concrete representation for the finitely presentable models of the latter theory as finite products of finitely presentable perfect MV-algebras. Among the results established on the way, we mention a Morita-equivalence between the theory of lattice-ordered abelian groups and that of cancellative lattice-ordered abelian monoids with bottom element.

We introduce a nonstandard arithmetic NQA− based on the theory developed by R. Chuaqui and P. Suppes in [2] (we will denote it by NQA+), with a weakened external open minimization schema. A finitary consistency proof for NQA− formalizable in PRA is presented. We also show interesting facts about the strength of the theories NQA−and NQA+; NQA−is mutually interpretable with IΔ0 + EXP, and on the other hand, NQA+interprets the theories IΣ1 and WKL0.

The Connes Embedding Problem (CEP) asks whether every separable II1 factor embeds into an ultrapower of the hyperfinite II1 factor. We show that the CEP is equivalent to the statement that every type II1 tracial von Neumann algebra has a computable universal theory.

Hermann Weyl was one of the greatest mathematicians of the 20th century, with contributions to many branches of mathematics and physics. In 1918, he wrote a famous book, “Das Kontinuum”, on the foundations of mathematics. In that book, he described mathematical analysis as a ‘house built on sand’, and tried to ‘replace this shifting foundation with pillars of enduring strength’.

In this paper, we reexamine and explain the philosophical and mathematical ideas that underly Weyl’s system in “Das Kontinuum”, and show that they are still useful and relevant. We propose a precise formalization of that system, which is the first to be completely faithful to what is written in the book. Finally, we suggest that a certain set-theoretical modern system reflects better Weyl’s ideas than previous attempts (most notably by Feferman) of achieving this goal.

This paper ties together much of the model theory of the last 50 years. Shelah's attempts to generalize the Morley theorem beyond first order logic led to the notion of excellence, which is a key to the structure theory of uncountable models. The notion of Abstract Elementary Class arose naturally in attempting to prove the categoricity theorem for Lω1,ω(Q). More recently, Zilber has attempted to identify canonical mathematical structures as those whose theory (in an appropriate logic) is categorical in all powers. Zilber's trichotomy conjecture for first order categorical structures was refuted by Hrushovski, by the introducion of a special kind of Abstract Elementary Class. Zilber uses a powerful and essentailly infinitary variant on these techniques to investigate complex exponentiation. This not only demonstrates the relevance of Shelah's model theoretic investigations to mainstream mathematics but produces new results and conjectures in algebraic geometry.

§0. Preface. There has been an expectation that the endgame of the more tenacious problems raised by the Los Angeles ‘cabal’ school of descriptive set theory in the 1970's should ultimately be played out with the use of inner model theory. Questions phrased in the language of descriptive set theory, where both the conclusions and the assumptions are couched in terms that only mention simply definable sets of reals, and which have proved resistant to purely descriptive set theoretic arguments, may at last find their solution through the connection between determinacy and large cardinals.

Perhaps the most striking example was given by [24], where the core model theory was used to analyze the structure of HOD and then show that all regular cardinals below ΘL(ℝ) are measurable. John Steel's analysis also settled a number of structural questions regarding HODL(ℝ), such as GCH.

Another illustration is provided by [21]. There an application of large cardinals and inner model theory is used to generalize the Harrington-Martin theorem that determinacy implies )determinacy.

However, it is harder to find examples of theorems regarding the structure of the projective sets whose only known proof from determinacy assumptions uses the link between determinacy and large cardinals. We may equivalently ask whether there are second order statements of number theory that cannot be proved under PD–the axiom of projective determinacy–without appealing to the large cardinal consequences of the PD, such as the existence of certain kinds of inner models that contain given types of large cardinals.

We show that, assuming the Axiom of Determinacy, every non-selfdual Wadge class can be constructed by starting with those of level $\omega _1$ (that is, the ones that are closed under Borel preimages) and iteratively applying the operations of expansion and separated differences. The proof is essentially due to Louveau, and it yields at the same time a new proof of a theorem of Van Wesep (namely, that every non-selfdual Wadge class can be expressed as the result of a Hausdorff operation applied to the open sets). The exposition is self-contained, except for facts from classical descriptive set theory.