Δ0-complexity of the relation y = Πi ⩽ nF

&
Annals of Pure and Applied Logic 75 (1-2):49-56 (1995)
  Copy   BIBTEX

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Δ 0

Categories

Keywords

Reprint years

DOI

10.1016/0168-0072(94)00055-8

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,219

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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 and sustainability.Jennifer Wells - 2013 - New York: Routledge.
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.
Synthetic analysis: How science combats complexity.Sunny Auyang - manuscript
Relation algebras of every dimension.Roger D. Maddux - 1992 - Journal of Symbolic Logic 57 (4):1213-1229.
Complexity and postmodernism: understanding complex systems.Paul Cilliers - 1998 - New York: Routledge.
Computationally tractable pairwise complexity profile.Yaneer Bar‐Yam & Dion Harmon - 2013 - Complexity 18 (5):20-27.
Epistemic complexity from an objective bayesian perspective.Jon Williamson - 2010
Peirce on Complexity.Jaime Nubiola - 2001 - In Schmitz Walter (ed.), Proceedings of the 7th International Congress of the IASS-AIS.
Preliminary data on a relation between self-talk.A. Morin - unknown
Computational complexity of some Ramsey quantifiers in finite models.Marcin Mostowski & Jakub Szymanik - 2007 - Bulletin of Symbolic Logic 13:281--282.
Introduction to Complexity and Complex Systems.Robert B. Northrop - 2010 - Taylor & Francis.
Simply complexity: a clear guide to complexity theory.Neil F. Johnson - 2007 - Oxford: Oneworld. Edited by Neil F. Johnson.

Analytics

Added to PP
2014-01-16

Downloads
13 (#978,482)

6 months
4 (#698,851)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Iterated multiplication in $$ VTC ^0$$.Emil Jeřábek - forthcoming - Archive for Mathematical Logic.
Abelian groups and quadratic residues in weak arithmetic.Emil Jeřábek - 2010 - Mathematical Logic Quarterly 56 (3):262-278.

Add more citations

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.
Local behaviour of the chebyshev theorem in models of iδ.Paola D'Aquino - 1992 - Journal of Symbolic Logic 57 (1):12 - 27.

Add more references