The Jordan decomposition theorem states that every function $f \colon \, [0,1] \to \mathbb {R}$ of bounded variation can be written as the difference of two non-decreasing functions. Combining this fact with a result of Lebesgue, every function of bounded variation is differentiable almost everywhere in the sense of Lebesgue measure. We analyze the strength of these theorems in the setting of reverse mathematics. Over $\mathsf {RCA}_{0}$ , a stronger version of Jordan’s result where all functions are continuous is equivalent to $\mathsf {ACA}_0$ , while the version stated is equivalent to ${\textsf {WKL}}_{0}$ . The result that every function on $[0,1]$ of bounded variation is almost everywhere differentiable is equivalent to ${\textsf {WWKL}}_{0}$ . To state this equivalence in a meaningful way, we develop a theory of Martin–Löf randomness over $\mathsf {RCA}_0$ .

In this work we investigate the Weihrauch degree of the problem Decreasing Sequence ( $\mathsf {DS}$ ) of finding an infinite descending sequence through a given ill-founded linear order, which is shared by the problem Bad Sequence ( $\mathsf {BS}$ ) of finding a bad sequence through a given non-well quasi-order. We show that $\mathsf {DS}$ , despite being hard to solve (it has computable inputs with no hyperarithmetic solution), is rather weak in terms of uniform computational strength. To make the latter precise, we introduce the notion of the deterministic part of a Weihrauch degree. We then generalize $\mathsf {DS}$ and $\mathsf {BS}$ by considering $\boldsymbol {\Gamma }$ -presented orders, where $\boldsymbol {\Gamma }$ is a Borel pointclass or $\boldsymbol {\Delta }^1_1$ , $\boldsymbol {\Sigma }^1_1$ , $\boldsymbol {\Pi }^1_1$ . We study the obtained $\mathsf {DS}$ -hierarchy and $\mathsf {BS}$ -hierarchy of problems in comparison with the (effective) Baire hierarchy and show that they do not collapse at any finite level.

We define the Scott complexity of a countable structure to be the least complexity of a Scott sentence for that structure. This is a finer notion of complexity than Scott rank: it distinguishes between whether the simplest Scott sentence is $\Sigma _{\alpha }$ , $\Pi _{\alpha }$ , or $\mathrm {d-}\Sigma _{\alpha }$ . We give a complete classification of the possible Scott complexities, including an example of a structure whose simplest Scott sentence is $\Sigma _{\lambda + 1}$ for $\lambda $ a limit ordinal. This answers a question left open by A. Miller.

We also construct examples of computable structures of high Scott rank with Scott complexities $\Sigma _{\omega _1^{CK}+1}$ and $\mathrm {d-}\Sigma _{\omega _1^{CK}+1}$ . There are three other possible Scott complexities for a computable structure of high Scott rank: $\Pi _{\omega _1^{CK}}$ , $\Pi _{\omega _1^{CK}+1}$ , $\Sigma _{\omega _1^{CK}+1}$ . Examples of these were already known. Our examples are computable structures of Scott rank $\omega _1^{CK}+1$ which, after naming finitely many constants, have Scott rank $\omega _1^{CK}$ . The existence of such structures was an open question.

We investigate the uniform computational content of the open and clopen Ramsey theorems in the Weihrauch lattice. While they are known to be equivalent to $\mathrm {ATR_0}$ from the point of view of reverse mathematics, there is not a canonical way to phrase them as multivalued functions. We identify eight different multivalued functions (five corresponding to the open Ramsey theorem and three corresponding to the clopen Ramsey theorem) and study their degree from the point of view of Weihrauch, strong Weihrauch, and arithmetic Weihrauch reducibility. In particular one of our functions turns out to be strictly stronger than any previously studied multivalued functions arising from statements around $\mathrm {ATR}_0$ .

Extending Aanderaa’s classical result that $\pi ^{1}_{1} < \sigma ^{1}_{1}$ , we determine the order between any two patterns of iterated $\Sigma ^{1}_{1}$ - and $\Pi ^{1}_{1}$ -reflection on ordinals. We show that this order of linear reflection is a prewellordering of length $\omega ^{\omega }$ . This requires considering the relationship between linear and some non-linear reflection patterns, such as $\sigma \wedge \pi $ , the pattern of simultaneous $\Sigma ^{1}_{1}$ - and $\Pi ^{1}_{1}$ -reflection. The proofs involve linking the lengths of $\alpha $ -recursive wellorderings to various forms of stability and reflection properties satisfied by ordinals $\alpha $ within standard and non-standard models of set theory.

