Abstract

We prove that the finite‐model version of arithmetic with the divisibility relation is undecidable (more precisely, it has Π01‐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)