Effective Versions of Strong Measure Zero

Rayman, Matthew

doi:10.4230/LIPIcs.STACS.2026.75

Effective Versions of Strong Measure Zero

Matthew Rayman

Department of Computer Science, Iowa State University, Ames, IA, USA

Abstract

Effective versions of strong measure zero sets are developed for various levels of complexity and computability. It is shown that the sets can be equivalently defined using a generalization of supermartingales called odds supermartingales, success rates on supermartingales, predictors, and coverings. We show Borel’s conjecture that a set has strong measure zero if and only if it is countable holds in the time and space bounded setting. At the level of computability this does not hold. We show the computable level contains sequences at arbitrary levels of the hyperarithmetical hierarchy. This is done by proving a correspondence principle yielding a condition for the sets of computable strong measure zero to agree with the classical sets of strong measure zero.

An algorithmic version of strong measure zero using lower semicomputability is defined. We show that this notion is equivalent to the set of NCR reals studied by Reimann and Slaman, thereby giving new characterizations of this set.

Effective strong packing dimension zero is investigated by requiring success with respect to the limit inferior instead of the limit superior. It is proven that every sequence in the corresponding algorithmic class is decidable. At the level of computability, the sets coincide with a notion of weak countability that we define.

Keywords and phrases:

Strong measure zero, NCR, Effective fractal dimensions, Borel’s Conjecture, Hausdorff dimension, Packing dimension

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

Related Version:

Full Version: https://arxiv.org/abs/2506.02031 [26]

Acknowledgements:

The author thanks Jack Lutz for many helpful conversations.

Funding:

This research was supported in part by National Science Foundation research grant 1900716.

DOI:

10.4230/LIPIcs.STACS.2026.75

Event:

43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Editors:

Meena Mahajan, Florin Manea, Annabelle McIver, and Nguyễn Kim Thắng

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Measure theory is a well studied area of mathematics resulting in a notion of smallness for sets of measure zero. This was effectivized all the way down to versions of time and space bounded measure zero sets by Lutz [18]. Hausdorff [8] refined measure zero sets in the classical (non effective) setting with dimension. This yields the dimension zero sets which are a subclass of the measure zero sets. Effective versions of dimension defined by Lutz [20] along with effective measure have led to many connections and results in areas of theoretical computer science including algorithmic randomness, complexity theory and the structure of complexity classes, natural proofs, pseudorandom generators and others. For more of an overview see [19, 22]. In this paper, we continue the above refinement by developing effective versions of a subclass of dimension zero sets called strong measure zero. Compared to the non random sets corresponding to measure zero where arbitrarily large portions of the sequences may appear completely random, we will see that on the other end of this hierarchy the effective strong measure zero sets are those that an algorithm can almost completely, if not completely, describe.

Borel [4] defined a set $X\subseteq\mathbb{R}$ to be strong measure zero (SMZ) if for every sequence $(\epsilon_{n})_{n\in\mathbb{N}}$ of positive reals there is a set $(I_{n})_{n\in\mathbb{N}}$ of intervals such that

X\subseteq\bigcup_{n\in\mathbb{N}}I_{n}\text{ and }|I_{n}|\leq\epsilon_{n}% \text{ for all }n\in\mathbb{N}

(1)

where $|I_{n}|$ is the length of $I_{n}$ . It is easy to see that every countable set has strong measure zero. Borel conjectured that a set is strong measure zero if and only if it is countable. The work of Sierpiński [32] and Laver [14] proved that this is independent of ZFC. Strong measure zero is easily defined for subsets of Cantor space which we focus on in this paper. For a thorough background on strong measure zero sets see [2].

An effective version of strong measure zero was studied by Higuchi and Kihara [9] where they only require (1) to hold for computable sequences of $(\epsilon_{n})$ yielding a weaker notion of strong measure zero sets. In doing so, they developed a characterization of strong measure zero sets using a generalized version of martingales called odds supermartingales.

In this work we investigate requiring the supermartingales themselves to be effective, leading instead to a stronger notion than strong measure zero sets in the classical setting. These supermartingale objects are similar to those used to define effective measure and dimension, but we will show in section 3 and that there are equivalent characterizations using the success rates of standard supermartingales.

Besicovitch [3] showed that a set being strong measure zero is equivalent to the set having Hausdorff measure zero with respect to all gauge functions. Hitchcock [10] has shown that Hausdorff dimension can be defined using predictors. We extend this to work for arbitrary gauge functions resulting in a new characterization of the strong measure zero sets and a useful tool to study them in the effective setting.

A natural effective version of Borel’s conjecture with time and space bounded resources along with at the computable level exists. This uses an effective countability definition by Lutz [18] which are roughly sets of sequences than can be uniformly enumerated within the resource bound. We prove that the effectively countable sets have effective strong measure zero at every level. For the time and space bounded setting it is proven that Borel’s conjecture holds. However, it does not hold at the computable level.

We investigate algorithmic strong measure zero occurring at the lower semicomputable level. The main result is that the resulting class is equivalent to the well studied set of NCR reals defined by Reimann and Slaman [28] containing sequences that are not algorithmically random with respect to any continuous probability measure. We will discuss this connection more in section 5, but note for now that in the classical setting these are not equivalent. NCR has been proven to be countable [29]. We thus have the following implication diagram where $\mathrm{\Delta}_{R}$ represents a time or space bounded resource class and the dashed arrow implies independence from ZFC.

Theorem 1.

We show that effective strong measure zero sets can be defined using effective coverings resulting in a characterization similar to Borel’s original definition (1). This results in another relatively simple characterization of NCR. While there are analagous classical results as well as in Higuchi and Kihara’s version, our setting requires use of different techniques. Using this result, we prove a correspondence principle giving sufficient conditions for computable, algorithmic, and classical versions of strong measure zero to agree on a set. This result is analogous to Hitchcock’s [12] correspondence principle for effective dimension. We use our result to show that there are sequences at arbitrarily high levels of the hyperarithmetic hierarchy with computable strong measure zero, mirroring a result for NCR.

Many of the characterizations of strong measure zero sets involve success with respect to a limit superior. We therefore investigate what happens if success is required in the limit inferior. For dimension, Lutz [20] showed a limit superior condition on martingales characterizes Hausdorff dimension while Althreya, Hitchcock, Lutz and Mayordomo [1] showed packing dimension can be characterized with a limit inferior. Requiring limit inferior success at all gauges leads to sets with strong packing dimension zero (SPDZ). In the classical setting, the existence of uncountable strong packing dimension zero sets is also independent of ZFC, see for example [34]. For time and space restrictions the sets are the same as strong measure zero. However at the computable level, the sets now correspond with a weak computably-countable notion that we define. It is also shown that the algorithmic version contains exactly the decidable sequences, giving the following implication chart.

Theorem 2.

Proofs of results omitted for space in this paper are marked with $(\bigstar)$ and can be found in the full version of the paper [26].

2 Preliminaries

We work in the Cantor space $\mathbf{C}=\{0,1\}^{\infty}$ consisting of all infinite binary sequences. A string is a finite, binary string $w\in\{0,1\}^{*}$ which has length $|w|$ . We write $\lambda$ for the empty string of length 0. For $0\leq i\leq j\leq|w|-1$ we write $w[i\dots j]$ for the string consisting of the $i^{\text{th}}$ through $j^{\text{th}}$ bits of $w$ . Similarly for $i,j\in\mathbb{N}$ with $i\leq j$ , we let $S[i\dots j]$ be the string consisting of the $i^{\text{th}}$ through $j^{\text{th}}$ bits of $S$ .

For a string $x$ and a string or sequence $y$ we let $x y$ be the concatenation of $x$ and $y$ . We say that $x\sqsubseteq y$ if there is a string or sequence $z$ such that $y=xz$ . We say $x\sqsubset y$ if $x\sqsubseteq y$ and $x\not=y$ . The cylinder at $x$ is $C_{x}=\{S\in\mathbf{C}|x\sqsubseteq S\}$

We associate a language $A\subseteq\{0,1\}^{*}$ with its characteristic sequence ${\chi_{A}\in\mathbf{C}}$ defined by

\chi_{A}(i)=\begin{cases}1,&\text{if }s_{i}\in A\\ 0,&\text{otherwise}\end{cases}

where $s_{0},s_{1},\dots$ is the enumeration of all strings in $\{0,1\}^{*}$ in standard lexicographic order.

Definition 3.

A time bounded resource class is a set ${T\subseteq\{f:\{0,1\}^{*}\to\{0,1\}^{*}\}}$ for which there is a sequence $(g_{n})_{n\in\mathbb{N}}$ of functions $g_{n}:\mathbb{N}\to\mathbb{N}$ satisfying

1.

$g_{n}=o(g_{n+1})$ for all $n\in\mathbb{N}.$
2.

There is some computable $h:\mathbb{N}\to\mathbb{N}$ such that $g_{n}=o(h)$ for all $n\in\mathbb{N}$ .
3.

$T=\bigcup_{n\in\mathbb{N}}\{f:\{0,1\}^{*}\to\{0,1\}^{*}\mid f\in\mathrm{DTIME}% (g_{n})\}$ .

Space bounded resource classes are defined analogously with $\mathrm{DSPACE}$ . In this paper we will let $\mathrm{\Gamma}_{R}$ be the set consisting of all time or space bounded resource classes that contain either $\mathrm{P}$ or $\mathrm{PSPACE}$ .

