Weakly uniform computable categoricity and function composition
Abstract
We introduce the definition of a weakly X-uniformly Y-computably categorical structure, relativizing a definition of Kudinov (1996), and show that this relativized notion is closely related to the 2-dimensional complexity of the pairs of partial functions (f,g) with the property that the composition g∘ f simulates convergent ∅'-oracle computations. We develop a general theory for computing via composition and use it to prove results about the surprisingly complex weakly uniform categoricity spectrum of the structure (ω,S) where S(n)=n+1. Namely, that (ω,S) is w.X.u.Y.c.c. for some Xnot≥T∅' and Y<T∅', but (ω,S) is not w.X.u.Y.c.c. for any X<T∅' and Ynot≥T∅'. We also construct a computably categorical structure that is not w.∅'.u.c.c., but is w.X.u.c.c. for a set X that is ≤T-incomparable with ∅'.
Related
- Uniform Gaussian Approximation for The Quasi-Likelihood Estimator for a Weakly Dependent Nonlinear Time Series Models
- From the Intermediate Value Theorem to the Rank Theorem: An Elementary and Computable Path Through the Implicit and Inverse Function Theorems
- Switching Categoricity Behavior with a Given Degree
- On a generating function of the basis of weakly holomorphic functions on an elliptic curve
- Uniform Partition-Function Estimates for Coulomb Modulated Energy at All Positive Temperatures
BibTeX
@misc{lakerdasgayle2026weakly,
title = {{Weakly uniform computable categoricity and function composition}},
author = {Joey Lakerdas-Gayle},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.24422},
eprint = {2610.24422},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.24422},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Weakly uniform computable categoricity and function composition
AU - Joey Lakerdas-Gayle
PY - 2026
DA - 2026/10/17
PB - arXiv
DO - 10.48550/arxiv.2610.24422
UR - https://arxiv.org/abs/2610.24422
AB - We introduce the definition of a weakly X-uniformly Y-computably categorical structure, relativizing a definition of Kudinov (1996), and show that this relativized notion is closely related to the 2-dimensional complexity of the pairs of partial functions (f,g) with the property that the composition g∘ f simulates convergent ∅'-oracle computations. We develop a general theory for computing via composition and use it to prove results about the surprisingly complex weakly uniform categoricity spectrum of the structure (ω,S) where S(n)=n+1. Namely, that (ω,S) is w.X.u.Y.c.c. for some Xnot≥_T∅' and Y<_T∅', but (ω,S) is not w.X.u.Y.c.c. for any X<_T∅' and Ynot≥_T∅'. We also construct a computably categorical structure that is not w.∅'.u.c.c., but is w.X.u.c.c. for a set X that is ≤_T-incomparable with ∅'.
ER -