Moritz Müller: Forcing against bounded arithmetic

BARCELONA RESEARCH GROUP IN SET THEORY

BARCELONA SET THEORY SEMINAR

Forcing against bounded arithmetic

Moritz Müller

Universitat Politècnica de Catalunya

Abstract: We study the following problem. Given a nonstandard
model of arithmetic we want to expand it by a binary relation that
does something prohibitive, e.g. violates the pigeonhole principle in
the sense that it is the graph of a bijection from n+1 onto n for
some (nonstandard) n in the model. The goal is to do so while
preserving as much as possible of true arithmetic. More precisely,
we want the expansion to model the least number principle for a
class of formulas as large as possible. The problem is of central
importance in bounded arithmetic and propositional proof
complexity. It is not well understood. The talk describes a general
method of forcing to produce such expansions.

Date: Thursday 7 February 2019
Time: 16:00

Place: Room S-1*
Departament de Matemàtiques i Informàtica
Universitat de Barcelona
Gran Via de les Corts Catalanes 585, 08007 Barcelona

* Enter the University building through the door 20 meters to the right of the
main door and, as you enter the courtyard, turn left, go to the end of the
corridor, and then downstairs.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.

This site uses Akismet to reduce spam. Learn how your comment data is processed.