slideshow 3

Logic seminar

usually takes place each Monday at 14:00 in IM, rear building, ground floor
Chair: Pavel Pudlak, Neil Thapen
More information on the old seminar web page. The programme is announced via the mailing list.

An interesting (?) problem equivalent to Continuum Hypothesis

Pavel Hrubes
Institute of Mathematics
Monday, 4. June 2018 - 14:00 to 15:30
I will discuss a problem which came up in the context of machine learning, and which ended up being undecidable in ZFC. The flavor is similar to the so-called Axioms of Symmetry of Freiling. Based on a work with B. Shai-David, S. Moran, A. Shpilka, A. Yehudayoff.

Rigid models of Presburger arithmetic

Emil Jerabek
Institute of Mathematics
Monday, 28. May 2018 - 14:00 to 15:30
While all first-order theories have plenty of models with many automorphisms (e.g., saturated), models with few automorphisms are harder to come by, and their existence varies with the theory. In the extreme case of rigid models (= with no nontrivial automorphism), some theories have no rigid models at all (such as divisible ordered abelian groups), while e.g. Peano arithmetic has many: every model of PA has a rigid elementary end-extension of the same cardinality. In this talk, we will give a complete description of rigid models of Presburger arithmetic Th(Z,+,<), and its toy version Th(Z,+). As we will see, Presburger arithmetic has rigid models that are somewhat nontrivial, but it only gets so far; in particular, it has no rigid models larger than the continuum.

Hyper Natural Deduction

Arnold Beckmann
Swansea University
Monday, 21. May 2018 - 14:00 to 15:30
We introduce Hyper Natural Deduction as an extension of Gentzen's Natural Deduction system by communication like rules. The motivation is to obtain a natural deduction like system which is equivalent to Avron's Hypersequent Calculus for Goedel-Dummett Logic, and which permits natural conversion rules for normalisation as an extension of the well-known conversion rules for Natural Deduction. The ultimate goal of this project is to establish a Curry-Howard correspondence to some (yet to be found) model of parallel computation. An additional aim is to shed further light on Avron's suggestion [in A. Avron: Hypersequents, Logical Consequence and Intermediate Logics for Concurrency. Annals of Mathematics and Artificial Intelligence, 4(1991), 225-248] that a hypersequent can be thought of as a multiprocess. This is joint work with Norbert Preining, supported by a Royal Society Daiwa Anglo-Japanese Foundation International Exchanges Award #IE130639.

Proof Complexity Catch 22

Jan Krajíček
Charles University
Monday, 23. April 2018 - 14:00 to 15:30
I will present some views on the structure of proof complexity and possible research directions, illustrating them by some theorems and problems.