𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Provably total functions of Basic Arithmetic

✍ Scribed by Saeed Salehi

Publisher
John Wiley and Sons
Year
2003
Tongue
English
Weight
134 KB
Volume
49
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

It is shown that all the provably total functions of Basic Arithmetic BA, a theory introduced by Ruitenburg based on Predicate Basic Calculus, are primitive recursive. Along the proof a new kind of primitive recursive realizability to which BA is sound, is introduced. This realizability is similar to Kleene's recursive realizability, except that recursive functions are restricted to primitive recursives.

πŸ“œ SIMILAR VOLUMES

On Ξ£1-definable Functions Provably Total
On Σ1-definable Functions Provably Total in I ∏
✍ Teresa Bigorajska πŸ“‚ Article πŸ“… 1995 πŸ› John Wiley and Sons 🌐 English βš– 159 KB

We prove the following theorem: Let cp(z) be a formula in the language of the theory PAof discretely ordered commutative rings with unit of the form 3 y p ' ( z , y ) with 'p' E Ao and let f, : N -+ R be such that f,(z) = y iff cp'(z, y) & (Vz < y) ~( p ' ( z , 2 ) . If ITIF I -(Vz 2 0) cp(z), then

On the Value Distribution of Arithmetic
On the Value Distribution of Arithmetic Functions
✍ J.W Sander πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 331 KB

In part II of a series of articles on the least common multiple, the central object of investigation was a particular integer-valued arithmetic function g 1 (n). The most interesting problem there was the value distribution of g 1 (n). We proved that the counting function card[n x: g 1 (n) d ] has o

On Zeta Functions of Arithmetically Defi
On Zeta Functions of Arithmetically Defined Graphs
✍ Ortwin Scheja πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 262 KB

We study the graph X(n) that is de"ned as the "nite part of the quotient (n)!T, with T the Bruhat}Tits tree over % O ((1/ΒΉ )) and (n) the principal congruence subgroup of "GΒΈ(% We give concrete realizations of the ΒΈ-functions of the "nite part of the hal#ine !T for "nite unitary representations of