Finite Substructure Lattices of Models of Peano Arithmetic

From MaRDI portal





Suppose \(N\) is an elementary extension of a model \(M\) of PA. The lattice \(\text{Lt}(M,N)\) consists of all elementary submodels of \(N\) containing \(M\), ordered by elementary extension. This lattice was first systematically investigated by \textit{H. Gaifman} in his seminal paper [``Models and types of Peano's arithmetic, Ann. Math. Logic 9, 223-306 (1976; Zbl 0332.02058)]. Gaifman's work in this direction was continued by Paris, Schmerl, and G. Mills to a very high degree of sophistication. The paper under review is a sequel to an earlier important paper of the author [``Substructure lattices of models of Peano arithmetic, Logic Colloq. '84, Stud. Logic Found. Math. 120, 225-243 (1986; Zbl 0596.03066)]. In his earlier paper the author had managed to reduce the model-theoretic question regarding the structure of \(\text{Lt}(M,N)\) to a lattice-theoretic one. More specifically, he had successfully isolated the purely lattice-theoretic property of ``possessing an \(n \text{-CPP}\) representation, where \(n\) is a natural number, to prove: Theorem. Suppose \(M\) is a countable nonstandard model of PA and \(L\) is a finite lattice. The following are equivalent: (a) There is a cofinal extension \(N\) of \(M\) such that the lattice \(\text{Lt} (M,N)\) is isomorphic to \(L\). (b) For every \(n<\omega\), \(M \models\) ``\(L\) has an \(n \text{-CPP}\) representation. Since possessing an \(n \text{-CPP}\) representation turns out to be a \(\Sigma_ 1\)-property, its truth implies its provability in PA. Therefore a key question to answer is: Which finite lattices have an \(n \text{-CPP}\) reprsentation for every \(n<\omega?\). In the author's earlier paper it was shown that many finite lattices (such as all distributive lattices, the pentagon lattice, and the 1-3-1 lattice) have an \(n \text{-CPP}\) representation for every \(n<\omega\) and it was conjectured that all finite lattices have this property. Furthermore, the 1-n-1 lattices for \(3<n<\omega\), and the hexagon lattice, were isolated as specific finite lattices which were not known to have this property. As a consequence of the results of this paper the 1-\(m\)-1 lattice, for \(m\) of the form \(p^ k+1\) (where \(p\) is a prime number), as well as the 1-7-1 lattice and the hexagon lattice, all can occur as substructure lattices. This is achieved by (a) demonstrating that these lattices possess a ``finite congruence representation, and (b) showing that if \(L\) is a finite lattice which has a finite congruence representation then for each \(n<\omega\), \(L\) has an \(n \text{-CPP}\) representation. It is still unknown whether the 1-11-1 lattice can occur as a substructure lattice.











This page was built for publication: Finite Substructure Lattices of Models of Peano Arithmetic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4695582)