Linear fragments of PA – beyond LA_1

Models of PAWednesday, May 6, 20154:50 pmGC 6300

Petr Glivický

Linear fragments of PA – beyond LA_1

Charles University

I will continue my series of talks on linear fragments of PA. Nevertheless, this talk will be mostly self contained.

In my previous talks, I paid attention almost exclusively to the case of the linear arithmetic LA_1 – a reduct of PA containing only unary multiplication by one distinguished element (scalar) instead of the complete binary multiplication. It was shown that LA_1 is a rather tame theory with most of the properties similar to those of Presburger arithmetic (model completeness, decidability, existence of non-standard recursive models, NIP, …).

In this talk, I will start to examine linear arithmetics with more then one scalar. Starting with LA_2 (two scalars) already, the picture changes dramatically – I will construct a model of LA_2 where a “Peano multiplication” is definable on an infinite initial segment. On the other hand, the quantifier elimination does not fail completely in linear arithmetics with more than one scalar – I will show that all linear arithmetics satisfy bounded QE.

I will summarize the results of this and previous talks in an almost complete characterization of linear fragments of PA which are/aren’t model complete.

If time permits, I will show some applications (in particular a result on (in)dependence of values of multiplication in different points in a saturated model of PA).

Petr Glivický is a Researcher at Charles University in Prague, in the Department of Theoretical Computer Science and Mathematical Logic, where he received his doctorate in 2013 as a student of Josef Mlček. His research interests include model theory, Peano Arithmetic, and non-standard analysis.

Posted by on May 3rd, 2015