Mathematical Logic Quarterly 50 (2):169 (2004)

Marcin Mostowski
Jagiellonian University
We prove that the finite-model version of arithmetic with the divisibility relation is undecidable . Additionally we prove FM-representability theorem for this class of finite models. This means that a relation R on natural numbers can be described correctly on each input on almost all finite divisibility models if and only if R is of degree ≤0′. We obtain these results by interpreting addition and multiplication on initial segments of finite models with divisibility only
Keywords Finite model  undecidability  FM‐representability  IS‐interpretability  arithmetical definability  divisibility relation  FM‐domain
Categories (categorize this paper)
DOI 10.1002/malq.200310086
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 54,608
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Theories of Arithmetics in Finite Models.Michał Krynicki & Konrad Zdanowski - 2005 - Journal of Symbolic Logic 70 (1):1-28.
2004 Summer Meeting of the Association for Symbolic Logic.Wolfram Pohlers - 2005 - Bulletin of Symbolic Logic 11 (2):249-312.

Add more citations

Similar books and articles

Theories of Arithmetics in Finite Models.Michał Krynicki & Konrad Zdanowski - 2005 - Journal of Symbolic Logic 70 (1):1-28.
Arithmetic of Divisibility in Finite Models.Andrzej Mostowski - 2004 - Mathematical Logic Quarterly 50:169-174.
Undecidability of Representability as Binary Relations.Robin Hirsch & Marcel Jackson - 2012 - Journal of Symbolic Logic 77 (4):1211-1244.
Arithmetical Definability Over Finite Structures.Troy Lee - 2003 - Mathematical Logic Quarterly 49 (4):385.
On Representing Concepts in Finite Models.Marcin Mostowski - 2001 - Mathematical Logic Quarterly 47 (4):513-523.
Forcing in Finite Structures.Domenico Zambella - 1997 - Mathematical Logic Quarterly 43 (3):401-412.
Inconsistent Models of Arithmetic Part I: Finite Models. [REVIEW]Graham Priest - 1997 - Journal of Philosophical Logic 26 (2):223-235.


Added to PP index

Total views
14 ( #668,401 of 2,385,937 )

Recent downloads (6 months)
1 ( #555,436 of 2,385,937 )

How can I increase my downloads?


My notes