It is known that rational approximations of elementary analytic functions (exp, log, trigonometric and hyperbolic functions, and their inverse functions) are computable in the complexity class TC^0. In this talk, we will show how to formalize their construction and basic properties in the correspoding arithmetical theory VTC^0, working with completions of fraction fields of models of VTC^0. As a consequence, we will show that every countable model of VTC^0 is an exponential integer part of a real-closed exponential field, using a recursive saturation argument.
Logic seminar
usually takes place each Monday at 16:00 in IM, rear building, ground floorChair: Pavel Pudlak, Neil Thapen, Jan Krajíček
More information on the old seminar web page. The programme is announced via the mailing list.
Elementary analytic functions in VTC^0
Emil Jeřábek
IM CAS
Monday, 17. October 2022 - 16:00 to 17:30
Compactness and incompactness in set theory, with applications to uncountable graphs
Chris Lambie-Hanson
IM CAS
Monday, 26. September 2022 - 16:00 to 17:30
(Joint seminar with set theory group)
The study of compactness phenomena at uncountable cardinals has been a central line of research in combinatorial set theory since the mid-twentieth century. In the first part of this talk, we will give a broad overview of this area of research and survey some of its most prominent results. We will then look at a few recent results concerning compactness phenomena for uncountable graphs. We first look at possible generalizations of the de Bruijn-Erdos compactness theorem for chromatic numbers to uncountable cardinalities, in particular showing that consistently there are large uncountable graphs witnessing extreme failures of compactness for, e.g., the property of having a countable chromatic number. We then turn to the study of the structure of the collections of finite subgraphs of uncountably chromatic graphs, answering a question of Erdos, Hajnal, and Szemeredi about the growth rates of chromatic numbers in such collections of... more
The study of compactness phenomena at uncountable cardinals has been a central line of research in combinatorial set theory since the mid-twentieth century. In the first part of this talk, we will give a broad overview of this area of research and survey some of its most prominent results. We will then look at a few recent results concerning compactness phenomena for uncountable graphs. We first look at possible generalizations of the de Bruijn-Erdos compactness theorem for chromatic numbers to uncountable cardinalities, in particular showing that consistently there are large uncountable graphs witnessing extreme failures of compactness for, e.g., the property of having a countable chromatic number. We then turn to the study of the structure of the collections of finite subgraphs of uncountably chromatic graphs, answering a question of Erdos, Hajnal, and Szemeredi about the growth rates of chromatic numbers in such collections of... more
On the Conjectures of Razborov and Rudich
Rahul Santhanam
University of Oxford
Monday, 23. May 2022 - 16:00 to 17:30
We say that Rudich's Conjecture holds for a propositional proof system Q if there are no efficient Q-proofs of random truth table tautologies. We say that Razborov's Conjecture holds for a propositional proof system Q if there are no efficient Q-proofs of any truth table tautologies. A fundamental task in proof complexity and the meta-mathematics of circuit lower bounds is to understand for which Q these conjectures hold. We show various results about these conjectures, including evidence for their difficulty.
Based on joint work with Jan Pich.
In search of the first-order part of Ramsey's theorem for pairs
Leszek Kołodziejczyk
University of Warsaw
Monday, 16. May 2022 - 16:00 to 17:30
Reverse mathematics studies the logical strength of mathematical theorems formalized as statements in the language of second-order arithmetic (which is a two-sorted language with one sort of variables for natural numbers and another for sets of natural numbers). The strength is usually measured in terms of implications between the theorems and some set existence axioms, but it also makes sense to ask about the first-order consequences of a theorem, that is, what statements about natural numbers it implies.
In recent decades, a particularly interesting case study has been provided by RT^2_2: Ramsey's theorem for pairs and two colours. RT^2_2 and its variants are anomalous in the sense of not being equivalent to any of the typical set existence axioms considered in reverse mathematics, or to each other. Characterizing the first-order part of RT^2_2 is a long-standing and highly interesting open problem. Methods used to make progress on this problem have typically been based on some... more