Premium
A wild model of linear arithmetic and discretely ordered modules
Author(s) -
Glivický Petr,
Pudlák Pavel
Publication year - 2017
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.201600012
Subject(s) - unary operation , mathematics , peano axioms , second order arithmetic , quantifier elimination , presburger arithmetic , arithmetic , scalar multiplication , multiplication (music) , discrete mathematics , scalar (mathematics) , algebra over a field , pure mathematics , combinatorics , decidability , geometry
Linear arithmetics are extensions of Presburger arithmetic ( Pr ) by one or more unary functions, each intended as multiplication by a fixed element (scalar), and containing the full induction schemes for their respective languages. In this paper, we construct a model M of the 2‐linear arithmetic LA 2 (linear arithmetic with two scalars) in which an infinitely long initial segment of “Peano multiplication” on M is ⌀ ‐definable. This shows, in particular, that LA 2 is not model complete in contrast to theories LA 1 andLA 0 = Pr that are known to satisfy quantifier elimination up to disjunctions of primitive positive formulas. As an application, we show that M , as a discretely ordered module over the discretely ordered ring generated by the two scalars, does not have the NIP, answering negatively a question of Chernikov and Hils.