Arithmetic of divisibility in finite models | Zendy

Mostowski Marcin | Zendy; Wasilewska Anna E. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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)

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research