Arithmetic of divisibility in finite models

From MaRDI portal





The paper concerns (Finite Model) FM-domains, a notion of representability in such domains and a notion interpretability of one domain in another. For a finite set \(R\) of recursive relations on \(\omega\), the FM-domain of \(R\) is the collection of the restrictions of the relations in \(R\) to the finite domains \(\{0,\dots,n-1\}\). A relation \(A\) is FM-representable in a FM-domain \(X\), if there is a formula \(\varphi(\bar x)\) of the language of \(X\) such that for any tuple \(\bar a\), \(A(\bar a )\) holds iff \(M\models\varphi(\bar a)\) for all \(M\) in \(X\) of sufficiently large cardinality. The other notion is a suitably defined notion of (Initial Segment) IS-interpretability between two FM-domains. The main result of the paper is that the FM-domain of the structure \((\omega, +,\times)\) is IS-interpretable in the FM-domain of \((\omega, | )\), where \(| \) is the divisibility relation. As a corollary of this and other results of the paper, it is shown that that the relations which are FM-representable in the domain of divisibility are exactly the FM-representable relations, and that the first-order theory of the FM-domain of divisibility is undecidable (in fact it is \(\Pi^0_1\)-complete). The results are obtained with the help of some elementary number theory, which is used to interpret addition and multiplication on initial segments of the divisibility relation.











This page was built for publication: Arithmetic of divisibility in finite models

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