We recall the notions of weak and strong Euler characteristics on a first order structure and make explicit the notion of a Grothendieck ring of a structure. We define partially ordered Euler characteristic and Grothendieck ring and give a characterization of structures that have non-trivial partially ordered Grothendieck ring. We give a generalization of counting functions to locally finite structures, and use the construction to show that the Grothendieck ring of the complex numbers contains as a subring the ring of integer polynomials in continuum many variables. We prove the existence of a universal strong Euler characteristic on a structure. We investigate the dependence of the Grothendieck ring on the theory of the structure and give a few counter-examples. Finally, we relate some open problems and independence results in bounded arithmetic to properties of particular Grothendieck rings.

§1. Overview. Philosophers and mathematicians have drawn lots of conclusions from Gödel's incompleteness theorems, and related results from mathematical logic. Languages, minds, and machines figure prominently in the discussion. Gödel's theorems surely tell us something about these important matters. But what?

A descriptive title for this paper would be “Gödel, Lucas, Penrose, Turing, Feferman, Dummett, mechanism, optimism, reflection, and indefinite extensibility”. Adding “God and the Devil” would probably be redundant. Despite the breath-taking, whirlwind tour, I have the modest aim of forging connections between different parts of this literature and clearing up some confusions, together with the less modest aim of not introducing any more confusions.

I propose to focus on three spheres within the literature on incompleteness. The first, and primary, one concerns arguments that Gödel's theorem refutes the mechanistic thesis that the human mind is, or can be accurately modeled as, a digital computer or a Turing machine. The most famous instance is the much reprinted J. R. Lucas [18]. To summarize, suppose that a mechanist provides plans for a machine, M, and claims that the output of M consists of all and only the arithmetic truths that a human (like Lucas), or the totality of human mathematicians, will ever or can ever know. We assume that the output of M is consistent.

Logicism is a thesis about the foundations of mathematics, roughly, that mathematics is derivable from logic alone. It is now widely accepted that the thesis is false and that the logicist program of the early 20th century was unsuccessful. Frege's [1893/1903] system was inconsistent and the Whitehead and Russell [1910–1913] system was not thought to be logic, given its axioms of infinity, reducibility, and choice. Moreover, both forms of logicism are in some sense non-starters, since each asserts the existence of objects (courses of values, propositional functions, etc.), something which many philosophers think logic is not supposed to do. Indeed, the tension in the idea underlying logicism, that the axioms and theorems of mathematics can be derived as theorems of logic, is obvious: on the one hand, there are numerous existence claims among the theorems of mathematics, while on the other, it is thought to be impossible to prove the existence of anything from logic alone. According to one well-received view, logicism was replaced by a very different account of the foundations of mathematics, in which mathematics was seen as the study of axioms and their consequences in models consisting of the sets described by Zermelo-Fraenkel set theory (ZF). Mathematics, on this view, is just applied set theory.

We announce two new dichotomy theorems for Borel equivalence relations, and present the results in context by giving an overview of related recent developments.

§1. Introduction. For X a Polish (i.e., separable, completely metrizable) space and E a Borel equivalence relation on X, a (complete) classification of X up to E-equivalence consists of finding a set of invariants I and a map c : X → I such that xEy ⇔ c(x) = c(y). To be of any value we would expect I and c to be “explicit” or “definable”. The theory of Borel equivalence relations investigates the nature of possible invariants and provides a hierarchy of notions of classification.

The following partial (pre-)ordering is fundamental in organizing this study. Given equivalence relations E and F on X and Y, resp., we say that E can be Borel reduced to F, in symbols

if there is a Borel map f : X → Y with xEy ⇔ f(x)Ff(y). Then if is an embedding of X/E into Y/F, which is “Borel” (in the sense that it has a Borel lifting).

Intuitively, E ≤BF might be interpreted in any one of the following ways:

(i) The classi.cation problem for E is simpler than (or can be reduced to) that of F: any invariants for F work as well for E (after composing by an f as above).

(ii) One can classify E by using as invariants F-equivalence classes.

(iii) The quotient space X/E has “Borel cardinality” less than or equal to that of Y/F, in the sense that there is a “Borel” embedding of X/E into Y/F.

This paper gives a brief survey of current research on the complexity of the constraint satisfaction problem over fixed constraint languages.

§1. Introduction. The classical propositional calculus has an undeserved reputation among logicians as being essentially trivial. I hope to convince the reader that it presents some of the most challenging and intriguing problems in modern logic.