In this paper, we examine the limit of applicability of Gödel’s first incompleteness theorem ($\textsf {G1}$ for short). We first define the notion “$\textsf {G1}$ holds for the theory $T$”. This paper is motivated by the following question: can we find a theory with a minimal degree of interpretation for which $\textsf {G1}$ holds. To approach this question, we first examine the following question: is there a theory T such that Robinson’s $\mathbf {R}$ interprets T but T does not interpret $\mathbf {R}$ (i.e., T is weaker than $\mathbf {R}$ w.r.t. interpretation) and $\textsf {G1}$ holds for T? In this paper, we show that there are many such theories based on Jeřábek’s work using some model theory. We prove that for each recursively inseparable pair $\langle A,B\rangle $, we can construct a r.e. theory $U_{\langle A,B\rangle }$ such that $U_{\langle A,B\rangle }$ is weaker than $\mathbf {R}$ w.r.t. interpretation and $\textsf {G1}$ holds for $U_{\langle A,B\rangle }$. As a corollary, we answer a question from Albert Visser. Moreover, we prove that for any Turing degree $\mathbf {0}< \mathbf {d}<\mathbf {0}^{\prime }$, there is a theory T with Turing degree $\mathbf {d}$ such that $\textsf {G1}$ holds for T and T is weaker than $\mathbf {R}$ w.r.t. Turing reducibility. As a corollary, based on Shoenfield’s work using some recursion theory, we show that there is no theory with a minimal degree of Turing reducibility for which $\textsf {G1}$ holds.

We prove a number of elementary facts about computability in partial combinatory algebras (pca’s). We disprove a suggestion made by Kreisel about using Friedberg numberings to construct extensional pca’s. We then discuss separability and elements without total extensions. We relate this to Ershov’s notion of precompleteness, and we show that precomplete numberings are not 1–1 in general.

We show that there is a cuppable c.e. degree, all of whose cupping partners are high. In particular, not all cuppable degrees are ${\operatorname {\mathrm {low}}}_3$-cuppable, or indeed ${\operatorname {\mathrm {low}}}_n$ cuppable for any n, refuting a conjecture by Li. On the other hand, we show that one cannot improve highness to superhighness. We also show that the ${\operatorname {\mathrm {low}}}_2$-cuppable degrees coincide with the array computable-cuppable degrees, giving a full understanding of the latter class.

The aim of this paper is to shed light on our understanding of large scale properties of infinite strings. We say that one string $\alpha $ has weaker large scale geometry than that of $\beta $ if there is color preserving bi-Lipschitz map from $\alpha $ into $\beta $ with small distortion. This definition allows us to define a partially ordered set of large scale geometries on the classes of all infinite strings. This partial order compares large scale geometries of infinite strings. As such, it presents an algebraic tool for classification of global patterns. We study properties of this partial order. We prove, for instance, that this partial order has a greatest element and also possess infinite chains and antichains. We also investigate the sets of large scale geometries of strings accepted by finite state machines such as Büchi automata. We provide an algorithm that describes large scale geometries of strings accepted by Büchi automata. This connects the work with the complexity theory. We also prove that the quasi-isometry problem is a $\Sigma _2^0$ -complete set, thus providing a bridge with computability theory. Finally, we build algebraic structures that are invariants of large scale geometries. We invoke asymptotic cones, a key concept in geometric group theory, defined via model-theoretic notion of ultra-product. Partly, we study asymptotic cones of algorithmically random strings, thus connecting the topic with algorithmic randomness.

