COLLOQUIUM LOGICUM 2004
Biannual Meeting of the German Society for Mathematical Logic (DVMLG)
September 17 - 19, 2004
Heidelberg (Germany)
LIST OF TALKS WITH ABSTRACTS
ABSTRACTS
Albert Atserias (Universitat Politècnica de Catalunya, Barcelona): The complexity of random 3-SAT: a survey and new results
Abstract: The random model of 3-CNF formulas parallels that of random graphs and provides a nice framework for studying the average-case complexity 3-SAT. We overview some of the known results in the area and announce some new results from the descriptive complexity front.
Stefan Bold (Universiteit van Amsterdam): A simple inductive argument to compute more Kleinberg sequences under the Axiom of Determinacy
Abstract: A characteristic feature of infinitary combinatorics under the Axiom of Determinacy is the existence of sequences of partition cardinals, called Kleinberg sequence. It is well known that there are lots of Kleinberg sequences below $\aleph_{\boldsymbol{\varepsilon}_0}$, but the exact values of their elements is still unknown. In this note, we give a simple inductive argument that allows to compute the Kleinberg sequences corresponding to the $\omega_1$-cofinal measures on the odd projective ordinals without doing any detailed ultrapower analyses.
Patrick Braselmann and Peter Koepke (Universität Bonn): A formal proof of the Gödel completeness theorem
Abstract: The Gödel completeness theorem is the fundamental theorem of formal logic and the foundation for automatic proof checking and automatic proving. It is therefore natural to ask for a formal proof of Gödel's theorem. We have recently completed a formal proof of the theorem in the system MIZAR (www.mizar.org). The proof follows the presentation of the standard textbook Mathematical Logic by H.D. Ebbinghaus et al. In our talk we shall present various aspects of the formalization.
S. Barry Cooper (University of Leeds): Incomputability, fifty years after Alan Turing
Abstract: For mathematicians, the main significance of the work of Goedel, Church and Turing in the 1930s was its negative impact on Hilbert's programme. In practical terms though, Turing's 1936 paper (setting out the intimate relationship between computable and incomputable phenomena) became an important step towards an ongoing implementation of that programme. Only recently have researchers from areas beyond computability theory returned to Turing's work with a new sense of the relevance of his engagement with the theoretical limitations on computation and human intelligence.
Oscar M. Esquisabel (Universidad Nacional de La Plata,Argentina): The interaction between mathematics and logic in Leibniz
Abstract: It is known that Leibniz adopts the mathematical paradigm for his attempts to renewing and expanding the scope of logic. From this point of view, algebra provides a model according to which Leibniz tries to construct logical calculi that are designed for improving the performance of logical reasoning. In this sense we may speak of a "mathematization" of logic in Leibniz thought. However, concerning the foundations of mathematics, Leibniz holds a program that can be considered in some extent as "logicist", that is, mathematics must be founded on logical concepts and principles. Moreover, in opposition to an "intuitionistic" view about mathematics, Leibniz defends the idea that mathematical reasoning receives its cogency from structural properties. In this sense, it can be said that in Leibniz' thought there is a mutual interdependence between logic and mathematics. This paper tries to summarize the way in which Leibniz' develops such an interrelation. At the same time, limits that Leibniz imposes on such interdependence are examined.
Gunter Fuchs (Universität Münster): Degrees of rigidity for Souslin trees
Abstract: We introduce and investigate a range of notions of rigidity for
(Souslin) trees. Many of these are concerned with forcing extensions
by the tree. Thus, e.g., T is absolutely rigid if it is rigid in every
forcing extension by T. The fact that Souslin trees, viewed as notions
of forcing, are c.c.c. (and even $\omega_1$-distributive) makes it
very natural to investigate these degrees of rigidity in connection
with Souslin trees. We show the consistency of the various rigidity
levels (assuming Jensen's Diamond Principle) and investigate the mutual
relationships between them.
This is joint work with Joel David Hamkins.
Philipp Gerhardy (TU Darmstadt): Strongly uniform bounds from semi-intuitionistic proofs
Abstract: In 2003, Kohlenbach proved very general logical metatheorems for the extraction of effective uniform bounds from classical, ineffective proofs in functional analysis, covering arbitrary abstract metric and normed linear spaces. Furthermore, the metatheorems allow to prove very general uniformities, i.e. the independence of extracted bounds from parameters ranging over not necessarily compact bounded metric spaces and bounded convex subsets of normed linear spaces, even without having to carry out the extraction. We present semi-intuitionistic counterparts to the classical metatheorems, where the semi-intuitionistic setting is intuitionistic analysis extended with certain non-constructive principles, such as e.g. comprehension for arbitrary negated formulas. Finally, we discuss some advantages and disadvantages of the classical and the semi-intuitionistic approach respectively.
Joost Joosten (University of Utrecht): Worms, interpretations and proof strength
Abstract: This talk consists of two parts. In the first part we
will study Beklemishevs approach to natural ordinal notation
systems. His approach is based on graded provability algebras
and makes extensively use of closed modal formulae. We shall
focus on the universal model of the closed fragment of GLP; a
modal semantics of depth $\epsilon_0$.
The second part of the talk is devoted to relativized
interpretability as a tool for proof-strength comparison. Our
main interest will be in the calculation of interpretability
logics.
Bjørn Kjos-Hanssen (University of Connecticut, Storrs) and Wolfgang Merkle (Universität Heidelberg): Recent results on the complexity of the prefixes of random and DNR sequences
Abstract: The talk shortly reviews dclassical and more recent results on the Kolmogorov complexity of the prefixes of random sequences. Furthermore, characterizations of sequences that compute diagonally non-recursive functions (DNR functions) are presented, e.g., a sequence truth-table computes a DNR function if and only if there is a computable lower bound on the complexity of the prefixes of this sequence.
Ulrich Kohlenbach (TU Darmstadt): Applications of logic to nonlinear functional analysis
Abstract: We discuss recent proof-theoretic techniques for extracting effective uniform bounds from large classes of ineffective existence proofs in functional analysis. "Uniform" here refers to the independence of the bounds from parameters in bounded (not necessarily compact!) metric spaces and selfmappings of such spaces among others. We prove general logical metatheorems and show how they can be applied. These theorems guarantee strong uniform versions of non-uniform existence theorems and provide algorithms for actually extracting effective uniform bounds. They deal with general classes of spaces (metric spaces, hyperbolic spaces, CAT(0)-spaces, normed linear spaces, uniformly convex and inner product spaces) and functions (nonexpansive, directionally nonexpansive, quasi-nonexpansive and asymptotically nonexpansive functions among others). We report on a number of concrete applications of this approach to fixed point theory where both qualitatively new uniformity results as well as new effective bounds were obtained (The talk is based in part on joint work with P. Gerhardy, B. Lambov and L. Leustean).
Branimir Lambov (TU Darmstadt): A generalization of a theorem of Matiyasevich
Abstract: This paper gives a generalization of a result by Matiyasevich which gives explicit rates of convergence for monotone recursively defined sequences. The generalization is motivated by recent developments in fixed point theory and the search for applications of proof mining to the field. It relaxes the requirement for monotonicity to the form x_{n+1} \le (1 + a_n)x_n + b_n where the parameter sequences have to be bounded in sum, and also provides means to treat computational errors. The paper also gives an example result, an application of proof mining to fixed point theory, that can be achieved by the means discussed in the paper.
Gyesik Lee (Universität Münster): Large threshold for PA-independence
Abstract: Some combinatorial assertions with a parameter function will be presented. They are variants of Friedman's $\Pi^0_2$-miniaturization. It will be shown that their provability e.g. in PA depends on how fast the given parameter function grows. Furthermore, it can be shown that there is a threshold for independence.
Javier Legris (Academia Nacional de Ciencias de Buenos Aires): The many faces of logicism. On the interrelations between symbolic logic and foundations of mathematics at the end of the 19th century
Abstract: Logicism was an influential line of thought in the foundational discussion that arose in mathematics in the second half of the 19th century. It proposed the reduction of mathematical notions to logical notions. The work of Frege and Dedekind are well known examples of this approach. Now, at that time there were different ideas about what "logical notions" should be. Sets, functions, extensions of predicates, abstract algebraic operations and relations were conceived in different opportunities as logical notions, and it did not exist a clear characterization of logic. In this paper I will try to distinguish among different forms of logicism at the end of the 19th century and to put them in connection with the evolution of symbolic logic. As a special case I will discuss Ernst Schröders work on algebra of logic and its application to foundational issues. In my opinion this case is particularly interesting because it sheds light on relevant aspects of the relation between symbolic logic and the logicist approach in foundations of mathematics.
Janos A. Makowsky (Technion Haifa / ETH Zürich): 50 years of the Spectrum Problem: History and new directions
Abstract: The slides are available at: http://www.cs.technion.ac.il/~admlogic/TR/slides.html (http://www.cs.technion.ac.il/~admlogic/TR/Kalmar/nslides-1.ps )
Amador Martin-Pizarro (Humboldt-Universität Berlin): Supersimple Fields
Abstract: Model theory studies definable sets within a
given structure. It has become an important and active area of
mathematics in the last decade. Its interactions with algebraic
geometry are worth considering. Its applications to other areas
of mathematics were underestimated until in 1996 Hrushovski gave
a proof of the Mordell-Lang conjecture for function fields valid
in all characteristics, using machinery from stability theory in
a clever way. Similarly, he was able to derive a new proof of
the Manin-Mumford conjecture for semi-abelian varities over
number fields. An active part of his results was the algebraic
characterization of $\omega$-stable fields. They were shown to
be algebraically closed by Macintyre, and later this argument
was extended to superstable fields by Cherlin and Shelah.
Following the original definition of Shelah, Kim and Pillay were
able to extend some of the machinery of Geometric Model Theory
to a wider class of theories: simple theories. Examples of
simple unstable structures are, among others, the random graph,
pseudofinite fields (shown by Chatzidakis-van den
Dries-Macintyre) and perfect pseudo-algebraically closed fields
(in short, PAC) with small absolute Galois group (shown by
Hrushovski). In 1995 Pillay conjectured that a similar
statement as in Macintyre's Theorem held: namely, supersimple
fields were PAC. So far, this conjecture is still open.
In this talk, we will present an overview of the aforementioned
topics, starting from the definition of simplicity and
stability, and comparing what tools can be carried over to the
simple case and which techniques need to be developed. Although
some content of the talk requires a certain familiarity with
objects in algebraic geometry, we will try to present it in a
self-contained way for a more general audience.
Jan Reimann (Universität Heidelberg): Hausdorff dimension, randomness, and entropy
Abstract: Martin-Löf introduced the notion of effective Lebesgue measure zero in order to define individual random binary sequences. It is possible to extend this concept to other measures, for instance Hausdorff measures. Lutz (2000) has used this approach to define the concept of effective Hausdorff dimension, which can be seen as a measure of the degree of randomness of an individual sequence. This view is supported by a close connection between Hausdorff dimension and algorithmic entropy, commonly known as Kolmogorov complexity, which emerged from works of Ryabko, Staiger, Lutz, and others. We will look at the connection between entropy and effective dimension from a computability theoretic viewpoint. For instance, we will study the question of existence of lower spans of non-integral dimension (with respect to various reducibilities). This will lead to more general questions concerning the interplay between randomness, computability, and entropy, such as the characterization of sequences which compute a Martin-Löf random sequence.
Ralf Schindler (Universität Münster): Cardinal arithmetic and determinacy
Abstract: Cardinal arithmetic is the study of the possible behavior of the continuum function, or - more generally - of cardinal exponentiation. Recent research has uncovered deep connections of cardinal arithmetic with the theory of large cardinals and with determinacy.
Peter Schuster (Universität München): On constructing completions (Talk at DMV-conference)
Abstract: (joint work with Laura Crosilla and Hajime Ishihara)
The Dedekind cuts in
an ordered set form a set in the sense of constructive Zermelo Fraenkel set
theory. We deduce this statement from the principle of refinement, which we
distill before from the axiom of fullness. Together with exponentiation,
refinement is equivalent to fullness. None of the defining properties of an
ordering is needed, and only refinement for two element coverings is used. In
particular, the Dedekind reals form a set; whence we have also refined an
earlier result by Aczel and Rathjen, who invoked the full form of fullness. To
further generalise this, we look at Richman s method to complete an arbitrary
metric space without sequences, which he designed to avoid countable choice. The
completion of a separable metric space turns out to be a set even if the
original space is a proper class; in particular, every complete separable metric
space automatically is a set.
Peter Schuster (Universität München): Algebra and geometry in first-order terms
Abstract: The concept of point in algebraic geometry is little satisfying from every cautious foundational perspective. Building upon work due to Joyal, methods to do definitions and proofs in commutative algebra entirely in first-order terms have recently been developed by Coquand, Lombardi, and others. Essentially, the idea is to pass from the Zariski spectrum to the corresponding distributive lattice. So the Krull dimension has been characterised without any talk of prime ideals, and proofs of some famous estimates for numerical invariants have been given without using any local-global principle. We briefly review this development, give some basic examples, and speculate about future applications of this approach.
Andreas Weiermann (University of Utrecht): Classifying the phase transition for independence results
Abstract: In her 1982 Science article "Does Gödel's theorem matter to mathematics?" Gina Kolata reported about celebrated independence results for first order arithmetic due to J. Paris, L. Harrington and H. Friedman. In our talk we take a closer look at these fascinating results and we will classify their underlying phase transitions from provability to unprovability. We will indicate the possible relevance of these investigations to cutting edge mathematics by indicating how these results might be used to attack longstanding open problems in Ramsey theory and analytic number theory.
|
|
|
Responsible:
Jan Reimann
|
|
Last modified: August 31, 2004
|