A lightface analysis of the differentiability rank

DOI10.1017/JSL.2013.23zbMATH Open1338.03089arXiv1302.2975OpenAlexW2963345040MaRDI QIDQ2921032FDOQ2921032

Authors: Linda Brown Westrick 

Publication date: 30 September 2014

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

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.

Full work available at URL: https://arxiv.org/abs/1302.2975

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

zbMATH Keywords

computable analysisdifferentiabilityeffective descriptive set theoryrank functionhyperarithmetical hierarchy

Mathematics Subject Classification ID

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

Cites Work

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

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)