We prove that the Weihrauch lattice can be transformed into a Brouwer algebra by the consecutive application of two closure operators in the appropriate order: first completion and then parallelization. The closure operator of completion is a new closure operator that we introduce. It transforms any problem into a total problem on the completion of the respective types, where we allow any value outside of the original domain of the problem. This closure operator is of interest by itself, as it generates a total version of Weihrauch reducibility that is defined like the usual version of Weihrauch reducibility, but in terms of total realizers. From a logical perspective completion can be seen as a way to make problems independent of their premises. Alongside with the completion operator and total Weihrauch reducibility we need to study precomplete representations that are required to describe these concepts. In order to show that the parallelized total Weihrauch lattice forms a Brouwer algebra, we introduce a new multiplicative version of an implication. While the parallelized total Weihrauch lattice forms a Brouwer algebra with this implication, the total Weihrauch lattice fails to be a model of intuitionistic linear logic in two different ways. In order to pinpoint the algebraic reasons for this failure, we introduce the concept of a Weihrauch algebra that allows us to formulate the failure in precise and neat terms. Finally, we show that the Medvedev Brouwer algebra can be embedded into our Brouwer algebra, which also implies that the theory of our Brouwer algebra is Jankov logic.

We show that a computable function $f:\mathbb R\rightarrow \mathbb R$ has Luzin’s property (N) if and only if it reflects $\Pi ^1_1$ -randomness, if and only if it reflects $\Delta ^1_1({\mathcal {O}})$ -randomness, and if and only if it reflects ${\mathcal {O}}$ -Kurtz randomness, but reflecting Martin–Löf randomness or weak-2-randomness does not suffice. Here a function f is said to reflect a randomness notion R if whenever $f(x)$ is R-random, then x is R-random as well. If additionally f is known to have bounded variation, then we show f has Luzin’s (N) if and only if it reflects weak-2-randomness, and if and only if it reflects $\emptyset '$ -Kurtz randomness. This links classical real analysis with algorithmic randomness.

Ramsey’s theorem asserts that every k-coloring of $[\omega ]^n$ admits an infinite monochromatic set. Whenever $n \geq 3$ , there exists a computable k-coloring of $[\omega ]^n$ whose solutions compute the halting set. On the other hand, for every computable k-coloring of $[\omega ]^2$ and every noncomputable set C, there is an infinite monochromatic set H such that $C \not \leq _T H$ . The latter property is known as cone avoidance.

In this article, we design a natural class of Ramsey-like theorems encompassing many statements studied in reverse mathematics. We prove that this class admits a maximal statement satisfying cone avoidance and use it as a criterion to re-obtain many existing proofs of cone avoidance. This maximal statement asserts the existence, for every k-coloring of $[\omega ]^n$ , of an infinite subdomain $H \subseteq \omega $ over which the coloring depends only on the sparsity of its elements. This confirms the intuition that Ramsey-like theorems compute Turing degrees only through the sparsity of its solutions.

We characterize Weihrauch reducibility in $ \operatorname {\mathrm {E-PA^{\omega }}} + \operatorname {\mathrm {QF-AC^{0,0}}}$ and all systems containing it by the provability in a linear variant of the same calculus using modifications of Gödel’s Dialectica interpretation that incorporate ideas from linear logic, nonstandard arithmetic, higher-order computability, and phase semantics.

We study computable Polish spaces and Polish groups up to homeomorphism. We prove a natural effective analogy of Stone duality, and we also develop an effective definability technique which works up to homeomorphism. As an application, we show that there is a $\Delta ^0_2$ Polish space not homeomorphic to a computable one. We apply our techniques to build, for any computable ordinal $\alpha $, an effectively closed set not homeomorphic to any $0^{(\alpha )}$-computable Polish space; this answers a question of Nies. We also prove analogous results for compact Polish groups and locally path-connected spaces.

The main objective of this paper is the following two results. (1) There exists a computable bi-orderable group that does not have a computable bi-ordering; (2) there exists a bi-orderable, two-generated computably presented solvable group with undecidable word problem. Both of the groups can be found among two-generated solvable groups of derived length $3$.

(1) [a]nswers a question posed by Downey and Kurtz; (2) answers a question posed by Bludov and Glass in Kourovka Notebook.

One of the technical tools used to obtain the main results is a computational extension of an embedding theorem of B. Neumann that was studied by the author earlier. In this paper we also compliment that result and derive new corollaries that might be of independent interest.