We also will look at the classes

	$\displaystyle\mathrm{all}$	$\displaystyle=\{f:\{0,1\}^{}\to\{0,1\}^{}\}$
	$\displaystyle\mathrm{comp}$	$\displaystyle=\{f\in\mathrm{all}\mid f\text{ is computable}\}$

and use $\mathrm{\Gamma}_{RCA}$ to be the set $\mathrm{\Gamma}_{R}$ along with the classes comp and all. Note that the class all corresponds to classical results.

Definition 4 (Lutz [17]).

A constructor is a function $\delta:\{0,1\}^{*}\to\{0,1\}^{*}$ such that $x\sqsubset\delta(x)$ holds for all $x\in\{0,1\}^{*}$ . The result of a constructor $\delta$ is the sequence ${R(\delta)\in\mathbf{C}}$ such that $\delta^{i}(\lambda)\sqsubseteq R(\delta)$ for all $i\in\mathbb{N}$ . For $\mathrm{\Delta}\in\mathrm{\Gamma}_{RCA}$ , let $R(\mathrm{\Delta})=\{R(\delta)\mid\delta\in\mathrm{\Delta}\text{ is a % constructor\}}$ .

For a discrete domain $D$ such as $\{0,1\}^{*}$ we say a function ${f:D\to[0,\infty)}$ is lower semicomputable if there is a computable function $g:\mathbb{N}\times D\to\mathbb{Q}\cap[0,\infty)$ , called a computation of $f$ , such that for all $r\in\mathbb{N},x\in D$ ,

g(r,x)\leq g(r+1,x)\leq f(x)\quad\text{and}\quad\lim_{r\to\infty}g(r,x)=f(x).

Similarly, for $\mathrm{\Delta}\in\mathrm{\Gamma}_{RCA}$ and a discrete domain $D$ we say that $f:D\to[0,\infty)$ is $\mathrm{\Delta}$ -computable if there is an function $g:\mathbb{N}\times D\to\mathbb{Q}\cap[0,\infty)\in\mathrm{\Delta}$ called a computation of $f$ such that ${|g(r,x)-f(x)|\leq 2^{-r}}$ for all $r\in\mathbb{N}$ . In this paper $\mathrm{\Gamma}$ denotes $\mathrm{\Gamma}_{RCA}$ together with the lower semicomputable class. We will also refer to the lower semicomputable level as algorithmic.

We also need a basic understanding of functionals and their complexity. Functionals generalize functions and can have have inputs and outputs that are functions themselves. Functionals in this paper will mostly have the form of

F:(A\to B)\to(D\to\mathbb{R})

where $A, B$ and $D$ are all discrete domains. Therefore on an input function $f:(A\to B)$ the functional outputs a function $F(f)=g$ for some $g:D\to\mathbb{R}$ . To talk about the complexity and computability we look at the functional

F^{\prime}:(A\to B)\to(\mathbb{N}\times D\to\mathbb{Q})

where $F^{\prime}(f)=g$ is a computation of $F(f)$ . For $\mathrm{\Delta}\in\mathrm{\Gamma}$ equal to comp or lower semicomputable, we say that the functional $F$ is in $\mathrm{\Delta}$ if there is an oracle Turing machine $M$ such that for all $f:A\to B,r\in\mathbb{N}$ and $x\in D$ , $M$ on input $(r,x)$ with oracle access to $f$ outputs $g(r,x)$ where $g\in\mathrm{\Delta}$ is a computation of $F(f)$ as defined above.

