Friday, February 27, 20152:00 pmCUNY Logic WorkshopGC 6417

Definability in linear fragments of Peano arithmetic

Petr Glivický

Charles University

Petr Glivický

In this talk, I will give an overview of recent results on linear arithmetics with main focus on definability in their models. Here, for a cardinal k, the k-linear arithmetic (LAk) is a full-induction arithmetical theory extending Presburger arithmetic by k non-standard scalars (= unary functions of multiplication by distinguished elements). The hierarchy of linear arithmetics lies between Presburger and Peano arithmetics and stretches from tame to wild.

I will present a quantifier elimination result for LA1 and give a complete characterisation of definable sets in its models. On the other hand, I will construct an example of a model of LA2 (or any LAk with k at least 2) where multiplication is definable on a non-standard initial segment (and thus no similar quantifier elimination is possible).

There is a close connection between models of linear arithmetics and certain discretely ordered modules (as each model of a linear arithmetic naturally corresponds to a discretely ordered module over the ordered ring generated by the scalars) which allows to construct wild (e.g. non-NIP) ordered modules. On the other hand, the quantifier elimination result for LA1 implies interesting properties of the structure of saturated models of Peano arithmetic.

Slides from this talk.

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.