Here, we present a category ${\mathbf {pEff}}$ which can be considered a predicative variant of Hyland's Effective Topos ${{\mathbf {Eff} }}$ for the following reasons. First, its construction is carried in Feferman’s predicative theory of non-iterative fixpoints ${{\widehat {ID_1}}}$ . Second, ${\mathbf {pEff}}$ is a list-arithmetic locally cartesian closed pretopos with a full subcategory ${{\mathbf {pEff}_{set}}}$ of small objects having the same categorical structure which is preserved by the embedding in ${\mathbf {pEff}}$ ; furthermore subobjects in ${{\mathbf {pEff}_{set}}}$ are classified by a non-small object in ${\mathbf {pEff}}$ . Third ${\mathbf {pEff}}$ happens to coincide with the exact completion of the lex category defined as a predicative rendering in ${{\widehat {ID_1}}}$ of the subcategory of ${{\mathbf {Eff} }}$ of recursive functions and it validates the Formal Church’s thesis. Hence pEff turns out to be itself a predicative rendering of a full subcategory of ${{\mathbf {Eff} }}$ .

We describe punctual categoricity in several natural classes, including binary relational structures and mono-unary functional structures. We prove that every punctually categorical structure in a finite unary language is ${\text {PA}}(0')$-categorical, and we show that this upper bound is tight. We also construct an example of a punctually categorical structure whose degree of categoricity is $0''$. We also prove that, with a bit of work, the latter result can be pushed beyond $\Delta ^1_1$, thus showing that punctually categorical structures can possess arbitrarily complex automorphism orbits.

As a consequence, it follows that binary relational structures and unary structures are not universal with respect to primitive recursive interpretations; equivalently, in these classes every rich enough interpretation technique must necessarily involve unbounded existential quantification or infinite disjunction. In contrast, it is well-known that both classes are universal for Turing computability.

Recent work in computability theory has focused on various notions of asymptotic computability, which capture the idea of a set being “almost computable.” One potentially upsetting result is that all four notions of asymptotic computability admit “almost computable” sets in every Turing degree via coding tricks, contradicting the notion that “almost computable” sets should be computationally close to the computable sets. In response, Astor introduced the notion of intrinsic density: a set has defined intrinsic density if its image under any computable permutation has the same asymptotic density. Furthermore, introduced various notions of intrinsic computation in which the standard coding tricks cannot be used to embed intrinsically computable sets in every Turing degree. Our goal is to study the sets which are intrinsically small, i.e. those that have intrinsic density zero. We begin by studying which computable functions preserve intrinsic smallness. We also show that intrinsic smallness and hyperimmunity are computationally independent notions of smallness, i.e. any hyperimmune degree contains a Turing-equivalent hyperimmune set which is “as large as possible” and therefore not intrinsically small. Our discussion concludes by relativizing the notion of intrinsic smallness and discussing intrinsic computability as it relates to our study of intrinsic smallness.

The Wadge hierarchy was originally defined and studied only in the Baire space (and some other zero-dimensional spaces). Here we extend the Wadge hierarchy of Borel sets to arbitrary topological spaces by providing a set-theoretic definition of all its levels. We show that our extension behaves well in second countable spaces and especially in quasi-Polish spaces. In particular, all levels are preserved by continuous open surjections between second countable spaces which implies e.g., several Hausdorff–Kuratowski (HK)-type theorems in quasi-Polish spaces. In fact, many results hold not only for the Wadge hierarchy of sets but also for its extension to Borel functions from a space to a countable better quasiorder Q.

A problem is a multivalued function from a set of instances to a set of solutions. We consider only instances and solutions coded by sets of integers. A problem admits preservation of some computability-theoretic weakness property if every computable instance of the problem admits a solution relative to which the property holds. For example, cone avoidance is the ability, given a noncomputable set A and a computable instance of a problem ${\mathsf {P}}$ , to find a solution relative to which A is still noncomputable.

In this article, we compare relativized versions of computability-theoretic notions of preservation which have been studied in reverse mathematics, and prove that the ones which were not already separated by natural statements in the literature actually coincide. In particular, we prove that it is equivalent to admit avoidance of one cone, of $\omega $ cones, of one hyperimmunity or of one non- $\Sigma ^{0}_1$ definition. We also prove that the hierarchies of preservation of hyperimmunity and non- $\Sigma ^{0}_1$ definitions coincide. On the other hand, none of these notions coincide in a nonrelativized setting.