For time bounded $\mathrm{\Delta}$ we require that the time $M$ takes to output $g(x,r)$ is $h(|x|+r+\bar{g}(h(|x|+r))$ for some $h$ in $\mathrm{\Delta}$ where $\bar{g}(n)$ is the maximum length of the oracle $g$ ’s output on a string of length at most $n$ . For example if $\mathrm{\Delta}$ is polynomial time then $M$ can query polynomially far out in the input length and use the maximum length of the query results as a parameter for the polynomial running time. Different notions of functional complexity exist, but all the results in the paper hold for every natural definition and most oracles will not impact the complexity in our use cases.

We therefore use $\mathrm{\Gamma}_{R},\mathrm{\Gamma}_{RCA}$ and $\mathrm{\Gamma}$ to represent classes of functions or functionals which will be clear from context.

3 Effective Strong Measure Zero Characterizations

We begin by utilizing the characterization of strong measure zero developed by Higuchi and Kihara.

Definition 5 (Higuchi and Kihara [9]).

An odds function is any function $O:\{0,1\}^{*}\rightarrow[1,\infty)$ . $O$ is said to be acceptable if $\prod_{w\sqsubset S}O(w)=\infty$ for all $S\in\mathbf{C}$ .

Higuchi and Kihara’s definition of an $O$ -supermartingale below can be viewed as a generalization of the other following martingale objects we will use in the paper.

Definition 6.

Let $O:\{0,1\}^{*}\rightarrow[1,\infty)$ be an odds function and $s\in[0,\infty)$ .

1.

An $O$ -supermartingale is a function ${d:\{0,1\}^{*}\rightarrow[0,\infty)}$ which satisfies

$d(w)\geq\frac{d(w0)}{O(w0)}+\frac{d(w1)}{O(w1)}$ (2)

for all $w\in\{0,1\}^{*}$ .
2.

An $O$ -martingale is an $O$ -supermartingale that satisfies (2) with equality
for all $w\in\{0,1\}^{*}$ .
3.

An s-supergale is an $O$ -supermartingale with the constant odds function $O(w)=2^{s}$ for all $w\in\{0,1\}^{*}$ .
4.

An s-gale is an $O$ -martingale with the constant odds function $O(w)=2^{s}$ for all $w\in\{0,1\}^{*}$ .
5.

A supermartingale is a 1-supergale.
6.

A martingale is a 1-gale.

We will use the following easy to verify result throughout the paper.

Observation 7.

Let $(d_{n})_{n\in\mathbb{N}}$ be a sequence of $O$ -supermartingales such that $\sum_{n\in\mathbb{N}}d_{n}(\lambda)<\infty$ . Then $d=\sum_{n\in\mathbb{N}}d_{n}$ is a $O$ -supermartingale. The same holds for the other martingale objects in Definition 6.

Definition 8.

Let $X\subseteq\mathbf{C}$ and $d$ be one of the martingale objects in Definition 6. We say that $d$ succeeds on $X$ if $\limsup_{n\to\infty}d(S[0\dots n])=\infty$ for all $S\in X$ .

Theorem 9 (Higuchi and Kihara [9]).

A set $X\subseteq\mathbf{C}$ has strong measure zero if and only if, for every acceptable odds $O:\{0,1\}^{*}\to[1,\infty)$ , there is an $O$ -supermartingale that succeeds on $X$ .

We will also make use of the following standard definitions and a lemma in their paper.

Definition 10.

An outer premeasure is a monotone subadditive atomless function $\mu:\{0,1\}^{*}\to[0,\infty)$ . That is, for all $w\in\{0,1\}^{*},a\in\{0,1\}$ and $S\in\mathbf{C}$ the following three properties hold:

1.

(monotone) $\mu(w)\geq\mu(wa)$ .
2.

(subadditive) $\mu(w)\leq\mu(w0)+\mu(w1)$ .
3.

(atomless) $\liminf_{n\to\infty}\mu(S[0\dots n])=0$ .

$\mu$ can be extended to an outer measure $\mu^{*}:\mathcal{P}(\mathbf{C})\to[0,\infty)$ by the “Method I construction” [30] to obtain

\mu^{*}(X)=\inf\{\sum_{w\in A}\mu(w)\mid A\subseteq\{0,1\}^{*}\text{ and }X% \subseteq\bigcup_{w\in A}C_{w}\}.

(3)

Lemma 11 (Higuchi and Kihara [9]).

Let $O$ be an odds function with $O(w0)^{-1}+O(w1)^{-1}\geq 1$ for all $w\in\{0,1\}^{*}$ . Then the function $\mu_{O}:\{0,1\}^{*}\to[0,\infty)$ defined by

\mu_{O}(w)=\prod_{i=0}^{|w|-1}O(w[0\dots i])^{-1}

is an outer premeasure.

One can then show that there is an $O$ -supermartingale that succeeds on a set $X$ if and only if $\mu_{O}^{*}(X)=0$ . In their paper, they defined a set as having effective strong measure zero if for every computable odds function $O$ there exists an $O$ -supermartingale that succeeds on the set. Here we instead use the following definition forcing effectivity on the $O$ -supermartingales.

Definition 12.

Let $\mathrm{\Delta}\in\mathrm{\Gamma}$ . A set $X\subseteq\mathbf{C}$ has $\mathrm{\Delta}$ -strong measure zero, $X\in\mathrm{\Delta}\operatorname{-SMZ}$ , if there is a functional

F:(\{0,1\}^{*}\to\mathbb{Q}\cap[1,2])\rightarrow(\{0,1\}^{*}\to[0,\infty))

in $\Delta$ such that for every acceptable odds function ${O:\{0,1\}^{*}\to\mathbb{Q}\cap[1,2]}$ , $F(O)$ is an $O$ -supermartingale that succeeds on $X$ . We say $F$ is an odds functional and write $F^{O}$ for $F(O)$ .

The fact that we limit odds functions to rationals in the interval $[1,2]$ may appear to be a weaker condition, but we will see that the definition is robust to this change and others later in this section. Note that all our odds functions therefore correspond to outer premeasures as in Lemma 11. From now on we will assume all odds functions are acceptable unless stated otherwise. We can also now see the connection between effective versions of strong measure zero, measure zero, and dimension zero.

Definition 13 (Lutz [18, 20, 21]).

Let $X\subseteq\mathbf{C}$ and $\mathrm{\Delta}\in\mathrm{\Gamma}$

1.

$X$ has $\mathrm{\Delta}$ -measure zero ( $X\in\mathrm{\Delta}\operatorname{-MZ}$ ), if there is a supermartingale $d\in\mathrm{\Delta}$ that succeeds on $X$ .
2.

$X$ has $\mathrm{\Delta}$ -dimension zero ( $X\in\mathrm{\Delta}\operatorname{-DZ}$ ), if there is a $s$ -supergale $d\in\mathrm{\Delta}$ that succeeds on $X$ for all $s\in\mathbb{Q}\cap(0,1)$ .

Observation 14.

For $X\subseteq\mathbf{C}$ and $\mathrm{\Delta}\in\mathrm{\Gamma}$ the following holds:

X\in\mathrm{\Delta}\operatorname{-SMZ}\implies X\in\mathrm{\Delta}% \operatorname{-DZ}\implies X\in\mathrm{\Delta}\operatorname{-MZ}

We will prove and use two similar equivalent in this section. First using success rates of supermartingales similar to the case for dimension [21, 6].

Definition 15.

A gauge function is a function $g:\mathbb{N}\to\mathbb{Q}^{+}$ that is non-increasing with ${\lim_{n\to\infty}g(n)=0}$ .

Definition 16.

A supermartingale $d$ $g$ -succeeds on $X\subseteq\mathbf{C}$ for a gauge function $g$ if

\limsup_{n\to\infty}\frac{d(S[0\dots n-1])}{2^{n}g(n)}=\infty

for all $S\in X$ .

$\blacktriangleright$ Remark 17.

Staiger [33] showed that a set has Hausdorff measure zero with respect to $g$ if and only if there is a supermartingale $d$ that $g$ -succeeds on it. In his work he looked at determining an exact gauge function for a set at the lower semicomputable and computable level. In this work we will instead be looking at sets that succeed on all gauges with oracle access to the gauges. In Staiger’s paper, and typically in fractal geometry, gauge functions have domain and range of $\mathbb{R}^{+}$ , see for example [7] for more background. The domain corresponds to diameters of sets which in our setting of Cantor space will be of the form $2^{-n}$ for $n\in\mathbb{N}$ . Schnorr [31] also looked at success rates with respect to order functions that can be seen as inverses of computable gauge functions.

Definition 18.

Let $\mathrm{\Delta}\in\mathrm{\Gamma}$ . A set $X\subseteq\mathbf{C}$ has $\mathrm{\Delta}$ -strong dimension zero, ${X\in\Delta\operatorname{-SDZ}}$ , if there is a functional

F:(\mathbb{N}\rightarrow\mathbb{Q}^{+})\rightarrow(\{0,1\}^{*}\rightarrow[0,% \infty))

in $\mathrm{\Delta}$ such that for every gauge function $g:\mathbb{N}\rightarrow[0,\infty)$ , $F(g)$ is a supermartingale that $g$ -succeeds on $X$ . We say $F$ is a dimension functional and write $F^{g}$ for $F(g)$ .

We now extend Hitchcock’s [10] characterization of dimension with predictors to our setting of strong measure zero.

Definition 19.

A superpredictor is a function $\pi:\{0,1\}^{*}\times\{0,1\}\to[0,1]$ such that

\pi(w,0)+\pi(w,1)\leq 1

(4)

for all $w\in\{0,1\}^{*}$ A predictor is a superpredictor that has equality for (4) for all $w\in\Sigma^{*}$ .

The value $\pi(w,a)$ is $\pi$ ’s prediction that the next bit in a sequence starting with $w$ will be $a$ . Given $p\in[0,1]$ we let $loss^{\log}(p)=\log\frac{1}{p}$ be the loss associated with a superpredictor predicting the next bit correctly with probability $p$ .

Definition 20.

The log-cumulative loss of a superpredictor $\pi$ on a string ${w\in\{0,1\}^{*}}$ is

\mathcal{L}^{\log}_{\pi}(w)=-\log(\prod_{i=0}^{|w|-1}\pi(w[0\dots i-1],w[i])).

Definition 21.

A prediction order is a function $h:\mathbb{N}\to\mathbb{Q}^{+}$ that is non-decreasing and unbounded. We say a predictor $\pi$ $h$ -succeeds on $X\subseteq\mathbf{C}$ if for all $S\in X$ ,

\liminf_{n\to\infty}\frac{\mathcal{L}^{\log}_{\pi}(S[0\dots n-1])}{h(n)}<1.

Definition 22.

Let $\mathrm{\Delta}\in\mathrm{\Gamma}$ . A set $X\subseteq\mathbf{C}$ is $\mathrm{\Delta}$ -strongly predictable if there is a functional

P:(\mathbb{N}\rightarrow\mathbb{Q}^{+})\rightarrow(\{0,1\}^{*}\times\{0,1\}% \rightarrow[0,1])

in $\mathrm{\Delta}$ such that for every prediction order $h$ , $P(h)$ is a predictor that $h$ -succeeds on $X$ .

Theorem 23 ( $\bigstar$ ).

For a set $X\subseteq\mathbf{C}$ and $\mathrm{\Delta}\in\Gamma$ allowing exponential time or polynomial space the following are equivalent:

1.

$X$ has $\mathrm{\Delta}$ -strong measure zero.
2.

$X$ has $\mathrm{\Delta}$ -strong dimension zero.
3.

$X$ is $\mathrm{\Delta}$ -strongly predictable.

Lastly we note that the restrictions on odds, gauge and predictor functions are robust in the following ways.

Lemma 24 ( $\bigstar$ ).

Let $D$ be any of the following sets or its intersection with $\mathbb{Q}$ . Then, defining $\mathrm{\Delta}$ strong measure zero as the sets succeeding on all acceptable odds functions $O:\{0,1\}^{*}\to D$ results in equivalent definitions for every $\mathrm{\Delta}\in\mathrm{\Gamma}$ .

1.

$[1,2]$
2.

$[1,\infty)$
3.

$\{1,2\}$
4.

$(1,2]$

Moreover, the choice between monotonic and strictly monotonic gauge and prediction orders does not matter.

4 Effective Borel Conjecture

Definition 25 (Lutz [18]).

Let $\mathrm{\Delta}\in\mathrm{\Gamma}_{RCA}$ . A set $X\subseteq\mathbf{C}$ is $\mathrm{\Delta}$ -countable if there is a function $\delta:\mathbb{N}\times\{0,1\}^{*}\rightarrow\{0,1\}^{*}$ with the following properties.

1.

$\delta\in\mathrm{\Delta}$ .
2.

For each $k\in\mathbb{N}$ , if we write $\delta_{k}(w)=\delta(k,w)$ , then the function $\delta_{k}$ is a constructor.
3.

$X\subseteq\{R(\delta_{k})\mid k\in\mathbb{N}\}$ .

$\blacktriangleright$ Remark 26.

In the original definition it was required that $X=\{R(\delta_{k})\mid k\in\mathbb{N}\}$ . For our purposes, we want all subsets of countable sets to be countable. Otherwise it is easy to come up with a set of languages $L_{i}$ with $|L_{i}|=1$ whose union is not $\mathrm{\Delta}$ -countable while having $\mathrm{\Delta}$ -strong measure zero.

Lemma 27 ( $\bigstar$ ).

Let $\mathrm{\Delta}\in\mathrm{\Gamma}$ . If $X$ is $\Delta$ -countable then $X\in\mathrm{\Delta}\operatorname{-SMZ}$ .

We will see that the other direction of Borel’s conjecture in the effective setting depends on the level of effectivity.

4.1 Time and Space Bounded Strong Measure Zero

We begin with the following result for singleton sets consisting of a sequence.

Lemma 28.

Let $f(n)$ be a function and $S\in\mathbf{C}$ be a sequence with $S\not=R(\delta)$ for every $\delta\in\mathrm{DTIME}(f(n))$ . Then there is an odds function $O$ such that no odds functional
$F\in\mathrm{DTIME}(f(n))$ succeeds on $S$ . Similarly for DSPACE.

Proof.

We will prove the DTIME version. Let $F_{0},F_{1},\dots$ be an enumeration of the odds functionals in $\mathrm{DTIME}(f(n))$ on odds oracles with range $\{1,2\}$ . We construct $O$ in steps $s\in\mathbb{N}$ with $O_{s}$ being the odds function after step $s$ and the starting $O_{-1}$ being the constant function $O(w)=1$ for all $w\in\{0,1\}^{*}$ . Note that this is not an acceptable odds function, but the resulting $O$ will be. We first describe the construction and then prove it works.

Algorithm 1 Constructing an unbeatable odds function

O

.

To see that this is possible at each stage, note that the oracle $O_{s-1}$ contains a finite amount of information. Moreover, as $F_{i}$ is resource bounded it has to eventually produce output even though $O_{s-1}$ is eventually all $1$ ’s and not acceptable. for every $i\leq s$ there must be infinitely many $k\in\mathbb{N}$ where $F_{i}^{O_{s-1}}(S[0\dots k+1])\leq\frac{1}{2}F_{i}^{O_{s-1}}(S[0\dots k])$ as otherwise a function could be created in $\mathrm{DTIME}(f(n))$ that computes $S$ . There are also only $s-1$ possible naturals $k$ such that $F_{i}^{O_{s-1}}(S[0\dots k+1])>F_{i}^{O_{s-1}}(S[0\dots k])$ . Hence ${F_{i}^{O_{s-1}}(S[0\dots n])\leq\frac{1}{2}}$ for all sufficiently large $n$ .

Thus, any odds functional $F_{i}$ will have $F_{i}^{O}(S[0\dots n])<2$ for all $n\geq n_{i}$ and hence not succeed on $S$ . $\hfill\blacktriangleleft$

To generalize this we prove the following result about $\mathrm{\Delta}$ -countable sets.

Lemma 29.

Let $\mathrm{\Delta}\in\mathrm{\Gamma}_{R}$ . Then there is a sequence of sets $X_{0},X_{1},X_{2}\subseteq\mathbf{C}$ such that the following hold.

1.

Each $X_{i}$ is $\mathrm{\Delta}$ -countable.
2.

$X_{i}\subseteq X_{i+1}$ for each $i\in\mathbb{N}$ .
3.

for every $S\in R(\mathrm{\Delta})$ , there is an $i$ such that $S\in X_{i}$ .

Proof.

We prove it for time bounds, the proof for space bounds is analogous. Let $f_{0},f_{1},f_{2},\dots$ be a sequence of functions such that each $f_{i}:\mathbb{N}\to\mathbb{N}\in\mathrm{\Delta}$ , $f_{i}=o(f_{i+1})$ , and $\mathrm{\Delta}=\bigcup_{i\in\mathbb{N}}\mathrm{DTIME}(f_{i})$ .

Now for each $f_{i}$ create a function $\delta_{i}:\mathbb{N}\times\{0,1\}^{*}\to\{0,1\}^{*}$ such that ${\delta_{i,k}(w)=\delta_{i}(k,w)}$ does the following. Let $k=\langle j,c\rangle$ for some $j,c\in\mathbb{N}$ . Then run the Turing machine $M_{j}$ on input $s_{|w|}$ for $f_{i}(|w|)+c$ steps. If it halts and accepts then output $w1$ , otherwise $w0$ . Then each $\delta_{i,k}$ is a constructor and $\{R(\delta)\mid\delta\in\mathrm{DTIME}(f_{i})\}=\{R(\delta_{i,k})\mid k\in% \mathbb{N}\}$ . Hence, letting $X_{i}=\{R(\delta_{i,k})\mid k\in\mathbb{N}\}$ the lemma holds. $\hfill\blacktriangleleft$

We are now able to prove the main result of this section.

Theorem 30.

If a set $X$ has $\mathrm{\Delta}\operatorname{-SMZ}$ for some $\mathrm{\Delta}\in\mathrm{\Gamma}_{R}$ then $X$ is $\mathrm{\Delta}$ -countable.

Proof.

We prove the contrapositive, suppose $X$ is not $\mathrm{\Delta}$ -countable and Let $f_{0},f_{1},f_{2},\dots$ be a sequence of functions that define $\mathrm{\Delta}$ . By Lemma 29, for every $m\in\mathbb{N}$ there must be some $S\in X$ such that $S\neq R(\delta)$ for every $\delta\in\mathrm{DTIME}(f_{m})$ . Thus, by Lemma 28 there is an $O$ that no odds functional in $\mathrm{DTIME}(f_{m})$ succeeds on for $S$ . $\hfill\blacktriangleleft$

The hypothesis of NP not having measure zero in E and the weaker hypothesis of NP not having dimension zero in E have led to many interesting consequences [19, 23]. For the case of strong measure zero, we get an even weaker hypothesis that gives a tight bound on the complexity of NP unlike in the other two cases.

Corollary 31.

$\mathrm{NP}$ has strong measure zero in $\mathrm{E}$ if and only if there is a $k\in\mathbb{N}$ such that

\mathrm{NP}\cap\mathrm{E}\subseteq\mathrm{DTIME}(2^{kn}).

4.2 Computable Strong Measure Zero

At the level of computability, we will see that strong measure zero does not imply countability. We start by defining a class of languages that are in a certain sense as close as possible to being computable.

Definition 32.

$S\in\mathbf{C}$ is almost constructible if there exists a computable

\delta:\mathbb{N}\times\{0,1\}^{*}\rightarrow\{0,1\}\times\{0,1\}^{*}

such that for every $w\sqsubseteq S$ and $n\in\mathbb{N}$ , $\delta(n,w)=(b,x)$ where $|x|=n$ and either $wb\sqsubseteq S$ or $wx\sqsubseteq S$ .

Example 33.

Let $M_{0},M_{1},M_{2}\dots$ be an enumeration of Turing machines and

f(n)=\max\{t\in\mathbb{N}\mid\exists k\in\mathbb{N},k\leq n\text{ and }M_{k}(k% )\text{ halts in exactly }t\text{ steps}\}.

Then the language $A=\mathrm{Graph}(f)=\{\langle n,f(n)\rangle\mid n\in\mathbb{N}\}$ is almost constructible, but not decidable.

Lemma 34 ( $\bigstar$ ).

If $S$ is almost constructible then $\{S\}$ has computable strong measure zero.

Note that for every undecidable language $S$ , $\{S\}$ is not computably countable so the following holds.

Corollary 35.

There exists an $X\subseteq\mathbf{C}$ with computable strong measure zero that is not computably countable.

5 Algorithmic Strong Measure Zero

We first show that at the level of lower-semicomputability there is a universal functional.

Definition 36.

A continuous semimeasure on $\mathbf{C}$ is a function $\mu:C\rightarrow\mathbb{R}^{+}$ such that $\mu(\lambda)\leq 1$ and $\mu(w)\geq\mu(w1)+\mu(w0)$ for all $w\in\{0,1\}^{*}$ .

Theorem 37 (Levin [35]).

There is a universal lower semicomputable continuous semimeasure $\mathbf{M}$ . That is, for every lower semicomputable continuous semimeasure $\mu$ there is a constant $c>0$ such that $\mathbf{M}(w)\geq c\mu(w)$ for all $w\in\{0,1\}^{*}$ .

Theorem 38 (Schnorr [31]).

The function $\mathbf{d}:\{0,1\}^{*}\rightarrow\mathbb{R}$ defined by $\mathbf{d}(x)=2^{|x|}\mathbf{M}(x)$ is a universal lower semicomputable supermartingale. That is, for every lower semicomputable supermartingale f there is a constant $c>0$ with $\mathbf{d}(w)\geq cf(w)$ for all $w\in\{0,1\}^{*}.$

Both of these theorems relativize to any oracle giving us the following.

Corollary 39.

There is an universal algorithmic functional $\mathbf{F}$ defined by ${\mathbf{F}(g)=\mathbf{d}^{g}}$ for all gauge functions $g:\mathbb{N}\to\mathbb{Q}^{+}$ . Specifically, a set $X\subseteq\mathbf{C}$ has algorithmic strong measure zero if and only if for every gauge function $g$ and every $S\in X$ ,

\limsup_{n\to\infty}\frac{\mathbf{d}^{g}(S[0\dots n])}{2^{n}g(n)}=\infty.

Unlike the other levels of effectivity, a set $X$ has algorithmic strong measure zero if and only if $\{S\}$ has algorithmic strong measure zero for every $S\in X$ . We will therefore focus on individual sequences and say $S$ has algorithmic strong measure zero if $\{S\}$ does. We make use of the relativized a priori complexity

\mathrm{KM}^{g}(x)=\log\frac{1}{\mathbf{M}^{g}(x)}

in order to classify the sequences with algorithmic strong measure zero.

Lemma 40.

A sequence $S$ has algorithmic strong measure zero if and only if for every gauge function $g$ there are infinitely many $n$ such that

\mathrm{KM}^{g}(S[0\dots n])\leq\log\frac{1}{g(n)}.

(5)

Proof.

Let $S$ be any sequence and $g$ be a gauge function. We have that $S$ has algorithmic strong measure zero if and only if

	$\displaystyle\limsup_{n\to\infty}\frac{\mathbf{d}^{g}(S[0\dots n])}{2^{n}g(n)}=\infty$
$\displaystyle\iff$	$\displaystyle\limsup_{n\to\infty}\frac{\mathbf{M}^{g}(S[0\dots n])}{g(n)}=\infty$
$\displaystyle\iff$	$\displaystyle\limsup_{n\to\infty}\frac{2^{-\mathrm{KM}^{g}(S[0\dots n])}}{g(n)% }=\infty.$	(6)

Note that ${\mathrm{KM}^{g}(x)=\mathrm{KM}^{g(n)^{2}}(x)+O(1)}$ . Hence, if we assume that (5) is true then there is a $c\in\mathbb{R}$ and infinitely many $n$ with $\mathrm{KM}^{g}(S[0\dots n])\leq\log\frac{1}{g(n)^{2}}+c$ . For each such $n$ we have $2^{-\mathrm{KM}^{g}(S[0\dots n])}\geq 2^{-c}g(n)^{2}$ and therefore $\frac{2^{-\mathrm{KM}^{g}(S[0\dots n])}}{g(n)^{2}}\geq 2^{-c}.$ Since $\lim_{n\to\infty}\frac{g(n)}{g(n)^{2}}=\infty$ , (6) is true.

For the other direction we will prove the contrapositive. Suppose there is gauge $g$ such that $\mathrm{KM}^{g}(S[0\dots n])>\log\frac{1}{g(n)}$ for all sufficiently large $n$ . Then we have $\frac{2^{-\mathrm{KM}^{g}(S[0\dots n])}}{g(n)}\leq 1$ for all sufficiently large $n$ so (6) does not hold. $\hfill\blacktriangleleft$

Reimann and Slaman have defined [28] a class of sequences called never continuously random, denoted NCR, consisting of all sequences that are never effectively random with respect to any continuous probability measure. Here continuous means the same as atomless, but the outer measures for strong measure zero in (11) are more general than probability measures. The following is an overview of the definition of NCR, see their paper for details.

Definition 41 (Reimann and Slaman [28]).

Let $\mu$ be a probability measure and $r_{\mu}$ be a representation of $\mu$ . Then

$\blacksquare$

A Martin-Löf- $\mu$ test relative to $r_{\mu}$ is a sequence of uniformly $\mathrm{\Sigma}_{1}^{0}$ sets $(W_{n})_{n\in\mathbb{N}}$ relative to $r_{\mu}$ with $\mu(W_{n})\leq 2^{-n}$ for all n.
$\blacksquare$

$X\in\mathbf{C}$ passes a Martin-Löf- $\mu$ test relative to $r_{\mu}$ if $X\not\in\bigcap_{n\in\mathbb{N}}W_{n}$ .
$\blacksquare$

$X\in\mathbf{C}$ is $\mu$ -random if it passes every Martin-Löf- $\mu$ test relative to $r_{\mu}$ for some representation $r_{\mu}$ of $\mu$ .
$\blacksquare$

$X\in\mathbf{C}$ is in NCR if it its not $\mu$ -random for every continuous probability measure $\mu$ .

A characterization of NCR by Li [16] based off the work of Reimann [27] and complex sequences defined by Kjos-Hanssen, Merkle, and Stephan [13] can be show to be equivalent to Lemma 40 yielding.

Theorem 42 ( $\bigstar$ ).

A sequence $S$ has algorithmic strong measure zero if and only if it is in NCR.

In the classical setting, the NCR class corresponds to sets that are measure zero with respect to all Borel atomless probability measures. These sets are referred to as universal measure zero which is a weaker property than strong measure zero. In fact, the existence of uncountable sets with universal measure zero is provable in ZFC [24]. However, Theorem 42 says that at the algorithmic level these two notions are equivalent. Reimann and Slaman also investigated $\mathrm{NCR}_{n}$ random sequences allowing more complex Martin-Löf tests. They were able to show each of these are countable, but in order to do so they needed an application of Borel determinacy and hence the existence of infinitely many iterates of the power set of the natural numbers [29].

6 Effective coverings and a Correspondence Principle

In this section we will look at how effective coverings can be used to characterize strong measure zero similar to Borel’s original definition.

Definition 43.

Let $\mathrm{\Delta}\in\mathrm{\Gamma}_{RCA}$ , $A\subseteq\mathbb{N}$ and $X\subseteq\mathbf{C}$ . A function ${f^{A}:\mathbb{N}\to\{0,1\}^{*}}$ is a $\mathrm{\Delta}$ - $A$ covering of $X$ if $f\in\mathrm{\Delta}$ with oracle $A:\mathbb{N}\to\{0,1\}$ satisfies the following.

1.

If $n\in A$ then $f^{A}(n)=w$ for some $w$ with $|w|=n$ .
2.

For every $S\in X$ there exits an $n\in A$ such that $f^{A}(n)\sqsubseteq S$ .

We refer to $\{f^{A}(n)\mid n\in A\}$ of such an $f$ as a $\mathrm{\Delta}$ - $A$ cover of $X$ and say that $X$ is strongly $\mathrm{\Delta}$ -coverable if there is a functional $F\in\mathrm{\Delta}$ such that $F(A)$ is a $\mathrm{\Delta}$ - $A$ covering of $X$ for all infinite $A\subseteq\mathbb{N}$ .

At the algorithmic level $\mathrm{\Delta}$ , the above definitions hold for $f^{A}$ being a partial recursive function that can also be undefined in condition 1 above. Specifically, $f$ corresponds to a oracle Turing machine that outputs a string of length $n$ or does not halt on every $n\in A$ .

Lemma 44.

For $\mathrm{\Delta}\in\mathrm{\Gamma}$ , a set $X$ has $\mathrm{\Delta}$ -strong measure zero if and only if it is strongly $\mathrm{\Delta}$ -coverable.

Proof.

It is easy to see that this is true for $\mathrm{\Delta}\in\mathrm{\Gamma}_{R}$ as well as $\mathrm{\Delta}=\mathrm{all}$ where it corresponds to the normal classical definition. We will prove that it is true for $\mathrm{\Delta}$ equal to computable or lower semicomputable. First, suppose $X$ has algorithmic (computable) strong measure zero and let $F$ be a odds functional witnessing this. Without loss of generality suppose $F^{O}(\lambda)<1$ for all odds functions $O$ . We will define a Turing machine $M$ that works as follows on oracle ${A=\{a_{0},a_{1},a_{2},\dots\}\subseteq\mathbb{N}}$ in standard order. Let $f_{A}:\mathbb{N}\rightarrow\mathbb{N}$ be the function

f_{A}(n)=a_{2^{n+2}-3}

and consider the odds function

O(w)=\begin{cases}2,&\text{if }|w|\in\mathrm{Range}(f_{A})\\ 1,&\text{otherwise}\end{cases}

Then let $M^{A}$ perform the following algorithm.

Algorithm 2 Definition of

M

.

Note that by construction the maximum number of strings $w$ with ${|w|=f_{A}(n)}$ and $F^{O}(w)>=1$ is at most $2^{n}$ in order for the supermartingale condition (2) to be satisfied. By construction, a prefix of each of these $w$ is output for every $n$ . Moreover, for every $S\in X$ , $F^{O}(S[0...n])$ can only increase on the lengths in $\mathrm{Range}(f_{A})$ . Therefore $M^{A}$ will output a prefix of $S$ for every $S$ with $\limsup_{n\to\infty}F^{O}(S[0\dots n])=\infty$ and hence all $S\in X.$

For the other direction, let $M^{A}$ be an oracle Turing machine that witnesses $X$ being strongly $\mathrm{\Delta}$ -coverable. We will define a odds functional that succeeds on $X$ given odds function $O$ as follows. Let

f_{O}(n)=\min\{m\in\mathbb{N}\mid\prod_{i=0}^{m-1}O(w[0\dots i])\geq n\text{ % for all }w\in\{0,1\}^{m}\}

be the minimum length $m$ so that the product of odds along every path of length $m$ is at least $n$ , noting it is possible by compactness. We will create an infinite set $d_{0},d_{1},d_{2},\dots$ of $O$ -martingales.

For $i\in\mathbb{N}$ let $A_{i}=\{f_{O}(2^{i+n})\mid n\in\mathbb{N}\}$ and let $d_{i}$ be an $O$ -martingale defined as follows.

$\blacksquare$

Initially let $d_{i}(w)=0$ for all $w\in\{0,1\}^{*}$
$\blacksquare$
For each $m=f_{O}(2^{i+n})\in A_{i}$ for some $n\in\mathbb{N}$ such that $M^{A_{i}}(m)=w$ :
- –
  
  Increase $d_{i}(\lambda)$ by $2^{-(i+n)}$ .
- –
  
  Increase $d_{i}(w[0\dots j])$ by $2^{-(i+n)}\prod_{k=0}^{j}O(w[0\dots k])$ for $j<|w|$ .
- –
  
  Increase $d_{i}(w0^{m})$ by $2^{-(i+n)}\prod_{j=0}^{|w|-1}O(w[0\dots j])\prod_{k=0}^{m}O(w0^{k})$ for all $m\in\mathbb{N}$ .

Then $d_{i}$ is a $\Delta$ -computable $O$ -martingale. For each $w$ in the range of $M^{A_{i}}$ we have $d_{i}(w)\geq 2^{-(i+n)}2^{2i+n}=2^{i}$ and hence $d_{i}$ shows that the $\limsup_{n\to\infty}d^{O}(S[0\dots n])\geq 2^{i}$ for all $S\in X$ . Now letting $F(O)=d=\sum_{i\in\mathbb{N}}d_{i}$ we have that $F(O)$ succeeds on all $S\in X$ . It is clear that $F\in\mathrm{\Delta}$ and we have $d(\lambda)<\infty$ since

d(\lambda)=\sum_{i\in\mathbb{N}}d_{i}(\lambda)\leq\sum_{i\in\mathbb{N}}(\sum_{% n\in\mathbb{N}}2^{-(i+n)})=\sum_{i\in\mathbb{N}}2^{-i+1}=4.\

$\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 45.

In the above proof we used a functional giving coverings to create a odds functional that outputs odds martingales for all odds functions. Therefore, odds martingales can be used instead of odds supermartingales to define $\mathrm{\Delta}$ -strong measure zero as is the case with dimension [11]. It follows that dropping the super on other characterizations also makes no impact.

This covering characterization can be used to show a correspondence theorem that is an analogue to the result of Hitchcock [12] for dimension.

Lemma 46 ( $\bigstar$ ).

Let $X$ be a $\mathrm{\Sigma}_{2}^{0}$ set. Then the following are equivalent.

1.

$X$ is strongly coverable
2.

$X$ is algorithmically strongly coverable
3.

$X$ is computably strongly coverable

Moreover 1 and 2 are equivalent for every union of $\mathrm{\Pi}_{1}^{0}$ sets.

Using this we are able to determine how complex computable strong measure zero sets can be by using the following result.

Theorem 47 (Cenzer et al. [5]).

Let $\alpha$ be a computable ordinal. Then there is a countable $\mathrm{\Pi}_{1}^{0}$ class containing $x$ with $x\equiv_{\mathrm{T}}\emptyset^{(\alpha)}.$

Corollary 48.

for every computable ordinal $\alpha$ there is a $x$ with $x\equiv_{\mathrm{T}}\emptyset^{(\alpha)}$ and $\{x\}$ having computable strong measure zero.

Kjos-Hanssen and Montalbán [25] had proved this result for NCR using Theorem 47 as well. Reimann and Slaman [28] showed that this is the best that can be done by proving if $x$ is not hyperarithmetic then it is not in NCR.

7 Strong Packing Dimension Zero

In this section we look at what happens if success is required in the limit inferior. We will use the following definition, but it is equivalent to our other characterizations of strong measure zero with a limsup replaced for a liminf.

Definition 49.

Let $\mathrm{\Delta}\in\mathrm{\Gamma}$ . A set $X\subseteq\mathbf{C}$ has $\mathrm{\Delta}$ -strong packing dimension zero if there is a $\mathrm{\Delta}$ -computable functional

F:(\{0,1\}^{*}\to\mathbb{Q}\cap[1,2])\rightarrow(\{0,1\}^{*}\to[0,\infty))

such that for every acceptable odds function ${O:\{0,1\}^{*}\to\mathbb{Q}\cap[1,2]}$ , $F(O)$ is an
$O$ -supermartingale with $\liminf_{n\to\infty}d(S[0\dots n])=\infty$ for all $S\in X$ .

For $\mathrm{\Delta}\in\mathrm{\Gamma}_{R}$ it’s easy to see that the change does not affect the sets, so we will focus on the computable and algorithmic versions. There exists another formulation of strong packing dimension zero by Zindulka [34] using box dimensions in the classical setting. He proved a characterization in terms of coverings that inspires the following definition.

Definition 50.

Let $\mathrm{\Delta}\in\mathrm{\Gamma}_{RCA}$ , $A=\{a_{0},a_{1},a_{2},\dots\}\subseteq\mathbb{N}$ be an infinite set and $X\subseteq\mathbf{C}$ . A function ${f^{A}:\mathbb{N}\to\{0,1\}^{*}}$ is a frequent $\mathrm{\Delta}$ - $A$ covering of $X$ if $f\in\mathrm{\Delta}$ with oracle $A:\mathbb{N}\to\{0,1\}^{*}$ satisfies the following.

1.

if $n\in A$ then $f^{A}(n)=w$ for some $w$ with $|w|=n$ .
2.

If $A_{0}=\{a_{0},\},A_{1}=\{a_{1},a_{2}\},\dots A_{i}=\{a_{\frac{i(i+1)}{2}},a_{% \frac{i(i+1)}{2}+1},\dots a_{\frac{i(i+1)}{2}+i}\}$ then for every $S\in X$ there exits only finitely many $i$ where $f^{A}(a_{n})\not\sqsubseteq S$ for all $a_{n}\in A_{i}$ .

We say that $X$ is $\mathrm{\Delta}$ -frequently coverable if there is a functional $F\in\mathrm{\Delta}$ such that $F(A)$ is a frequent $\mathrm{\Delta}$ - $A$ covering of $X$ for all infinite $A\subseteq\mathbb{N}$ .

Again at the algorithmic level $\mathrm{\Delta}$ , the above definitions hold for $f^{A}$ being a partial recursive function that can also be undefined in condition 1 above.

Lemma 51.

A set $X$ has algorithmic (computable) strong packing dimension zero if and only if it is algorithmically (computably) frequently coverable.

Proof.

First suppose $X$ has algorithmic (computable) strong packing dimension zero and let $F$ be a odds functional witnessing this. Without loss of generality suppose $F^{O}(\lambda)<1$ for all odds functions $O$ . We will define a Turing machine $M$ that works as follows on input $A=\{a_{0},a_{1},a_{2},\dots\}\subseteq\mathbb{N}$ in standard order. Let $f_{A}:\mathbb{N}\rightarrow\mathbb{N}$ be the function

f_{A}(n)=a_{\frac{n(n+1)}{2}+n}

and consider the odds function

O(w)=\begin{cases}\frac{n+2}{n+1},&\text{if }|w|=f_{A}(n)\\ 1,&\text{otherwise}\end{cases}

Then let $M^{A}$ be the following algorithm.

Algorithm 3 Definition of

M

.

Note that by construction the maximum number of strings of $w$ with ${|w|=f_{A}(n)}$ such that $F^{O}(w)>1$ is at most

(\prod_{i=0}^{n}\frac{i+2}{i+1})-1=n+1

in order for the supermartingale condition (2) to be satisfied. Therefore each of these $n+1$ strings can be output for the set $A_{i}$ . Thus, for every $S\in X$ , $F^{O}(S[0...n])>1$ for all but finitely many $n\in\mathrm{Range}(f_{A})$ so it must have a prefix in all but finitely many $A_{i}$ .

For the other direction let $M$ be an oracle Turing machine showing that $X$ is $\mathrm{\Delta}$ -frequently coverable. We will define a odds functional that succeeds on $X$ given odds function $O$ as follows. Let

g_{O}(n)=\max\{\prod_{i=0}^{n-1}O(w[0\dots i])\mid w\in\{0,1\}^{n}\}

be the maximum product of odds along any string of length $n$ (with $g_{O}(0)=1$ ). Define a function $f_{O}:\mathbb{N}\to\mathbb{N}$ by

f_{O}(n)=\min\{m\in\mathbb{N}\mid\prod_{i=0}^{m-1}O(w[0\dots i])\geq 2(n+1)% \cdot g_{O}(f_{O}(n-1))\text{ for all }w\in\{0,1\}^{m}\}

using $f_{O}(-1)=0$ . This is the minimum length $m$ so that the product of odds along every path of length $m$ is at least $2(n+1)$ times the amount of any string of length $f_{O}(n-1)$ . Note this is possible by compactness. Let

A=\bigcup_{n\in\mathbb{N}}\{f_{O}(n),f_{O}(n)+1,\dots f_{O}(n)+n\}

and $A_{0},A_{1},A_{2}\dots$ be as stated in the lemma. We will define a $O$ -supermartingale $d$ in steps where $d_{i}$ is the $O$ -supermartingale after step $i$ and $d=\lim_{n\to\infty}d_{i}$ . Starting with $d_{-1}(w)=0$ for all $w$ , let $d_{i+1}=d_{i}$ with the following changes.

$\blacksquare$
For each each $a_{j}\in A_{i+1}$ where $M^{A}(a_{j})=w$ :
- –
  
  Add $\frac{1}{(i+2)2^{(i+2)}}$ to $d_{i+1}(\lambda)$ .
- –
  
  Add $\frac{1}{(i+2)2^{(i+2)}}\prod_{j=0}^{k}O(w[0\dots j])$ to $d_{i+1}(w[0\dots j])$ for $0\leq k<f_{O}(i+1)$ .
- –
  For each $x$ where $x=M^{A}(a_{k})$ for some $a_{k}\in A_{i}$ and $x\sqsubset w$ :
  - *
    
    add $\frac{1}{i+1}d_{i}(x)\prod_{j=f_{O}(i)}^{k}O(w[0\dots j])$ to $d_{i+1}(w[0\dots k])$ for all ${f_{O}(i)\leq k<f_{O}(i+1)}$ .

Note that there are at most $i+1$ extensions of a $x$ in $A_{i}$ to a $w$ in $A_{i+1}$ so this results in a $O$ -supermartingale. At the computable level, $d$ can be computed to arbitrary precision by computing $d_{i}$ exactly after $i$ is large enough. At the algorithmic level, an algorithm can keep track of the seen outputs and perform the necessary changes from last step when connections are found across different levels.

Then we have that

d(\lambda)\leq\sum_{i\in\mathbb{N}}(i+1)(\frac{1}{(i+1)2^{(i+1)}})=1

so $F(O)=d$ is an $O$ -supermartingale. Now suppose that $S\in X$ and let $n$ be such that $A_{i}$ contains a prefix of $S$ for all $i\geq n$ . Let $r>0$ be such that $d(S[0\dots f_{O}(n)])=r$ . Then by construction, for all $k\geq f_{O}(n+i)$ we have $d(S[0\dots k])\geq\frac{2^{i}r}{n+i+1}$ and hence $\liminf_{n\to\infty}d^{O}(S[0\dots n])=\infty.$ $\hfill\blacktriangleleft$

Lemma 52.

If a sequence $S$ has algorithmic strong packing dimension zero then there is a fixed constant $c\in\mathbb{N}$ and a Turing Machine $M$ such that $M$ halts on at most $c$ inputs of length $n$ , one of which is $S[0\dots n]$ , for all $n\in\mathbb{N}$ .

Proof.

We will prove the contrapositive. Assume no such $M$ exists and let $N$ be any oracle Turing machine. We will construct an $A\subseteq\mathbb{N}$ such that $N^{A}$ does not produce a frequent cover.

We do this in stages. At stage $s$ , let $A^{s-1}$ be the finite set of naturals in $A$ after stage $s-1$ , initially empty, and let $m_{s-1}=\max\{A^{s-1}\}$ . Let $n_{s}$ be the amount of naturals needed to finish the next $A_{i}$ along with $A_{i-1}$ if necessary as defined in the third condition of Definition 50. Now let $m\in\mathbb{N}>m_{s-1}$ be such that the last condition in the following construction holds:

$\blacksquare$

Let $A^{\prime}=A^{s-1}\cup\{m,m+1,\dots m+n_{s}-1\}$ .
$\blacksquare$

Dovetail $N$ on inputs $m,m+1,\dots,m+n_{s}-1$ and all finite oracles $A$ that extend $A^{\prime}$ .
$\blacksquare$

Whenever $N$ halts on one of these inputs update $A^{\prime}$ to be this new finite oracle that caused $N$ to halt and restart dovetailing on the rest.
$\blacksquare$

After $N$ has halted on all inputs or $A^{\prime}$ has been defined to where no extension of $A^{\prime}$ will cause any of the remaining inputs to halt, none of the outputs are a prefix of $S$ .

Then define $A_{s}$ to be the final $A^{\prime}$ above and go to the next stage.

It is clear $A_{i}$ will not contain a prefix of $S$ so it suffices to show that there is such an $m$ at each stage. If this was not possible at some stage $s$ , then using the finite $A^{s-1}$ and the machine $N$ , it is possible to create a new Turing machine $M$ that performs the above dovetailing for each $m$ and creates a computably enumerable set of size at most $n_{s}=c$ strings of length m with one being a prefix of $S$ , contradicting our assumption. $\hfill\blacktriangleleft$

Corollary 53.

If a sequence $S$ has algorithmic or computable strong packing dimension zero then $S$ is decidable.

Proof.

By Lemma 52, any $S$ with algorithmic strong packing dimension zero has $\mathrm{K}(S[0\dots n]|n)\leq c$ for some $c$ and all $n$ . Therefore $S$ is decidable, see for instance [15]. $\hfill\blacktriangleleft$

However, the set of all decidable langauges does not have computable strong packing dimension zero. The sets at the computable level can be classified in the following way.

Definition 54.

A weak constructor is a function $\delta:\mathbb{N}\rightarrow({\{0,1\}^{*}})^{b}$ for some $b\in\mathbb{N}$ satisfying $w\in\delta(n)\Rightarrow\exists u\in\delta(n-1)\text{ with }u\sqsubset w$ for all $n\in\mathbb{N}^{+}$ . The result of a weak constructor is the set $\{S\in\mathbf{C}\mid\forall n\in\mathbb{N}\enspace\exists w\in\delta(n)% \enspace w\sqsubseteq S\}$ .

It is easy to see that every normal constructor coincides with a weak constructor with $b=1$ and that a language is decidable if and only if has a computable weak constructor. One can view a weak constructor as a growing tree with at most $b$ “alive” branches at any stage. The extra power comes from not having to decide which branch to follow in a computable amount of time when looking at effective unions of constructors.

Definition 55.

A set $X\subseteq\mathbf{C}$ is weakly $\mathrm{\Delta}$ -countable if there exists a function $\delta:\mathbb{N}\times\mathbb{N}\rightarrow\mathcal{P}\{0,1\}^{*}$ meeting the following properties.

1.

$\delta\in\mathrm{\Delta}$ .
2.

For each $k\in\mathbb{N}$ , if we write $\delta_{k}(n)=\delta(k,n)$ , then the function $\delta_{k}$ is a weak constructor.
3.

$X\subseteq\bigcup_{k\in\mathbb{N}}R(\delta_{k})$ .

Theorem 56 ( $\bigstar$ ).

A set $X$ has computable strong packing dimension zero if and only if it is weakly computably countable.

References

[1] Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo. Effective strong dimension in algorithmic information and computational complexity. SIAM journal on computing, 37(3):671–705, 2007. doi:10.1137/S0097539703446912.
[2] T. Bartoszyński and H. Judah. Set theory: On the structure of the real line. Studia Logica, 62(3):444–445, 1999.
[3] AS Besicovitch. On the definition of tangents to sets of infinite linear measure. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 52, pages 20–29. Cambridge University Press, 1956.
[4] E. Borel. Sur la classification des ensembles de mesure nulle. Bulletin de la Société Mathématique de France, 47:97–125, 1919. URL: http://eudml.org/doc/86398.
[5] Douglas Cenzer, Peter Clote, Rick L Smith, Robert I Soare, and Stanley S Wainer. Members of countable $\pi$ 10 classes. Annals of Pure and Applied Logic, 31, 1986. doi:10.1016/0168-0072(86)90067-9.
[6] Rodney G. Downey and Denis R. Hirschfeldt. Algorithmic Randomness and Complexity. Springer Science & Business Media, 2010.
[7] Kenneth Falconer. Fractal geometry: mathematical foundations and applications. Wiley, 2014.
[8] F Hausdorff. Dimension und äußeres maß. Mathematische Annalen, 79:157–179, 1919.
[9] Kojiro Higuchi and Takayuki Kihara. On effectively closed sets of effective strong measure zero. Annals of Pure and Applied Logic, 165(9):1445–1469, September 2014. doi:10.1016/j.apal.2014.04.013.
[10] John M Hitchcock. Fractal dimension and logarithmic loss unpredictability. Theoretical Computer Science, 304(1-3):431–441, 2003. doi:10.1016/S0304-3975(03)00138-5.
[11] John M Hitchcock. Gales suffice for constructive dimension. Information Processing Letters, 86(1):9–12, 2003. doi:10.1016/S0020-0190(02)00454-4.
[12] John M Hitchcock. Correspondence principles for effective dimensions. Theory of Computing Systems, 38(5):559–571, 2005. doi:10.1007/S00224-004-1122-1.
[13] Bjørn Kjos-Hanssen, Wolfgang Merkle, and Frank Stephan. Kolmogorov complexity and the recursion theorem. In STACS 2006: 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006. Proceedings 23, pages 149–161. Springer, 2006. doi:10.1007/11672142_11.
[14] Richard Laver. On the consistency of Borel’s conjecture. Acta Mathematica, 137(none):151–169, 1976. doi:10.1007/BF02392416.
[15] Ming Li and Paul M.B. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Springer Publishing Company, Incorporated, 4 edition, 2019.
[16] Mingyang Li. Algorithmic randomness and complexity for continuous measures. PhD thesis, Pennsylvania State University, 2020.
[17] Jack H Lutz. Category and measure in complexity classes. SIAM Journal on Computing, 19(6):1100–1131, 1990. doi:10.1137/0219076.
[18] Jack H. Lutz. Almost everywhere high nonuniform complexity. J. Comput. Syst. Sci., 44(2):220–258, April 1992. doi:10.1016/0022-0000(92)90020-J.
[19] Jack H Lutz. The quantitative structure of exponential time. In [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference, pages 158–175. IEEE, 1993. doi:10.1109/SCT.1993.336530.
[20] Jack H Lutz. Dimension in complexity classes. SIAM Journal on Computing, 32(5):1236–1259, 2003. doi:10.1137/S0097539701417723.
[21] Jack H. Lutz. The dimensions of indvidual strings and sequences. Information and Computation, 187(1):49–79, 2003. doi:10.1016/S0890-5401(03)00187-1.
[22] Jack H Lutz. Effective fractal dimensions. Mathematical Logic Quarterly, 51(1):62–72, 2005. doi:10.1002/MALQ.200310127.
[23] Jack H Lutz, Neil Lutz, and Elvira Mayordomo. Dimension and the structure of complexity classes. Theory of Computing Systems, 67(3):473–490, 2023. doi:10.1007/S00224-022-10096-7.
[24] Arnold W Miller. Special subsets of the real line. In Handbook of set-theoretic topology, pages 201–233. Elsevier, 1984.
[25] Antonio Montalbán. Beyond the arithmetic. PhD thesis, Cornell University, 2005.
[26] Matthew Rayman. Effective versions of strong measure zero. arXiv preprint arXiv:2506.02031, 2025. doi:10.48550/arXiv.2506.02031.
[27] Jan Reimann. Effectively closed sets of measures and randomness. Annals of Pure and Applied logic, 156(1):170–182, 2008. doi:10.1016/J.APAL.2008.06.015.
[28] Jan Reimann and Theodore Slaman. Measures and their random reals. Transactions of the American Mathematical Society, 367(7):5081–5097, 2015.
[29] Jan Reimann and Theodore Slaman. Effective randomness for continuous measures. Journal of the American Mathematical Society, 35(2):467–512, 2022.
[30] Claude Ambrose Rogers. Hausdorff measures. Cambridge University Press, 1998.
[31] Claus-Peter Schnorr. A unified approach to the definition of random sequences. Mathematical Systems Theory, 5(3):246–258, 1971. doi:10.1007/BF01694181.
[32] Wacław Sierpiński. Sur un ensemble non dénombrable, dont toute image continue est de mesure nulle. Fundamenta Mathematicae, 11(1):302–303, 1928. URL: http://eudml.org/doc/211448.
[33] Ludwig Staiger. Exact constructive and computable dimensions. Theory of Computing Systems, 61:1288–1314, 2017. doi:10.1007/S00224-017-9790-9.
[34] Ondrej Zindulka. Small sets of reals through the prism of fractal dimensions. arXiv preprint arXiv:1208.5521, 2012.
[35] Alexander K. Zvonkin and Leonid A. Levin. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russian Mathematical Surveys, 25(6):83, 1970.

[bib.bib1] [1] Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo. Effective strong dimension in algorithmic information and computational complexity. SIAM journal on computing, 37(3):671–705, 2007. doi:10.1137/S0097539703446912.

[bib.bib2] [2] T. Bartoszyński and H. Judah. Set theory: On the structure of the real line. Studia Logica, 62(3):444–445, 1999.

[bib.bib3] [3] AS Besicovitch. On the definition of tangents to sets of infinite linear measure. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 52, pages 20–29. Cambridge University Press, 1956.

[bib.bib4] [4] E. Borel. Sur la classification des ensembles de mesure nulle. Bulletin de la Société Mathématique de France, 47:97–125, 1919. URL: http://eudml.org/doc/86398.

[bib.bib5] [5] Douglas Cenzer, Peter Clote, Rick L Smith, Robert I Soare, and Stanley S Wainer. Members of countable $\pi$ 10 classes. Annals of Pure and Applied Logic, 31, 1986. doi:10.1016/0168-0072(86)90067-9.

[bib.bib6] [6] Rodney G. Downey and Denis R. Hirschfeldt. Algorithmic Randomness and Complexity. Springer Science & Business Media, 2010.

[bib.bib7] [7] Kenneth Falconer. Fractal geometry: mathematical foundations and applications. Wiley, 2014.

[bib.bib8] [8] F Hausdorff. Dimension und äußeres maß. Mathematische Annalen, 79:157–179, 1919.

[bib.bib9] [9] Kojiro Higuchi and Takayuki Kihara. On effectively closed sets of effective strong measure zero. Annals of Pure and Applied Logic, 165(9):1445–1469, September 2014. doi:10.1016/j.apal.2014.04.013.

[bib.bib10] [10] John M Hitchcock. Fractal dimension and logarithmic loss unpredictability. Theoretical Computer Science, 304(1-3):431–441, 2003. doi:10.1016/S0304-3975(03)00138-5.

[bib.bib11] [11] John M Hitchcock. Gales suffice for constructive dimension. Information Processing Letters, 86(1):9–12, 2003. doi:10.1016/S0020-0190(02)00454-4.

[bib.bib12] [12] John M Hitchcock. Correspondence principles for effective dimensions. Theory of Computing Systems, 38(5):559–571, 2005. doi:10.1007/S00224-004-1122-1.

[bib.bib13] [13] Bjørn Kjos-Hanssen, Wolfgang Merkle, and Frank Stephan. Kolmogorov complexity and the recursion theorem. In STACS 2006: 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006. Proceedings 23, pages 149–161. Springer, 2006. doi:10.1007/11672142_11.

[bib.bib14] [14] Richard Laver. On the consistency of Borel’s conjecture. Acta Mathematica, 137(none):151–169, 1976. doi:10.1007/BF02392416.

[bib.bib15] [15] Ming Li and Paul M.B. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Springer Publishing Company, Incorporated, 4 edition, 2019.

[bib.bib16] [16] Mingyang Li. Algorithmic randomness and complexity for continuous measures. PhD thesis, Pennsylvania State University, 2020.

[bib.bib17] [17] Jack H Lutz. Category and measure in complexity classes. SIAM Journal on Computing, 19(6):1100–1131, 1990. doi:10.1137/0219076.

[bib.bib18] [18] Jack H. Lutz. Almost everywhere high nonuniform complexity. J. Comput. Syst. Sci., 44(2):220–258, April 1992. doi:10.1016/0022-0000(92)90020-J.

[bib.bib19] [19] Jack H Lutz. The quantitative structure of exponential time. In [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference, pages 158–175. IEEE, 1993. doi:10.1109/SCT.1993.336530.

[bib.bib20] [20] Jack H Lutz. Dimension in complexity classes. SIAM Journal on Computing, 32(5):1236–1259, 2003. doi:10.1137/S0097539701417723.

[bib.bib21] [21] Jack H. Lutz. The dimensions of indvidual strings and sequences. Information and Computation, 187(1):49–79, 2003. doi:10.1016/S0890-5401(03)00187-1.

[bib.bib22] [22] Jack H Lutz. Effective fractal dimensions. Mathematical Logic Quarterly, 51(1):62–72, 2005. doi:10.1002/MALQ.200310127.

[bib.bib23] [23] Jack H Lutz, Neil Lutz, and Elvira Mayordomo. Dimension and the structure of complexity classes. Theory of Computing Systems, 67(3):473–490, 2023. doi:10.1007/S00224-022-10096-7.

[bib.bib24] [24] Arnold W Miller. Special subsets of the real line. In Handbook of set-theoretic topology, pages 201–233. Elsevier, 1984.

[bib.bib25] [25] Antonio Montalbán. Beyond the arithmetic. PhD thesis, Cornell University, 2005.

[bib.bib26] [26] Matthew Rayman. Effective versions of strong measure zero. arXiv preprint arXiv:2506.02031, 2025. doi:10.48550/arXiv.2506.02031.

[bib.bib27] [27] Jan Reimann. Effectively closed sets of measures and randomness. Annals of Pure and Applied logic, 156(1):170–182, 2008. doi:10.1016/J.APAL.2008.06.015.

[bib.bib28] [28] Jan Reimann and Theodore Slaman. Measures and their random reals. Transactions of the American Mathematical Society, 367(7):5081–5097, 2015.

[bib.bib29] [29] Jan Reimann and Theodore Slaman. Effective randomness for continuous measures. Journal of the American Mathematical Society, 35(2):467–512, 2022.

[bib.bib30] [30] Claude Ambrose Rogers. Hausdorff measures. Cambridge University Press, 1998.

[bib.bib31] [31] Claus-Peter Schnorr. A unified approach to the definition of random sequences. Mathematical Systems Theory, 5(3):246–258, 1971. doi:10.1007/BF01694181.

[bib.bib32] [32] Wacław Sierpiński. Sur un ensemble non dénombrable, dont toute image continue est de mesure nulle. Fundamenta Mathematicae, 11(1):302–303, 1928. URL: http://eudml.org/doc/211448.

[bib.bib33] [33] Ludwig Staiger. Exact constructive and computable dimensions. Theory of Computing Systems, 61:1288–1314, 2017. doi:10.1007/S00224-017-9790-9.

[bib.bib34] [34] Ondrej Zindulka. Small sets of reals through the prism of fractal dimensions. arXiv preprint arXiv:1208.5521, 2012.

[bib.bib35] [35] Alexander K. Zvonkin and Leonid A. Levin. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russian Mathematical Surveys, 25(6):83, 1970.

Effective Versions of Strong Measure Zero

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Theorem 1.

Theorem 2.

2 Preliminaries

Definition 3.

Definition 4 (Lutz [17]).

3 Effective Strong Measure Zero Characterizations

Definition 5 (Higuchi and Kihara [9]).

Definition 6.

Observation 7.

Definition 8.

Theorem 9 (Higuchi and Kihara [9]).

Definition 10.

Lemma 11 (Higuchi and Kihara [9]).

Definition 12.

Definition 13 (Lutz [18, 20, 21]).

Observation 14.

Definition 15.

Definition 16.

▶ Remark 17.

Definition 18.

Definition 19.

Definition 20.

Definition 21.

Definition 22.

Theorem 23 (★).

Lemma 24 (★).

4 Effective Borel Conjecture

Definition 25 (Lutz [18]).

▶ Remark 26.

Lemma 27 (★).

4.1 Time and Space Bounded Strong Measure Zero

Lemma 28.

Proof.

Lemma 29.

Proof.

Theorem 30.

Proof.

Corollary 31.

4.2 Computable Strong Measure Zero

Definition 32.

Example 33.

Lemma 34 (★).

Corollary 35.

5 Algorithmic Strong Measure Zero

Definition 36.

Theorem 37 (Levin [35]).

Theorem 38 (Schnorr [31]).

Corollary 39.

Lemma 40.

Proof.

Definition 41 (Reimann and Slaman [28]).

Theorem 42 (★).

6 Effective coverings and a Correspondence Principle

Definition 43.

Lemma 44.

Proof.

▶ Remark 45.

Lemma 46 (★).

Theorem 47 (Cenzer et al. [5]).

Corollary 48.

7 Strong Packing Dimension Zero

Definition 49.

Definition 50.

Lemma 51.

Proof.

Lemma 52.

Proof.

$\blacktriangleright$ Remark 17.

Theorem 23 ( $\bigstar$ ).

Lemma 24 ( $\bigstar$ ).

$\blacktriangleright$ Remark 26.

Lemma 27 ( $\bigstar$ ).

Lemma 34 ( $\bigstar$ ).

Theorem 42 ( $\bigstar$ ).

$\blacktriangleright$ Remark 45.

Lemma 46 ( $\bigstar$ ).

Theorem 56 ( $\bigstar$ ).