Celebrating 90 Years of Gödel's Incompleteness Theorems
The conference is a hybrid event, taking place online and in Nürtingen (Germany) from 5 to 9 July 2021.
Topics
The topics of the conference comprise all areas of logic relating in a narrower or wider sense to Gödel's incompleteness results. This includes the history of logic, proof theory, philosophy of mathematics, aspects of incompleteness in computer science and others.
The conference is organised as a collection of workshops for these specific topics.
Participation
If you would like to participate online, please write to Marcel Ertel events.cfvwz to receive the Zoom link. @listserv.uni-tuebingen.de
In memoriam
On April 26, 2021 Thomas Strahm, a dear friend and close colleague of the organizers and many participants of this meeting, passed away at the age of 57 after prolonged health problems. His research was in the best tradition of Gödel's work and we will remember him at this meeting. You find an obituary at the University of Bern.
Related Workshop
On August 16-20, 2021 a related online workshop on Gödel's Incompleteness Theorems will be organized by the School of Philosophy, Wuhan University.
Programme overview
- 5.7. Monday afternoon: Opening. Higher proof theory after Gödel
- 6.7. Tuesday morning: Type theory in type theory
- 6.7. Tuesday afternoon: Computation in face of incompleteness
- 7.7. Wednesday morning: Cut-elimination and Herbrand's Theorem
- 7.7. Wednesday afternoon: Provability predicates
- 8.7. Thursday morning: Diagonalisation
- 8.7. Thursday afternoon: Recursion-theoretic approaches to computation and complexity
- 9.7. Friday morning: Philosophy of mathematics after Gödel
- 9.7. Friday afternoon: Aspects of Gödel's unpublished work; Closing Lecture by Jan von Plato
Workshop programmes
Times are CEST.
5.7. Monday afternoon
Higher proof theory after Gödel
Organisers: Reinhard Kahle (University of Tübingen) and Michael Rathjen (University of Leeds)
13:00-13:45 Gerhard Jäger (University of Bern): Remembering Thomas Strahm
Remembering Thomas Strahm
Gerhard Jäger (University of Bern):
A brief overview of Thomas Strahm’s scientific activities and the impact of his work will be given.
13:45-14:30 Anton Setzer (Swansea University): Formalising the extended predicative Mahlo universe in the context of Martin- Löf Type Theory
Formalising the extended predicative Mahlo universe in the context of Martin-Löf Type Theory
Anton Setzer (Swansea University):
In previous talk (joint work with Reinhard Kahle) we have presented the extended predicative Mahlo universe, which allows to give a more predicative formalisation of the Mahlo universe in the setting of Feferman's system of Explicit Mathematics.
In this talk we formalise explicit mathematics using Martin-Löf extended by inductive recursive definitions. We formulate the construction in the theorem prover Agda based on Martin-Löf Type Theory. The formalisation is slightly adapted to be in accordance with the setting of Martin-Löf Type Theory. We will see that this formalisation doesn't entirely remove the underlying problem, for the formalisation of the extended predicative Mahlo universe itself we need non strictly positive inductive definitions. This is to be expected since when iterating this construction, which is possible, we would go beyond the strength inductive-recursive definitions.
14:30-15:15 Anton Freund (Technical University of Darmstadt): A Uniform Picture of Gap Condition and Collapsing Functions
A Uniform Picture of Gap Condition and Collapsing Functions
Anton Freund (Technical University of Darmstadt):
As Gödel showed, in any formal theory for the foundations of mathematics, there are concrete statements that can neither be proved nor
refuted. Mathematical examples of such statements include Kruskal's tree theorem and its strengthening by a gap condition, as shown by H. Friedman. These mathematical independence results are intimately connected to ordinal analysis. The present talk presents a new and very uniform picture of this connection: First, Kruskal's theorem and the Bachmann-Howard ordinal arise by the same construction, applied to partial and linear orders, respectively. Secondly, by iterating this construction, we obtain the gap condition and ordinal collapsing functions. The talk aims to explain the grand lines of this picture in an accessible way. Parts of it are based on joint work with M. Rathjen and A. Weiermann.
15:15-15:45 Coffee break
15:45-16:30 Wolfram Pohlers (University of Münster): On the performance of axiom systems. Set universes
On the performance of axiom systems.
Set universes
Wolfram Pohlers (University of Münster):
One of the aims of proof theory is to characterize axiom systems by invariants. Due to Gödel’s second incompleteness theorem it is to be expected that such invariants are unlikely to be finite. Pioneering work in this directions had then been done by Gerhard Gentzen who characterized the axiom system for Peano Arithmetic by the transfinite ordinal ε0. Our aim is to investigate in how far proof–theoretic or- dinals can serve as measures for the performance of axiom system with respect to their intended standard models. The key observation is the “No Enhancement Theorem” which states that the proof–theoretic ordinal of an axiom system will not grow, even if we strengthen it by arbitrary sentences of the elementary diagram of its standard model. Thus the Peano axioms and D(ℕ), the elementary diagram of ℕ augmented by the scheme of Mathematical Induction, share the proof–theoretic ordinal ε0 although D(ℕ) should know everything about ℕ which, due to Gödel, cannot be true for the Peano axioms.
This indicates that the proof–theoretic ordinal of an axiom system A can hardly be a measure for the performance of A with respect to its standard model. It turns out that it rather measures the performance of A with respect to “universes above” its intended standard model. So called impredicative axiom systems axiomatize more than just one universe above its standard model and thus induce a spec- trum of proof–theoretic ordinals. In a previous paper (which will appear in the volume Axiomatic Thinking II, Springer 2021) we studied axiom systems in the language of arithmetic and their spectra in “analytical universes”, i.e. universes whose sets are sets of natural numbers. In the present talk we will indicate how to extend these studies to axiom systems for set theory and set theoretical—especially admissible—universes. We obtain a bridge to abstract α–recursion theory in so far, that the spectra of the investigated axiom systems contain exactly the ordinals which are closed under the α–recursive functions whose totality is provable in the axiom system.
16:30-17:15 Annika Kanckos (University of Helsinki): Strong Normalization of Gödel's T
Strong Normalization of Gödel's T
Annika Kanckos (University of Helsinki)
Following (Wilken &) Weiermann's proofs of SN of Gödel's T the main problems with SN can be located to the λ-formulation of T and the generality of the recursor reductions in the successor case. These problems typically lead to a non-unique (ordinal) number assignment showing termination. We will, based on an observation of how to implement Howard's permutation lemma, sketch how a unique assignment can be constructed for the full system T.
17:15-18:00 Harvey Friedman (Ohio State University): Gödel's Incompleteness Theorems
Harvey Friedman (Ohio State University)
6.7. Tuesday morning
Type theory in type theory
Organsiers: Roberta Bonacina (University of Tübingen) and Peter Schuster (University Verona)
8:00-8:45 Peter Dybjer (University of Gothenburg): A Note on Generalized Algebraic Theories and Categories with Families
A Note on Generalized Algebraic Theories and Categories with Families
Peter Dybjer (University of Gothenburg):
We give a new syntax independent definition of the notion of a finitely presented generalized algebraic theory as an initial object in a category of categories with families (cwfs) with extra structure. To this end we define inductively how to build a valid signature Σ for a generalized algebraic theory and the associated category CwF_Σ of cwfs with a Σ-structure and cwf-morphisms that preserve Σ-structure on the nose. Our definition refers to the purely semantic notions of uniform family of contexts, types, and terms. Furthermore, we show how to syntactically construct initial cwfs with Σ-structures. This result can be viewed as a generalization of Birkhoff’s completeness theorem for equational logic. It is obtained by extending Castellan, Clairambault, and Dybjer’s construction of an initial cwf. We provide examples of generalized algebraic theories for monoids, categories, categories with families, and categories with families with extra structure for some type formers of dependent type theory. The models of these are internal monoids, internal categories, and internal categories with families (with extra structure) in a category with families. Finally, we show how to extend our definition to some generalized algebraic theories that are not finitely presented, such as the theory of contextual categories with families.
This is joint work with Marc Bezem, Thierry Coquand, and Martin Escardo.
8:45-9:30 Thorsten Altenkirch (University of Nottingham): Incompleteness in Type Theory
Incompleteness in Type Theory
Thorsten Altenkirch (University of Nottingham):
I am discussing the issue of Leibniz incompleteness in Type Theory: we have two objects that satisfy the same properties, i.e. are indistinguishable but which cannot be shown to be equal. For example in Intensional Type Theory, extensionally equal functions cannot shown to be equal but they also cannot be distinguished. A more interesting example is the fact that isomorphic types cannot be distinguished but also cannot be shown equal (this also applies to Extensional Type Theory). The latter can be addressed by Voevodsky's univalence principle. This raises the question wether HoTT is Leibniz complete.
9:30-10:00 Coffee break
10:00-10:45 Ambrus Kaposi (Eötvös-Loránd-University): Levels of abstraction when defining type theory in type theory
Levels of abstraction when defining type theory in type theory
Ambrus Kaposi (Eötvös-Loránd-University):
There are multiple levels of abstraction in which one can encode the syntax of type theory inside type theory. These include Gödel numbers, lists of lexical elements, abstract syntax trees, well-scoped syntax trees, well-typed syntax trees, well-typed syntax trees quotiented by the conversion relation, higher order abstract syntax. In this talk I will present these encodings, discuss their relationships, discuss which properties of the syntax can be proven at which level, and explain what features of type theory are needed to use them.
10:45-11:30 Bruno Barras (Laboratoire Spécification et Vérification): Type Theory in Set Theory, in Type Theory
Type Theory in Set Theory, in Type Theory
Bruno Barras (Laboratoire Spécification et Vérification):
This talk is about encoding Type Theory in Type Theory via a translation to Set Theory. This breaks embeddings of Type Theory in itself in two steps: (1) a set-theoretical model of Type Theory, and (2) a representation of sets in Type Theory. Those mutual encodings gives results on the relative strength of type and set theories.
We first recall previous works, such as Aczel's Constructive Zermelo Frankel (CZF) that corresponds to predicative type theories. Werner has shown that ZFC (Zermelo Fraenkel with Choice) plus a hierarchy of inaccessible cardinals corresponds to the Calculus of Inductive Constructions (CIC) extended with 2 axioms.
The goal of our work is to find a restriction of intuitionistic ZF (IZF) such that we have a correspondence with impredicative type theories like CIC. For this purpose, we introduce IZF with functional replacement and well-founded recursion as a good candidate, and we discuss the issues related to the correspondence between type-theoretic universes and set-theoretical Grothendieck universes (or inaccessible cardinals).
11:30-12:15 Peter LeFanu Lumsdaine (Stockholm University): Comparing general definitions of type theories
Comparing general definitions of type theories
Peter LeFanu Lumsdaine (Stockholm University):
In recent years, several authors have introduced quite general definitions of dependent type theories. A major goal is to allow a more unified study of type theories and their models, with theorems and constructions proven in a precise and broad generality, instead of (as currently) given for specific individual type theories and adapted to others as needed.
- Uemura (arXiv:1904.04097) gives an abstract categorical definition, *categories with representable maps*, together with a syntactic definition based on logical frameworks.
- Bauer–Haselwarter–Lumsdaine (arXiv:2009.05539) give a concrete syntactic definition, not LF-based (using Fiore-Plutkin-Turi or similar syntax with binding), and have also formalised this definition in Coq. A similar definition was independently given by Brunerie (unpublished).
- Isaev (arXiv:1602.08504) gives an essentially-algebraic definition
I will concisely present these definitions, and survey the connections between them.
12:15-13:30 Lunch break
13:30-14:15 Thierry Coquand (University of Gothenburg): Internal Models of Type Theory
Internal Models of Type Theory
Thierry Coquand (University of Gothenburg):
The notion of definitional equality plays an important role in the formulation of dependent type theory. This makes it difficult to build models (e.g. Kleisli models) of type theory in an intensional framework, where one would like to see the model construction as a purely syntactical transformation of the type systems into itself.
In the past 10 years however, several internal models have been built, such as the parametricity and exception models.
Some class of nominal/presheaf models, where restriction maps are substitutions, also preserve the intensional character of type theory, and I will explain how this internal model technique can be used to build various models of univalence in an intensional and constructive setting.
6.7. Tuesday afternoon
Computation in face of incompleteness
Organisers: Roberta Bonacina (University of Tübingen) and Peter Schuster (University Verona)
14:15-15:00 Ulrich Berger (Swansea University): From Brouwer’s Thesis to the Fan Functional
Ulrich Berger (Swansea University): From Brouwer's Thesis to the Fan Functional
15:00-15:30 Coffee break
15:30-16:15 Ulrich Kohlenbach (TU Darmstadt): From Gödel's incompleteness theorems and foundational reductions to applications in core mathematics
From Gödel's incompleteness theorems and foundational reductions to applications in core mathematics
Ulrich Kohlenbach (TU Darmstadt):
Gödel's 2nd incompleteness theorem established that Hilbert's program to prove the consistency of arithmetic, analysis and even set theory by finitistic means, cannot be carried out globally. However, Gödel himself achieved important foundational reductions to reduce e.g. the consistency of classical number theory to that of intuitionistic number theory (Gödel 1933) and of the latter to that of a quantifier-free calculus of primitive recursive functionals of finite types which had been first defined by Hilbert in 1926 (Gödel 1941,1958).
These foundational reductions have (with many subsequent extensions and adaptations) been used during the last two decades in the systematic program of 'proof mining', i.e. the extraction of new effective data such as bounds from prima facie noneffective proofs, in a number of areas of core mathematics. Extended case studies have revealed that whole areas of e.g. nonlinear analysis are largely based on proofs which actually do have a computational content of low and (with very few exceptions) at most primitive recursive complexity. This shows that locally large parts of ordinary mathematics in fact do allow for a 'finitization' as Hilbert had envisaged.
We will sketch some of the reasons for this proof-theoretic tameness often observed in ordinary mathematics and present recent - essentially polynomial - rates of convergence extracted from proofs in geodesic geometry and nonsmooth optimization respectively.
16:15-17:00 Daniel Wessel (LMU Munich): Spectra and radicals
Spectra and radicals
Daniel Wessel (LMU Munich):
Radical theory offers rich tools to encode properties of rings and their modules through suitable classes of ideal objects. By analogy, we discuss spectra that arise from non-deterministic axioms over complete lattices, and break down the corresponding radicals into their constituent parts. The intention is twofold: complement the approach taken in dynamical algebra, and contribute to a revised Hilbert programme.
This talk is partly based on joint work with Peter Schuster.
17:00-17:45 Stefan Neuwirth (Université de Franche-Comté): Paul Lorenzen's reception of Gödel's incompleteness theorems
Paul Lorenzen's reception of Gödel's incompleteness theorems
Stefan Neuwirth (Université de Franche-Comté):
7.7. Wednesday morning
Cut-elimination and Herbrand's Theorem
Organisers: Matthias Baaz (TU Wien) and Anela Lolic (TU Wien)
8:15-9:00 Anela Lolic (TU Wien): Proof Analysis with CERES
Proof Analysis with CERES
Anela Lolic (TU Wien)
The method CERES is an efficient cut-elimination method based on resolution and has beendefined for various proof calculi. The original method was constructed for classical first-order logic, and the result of CERES (a proof in atomic cut normalform) was used for proof analysis by the extraction of variations of Herbrand's theorem.
The method CERES has been extended to several logics, and the proof analysis methods have been considerably simplified by extracting the Herbrand information from proofs that are not in normalform. In fact, it was shown that the Herbrand information can be obtained from the cut-free parts of a proof, which are represented by the so-called projections in the CERES method.
The most recent development was the extension of the methods to classical first-order logic with induction. Using the proof analysis methods for CERES it was possible to define a structure representing a variant of Herbrand's theorem.
9:00-9:45 Jan Bydzovsky (TU Wien): The Number of Axioms
The Number of Axioms
Jan Bydzovsky (TU Wien)
Following Goedel's incompleteness theorem no recursive notion of a proof can be efficient enough to ensure that every provable first-order formula A is also provable by a proof its length is recursively bounded in the number of symbols in A. However, this does not directly give much inside into the structure of long proofs when a particular proof system is fixed. I will comment on a new result together with Juan P. Aguilera and Matthias Baaz that for cut-free sequent calculus one of the sources of hardness to prove a formula is the number of (instances) of the axioms one needs to use. I will also comment on what the situation is for sequent proofs with cuts and sequent proofs from theories like Robinson arithmetic, PA or ZFC.
9:45-10:15 Coffee break
10:15-11:30 Yong Cheng (Wuhan University): The landscape of Gödel's incompleteness theorems
The landscape of Gödel's incompleteness theorems
Yong Cheng (Wuhan University)
In the first part of the talk, we will give a brief overview of recent
research on Gödel's incompleteness theorems from the following aspects: (1)
the influence of Gödel's incompleteness theorems on foundations of
mathematics, philosophy and mathematics; (2) different proofs of Gödel's
incompleteness theorems; (3) generalizations of Gödel's incompleteness
theorems; (4) the limit of the applicability of the first incompleteness
theorem (G1); (5) the intensionality problem of Gödel's second incompleteness
theorem (G2).
In the second part of the talk, we will focus on our recent work of finding
the limit of the first incompleteness theorem (G1) w.r.t. interpretation. We
examine the interpretation degree structure of weak r.e. theories for which
G1 hold, and especially on the question whether there is a minimal r.e. theory
for which G1 holds. We find that the answers depend on the signature of
language and the class of theories we consider.
Video of the talk
References:
Yong Cheng, Incompleteness for Higher-Order Arithmetic: An Example Based on
Harrington's Principle, Springer series: Springerbrief in Mathematics,
Springer, 2019.
Yong Cheng, Finding the limit of incompleteness I.
Bulletin of Symbolic Logic, Volume 26, Issue 3-4, December 2020, pp. 268-286.
Yong Cheng, Current research on Gödel's incompleteness theorem, online in The
Bulletin of Symbolic Logic, DOI: 10.1017/bsl.2020.44, 2021.
11:30-12:15 Lorenzo Sauras (TU Wien): Generalization of arithmetical proofs
Generalization of arithmetical proofs
Lorenzo Sauras (TU Wien):
In this talk, I will explain how to apply Baaz’s generalization method to proofs of universal sentences from elementary number theory. This procedure has resulted to have a considerable potential in revealing arithmetical patterns, that got reflected in theorems (for example, sufficient conditions for a value to be a divisor of an arbitrary Fermat number) and conjectures (mainly about integer sequences).
12:15-13:30 Lunch break
7.7. Wednesday afternoon
Provability predicates
Organisers: Reinhard Kahle (University of Tübingen) and Paulo Santos (FCT NOVA, University of Tübingen)
13:30-14:15 Albert Visser (Utrecht University): Provability according to Kreisel, Löb, Feferman
Provability according to Kreisel, Löb, Feferman
Albert Visser (Utrecht University):
In this talk, I discuss three sets of conditions for being a provability predicate: the Kreisel Condition, the Löb Conditions, and Feferman’s Framework for Provability. We review the conditions, have a look at some separating examples and, briefly, discuss the role and place of the sets of conditions.
Secondly, we present the result that every consistent RE theory extending Peano Arithmetic has a provability predicate satisfying all three sets of conditions. We show that this predicate is part of an interesting bi-modal logic. We discuss some applications of the result. If there is still time, we have a brief look at its proof.
14:15-15:00 Taishi Kurahashi (Kobe University): On the second incompleteness theorem and provability predicates
On the second incompleteness theorem and provability predicates
Taishi Kurahashi (Kobe University)
Gödel's second incompleteness theorem states that every consistent computably axiomatized theory containing Peano Arithmetic cannot prove a sentence claiming the consistency of the theory. This statement is of course ambiguous in that it does not specify what a sentence claiming the consistency of a theory is. In this talk, we investigate relationships between several versions of the second incompleteness theorem and the derivability conditions for provability predicates.
15:00-15:30 Coffee break
15:30-16:15 Reinhard Kahle (University of Tübingen): The Formalized Consistency Statement Revisited
The Formalized Consistency Statement Revisited
Reinhard Kahle (University of Tübingen)
We discuss the limitations of the standard formalization of consistency (of a theory T) when it is supposed to express the consistency of T.
16:15-17:00 Paulo Santos (FCT NOVA, University of Tübingen): Numeral Completeness
Numeral Completeness
Paulo Santos (FCT NOVA, University of Tübingen)
We will present a numeral completeness result that holds for weak theories of arithmetic; more precisely, we are going to prove that, starting from a true sentence, one can express the fact that the sentence is true inside the weak theory using numerals. As an immediate consequence, we will obtain a numeral form of provable consistency. The third main result that we will present shows that there is a primitive recursive function (we will see that this function can also be Kalmar elementary) that outputs, for each n, a proof that n is not a proof of a contradiction in a fixed consistent theory. We will relate our result with late versions of Hilbert's Program.
17:00-17:45 Sergei Artemov (Graduate Center, CUNY): Missing Proofs and the Provability of Consistency
Missing Proofs and the Provability of Consistency
Sergei Artemov (Graduate Center, CUNY):
We argue that there is a class of widely used and readily formalizable arithmetical proofs of universal properties which are not accounted for in the traditional unprovability of consistency analysis.
On this basis, we offer a mathematical proof of consistency for Peano Arithmetic PA and demonstrate that this proof is formalizable in PA. This refutes the wide spread belief that there exists no consistency proof of a system that can be formalized in the system itself. Gödel’s Second Incompleteness theorem yields that PA cannot derive the consistency formula ConPA. This does not interfere with our formalized proof of PA-consistency which is not a derivation of the consistency formula ConPA.
8.7. Thursday morning
Diagonalisation
Organisers: Reinhard Kahle (University of Tübingen) and Paulo Santos (FCT NOVA, University of Tübingen)
8:45-9:30 Saeed Salehi (University of Tabriz): The Diagonalization Lemma — Demystified Hopefully
The Diagonalization Lemma — Demystified Hopefully
Saeed Salehi (University of Tabriz):
The diagonal lemma says that when a computable and injective Gödel coding # is available from the formulas to the closed terms of a fixed language, then for every formula F(x), with x as the only free variable, there exists a sentence S such that S ↔ F(#S) holds. Holding may mean that the above equivalence is true in the standard model of natural numbers (the semantic diagonal lemma) or may mean that the equivalence is provable in a sufficiently strong theory such as Robinson's Arithmetic (the syntactic diagonal lemma).
The so-called lemma, first proved by Gödel (1931) for a particular formula F(x), that of unprovability, and explicated by Carnap (1934) for every formula F, has a (couple of) very short but extremely tricky and easy-to-forget proof(s). The (classical) proof is mysterious and a kind
of magical (pulling a rabbit out of a hat), which adds to the confusion on and about the lemma. It can be even said that once this lemma has been mastered and grasped, then the proofs of the theorems of Gödel's first incompleteness, Tarski's undefinability of truth, and Rosser's (strengthening of Gödel's) incompleteness can be easily understood.
In this talk we will give some alternative proofs for the semantic form of this lemma and for its weak syntactic forms. We will see that the lemma is actually equivalent, in a sense, to the above mentioned theorems of Gödel, Tarski, and Rosser. These new results, we hope, will help us in demystifying this wonderful and prolific lemma; though its classic proof may remain in shadow, our new proofs will hopefully shed some light on the true nature of the diagonal lemma.
Video of the talk
References
· SAEED SALEHI, On the Diagonal Lemma of Gödel and Carnap, The
Bulletin of Symbolic Logic 26:1 (2020) 80—88.
· SAEED SALEHI, Tarski’s Undefinability Theorem and the Diagonal
Lemma, Logic Journal of the IGPL (forthcoming).
9:30-10:00 Coffee break
10:00-10:45 Paulo Santos (FCT NOVA, University of Tübingen): Yablo's Paradox Revisited
Yablo's Paradox Revisited
Paulo Santos (FCT NOVA, University of Tübingen)
Stephen Yablo proposed a paradox which, according to his evaluation, does not depend on self-reference. In this talk, we render Yablo’s paradox, first, by the use of an order relation, showing that it does not rely on arithmetic. Secondly, we formalise it in Linear Temporal Logic and in Modal Logic. These formalisations uncover the underlying logical structure of Yablo’s paradox.
10:45-11:30 Helen Preiß (Technical University of Darmstadt): What Replaces Diagonalisation in Boolos’ Proof of the First Incompleteness Theorem?
What Replaces Diagonalisation in Boolos’ Proof of the First Incompleteness Theorem?
Helen Preiß (Technical University of Darmstadt):
In a short note, Boolos sketched a proof of Gödel's First Incompleteness Theorem based on Berry's Paradox. He distinguishes his argumentation from Gödel's as it "does not involve diagonalization". In this talk we discuss the replacement for diagonalization Boolos is using.
11:30-12:15 Noson S. Yanofsky (Brooklyn College, CUNY): Diagonalization, Fixed Points, and Self-reference
Diagonalization, Fixed Points, and Self-reference
Noson S. Yanofsky (Brooklyn College, CUNY):
Some of the most profound and famous theorems in mathematics and computer science of the past 150 years can simultaneously be seen as a consequence of diagonalization, as a fixed-point theorem, and as an instance of a self-referential paradox. These results include Cantor's theorems about different levels of infinity; Russell's paradox; Gödel's incompleteness theorem; Turing's halting problem; and much more. Amazingly, all these diverse theorems and all viewpoints can be seen as instances of a single simple theorem of basic category theory. We describe this theorem and show some of the instances. A large part of the talk will be a discussion of diagonalization proofs, fixed point theorems, and self- referential paradoxes that fail to be an instance of this categorical theorem. We will meet another categorical idea that unifies some of these ideas. No category theory is needed for this talk.
12:15-13:30 Lunch break
8.7. Thursday afternoon
Recursion-theoretic approaches to computation and complexity
Organisers: Jean-Yves Marion (Institut universitaire de France) and Isabel Oitavem (FCT NOVA, Lisbon)
13:30-14:30 Simona Ronchi della Rocca (University of Turin): Characterising Probabilistic Termination
Characterising Probabilistic Termination
Simona Ronchi della Rocca (University of Turin):
In the probabilistic setting, termination has a double nature. Namely we speak about Almost Sure Termination (AST) in case the probability of divergence is null, and about Positive Almost Sure Termination (PAST) if the time to termination is finite. PAST implies AST but not viceversa. A powerful tool for proving program termination are intersection type assignment systems, which have been successfully applied to various kind of deterministic calculi. Here I will show how they can be tailored in order to be applied to the probabilistic case: a unique type assignment system, where the intersection is non idempotent, gives a complete characterisation of both kinds of termination. More specifically, any type derivation for a given term M supplies both a lower bound to the expected time to termination for M, and a lower bound to M’s probability of termination. The system is designed for a call-by-value lambda-calculus, enriched with a probabilistic choice, but all the results are robust and hold for the call-by-name calculus too.
14:30-15:30 Helmut Schwichtenberg (LMU Munich): Linear Two-Sorted Constructive Arithmetic
Linear Two-Sorted Constructive Arithmetic
Helmut Schwichtenberg (LMU Munich)
We consider a term system in the style of Goedel's system T together with a computation model that allows to faithfully represent
polynomial-time algorithms. To this end we follow a tradition initiated by Simmons (1988) and developed by Bellantoni and Cook (1992), where two sorts of variables are admitted, here called output and input variables. The idea is that input variables are the general ones which may be recursed on and used many times, whereas output variables cannot be recursed on and can be used only once. These ideas have been extended to a higher type setting and hence – via the Curry-Howardcorrespondence – to a linear two-sorted arithmetical system in the style of Heyting arithmetic in all finite types. Here we further extend this setup with the aim to also include certain nonlinear algorithms (like treesort), given by constants defined by equations involving multiple recursive calls.
15:30-16:00 Coffee break
16:00-17:00 Daniel Leivant (Indiana University Bloomington): Recurrence without structuralism, and the delineation of finitism and feasibility
Recurrence without structuralism, and the delineation of finitism and feasibility
Daniel Leivant (Indiana University Bloomington):
Primitive recursion is umbilically related to actual infinite totalities, viz the functions being defined. Yet Tait's Thesis (1981) identifies finitism with primitive-recursive mathematics. We start by showing that this conflict is a non-issue, by defining a generic formal theory for finite data, with a companion imperative programming language, free of implicit assumptions about actual infinities, yielding fresh strong arguments in support of Tait's Thesis.
We further refine our programming language with a ramification discipline, obtaining algorithmically broad imperative programming languages for PTime and PSpace, depending on the strictness of the ramification condition.
17:00-18:00 Sam Buss (University of California, San Diego): Gödel and the Lengths of Proofs
Gödel and the Lengths of Proofs
Sam Buss (University of California, San Diego):
The lengths of proofs and the complexity of proofs are of great interest due to its connections to complexity theory and theorem proving. Gödel was the first one to consider lengths of proofs. This talk will discuss three results in lengths of proofs related to Gödel's writings. The first is upper and lower bounds on the lengths of partial consistency statements (due to P. Pudlak and H. Friedman). The second is Gödel's separation of higher order theories of arithmetic. The third is a claim made by Gödel in a letter to von Neumann related to the question of whether P=NP.
9.7. Friday morning
Philosophy of mathematics after Gödel
Organisers: Laura Crosilla (University of Oslo) and Thomas Piecha (University of Tübingen)
8:45-9:30 Øystein Linnebo (University of Oslo): Potentialism and Critical Plural Logic
Potentialism and Critical Plural Logic
Øystein Linnebo (University of Oslo):
Potentialism is the view that certain types of entity are successively generated, in such a way that it is impossible to complete the process of generation. What is the correct logic for reasoning about all entities of some such type? Under some plausible assumptions, classical first-order logic has been shown to remain valid, whereas the traditional logic of plurals needs to be restricted. Here I seek to answer the open question of what is the correct plural logic for reasoning about such domains. The answer takes the form of a critical plural logic. An unexpected benefit of this new logic is that it paves the way for an alternative analysis of potentialism, which is simpler and more user-friendly than the extant modal analysis.
9:30-10:00 Coffee break
10:00-10:45 Mirna Džamonja (IRIF, CNRS & Université de Paris): Truth in mathematics
Truth in mathematics
Mirna Džamonja (IRIF, CNRS & Université de Paris)
Hilbert’s programme was the holy grail of logic in the late 19th century and the early 20th century. It sought to find common logical foundation to the whole of mathematics, where all the mathematical truths would be derivable from the system through a commonly accepted notion of a proof, preferably in an algorithmic manner. Gödel’s Incompleteness theorems, along with Turing’s undecidability, have put an end to this dream. Logic has been integrating that reality ever since. Logicians have learned how to deal with incompleteness, although not everybody has the same philosophical position on it.
In this talk, we shall move focus on the dual of completeness: the soundness. Formally, there is no reason to question the soundness of our proofs. Heuristically, there is an elephant in the room. Our proofs are becoming uncheckable due to their length, level of sophistication and the partition of the mathematical community into small and very specialised groups which can hardly understand the announcements of each other's theorems. The traditional system of refereeing does not seem to be sufficiently prepared, so serious journals take years to publish as the referees take years to verify and the less serious kind of journals proliferate, feeding on the « publish or perish » credo driven by financial needs of the universities.
It is difficult to propose remedies to this situation. Some of the world’s top mathematicians have noticed and have reacted: Voevodsky, Perelman, the Lean community and yours truly in a joint with Koutsoukou-Argyraki and Paulson.
All of these are tries and, in our opinion, due to the difficulty of implementation which is mostly manual, not likely to resolve the situation in real time. It seems that the soundness problems should be attacked differently. We feel that it is logic that should take over at this point. The logic should help us understand the uncertainty that high level mathematics has become.
10:45-11:30 Carlo Nicolai (King's College London): Inexhaustibility and Implicit Commitment
Inexhaustibility and Implicit Commitment
Carlo Nicolai (King's College London):
Gödel's incompleteness theorems are often taken to indicate that our mathematical commitments are inexhaustible. Soundness assertions for a mathematical theory T cannot be established in T. However, they appear to be implicit in the acceptance of T. This notion of implicit commitment is often associated with highly technical studies but it remains, so far, an elusive notion. For instance, it is often claimed that the acceptance of a mathematical theory implicitly commits one to the acceptance of a Uniform Reflection Principle for it. However, logicians and philosophers agree that a satisfactory conceptual analysis of the transition from a theory to its reflection principle is still lacking. In the talk I will survey recent proposals to analyse and justify the transition from a theory to its soundness assertions and present some new results and observations. The original material will mainly concern two ways of articulating the notion of implicit commitment: a direct axiomatization of (minimal) implicit commitment, and the analysis of implicit commitment via a primitive truth predicate.
11:30-12:15 Gabriella Crocco (Aix-Marseille Université) and Paola Cantù (CNRS): The application of mathematics in Gödel and beyond
The application of mathematics in Gödel and beyond
Gabriella Crocco (Aix-Marseille Université) and Paola Cantù (CNRS):
The question of the applicability of mathematics to the empirical sciences is crucial in Gödel's philosophy and constitutes a key problem in contemporary philosophy of mathematics. In the first part, the paper emphasizes the importance of applicability in Gödel, suggesting a new reading of Gödel's criticism to Carnap in The Logical Syntax of Language and a comparison with some passages from the unpublished philosophical notebooks Max Phil. In the second part, the paper shows that the question was already central in Frege, Helmholtz and Bettazzi and analyzes its legacy with reference to neologicism and structuralism.
Video of the talk
12:15-13:30 Lunch break
9.7. Friday afternoon
Aspects of Gödel's unpublished work
Organisers: Maria Hämeen-Anttila (University of Helsinki) and Jan von Plato (University of Helsinki)
13:30-14:15 Tim Lethen (Saarland University): Gödel's theological notes
Gödel's theological notes
Tim Lethen (Saarland University):
In the winter semester of 1937/38, Gödel attended about 30 theological lectures, taking notes which are preserved in his Nachlass in Princeton. These notes are supplemented by an extensive list of theological literature as well as by two lists of literally hundreds of remarks and questions concerning the Catholic Church, the Bible, dogmatics, and theology in general.
The talk will present passages from these sources and attempt to shed light on two of Gödel's main theological concerns. The first one focuses on the idea of formalising theology by capturing a few basic terms and concepts, which are then fixed by a set of axioms and developed into a theory by appropriate rules of inference. In a second approach, Catholic dogmas take on the role of axioms, thus allowing – for example – for a logical investigation of differences between the Western and Eastern Church.
Finally, the talk will present material – recently discovered in Gödel's Nachlass – which reveals his remarkably intensive biblical studies.
14:15-15:00 Miloš Adžić (University of Belgrade): Gödel’s Introduction to Deduction: Logic Lectures at Notre Dame
Gödel’s Introduction to Deduction: Logic Lectures at Notre Dame
Miloš Adžić (University of Belgrade):
Gödel taught a one-semester course in basic logic at the University of Notre Dame in the spring of 1939. Among his unpublished writings in the Princeton University Library one can find notebooks with the manuscript of his notes for that course. Together with Kosta Došen, we have prepared an edition of the notes of which we will offer a brief summary and address some of their importance. We will also comment upon parts of Gödel’s manuscript unavailable to us previously, which were only recently brought to our attention by Jan von Plato.
15:00-15:30 Coffee break
15:30-16:15 Maria Hämeen-Anttila (University of Helsinki): Gödel’s functional interpretation in context
Gödel’s functional interpretation in context
Maria Hämeen-Anttila (University of Helsinki):
Gödel’s functional interpretation of intuitionistic arithmetic was first introduced in a 1958 article published in the journal Dialectica under the title “Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes”. However, the interpretation itself was first discovered by Gödel in 1941, when he was preparing a lecture course on intuitionistic logic at Princeton.
The main sources for the interpretation that Gödel calls ∑ are the Princeton lecture notes, another lecture (“In what sense is intuitionistic logic constructive?”) given in Yale in April 1941, as well as shorthand notes in the notebook series Arbeitshefte and, to a lesser extent, Resultate Grundlagen. In my presentation, I will discuss the historical development of the functional interpretation based on the lecture notes and the shorthand notebooks. The aim is to give a general idea of what there is to be found in the fragmentary notes contained in the Arbeitshefte series, and how they might be used to better understand the early functional interpretation and the problems Gödel encountered while working on it.
16:15-17:00 Akihiro Kanamori (Boston University): The Set Theory in Gödel’s Resultate Grundlagen
The Set Theory in Gödel’s Resultate Grundlagen
Akihiro Kanamori (Boston University):
Most of the four notebooks of Gödel’s 1940-1942 Resultate Grundlagen have to do with set theory, and we find here incisive work of remark- able breadth and depth, much of it replicating the best results achieved at the time or anticipating major avenues of research later. Especially conspicuous are his constructions of an Aronszajn tree and a paradoxical decomposition of the sphere, his formulation of relative constructibility and pointwise definability leading to minimal models, his results in Ramsey-type infinite combinatorics, and his exploration of scales of orders of growth in connection with the Contin- uum Hypothesis. On this last, we now see that his intriguing 1970 remarks on the continuum problem had definite anticipations here.
17:00-18:00 Jan von Plato (University of Helsinki): Gödel's first steps in logic: From Carnap's axiomatic exercises to incompleteness
Gödel's first steps in logic: From Carnap's axiomatic exercises to incompleteness
Jan von Plato (University of Helsinki)
Recent findings in the Gödel papers show that his active involvement with logical questions began with Carnap's "Axiomatics exercises" in the summer of 1928, with formalizations of second-order arithmetic, Hilbert's geometry, and point set topology. These show already the effect of Hilbert-Ackermann's book, from which he then found the completeness problem, solved by the end of January 1929. The extension of completeness to higher-order logic failed but led instead, from early summer 1930 to November, to the now famous incompleteness article published 90 years ago.
Organization
The conference is organized by:
- Carl Friedrich von Weizsäcker Center
- Kurt Gödel Society
- the ERC-funded project Gödel Enigma: Rediscovering Kurt Gödel through his unpublished works, headed by Jan von Plato
Programme committee
Matthias Baaz, Reinhard Kahle, Thomas Piecha, Jan von Plato