Although the problem of the complexity of propositional proofs is very natural, it has been investigated systematically only since the late 1960s. Interest in the problem arose from two fields connected with computers, automated theorem proving and computational complexity theory. The earliest paper in the subject is a ground-breaking article by Tseitin [62], the published version of a talk given in 1966 at a Leningrad seminar. In the three decades since that talk, substantial progress has been made in determining the relative complexity of proof systems, and in proving strong lower bounds for some restricted proof systems. However, major problems remain to challenge researchers.

The present paper provides a survey of the field, and of some of the techniques that have proved successful in deriving lower bounds on the complexity of proofs. A major area only touched upon here is the proof theory of bounded arithmetic and its relation to the complexity of propositional proofs. The reader is referred to the book by Buss [10] for background in bounded arithmetic. The forthcoming book by Krajíček [40] also gives a good introduction to bounded arithmetic, as well as covering most of the basic results in complexity of propositional proofs.

After giving a brief overview of the renewal of interest in logic and the foundations of mathematics in Göttingen in the period 1914-1921, I give a detailed presentation of the approach to the foundations of mathematics found in Behmann's doctoral dissertation of 1918, Die Antinomie der transfiniten Zahl und ihre Auflösung durch die Theorie von Russell und Whitehead. The dissertation was written under the guidance of David Hilbert and was primarily intended to give a clear exposition of the solution to the antinomies as found in Principia Mathematica. In the process of explaining the theory of Principia, Behmann also presented an original approach to the foundations of mathematics which saw in sense perception of concrete individuals the Archimedean point for a secure foundation of mathematical knowledge. The last part of the paper points out an important numbers of connections between Behmann's work and Hilbert's foundational thought.

§1. Iterated Gödelian extensions of theories. The idea of iterating ad infinitum the operation of extending a theory T by adding as a new axiom a Gödel sentence for T, or equivalently a formalization of “T is consistent”, thus obtaining an infinite sequence of theories, arose naturally when Godel's incompleteness theorem first appeared, and occurs today to many non-specialists when they ponder the theorem. In the logical literature this idea has been thoroughly explored through two main approaches. One is that initiated by Turing in his “ordinal logics” (see Gandy and Yates [2001]) and taken very much further in Feferman's work on transfinite progressions, which also introduced the more general study of extensions by reflection principles, of which consistency statements are a special case. This approach starts from an assignment of theories to ordinal notations, and extracts sequences of theories through a suitable choice of a path in the set of ordinal notations. The second approach, illustrated in particular by the work of Schmerl and Beklemishev, starts instead from a suitably well-behaved primitive recursive well-ordering, which is used to define a sequence of theories. This second approach has led to precise results about the relative proof-theoretical strength of sequences of theories obtained by iterating different reflection principles. The Turing-Feferman approach, on the other hand, lends itself well to an investigation in qualitative and philosophical terms of the relevance of such iterated reflection extensions to mathematical knowledge, in particular because of two developments associated with this approach.

We show that each of the five basic theories of second order arithmetic that play a central role in reverse mathematics has a natural counterpart in the language of nonstandard arithmetic. In the earlier paper [3] we introduced saturation principles in nonstandard arithmetic which are equivalent in strength to strong choice axioms in second order arithmetic. This paper studies principles which are equivalent in strength to weaker theories in second order arithmetic.

We try to answer the question which is the “right” foundation of mathematics, second order logic or set theory. Since the former is usually thought of as a formal language and the latter as a first order theory, we have to rephrase the question. We formulate what we call the second order view and a competing set theory view, and then discuss the merits of both views. On the surface these two views seem to be in manifest conflict with each other. However, our conclusion is that it is very difficult to see any real difference between the two. We analyze a phenomenonwe call internal categoricity which extends the familiar categoricity results of second order logic to Henkin models and show that set theory enjoys the same kind of internal categoricity. Thus the existence of non-standard models, which is usually taken as a property of first order set theory, and categoricity, which is usually taken as a property of second order axiomatizations, can coherently coexist when put into their proper context. We also take a fresh look at complete second order axiomatizations and give a hierarchy result for second order characterizable structures. Finally we consider the problem of existence in mathematics from both points of view and find that second order logic depends on what we call large domain assumptions, which come quite close to the meaning of the axioms of set theory.

