✦ LIBER ✦

Some subrecursive versions of Grzegorczyk's Uniformity Theorem

✍ Scribed by Dimiter Skordev

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

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A theorem published by A. Grzegorczyk in 1955 states a certain kind of effective uniform continuity of computable functionals whose values are natural numbers and whose arguments range over the total functions in the set of the natural numbers and over the natural numbers. Namely, for any such functional a computable functional with one function‐argument and the same number‐arguments exists such that the values of the first of the functionals at functions dominated by a given one are completely determined by their restrictions to numbers not exceeding the corresponding values of the second functional at the given function. We prove versions of this theorem for the class of the primitive recursive functionals and for the class of the elementary recursive ones. Analogous results can be proved for many other subrecursive classes of functionals. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)

📜 SIMILAR VOLUMES

Uniform versions of some axioms of secon

Uniform versions of some axioms of second order arithmetic

✍ Nobuyuki Sakamoto; Takeshi Yamazaki 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB

## Abstract In this paper, we discuss uniform versions of some axioms of second order arithmetic in the context of higher order arithmetic. We prove that uniform versions of weak weak König's lemma WWKL and Σ^0^~1~ separation are equivalent to (∃^2^) over a suitable base theory of higher order arit

An Effective Version of Belyi's Theorem

✍ Lily S. Khadjavi 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 216 KB

We compute bounds on covering maps that arise in Belyi's Theorem. In particular, we construct a library of height properties and then apply it to algorithms that produce Belyi maps. Such maps are used to give coverings from algebraic curves to the projective line ramified over at most three points.

Multivariate Versions of Cochran′s Theor

Multivariate Versions of Cochran′s Theorems II

✍ C.S. Wong; T.H. Wang 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 336 KB

A general easily checkable Cochran theorem is obtained for a normal random operator \(Y\). This result does not require that the covariance, \(\Sigma_{\mathbf{r}}\), of \(Y\) is nonsingular or is of the usual form \(A \otimes 2\); nor does it assume that the mean. \(\mu\). of \(Y\) is equal to zero.

An Intuitionistic Version of Cantor's Th

An Intuitionistic Version of Cantor's Theorem

✍ Dario Maguolo; Silvio Valentini 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 163 KB 👁 1 views

An intuitionistic version of Cantor's theorem, which shows that there is no surjective function from the type of the natural numbers Af into the type N + h/ of the functions from N into N, is proved within Martin-Lijf's Intuitionistic Type Theory with the universe of the small types.

A constructive version of Birkhoff's the

A constructive version of Birkhoff's theorem

✍ Jesper Carlström 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB 👁 1 views

## Abstract A version of Birkhoff's theorem is proved by constructive, predicative, methods. The version we prove has two conditions more than the classical one. First, the class considered is assumed to contain a generic family, which is defined to be a set‐indexed family of algebras such that if

A Longest Cycle Version of Tutte's Wheel

A Longest Cycle Version of Tutte's Wheels Theorem

✍ Talmage James Reid; Haidong Wu 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 316 KB

## dedicated to professor w. t. tutte on the occasion of his eightieth birthday An edge e of a minimally 3-connected graph G is non-essential if and only if the graph obtained by contracting e from G is both 3-connected and simple. Suppose that G is not a wheel. Tutte's Wheels Theorem states that