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 expansion.
Forcing against bounded arithmetic
17.01.2019 15:00 - 16:30
Organiser:
KGRC
Location:
SR 101, 2. St., Währinger Str. 25
Related Files
- slides 129 KB