The note concerns the comparative study of two approaches to generalized computability over the real numbers: computable analysis and Σ-definability in hereditarily finite su-perstructures. As known, there exist total computable functions that are not Σ-definable and discontinuous Σ-definable functions that are not computable. In this note, we show that even among continuous real functions, there exists a Σ-definable function that is not computable in the sense of computable analysis. The proof uses a diagonalization construction with infinite computable disjunctions of Δ 0 -formulas.
Continuity in Computable Analysis and Σ-Definability. // Graphs and Combinatorics. – 2025. – DOI: 10.1007/s10469-026-09835-3. – URL: https://link.springer.com/article/10.1007/s10469-026-09835-3
(2025). Continuity in Computable Analysis and Σ-Definability. Graphs and Combinatorics. https://doi.org/10.1007/s10469-026-09835-3
“Continuity in Computable Analysis and Σ-Definability.” Graphs and Combinatorics, 2025. doi:10.1007/s10469-026-09835-3.
@article{article34267,
title = {Continuity in Computable Analysis and Σ-Definability},
journal = {Graphs and Combinatorics},
year = {2025},
doi = {10.1007/s10469-026-09835-3},
url = {https://link.springer.com/article/10.1007/s10469-026-09835-3}
}
We study the complexity of the existence problem of a ∀-sentence (∃-sentence) equivalent to a given sentence in signatures containing only unary symbols. We prove that if the signature consists of an at most one function symbol and an...
We obtain a criterion for decidable categoricity of injective unars. Exact complexity estimates are established for the index sets of the classes of strongly constructivizable injective unars and decidably categorical injective unars....
Some conditions are given under which the union of an increasing chain of Jónsson algebras is again a Jónsson algebra. Conditions are found under which there exists a countable increasing chain of Jónsson groups whose union is not a...
We study a categorical approach to the concept of varieties of chiral algebras. We prove that the class of chiral algebras in the variety defined by a binary quadratic operad Var, whose conformal structure is abelian, coincides with the...