Logic Seminar, Petr Glivicky (Charles University): 'Definability in linear fragments of Peano Arithmetic'

Monday, April 27, 2015
4:45 PM - 6:00 PM (ET)
ESC 638
Event Type
Academic Calendar
Philip Scowcroft, x2185
Math CS Logic Seminar

Abstract: 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.

Get Directions
Event Date
Event Time