Recent zbMATH articles in MSC 03Dhttps://zbmath.org/atom/cc/03D2023-11-13T18:48:18.785376ZWerkzeugWhat is effective transfinite recursion in reverse mathematics?https://zbmath.org/1521.030202023-11-13T18:48:18.785376Z"Freund, Anton"https://zbmath.org/authors/?q=ai:freund.antonSummary: In the context of reverse mathematics, effective transfinite recursion refers to a principle that allows us to construct sequences of sets by recursion along arbitrary well orders, provided that each set is \(\Delta _1^0\)-definable relative to the previous stages of the recursion. It is known that this principle is provable in \(\mathsf{ACA}_0\). In the present note, we argue that a common formulation of effective transfinite recursion is too restrictive. We then propose a more liberal formulation, which appears very natural and is still provable in \(\mathsf{ACA}_0\).
{{\copyright} 2021 The Authors. \textit{Mathematical Logic Quarterly} published by Wiley-VCH GmbH}Orders on computable ringshttps://zbmath.org/1521.030222023-11-13T18:48:18.785376Z"Wu, Huishan"https://zbmath.org/authors/?q=ai:wu.huishanSummary: The Artin-Schreier theorem says that every formally real field has orders. \textit{H. M. Friedman} et al. showed in [Ann. Pure Appl. Logic 25, 141--181 (1983; Zbl 0575.03038); addendum ibid. 28, 319--320 (1985; Zbl 0575.03039)] that the Artin-Schreier theorem is equivalent to \(\mathsf{WKL}_0\) over \(\mathsf{RCA}_0\). We first prove that the generalization of the Artin-Schreier theorem to noncommutative rings is equivalent to \(\mathsf{WKL}_0\) over \(\mathsf{RCA}_0\). In the theory of orderings on rings, following an idea of Serre, we often show the existence of orders on formally real rings by extending pre-orders to orders, where Zorn's lemma is used. We then prove that ``pre-orders on rings not necessarily commutative extend to orders'' is equivalent to \(\mathsf{WKL}_0\).The theory of hereditarily bounded setshttps://zbmath.org/1521.030772023-11-13T18:48:18.785376Z"Jeřábek, Emil"https://zbmath.org/authors/?q=ai:jerabek.emilSummary: We show that for any \(k\in \omega \), the structure \(\langle H_k,{\in }\rangle\) of sets that are hereditarily of size at most \(k\) is decidable. We provide a transparent complete axiomatization of its theory, a quantifier elimination result, and tight bounds on its computational complexity. This stands in stark contrast to the structure \(V_\omega =\bigcup_kH_k\) of hereditarily finite sets, which is well known to be bi-interpretable with the standard model of arithmetic \(\langle \mathbb{N},+,\cdot \rangle \).
{{\copyright} 2022 Wiley-VCH GmbH}On the effective universality of mereological theorieshttps://zbmath.org/1521.030822023-11-13T18:48:18.785376Z"Bazhenov, Nikolay"https://zbmath.org/authors/?q=ai:bazhenov.n-a"Tsai, Hsing-Chien"https://zbmath.org/authors/?q=ai:tsai.hsing-chienSummary: Mereological theories are based on the binary relation ``being a part of''. The systematic investigations of mereology were initiated by \textit{S. Leśniewski} [Collected works. Volume I and II. Edited by Stanisław J. Surma, Jan T. Srzednicki and D. I. Barnett. With an annotated bibliography by V. Frederick Rickey. Dordrecht: Kluwer Academic Publishers; Warsaw: PWN-Polish Scientific Publishers (1992; Zbl 0765.03002)]. More recent authors (including \textit{P. Simons} [Parts: a Study in ontology. Oxford: Clarendon Press (1987)], \textit{A. Casati} and \textit{A. C. Varzi} [Parts and places. Cambridge: The MIT Press (1999)], \textit{P. Hovda} [J. Philos. Log. 38, No. 1, 55--82 (2009; Zbl 1171.03002)]) formulated a series of first-order mereological axioms. These axioms give rise to a plenitude of theories, which are of great philosophical interest. The paper considers first-order mereological theories from the point of view of computable (or effective) algebra. Following the approach of \textit{D. R. Hirschfeldt} et al. [Ann. Pure Appl. Logic 115, No. 1--3, 71--113 (2002; Zbl 1016.03034)], we isolate two important computability-theoretic properties \(\mathrm{P}\) (namely, degree spectra of structures, and effective dimensions), and consider the following problem: for a given mereological theory \(T\), is it true that its models can realize every possible variant of the property \(\mathrm{P}\)? If the answer is positive, then we say that the theory \(T\) is \(\mathit{DSED} \)-universal. We obtain the following results about known mereological theories. Any theory \(T\) which is weaker than Extensional Closure Mereology (CEM) is \(\mathit{DSED} \)-universal. A similar fact is true for the theory GM2. On the other hand, any theory stronger that CEM + (C) + (G) is not \(\mathit{DSED} \)-universal. In particular, General Extensional Mereology is not \(\mathit{DSED} \)-universal.
{{\copyright} 2021 Wiley-VCH GmbH}Jump inversions of algebraic structures and \(\Sigma \)-definabilityhttps://zbmath.org/1521.030832023-11-13T18:48:18.785376Z"Faizrahmanov, Marat"https://zbmath.org/authors/?q=ai:faizrahmanov.marat-khaidarovich"Kach, Asher"https://zbmath.org/authors/?q=ai:kach.asher-m"Kalimullin, Iskander"https://zbmath.org/authors/?q=ai:kalimullin.iskander-sh"Montalbán, Antonio"https://zbmath.org/authors/?q=ai:montalban.antonio"Puzarenko, Vadim"https://zbmath.org/authors/?q=ai:puzarenko.vadim-gSummary: It is proved that for every countable structure \(\mathcal{A}\) and a computable successor ordinal \(\alpha\) there is a countable structure \(\mathcal{A}^{-\alpha}\) which is \(\leq _{\Sigma}\)-least among all countable structures \(\mathcal{C}\) such that \(\mathcal{A}\) is \(\Sigma\)-definable in the \(\alpha\)th jump \(\mathcal{C}^{(\alpha)}\). We also show that this result does not hold for the limit ordinal \(\alpha=\omega\). Moreover, we prove that there is no countable structure \(\mathcal{A}\) with the degree spectrum \(\{\mathbf{d}:\mathbf{a}\leq\mathbf{d}^{(\omega)}\}\) for \(\mathbf{a}>\mathbf{0}^{(\omega)}\).Bi-embeddability spectra and bases of spectrahttps://zbmath.org/1521.030842023-11-13T18:48:18.785376Z"Fokina, Ekaterina"https://zbmath.org/authors/?q=ai:fokina.ekaterina-b"Rossegger, Dino"https://zbmath.org/authors/?q=ai:rossegger.dino"San Mauro, Luca"https://zbmath.org/authors/?q=ai:san-mauro.lucaSummary: We study degree spectra of structures with respect to the bi-embeddability relation. The bi-embeddability spectrum of a structure is the family of Turing degrees of its bi-embeddable copies. To facilitate our study we introduce the notions of bi-embeddable triviality and basis of a spectrum. Using bi-embeddable triviality we show that several known families of degrees are bi-embeddability spectra of structures. We then characterize the bi-embeddability spectra of linear orderings and study bases of bi-embeddability spectra of strongly locally finite graphs.Spectra and satisfiability for logics with successor and a unary functionhttps://zbmath.org/1521.031152023-11-13T18:48:18.785376Z"Milchior, Arthur"https://zbmath.org/authors/?q=ai:milchior.arthurSummary: We investigate the expressive power of two logics, both with the successor function: first-order logic with an uninterpreted function, and existential monadic second order logic -- that is first-order logic over words --, with multiplication by a constant \(b\). We prove that all \(b\)-recognizable sets are spectra of those logics. Furthermore, it is proven that some encoding of the set of halting times of a non-deterministic 2-counter automaton is also a spectrum. This yields undecidability of the finite satisfiability problem for those logics. Finally, it is shown that first-order logic with one uninterpreted function and successor can encode quickly increasing functions, such as the Knuth's up-arrows.On elementary word functions obtained by bounded prefix concatenationhttps://zbmath.org/1521.031162023-11-13T18:48:18.785376Z"Marchenkov, Sergey S."https://zbmath.org/authors/?q=ai:marchenkov.sergey-sSummary: The operation of bounded prefix concatenation (BPC) is introduced on the set of word functions in the alphabet \(\{1, 2\}\). The class BPC of polynomially computable functions is defined on the basis of this operation and the superposition operation. The class BPC is shown to contain a number of word functions and to be closed with respect to certain known operations. A certain type of two-tape nonerasing Turing machines is introduced, functions from the class BPC are shown to be computable on machines of this type in polynomial time.\(r\)-maximal sets and \(Q_{1 , N}\)-reducibilityhttps://zbmath.org/1521.031172023-11-13T18:48:18.785376Z"Omanadze, Roland Sh."https://zbmath.org/authors/?q=ai:omanadze.roland-sh"Chitaia, Irakli O."https://zbmath.org/authors/?q=ai:chitaia.irakli-oSummary: We show that if \(M\) is an \(r\)-maximal set, \(A\) is a major subset of \(M\), \(B\) is an arbitrary set and \(M \setminus A \equiv_{Q_{1 , N}} B\), then \(M \setminus A \leq_m B\). We prove that the c.e. \(Q_{1 , N}\)-degrees are not dense. We also show that there exist infinite collections of \(Q_{1 , N}\)-degrees \(\{ \mathbf{a}_i \}_{i \in \omega}\) and \(\{ \mathbf{b}_j \}_{j \in \omega}\) such that the following hold: (i) for every \(i, j\), \(\mathbf{a}_i <_{Q_{1 , N}} \mathbf{a}_{i + 1}, \mathbf{b}_{j + 1} <_{Q_{1 , N}} \mathbf{b}_j\) and \(\mathbf{a}_i <_{Q_{1 , N}} \mathbf{b}_j\), (ii) each \(\mathbf{a}_i\) consists entirely of \(r\)-maximal sets, and (iii) each \(\mathbf{b}_j\) consists entirely of non-\(r\)-maximal hyperhypersimple sets.
{{\copyright} 2021 Wiley-VCH GmbH}An effectively closed set with no join propertyhttps://zbmath.org/1521.031182023-11-13T18:48:18.785376Z"Çevik, Ahmet"https://zbmath.org/authors/?q=ai:cevik.ahmet-sinanSummary: In this paper, we establish a relationship between the join property and Turing degrees of members of effectively closed sets in Cantor space, i.e., \(\Pi_1^0\) classes. We first give a proof of the observation that there exists a non-empty special \(\Pi_1^0\) class in which no join of two members computes the halting set. We then prove the existence of a non-empty special \(\Pi_1^0\) class such that no member satisfies the join property, where a degree \(\mathbf{a}\) satisfies the \textit{join property} if for all non-zero \(\mathbf{b} < \mathbf{a}\) there exists \(\mathbf{c} < \mathbf{a}\) such that \(\mathbf{b} \vee \mathbf{c} = \mathbf{a}\).
{{\copyright} 2021 Wiley-VCH GmbH}Lowness for isomorphism, countable ideals, and computable traceabilityhttps://zbmath.org/1521.031192023-11-13T18:48:18.785376Z"Franklin, Johanna N. Y."https://zbmath.org/authors/?q=ai:franklin.johanna-n-y"Solomon, Reed"https://zbmath.org/authors/?q=ai:solomon.reedSummary: We show that every countable ideal of degrees that are low for isomorphism is contained in a principal ideal of degrees that are low for isomorphism by adapting an exact pair construction. We further show that within the hyperimmune free degrees, lowness for isomorphism is entirely independent of computable traceability.Normalizing notations in the Ershov hierarchyhttps://zbmath.org/1521.031202023-11-13T18:48:18.785376Z"Peng, Cheng"https://zbmath.org/authors/?q=ai:peng.chengSummary: The Turing degrees of infinite levels of the Ershov hierarchy were studied by \textit{Y. Liu} and \textit{C. Peng} [Notre Dame J. Formal Logic 61, No. 4, 521--536 (2020; Zbl 1486.03071)]. In this paper, we continue the study of Turing degrees of infinite levels and lift the study of density property to the levels beyond \(\omega^2\). In doing so, we rely on notations with some nice properties. We introduce the concept of normalizing notations and generate normalizing notations for higher levels. The generalizations of the weak density theorem and the nondensity theorem are proved for higher levels in the Ershov hierarchy. Furthermore, we also investigate the minimal degrees in the infinite levels of the Ershov hierarchy.
{{\copyright} 2021 Wiley-VCH GmbH}Agreement reducibilityhttps://zbmath.org/1521.031212023-11-13T18:48:18.785376Z"Epstein, Rachel"https://zbmath.org/authors/?q=ai:epstein.rachel"Lange, Karen"https://zbmath.org/authors/?q=ai:lange.karenSummary: We introduce \textit{agreement reducibility} and highlight its major features. Given subsets \(A\) and \(B\) of \(\mathbb{N}\), we write \(A \leq_{\mathrm{agree}} B\) if there is a total computable function \(f : \mathbb{N} \to \mathbb{N}\) satisfying for all \(e\), \(e^\prime\), \(\mathrm{W}_e \cap A = \mathrm{W}_{e^\prime} \cap A \text{ if and only if } \mathrm{W}_{f (e)} \cap B = \mathrm{W}_{f (e^\prime)} \cap B\). We shall discuss the central role \(\mathbb{N}\) plays in this reducibility and its connection to strong-hyper-hyper-immunity. We shall also compare agreement reducibility to other well-known reducibilities, in particular \(s_1\)- and s-reducibility. We came upon this reducibility while studying the computable reducibility of a class of equivalence relations on \(\mathbb{N}\) based on set-agreement. We end by describing the origin of agreement reducibility and presenting some results in that context.
{{\copyright} 2021 Wiley-VCH GmbH}Limitwise monotonic reducibility on sets and on pairs of setshttps://zbmath.org/1521.031222023-11-13T18:48:18.785376Z"Zainetdinov, Damir Kh."https://zbmath.org/authors/?q=ai:zainetdinov.damir-khSummary: We study limitwise monotonic sets and pairs of sets. We investigate the properties of limitwise monotonic reducibility between sets and pairs of sets defined in terms of \(\Sigma\)-reducibility corresponding to initial segment of sets. In addition, we obtain a description of \(\Sigma\)-reducibility of families of a special form in terms of \textit{lm}-reducibility. At the same time we show the relationship of concepts of \textit{lm}-reducibility and \(\Sigma\)-reducibility between the pairs of sets.Bernoulli randomness and Bernoulli normalityhttps://zbmath.org/1521.031232023-11-13T18:48:18.785376Z"DeLapo, Andrew"https://zbmath.org/authors/?q=ai:delapo.andrewSummary: One can consider \(\mu\)-Martin-Löf randomness for a probability measure \(\mu\) on \(2^\omega\), such as the Bernoulli measure \(\mu_p\) given \(p \in (0, 1)\). We study Bernoulli randomness of sequences in \(b^\omega\) with parameters \(p_0\), \(p_1, \ldots, p_{b - 1}\), and we reintroduce Bernoulli normality, where the uniform distribution of digits is replaced with a Bernoulli distribution. We prove the equivalence of three characterizations of Bernoulli normality. We show that every Bernoulli random real is Bernoulli normal, and this has the corollary that the set of Bernoulli normal reals has full Bernoulli measure in \(b^\omega\). We give an algorithm for computing Bernoulli normal sequences from normal sequences so that we can give explicit examples of Bernoulli normal reals. We investigate an application of randomness to iterated function systems. Finally, we list a few further questions relating to Bernoulli randomness and Bernoulli normality.
{{\copyright} 2021 Wiley-VCH GmbH}On unstable and unoptimal predictionhttps://zbmath.org/1521.031242023-11-13T18:48:18.785376Z"Kalociński, Dariusz"https://zbmath.org/authors/?q=ai:kalocinski.dariusz"Steifer, Tomasz"https://zbmath.org/authors/?q=ai:steifer.tomaszSummary: We consider the notion of prediction functions (or predictors) studied before in the context of randomness and stochasticity by Ko, and later by Ambos-Spies and others. Predictor is a total computable function which tries to predict bits of some infinite binary sequence. The prediction error is defined as the limit of the number of incorrect answers divided by the number of answers given so far. We discuss indefiniteness of prediction errors for weak 1-generics and show that this phenomenon affects certain c.e. sequences as well. On the other hand, a notion of optimal predictor is considered. It is shown that there is a sequence for which increasingly better predictors exist but for which no predictor is optimal.Russell's typicality as another randomness notionhttps://zbmath.org/1521.031252023-11-13T18:48:18.785376Z"Tzouvaras, Athanassios"https://zbmath.org/authors/?q=ai:tzouvaras.athanassiosSummary: We reformulate slightly Russell's notion of typicality, so as to eliminate its circularity and make it applicable to elements of any first-order structure. We argue that the notion parallels Martin-Löf (ML) randomness, in the sense that it uses definable sets in place of computable ones and sets of ``small'' cardinality (i.e., strictly smaller than that of the structure domain) in place of measure zero sets. It is shown that if the domain \(M\) satisfies \(\operatorname{cf} ( | M | ) > \aleph_0\), then there exist \(| M |\) typical elements and only \(< | M |\) non-typical ones. In particular this is true for the standard model \(\mathcal{R}\) of second-order arithmetic. By allowing parameters in the defining formulas, we are led to relative typicality, which satisfies most of van Lambalgen's axioms for relative randomness. However van Lambalgen's theorem is false for relative typicality. The class of typical reals is incomparable (with respect to \(\subseteq )\) with the classes of ML-random, Schnorr random and computably random reals. Also the class of typical reals is closed under Turing degrees and under the jump operation (both ways).
{{\copyright} 2020 Wiley-VCH GmbH}Rogers semilattices of limitwise monotonic numberingshttps://zbmath.org/1521.031262023-11-13T18:48:18.785376Z"Bazhenov, Nikolay"https://zbmath.org/authors/?q=ai:bazhenov.n-a"Mustafa, Manat"https://zbmath.org/authors/?q=ai:mustafa.manat"Tleuliyeva, Zhansaya"https://zbmath.org/authors/?q=ai:tleuliyeva.zhansayaSummary: Limitwise monotonic sets and functions constitute an important tool in computable structure theory. We investigate limitwise monotonic numberings. A numbering \(\nu\) of a family \(S\subset P(\omega )\) is limitwise monotonic (l.m.) if every set \(\nu (k)\) is the range of a limitwise monotonic function, uniformly in \(k\). The set of all l.m. numberings of \(S\) induces the Rogers semilattice \(R_{\mathrm{lm}}(S)\). The semilattices \(R_{\mathrm{lm}}(S)\) exhibit a peculiar behavior, which puts them \textit{in-between} the classical Rogers semilattices (for computable families) and Rogers semilattices of \(\Sigma^0_2\)-computable families. We show that every Rogers semilattice of a \(\Sigma^0_2\)-computable family is isomorphic to some semilattice \(R_{\mathrm{lm}}(S)\). On the other hand, there are infinitely many isomorphism types of classical Rogers semilattices which can be realized as semilattices \(R_{\mathrm{lm}}(S)\). In particular, there is an l.m. family \(S\) such that \(R_{\mathrm{lm}}(S)\) is isomorphic to the upper semilattice of c.e. \(m\)-degrees. We prove that if an l.m. family \(S\) contains more than one element, then the poset \(R_{\mathrm{lm}}(S)\) is infinite, and it is not a lattice. The l.m. numberings form an ideal (w.r.t. reducibility between numberings) inside the class of all \(\Sigma^0_2\)-computable numberings. We prove that inside this class, the index set of l.m. numberings is \(\Sigma^0_4\)-complete.
{{\copyright} 2022 Wiley-VCH GmbH}Initial segments of computable linear orders with computable natural relationshttps://zbmath.org/1521.031272023-11-13T18:48:18.785376Z"Bikmukhametov, R. I."https://zbmath.org/authors/?q=ai:bikmukhametov.r-iSummary: We study the algorithmic complexity of natural relations on initial segments of computable linear orders. We prove that there exists a computable linear order with computable density relation such that its \(\Pi_1^0\)-initial segment has no computable presentation with a computable density relation. We also prove that the same holds for a right limit and a left limit relations.Word problems and ceershttps://zbmath.org/1521.031282023-11-13T18:48:18.785376Z"Delle Rose, Valentino"https://zbmath.org/authors/?q=ai:delle-rose.valentino"San Mauro, Luca"https://zbmath.org/authors/?q=ai:san-mauro.luca"Sorbi, Andrea"https://zbmath.org/authors/?q=ai:sorbi.andreaSummary: This note addresses the issue as to which ceers can be realized by word problems of computably enumerable (or, simply, c.e.) structures (such as c.e. semigroups, groups, and rings), where being realized means to fall in the same reducibility degree (under the notion of reducibility for equivalence relations usually called ``computable reducibility''), or in the same isomorphism type (with the isomorphism induced by a computable function), or in the same strong isomorphism type (with the isomorphism induced by a computable permutation of the natural numbers). We observe, e.g., that every ceer is isomorphic to the word problem of some c.e. semigroup, but (answering a question of \textit{S. Gao} and \textit{P. Gerdes} [Stud. Log. 67, No. 1, 27--59 (2001; Zbl 0981.03046)]) not every ceer is in the same reducibility degree of the word problem of some finitely presented semigroup, nor is it in the same reducibility degree of some non-periodic semigroup. We also show that the ceer provided by provable equivalence of Peano Arithmetic is in the same strong isomorphism type as the word problem of some non-commutative and non-Boolean c.e. ring.
{{\copyright} 2020 Wiley-VCH GmbH}Extremal numberings and fixed point theoremshttps://zbmath.org/1521.031292023-11-13T18:48:18.785376Z"Faizrahmanov, Marat"https://zbmath.org/authors/?q=ai:faizrahmanov.marat-khaidarovichSummary: We consider so-called \textit{extremal} numberings that form the greatest or minimal degrees under the reducibility of all \(A\)-computable numberings of a given family of subsets of \(\mathbb{N}\), where \(A\) is an arbitrary oracle. Such numberings are very common in the literature and they are called \textit{universal} and \textit{minimal} \(A\)-computable numberings, respectively. The main question of this paper is when a universal or a minimal \(A\)-computable numbering satisfies the Recursion Theorem (with parameters). First we prove that the Turing degree of a set \(A\) is hyperimmune if and only if every universal \(A\)-computable numbering satisfies the Recursion Theorem. Next we prove that any universal \(A\)-computable numbering satisfies the Recursion Theorem with parameters if \(A\) computes a non-computable c.e. set. We also consider the property of precompleteness of universal numberings, which in turn is closely related to the Recursion Theorem. Ershov proved that a numbering is \textit{precomplete} if and only if it satisfies the Recursion Theorem with parameters for partial computable functions. In this paper, we show that for a given \(A\)-computable numbering, in the general case, the Recursion Theorem with parameters for total computable functions is not equivalent to the precompleteness of the numbering, even if it is universal. Finally we prove that if \(A\) is high, then any infinite \(A\)-computable family has a minimal \(A\)-computable numbering that satisfies the Recursion Theorem.
{{\copyright} 2022 Wiley-VCH GmbH.}\(\Pi_1^1\)-Martin-Löf randomness and \(\Pi_1^1\)-Solovay completenesshttps://zbmath.org/1521.031302023-11-13T18:48:18.785376Z"Sureson, Claude"https://zbmath.org/authors/?q=ai:sureson.claudeSummary: Developing an analogue of Solovay reducibility in the higher recursion setting, we show that results from the classical computably enumerable case can be extended to the new context.Three topological reducibilities for discontinuous functionshttps://zbmath.org/1521.031312023-11-13T18:48:18.785376Z"Day, Adam R."https://zbmath.org/authors/?q=ai:day.adam-r"Downey, Rod"https://zbmath.org/authors/?q=ai:downey.rodney-graham"Westrick, Linda"https://zbmath.org/authors/?q=ai:westrick.linda-brownThe idea of reducibility has been a central notion in computability theory. In this paper the authors analyze three types of reducibility for functions \(f,g:X\to\mathbb{R}\), where \(X\) is a compact separable metric space. Several results are presented about equivalence classes and the degree structure associated to these reductions.
The three reducibilities considered are \(\leq_{\textbf{T}}\), \(\leq_{\textbf{tt}}\) and \(\leq_{\textbf{m}}\). The \(f\leq_{\textbf{T}}g\) reduction is interpreted as meaning that \(f\) is continuously Weihrauch reducible to the parallelization of \(g\) (Section 3 recalls represented spaces and the notion of Weihrauch reducibility on represented spaces). Section 2 provides motivations for considering this particular notion of reduction, while Section 1 introduces the main ideas and history of the contents of the paper.
Section 4 considers topological reducibility \(\leq_{\textbf{T}}\) on \(2^\omega\) and defines jump functions to characterize the \(\leq_{\textbf{T}}\)-degrees of the Baire functions (Baire functions are also revisited in Section 3.4).
Section 5 defines the topological reducibilities \(\leq_{\textbf{tt}}\) and \(\leq_{\textbf{m}}\) by restricting the oracle use in the Weihrauch reduction in a certain manner. Section 6 studies properties of \(\leq_{\textbf{m}}\), by presenting results about the \(\leq_{\textbf{m}}\)-degrees of the jump functions over Baire functions.
On Section 7, the authors study the Bourgain rank in a slightly more general setting which will be related to the structure of \(\leq_{\textbf{tt}}\)-degrees and \(\leq_{\textbf{m}}\)-degrees within the Baire 1 functions. Section 8 characterizes the \(\leq_{\textbf{m}}\)-degrees within the Baire 1 functions, while Section 9 presents another reducibility notion and Section 10 characterizes the \(\leq_{\textbf{tt}}\)-degrees within the Baire 1 functions in terms of the Bourgain rank.
Finally Section 11 presents further directions for research and some open questions.
Reviewer: Daniel Graça (Faro)Computability of graphshttps://zbmath.org/1521.031322023-11-13T18:48:18.785376Z"Iljazović, Zvonko"https://zbmath.org/authors/?q=ai:iljazovic.zvonkoSummary: We consider topological pairs \((A, B)\), \(B \subseteq A\), which have computable type, which means that they have the following property: if \(X\) is a computable topological space and \(f : A \to X\) a topological imbedding such that \(f (A)\) and \(f (B)\) are semicomputable sets in \(X\), then \(f (A)\) is a computable set in \(X\). It is known, e.g., that \((M, \partial M)\) has computable type if \(M\) is a compact manifold with boundary. In this paper we examine topological spaces called graphs and we show that we can in a natural way associate to each graph \(G\) a discrete subspace \(E\) so that \((G, E)\) has computable type. Furthermore, we use this result to conclude that certain noncompact semicomputable graphs in computable metric spaces are computable.Parametric Presburger arithmetic: complexity of counting and quantifier eliminationhttps://zbmath.org/1521.032222023-11-13T18:48:18.785376Z"Bogart, Tristram"https://zbmath.org/authors/?q=ai:bogart.tristram"Goodrick, John"https://zbmath.org/authors/?q=ai:goodrick.john"Nguyen, Danny"https://zbmath.org/authors/?q=ai:nguyen.danny"Woods, Kevin"https://zbmath.org/authors/?q=ai:woods.kevin-m|woods.kevinSummary: We consider an expansion of Presburger arithmetic which allows multiplication by \(k\) parameters \(t_1,\dots,t_k\). A formula in this language defines a parametric set \(S_{\mathbf{t}} \subseteq\mathbb{Z}^d\) as \(\mathbf{t}\) varies in \(\mathbb{Z}^k\), and we examine the counting function \(|S_{\mathbf{t}}|\) as a function of \(\mathbf{t}\). For a single parameter, it is known that \(|S_t|\) can be expressed as an eventual quasi-polynomial (there is a period \(m\) such that, for sufficiently large \(t\), the function is polynomial on each of the residue classes mod \(m)\). We show that such a nice expression is impossible with 2 or more parameters. Indeed (assuming \(\mathbf{P}\neq\mathbf{NP})\) we construct a parametric set \(S_{t_1,t_2}\) such that \(|S_{t_1,t_2}|\) is not even polynomial-time computable on input \((t_1,t_2)\). In contrast, for parametric sets \(S_{\mathbf{t}}\subseteq\mathbb{Z}^d\) with arbitrarily many parameters, defined in a similar language without the ordering relation, we show that \(| S_{\mathbf{t}}|\) is always polynomial-time computable in the size of \(\mathbf{t}\), and in fact can be represented using the gcd and similar functions.On the finite axiomatizability of \(\forall\hat{\Sigma}^{\mathrm{b}}_1 (\hat{\mathsf{R}}^1_2)\)https://zbmath.org/1521.032312023-11-13T18:48:18.785376Z"Pollett, Chris"https://zbmath.org/authors/?q=ai:pollett.chrisSummary: The question of whether the bounded arithmetic theories \(\mathsf{S}^1_2\) and \(\mathsf{R}^1_2\) are equal is closely connected to the complexity question of whether \(\mathbf{P}\) is equal to \(\mathbf{NC}\). In this paper, we examine the still open question of whether the prenex version of \(\mathsf{R}^1_2\), \(\hat{\mathsf{R}}^1_2\), is equal to \(\mathsf{S}^1_2\). We give new dependent choice-based axiomatizations of the \(\forall\hat{\Sigma}^{\mathrm{b}}_1\)-consequences of \(\mathsf{S}^1_2\) and \(\hat{\mathsf{R}}^1_2\). Our dependent choice axiomatizations give new normal forms for the \(\hat{\Delta}^{\mathrm{b}}_1\)-consequences of \(\mathsf{S}^1_2\) and \(\hat{\mathsf{R}}^1_2\). We use these axiomatizations to give an alternative proof of the finite axiomatizability of \(\forall\hat{\Sigma}^{\mathrm{b}}_1(\mathsf{S}^1_2)\) and to show new results such as \(\forall\hat{\Sigma}^{\mathrm{b}}_1(\mathsf{R}'^1_3)\) is finitely axiomatized and that there is a finitely axiomatized theory, \(\mathsf{TUC}\), containing \(\hat{\mathsf{S}}^0_2\) and contained in \(\hat{\mathsf{R}}^1_2\). On the other hand, we show that our theory for \(\forall\hat{\Sigma}^{\mathrm{b}}_1 (\hat{\mathsf{R}}^1_2)\) splits into a natural infinite hierarchy of theories. We give a diagonalization result that stems from our attempts to separate the hierarchy for \(\forall\hat{\Sigma}^{\mathrm{b}}_1 (\hat{\mathsf{R}}^1_2)\).Encoding true second-order arithmetic in the real-algebraic structure of models of intuitionistic elementary analysishttps://zbmath.org/1521.032392023-11-13T18:48:18.785376Z"Erdélyi-Szabó, Miklós"https://zbmath.org/authors/?q=ai:erdelyi-szabo.miklosSummary: Based on the paper [the author, J. Symb. Log. 65, No. 3, 1014--1030 (2000; Zbl 0970.03037)] we show that true second-order arithmetic is interpretable over the real-algebraic structure of models of intuitionistic analysis built upon a certain class of complete Heyting algebras.
{{\copyright} 2021 Wiley-VCH GmbH}Topological recursion and uncoupled BPS structures. II: Voros symbols and the \(\tau\)-functionhttps://zbmath.org/1521.813942023-11-13T18:48:18.785376Z"Iwaki, Kohei"https://zbmath.org/authors/?q=ai:iwaki.kohei"Kidwai, Omar"https://zbmath.org/authors/?q=ai:kidwai.omarSummary: We continue our study of the correspondence between BPS structures and topological recursion in the uncoupled case, this time from the viewpoint of quantum curves. For spectral curves of hypergeometric type, we show the Borel-resummed Voros symbols of the corresponding quantum curves solve Bridgeland's ``BPS Riemann-Hilbert problem''. In particular, they satisfy the required jump property in agreement with the generalized definition of BPS indices \(\Omega\) in our previous work. Furthermore, we observe the Voros coefficients define a closed one-form on the parameter space, and show that (log of) Bridgeland's \(\tau\)-function encoding the solution is none other than the corresponding potential, up to a constant. When the quantization parameter is set to a special value, this agrees with the Borel sum of the topological recursion partition function \(Z_\mathrm{TR}\), up to a simple factor.
For Part I, see [the authors, Adv. Math. 398, Article ID 108191, 54 p. (2022; Zbl 1486.81157)].