Arithmetic of divisibility in finite models

We prove that the finite‐model version of arithmetic with the divisibility relation is undecidable (more precisely, it has Π⁰₁‐complete set of theorems). 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. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)