A Baire Category Approach to Besicovitch’s Theorem and Measure Regularity Emma Gruner, Jan Reimann Abstract . By reformulating the classical proof as a Baire Category argument, we show that Besicovitch’s Theorem in Cantor space is provable in ACA 0 \text{ACA}_{0} , and additionally that the witnessing subset is computable from one jump of the original set. We show that the necessary formulation of Baire Category, which we call Baire Category Theorem for Closed Sets (BCTC), is equivalent to ACA 0 \text{ACA}_{0} , contrasting with previous results on the reverse math strength of Baire Category variants. We also examine the implications of BCTC for more general monotone functions on closed sets, and explore how changing the representation of a closed set affects the reverse math strength of its measure regularity properties. 2020 Mathematics Subject Classification 03B30 1. Introduction Since its inception in the latter half of the twentieth century, the reverse mathematics research program has been used to analyze theorems across a wide range of disciplines. Real analysis and point-set topology have been some of the most popular areas of study, since many of the objects involved (real numbers, separable metric spaces, continuous functions, open sets, etc.) have “essentially countable” structures which allows them to be coded naturally as elements of 2^{\omega} . Thus, these fields can be meaningfully discussed in the context of second-order arithmetic. Geometric measure theory, on the other hand, is almost entirely unexplored from the reverse mathematics framework. Pauly and Fouché 9 studied Frostman’s Lemma in the context of Weihrauch degrees (see also 10 for effective aspects of Frostman’s Lemma). Another foundational result of geometric measure theory is a theorem proven by Abram Besicovitch in 1952 1 , which states that any closed subset in Euclidean space having infinite Hausdorff measure contains a closed subset with positive finite Hausdorff measure. Sets of positive finite measure have many convenient local properties (see 6 for an extensive treatment), so the ability to “pass” to such a subset is highly useful. Later in 1952 4 , Roy Davies strengthened Besicovitch’s result to the case where the given set is analytic. We will refer to the combined result as the Besicovitch-Davies Theorem . Besides its importance in geometric measure theory as a whole, there are a few reasons why the reverse mathematical content of this theorem is of interest. For one, the original form of the theorem proven by Besicovitch only concerns closed sets. When we work over Cantor space 2^{\omega} , the tree structure and compactness properties of these sets, particularly with regard to the definition of Hausdorff measure, are very convenient for formalization in second-order arithmetic. Additionally, the set existence axioms required to prove Besicovitch’s theorem are not obvious from the structure of the original argument. If F represents the original closed subset, then the witnessing subset E is defined as the infinite intersection of nested decreasing closed subsets \{E_{k}\}_{k\in\omega} . By the properties of the s -dimensional Hausdorff \delta -measure on compact sets, one can verify that E_{0} has an arithmetic definition from F , and each subsequent E_{k+1} can be defined similarly from E_{k} . Thus, while the existence of each set E_{k} in the approximating sequence is provable in \text{ACA}_{0} , the same may not be true for the infinite intersection E=\bigcap_{k\in\omega}E_{k} . In this paper, we were able to impose a topology on the space of closed subsets of our given set F , and relate the Hausdorff \delta -measures of these sets to certain open and closed sets within this topology. By exploiting this topological structure, we could use a variant of the Baire Category Theorem to significantly decrease the arithmetic complexity of the final witnessing subset E . This brings us to the following main theorem: Theorem 1.1 . In Cantor space 2^{\omega} , Besicovitch’s Theorem is provable in \text{ACA}_{0} . In fact, from a computability standpoint, Besicovitch’s Theorem only requires a small amount of \text{ACA}_{0} ’s full power, in the following sense: Theorem 1.2 . Let F\subseteq 2^{\omega} be a closed subset with infinite s -dimensional Hausdorff measure, and suppose Z_{F}\in 2^{\omega} is a code for its tree. Then we can find a closed subset E\subseteq F with positive finite Hausdorff measure whose code Z_{E} is computable from Z_{F}^{\prime} (the first Turing jump of Z_{F} ). Besicovitch’s original argument suggests that infinitely many jumps of the original closed set F may be required to compute the witnessing subset E . The theorem above also stands in contrast to a result by Reimann and Kjos-Hanssen (2014) regarding G_{\delta} sets 8 . By the full Besicovitch-Davies Theorem, any G_{\delta} set of infinite Hausdorff measure contains a closed subset of positive measure, but the authors exhibited a lightface \Pi^{0}_{2} subset of 2^{\omega} whose witnessing closed subsets could not be computed from any hyperarithmetic real. Whether Besicovitch’s Theorem is equivalent to \text{ACA}_{0} remains open. However, we did show that Besicovitch implies the axioms of \text{WWKL}_{0} , or even \text{WKL}_{0} if we impose additional structure on the witnessing subset E . (See Section 4.2 for details). Therefore, we at least know that Besicovitch is not provable in \text{RCA}_{0} . While Besicovitch’s theorem provided the motivation for this project, the measure theoretic and topological techniques developed along the way led to interesting avenues of study in their own right. For one, the definition of s -dimensional Hausdorff measure involves taking the limit of a sequence of outer measures, called \delta -measures. If we fix one of these outer measures, we can ask a variety of questions related to its regularity properties and their reverse mathematical strength. These investigations also have implications for the standard Lebesgue measure on 2^{\omega} , since any of these s -dimensional \delta -measures reduces to the Lebesgue measure when s=1 . Other research projects on the reverse mathematics of measure theory have already explored many of its technicalities. One of the first extensive treatments was in Xiaokang Yu’s Ph.D. thesis (1987) and a subsequent joint paper with Stephen Simpson (1990), where it was demonstrated that \text{ACA}_{0} was necessary to prove that the Lebesgue measure of every open set exists, and that \text{WWKL}_{0} was necessary to prove that the Lebesgue measure is countably additive 14 , 13 . A 2009 paper by Simpson investigated the reverse math strength of the well-known regularity result that any Borel set contains an F_{\sigma} -subset of the same Lebesgue measure 11 . Surprisingly, Simpson showed that this result is independent of many standard subsystems of second-order arithmetic, as one can find models of \text{RCA}_{0} where this regularity property holds, but where the axioms of \text{WWKL}_{0} , \text{WKL}_{0} , and \text{ACA}_{0} may either hold or fail. In this paper, we restrict our attention to closed sets, and to questions that are some variation of the following: given a closed subset F , how hard is it to construct a closed subset E of some desired s -dimensional \delta -measure? In particular, we explore how the answer to this question may change depending on how the closed sets are coded; we introduce the notions of “standard closed” and “pruned closed” to describe differences in the structure of these sets’ representative trees. Other variables that affect the reverse math strength are the precision with which we specify the target measure of our set E , and whether the measure of our starting set F exists in the space. Preliminaries regarding the representations of closed sets and the Hausdorff \delta -measure can be found in Sections 2.2 and 2.3 respectively, and various regularity results for these measures are proven in Section 4.1. A few contrasting results of note are given below: Proposition 1.3 . The following is provable in \text{RCA}_{0} : If F\subseteq 2^{<\omega} is a nontrivial standard closed set with tree code Z_{F} , and c is such that 0\leq c\leq H^{s}_{n}(Z_{F}) , then for any \epsilon>0 , there exists a nontrivial standard closed set E\subseteq F whose associated tree code Z_{E} satisfies c\leq H^{s}_{n}(Z_{E})0 , there exists a nontrivial pruned closed set E\subseteq F whose associated tree code Z_{E} satisfies c\leq H^{s}_{n}(Z_{E})f(k)=n. The system \text{ACA}_{0} is also equivalent to various statements regarding sequence convergence. We state two such statements below, since they will be of use to us later. Proposition 2.3 . Over \text{RCA}_{0} , the system \text{ACA}_{0} is equivalent to the following: (1) In a compact metric space, every sequence of points has a convergent subsequence. (2) Every bounded monotone sequence of real numbers converges. As with the \text{WKL}_{0} equivalences, proofs of the above results can be found in 12 . Between the subsystems of \text{RCA}_{0} and \text{WKL}_{0} in reverse mathematical strength is the system \text{WWKL}_{0} , whose definition we give below. Definition 2.1 . We define Weak Weak König’s Lemma to be the following axiom: if T\subseteq 2^{<\omega} is a tree with the property that \lim_{n\to\infty}\frac{|\{\sigma\in T:|\sigma|=n\}|}{2^{n}}>0, then T has an infinite path. The formal system \text{WWKL}_{0} consists of the axioms of \text{RCA}_{0} plus Weak Weak König’s Lemma. It is clear that \text{WWKL}_{0} can be at most as strong as \text{WKL}_{0} , since the statement of Weak Weak König’s Lemma is just the standard Weak König’s Lemma restricted to a certain class of infinite trees. One can also demonstrate a computable infinite tree which meets the conditions of Weak Weak König’s Lemma but which does not have a computable path, proving that \text{WWKL}_{0} is strictly stronger than \text{RCA}_{0} . Showing that \text{WWKL}_{0} lies strictly below \text{WKL}_{0} requires constructing a more sophisticated model. While \text{WWKL}_{0} is not one of the standard “Big Five” systems, it has been shown to be equivalent to several theorems of measure theory and algorithmic randomness. 2.2. Closed Sets and their Representations In this paper, we will concern ourselves with measure and topological results in Cantor space, or 2^{\omega} . In this topology, we will use the notation N_{\sigma} to denote the basic open set N_{\sigma}=\{X\in 2^{\omega}:X\supseteq\sigma\}, where \sigma\in 2^{<\omega} . It is likely that many of the results in this work can be generalized to arbitrary compact metric spaces, although the details have not been formalized. Since we cannot speak of general subsets of 2^{\omega} within second-order arithmetic, we need a way to code a closed subset F\subseteq 2^{\omega} as a subset of \omega . To do this, we will almost exclusively use trees. Definition 2.2 . A tree over \{0,1\} is a subset T\subseteq 2^{<\omega} with the property that if \sigma\in T and \tau\subseteq\sigma , then \tau\in T as well. This property is called being closed under initial segments . A sequence X\in 2^{\omega} is a path through T if the length- n initial segment X\upharpoonright_{n} is an element of T for all n\in\omega . The set of all paths through a tree T is denoted by [T] . We will call a set F\subseteq 2^{\omega} standard closed if there exists a tree T\subseteq 2^{<\omega} with F=[T]. Classically, any closed set F\subseteq 2^{\omega} can be represented by some tree T\subseteq 2^{<\omega} . Unless otherwise specified, when we are working in second-order arithmetic and we speak of the existence of a closed set in 2^{\omega} , we implicitly mean a tree which represents that closed set. However, we will also discuss two other ways we can represent closed sets. Definition 2.3 . A pruned tree is a tree T\subseteq 2^{<\omega} with the additional property that for every \sigma\in T , we have at least one of \sigma^{\frown}0\in T or \sigma^{\frown}1\in T . As with a standard tree, we associated a pruned tree T with the closed set [T] in 2^{\omega} , the set of all paths through T . We will call a set F\subseteq 2^{\omega} pruned closed if there exists a pruned tree T with F=[T]. Certainly any closed set which has a pruned tree representation also has a standard tree representation, since a pruned tree is just a specific type of tree. However, depending on the axiom system being used, the converse does not always hold; we will explore the reverse math strength of the existence of pruned tree representations later in this section. Note that unlike the standard tree representation, the pruned tree representation for a closed set F\subseteq 2^{\omega} is unique, consisting of exactly the strings \sigma\in 2^{<\omega} which are initial segments of some element X\in F . Also, later in this work it will be convenient to have a name for closed subsets whose corresponding tree representations are infinite. If we are working in an axiom system equivalent to or stronger than \text{WKL}_{0} , this is equivalent to the closed set being nonempty. However, to avoid any ambiguity, we make the following definition. Definition 2.4 . Let F be a standard closed or pruned closed set in 2^{\omega}. We call F nontrivial if its corresponding tree (or pruned tree) in 2^{<\omega} is infinite. An alternative way to code a closed set is by specifying a countable sequence of elements of 2^{\omega} which are dense in that set, in the following sense: Definition 2.5 . Let S=\langle X_{n}\rangle_{n\in\omega} be a sequence of elements of 2^{\omega} . The set \bar{S} consists of all X\in 2^{\omega} with the property that \forall k\in\omega\>\exists n\in\omega\>\forall iX_{n}(i)=X(i). A set F\subseteq 2^{\omega} is called separably closed if it is empty, or if there exists a sequence S of elements of 2^{\omega} such that F=\bar{S} . When it comes to representing open sets in 2^{\omega} , we will use the notion defined below. This corresponds naturally to the idea of an open set as a union of cylinder sets. Definition 2.6 . A set U\subseteq 2^{\omega} is called open if there exists a set V\subseteq 2^{<\omega} with the property that for all X\in 2^{\omega} X\in U\iff\exists\sigma\in V\>\sigma\subseteq X. Such a set V is called a code for U . Without loss of generality, we may assume that V is closed upward under extensions: that is, if \sigma\in V and \tau\supseteq\sigma , then \tau\in V . Observe that if an open code V\subseteq 2^{<\omega} is nonempty, then there will necessarily be an element X in our model which lies in the corresponding open set U ; we can (for example) just take any string \sigma\in V and extend with infinitely many 0’s. Thus, we will freely use the term “nonempty open set” to refer to an open set U whose corresponding code V is nonempty, without any danger of ambiguity. It is straightforward to see that, given an open code V\subseteq 2^{<\omega} (closed under extensions), then T=2^{<\omega}\setminus V is a tree, and vice versa. From this fact, it follows that a set U\subseteq 2^{\omega} is open if and only if its complement F=2^{\omega}\setminus U is standard closed. While we will not work with this notion in this paper, one can also represent an open set as the complement of a separably closed set. This notion has been previously studied in the context of Baire Category, as mentioned in the introduction. It turns out that the ability to translate between different representations of the same closed set (or open set) is not trivial, as the results below will demonstrate. In the statements of these results, we will abuse language slightly for the sake of efficiency, as we will conflate the existence of closed subsets with the existence of their appropriate representations. For example, the statement “Every separably closed set is pruned closed” is technically shorthand for “For every countable sequence S of elements of 2^{\omega} , there exists a pruned tree T\subseteq 2^{<\omega} such that for all X\in 2^{\omega} , X\in\bar{S} if and only if X\in[T] .” First, we note that a pruned tree representation is the strongest in a sense, since it can generate both of the remaining representations. Proposition 2.4 . The following are provable in \text{RCA}_{0}: (1) Every pruned closed set in 2^{\omega} is standard closed. (2) Every pruned closed set in 2^{\omega} is separably closed. Proof. First, we note that (i) is trivial; as a pruned tree is just a special type of tree, any pruned closed set is automatically standard closed as well. For (ii), let T be a pruned tree. If T is finite, then the corresponding closed set F=[T] is empty, so F is separably closed trivially. Otherwise, let \{\sigma_{n}\}_{n\in\omega} be an enumeration of the elements of T . Define a sequence S=\langle X_{n}\rangle_{n\in\omega} in 2^{\omega} by setting X_{n} to be the leftmost extension of the string \sigma_{n} through T . More precisely, X_{n} is defined recursively by X_{n}(m)=\begin{cases}\sigma_{n}(m),&\text{if }m<|\sigma|\\ 0,&\text{if }m\geq|\sigma|\text{ and }X_{n}\upharpoonright_{m}^{\frown}0\in T\\ 1,&\text{ otherwise.}\end{cases} Note that the above construction is (uniformly) computable from \sigma_{n} , so the existence of the overall sequence S is provable in \text{RCA}_{0} . Also, since T is pruned, every string \sigma\in T satisfies at least one of \sigma^{\frown}0\in T or \sigma^{\frown}1\in T . Therefore, each sequence X_{n} defined in the above manner will be an element of [T] . We claim that \bar{S} and [T] define the same closed set. Indeed, if X\in[T] , then all initial segments X\upharpoonright_{k} (for k\in\omega ) are elements of T , so will appear as strings in the enumeration \{\sigma_{n}\}_{n\in\omega}. For each X\upharpoonright_{k} , the corresponding element of the sequence S will agree with X through the first k entries, so X satisfies the conditions for being in \bar{S} . On the other hand, suppose X\in\bar{S} . We wish to show that for each k\in\omega , the initial segment X\upharpoonright_{k} is an element of T . First, note that for each k , there must be some N_{k}\in\omega such that in our enumeration \{\sigma_{n}\}_{n\in\omega} of T , all strings \sigma_{n} with n\geq N_{k} have |\sigma_{n}|\geq k . This implies that for all X_{n} in the sequence S=\langle X_{n}\rangle_{n\in\omega} with n\geq N_{k} , the length- k initial segment of X_{n} will be an element of T (as T is closed under initial segments). Since X\in\bar{S} , we know there is some X_{n} in S such that X agrees with X_{n} for the first k entries. If we can find such an X_{n} at or after index N_{k} , then this implies X\upharpoonright_{k}=X_{n}\upharpoonright_{k} is an element of T . If not, then for all m\geq k , the witnessing element of S which agrees with X through the first m entries must occur before position N_{k} . By the infinite pigeonhole principle, one of these elements X_{n} must agree with X in all entries, i.e. X_{n}=X . By our earlier discussion, all X_{n} in the sequence S are elements of [T] , so in particular the string X\upharpoonright_{k}=X_{n}\upharpoonright_{k} is in T as desired. ∎ In contrast to the result above, obtaining a pruned tree representation from a standard or separately closed set, or translating between the latter two representations, requires much more axiomatic strength. As mentioned in the introduction, variations of items (iii) and (iv) of the theorem below have been proven before for arbitrary compact metric spaces: see 3 . However, we include the proofs anyway for the sake of completeness and consistency with our terminology in Cantor space. Theorem 2.5 . Over \text{RCA}_{0} , the following statements are all equivalent to \text{ACA}_{0} : (1) Every standard closed set in 2^{\omega} is pruned closed. (2) Every separably closed set in 2^{\omega} is pruned closed. (3) Every standard closed set in 2^{\omega} is separably closed. (4) Every separably closed set in 2^{\omega} is standard closed. Proof. We first show that \text{ACA}_{0} is sufficient to prove both (i) and (ii). In light of the previous proposition, this would also imply that \text{ACA}_{0} can prove (iii) and (iv). Claim 1: \text{ACA}_{0}\implies(i) Proof of Claim 1: Let T\subseteq 2^{<\omega} be a tree. Using arithmetic comprehension, we can define the tree \tilde{T} by \tilde{T}=\{\sigma\in T:\forall n\geq|\sigma|,\exists\tau\supseteq\sigma\text{ such that }|\tau|=n\text{ and }\tau\in T\}. Note that by the pigeonhole principle and closure under initial segments, \tilde{T} consists precisely of the strings in T which have infinitely many extensions which are also in T . (Note that \tilde{T} could potentially be empty.) We can then deduce that \tilde{T} is pruned; if \sigma has infinitely many extensions in T , then by the pigeonhole principle again, at least one of \sigma^{\frown}0 or \sigma^{\frown}1 must also have infinitely many extensions in T . It is then straightforward to verify that [T] and [\tilde{T}] represent the same closed set. As \tilde{T} is a subset of T , certainly any X\in[\tilde{T}] is also an element of [T] . On the other hand, if we have an element X\in[T] , then any initial segment \sigma\subseteq X has infinitely many extensions in T (namely, all finite initial segments \tau\subseteq X with |\tau|\geq|\sigma| ), and thus X\in[\tilde{T}] as well. This completes the proof of (i) under \text{ACA}_{0}. \square Claim 2: \text{ACA}_{0}\implies(ii) Proof of Claim 2: If we have a separably closed set which is empty, then the empty tree T is trivially a pruned tree representing the same closed set. So assume our separably closed set F is nonempty, and let S=\langle X_{n}\rangle_{n\in\omega} be a sequence representing F . Using arithmetic comprehension, we can define a pruned tree T by collecting all the finite initial segments of the elements in the sequence S . That is, T=\{\sigma\in 2^{<\omega}:\exists n\in\omega\text{ such that }\sigma\subseteq X_{n}\}. It is clear that T is closed under initial segments, and that any \sigma\in T has infinitely many extensions in T (namely, all sufficiently long initial segments of its witnessing element X_{n} ). Thus, T represents a pruned tree. We can also check that [T] represents the same closed set as \bar{S} . If X\in\bar{S} , then for each k\in\omega, there is some X_{n} in S for which X_{n}\upharpoonright_{k}=X\upharpoonright_{k} . By definition, X_{n}\upharpoonright_{k}=X\upharpoonright_{k} is an element of T , which since k is arbitrary proves that X\in[T] . Conversely, if X\in[T] , then for each initial segment X\upharpoonright_{k} , there exists some element of S which shares that same initial segment. This is precisely what it means to be an element of \bar{S} . \square We now wish to show that each of statements (i) - (iv) is sufficient to prove the axioms of \text{ACA}_{0} . Again, we will use the previous proposition to consolidate this argument. Under \text{RCA}_{0} , statement (i) implies statement (iii) and statement (ii) implies statement (iv). Therefore, it suffices to demonstrate a reversal argument for the weaker statements (iii) and (iv). Claim 3: (iii)\implies\text{ACA}_{0} Proof of Claim 3: Recall that by Theorem 2.2 , it suffices to show that under the assumed statement, every one-to-one function on the natural numbers has a range. Therefore, assume statement (iii) (every standard closed set in 2^{\omega} is separably closed), and let f:\omega\to\omega be a one-to-one function. For each n\in\omega , let \tau_{n} denote the length- (n+1) string consisting of n 0 ’s followed by a single 1 . Under \text{RCA}_{0} , we may define a tree T\subseteq 2^{<\omega} by setting \sigma\in T if and only if either: (1) \sigma consists entirely of 0’s (2) \sigma extends \tau_{n} for some n\in\omega , and there exists no k<|\sigma| with f(k)=n . Note that T does define a tree. If \sigma\in T according to condition (1) - i.e. \sigma consists entirely of 0’s - then certainly any prefix of \sigma will consist entirely of 0’s as well. If \sigma\in T according to condition (2), then any prefix of \tau\subseteq\sigma will either consist entirely of 0’s, or will have the same corresponding prefix \tau_{n} as \sigma . In the latter case, if no k with f(k)=n has been found before input |\sigma| , then certainly no witness will be found before input |\tau| either. Thus, \tau\in T as well. Now, if we are assuming statement (iii), then there must be some sequence S=\langle X_{k}\rangle_{k\in\omega} in 2^{\omega} such that \bar{S}=[T] . We claim that S and f together can be used to compute the range of f , which is a consequence of the following fact: n\notin\text{ran}(f)\iff\exists k\in\omega,X_{k}\supseteq\tau_{n}. To understand this correspondence, assume first that n\notin\text{ran}(f) . It follows that any infinite sequence X which extends \tau_{n} will be an element of [T] , since we will never locate a k for which f(k)=n . Such an X will be an element of \bar{S} as well, which means there must be some X_{k} in the sequence S which agrees with X up through the initial segment \tau_{n} , as desired. Conversely, if there is some X_{k} in the sequence S which extends \tau_{n} , then X_{k} must necessarily be an element of \bar{S}=[T]. From this, it follows that n cannot be in the range of f ; otherwise, some sufficiently long initial segment of X_{k} would be excluded from the tree T according to condition (2). Now that we have this correspondence, we can use both the function f and the sequence S to compute \text{ran}(f) . Given any n\in\omega , we can simply enumerate the natural numbers until we find k\in\omega such that either f(k)=n , or X_{k}\supseteq\tau_{n} . Exactly one of these occurrences will eventually happen, at which point we will have identified whether n is in the range of f . More formally, we have shown that \text{ran}(f) has a \Delta^{0}_{1} definition using parameters f and S=\langle X_{k}\rangle_{k\in\omega} , as n\in\text{ran}(f)\iff\exists k\>f(k)=n\iff\forall k\>\tau_{n}\nsubseteq X_{k}. Thus, \text{ran}(f) must exist by \Delta^{0}_{1} -comprehension in \text{RCA}_{0} . \square Claim 4: (iv)\implies\text{ACA}_{0} Once again, let f:\omega\to\omega be a one-to-one function. For each n\in\omega , let Y^{(n)} denote the (computable) infinite sequence with a 1 in position n and 0’s elsewhere, and define a sequence S=\langle X_{k}\rangle_{k\in\omega} by setting X_{k}=Y^{(f(k))}. Assuming statement (iv), there must be a tree T\subseteq 2^{<\omega} such that [T]=\bar{S} . We claim that T has the following property: n\in\text{ran}(f)\iff\forall k\in\omega,Y^{(n)}\upharpoonright_{k}\in T\iff Y^{(n)}\in[T]. Indeed, if n\in\text{ran}(f) , then the sequence Y^{(n)} will be an element of S , and thus will necessarily be in \bar{S}=[T]. Conversely, if n\notin\text{ran}(f) , then no element of the sequence S will have a 1 in position n . Thus, none of these elements can agree with Y^{(n)} beyond position n-1 , so Y^{(n)} cannot be in \bar{S}=[T]. Thus, the tree [T] provides a \Pi^{0}_{1} characterization of \text{ran}(f) . In combination with the \Sigma^{0}_{1} characterization given by f itself, we have shown that \text{ran}(f) is \Delta^{0}_{1} -definable, and so must exist by the axioms of \text{RCA}_{0} . This completes the proof of this claim, as well as the overall proof of this proposition. \square ∎ While we will briefly look at separably closed sets in the context of the Baire Category theorem (see Section 3.1), most of this paper will be concerned with standard and pruned closed sets (i.e. those which are represented by trees). These representations provide a natural way of approximating the sets’ measure, as we will demonstrate in the following subsection. If we are given a particular tree representation for a standard/pruned closed set F , we would like a way to code the set of all nontrivial closed subsets of F . It turns out that this can also be done using a tree. Before we introduce this representation, we observe that there is a standard (computable) bijection between \omega and 2^{<\omega} which enumerates the elements of 2^{<\omega} first by length and then lexicographically. For example, the first few elements of this enumeration are \langle\rangle,0,1,00,01,10,11,000,001,\dots Throughout the rest of this paper, we freely identify the elements of 2^{<\omega} with their counterparts in \omega under this bijection, letting the meaning be clear from context. In light of this bijection, we also introduce some useful notation. Definition 2.7 . Given an element X\in 2^{\omega} and a natural number n\in\omega , we let X^{\leq n} denote the initial segment of X with length 2^{n+1}-1 . If a finite string \nu\in 2^{<\omega} is such that |\nu|\geq 2^{n+1}-1 , then we use the notation \nu^{\leq n} similarly. This notation is convenient since X^{\leq n}(\sigma) will be defined for a particular \sigma (under the bijection mentioned above) if and only if |\sigma|\leq n . Definition 2.8 . Let T\subseteq 2^{<\omega} be a tree. Let S_{T}\subseteq 2^{<\omega} be the tree consisting of all \nu\in 2^{<\omega} which satisfy the following properties: (1) For all \sigma<|\nu| with \nu(\sigma)=1 , we also have \nu(\tau)=1 for all \tau\subseteq\sigma . (2) For all \sigma<|\nu| with \nu(\sigma)=1 , we have \sigma\in T . (3) For all n\in\omega such that \nu^{\leq n} is defined, at least one \sigma\in 2^{<\omega} of length n satisfies \nu(\sigma)=1 . If we have an element Z\in[S_{T}] , then we can identify Z with the subset T_{Z}\subseteq 2^{<\omega} consisting of exactly the strings \sigma for which Z(\sigma)=1 ; we will say that Z represents or codes the tree T_{Z} . Property (1) in the definition of S_{T} guarantees that Z does indeed code a tree, property (2) guarantees that this tree will be a subset of T , and property (3) guarantees that this tree will be infinite. Thus, the closed set [T_{Z}] will be a nontrivial closed subset of the closed set [T] . (Assuming we have access to Weak König’s Lemma, this also means that [T_{Z}] will be nonempty.) Likewise, if we have an arbitrary nontrivial standard/pruned closed subset of [T] , we can find a tree corresponding to that set which will be an element of [S_{T}] . At times, it will be convenient to work with a variant of S_{T} whose infinite paths all correspond to pruned trees. Such a variant is defined below. Definition 2.9 . Let T\subseteq 2^{<\omega} be a tree. Let \tilde{S}_{T}\subseteq 2^{<\omega} be the tree consisting of all \nu\in 2^{<\omega} which satisfy the conditions for S_{T} in the previous definition, as well as the following additional condition: (1) For all \sigma<|\nu| such that \nu(\sigma)=1 and such that \nu(\sigma^{\frown}0) and \nu(\sigma^{\frown}1) are both defined, we have at least one of \nu(\sigma^{\frown}0)=1 or \nu(\sigma^{\frown}1)=1 . In light of these results, we can impose a completely metrizable topology on the space of nontrivial closed subsets of a particular standard/pruned closed set F\subseteq 2^{\omega} . If T is a tree with F=[T] , then we can simply restrict the usual topology and metric on 2^{\omega} to the closed subset [S_{T}] or [\tilde{S}_{T}] . 2.3. Hausdorff Measure and its Representations The notion of Hausdorff measure on a metric space is a generalization of Lebesgue measure. This measure is the main object of study in the subfield of analysis known as geometric measure theory, of which a standard reference is 6 . The classical concept of Hausdorff measure is defined as a limit of a sequence of intermediate outer measures, which can be defined in the following way for Cantor space. Definition 2.10 . Let E\subseteq 2^{\omega} be a set, let \delta be a positive real number, and s a nonnegative real number. We call a countable or finite collection of cylinder sets \{N_{\sigma_{i}}\}_{i\delta can just be replaced with its two “halves” N_{\sigma^{\frown}0} and N_{\sigma^{\frown}1} , and the process can be repeated as many times as necessary until all cylinders have measure at most \delta . On the other hand, if s<1 , then different values of \delta can potentially yield different values of \mathcal{H}^{s}_{\delta}(E) . However, note that if \delta_{0}>\delta_{1} , then the collection of \delta_{1} -covers for a set E will be a subset of the collection of \delta_{0} -covers, which implies that \mathcal{H}^{s}_{\delta_{0}}(E)\leq\mathcal{H}^{s}_{\delta_{1}}(E) . Therefore, the limit in the definition below is (classically) well-defined, although it can potentially be infinite. Definition 2.11 . Let E\subseteq 2^{\omega} , and let s be a nonnegative number. Then the s-dimensional Hausdorff measure \mathcal{H}^{s}(E) is defined by \mathcal{H}^{s}(E)=\lim_{\delta\to 0}\mathcal{H}^{s}_{\delta}(E). The fact that the definition of Hausdorff measure involves checking infinitely many collections of open sets makes it somewhat nonconstructive and difficult to work with in a reverse math context. However, we can define a more explicit measure function in the case where E is closed, which will also correspond nicely to a more general discussion of “monotone functions” in Section 3.2. As we show below, this function will be equivalent to the usual definition of Hausdorff measure as long as we are in a sufficiently strong axiom system. First, we introduce some preliminary notation. Definition 2.12 . Let V\subseteq 2^{<\omega} , and let s\geq 0 . Define the s -weight of V by W_{s}(V)=\sum_{\sigma\in V}2^{-s|\sigma|} with W_{s}(\emptyset) defined to be 0. Definition 2.13 . Let S\subseteq 2^{<\omega} denote the set S_{T} from Definition 2.8 , where T is taken to be all of 2^{<\omega} . Suppose s\geq 0 and n\in\omega . We define a function \tilde{H}^{s}_{n}:S\to\mathbb{R} as follows. Given \nu\in S of length at least 1, we first find the largest integer m for which |\nu|\geq 2^{m+1}-1 , i.e. for which \nu^{\leq m} is defined. (We handle the case where \nu is the empty string \langle\rangle separately). We then proceed in cases depending on the value of m . • Case 1: If m\geq n , we define \tilde{H}^{s}_{n}(\nu)=\min\{W_{s}(V)\}, where the minimum is taken over all V\subseteq 2^{<\omega} with the following properties: (1) For all \sigma\in V , n\leq|\sigma|\leq m . (2) For all \sigma such that |\sigma|=m and \nu(\sigma)=1 , there is some \tau\in V with \tau\subseteq\sigma . • Case 2: If mZ_{k}\supseteq\sigma. As with BCTCIII, we will construct our desired X\in 2^{\omega} as the limit of an increasing sequence \{\sigma_{n}\}_{n\in\omega} whose elements satisfy three properties. Properties (1) and (2) will be the same as in the previous proof, while the new property (3) will be that for all n\in\omega , there exists some k\in\omega such that Z_{k}\supseteq\sigma_{n} . Note that since our final sequence \{\sigma_{n}\}_{n\in\omega} will be strictly increasing, for any m\in\omega we can find an element Z_{k} which agrees with our limit element X\in 2^{\omega} up to position m . Thus, X\in F=\bar{S} . To inductively construct the element \sigma_{n} , we fix an enumeration of all pairs (\tau,k) such that \tau\supsetneq\sigma_{n-1} and k\in\omega . For each pair, we check if \tau\in V_{n} and \tau\subseteq Z_{k} , and once we find such a pair we set \sigma_{n}=\tau . Again, we know such a pair must be encountered eventually because of density. Our inductive assumption on \sigma_{n-1} means that N_{\sigma_{n-1}}\cap F is nonempty, so there is some Y\in N_{\sigma_{n-1}}\cap U_{n}\cap F . Thus, we just need to consider an initial segment \tau\subseteq Y sufficiently long for both \tau\supsetneq\sigma_{n-1} and \tau\in V_{n} , and then consider k\in\omega such that Z_{k} agrees with Y up through the length of \tau . ∎ We finally turn to the complexity of BCTCI, which we will henceforth refer to as just BCTC. One might start by attempting to carry out a proof in \text{RCA}_{0} by following the structure of the argument for BCTCIII. However, the fact that the tree T representing F is not necessarily pruned causes issues with the inductive construction. Naturally, each \sigma_{n} in that construction needs to have infinitely many extensions in the tree in order for a limiting element X to be well-defined, yet we cannot determine in a computable way whether a given string \sigma in T has that property. Of course, if we have access to \text{ACA}_{0} we can just replace the tree T with a pruned subtree representing the same closed set F , and the BCTCIII proof goes through. But considering that other versions of the Baire Category theorem are provable in \text{RCA}_{0} , one might conjecture that BCTC is still relatively “simple” from a reverse math perspective, even if its power does reach beyond \text{RCA}_{0} . However, it turns out that \text{ACA}_{0} is in fact necessary, as the next result shows. However, first we introduce some notation. Definition 3.2 . Let \langle\rangle:\omega^{2}\to\omega denote a fixed pairing function. Assume that \langle\rangle has the property that for all n,m\in\omega : • \langle n,m\rangle<\langle n+1,m\rangle • \langle n,m\rangle<\langle n,m+1\rangle For X\in 2^{\omega} and n\in\omega , let \langle X\rangle_{n}\in 2^{\omega} be defined by \langle X\rangle_{n}(m)=X(\langle n,m\rangle), for all m\in\omega . We call \langle X\rangle_{n} the n -th column of X . We can generalize this definition to finite strings \sigma\in 2^{<\omega} . Here, the n -th column \langle\sigma\rangle_{n} will be another finite string (possibly empty), since for a fixed n\in\omega , \sigma(\langle n,m\rangle) will be undefined for all but finitely many m\in\omega . Theorem 3.6 . Over \text{RCA}_{0} , BCTC is equivalent to \text{ACA}_{0}. Proof. To show that \text{ACA}_{0} implies BCTC, let T be a tree representing the closed set F from the statement of BCTC. Under \text{ACA}_{0} , we can find a pruned tree \tilde{T}\subseteq T such that [\tilde{T}]=[T]=F (see Theorem 2.5 ). Using \tilde{T} , we can then carry out the proof of BCTCIII, which does not require any axioms beyond \text{RCA}_{0} . For the opposite implication, we will use BCTC to show that every one-to-one function has a range. Let f:\omega\to\omega be a one-to-one function, and consider the f -computable tree T\subseteq 2^{<\omega} defined as follows. For \sigma\in 2^{<\omega} , we set \sigma\in T if and only if for all n\in\omega such that \langle\sigma\rangle_{n} is nonempty, \langle\sigma\rangle_{n}\text{ contains a }0\implies\text{there exists no }k<|\sigma|\text{ such that }f(k)=n. We first observe that this does indeed define a tree. If \sigma\in T and \tau\subseteq\sigma , then the properties of the pairing function guarantee that \langle\tau\rangle_{n}\subseteq\langle\sigma\rangle_{n} for all n\in\omega . If n is such that \langle\tau\rangle_{n} contains a 0, then so will \langle\sigma\rangle_{n} , which if \sigma\in T means that there is no k<|\sigma| with f(k)=n. Thus, we will not find a witnessing k<|\tau| either, which means \tau\in T since this applies to all n . Let F=[T] denote the closed set corresponding to T . Note that F is nonempty, since it (for example) contains the infinite sequence consisting entirely of 1’s. Claim 1: If X\in F , then any n\in\omega for which \langle X\rangle_{n} contains a 0 is not in the range of f . Proof of Claim 1: Suppose there did exist some k\in\omega for which f(k)=n . If \langle X\rangle_{n} contains a 0 (say at position m ) we can choose \tau\subseteq X to be a finite initial segment long enough for |\tau|>k and for \langle\tau\rangle_{n}(m)=\langle X\rangle_{n}(m)=0 to be defined. By the definition of T , \tau cannot be an element of this tree, but this contradicts the fact that X was in [T]=F . \square Next, we define a sequence of subsets \{V_{n}\}_{n\in\omega} of 2^{<\omega} , which will code a sequence of open sets \{U_{n}\}_{n\in\omega} in 2^{\omega} . For each n\in\omega , we set \sigma\in V_{n} if and only if at least one of the following conditions holds: (1) There exists k<|\sigma| with f(k)=n . (2) \langle\sigma\rangle_{n} contains a 0. Note that each V_{n} is closed upward under taking extensions. Claim 2: For every n\in\omega , the open set U_{n} is dense in F . Proof of Claim 2: Let \sigma\in 2^{<\omega} be such that N_{\sigma}\cap F is nonempty, and let X be an element of N_{\sigma}\cap F . We wish to show that N_{\sigma}\cap F contains an element of U_{n} . Suppose first that n\in\text{ran}(f) . If k\in\omega is such that f(k)=n , and \tau\subseteq X is a finite initial segment with length |\tau|>k , then we see that \tau\in V_{n} by condition (1). Thus, the sequence X itself is already an element of U_{n} , and we are done. On the other hand, suppose n\notin\text{ran}(f) . Let m\in\omega be the least index for which \langle\sigma\rangle_{n}(m) is undefined. Define a sequence Y\in 2^{\omega} by setting \langle Y\rangle_{n}(m)=Y(\langle n,m\rangle)=0 , and by setting all other entries of Y to agree with the respective entries of X . (Note that if \langle X\rangle_{n}(m) was already equal to 0, then we just have Y=X ). Observe that this sequence Y must exist in the model, since it is computable from the element X . We first note that Y is an element of N_{\sigma} , since we didn’t change any entries of X which agreed with the defined entries of \sigma . We also observe that Y is in U_{n} , since we can take an initial segment \tau\subseteq Y sufficiently long that \langle\tau\rangle_{n}(m)=\langle Y\rangle_{n}(m)=0 , putting \tau\in V_{n} by condition (2). Finally, we observe that Y is an element of F . For suppose \tau\subseteq Y is a finite initial segment, and i\in\omega is such that \langle\tau\rangle_{i} is nonempty. If i\neq n , then \langle\tau\rangle_{i}=\langle\tau^{\prime}\rangle_{i} , where \tau^{\prime} is the initial segment of X with the same length as \tau . As X was an element of F , we know that \tau^{\prime}\in T , and thus \langle\tau^{\prime}\rangle_{i}=\langle\tau\rangle_{i} containing a 0 means that there is no k<|\tau^{\prime}|=|\tau| with f(k)=i . For i=n , we know that there is no k<|\tau| with f(k)=n since we assumed that n\notin\text{ran}(f). This means that regardless of the entries of \langle\tau\rangle_{n} , \tau meets the conditions for being in T , so Y\in[T]=F as desired. \square Having shown that the relevant hypotheses hold, we can now apply BCTC to deduce that \bigcap_{n\in\omega}U_{n} is dense in F . In particular, there must exist an element Z\in F\cap\bigcap_{n\in\omega}U_{n} , since F is nonempty. We claim that \text{ran}(f) is computable from Z and f . Indeed, consider the algorithm that, on input n , searches through the initial segments of Z until a \sigma is found such that either (1) there exists k<|\sigma| with f(k)=n , or (2) \langle\sigma\rangle_{n} contains a 0. Since we know Z is an element of U_{n} , such an initial segment must be located eventually, as these are just the conditions for entering the coding set V_{n} . If the string \sigma meets the first condition, then clearly n\in\text{ran}(f) . If \sigma meets the second condition, then we know that \langle Z\rangle_{n} contains a 0, which means n\notin\text{ran}(f) since Z\in F . (See the previous Claim 1.) Since our algorithm can distinguish between these two conditions, we can determine whether n is in \text{ran}(f) , as desired. (Formally, one could argue that \text{ran}(f) exists by \Delta^{0}_{1} -comprehension with parameters f and Z , similar to the proof of Theorem 2.5 ). ∎ 3.2. Monotone Functions on Closed Sets In this section, we introduce a new context in which we can consider BCTC and its reverse mathematical strength. This context involves the behavior of certain “monotone” functions defined on closed sets. Definition 3.3 . Let T\subseteq 2^{<\omega} be a tree, and let \tilde{f}:T\to\mathbb{R} be a function. We say that \tilde{f} is monotone decreasing if \tilde{f}(\sigma)\geq\tilde{f}(\tau) whenever \sigma\subseteq\tau . Similarly, we say that \tilde{f} is monotone increasing if \tilde{f}(\sigma)\leq\tilde{f}(\tau) whenever \sigma\subseteq\tau . Definition 3.4 . Let T\subseteq 2^{<\omega} be a tree, and let F=[T] be the corresponding closed set. If \tilde{f}:T\to\mathbb{R} is a function, we define the partial function f:F\rightharpoonup\mathbb{R} by f(X)=\lim_{n\to\infty}f(X\upharpoonright_{n}), if the quantity on the right exists. Observe that if \tilde{f} is a monotone increasing function which is bounded above, or a monotone decreasing function which is bounded below, then the limit in the definition above always exists “classically.” However, this limiting value may not exist in the model for all X\in F if we are working in a system strictly weaker than \text{ACA}_{0} . That said, we will sometimes abuse notation in the following way. If \tilde{f} is a monotone decreasing function on a tree T , X is an element of [T] , and c is a real number, then we may write f(X)\geq c to mean that \tilde{f}(X\upharpoonright_{n})\geq c for all n\in\omega , even if the limiting value for f(X) doesn’t exist in the model. Similarly, writing f(X)0 , there exists some X\in F such that f(X)<\alpha+\epsilon . The notion of supremum for a monotone increasing function is defined similarly. It turns out that the realization of infimums (or supremums) of certain types of functions gives equivalent characterizations of \text{ACA}_{0} , which can be realized by considering their similarities to BCTC (recall that the equivalence of these statements was proven in the last section). First, suppose that we have a tree T\subseteq 2^{<\omega} with corresponding closed set F=[T] and a function \tilde{f}:T\to\mathbb{R} which is monotone decreasing. Let f:F\rightharpoonup\mathbb{R} be the induced function, and suppose there exists \alpha\in\mathbb{R} such that \alpha is an infimum of f over F. Under what conditions is there an element X\in F for which f(X)=\alpha ? (Of course, we could also ask the symmetric question involving a monotone increasing function and a supremum.) We observe that the conditions mentioned above are not sufficient to guarantee that the infimum is realized, in any axiom system. Proposition 3.7 . There exists a tree T\subseteq 2^{<\omega} , a monotone decreasing function \tilde{f}:T\to\mathbb{R} , and a real number \alpha such that \alpha is an infimum of the induced function f over F=[T] , but there is no X\in F for which f(X)=\alpha . Proof. Let T be all of 2^{<\omega} (meaning that F is all of 2^{\omega} ). We define a monotone decreasing function \tilde{f}:2^{<\omega}\to\mathbb{R} by setting \tilde{f}(\sigma)=1 if \sigma consists entirely of 0’s (or if \sigma is the empty string), and otherwise setting \tilde{f}(\sigma)=2^{-k} , where k is the position of the first 1 in \sigma . It is clear that \tilde{f} is monotone decreasing. We also see that 0 is an infimum of the induced function f over 2^{\omega} , yet there is no X\in 2^{\omega} for which f(X)=0 . If X is the sequence consisting entirely of 0’s, then f(X)=1 . Otherwise, f(X)=2^{-k}>0 , where k is the position of the first 1 in X . ∎ However, there are more restricted types of monotone decreasing functions that do realize their infimums. To describe them, we introduce some terminology. For brevity, we assume going forward that T,F,\tilde{f},f, and \alpha are defined as in Definition 3.5 . Definition 3.6 . Let X be an element of [T]=F . We say that X is a limit point for \alpha if for every \sigma\subseteq X and every \epsilon>0 , there exists Y\in F such that \sigma\subseteq Y and f(Y)<\alpha+\epsilon . In other words, if X is a limit point, then we can find points which are arbitrarily close to Y (in the usual metric on 2^{\omega} ) which get mapped arbitrarily close to \alpha . The following definitions describe two “extreme” properties that a function can have regarding limit points. Definition 3.7 . We say that f is dense above \alpha if every X\in F is a limit point for \alpha . Definition 3.8 . We say that f is separated from \alpha if the only limit points above \alpha are those points X\in F for which f(X)=\alpha (if they exist). Despite describing very different types of functions, both of these extreme behaviors allow the infimum \alpha to be realized “classically.” These principles are summarized in the following principles. Proposition 3.8 (Dense Monotone Minimum (DMMin)) . If f is dense above \alpha , then there exists X\in F for which f(X)=\alpha . Proposition 3.9 (Separated Monotone Minimum (SMMin)) . If f is separated from \alpha , then there exists X\in F for which f(X)=\alpha . Given the “density” properties displayed by the notion of limit point, it is not terribly surprising that the Dense Monotone Minimum principle is related to BCTC. In fact, the two statements are equivalent, which, by the result in the previous section, implies DMMin is equivalent to \text{ACA}_{0} . We can also demonstrate an equivalence directly between \text{ACA}_{0} and SMMin, which gives the following four-fold equivalence theorem: Theorem 3.10 . Over \text{RCA}_{0} , the following are equivalent: (1) \text{ACA}_{0} (2) BCTC (3) SMMin (4) DMMin Proof. We have already shown the equivalence of (i) and (ii) in Theorem 3.6 . We will complete the chain by proving the equivalences \text{(ii)}\iff\text{(iv)} and \text{(i)}\iff\text{(iii)} . Claim 1 : (ii)\implies(iv) , i.e. BCTC implies DMMin . Proof of Claim 1: Let T,F,\tilde{f},f,\alpha be as in the statement of Dense Monotone Minimum. For each n\in\omega , define the set V_{n}=\{\sigma\in 2^{<\omega}:\sigma\notin T\text{ or }\tilde{f}(\sigma)<\alpha+2^{-n}\}. Since T is a tree and \tilde{f} is monotone decreasing, each set V_{n} is closed under taking extensions, so corresponds to an open set U_{n}\subseteq 2^{\omega}. Furthermore, each set U_{n} is dense in F . Indeed, suppose \sigma\in 2^{<\omega} is such that N_{\sigma}\cap F\neq\emptyset , and let X be an element of F extending \sigma . Since f is dense above \alpha , we know that X is a limit point for \alpha . Therefore, there must be some Y\in F for which \sigma\subseteq Y and f(Y)<\alpha+2^{-n} . The latter statement then implies that there is some initial segment \tau\subseteq Y for which \tilde{f}(\tau)<\alpha+2^{-n} , and thus Y\in U_{n} . We can now apply BCTC to conclude that \bigcap_{n\in\omega}U_{n} is dense in F . In particular, this means that the intersection \left(\bigcap_{n\in\omega}U_{n}\right)\cap F is nonempty (as the existence of a finite infimum implies that F itself is nonempty). Taking X_{0} to be an element of this intersection, we observe that we must have f(X_{0})=\lim_{n\to\infty}\tilde{f}(X_{0}\upharpoonright_{n})=\alpha, since X_{0} is in F=[T] yet has initial segments in every set V_{n} . This completes the proof of Claim 1. \square Claim 2: (iv)\implies(ii) , i.e. DMMin implies BCTC. Proof of Claim 2: Assume that F is a standard closed set, and \{U_{n}\}_{n\in\omega} is a sequence of open sets in 2^{\omega} such that each U_{n} is dense in F . We wish to show that the intersection \bigcap_{n\in\omega}U_{n} is dense in F . So let \nu\in 2^{<\omega} be such that N_{\nu}\cap F is nonempty. Let F^{\prime} denote the closed set N_{\nu}\cap F , and let T^{\prime} be a tree representing F^{\prime} . (Note that we can obtain this computably from our tree representing F just by taking all sequences which are compatible with \nu ). Additionally, let V_{n} denote the set of strings representing each open set U_{n} . We define a monotone decreasing function \tilde{f}:T^{\prime}\to\mathbb{R} by setting \tilde{f}(\sigma)=2^{-k-1} , where k is the largest index with 0\leq k<|\sigma| such that \sigma\in V_{i} for all i with 0\leq i\leq k ; if no such k exists, we set \tilde{f}(\sigma)=1 . Given that the sets V_{n} are all closed under taking extensions, it is straightforward to check that \tilde{f} is monotone decreasing. Additionally, we see that 0 is the infimum of the induced function f over F^{\prime} . One one hand, 0 is certainly a lower bound for f , since \tilde{f} only outputs positive values. To see that 0 is the greatest lower bound, let \epsilon>0 be arbitrary, and let n\in\omega be such that 2^{-n-1}<\epsilon. Since each of U_{0},U_{1},\dots,U_{n} is dense in the original set F , we can construct an element X_{n}\in F^{\prime}\cap(\bigcap_{i=0}^{n}U_{i}) as follows. First, choose X_{0}\in F^{\prime}\cap U_{0} , and let \tau_{0}\subseteq X_{0} be sufficiently long that \nu\subsetneq\tau_{0} and \tau_{0}\in V_{0} . By density of U_{1} , we can then choose X_{1}\in N_{\tau_{0}}\cap F\cap U_{1} and select an initial segment \tau_{1}\subseteq X_{1} with \tau_{0}\subsetneq\tau_{1} and \tau_{1}\in V_{1} . We can continue inductively in this manner until we have obtained a sequence of strings \nu\subsetneq\tau_{0}\subsetneq\tau_{1}\subsetneq\dots\subsetneq\tau_{n}, and a corresponding sequence of element X_{0},X_{1},\dots,X_{n} with the property that each \tau_{i}\in V_{i} and each X_{i}\in N_{\tau_{i}}\cap F. Note also that since our sequence of \tau_{i} ’s is strictly increasing in length, each \tau_{i} must have length greater than i . For our final element X_{n}\in F , we observe that we must have f(X_{n})\leq 2^{-n-1}<\epsilon . Our inductive construction, and the fact that the sets V_{i} are closed under taking extensions, means that the initial segment \tau_{n}\subseteq X_{n} must be an element of each of V_{0},V_{1},\dots,V_{n} . Thus, \tilde{f}(\tau_{n})\leq 2^{-n-1} as desired. Finally, we observe that every X\in F^{\prime} is a limit point over 0 , meaning that f is dense above 0. Again, this comes from the density of each set U_{n} in our original set F . Let \sigma\subseteq X and \epsilon>0 be arbitrary. To construct an element Y\in F^{\prime} with Y\supseteq\sigma and f(Y)<\epsilon , we essentially follow the same procedure used in verifying that 0 was the infimum of f over F^{\prime} . We just start by choosing an X_{0} in F\cap N_{\sigma}\cap N_{\nu}\cap U_{0} , rather than one which is only in F\cap N_{\nu}\cap U_{0}=F^{\prime}\cap U_{0} . At this point, we can use DMMin to conclude that there is some Z\in F^{\prime}=N_{\nu}\cap F for which f(Z)=0 . We can then check that this Z must be in \bigcap_{n\in\omega}U_{n} . Indeed, for any n\in\omega , we can choose an initial segment \tau\subseteq Z for which \tilde{f}(\tau)\leq 2^{-n-1}. From the definition of \tilde{f} , we must have \tau in each of V_{0},V_{1},\dots V_{n} , meaning that Z\in U_{0},U_{1},\dots,U_{n} . This completes the proof of Claim 2, implying the full equivalence of statements (ii) and (iv). \square Claim 3: (i)\implies(iii) , i.e. \text{ACA}_{0} implies SMMin. Proof of Claim 3: Let T,f,\tilde{f},f, and \alpha be as in the statement of Separated Monotone Minimum. First, by Theorem 2.5 we may use \text{ACA}_{0} to obtain a pruned tree representation \tilde{T} of F=[T] . Observe that F must be nonempty since f has a finite infimum over F , and thus \tilde{T} is infinite. We define a sequence \langle X_{n}\rangle_{n\in\omega} uniformly in n as follows. For each n\in\omega , we enumerate the elements of \tilde{T} with length at least n until we find a string \sigma for which \tilde{f}(\sigma)<\alpha+2^{-n}. By the definition of infimum, we know this must happen eventually. Indeed, there must be some X\in F=[\tilde{T}] and some initial segment X\upharpoonright_{k} for which \tilde{f}(X\upharpoonright_{k})<\alpha+2^{-n} , and since \tilde{f} is monotone decreasing, we may assume that this initial segment has length at least n . Once this \sigma has been identified, we then define X_{n} to be the leftmost path through \tilde{T} above \sigma , which we can construct in a computable way since \tilde{T} is pruned. At this point, we have constructed a sequence of elements in a compact subspace F of 2^{\omega} . Using \text{ACA}_{0} again, we can find a subsequence \langle X_{k_{i}}\rangle_{i\in\omega} which converges to some Y\in F (see Theorem 2.3 ). We claim that this Y satisfies f(Y)=\alpha . For suppose not; then since f is separated from \alpha , we could conclude that Y was not a limit point for \alpha . Thus, there would be some initial segment \tau\subseteq Y and some \epsilon>0 such that all X\in F which extend \tau would yield f(X)\geq\alpha+\epsilon . But now we could choose an element X_{k_{i}} sufficiently far along in our subsequence such that X_{k_{i}} agrees with Y up through the length of \tau , yet the index n of X_{k_{i}} in the original sequence satisfies 2^{-n}<\epsilon . This last would imply that f(X_{k_{i}})<\alpha+2^{-n}<\alpha+\epsilon from the construction of \langle X_{n}\rangle_{n\in\omega}, contradicting our assumptions about Y . Therefore, we must have f(Y)=\alpha , completing the proof of Claim 3. \square Claim 4: (iii)\implies(i) , i.e. SMMin implies \text{ACA}_{0} . Proof of Claim 4: As in previous proofs, we will use SMMin to prove that every one-to-one function has a range. The setup used is somewhat similar to the proof that BCTC implies \text{ACA}_{0} , as seen in Theorem 3.6 . Let g:\omega\to\omega be an arbitrary one-to-one function. Define a tree T\subseteq 2^{<\omega} by setting \sigma\in T if and only if for all n<|\sigma| , \sigma(n)=0\implies\text{there exists no }k<|\sigma|\text{ with }g(k)=n. It is straightforward to verify that T is a tree; let F=[T] denote the corresponding closed set. We also observe that for any X\in 2^{\omega}, we have X\in F\iff\forall n\in\omega\>(X(n)=0\rightarrow n\notin\text{ran}(g)). The proof of this correspondence is also straightforward and is similar to the argument used for the analogous statement from the proof of Theorem 3.6 . Now, we define a function \tilde{f}:T\to\mathbb{R} as follows. First, for any \sigma\in T we use the notation A[\sigma] to denote the set of all n<|\sigma| for which either \sigma(n)=0 , or \sigma(n)=1 and there exists k<|\sigma| with g(k)=n . Note that A[\sigma] is computable from \sigma . We then set \tilde{f}(\sigma)=1-\left(\sum_{n\in A[\sigma]}2^{-n-1}\right). Note that \tilde{f} is monotone decreasing, which follows from the easy observation that \sigma\subseteq\tau implies A[\sigma]\subseteq A[\tau]. We also claim that \tilde{f} has an infimum of 0. As \tilde{f} can only output positive values (the sum being subtracted is always less than 1), 0 is certainly a lower bound for \tilde{f} . To see that 0 is the greatest lower bound, let \epsilon>0 be arbitrary, and choose n\in\omega so large that 2^{-n}=1-\left(\sum_{i=0}^{n-1}2^{-i-1}\right)<\epsilon. Let \sigma be the length- n string such that for all 0\leq k0 (or f(X) is undefined). In this case, there must be some k\in\omega for which X(k)=1 but n\notin\text{ran}(g) . Otherwise, for any \epsilon>0 we could find an initial segment \tau\subseteq X for which \tilde{f}(\tau)<\epsilon ; the argument is similar to that used above in verifying that 0 was the infimum of f . With that in mind, choose such a witnessing k for which X(k)=1 but k\notin\text{ran}(g), and let \sigma\subseteq X be long enough that \sigma(k)=X(k) is defined. Then we see that for any Y\in F which extends \sigma and any initial segment \tau\subseteq Y , we will never have k\in A[\tau] . Thus, the sum being subtracted in the definition of \tilde{f}(\tau) will always be missing the term 2^{-k-1} , meaning that the difference will always be at least 2^{-k}. Therefore, if f(Y) is defined, it must be the case that f(Y)\geq 2^{-k}>0 , proving our desired separation property. At this point, we can finally use SMMin to conclude that there is some X\in F for which f(X)=0 . We claim that for this X , we have X(n)=1 if and only if n\in\text{ran}(g) , which tells us the range of g exists in our model. On one hand, we’ve already mentioned that for any X\in F , X(n)=0 implies that n\notin\text{ran}(g) . On the other hand, our separation argument showed that any n for which X(n)=1 must satisfy n\in\text{ran}(g) . If there were an n for which this failed, then we could take an initial segment \tau\subseteq X long enough that any Y\in F extending \tau would give f(Y)\geq 2^{-n}, contradicting our assumption that f(X)=0 . This completes the proof of Claim 4, and of the entire theorem. \square ∎ 4. Measure Regularity Results If we return to the formalization of Lebesgue and Hausdorff measure for closed sets that was discussed in the introduction, we see that this function represents a natural example of a monotone decreasing function on Cantor space. Therefore, the results from the previous section can help us deduce the reverse mathematical strength of some measure regularity results. These same techniques will also aid us in the analysis of the Besicovitch Theorem for Hausdorff measure in the final section. 4.1. Regularity of H^{s}_{n} measure In this section, we assume that we have some fixed s\geq 0 and n\in\omega , and we will work with the H^{s}_{n} measure as defined in Section 2.3. For these results, we assume that we start with some (standard or pruned) closed set F , and we seek to construct a closed subset E\subseteq F with some specified measure. The complexity of this construction varies depending on how the closed sets are represented as well as on how precisely the measures are specified. Note that if we consider the specific measure H^{1}_{1} , we obtain a version of the standard Lebesgue measure. This will be equivalent to the normal definition of Lebesgue measure in \text{WKL}_{0} and stronger systems, but in any system it still provides a well-defined function on the space of “tree codes.” While the case of Lebesgue measure may hold the most interest, we decided to work with the general measure H^{s}_{n} (for s\geq 0 and n\in\omega ) since those versions of the results will be needed for the discussion on Besicovitch’s theorem later. As in the section on general monotone functions, we will abuse notation slightly in writing inequalities involving H^{s}_{n} , since the limiting value of H^{s}_{n}(Z) itself may not exist for every tree code Z without the axioms of \text{ACA}_{0} . (See the paragraph before Definition 3.5 for the interpretation of these inequalities). First, we demonstrate how closed sets which satisfy a desired measure bound can be coded topologically. Definition 4.1 . Let F\subseteq 2^{\omega} be a nontrivial standard closed set, and let T_{F}\subseteq 2^{<\omega} be a tree coding F . Recall from Section 2.2 that S_{T_{F}} and \tilde{S}_{T_{F}} represent the trees whose infinite paths code standard subtrees and pruned subtrees of T_{F} , respectively. Let Z_{F}\in\omega be a code for T_{F} , and let c be a real number such that 0\leq c\leq H^{s}_{n}(Z_{F}) . Then we define \mathcal{S}^{c}_{F}\subseteq 2^{\omega} as the closed set generated by the following tree: \{\nu\in S_{T_{F}}:\tilde{H^{s}_{n}}(\nu)\geq c\}. Note that the monotonicity of the function \tilde{H}^{s}_{n} guarantees that the set above is indeed a tree. We define \tilde{\mathcal{S}}^{c}_{F} similarly, using \tilde{S}_{T_{F}} in place of S_{T_{F}} . Observe that if Z\in\mathcal{S}^{c}_{F} or \tilde{\mathcal{S}}^{c}_{F} , then H^{s}_{n}(Z)\geq c , and the associated closed set E_{Z} will be a subset of F . Lemma 4.1 . The following is provable in \text{RCA}_{0} : Let F be a nontrivial closed set, and let \mathcal{S}^{c}_{F} and \tilde{\mathcal{S}}^{c}_{F} be defined as above. If \mathcal{S}^{c}_{F} (respectively \tilde{\mathcal{S}}^{c}_{F} ) is nonempty, we have the following properties for the restriction of the monotone decreasing function H^{s}_{n} : • c is an infimum of H^{s}_{n} over \mathcal{S}^{c}_{F} (respectively \tilde{\mathcal{S}}^{c}_{F} ) • H^{s}_{n} is dense above c over \mathcal{S}^{c}_{F} (respectively \tilde{\mathcal{S}}^{c}_{F} ) Proof. For ease of notation, we will use the set \mathcal{S}^{c}_{F} for the following proof. The construction for \tilde{\mathcal{S}}^{c}_{F} is the exact same, and we will point out the places where the distinction is relevant. We will also assume initially that c is positive; we will discuss the case when c=0 at the end. As mentioned above, all elements Z\in\mathcal{S}^{c}_{F} will satisfy H^{s}_{n}(Z)\geq c . Therefore, we wish to show that given an arbitrary Z\in\mathcal{S}^{c}_{F} , any finite initial segment \tau\subseteq Z , and any \epsilon>0 , there exists some X\in\mathcal{S}^{c}_{F} with \tau\subseteq X and c\leq H^{s}_{n}(X)m , then Y_{0}(\sigma)=1 if and only if Y(\sigma\upharpoonright_{m})=1 and Z(\sigma)=1 . Since Y_{0} is computable from Z , the existence of the element Y_{0} is provable in \text{RCA}_{0} . Given the fact that Z\in[S_{T_{F}}] , it is straightforward to check that Y_{0} represents a tree, and that this tree is a subtree of T_{F} . Additionally, if Z represents a pruned tree (i.e. if Z\in[\tilde{S}_{T_{F}}] ), then Y_{0} will represent a pruned tree as well. If the tree for Z is not pruned, then it is possible that Y_{0} codes a finite tree, since the length- m strings which remain may all code “dead ends.” This means that Y_{0} may not actually be an element of [S_{T_{F}}] (since this set only contains codes for nontrivial closed sets), but we can define H^{s}_{n} in the same way. Observe that by property (2), we will have at most K length- m strings \sigma for which Y_{0}(\sigma)=1 , since each of the K -many length- n^{\prime} strings represented in Z will either have no extensions represented in Y_{0} , or exactly one. If we take U to consist of exactly these extensions, then W_{s}(U)\leq K\cdot 2^{-sm}0 . If H^{s}_{n}(Z)=0 , then Z itself works as our witnessing element X\in\mathcal{S}_{F}^{c} with 0\leq H^{s}_{n}(X)<\epsilon. Otherwise, choose d>0 such that d<\epsilon and d\leq H^{s}_{n}(Z) . Then our Z will be an element of \mathcal{S}^{d}_{F} , so we can apply the argument above with respect to this positive d , using the same Z and \tau but with \delta=\epsilon-d in place of \epsilon . This will yield an element X\supseteq\tau of \mathcal{S}^{d}_{F}\subseteq\mathcal{S}^{0}_{F} which satisfies 00 , there exists a nontrivial standard closed (respectively, pruned closed) set E\subseteq F whose associated tree code Z_{E} satisfies c\leq H^{s}_{n}(Z_{E})0 , there exists a nontrivial pruned closed set E\subseteq F whose associated tree code Z_{E} satisfies c\leq H^{s}_{n}(Z_{E})0 . For the reversal, consider any infinite tree T , and let Z\in 2^{\omega} and F=[T] be the corresponding code and closed set respectively. Note that F is nontrivial since T is infinite. Choose any c\geq 0 such that 0\leq c\leq H^{s}_{n}(Z_{F}) , any \epsilon>0 , and apply the statement to choose a nontrivial pruned closed E\subseteq F whose code Z_{E} satisfies c\leq H^{s}_{n}(Z_{E})0 and apply the previous corollary to c=d to obtain a nontrivial pruned closed set E\subseteq F whose code Z_{E} satisfies d\leq H^{s}_{n}(Z_{E})0 , there is some valid 2^{-n} -cover of F with weight less than d+\delta . As E is a subset of F , this cover would be valid for E as well, so we can conclude that H^{s}_{n}(Z_{E})0 was arbitrary, we can combine this observation with the previous inequality of H^{s}_{n}(Z_{F})\geq d to conclude that H^{s}_{n}(Z_{E})=d as desired. The reversal is the same as for the previous corollary, again making use of the fact that we can computably find an infinite path through any infinite pruned tree. ∎ Consider now the assertion that we can obtain a closed set with an exact positive measure, although unlike the previous result, this measure may be strictly less than that of the original set. We again break this down into cases depending on the representations of the sets involved. Proposition 4.5 . (Reg-S) If F\subseteq 2^{\omega} is a nontrivial standard closed set with tree code Z_{F} , and c is such that 0\leq c\leq H^{s}_{n}(Z_{F}) , then there exists a nontrivial standard closed set E\subseteq F whose associated tree code Z_{E} satisfies H^{s}_{n}(Z_{E})=c . Proposition 4.6 . (Reg-SP) If F\subseteq 2^{\omega} is a nontrivial standard closed set with tree code Z_{F} , and c is such that 0\leq c\leq H^{s}_{n}(Z_{F}) , then there exists a nontrivial pruned closed set E\subseteq F whose associated tree code Z_{E} satisfies H^{s}_{n}(Z_{E})=c . Proposition 4.7 . (Reg-P) If F\subseteq 2^{\omega} is a nontrivial pruned closed set with tree code Z_{F} , and c is such that 0\leq c\leq H^{s}_{n}(Z_{F}) , then there exists a nontrivial pruned closed set E\subseteq F whose associated tree code Z_{E} satisfies H^{s}_{n}(Z_{E})=c . Proposition 4.8 . (Reg-PS) If F\subseteq 2^{\omega} is a nontrivial pruned closed set with tree code Z_{F} , and c is such that 0\leq c\leq H^{s}_{n}(Z_{F}) , then there exists a nontrivial standard closed set E\subseteq F whose associated tree code Z_{E} satisfies H^{s}_{n}(Z_{E})=c . We first verify that \text{ACA}_{0} is sufficient to prove all of these results. Proposition 4.9 . Each of Reg-S, Reg-SP, Reg-P, and Reg-PS is provable in \text{ACA}_{0}. Proof. Note that it suffices to show that at least one of these regularity statements is provable in \text{ACA}_{0} . By Theorem 2.5 , standard and pruned closed sets are equivalent over \text{ACA}_{0} . Also, as \text{ACA}_{0} can prove any statement which holds in \text{WKL}_{0} , we can conclude from Corollary 2.8 that for any (standard or pruned) closed set F with associated code Z_{F} , we have H^{s}_{n}(Z_{F})=\mathcal{H}^{s}_{2^{-n}}(F) . The latter measure only depends on the elements in the closed set F , not on the specific tree we are using to code it. Taken together we can conclude that each of Reg-S, Reg-SP, Reg-P, and Reg-PS are pairwise equivalent under the axioms of \text{ACA}_{0} . We choose to show that \text{ACA}_{0} proves Reg-S. To that end, we use the fact that \text{ACA}_{0} is equivalent to the Dense Monotone Minimum principle (see Theorem 3.10 ). Let F and c be as in the statement of Reg-S. By Lemma 4.1 , the function H^{s}_{n} is dense above its infimum c over the nonempty closed set \mathcal{S}^{c}_{F} . Therefore, by DMMin there must be some Z\in\mathcal{S}^{c}_{F} for which H^{s}_{n}(Z)=c . The corresponding closed set E_{Z}\subseteq F\subseteq 2^{\omega} serves as our desired witness. ∎ Obtaining lower bounds for the complexity of these results is more difficult. In fact, Reg-PS could still potentially be provable in \text{RCA}_{0} , although the author suspects that this is unlikely. However, we do have some results regarding the other three; in particular, none of them hold computably. First, we will prove a lemma that we will need for the complexity lower bounds of Reg-S and Reg-P. Lemma 4.10 . The following is provable in \text{RCA}_{0} : Let E\subseteq 2^{\omega} be a nontrivial standard closed set, and let Z_{E} be a code for its tree. Suppose there exists a real number c>0 such that H^{1}_{0}(Z_{E})=c . Then there must exist an element X\in E . Proof. Let T_{E} denote the tree representing the closed set E . Given \tau\in 2^{<\omega} and m\geq|\tau| , we define the following notation: W_{m}[\tau]=2^{-m}\cdot|\{\sigma\in T_{E}:|\sigma|=m\wedge\sigma\supseteq\tau\}| W_{m}[\neg\tau]=2^{-m}\cdot|\{\sigma\in T_{E}:|\sigma|=m\wedge\sigma\nsupseteq\tau\}| Note that these quantities are both computable from T_{E} , and that they are monotonically decreasing in m . We will now inductively define an element X\in E . Since the procedure will be computable, the existence of X is provable in \text{RCA}_{0}. Assume for k\geq 0 that X\upharpoonright_{k}\in T_{E} has already been defined, and that W_{M}[\neg X\upharpoonright_{k}]0. Therefore, X\upharpoonright_{k+1} must have at least one length- m extension in T_{E} , which means X\upharpoonright_{k+1} itself is an element of T_{E} by initial segment closure. Also, since W_{m}[X\upharpoonright_{k}^{\frown}i]+W_{m}[\neg X\upharpoonright_{k}]=W_{m}[\neg X\upharpoonright_{k+1}], we have W_{m}[\neg X\upharpoonright_{k+1}]0 ; note that we will have c-W_{m}[\neg X\upharpoonright_{k}]\geq\epsilon for all m\geq M , since the quantity W_{m}[\neg\tau] is monotone decreasing in m . Since H^{1}_{0}(Z_{E})=c , we must have \tilde{H}^{1}_{0}(Z_{E}^{\leq m})0. (Technically, we should understand the above to mean that the terms in our sequence are uniformly bounded away from zero, since formally the limit may not exist without \text{ACA}_{0}. ) We wish to use Reg-S to show that this tree has an infinite path. First, observe that if Z\in 2^{\omega} is the code for T , then the above condition on T implies that H^{1}_{0}(Z)>0 , using the same considerations as discussed in the proof of the previous lemma. With that in mind, we can set F=[T] , we can choose c>0 such that H^{1}_{0}(Z)\geq c , and we can apply Reg-S to choose a nontrivial standard closed subset E\subseteq F whose associated tree code Z_{E} satisfies H^{1}_{0}(Z_{E})=c . From the previous lemma, we can deduce that there is an element X\in E\subseteq F=[T] , serving as our witness to \text{WWKL}_{0} . \square Proof of (iii): Finally, we wish to show that Reg-P implies \text{WWKL}_{0}. As in the proof of the previous item, we will let T\subseteq 2^{\omega} be an infinite tree satisfying the hypothesis of \text{WWKL}_{0} . We will define a new tree T^{\prime}\subseteq 2^{\omega} by setting \sigma\in T^{\prime} if and only if \sigma satisfies one of the following conditions: (1) \sigma\in T (2) There exists \tau\subseteq\sigma such that \tau\in T , neither of \tau^{\frown}0 or \tau^{\frown}1 are in T , and \sigma(i)=0 for all i\geq|\tau| . One can verify that T^{\prime} is a tree, and that T^{\prime} is pruned. Also, since T^{\prime} contains our original tree T , T^{\prime} must also satisfy the hypothesis of \text{WWKL}_{0}. In particular, if Z^{\prime} represents the code for T^{\prime} , then we may choose c>0 such that H^{1}_{0}(Z^{\prime})\geq c . By Reg-P, there exists a nontrivial pruned closed set E^{\prime}\subseteq[T^{\prime}] whose associated tree code Z_{E}^{\prime} satisfies H^{1}_{0}(Z_{E}^{\prime})=c . We will now define a tree code Z_{E}\in 2^{\omega} by setting Z_{E}(\sigma)=1 if and only if we have both Z_{E}^{\prime}(\sigma)=1 and \sigma\in T . (Here T represents our original tree). Note that Z_{E} does indeed represent a tree, since both T and Z_{E}^{\prime} represent trees. We claim that H^{1}_{0}(Z_{E})=c . First, since the tree coded by Z_{E} is a subset of that coded by Z_{E}^{\prime} , we certainly have H^{1}_{0}(Z_{E})\leq H^{1}_{0}(Z_{E}^{\prime})=c . Therefore, we just need to show that H^{1}_{0}(Z_{E})\geq c . Suppose for contradiction that H^{1}_{0}(Z_{E})0 so small that \tilde{H}^{1}_{0}(Z_{E}^{\leq m})0 . By Proposition 4.3 in \text{WKL}_{0} , we may choose a nontrivial pruned closed set F^{\prime}\subseteq F whose associated tree code Z_{F}^{\prime} satisfies c\leq H^{s}_{n}(Z_{F}^{\prime})0,\exists k\in\omega,\forall m\in\omega,\tilde{H}^{s}_{n}(Z_{E}^{\leq k})<\tilde{H}^{s}_{n}(Z_{F}^{\leq m})+\epsilon. It is straightforward to show that if both quantities H^{s}_{n}(Z_{E}) and H^{s}_{n}(Z_{F}) exist, then the above statement is equivalent to the interpretation of H^{s}_{n}(Z_{E})\leq H^{s}_{n}(Z_{F}) as a normal inequality of real numbers. Naturally, we will write H^{s}_{n}(Z_{E})=H^{s}_{n}(Z_{F}) to mean that we have both H^{s}_{n}(Z_{E})\leq H^{s}_{n}(Z_{F}) and H^{s}_{n}(Z_{F})\leq H^{s}_{n}(Z_{E}) . This allows us to finally obtain a regularity result equivalent to \text{ACA}_{0} : passing from a standard closed to a pruned closed subset of the same measure. Proposition 4.13 . Over \text{RCA}_{0} , the following is equivalent to \text{ACA}_{0} : if F\subseteq 2^{\omega} is a nontrivial standard closed set with associated tree code Z_{F} , then there exists a nonempty pruned closed set E\subseteq F whose associated tree code Z_{E} satisfies H^{s}_{n}(Z_{E})=H^{s}_{n}(Z_{F}) . Proof. The fact that \text{ACA}_{0} proves the stated result is straightforward, since standard and pruned closed sets are equivalent. Therefore, given a nontrivial standard closed set F\subseteq 2^{\omega} with tree code Z_{F} , we can simply take a code Z_{F}^{\prime} for a pruned tree representing the same set. Applying the equivalence of the H^{s}_{n} and \mathcal{H}^{s}_{2^{-n}} measures in \text{ACA}_{0} , we can conclude that H_{n}^{s}(Z_{F}^{\prime})=\mathcal{H}^{s}_{2^{-n}}(F)=H_{n}^{s}(Z_{F}). As is typical for \text{ACA}_{0} reversals, we will show that the given statement is sufficient to prove that every one-to-one function f:\omega\to\omega has a range. Using the given function f , we will define a code Z_{F} for the same tree T which was used in the proof of (iii) \implies\text{ACA}_{0} in Proposition 2.5 . As a reminder, this tree T consists of all \sigma\in 2^{<\omega} such that either (1) \sigma consists entirely of 0’s (2) \sigma\supseteq\tau_{n} for some n\in\omega , and f(k)\neq n for all k<|\sigma| , where \tau_{n} represents the length- (n+1) string consisting of n 0’s followed by a single 1. For the corresponding closed set F , we will apply the given statement to obtain a nontrivial pruned closed set E\subseteq F whose tree code Z_{E} satisfies H^{1}_{0}(Z_{E})=H^{1}_{0}(Z_{F}) . We claim that for this tree code Z_{E} and for all n\in\omega , we have Z_{E}(\tau_{n})=1 if and only if n\notin\text{ran}(f) . This gives us a means of computing the range of f from the element Z_{E} , and thus \text{ran}(f) must exist in our model by \Delta^{0}_{1} -comprehension in \text{RCA}_{0} . To see this correspondence, suppose first that n\in\omega is such that Z_{E}(\tau_{n})=1 . Since Z_{E} represents a pruned tree, there must be some infinite sequence X\supseteq\tau_{n} with X\in E\subseteq F . From this, we can deduce that n\notin\text{ran}(f) , since otherwise some sufficiently long initial segment of X would be excluded from the tree coded by Z_{F} . Suppose instead that n is such that Z_{E}(\tau_{n})=0 . Choose \epsilon>0 small enough that \epsilon<2^{-|\tau_{n}|}=2^{-n-1} . Since H^{1}_{0}(Z_{E})=H^{1}_{0}(Z_{F}) , there must be some k\in\omega such that for all m\in\omega , we have \tilde{H}^{1}_{0}(Z_{F}^{\leq k})<\tilde{H}^{1}_{0}(Z_{F}^{\leq m})+\epsilon. By monotonicity, we may assume that k\geq n+1 . Applying the above inequality to m=k , we can conclude 2^{-k}\cdot|\{\sigma\in 2^{<\omega}:Z_{F}(\sigma)=1\wedge|\sigma|=k\}|<2^{-k}\cdot|\{\sigma\in 2^{<\omega}:Z_{E}(\sigma)=1\wedge|\sigma|=k\}|+\epsilon, and subsequently |\{\sigma\in 2^{<\omega}:Z_{F}(\sigma)=1\wedge|\sigma|=k\}|<|\{\sigma\in 2^{<\omega}:Z_{E}(\sigma)=1\wedge|\sigma|=k\}|+\epsilon\cdot 2^{k}. Note that any string \sigma for which Z_{E}(\sigma)=1 must also satisfy Z_{F}(\sigma)=1 . Again, this follows from the fact that Z_{E} represents a pruned tree, so any \sigma in this tree has some infinite extension X\in E\subseteq F , whose initial segments are all in the tree coded by Z_{F} . Thus, we can deduce from the above inequality that the number of length- k strings \sigma for which Z_{F}(\sigma)=1 but Z_{E}(\sigma)=0 is less than \epsilon\cdot 2^{k}<2^{k-n-1} by choice of \epsilon . But now observe that since Z_{E}(\tau_{n})=0 , none of the 2^{k-n-1} -many length- k extensions of \tau_{n} can be in the tree coded by Z_{E} . If all of these strings were in the tree coded by Z_{F} , we would contradict the bound outlined above. Therefore, at least one of these strings \sigma must be excluded from Z_{F} , which by its definition means that there is some i<|\sigma|=k for which f(i)=n . Thus, n\in\text{ran}(f) , as desired. ∎ Compare the result from this proposition to that of Corollary 4.4 , where the measure of the original closed set F is assumed to already exist. As an aside, this pair of results is somewhat analogous to some prior results concerning maxima/minima for continuous functions on compact sets. If the supremum of the function’s values on the set exists, as a real number, then the existence of a point in the set realizing that supremum is equivalent to \text{WKL}_{0} ; otherwise, the existence is equivalent to \text{ACA}_{0} . See 12 for more details. 4.2. The Besicovitch Theorem In this final section, we will use the techniques and results developed thus far to analyze the strength of the following regularity result for the s -dimensional Hausdorff measure, first proven by Abram Besicovitch in 1952. For a reproduction of Besicovitch’s proof (albeit for Euclidean space), see 5 . While the particular formulation of the proof given in this section is original, we give due credit to Besicovitch for the overall structure and key measure theoretic insights. Theorem 4.14 . Let s\geq 0 , and let F\subseteq 2^{\omega} be a closed set with \mathcal{H}^{s}(F)=\infty . Then for any real number c>0 , there exists a closed subset E\subseteq F with \mathcal{H}^{s}(E)=c . Our main goal is to verify that this theorem is provable in \text{ACA}_{0} . As discussed in the introduction, this fact is not obvious from Besicovitch’s original argument. Fortunately, with the axioms of \text{ACA}_{0} , the various ways of coding closed sets are all equivalent, as are the different ways of representing the s -dimensional Hausdorff 2^{-n} -measure. Thus, the provability of Besicovitch’s theorem in \text{ACA}_{0} does not depend on the precise way in which the theorem is formalized. We choose to prove the formulation below; this version is slightly stronger than the original statement, in that it does not require the original set’s Hausdorff measure to be infinite, nor the witnessing subset’s measure to be positive. Theorem 4.15 . (Besicovitch) Let F\subseteq 2^{\omega} be a nontrivial standard closed set with tree code Z_{F} , and suppose that c,s\geq 0 are real numbers such that c\leq\lim_{n\to\infty}H^{s}_{2^{-n}}(Z_{F}). Then there exists a nontrivial standard closed set E\subseteq F whose associated tree code Z_{E} satisfies \lim_{n\to\infty}H^{s}_{n}(Z_{E})=c. We will derive this result as a consequence of BCTC, which is equivalent to (and therefore provable in) \text{ACA}_{0} by Theorem 3.6 . First, we introduce some notation. We assume throughout the remainder of this section that our parameter s\geq 0 and our given closed set F\subseteq 2^{\omega} are fixed, as are the corresponding tree T_{F}\subseteq 2^{\omega} and tree code Z_{F}\in 2^{\omega} . Definition 4.2 . Let c\geq 0 be a real number, and let n\in\omega . Define the tree T^{c}_{n} by T^{c}_{n}=\{\nu\in S_{T_{F}}:\tilde{H}^{s}_{n}(\nu)\geq c\}, and let \mathcal{S}^{c}_{n}=[T^{c}_{n}] denote the corresponding closed set. In other words, \mathcal{S}^{c}_{n} consists of all Z\in[S_{T_{F}}] for which H^{s}_{n}(Z)\geq c . We will let \mathcal{U}^{c}_{n} denote the open complement 2^{\omega}\setminus\mathcal{S}^{n}_{c} . Note that the definition of \mathcal{S}^{c}_{n} is essentially the same as that in Definition 4.1 . However, in that section we assumed that the index n was fixed, so we did not need to keep track of it. Here, we will be working with changing values of n so we include that parameter as part of the notation. Our BCTC argument hinges on the following result, which we will call Besicovitch-Density or BD . Proposition 4.16 . (BD) Let n_{0}\in\omega be such that \mathcal{S}^{c}_{n_{0}} is nonempty. If d>c , then for all n\in\omega , the open set \mathcal{U}^{d}_{n} is dense in the closed set \mathcal{S}^{c}_{n_{0}} . If this proposition holds in \text{ACA}_{0} , then if we choose a sufficiently large n_{0}\in\omega , and a decreasing sequence (d_{n})_{n\in\omega} of real numbers converging downward to c , then BCTC will allow us to obtain an element Z\in\mathcal{S}^{c}_{n_{0}}\cap\bigcap_{n\in\omega}\mathcal{U}^{d_{n}}_{n} . This element Z will code a closed subset E_{Z}\subseteq F satisfying \mathcal{H}^{s}(E_{Z})=c . (We will provide the details at the end of this section). The proof of the Besicovitch Density result is quite technical and requires multiple lemmas. First, we verify that the proposition holds in the case where the indices n agree. Lemma 4.17 . The following is provable in \text{RCA}_{0} : Let n\in\omega be fixed, and assume c\geq 0 is such that \mathcal{S}^{c}_{n} is nonempty. If d>c , then the open set \mathcal{U}^{d}_{n} is dense in the closed set \mathcal{S}^{c}_{n} . Proof. This result is essentially just a reformulation of Lemma 4.1 . Indeed, suppose \tau\in 2^{<\omega} is such that N_{\tau}\cap\mathcal{S}^{c}_{n}\neq\emptyset . We wish to show that there exists some Y\in\mathcal{S}^{c}_{n}\cap\mathcal{U}^{d}_{n} with Y\supseteq\tau. By Lemma 4.1 , (after accounting for the change in notation), we know that the function H^{s}_{n} is dense above c over \mathcal{S}^{c}_{n} . Therefore, if we choose any Z\in\mathcal{S}^{c}_{n} , we know Z is a limit point with respect to c and H^{s}_{n} . If we take \epsilon=d-c>0 , then there is some Y\in\mathcal{S}^{c}_{n} with Y\supseteq\tau and H^{s}_{n}(Y)0 , we have \mathcal{U}_{n}^{d}\cap\mathcal{T}_{n}\subseteq\mathcal{U}^{d}_{n+1}. Proof. Let Z\in\mathcal{U}_{n}^{d}\cap\mathcal{T}_{n} . As Z\in\mathcal{T}_{n}\subseteq[S_{T_{F}}] , we know that Z does represent a valid tree code, so the fact that Z\in\mathcal{U}_{n}^{d} implies that H^{s}_{n}(Z)0 small enough that we also have W_{s}(U)n , so the value of Y(\tau) will be determined uniquely by Y_{\tau\upharpoonright_{n}}(\tau) . It is straightforward to show that Y will be an element of [S_{T_{F}}] as long as each Y_{\sigma} is. Additionally, as long as \text{ACA}_{0} can prove the existence of each Y_{\sigma} , we can also deduce the existence of the overall element Y , which is computable from the (finite) collection of all Y_{\sigma} . We will define the elements Y_{\sigma} according to two cases. Suppose first that \sigma is such that Z is n -thin for \sigma , i.e. H^{s}_{n+1}(Z_{\sigma})\leq 2^{-ns} . Define Y_{\sigma}=Z_{\sigma} for all such \sigma . Note that \nu_{\sigma}\subseteq Z_{\sigma} so our desired condition is satisfied. For all other \sigma\in 2^{<\omega} of length n , it must be the case that H^{s}_{n+1}(Z_{\sigma})>2^{-ns} , which implies that Z_{\sigma} is an element of \mathcal{S}_{n+1}^{2^{-ns}}. By Lemma 4.1 , we know that the function H^{s}_{n+1} is dense above 2^{-ns} over \mathcal{S}_{n+1}^{2^{-ns}} . As \mathcal{S}_{n+1}^{2^{-ns}}\cap N_{\nu_{\sigma}} is nonempty (it at least contains Z_{\sigma} ), we can actually conclude that H^{s}_{n+1} is dense above 2^{-ns} over the closed set \mathcal{S}_{n+1}^{2^{-ns}}\cap N_{\nu_{\sigma}} as well. (The proof is just a matter of working through the definitions). Since we have access to \text{ACA}_{0} , we may apply the Dense Monotone Minimum principle (see Theorem 3.10 ) to find an element Y_{\sigma}\in\mathcal{S}_{n+1}^{2^{-ns}}\cap N_{\nu_{\sigma}} which satisfies H^{s}_{n+1}(Y_{\sigma})=2^{-ns} . It remains to observe that by its construction, the sequence Y extends the string \nu and is n -thin. Step 2: Show that Y is an element of \mathcal{S}_{n_{0}}^{c} . By the monotonicity of the function \tilde{H}^{s}_{n_{0}} , it suffices to show that \tilde{H}^{s}_{n_{0}}(Y^{\leq m})\geq c for all m\geq n\geq n_{0} . Let such an m be arbitrary, and suppose U is a cover for computing \tilde{H}^{s}_{n_{0}}(Y^{\leq m}) . We wish to show that W_{s}(U)\geq c . Note that if we delete a string which properly extends another element of U , we have a still-valid cover of smaller weight, so we may assume that U is prefix-free. We wish to replace U with a cover U^{\prime} which is valid for computing \tilde{H}^{s}_{n_{0}}(Z^{\leq m}) and for which W_{s}(U^{\prime})\leq W_{s}(U). Since Z was an element of \mathcal{S}_{n_{0}}^{c} , this would yield W_{s}(U)\geq W_{s}(U^{\prime})\geq c . This would imply that Y\in\mathcal{S}_{n_{0}}^{c} since the cover U was arbitrary. Suppose we have a string \sigma\in 2^{<\omega} of length n for which H^{s}_{n+1}(Z_{\sigma})>2^{-ns} . If \sigma has no proper extensions in U , then we do nothing. Otherwise, delete all of these extensions and replace them with \sigma . We claim that this action will not increase the s -weight of the cover. Indeed, let V_{\sigma} denote the (nonempty) set of proper extensions of \sigma in U . Note that all strings in V_{\sigma} have length between n+1 and m , inclusive. Also, if \tau is such that |\tau|=m and Y_{\sigma}(\tau)=1 , then \tau must extend some element of V_{\sigma} . Given that the original set U was a cover for Y , we know that \tau extends some element \mu\in U , which must be compatible with \sigma . If \mu\subseteq\sigma , then \mu would be a proper prefix of any element in V_{\sigma} , contradicting the fact that V_{\sigma} was nonempty and U was prefix-free. Therefore, we must have \mu\supsetneq\sigma , and thus \mu\in V_{\sigma}. Taken together, we see that V_{\sigma} is a valid cover for computing \tilde{H}^{s}_{n+1}(Y_{\sigma}^{\leq m}) . Since \sigma was such that H^{s}_{n+1}(Z_{\sigma})>2^{-ns} , the construction of Y yields that H^{s}_{n+1}(Y_{\sigma})=2^{-ns} , and thus W_{s}(V_{\sigma})\geq 2^{-ns} . Therefore, replacing the strings in V_{\sigma} with a string \sigma having length n cannot increase the s -weight of U. Let U^{\prime} be the cover obtained from applying this replacement process to all length- n strings \sigma for which \tilde{H}^{s}_{n+1}(Z_{\sigma})>2^{-ns} . It remains to verify that U^{\prime} is a valid cover for computing \tilde{H}^{s}_{n_{0}}(Z^{\leq m}) . For the length condition, note that we only added strings of length n , and we assumed that n_{0}\leq n\leq m . Thus our string lengths remain within the proper bounds. For the second condition, suppose we have a string \tau with |\tau|=m and Z(\tau)=1 . Let \sigma be the unique length- n prefix of \tau . If \sigma satisfies H^{s}_{n+1}(Z_{\sigma})\leq 2^{-ns} , then from our construction we know that Y_{\sigma}=Z_{\sigma} , and thus Y_{\sigma}(\tau)=Z_{\sigma}(\tau)=1 . As the original cover U was valid for computing \tilde{H}^{s}_{n_{0}}(Y^{\leq m}) , this implies that U contains some prefix of \tau , which will be compatible with \sigma . As \sigma was not one of the strings considered in our replacement process, this compatible prefix \tau will still be in U^{\prime} . Suppose instead that \sigma satisfies H^{s}_{n+1}(Z_{\sigma})>2^{-ns} . Once again, we know that the original cover U was valid for computing H^{s}_{n_{0}}(Y^{\leq m}) , and thus for computing H^{s}_{n_{0}}(Y_{\sigma}^{\leq m}) as well. Given that \tilde{H}^{s}_{n+1}(Y_{\sigma}^{\leq m})\geq 2^{-ns} (from the construction of Y ) there must be at least one \tau^{\prime} of length m for which Y_{\sigma}(\tau^{\prime})=1 , so this \tau^{\prime} has a prefix \mu\in U , compatible with \sigma . If \mu\subseteq\sigma , then \mu is also a prefix of \tau and was not removed in passing to U^{\prime} . If instead \mu\supseteq\sigma , then \mu was removed and replaced with \sigma . Either way, we determine that U^{\prime} contains a prefix of \tau , which completes the argument that U^{\prime} is a valid cover for computing \tilde{H}^{s}_{n_{0}}(Z^{\leq m}) , as desired. ∎ We are now ready to complete the proof of our desired density result. Proposition 4.20 . Proposition 4.16 (BD) is provable in \text{ACA}_{0}. Proof. By Lemma 4.17 and the remark that followed, we have that \mathcal{U}_{n}^{d} is dense in \mathcal{S}^{c}_{n_{0}} for all n\leq n_{0} , and that this result is provable in \text{RCA}_{0} . Assume inductively that \mathcal{U}_{n}^{d} is dense in \mathcal{S}^{c}_{n_{0}} for some n\geq n_{0}. Let \tau\in 2^{<\omega} be such that N_{\tau}\cap\mathcal{S}_{n_{0}}^{c}\neq\emptyset ; we wish to exhibit an element Y\in N_{\tau}\cap\mathcal{S}^{c}_{n_{0}}\cap\mathcal{U}^{d}_{n+1} . First, we may apply the inductive hypothesis to choose Z\in N_{\tau}\cap\mathcal{S}_{n_{0}}^{c}\cap\mathcal{U}_{n}^{d} . Since \mathcal{U}_{n}^{d} is open, we may choose \tau^{\prime}\in 2^{<\omega} such that \tau\subseteq\tau^{\prime}\subseteq Z and N_{\tau^{\prime}}\subseteq\mathcal{U}_{n}^{d} . Then since N_{\tau^{\prime}}\cap\mathcal{S}_{n_{0}}^{d} is nonempty (it at least contains Z ), by Lemma 4.19 (provable in \text{ACA}_{0} ) we can find Y\in N_{\tau^{\prime}}\cap\mathcal{S}_{n_{0}}^{d} with Y\in\mathcal{T}_{n} . By choice of \tau^{\prime} , we have Y\in\mathcal{T}_{n}\cap\mathcal{U}_{n}^{d} , so by Lemma 4.18 (provable in \text{RCA}_{0} ) we have Y\in\mathcal{U}^{d}_{n+1} . This proves the density of \mathcal{U}^{d}_{n+1} in S_{n_{0}}^{d} , completing the inductive step. We can then use induction on arithmetic formulas in \text{ACA}_{0} to conclude that \mathcal{U}_{n}^{d} is dense in \mathcal{S}^{c}_{n_{0}} for all n\in\omega , as desired. ∎ While we have already outlined the argument, we will now formally demonstrate the proof of Besicovitch’s theorem (according to the formulation in Theorem 4.15 ) in \text{ACA}_{0} . Theorem 4.21 . Theorem 4.15 (Besicovitch) is provable in \text{ACA}_{0} . Proof. First, if \mathcal{H}^{s}(F)=\lim_{n\to\infty}H^{s}_{n}(Z_{F})=c , then the result is trivial, since we can just take our witnessing subset E to be F itself (with appropriate codes). So assume that \mathcal{H}^{s}(F) (which may be infinite) is strictly greater than the target measure c . In that case, there must be some n_{0}\in\omega for which H^{s}_{n_{0}}(Z_{F})\geq c . In that case, the closed set \mathcal{S}^{c}_{n_{0}} will be nonempty, since it will at least contain the element Z_{F} . Now, let (d_{n})_{n\in\omega} be a strictly decreasing sequence of real numbers which converges to c . (For example, we may take d_{n}=c+2^{-n} .) As each d_{n} is strictly greater than c , it follows from Proposition 4.20 that each open set \mathcal{U}^{d_{n}}_{n} is dense in \mathcal{S}^{c}_{n_{0}} , and that this fact is provable in \text{ACA}_{0} . We can then apply BCTC (also provable in \text{ACA}_{0} ) to obtain an element Z\in\mathcal{S}^{c}_{n_{0}}\cap\bigcap_{n\in\omega}\mathcal{U}^{d_{n}}_{n} . We claim that for the associated closed set E_{Z}\subseteq F , we have \mathcal{H}^{s}(E_{Z})=\lim_{n\to\infty}H^{s}_{n}(Z)=c, implying that E_{Z} is our desired witnessing subset. First, since Z\in\mathcal{S}^{c}_{n_{0}} , we know that H^{s}_{n_{0}}(Z)\geq c , and thus \mathcal{H}^{s}(E_{Z})\geq c since the quantity H^{s}_{n}(Z) is monotonically increasing in n . To prove the opposite inequality, let \epsilon>0 be arbitrary, and choose N\in\omega so large that d_{n}0 was arbitrary, we must in fact have \mathcal{H}^{s}(E_{Z})\leq c , and therefore \mathcal{H}^{s}(E_{Z})=c when combined with our earlier inequality. This completes the proof. ∎ Having shown that \text{ACA}_{0} implies Besicovitch’s theorem, it is natural to wonder whether the converse is true. After all, the BCTC result was integral to this particular proof, and BCTC itself is equivalent to \text{ACA}_{0} as shown in Section 3.1. While we have not yet determined whether this is the case, the results in the previous section at least demonstrate that Besicovitch - as formalized in Proposition 4.15 - does not hold in \text{RCA}_{0} . We can obtain similar lower bounds by changing the representations of the closed sets involved. Proposition 4.22 . Over \text{RCA}_{0} , Theorem 4.15 (Besicovitch) implies \text{WWKL}_{0} , as does the analog of Theorem 4.15 where the sets F and E are pruned closed. If F is standard closed but E is required to be pruned closed, then the theorem implies \text{WKL}_{0} . Proof. Assume that Theorem 4.15 holds (or one of its variants), and suppose we apply it in the case where s=1 . In this case, H^{1}_{n} will compute the same function for every n\in\omega , so for any closed set F with tree code Z_{F} , we will just have \mathcal{H}^{1}(F)=H^{1}_{0}(Z_{F}) . We can then apply the same reversal proofs as were used for Reg-S, Reg-P, and Reg-SP in Proposition 4.11 . ∎ We conclude this section with an examination of Besicovitch’s theorem from the perspective of computability theory. One well-known property of \text{ACA}_{0} is that its \omega -models are precisely those which are closed under Turing reducibility (downwards), the Turing join, and the Turing jump. Given any real A\in 2^{\omega} , we can construct an \omega -model of \text{ACA}_{0} containing A by defining its second order part to be the collection \{X\in 2^{\omega}:X\leq_{T}A^{(n)}\text{ for some }n\in\omega\}. Here, A^{(n)} represents the n -th iterate of the Turing jump of A . Suppose Z_{F}\in 2^{\omega} is any tree code representing a nontrivial standard closed set, and suppose that our real number parameter s and our target measure c are both computable. Consider the model of \text{ACA}_{0} above with A=Z_{F} , whose second-order part would contain (codes for) each of Z_{F},c, and s . As Besicovitch’s theorem holds in this model, we can conclude that there exists a witnessing subset E\subseteq F whose tree code Z_{E} is computable from Z_{F}^{(n)} for some n\in\omega . If we could place some lower bound on the value of this n , then we could gain some understanding about the computability-theoretic complexity of Besicovitch’s theorem. Since Besicovitch’s theorem is not provable in \text{RCA}_{0} , we know there are at least some tree codes Z_{F} for which the witnessing subset code Z_{E} is not computable from Z_{F} itself; this would mean that the necessary jump iterate n is at least 1. However, by examining the computability theoretic techniques used in previous arguments, we can deduce that a single jump is always sufficient, as formalized below. Theorem 4.23 . Let Z_{F}\in 2^{\omega} be a tree code representing a nontrivial standard closed set F , and suppose that c,s\geq 0 are computable real numbers such that c\leq\lim_{n\to\infty}H^{s}_{2^{-n}}(Z_{F}). Then there exists a tree code Z_{E}\in 2^{\omega} for a nontrivial standard closed subset E\subseteq F such that Z_{E}\leq_{T}Z_{F}^{\prime} and \lim_{n\to\infty}H^{s}_{n}(Z_{E})=c. Proof. Let the closed set \mathcal{S}^{c}_{n_{0}} be defined as in the proof of Theorem 4.21 . Observe that the corresponding tree T^{c}_{n_{0}}=\{\nu\in S_{T_{F}}:\tilde{H}^{s}_{n_{0}}(\nu)\geq c\} is computable from Z_{F} (i.e. T_{F} ). Therefore, the first jump Z_{F}^{\prime} is sufficient to compute the pruned subtree \tilde{T}^{c}_{n_{0}}=\{\sigma\in T^{c}_{n_{0}}:\forall m\geq|\sigma|,\exists\tau\supseteq\sigma\text{ with }|\tau|=m\text{ and }\tau\in T^{c}_{n_{0}}\}, since \tilde{T}^{c}_{n_{0}} is \Pi^{0}_{1} -definable from Z_{F} . Note that \tilde{T}^{c}_{n_{0}} still represents the same closed set \mathcal{S}^{c}_{n_{0}} , which we can now think of as pruned closed with this new tree code. Now, consider the sequence of open sets \{\mathcal{U}_{n}^{d_{n}}\}_{n\in\omega} from the proof of Theorem 4.21 . Each set \mathcal{U}_{n}^{d_{n}} has an open set code V_{n} defined by 2^{\omega}\setminus T^{d_{n}}_{n} , so these are all (uniformly) computable from Z_{F} . We know from Proposition 4.20 that each open set \mathcal{U}_{n}^{d_{n}} is dense in \mathcal{S}^{c}_{n_{0}} . By following the proof of BCTCIII as given in Proposition 3.5 , we can, in a computable way, construct an element Z\in\mathcal{S}^{c}_{n_{0}}\cap\bigcap_{n\in\omega}\mathcal{U}_{n}^{d_{n}} using the pruned tree \tilde{T}^{c}_{n} and the open codes \{V_{n}\}_{n\in\omega} . This element Z is thus computable from Z_{F}^{\prime} , and by the argument given in the proof of Theorem 4.21 , the corresponding closed set will satisfy \lim_{n\to\infty}H^{s}_{n}(Z_{E})=c, as desired. ∎ As discussed in the introduction, the witnessing subset constructed in the original proof would require infinitely many iterates of the original set’s jump, were it to be constructed precisely as Besicovitch described. Thus, the existence of a subset that is relatively simple from a computability perspective provides a rather surprising conclusion to this project.