slideshow 3

Logic seminar

usually takes place each Monday at 13:30 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.

Bounded arithmetic does not collapse to approximate counting

Neil Thapen
Institute of Mathematics
Monday, 20. November 2017 - 14:00 to 15:30
We adapt the "fixing lemma", a simple switching lemma used recently to show lower bounds for random resolution, to show that Jerabek's theory of approximate counting does not prove the CPLS principle. This settles an open problem by showing that bounded arithmetic is strictly stronger than approximate counting, if we compare the strength of theories by looking at their \forall \Sigma^b_1 consequences.

A Ramsey theorem for Metric spaces

Jonathan Verner
Charles University
Monday, 13. November 2017 - 14:00 to 15:30
We use the following variation of the standard Hungarian arrow notation which takes into account additional structure: Let K be a class of structures and kappa,lambda,nu be cardinals. The arrow kappa ->_K (lambda)^1_mu, is shorthand for the statement that for every X in K of size lambda there is a Y in K of size kappa such that for any partition of Y into mu-many pieces one of the pieces contains an isomorphic copy of X. In the talk we will investigate this arrow in the case where K is the class of bounded metric spaces with isomorphic copies being scaled copies. We extend previous work on these questions (e.g. Komjath (1987), Nesetril(2006), Komjath (1987b), Weiss (1990)).

Incompleteness in the finite domain, Part 2

Pavel Pudlák
Institute of Mathematics
Monday, 16. October 2017 - 14:00 to 15:30
The title is just a new name for what I used to call "feasible incompleteness". In this lecture I will recall some basic old results and mention some new developments in this field.

Incompleteness in the finite domain

Pavel Pudlák
Institute of Mathematics
Monday, 9. October 2017 - 14:00 to 15:30
The title is just a new name for what I used to call "feasible incompleteness". In this lecture I will recall some basic old results and mention some new developments in this field.

Pages