✦ LIBER ✦

Arithmetic of divisibility in finite models

✍ Scribed by Marcin Mostowski; Anna E. Wasilewska

Publisher: John Wiley and Sons
Year: 2004
Tongue: English
Weight: 110 KB
Volume: 50
Category: Article
ISSN: 0044-3050
DOI: 10.1002/malq.200310086

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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)

📜 SIMILAR VOLUMES

Generic cuts in models of arithmetic

✍ Richard Kaye 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 188 KB

## Abstract We present some general results concerning the topological space of cuts of a countable model of arithmetic given by a particular indicator __Y__. The notion of “indicator” is de.ned in a novel way, without initially specifying what property is indicated and is used to de.ne a topologi

Nonstandard models that are definable in

Nonstandard models that are definable in models of Peano Arithmetic

✍ Kazuma Ikeda; Akito Tsuboi 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 183 KB

## Abstract In this paper, we investigate definable models of Peano Arithmetic PA in a model of PA. For any definable model __N__ without parameters in a model __M__, we show that __N__ is isomorphic to __M__ if __M__ is elementary extension of the standard model and __N__ is elementarily equivalen

Finite Arithmetic Subgroups of GLn, II

✍ Marcin Mazur 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 172 KB

ON AUTOMORPHISMS OF RESPLENDENT MODELS O

ON AUTOMORPHISMS OF RESPLENDENT MODELS OF ARITHMETIC

✍ Zofia Seremet 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 225 KB

In this paper we show theorems concerning automorphisms of models of Peano Arithmetic. These results were obtained by KOTLARSKI [ 2 ] , 5 4 (as K~TLARSKI informed the author, at least part of these results were obtained by ALENA VENCOVSKA (unpublished) and CRAIG SMORYNSKI [4]). KoTLARbKI asked the a

Interstitial and pseudo gaps in models o

Interstitial and pseudo gaps in models of Peano Arithmetic

✍ Ermek S. Nurkhaidarov 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 111 KB 👁 1 views

In this paper we study the automorphism groups of models of Peano Arithmetic. Kossak, Kotlarski, and Schmerl [9] shows that the stabilizer of an unbounded element a of a countable recursively saturated model of Peano Arithmetic M is a maximal subgroup of Aut(M ) if and only if the type of a is selec

On the Finite-Precision Implementation o

On the Finite-Precision Implementation of Arithmetic Codes

✍ Shaw-Min Lei 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 439 KB

Arithmetic coding is a powerful lossless data compression technique that has attracted much attention in recent years. It provides more flexibility and better efficiency than the celebrated Huffman coding does. In this paper, we discuss many issues on the finite-precision implementation of arithmeti