Δ0-complexity of the relation y = Πi ⩽ nF
Annals of Pure and Applied Logic 75 (1-2):49-56 (1995)
Abstract
We prove that if G is a Δ 0 -definable function on the natural numbers and F = Π i = 0 n G , then F is also Δ 0 -definable. Moreover, the inductive properties of F can be proved inside the theory IΔ 0DOI
10.1016/0168-0072(94)00055-8
My notes
Similar books and articles
< i> Δ< sub> 0-complexity of the relation< i> y_=< i> Π_< sub> i⩽ n< i> F_(< i> i).Alessandro Berarducci & Paola D'Aquino - 1995 - Annals of Pure and Applied Logic 75 (1):49-56.
Computing the complexity of the relation of isometry between separable Banach spaces.Julien Melleray - 2007 - Mathematical Logic Quarterly 53 (2):128-131.
Complexity of networks II: The set complexity of edge‐colored graphs.Tomasz M. Ignac, Nikita A. Sakhanenko & David J. Galas - 2012 - Complexity 17 (5):23-36.
Relation algebras of every dimension.Roger D. Maddux - 1992 - Journal of Symbolic Logic 57 (4):1213-1229.
Computationally tractable pairwise complexity profile.Yaneer Bar‐Yam & Dion Harmon - 2013 - Complexity 18 (5):20-27.
Peirce on Complexity.Jaime Nubiola - 2001 - In Schmitz Walter (ed.), Proceedings of the 7th International Congress of the IASS-AIS.
Computational complexity of some Ramsey quantifiers in finite models.Marcin Mostowski & Jakub Szymanik - 2007 - Bulletin of Symbolic Logic 13:281--282.
Analytics
Added to PP
2014-01-16
Downloads
9 (#937,492)
6 months
1 (#450,993)
2014-01-16
Downloads
9 (#937,492)
6 months
1 (#450,993)
Historical graph of downloads
Citations of this work
Abelian groups and quadratic residues in weak arithmetic.Emil Jeřábek - 2010 - Mathematical Logic Quarterly 56 (3):262-278.
References found in this work
On the scheme of induction for bounded arithmetic formulas.A. J. Wilkie & J. B. Paris - 1987 - Annals of Pure and Applied Logic 35 (C):261-302.
Provability of the pigeonhole principle and the existence of infinitely many primes.J. B. Paris, A. J. Wilkie & A. R. Woods - 1988 - Journal of Symbolic Logic 53 (4):1235-1244.
Local behaviour of the chebyshev theorem in models of iδ.Paola D'Aquino - 1992 - Journal of Symbolic Logic 57 (1):12 - 27.
Local Behaviour of the Chebyshev Theorem in Models of $I\Delta_0$.Paola D'Aquino - 1992 - Journal of Symbolic Logic 57 (1):12-27.
