Arithmetic of divisibility in finite models
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.
- Representability of functions in finite models. Arithmetical theories
- scientific article; zbMATH DE number 3875247 (Why is no real title available?)
- 2004 Summer Meeting of the Association for Symbolic Logic
- Theories of arithmetics in finite models
- scientific article; zbMATH DE number 3933028 (Why is no real title available?)
- Division in the Theory S02+ of Bounded Arithmetic.
- Proper divisibility in computable rings
- Computer Science Logic
- Theories of initial segments of standard models of arithmetics and their complete extensions
- On decidability within the arithmetic of addition and divisibility
- The elementary theory of the natural lattice is finitely axiomatizable
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)