COLLOQUIUM LOGICUM 2004Biannual Meeting of the German Society for Mathematical Logic (DVMLG)September 17  19, 2004Heidelberg (Germany)
LIST OF TALKS WITH ABSTRACTS
ABSTRACTS
Albert Atserias (Universitat Politècnica de Catalunya, Barcelona): The complexity of random 3SAT: a survey and new results Abstract: The random model of 3CNF formulas parallels that of random graphs and provides a nice framework for studying the averagecase complexity 3SAT. 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.
Philipp Gerhardy (TU Darmstadt): Strongly uniform bounds from semiintuitionistic 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 semiintuitionistic counterparts to the classical metatheorems, where the semiintuitionistic setting is intuitionistic analysis extended with certain nonconstructive principles, such as e.g. comprehension for arbitrary negated formulas. Finally, we discuss some advantages and disadvantages of the classical and the semiintuitionistic 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$.
Bjørn KjosHanssen (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 nonrecursive functions (DNR functions) are presented, e.g., a sequence truthtable 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 prooftheoretic 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 nonuniform 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, quasinonexpansive 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 PAindependence 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/nslides1.ps ) Amador MartinPizarro (HumboldtUniversitä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 MordellLang 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 ManinMumford conjecture for semiabelian 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.
Jan Reimann (Universität Heidelberg): Hausdorff dimension, randomness, and entropy Abstract: MartinLö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 nonintegral 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 MartinLö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 DMVconference)
Abstract: (joint work with Laura Crosilla and Hajime Ishihara) Peter Schuster (Universität München): Algebra and geometry in firstorder 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 firstorder 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 localglobal 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.