We consider tautologies formed from a pseudo-random number generator, defined in Krajíček [11] and in Alekhnovich et al. [2]. We explain a strategy of proving their hardness for Extended Frege systems via a conjecture about bounded arithmetic formulated in Krajíček [11]. Further we give a purely finitary statement, in the form of a hardness condition imposed on a function, equivalent to the conjecture.

We initiate the reverse mathematics of general topology. We show that a certain metrization theorem is equivalent to Π12 comprehension. An MF space is defined to be a topological space of the form MF(P) with the topology generated by {Np ∣ p ϵ P}. Here P is a poset, MF(P) is the set of maximal filters on P, and Np = {F ϵ MF(P) ∣ p ϵ F }. If the poset P is countable, the space MF(P) is said to be countably based. The class of countably based MF spaces can be defined and discussed within the subsystem ACA0 of second order arithmetic. One can prove within ACA0 that every complete separable metric space is homeomorphic to a countably based MF space which is regular. We show that the converse statement, “every countably based MF space which is regular is homeomorphic to a complete separable metric space,” is equivalent to . The equivalence is proved in the weaker system . This is the first example of a theorem of core mathematics which is provable in second order arithmetic and implies Π12 comprehension.

Completeness and other forms of Zorn’s Lemma are sometimes invoked for semantic proofs of conservation in relatively elementary mathematical contexts in which the corresponding syntactical conservation would suffice. We now show how a fairly general syntactical conservation theorem that covers plenty of the semantic approaches follows from an utmost versatile criterion for conservation given by Scott in 1974.

To this end we work with multi-conclusion entailment relations as extending single-conclusion entailment relations. In a nutshell, the additional axioms with disjunctions in positive position can be eliminated by reducing them to the corresponding disjunction elimination rules, which in turn prove admissible in all known mathematical instances. In deduction terms this means to fold up branchings of proof trees by way of properties of the relevant mathematical structures.

Applications include the syntactical counterparts of the theorems or lemmas known under the names of Artin–Schreier, Krull–Lindenbaum, and Szpilrajn. Related work has been done before on individual instances, e.g., in locale theory, dynamical algebra, formal topology and proof analysis.

The Loeb space construction in nonstandard analysis is applied to the theory of processes to reveal basic phenomena which cannot be treated using classical methods. An asymptotic interpretation of results established here shows that for a triangular array (or a sequence) of random variables, asymptotic uncorrelatedness or asymptotic pairwise independence is necessary and sufficient for the validity of appropriate versions of the law of large numbers. Our intrinsic characterization of almost sure pairwise independence leads to the equivalence of various multiplicative properties of random variables.

Set theory, it has been contended, developed from its beginnings through a progression of mathematical moves, despite being intertwined with pronounced metaphysical attitudes and exaggerated foundational claims that have been held on its behalf. In this paper, the seminal results of set theory are woven together in terms of a unifying mathematical motif, one whose transmutations serve to illuminate the historical development of the subject. The motif is foreshadowed in Cantor's diagonal proof, and emerges in the interstices of the inclusion vs. membership distinction, a distinction only clarified at the turn of this century, remarkable though this may seem. Russell runs with this distinction, but is quickly caught on the horns of his well-known paradox, an early expression of our motif. The motif becomes fully manifest through the study of functions of the power set of a set into the set in the fundamental work of Zermelo on set theory. His first proof in 1904 of his Well-Ordering Theoremis a central articulation containing much of what would become familiar in the subsequent development of set theory. Afterwards, the motif is cast by Kuratowski as a fixed point theorem, one subsequently abstracted to partial orders by Bourbaki in connection with Zorn's Lemma. Migrating beyond set theory, that generalization becomes cited as the strongest of fixed point theorems useful in computer science.

Section 1 describes the emergence of our guiding motif as a line of development from Cantor's diagonal proof to Russell's Paradox, fueled by the clarification of the inclusion vs. membership distinction. Section 2 engages the motif as fully participating in Zermelo's work on the Well-Ordering Theorem and as newly informing on Cantor's basic result that there is no bijection . Then Section 3 describes in connection with Zorn's Lemma the transformation of the motif into an abstract fixed point theorem, one accorded significance in computer science.

Paul Cohen's method of forcing, together with Saul Kripke's related semantics for modal and intuitionistic logic, has had profound effects on a number of branches of mathematical logic, from set theory and model theory to constructive and categorical logic. Here, I argue that forcing also has a place in traditional Hilbert-style proof theory, where the goal is to formalize portions of ordinary mathematics in restricted axiomatic theories, and study those theories in constructive or syntactic terms. I will discuss the aspects of forcing that are useful in this respect, and some sample applications. The latter include ways of obtaining conservation results for classical and intuitionistic theories, interpreting classical theories in constructive ones, and constructivizing model-theoretic arguments.

