The lattice problem
The City University of New York
Ordered by inclusion, the set of elementary substructures of a model of PA is a lattice.
It is an ℵ1-compactly generated lattice, meaning that every element of the lattice is a supremum of its compact elements, and for every compact element, there are at most countably many compact elements below it. The lattice problem for models of PA is to determine which lattices can be represented as lattices of elementary substructures of a model of PA. The condition above puts a restriction on the types of lattices that can be represented this way. As far as we know, this can be the only restriction. Much work on the problem has been done in the 1970s by Gaifman, Knight, Mills, Paris, Schmerl, and Wilkie, and has been continued by Schmerl. It involves some specialized knowledge of models of PA, highly nontrivial lattice representation theory, combinatorics, and sometimes number theory. There are many positive results, but we still do not know if there is a finite lattice which cannot be represented as a substructure lattice of a model of PA. My talk will be an introduction to the lattice problem. I’ll introduce basic definitions and I’ll prove a couple of introductory negative results.
Roman Kossak is professor of mathematics at The City University of New York, at Bronx Community College and also at the CUNY Graduate Center. He conducts research in mathematical logic, especially in model theory of Peano Arithmetic.