A lightface analysis of the differentiability rank

DOI10.1017/JSL.2013.23MaRDI QIDQ2921032zbMATH OpenOpenAlexFDO

Authors Linda Brown Westrick

Publication date 30 September 2014

Published in The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.2975, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.743.432

zbMATH Keywords

computable analysisdifferentiabilityeffective descriptive set theoryrank functionhyperarithmetical hierarchy

Mathematics Subject Classification ID

Computation over the reals, computable analysis (03D78) Descriptive set theory (03E15)

Abstract: We examine the computable part of the differentiability hierarchy defined by Kechris and Woodin. In that hierarchy, the rank of a differentiable function is an ordinal less than omega_1 which measures how complex it is to verify differentiability for that function. We show that for each recursive ordinal alpha>0, the set of Turing indices of C[0,1] functions that are differentiable with rank at most alpha is Pi_{2 alpha + 1}-complete. This result is expressed in the notation of Ash and Knight.

Recommendations

• Ranks of differentiable functions
• Index sets for computable differential equations
• Three ordinal ranks for the set of differentiable functions
• The Complexity Of Nowhere Differentiable Continuous Functions
• On the Denjoy rank, the Kechris-Woodin rank and the Zalcwasser rank

Cites work

• A recursive function, defined on a compact interval and having a continuous derivative that is not recursive
• Computable structures and the hyperarithmetical hierarchy
• Hyperarithmetical Index Sets in Recursion Theory
• Index sets for computable differential equations
• On the Denjoy rank, the Kechris-Woodin rank and the Zalcwasser rank
• On the definitions of computable real continuous functions
• Ranks of differentiable functions
• Subsystems of second order arithmetic
• The Slaman-Wehner theorem in higher recursion theory

Cited in

(8)

• \(K\)-quasiderivations
• Index sets for computable differential equations
• Computable analysis and classification problems
• Ranks of differentiable functions
• Computable structures and operations on the space of continuous functions
• Three ordinal ranks for the set of differentiable functions
• An effective analysis of the Denjoy rank
• On the complexity of continuous functions differentiable on cocountable sets

This page was built for publication: A lightface analysis of the differentiability rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2921032)