We provide an introduction to methods and recent results on infinitely generated abelian groups with decidable word problem.

Introduction. Il est bien connu que la correspondance de Curry-Howard permet d'associer un programme, sous la forme d'un λ-terme, à toute preuve intuitionniste, formalisée dans le calcul des prédicats du second ordre (voir, par exemple [3]). Cette correspondance a été étendue, assez récemment, à la logique classique moyennant une extension convenable du λ-calcul (voir [1, 4, 5, 6]). Chaque théorème formalisé en logique du second ordre correspond donc à une spécification de programme.

Il se pose alors le problème, en général tout à fait non trivial, de trouver la spécification associée à un théorème donné; autrement dit, de déterminer le comportement opérationnel commun aux λ-termes associés aux diverses démonstrations formelles du théorème considéré.

Cette question est résolue ici pour le théorème de complétude de la logique classique.

La première étape consiste à formaliser convenablement ce théorème en logique du second ordre. Ce travail est fait complètement dans la section 1. Il a comme sous-produit, peut-être inattendu, de montrer que ce théorème est prouvable en logique intuitionniste du second ordre (section 2). Ceci, toutefois, à condition d'introduire une légère variante de la notion de modèle, en admettant un modèle supplémentaire trivial, où toute formule est satisfaite.

On notera, à ce sujet, que des preuves intuitionnistes du théorème de complétude de la logique intuitionniste, utilisant des variantes de la notion de modele de Kripke, ont été données par H. Friedman [7] et W. Veldman [8]. On remarquera également qu'un argument de G. Kreisel [2] montre que le théorème de complétude habituel de la logique intuitionniste n'a pas de preuve intuitionniste.

The present paper investigates the power of proper forcings to change the shape of the universe, in a certain well-defined respect. It turns out that the ranking among large cardinals can be used as a measure for that power. However, in order to establish the final result I had to isolate a new large cardinal concept, which I dubbed “remarkability.” Let us approach the exact formulation of the problem—and of its solution—at a slow pace.

Breathtaking developments in the mid 1980s found one of its culminations in the theorem, due to Martin, Steel, and Woodin, that the existence of infinitely many Woodin cardinals with a measurable cardinal above them all implies that AD, the axiom of determinacy, holds in the least inner model containing all the reals, L(ℝ) (cf. [6[, p. 91). One of the nice things about AD is that the theory ZF + AD + V = L(ℝ) appears as a choiceless “completion” of ZF in that any interesting question (in particular, about sets of reals) seems to find an at least attractive answer in that theory (cf., for example, [5] Chap. 6). (Compare with ZF + V = L!) Beyond that, AD is very canonical as may be illustrated as follows.

Let us say that L(ℝ) is absolute for set-sized forcings if for all posets P ∈ V, for all formulae ϕ, and for all ∈ ℝ do we have that

where is a name for the set of reals in the extension.

In a lecture manuscript written around 1961 (Gödel *1961/?), Gödel describes a philosophical path from the incompleteness theorems to Husserl's phenomenology. It is known that Gödel began to study Husserl's work in 1959 and that he continued to do so for many years. During the 1960s, for example, he recommended the sixth investigation of Husserl's Logical Investigations to several logicians for its treatment of categorial intuition (Wang 1997, p. 164). While Gödel may not have been satisfied with what he was able to obtain from philosophy and Husserl's phenomenology, he nonetheless continued to recommend Husserl's work to logicians as late as the 1970s. In this paper I present and discuss the kinds of arguments that led Gödel to the work of Husserl. Among other things, this should help to shed additional light on Gödel's philosophical and scientific ideas and to show to what extent these ideas can be viewed as part of a unified philosophical outlook. Some of the arguments that led Gödel to Husserl's work are only hinted at in Gödel's 1961 paper, but they are developed in much more detail in Gödel's earlier philosophical papers (see especially 1934, *193?, 1944, 1947, *1951, *1953/59). In particular, I focus on arguments concerning Hilbert's program and an early version of Carnap's program.

§1. Some ideas from phenomenology. Since Husserl's work is not generally known to mathematical logicians, it may be helpful to mention briefly a few details about his background.