Definability in linear fragments of Peano arithmetic III

Models of PAWednesday, March 4, 20154:50 pmGC 6300

Petr Glivický

Definability in linear fragments of Peano arithmetic III

Charles University

In this series of talks, I will provide an analysis of definable sets in models of linear arithmetics. Here, for a cardinal k, the k-linear arithmetic (LA_k) is a full-induction arithmetical theory extending Presburger arithmetic by k non-standard scalars (= unary functions of multiplication by distinguished elements). Note that each model of a linear arithmetic naturally corresponds to a discretely ordered module over the ordered ring generated by the scalars.

I will prove a quantifier elimination result (QE up to disjunctions of bounded pp-formulas) for LA_1 and give a complete characterisation of definable sets in its models. On the other hand, I will construct an example of a model of LA_2 (or any LA_k with k at least 2) where multiplication is definable on a non-standard initial segment (and thus no pp-elimination is possible). Finally, I will show that all the theories LA_k satisfy quantifier elimination (at least) up to bounded formulas.

I will mention several applications and corollaries of these results including a construction of a non-NIP ordered module, or a result on automorphisms in saturated models 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 January 30th, 2015