\(\Delta_ 0\)-complexity of the relation \(y= \prod_{i\leq n} F(i)\)
type: Item
instance of: scholarly article
title: \(\Delta_ 0\)-complexity of the relation \(y= \prod_{i\leq n} F(i)\)
zbMATH Open document ID: 0838.03042
DOI: 10.1016/0168-0072(94)00055-8
author: Alessandro Berarducci
author: Paola D'Aquino
published in: Annals of Pure and Applied Logic
publication date: 1995-11-05T00:00:00Z
review text: The authors prove that if \(G\) is a \(\Delta_0\)-definable function on the natural numbers and \(F(n)= \prod^n_{i=0} G(i)\), then \(F\) is also \(\Delta_0\)-definable. Moreover, the inductive properties of \(F\) can be proved inside that theory \(I\Delta_0\). The authors use the standard notation \(I\Delta_0\) to denote the fragment of Peano arithmetic where induction is restricted to bounded formulas (\(\Delta_0\)-formulas).
Mathematics Subject Classification ID: 03F30
zbMATH DE Number: 802546
zbMATH Keywords: induction restricted to bounded formulas
zbMATH Keywords: \(\Delta_ 0\)-definable function
zbMATH Keywords: fragment of Peano arithmetic
reviewed by: M.Tetruashvili
MaRDI profile type: Publication
full work available at URL: 0168-0072(94)00055-8
OpenAlex ID: W2008286614
cites work: Expectations for Inbreeding Depression on Self-Fertilization of Tetraploids
cites work: Local behaviour of the Chebyshev theorem in models of I⊿0
cites work: Q3962995
cites work: Q5286672
cites work: Counting $Δ_0$ sets
cites work: Q3689182
cites work: Provability of the pigeonhole principle and the existence of infinitely many primes
cites work: Q3315507
cites work: On the scheme of induction for bounded arithmetic formulas
cites work: Rudimentary Predicates and Relative Computation
Recommended article: Q3197331
Recommended article: On a complexity of the formula \((A\bigvee B) \Rightarrow C\)
Recommended article: Measures related to \((\varepsilon,n)\)-complexity functions
Recommended article: Complexity of finite-variable fragments of products with K
Recommended article: Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
Recommended article: CONVERGENCE OF C0 COMPLEXITY
Recommended article: On the quantifier complexity of \(\Delta_{n+1}(T)\)-induction
Recommended article: Q4788068
Recommended article: Abstract complexity theory and the \(\Delta_{2}^{0}\) degrees
Recommended article: Towards the computational complexity of \(\mathcal{PR}^ \omega\)-terms
description: scientific article; zbMATH DE number 802546