Premium
Arithmetic of divisibility in finite models
Author(s) -
Mostowski Marcin,
Wasilewska Anna E.
Publication year - 2004
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.200310086
Subject(s) - divisibility rule , undecidable problem , mathematics , natural number , finite set , class (philosophy) , set (abstract data type) , relation (database) , multiplication (music) , discrete mathematics , pure mathematics , combinatorics , decidability , computer science , mathematical analysis , database , artificial intelligence , programming language
We prove that the finite‐model version of arithmetic with the divisibility relation is undecidable (more precisely, it has Π 0 1 ‐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)