Measure-theoretic uniformity and the Suslin functional

Abstract

Given a set A in the unit interval and the associated Lebesgue measure λ, it is a natural question whether we may (in some sense) compute the measure $λ (A)$ in terms of the set A. Under the moniker measure theoretic uniformity, Tanaka and Sacks have (independently) provided a positive answer for the well-known class of hyperarithmetical sets of reals, and provided a basis theorem for such sets of positive measure. The hyperarithmetical sets are exactly the sets computable in terms of the functional $^{2} E$ , in the sense of Kleene’s S1–S9. In turn, Kleene’s $^{2} E$ essentially corresponds to arithmetical comprehension as in ${ACA}_{0}$ . In this paper, we generalise the aforementioned results to the ‘next level’, namely $Π_{1}^{1} {-CA}_{0}$ , in the form of the Suslin functional, or the equivalent hyperjump. We also generalise the Tanaka-Sacks basis theorem to sets of positive measure that are semi-computability relative to the Suslin functional. Finally, we discuss similar generalisations for infinite time Turing machines.

Keywords

Measurability Suslin operator infinite time Turing machine

1. Introduction

1.1. Measure, uniformity, and computability

Infamous as they may be to the highschool students required to memorise them, the formulas for determining the length, surface, or volume of basic objects in three-dimensional Euclidean space are highly elementary in the sense of computational complexity. Now, the Lebesgue measure λ assigns a real number $λ (A)$ to general classes of sets A conforming to the intuitive rules governing length, surface, and volume (as much as possible). In its full generality, measure theory is a complicated affair as even the countable additivity of the Lebesgue measure requires a fragment of the Axiom of Choice not provable in $ZF$ [5]. In light of this, it is a natural question whether we may (somehow) compute the measure $λ (A)$ in terms of the set A, for certain classes of sets. In a nutshell, the aim of this paper is to provide a substantial generalisation of established results, known as measure-theoretic uniformity, by Tanaka [22] and Sacks [16], on the computational properties of the Lebesgue measure. We should note that ‘computable’ in general refers to Kleene’s well-known schemes S1–S9, see [8] or [10, p. 169], unless explicitly stated otherwise. We give our equivalent, modified version of Kleene computability in Definition 1.1.

First of all, the aforementioned results due to Tanaka and Sacks (see Theorem 1.3 for the exact formulation), deal with the well-known hyperarithmetical sets. The latter are exactly the sets Kleene-computable in the functional $^{2} E$ (see Section 1.2), and computing with $^{2} E$ represents a natural transfinite extension of the arithmetical comprehension principle, expressed by the axiom ${ACA}_{0}$ from [20, III], up to the first non-computable ordinal. In this paper, we generalise the Tanaka-Sacks results to the ‘next level’, namely $Π_{1}^{1} {-CA}_{0}$ , in the form of the Suslin functional S, or the equivalent hyperjump (see Section 1.2 for definitions). We also generalise the basis theorem for $Π_{1}^{1}$ -sets of positive measure to sets computable and semi-computable relative to S. Note that computing with S represents a natural transfinite extension of $Π_{1}^{1} {-CA}_{0}$ , up to the first recursively inaccessible ordinal. In Section 1.3 we give reference to a non-trivial application of the basis theorem, and in Section 3 we provide a new application, i.e. the basis theorem is not mere theory. Finally, we discuss similar generalisations for infinite time Turing machines, originally due to Carl and Schlicht [2].

Secondly, hyperarithmetical sets come in two forms, as sets of integers and as sets of sets (or sets of functions), i.e. as objects of order 2 and as objects of order 3. An important aspect is that sets of the second kind can be coded by objects of the first kind, and one aspect of measure theoretic uniformity is that the measure theory of objects of the second kind can be reduced to properties of the codes, staying within the hyperarithmetical fragment of second-order arithmetic. Another aspect is that while there may be a mismatch between the complexity of a hyperarithmetical set and that of its elements, this mismatch disappears for hyperarithmetical sets of positive measure.

The main result of the paper will broaden the above picture to the class of C-sets as defined by Selivanovskij in [18] and the related class of sets computable in the Suslin functional. [18] is written in Russian, with a résumé in French, and we give the French reference.

Thirdly, as to the technical framework, some of our arguments are well-known from the classical literature on Descriptive Set Theory, but the intention is to make the note reasonably self-contained. For arguments and results on measure-theoretic uniformity, we refer to Sacks [17], and not to the original papers. We refer to Kechris [7] for some results in Descriptive Set Theory. Finally, there are several sources for the definitions of admissible ordinals, e.g. Sacks [17, Chapter VII] and the recent Normann [11, §2]

Finally, as to content, in Section 1.2 we state the known results on measure theoretic uniformity and the proposed generalisation. In Section 1.3 we place our results in a wider context, and discuss why Kleene computability is an appropriate notion of higher-order computability (in this wider context). In Remark 1.5 we provide a brief account of research related to the contents of Sections 2 and 3. In Section 2 we introduce the C-sets of Selivanovskij and show how the measure theory of those sets is captured by S-computability. The key step will be to give a natural coding of the C-sets and then, given a code for a C-set A, use S to compute codes for Borel-sets $B_{1} \subseteq A \subseteq B_{2}$ approximating A in measure. In Section 3 we show how the termination predicate for computing relative to S can be approximated by C-sets, and we prove our main results for computability relative to S in Proposition 1.4. As an application, we also provide a selection theorem for C-sets. In Section 4 we place our results in a broader picture, namely in the framework of infinite time Turing machines. In Section 5 we round off with discussions and acknowledgements.

1.2. Definitions and main results

1.2.1. Some definitions from computability theory

First of all, Kleene’s functional $^{2} E$ is defined as follows for any $f : N \to N$ : $\begin{matrix} ^{2} E (f) : = \{\begin{matrix} 0 & if (\forall n \in N) (f (n) = 0) \\ 1 & if (\exists n \in N) (f (n) > 0) . \end{matrix} \end{matrix}$ For now, we just point out that hyperarithmetic theory can be formulated via computations relative to $^{2} E$ .

Secondly, the Suslin functional S is the functional of pure type two defined as follows for any $g : N \to N$ : $\begin{matrix} S (g) : = \{\begin{matrix} 0 & if (\exists f \in N^{N}) (\forall n \in N) (g (\bar{f} (n)) = 0) \\ 1 & if (\forall f \in N^{N}) (\exists n \in N) (g (\bar{f} (n)) > 0) . \end{matrix} \end{matrix}$ The Suslin functional is computationally equivalent to the hyperjump, and is closely related to the $Π_{1}^{1}$ -comprehension axiom from [20]. At the same time, the Suslin functional is the characteristic function of a complete $Π_{1}^{1}$ -set on $N^{N}$ and the functional version of the Suslin operator, see Section 2.1.

Thirdly, Kleene has introduced in [8] a notion of higher-order computation via his schemes S1–S9, see e.g. [10, Section 5.1] or [11, §3] for recent formulations. The Kleene schemes define a relation ${e} (\vec{Φ}) = n$ by transfinite recursion, where Φ is a finite sequence of functionals of pure type at any level. In this note, we will only consider input sequences $\vec{Φ}$ where all but at most one $Φ_{i}$ are of type 0 or 1, and where any higher-order input F will be of type two, mainly $F =^{2} E$ or $F = S$ . For the sake of notational simplicity, we base ourselves on this simplified definition, where we also omit the redundant scheme S5 for primitive recursion. We will refer to this definition in Section 3.

Definition 1.1.
Using transfinite recursion, we define the relation ${e} (F, \vec{f}, \vec{a}) = c$ , where F is of type $N^{N} \to N$ , $\vec{f} = (f_{1}, \dots, f_{n})$ is a sequence from $N^{N}$ , $\vec{a} = (a_{1}, \dots, a_{k})$ is a sequence from $N$ and $c \in N$ , as follows.
If $e = ⟨ 1 ⟩$ , then ${e} (F, \vec{f}, \vec{a}) = a_{1} + 1$ .

If $e = ⟨ 2, q ⟩$ , then ${e} (F, \vec{f}, \vec{a}) = q$ .

If $e = ⟨ 3 ⟩$ , then ${e} (F, \vec{f}, \vec{a}) = a_{1}$ .

If $e = ⟨ 4, e_{1}, e_{2} ⟩$ , ${e_{2}} (F, \vec{f}, \vec{a}) = b$ and ${e_{1}} (F, \vec{f}, b, \vec{a}) = c$ , then ${e} (F, \vec{f}, \vec{a}) = c$ .

If $e = ⟨ e_{1}, τ_{1}, τ_{2} ⟩$ , where $τ_{1}$ and $τ_{2}$ are permutations of (the index sets for) the input sequences $\vec{f}$ and $\vec{a}$ , then ${e} (F, \vec{f}, \vec{a}) = {e_{1}} (F, {\vec{f}}_{τ_{1}}, {\vec{a}}_{τ_{2}})$ .

If $e = ⟨ 7 ⟩$ , then ${e} (F, \vec{f}, \vec{a}) = f_{1} (a_{1})$ .

If $e = ⟨ 8, e_{1} ⟩$ , then ${e} (F, \vec{f}, \vec{a}) = F (λ b . {e_{1}} (F, \vec{f}, b, \vec{a}))$ when defined.

If $e = ⟨ 9 ⟩$ then ${e} (F, \vec{f}, d, \vec{a}) = c$ if ${d} (F, \vec{f}, \vec{a}) = c$ .

On purpose, we omitted S5, the scheme for primitive recursion. For S8, we require that ${e_{1}} (F, \vec{f}, b, \vec{a})$ has a value for all $b \in N$ , which means that an entry ${e} (F, \vec{f}, \vec{a}) = c$ in the inductively defined set of computations may have infinitely many predecessors. We introduce non-terminating computations with S9, since we do not provide a value if d does not code a scheme. The scheme S9 suffices to prove the recursion theorem for Kleene-computations, and this is why both primitive recursion and the μ-operator are redundant. Now, each computation will have a rank, the countable ordinal where the computation is added in this inductive process.

Fourth, the computability theory of $^{2} E$ is well-behaved and well-treated in the literature. We survey what we need below, and use Sacks [17] as our reference text for this brief survey. For all results but one, Part A of [17] will do. The monotone inductive definition of ${(e, \vec{a}, c) : {e} (^{2} E, \vec{f}, \vec{a}) = c}$ is arithmetical in $\vec{f}$ , and thus the relation ${e} (^{2} E, \vec{f}, \vec{a}) = c$ will be a $Π_{1}^{1}$ -relation by [17, III.8]. Thus, every set $A \subset N^{N}$ computable in $^{2} E$ is $Δ_{1}^{1}$ , which is equivalent to being hyperarithmetical, and will have a hyperarithmetical code as a Borel set by [17, II].

Fifth, we use the standard definition of $ω_{1}^{CK}$ as the first non-computable ordinal and $ω_{1}^{f}$ as the first ordinal that is not computable in the function f. The ordinal $ω_{1}^{CK}$ is the least ordinal $α > ω$ that is admissible in the sense that $L_{α}$ satisfies the Kripke–Platek axioms, and this characterisation relativises to any function f.

Finally, we let $C = {0, 1}^{N}$ be Cantor space and we let m be the standard product measure on C. Remark 1.2.
We may view the elements of C as binary expansions of reals in $[0, 1]$ , a representation that is one-to-one except at countably many points. With this view, m is equivalent to the Lebesgue-measure λ on $[0, 1]$ , and we may freely transfer results from one measure to the other.

1.2.2. Measure-theoretic uniformity and its generalisation

First of all, we consider the following results independently due to Tanaka [22] and Sacks [16]. As explained in the previous section, the aim of this paper is to establish the generalisation of these results to ‘the next level’ as embodied by $Π_{1}^{1} {-CA}_{0}$ , i.e. we establish measure-theoretic uniformity relative to S. Note that a Borel set is the same as a set hyperarithmetical in some function f, which is the same as a set computable in $^{2} E$ and some function f.

Proposition 1.3 (Measure-theoretic uniformity relative to $^{2} E$ ).

If $A \subseteq C$ is a Borel set, then $m (A)$ is hyperarithmetical uniformly in any Borel-code for A. This is a corollary of [17, Theorem IV.1.3].

We have $m ({f \in C : ω_{1}^{f} = ω_{1}^{CK}}) = 1$ [17, Corollary IV.1.6].

If $A \subseteq C$ is hyperarithmetical and $m (A) > 0$ , then there is a hyperarithmetical $f \in A$ [17, Theorem IV.2.2].

An important consequence of Proposition 1.3.c), proved via Gandy selection, is that if $A \subseteq C$ is hyperarithmetical with $m (A) > 0$ , then we can compute an element $f \in A$ uniformly from a Kleene-index for A and $^{2} E$ . By contrast, there are arithmetical sets with no hyperarithmetical elements. Gandy selection is proved in a more general form as in [17, Theorem X.4.1] and was originally proved in [3]. We will discuss an application of this in Section 1.3, an application that was the original motivation for the aforementioned generalisation.

Secondly, the technical results to be proved in Section 3 are as follows.

Proposition 1.4 (Measure-theoretic uniformity relative to S).

If $A \subset C$ is computable in S , then $m (A)$ is computable in S . This relativises to all functions of type 1.

The set of $f \in C$ such that all ordinals computable in f and S are computable just in S has measure 1. This set is the set of f such that the least recursively inaccessible ordinal is recursively inaccessible relative to f. We denote this result as $m ({f \in N^{N} : ω_{1}^{f, S} = ω_{1}^{S}}) = 1$ .

If $A \subseteq C$ is computable in S and $m (A) > 0$ , then A contains an element computable in S .

The conditions of the theorem are really necessary: there is in fact a subset of C computable in S with one single element, and this element is not computable in S. Thus the assumption that the measure be positive is essential for the basis theorem. The set in question is defined as the set of least fixed points of the monotone inductive definition of the set of computations relative to S. Moreover, it is possible to construct a nonempty $Π_{1}^{1}$ -set $X \subseteq C$ which is computable in S but has no element even computable by an infinite time Turing machine, the set of codes for executions of the universal machine until the full behaviour of all machines is shown through termination or cyclic computations, see e.g. the discussion in [24, p. 502].

Finally, it is well-known that all subsets of $N^{N}$ (semi-)computable in S, are $Δ_{2}^{1}$ , and since this is provable in ZFC, all such sets are measurable for any completed Borel-measure on $N^{N}$ or on closed subsets thereof. Thus, the measurability of the sets we define will not be an issue. This neat result is due to R. Solovay (unpublished) based on a forcing argument from [21].

1.3. The bigger picture

In this section we place our results in a wider context by providing a brief survey of the project this research is a part of. Readers only interested in the new results of the paper may skip this part.

This paper is a spin-off from a joint project with Sam Sanders. In this project, we combine methods from proof theory and higher computability theory to analyse the logical and computational complexity of classical theorems in analysis concerning the uncountable. One aspect is to investigate the relative computational complexity of realisers for (higher-order) theorems of ordinary mathematics, like e.g. Heine-Borel compactness for uncountable covers.

For instance, the input for a realiser of the Heine-Borel theorem is a map sending each $x \in [0, 1]$ to a neighbourhood of itself and the output will be a finite sub-covering. An input for a realiser of the Vitali covering theorem is a map sending $x \in R$ and $k \in N$ to a neighbourhood of x of radius bounded by $2^{- k}$ . The output will be a set of pairwise disjoint neighbourhoods in the range of the input covering almost all reals. In [13, Theorem 3.29], it is (indirectly) proved that there is a realiser Λ of this kind for the Vitali Covering Theorem such that no realiser Θ for the Heine-Borel theorem is Kleene-computable in Λ and $^{2} E$ . As it happens, Proposition 1.3 of this paper is used in the proof, using both the fact that one can compute the measure of a Borel set from a code for it and $^{2} E$ and that one can effectively, in the sense of $^{2} E$ -computability, select an element when the Borel-set has positive measure.

Later, $^{2} E$ was replaced by S, yielding [15, Theorem 4.17]. The latter result provides computational evidence for the claim that $Π_{1}^{1}$ -comprehension does not suffice to obtain ‘full’ compactness from compactness ‘up to measure’. In contrast, the combination of $Π_{1}^{1}$ -comprehension and (a realiser for) the Heine-Borel theorem yields the full strength of non-monotone inductive definitions of subsets of $N$ by [12, Theorem 1]. We note that Theorem 3.9 of this paper, and its corollaries, are essential for the proof of the theorem from [15]. We refer to the Introduction in [14] for a discussion of the foundational interest of such realisers.

As to alternative approaches, there is no Turing thesis for higher-order computability, and Kleene’s definition is just one possible generalisation of classical (Turing) computability to computability relative to higher-order objects. Alternatively, one could consider the weaker typed λ-calculus that can be relativized by the use of constants, or the stronger concept of infinite time Turing machines, ITTMs for short. We will take a closer look at ITTMs in Section 4. For the purpose of our foundational project, the ITTM-approach is too strong as many of the type 3 realisers studied in our project can be obtained using non-monotone induction, and thus computed by ITTMs. Indeed, Welch describes in [25] how to compute functionals of type 3 using ITTMs. Thus, Kleene-computability relative to some or all functionals of type 2 is adequate for proving negative results as in $\begin{matrix} Objects of kind A can not be uniformly computed from objects of kind B, \end{matrix}$ since this is the strongest natural concept for computing with higher-order objects for which we have hitherto managed to prove most negative results. Positive results on relative computability in this project require for the most part only typed λ-calculus or a small fragment of Gödel’s system T of higher-order primitive recursion.

Remark 1.5 (Related research).

First of all, the concept of C-set has been studied for its own sake, in the original paper [18], and in e.g. Shreve [19] and Burgess [1]. What is new in this paper is the connection between the measure theory of C-sets and computability relative to S.

Secondly, Hinman describes in [6], via a hierarchy for the set of subsets of $N$ computable in S, an effective version of the C-sets, in much the same way that the hyperarithmetical subsets of $N$ form an effective version of the Borel sets. We will see that there are subsets of C that are computable in S but that are not C-sets. In this way, the C-sets form a proper subclass of the sets computable in S and some function, in contrast to how computability in $^{2} E$ corresponds to the Borel-sets.

Thirdly, Burgess [1, §3] introduces the C-sets in a similar way as we do in Section 2, and proves a number of selection theorems for C-sets based on topological properties ([1, §8]). Our basis theorem, Proposition 1.4, item c), in conjunction with the Gandy selection theorem, leads to a similar selection theorem based on measure theoretic properties, namely Theorem 3.13. Our methods are quite different from those used by Burgess in [1].

Fourth, Carl and Schlicht proved the analogue of Proposition 1.4 for infinite time Turing machine computability in [2, Theorem 4.5]. In Section 4 we will look closer at how their results connect to ours.

2. The hierarchy of C-sets

We introduce the hierarchy of C-sets and prove some measure and computability theoretic facts.

2.1. Basic facts about C-sets

In this section, we define the notion of ‘C-set’, first introduced by Selivanovskij in [18], and prove elementary facts.

First of all, let SEQ be the set of finite sequences s of integers $⟨ s_{0}, \dots, s_{lh (s) - 1} ⟩$ where $lh (s)$ is the length of the sequence. We use s, t for elements of SEQ, and we identify them with the corresponding sequence numbers $⟨ s ⟩$ and $⟨ t ⟩$ . We use the standard notation $\bar{f} (n) = ⟨ f (0), \dots, f (n - 1) ⟩$ . We let $s ⪯ t$ if $lh (s) ⩽ lh (t)$ and $s_{i} = t_{i}$ for $i < lh (s)$ . We let P, Q range over subsets of X, where X may be the Cantor space C, the Baire space $N^{N}$ , or any product of such spaces, possibly with $N$ as extra factors.

Secondly, a Suslin scheme P on X is a map $s \mapsto P_{s}$ from SEQ to the powerset of X. Given a Suslin scheme P, we define $A (P) = ⋃_{f \in N^{N}} ⋂_{n \in N} P_{\bar{f} (n)}$ . The functional A is known as the Suslin operator.

Thirdly, by simultaneous recursion on the countable ordinal α, we now define two classes $Σ_{α}$ and $Π_{α}$ of subsets of X. The C-sets inhabit the ‘limit’ of this recursion process.

Definition 2.1 (C-sets).

$Σ_{0}$ consists of all sets that are both closed and open.

For $α > 0$ , $Σ_{α}$ is the set of $A (P)$ where P is a Suslin scheme with all $P_{s}$ in $\begin{matrix} ⋃ {Π_{β} : β < α} . \end{matrix}$

$Π_{α} = {X ∖ P : P \in Σ_{α}}$ .

Let

Σ_{ω_{1}}

be the union of all

Σ_{α}

for countable α. The C-sets are exactly the elements of

Σ_{ω_{1}}

It is easy to see that $Σ_{α} \subseteq Σ_{γ}$ and $Π_{α} \subseteq Π_{γ}$ when $α ⩽ γ$ , and that $Π_{α} \subseteq Σ_{α + 1}$ for all α. Thus the complement of a set in $Σ_{ω_{1}}$ will itself be in $Σ_{ω_{1}}$ .

We shall need the following lemmas pertaining to the previous definitions.

Lemma 2.2.
For each $α > 0$ , $Σ_{α}$ is closed under the application of A to Suslin schemes with sets from $Σ_{α}$ , and consequently the class of C-sets is closed under the application of A .
Proof.
The proof is classical, and not too difficult. See e.g. Proposition (25.6) in [7]. □

In the same way we use well-founded trees to code Borel sets, we can use well-founded trees, or rather function codes for them, to code elements in $Σ_{ω_{1}}$ . We do not provide the tedious details: it is easy to distinguish between codes for $Σ_{0}$ , codes for Π-sets, and codes for Σ-sets; when a tree codes a set, then we can extract codes for all the building blocks. The ordinal rank of the tree coded by a function f will determine if f is a $Σ_{α}$ -code or a $Π_{α}$ -code. The set of these codes will be a complete $Π_{1}^{1}$ -set.
Remark 2.3.
If we consider the Borel sets as inductively defined from the clopen sets through the processes of countable unions and taking complements, each code for a Borel set can be viewed as a code for a C-set as well. Instead of interpreting a countable branching as representing a union, we interpret it via the use of the aforementioned Suslin operator A. However, we must distinguish between the two interpretations of a single code.
Lemma 2.4.
For each ordinal α, the sets $Σ_{α}$ and $Π_{α}$ are closed under finite unions and intersections. Moreover, given a finite list of $Σ_{α}$ -codes or of $Π_{α}$ -codes, we can compute the codes for the respective unions and intersections in the given classes uniformly in $^{2} E$ .
Proof.
By De Morgan’s laws, it suffices to prove the lemma for $Σ_{α}$ . Closure under finite unions is trivial. Closure under finite intersections requires a combinatorial effort, but essentially is proved translating the quantifier change $\begin{matrix} \forall k ⩽ m \exists f \forall n R (k, f, n) \mapsto \exists f \forall k ⩽ m \forall n R (k, {(f)}_{k}, n) \end{matrix}$ to a manipulation of Suslin schemes. □
Definition 2.5.
A Suslin scheme P is regular if $s ⪯ t \Rightarrow P_{t} \subseteq P_{s}$ for all s and t in SEQ.

Every Suslin scheme is equivalent to a regular one in the sense that it defines the same set, see e.g. [7, Exercise 25.5]. By Lemma 2.4 we can ‘reorganise’ a Suslin scheme to a regular one without increasing the rank. Using the recursion theorem for $^{2} E$ , we may even transform a code for a well-founded tree of Suslin schemes to a code for an equivalent tree of regular Suslin schemes, using a $^{2} E$ -algorithm. In the sequal, we therefore assume that all our Suslin schemes are regular. Moreover, for $α > 0$ , we can use the arguments of Lemma 2.4 to show that the classes of Σ and Π-sets are closed under countable unions and intersections, possibly at the cost of increasing the rank by 1. We can also find codes for the intersection and the union from a sequence of codes for such sets uniformly computable in $^{2} E$ . However, it is only for finite unions and intersections that we can preserve the rank.

We end this section with an application of the recursion theorem for S:
Lemma 2.6.
Each C-set A is uniformly computable in S and any of its codes. Moreover, if A has code g, then the ordinal ranks of the computations deciding if $f \in A$ from S and g will be strictly bounded below $ω_{1}^{S, g}$

Since the set of codes is computable in S as well, we see, by a standard diagonal argument, that there will be sets computable in S that are not C-sets.
2.2. Measurability

In this section, we restrict our attention to $X = C$ , the Cantor space. As stated in the introduction, all sets semi-computable in S will be measurable. In this section, we show that if f is a code for the C-set $P [f]$ , then we can compute $m (P [f])$ from f and S in the sense of computing its Dedekind cut.

For $f, g \in N^{N}$ , we let ‘ $f ⩽ g$ ’ mean that f is bounded by g in the pointwise ordering. Likewise, for $s \in SEQ$ and $f \in N^{N}$ , ‘ $s ⩽ f$ ’ means that $s_{i} ⩽ f (i)$ whenever for $i < lh (s)$ .

Definition 2.7.
Let P be a (regular) Suslin scheme and let $f \in N^{N}$ . Define $A_{f} (P) : = ⋃_{g ⩽ f} ⋂_{n \in N} P_{\bar{g} (n)}$ .
Lemma 2.8.
With the notation from Definition 2.7 , we have $A_{f} (P) = ⋂_{n \in N} ⋃_{lh (s) = n, s ⩽ f} P_{s}$ .
Proof.
The proof is by an application of the Weak König’s Lemma, also called WKL in [20], and is left for the reader. We do need that the Suslin scheme is regular. □

In the next classical lemma we use that we are only dealing with sets that are measurable: Lemma 2.9.
For a Suslin scheme P , we have $m (A (P)) = sup {m (A_{f} (P)) : f \in N^{N}}$ .
Proof.
Let $m (A (P)) = a$ . Let $ϵ > 0$ . By recursion on k, we find $f (k)$ such that the union of all $⋂_{n \in N} P_{\bar{g} (n)}$ , where $g (i) ⩽ f (i)$ for $i ⩽ k$ , has measure larger than $a - ϵ (1 - 2^{k + 1})$ . Then $m (A_{f} (P)) ⩾ a - ϵ$ , which proves the lemma. □
Theorem 2.10.
For a code f of the Σ-set or Π-set $P [f]$ , the measure $m (P [f])$ is computable in S and f, uniformly in f.
Proof.
We use the recursion theorem and argue by induction on the ordinal complexity of the code. The only non-trivial case is when $P [f] = A (P)$ where each $P_{s}$ is of the form $P [f_{s}]$ . As an induction hypothesis we assume, with reference to Lemma 2.4, that for any finite Boolean combination of the sets $P [f_{s}]$ we can compute the measure using S. We can effectively enumerate all finite Boolean combinations of the sets $P [f_{s}]$ indexed by the finite sequences s. Thus there will be a function $h = {⟨ h_{a} ⟩}_{a \in N}$ , computable in S and f, such that $h_{a}$ gives us (the code for) the measure of the corresponding Boolean combination of the sets $P [f_{s}]$ . Using lemmas 2.8 and 2.9 we see that the measure of $A (P [f])$ , still seen as a Dedekind cut, will be $Σ_{1}^{1}$ in h, and thus computable in S and f itself. □

2.3. A basis theorem

It is well-known that any measurable set can be approximated from the inside and from the outside by Borel sets with the same measure. In this section, we show that we can find such sets for $P [f]$ uniformly in f and S. This is a crucial step in showing that a C-set A of positive measure contains an element computable in S and a code for A.

First of all, we establish the following lemma and theorem.

Lemma 2.11.
Let P and Q be two Suslin schemes of measurable sets such that $m (P_{s} Δ Q_{s}) = 0$ for all finite sequences s, where Δ is the symmetric difference. Then $m (A (P)) = m (A (Q))$ .
Proof.
Since the measure of a Boolean manipulation of countably many sets does not change through perturbations of the sets of measure 0, we can use Lemmas 2.8 and 2.9. □
Theorem 2.12.
Let f be a code for a Σ-set or Π-set $P [f]$ . Then uniformly computable in f and S we can find Borel codes for sets $B_{\subseteq} [f]$ and $B_{\supseteq} [f]$ such that $B_{\subseteq} [f] \subseteq P [f] \subseteq B_{\supseteq} [f]$ and $m (B_{\subseteq} [f]) = m (B_{\supseteq} [f])$ .
Proof.
Like before, we use the recursion theorem and induction on the rank; like before, the only non-trivial case is an application of the Suslin operator A.

In this way, let $P [f] = A (P)$ where $P_{s} = P [f_{s}]$ for each $s \in SEQ$ , and let $B_{\subseteq} [f_{s}]$ and $B_{\supseteq} [f_{s}]$ satisfy the induction hypothesis for each s. Then we can find a g computable in f and S such that g is the join of the Borel-codes for all $B_{\subseteq} [f_{s}]$ and $B_{\supseteq} [f_{s}]$ . Now consider the Suslin schemes $B_{\subseteq}$ and $B_{\supseteq}$ given by the sets $B_{\subseteq} [f_{s}]$ and $B_{\supseteq} [f_{s}]$ respectively. Then both $A (B_{\subseteq})$ and $A (B_{\supseteq})$ are $Σ_{1}^{1}$ -sets relative to g, they have the same measure as $A (P)$ by Lemma 2.11, and they are a subset, resp. superset of the same.

For $a = m (A (P))$ and $n \in N$ , we can use the Kleene basis theorem (see e.g. [17, Theorem III 1.3]) relative to g to find $f_{n}$ such that $m (A_{f_{n}} (B_{\subseteq})) > a - 2^{n}$ . The sequence ${f_{n}}_{n \in N}$ is computable in g and S, and from this sequence and g we can compute a Borel-code for $⋃_{n \in N} A_{f_{n}} (B_{\subseteq})$ , a set with measure a. We use this set as $B_{\subseteq} [f]$ .

In order to find $B_{\supseteq} [f]$ , we use the relativised version of the theorem saying that if a $Π_{1}^{1}$ -set D has a hyperarithmetical measure, there will be a $Δ_{1}^{1}$ -subset with the same measure (see [17, Chapter IV]). Thus, there will be a Borel-code hyperarithmetical in g for a subset E of the set $C ∖ A (B_{\supseteq})$ with the same measure as $C ∖ A (B_{\supseteq})$ . We use the complement of E as our $B_{\supseteq} [f]$ . □
Corollary 2.13.
Let f be a code for a Σ-set or Π-set $P [f]$ , and assume that $m (P [f]) > 0$ . Then $P [f]$ contains an element computable in f and S.
Proof.
This follows from Theorem 2.12 and the Tanaka-Sacks basis theorem, see Proposition 1.3, item c. □

In the sequel we will need the following uniform version of Theorem 2.12. The proof is left for the reader. Theorem 2.14.
Let $A \subset C \times C$ be a C-set with code g. Then there are S , g computable functions F and G from C to $N^{N}$ computing, for each $f \in C$ , Borel-codes for inner and outer approximations-in-measure to ${h \in C : (f, h) \in A}$ such that the ordinal ranks of the computations of $F (f)$ and $G (f)$ are uniformly and strictly bounded by $ω_{1}^{S, g}$ .

3. Computing with the Suslin-functional

3.1. Terminating computations and C-sets

We establish that computations in S terminating at a countable level give rise to C-sets. We refer to Definition 1.1 for our inerpretation of the Kleene schemes S1–S9.

As to context, it is well-known that if F is a functional of type 2 computable in $^{2} E$ , then the ordinal ranks of the computations of $F (f)$ , when f varies over $N^{N}$ , will be bounded by a computable ordinal. However, S does not share this nice behaviour: the set WO of codes for well-orderings is computable in S, and for each $f \in WO$ we can (uniformly and easily) devise a terminating computation that lasts at least as long as the ordinal rank of f. However, we will see that the C-sets capture computations in S at a countable level much in the same way the Borel sets capture computations relative to $^{2} E$ .

Definition 3.1.
Let $Ω_{S}$ be the set of sequences $⟨ e, \vec{f}, \vec{a}, b ⟩$ such that ${e} (S, \vec{f}, \vec{a}) = b$ and let $‖ \cdot ‖_{Ω_{S}}$ be the corresponding ordinal rank. We let all arguments come in the order Suslin, functions, integers, as in Definition 1.1.
Theorem 3.2.
For a countable ordinal α and, e, k, $\vec{a}$ and b from $N$ , ${\vec{f} \in {(N^{N})}^{k} : ‖ ⟨ e, \vec{f}, \vec{a}, b ⟩ ‖_{Ω_{S}} < α}$ is a C-set.
Proof.
We prove this by induction on α. In the case $α = 0$ , all sets in question are empty, so this case is trivial. When α is a limit ordinal, all sets in question are countable unions of C-sets by the induction hypothesis, so again, this case is trivial. We are left with the simple case when $α = β + 1$ , where we assume that the theorem holds for β.

There are now nine sub-cases: one for each of S1–S4, S6–S9 and one for the otherwise case. For the cases S1–S3, S7, the initial computations, we do not even need the induction hypothesis, and for the otherwise-case, all sets in question are empty. Case S9, the scheme of enumeration, and case S6, the scheme of permutation, follow by direct applications of the induction hypothesis, since there is only one immediate subcomputation in each case. This leaves us with S4 (composition) and S8 (application of S), as follows. Recall that ‘≃’ means that both sides are undefined or both sides are defined and equal.

For the case S4 (composition), let $e = ⟨ 4, e_{1}, e_{2} ⟩$ be such that ${e} (S, \vec{f}, \vec{a}) ≃ {e_{1}} (S, {e_{2}} (S, \vec{f}, \vec{a}), \vec{f}, \vec{a})$ . We obtain the required results from the induction hypothesis and that C-sets are closed under countable unions, since $\begin{matrix} {‖ ⟨ e, \vec{f}, \vec{a}, b ⟩ ‖}_{Ω_{S}} < α \leftrightarrow \exists c \in N [{‖ ⟨ e_{2}, \vec{f}, \vec{a}, c ⟩ ‖}_{Ω_{S}} < β \land {‖ ⟨ e_{1}, \vec{f}, c, \vec{a}, b ⟩ ‖}_{Ω_{S}} < β] . \end{matrix}$ For the case S8 (application of S), let ⊥ mean ‘undefined’ and let $\begin{matrix} {e} (S, \vec{f}, \vec{a}) = \{\begin{matrix} 0 & if (\exists f \in N^{N}) (\forall n \in N) ({e_{1}} (S, \vec{f}, \bar{f} (n), \vec{a}) = 0) \\ 1 & if (\forall f \in N^{N}) (\exists n \in N) ({e_{1}} (S, \vec{f}, \bar{f} (n), \vec{a}) > 0) \\ ⊥ & otherwise . \end{matrix} \end{matrix}$ Define R as the C-set $R = ⋂_{s \in SEQ} ⋃_{c \in N} {\vec{f} : ‖ ⟨ e, \vec{f}, s, \vec{a}, c ⟩ ‖_{Ω_{S}} < β}$ , i.e. the set of $\vec{f}$ for which we apply S to a total function at level β. We will consider two Suslin schemes P and Q where $\begin{matrix} P_{s} : = R \cap {\vec{f} : {‖ ⟨ e_{1}, \vec{f}, s, \vec{a}, 0 ⟩ ‖}_{Ω_{S}} < β} and Q_{s} : = R ∖ ⋃_{c > 0} {\vec{f} : ‖ ⟨ e_{1}, \vec{f}, s, \vec{f}, c ⟩ ‖ < β} . \end{matrix}$ Then we have that $\begin{matrix} A (P) = {\vec{f} : {‖ ⟨ e, \vec{f}, \vec{a}, 0 ⟩ ‖}_{Ω_{S}} < α} and [R ∖ A (Q)] = {\vec{f} : {‖ ⟨ e, \vec{f}, \vec{a}, 1 ⟩ ‖}_{Ω_{S}} < α} . \end{matrix}$ In this case, for $b \neq 0, 1$ , there will be no $\vec{f}$ such that $‖ ⟨ e, \vec{f}, \vec{a}, b ⟩ ‖_{Ω_{S}} < α$ since S is ${0, 1}$ -valued, so the set in question will be empty, and we are through. □
Remark 3.3.
If we have an ordinal code h for α in the above proof, then a code for the C-set constructed will be computable in h and $^{2} E$ , uniformly in h.

3.2. Measure-theoretical uniformity for the Suslin functional

In this section, we adjust arguments from [17] in order to ‘relativise to S the result that almost all reals are hyperarithmetically low. This will be done via a series of lemmas leading up to Theorem 3.9.

As to representation, the elements of the structure $L_{ω_{1}^{S}} [f]$ can be described as the interpretations $t^{f}$ of terms $t = t (f)$ where f is a constant that in each case is interpreted as f. The terms t will be coded by elements in $L_{ω_{1}^{S}}$ , and the interpretation $t^{f}$ will be in $L_{ω_{1}^{S}} [f]$ .

Remark 3.4.
In our coding, we can replace $ω_{1}^{S}$ with any ordinal α that is admissible, or a limit of admissibles. Indeed, employing a standard projection of the ordinals onto $L [f]$ , using a Gödel-numbering with an extra number for f will do. See e.g. [9, Chapter V, §1] for a precise way to do this. There is no need to introduce forcing-related concepts for our applications.

With the above coding, any $Δ_{0}$ -formula of $L_{ω_{1}^{S}}$ , with free variables x and X for numbers and sets, will then be of the form $ϕ (x, X, t_{1}, \dots, t_{k})$ , where ϕ has bounded quantifiers only. If $ϕ (t_{1}, \dots, t_{k})$ is a $Δ_{0}$ -formula and $t_{1}, \dots, t_{k} \in L_{β}$ for $β < ω_{1}^{S}$ , then ${f : L_{β} [f] ⊧ ϕ}$ will be a Borel-set with a code uniformly $^{2} E$ -computable in codes for β and $t_{1}, \dots, t_{k}$ , and thus with a measure uniformly $^{2} E$ -computable in these codes. Since the codes can be chosen to be S-computable, the measure will be S-computable.
Lemma 3.5 (Push-down lemma).

Let $0 ⩽ r ⩽ 1$ , and let $ϕ (x, X, t_{1}, \dots, t_{k})$ be a $Δ_{0}$ -formula where x and X are free variables and assume that $\begin{matrix} m ({f \in N^{N} : (\forall x \in N) (\exists X \in L_{ω_{1}^{S}} [f]) ϕ (x, X, t_{1}^{f}, \dots, t_{k}^{f})}) ⩾ r . \end{matrix}$ Then $\begin{matrix} m ({f \in N^{N} : (\exists β < ω_{1}^{S}) (\forall x \in N \exists X \in L_{β} [f]) ϕ (x, X, t_{1}^{f}, \dots, t_{k}^{f})}) ⩾ r . \end{matrix}$

Proof.
It suffices to prove this for rational numbers r. We have that $\begin{matrix} {f : (\forall x \in N) (\exists X \in L_{ω_{1}^{S}} [f]) ϕ (x, X, t_{1}^{f}, \dots, t_{k}^{f})} = ⋂_{n \in N} {f : (\forall x ⩽ n) (\exists X \in L_{ω_{1}^{S}} [f]) ϕ (x, X, t_{1}^{f}, \dots, t_{k}^{f})} . \end{matrix}$ For each $n \in N$ we then have that $m ({f : \forall x ⩽ n \exists X \in L_{ω_{1}^{S}} [f] ϕ (x, X, t_{1}^{f}, \dots, t_{k}^{f})}) ⩾ r$ , and for each rational $r^{'} < r$ we can find $β_{n, r^{'}} < ω_{1}^{S}$ such that $m ({f : \forall x ⩽ n \exists X \in L_{β_{n, r^{'}}} [f] ϕ (x, X, t_{1}^{f}, \dots, t_{k}^{f})}) > r^{'}$ . We then use Gandy selection for S to find such $β_{n, r^{'}}$ . Since r is rational, we can use the bounding principle in $L_{ω_{1}^{S}}$ and conclude that there is one $β < ω_{1}^{S}$ larger than all the $β_{n, r^{'}}$ . Then $m ({f : \forall x \in N \exists X \in L_{β} [f] ϕ (x, X, t_{1}^{t}, \dots, t_{k}^{t})}) ⩾ r$ as required. □
Remark 3.6.
Lemma 3.7 and Theorem 3.9 below are consequences of Lemma 2.11 in Carl and Schlicht [2]. They work in the context of random reals and forcing. We give proofs without reference to this context.
Lemma 3.7.
The set of $f \in C$ such that $ω_{1}^{S}$ is f-admissible has measure 1.
Proof.
We only need to check $Δ_{0}$ -replacement, since the other Kripke–Platek axioms are trivially satisfied for all f. Since there are only countably many instances of replacement, we only need to verify the lemma for each one of them. By Lemma 3.5, the set of f such that a particular instance of $Δ_{0}$ -replacement fails, will have measure 0. Thus, the set of f for which this axiom holds will have measure 1. □
Lemma 3.8.
There is a well-ordering $(A, ≺)$ of a subset of $N$ of order type $ω_{1}^{S}$ , semicomputable in S , such that for each $a \in A$ , ${⟨ b, c ⟩ : b ≺ c ≺ a}$ is computable in S , uniformly in a.
Proof.
We let A be the set of computation tuples $a = ⟨ e, \vec{a}, b ⟩$ such that ${e} (S, \vec{a}) = b$ with the norm $‖ \cdot ‖$ , and we let $a ≺ a^{'}$ if $‖ a ‖ < ‖ a^{'} ‖$ or if $‖ a ‖ = ‖ a^{'} ‖$ and $a < a^{'}$ . This ordering has the desired properties. □
Theorem 3.9.
The set ${f \in C : ω_{1}^{S} = ω_{1}^{S, f}}$ has measure 1.
Proof.
Let $(A, ≺)$ be as in Lemma 3.8, let $a \in A$ and let $(A_{a}, ≺_{a})$ be the corresponding initial segment of $(A, ≺)$ , coded as the function $f_{a}$ . Then applying a relativized version of Proposition 1.3, b) we have that $\begin{matrix} m ({f : ω_{1}^{f_{a}, f} = ω_{1}^{f_{a}}}) = 1 . \end{matrix}$ Taking the intersection of all these sets and the set from Lemma 3.7, we see that the set of f such that $ω_{1}^{S}$ is both f-admissible and a limit of f-admissibles will have measure 1. □
Corollary 3.10.
Let $F : C \to N$ be computable in S. Then there is an ordinal $α < ω_{1}^{S}$ such that the algorithm for F terminates at an ordinal rank below α on a set of measure 1.
Proof.
Define $F (f) = {e} (S, f)$ . By Theorem 3.9, the set of f such that ${e} (S, f)$ terminates before $ω_{1}^{S}$ has measure 1. Then for all $n \in N$ there is an $α_{n} < ω_{1}^{S}$ such that the set of f where ${e} (S, f)$ terminates before $α_{n}$ has measure $> 1 - 2^{- n}$ . Combining the S-effective version of Theorem 3.2 and Theorem 2.10 we can use Gandy selection for S to compute $α_{n}$ from n. Thus ${α_{n}}_{n \in N}$ is bounded below $ω_{1}^{S}$ , and we are through. □
Corollary 3.11.
Let $A \subseteq C$ be semicomputable in S and with a positive measure. Then A contains an element computable in S .
Proof.
Let A be such that $f \in A \leftrightarrow {e} (S, f) ↓$ . By Theorem 3.9, almost all of these computations terminate at an ordinal level below $ω_{1}^{S}$ . Thus, there is $α < ω_{1}^{S}$ such that the set of f such that ${e} (S, f)$ terminates before α have positive measure. This is a C-set of positive measure and it contains an element computable in S by Corollary 2.13. □
Remark 3.12.
If $A \subseteq C$ is computable in S, we can combine Corollary 3.10, Theorem 2.12, and Theorem 3.2 (with Remark 3.3) to search over $L_{ω_{1}^{S}}$ to find both the measure of A computably in S and the codes for Borel sets $A_{\subseteq} \subseteq A \subseteq A_{\supseteq}$ with the same measure as A.

In [1, §8], Burgess lists a number of selection theorems for C-sets where the selecting function claimed to exist is always C-measurable. As promised in Section 1.1, we obtain a similar result as applications of the above. Theorem 3.13.
Define the set $E_{f} : = {g \in C : (f, g) \in E}$ where $E \subset C \times C = C^{2}$ .
Let $A \subset C^{2}$ be a C-set such that for all $f \in C$ , we have $m (A_{f}) > 0$ . Then there is a C-measurable function $F : C \to C$ such that $(f, F (f)) \in A$ for all $f \in C$ .

Let $B \subset C^{2}$ be computable in S and such that $m (B_{f}) > 0$ for all $f \in C$ . Then there is an S -computable function $G : C \to C$ such that $(f, G (f)) \in B$ for all $f \in C$ .

Proof.
Item b) is a direct consequence of Corollary 3.11 and Gandy selection. To prove item a), we argue uniformly in the C-code for A. For the sake of notational simplicity, we assume that this code is computable in S. By Theorem 2.14 there is a function $H : C \to N^{N}$ computable in S such that for each $f \in C$ , $H (f)$ is a Borel-code for a set $H_{f} \subseteq A_{f}$ with the same measure. We now consider the following two easy computational facts about H.
Each value $H (f)$ is computed with a rank uniformly below $ω_{1}^{S}$ .

The functional S can compute complete $Π_{1}^{1}$ -subsets of $N$ relative to each $H (f)$ in finitely many steps.
Thus, we define $F (f)$ as an element from $H_{f}$ and this procedure can be done (i) computably in S and (ii) uniformly at a bounded level. By Theorem 3.2, $F^{- 1} (X)$ is a C-set whenever X is a basic neighbourhood. Since the Suslin operator commutes with inverse images, the inverse $F^{- 1} (X)$ is a C-set whenever X is a C-set, and F is C-measurable. □
Remark 3.14.
In contrast to Borel-sets, it does not suffice to show that the graph of F is a C-set in order to prove that it is C-measurable.

4. Measure-theoretic uniformity and infinite time Turing machines

Using the above results, we show that the computability theory induced by infinite time Turing machines (ITTMs) satisfies similar properties of measure-theoretic uniformity as for the hyperarithmetical sets (Tanaka-Sacks; see Proposition 1.3) and computability relative to S (Section 3). The key result of this section is already known, namely as [2, Theorem 4.5], where it is proved in the context of random reals and forcing. In this section, we adjust Theorem 3.9 to obtain a generalisation to ITTMs. While not new, our results provide an alternative and more elementary proof that in particular does not make use of forcing.

4.1. Infinite time Turing machines

The notion of ITTM was introduced by Hamkins and Lewis in [4]. An ITTM is like an ordinary Turing machine, with the extra option of continuing working after passing limit ordinals. The notion of ITTM-computability is a strong concept, much stronger than computations relative to S. We refer to [4] or recent surveys like [24, §3] for an introduction to ITTMs and their theory.

What is of interest to us is that an ITTM has three tapes: one input tape where the input may be any binary function $f : N \to {0, 1}$ , a work tape, and an output tape where at each stage ν of the computation there is a function $g_{ν} : N \to {0, 1}$ . An empty input tape also represents the input 0. There are various classes of characteristic functions (or sets) of interest associated with the ITTMs.

Definition 4.1 (ITTM output classes).

A function g is writable if there is an ITTM that halts on input 0 with g on the output tape when halting.

A function g is eventually writable if there is an ITTM with input 0 that after some stage ν will always have g on the output tape. This machine does not have to halt.

A function g is accidentally writable if there is an ITTM with input 0 that have g on its output tape at least once.

An ordinal is clockable if it is the exact length of an ITTM computation with input 0 that halts

Ordinals will, by definition, belong to these classes if they have codes belonging to them. The least ordinal that is not writable is denoted λ, the least one that is not eventually writable is denoted ζ, and the least one that is not even accidentally writable is denoted Σ. They are all countable ordinals and λ is also the least upper bound of the clockable ordinals. The relativized version of this was proved in [23, Theorem 1.1], and will be applied in the proof of Corollary 4.5. We will also need the following results.

Proposition 4.2 (Hamkins–Lewis, Welch).

The above ordinals satisfy $λ < ζ < Σ$ and all three are closed under “the next admissible”-operator.

The triple $(ζ, Σ, λ)$ is the least triple with $λ < ζ < Σ$ in the lexicographical ordering of $ℵ_{1}^{3}$ satisfying $L_{λ} ≺_{Σ_{1}} ζ ≺_{Σ_{2}} Σ$ . Moreover, this result can be relativised to any input $f \in C$ on the input tape.

Proof.
For the first item, we refer to [4, §8] for λ and ζ, and to [23, Corollary 3.4] for Σ. The second item can be found in [23]. We refer to [24, Theorem 3] for further details. □

The key result on measure-theoretic uniformity for ITTMs is now as follows, to be proved in Section 4.2.
Theorem 4.3 ([2], Theorem 4.5).

The set ${f \in C : L_{λ} [f] ≺_{Σ_{1}} L_{ζ} [f] ≺_{Σ_{2}} L_{Σ} [f]}$ has measure one.

We have the following corollaries, also originally due to Carl-Schlicht in [2].

Corollary 4.4.
For almost all $f \in C$ we have that all ordinals writable relative to f will be writable, all ordinals eventually writable relative to f will be eventually writable and all ordinals accidentally writable relative to f will be accidentally writable.
Proof.
This follows from the relativized version of [24, Theorem 3]. □
Corollary 4.5.
Let $X \subseteq C$ be ITTM-semicomputable such that $m (X) > 0$ . Then X contains an element that is ITTM-computable.

4.2. The proof of Theorem 4.3

The proof of Theorem 4.3, to be found below, requires a few concepts and lemmas, as follows.

First of all, we recall the terms t ( $= t^{f}$ ) from Section 3.2 and Remark 3.4. When α is sufficiently closed, which our crucial ordinals λ, ζ and Σ are, each element in $L_{α} [f]$ will be the interpretation $t^{f}$ of a term t in $L_{α}$ , and the map $t \mapsto t^{f}$ is defined by a $Δ_{1}$ transfinite recursion uniformly in f. A full proof of the next lemma requires a tediously detailed definition of the terms t and the map $t \mapsto t^{f}$ , but the essence of the proof is trivial.

Lemma 4.6.
Let $ϕ (x_{0}, \dots x_{k - 1})$ be a $Δ_{0}$ -formula and let $t_{1}, \dots, t_{k - 1}$ be countable terms with codes $g_{1}, \dots, g_{k - 1}$ in $N^{N}$ . Then ${f \in C : ϕ (t_{1}^{f}, \dots, t_{k - 1}^{f})}$ is a Borel set with a Borel code uniformly hyperarithmetical in $g_{1}, \dots, g_{k - 1}$ .
Lemma 4.7.
Let $α \in {λ, ζ, Σ}$ and let $β < α$ . Let $\vec{t}$ be terms for elements in $L_{β} [f]$ and let $Φ (\vec{x})$ be any formula where $\vec{x}$ and $\vec{t}$ are of the same length. For $r \in Q$ , the statement $m ({f \in C : L_{β} [f] ⊧ Φ ({\vec{t}}^{f})}) ⩾ r$ is $Δ_{1}$ over $L_{α}$ in parameters r, $\vec{t}$ and β.
Proof.
By the choice of α, there will be a term t for $L_{β} [f]$ in $L_{α}$ and a code g for this term, also in $L_{α}$ . By the closure properties of α we see that the relation between sets and codes will be $Δ_{1}$ over $L_{α}$ . We then use Lemma 4.6 and Proposition 1.3, a), and our lemma follows. □
Lemma 4.8.
Let $\vec{t} = (t_{0}, \dots, t_{k - 1})$ be terms in $L_{λ}$ , let $ϕ (\vec{x}, y)$ be a $Δ_{0}$ -formula and let $0 ⩽ r ⩽ 1$ . For each ordinal α, let $E_{α} : = {f \in C : (\exists y \in L_{α} [f]) ϕ ({\vec{t}}^{f}, y)}$ . We then have that $m (E_{ζ}) ⩾ r$ implies $m (E_{λ}) ⩾ r$ .
Proof.
Assume that $m (E_{ζ}) ⩾ r$ . It suffices to show that $m (E_{λ}) ⩾ r - ϵ$ for each rational r and each $ϵ > 0$ .

By our assumptions there will be an ordinal $β < ζ$ such that $m (E_{β}) ⩾ r - ϵ$ and by Lemma 4.7 the existence of this β is a $Σ_{1}$ statement with parameters from $L_{λ}$ . Since $L_{λ} ≺_{Σ_{1}} L_{ζ}$ we have a $β < λ$ such that $m (E_{β}) ⩾ r - ϵ$ and this proves the lemma. □

We can replace $(λ, ζ)$ with $(ζ, Σ)$ in this lemma, and by direct application of the two versions we obtain the following.
Lemma 4.9.
The set ${f \in C : L_{λ} [f] ≺_{Σ_{1}} L_{ζ} [f] ≺_{Σ_{1}} L_{Σ} [f]}$ has measure 1.

In order to prove Theorem 4.3 it remains to prove that ${f \in C : L_{ζ} [f] ≺_{Σ_{2}} L_{Σ} [f]})$ has measure 1, and this follows from our final lemma. Lemma 4.10 (Relativisation).

Let ϕ be $Δ_{0}$ , $\vec{t}$ be a list of terms in $L_{ζ}$ and assume that $\begin{matrix} m ({f \in C : L_{Σ} [f] ⊧ (\exists x) (\forall y) ϕ ({\vec{t}}^{f}, x, y)}) ⩾ r . \end{matrix}$ Then the same holds ‘relativised’ as follows: $\begin{matrix} m ({f \in C : (\exists x \in L_{ζ} [f]) (\forall y \in L_{Σ} [f]) ϕ ({\vec{t}}^{f}, x, y)}) ⩾ r . \end{matrix}$

Proof.
We may restrict to rational r. Let $ϵ > 0$ be rational. Let T be the set of terms for elements in $L_{Σ} [f]$ . Then $\begin{matrix} {f \in C : L_{Σ} [f] ⊧ \exists x \forall y ϕ ({\vec{t}}^{f}, x, y)} = ⋃_{t \in T} {f \in C : L_{Σ} [f] ⊧ \forall y ϕ ({\vec{t}}^{f}, t^{f}, y)} . \end{matrix}$ Since T is countable, there will be a finite set ${s_{1}, \dots, s_{n}}$ from T such that $\begin{matrix} m ({f \in C : ⋁_{i = 1}^{n} (\forall y \in L_{Σ} [f]) ϕ ({\vec{t}}^{f}, s_{i}^{f}, y)}) > r - ϵ . \end{matrix}$ Then $L_{Σ}$ will satisfy the following $Σ_{2}$ -formula: $\begin{matrix} (1) & (\exists s_{1}, \dots, s_{n}) (\forall β < Σ) (m ({f \in C : ⋁_{i = 1}^{n} (L_{β} [f] ⊧ \forall y ϕ ({\vec{t}}^{f}, s_{i}^{f}, y))}) > r - ϵ), \end{matrix}$ and thus $L_{ζ}$ will satisfy (1) as well. We now fix $s_{1}, \dots, s_{n}$ in $L_{ζ}$ satisfying (1) and note that the following set ${f \in C : ⋁_{i = 1}^{n} (L_{β} [f] ⊧ \forall y ϕ ({\vec{t}}^{f}, s_{i}^{f}, y))}$ is clearly decreasing with increasing β. Thus, we obtain $\begin{matrix} m (⋂_{β < ζ} {f \in C : ⋁_{i = 1}^{n} (L_{β} [f] ⊧ \forall y ϕ ({\vec{t}}^{f}, s_{i}^{f}, y))}) ⩾ r - ϵ . \end{matrix}$ For each $f \in C$ we have the following equivalence (we only need that ζ is a limit ordinal for this): $\begin{matrix} (\forall β < ζ) [⋁_{i = 1}^{n} (L_{β} [f] ⊧ \forall y ϕ ({\vec{t}}^{f}, s_{i}^{f}, y))] \leftrightarrow ⋁_{i = 1}^{n} (\forall y \in L_{ζ} [f]) ϕ ({\vec{t}}^{f}, s_{i}^{f}, y), \end{matrix}$ Hence, we have $m ({f \in C : \exists x \in L_{ζ} [f] \forall y \in L_{ζ} [f] ϕ ({\vec{t}}^{f}, x, y)}) ⩾ r - ϵ$ . Now, if f is such that $\begin{matrix} L_{ζ} [f] ≺_{Σ_{1}} L_{Σ} [f] and (\exists x \in L_{ζ} [f]) (\forall y \in L_{ζ} [f]) ϕ ({\vec{t}}^{f}, x, y), \end{matrix}$ then $\exists x \in L_{ζ} [f] \forall y \in L_{Σ} [f] ϕ ({\vec{t}}^{f}, x, y)$ , and our claim holds. Since $ϵ > 0$ was arbitrary, the lemma follows. □

5. Conclusions and discussion

The results of this paper illustrate a more general phenomenon, which we formulate as follows. $\begin{matrix} Almost all subsets of N are random, and random sets do not have any particular qualities. \end{matrix}$ We have seen that for almost all $f \in C$ we have that $ω_{1}^{C K} = ω_{1}^{f}$ , $ω_{1}^{S} = ω_{1}^{S, f}$ , $λ = λ^{f}$ , $ζ = ζ^{f}$ and $Σ = Σ^{f}$ using quite elementary methods. By the forcing argument in [21], we even have that if α is a countable ordinal such that $L_{α} ⊧ ZFC$ then $L_{α} [f] ⊧ ZFC$ for almost all f. The paper [2] by Carl and Schlicht broadens this picture in a precise and more general way, using methods that fall outside the scope of this paper.

Footnotes

Acknowledgements

I am grateful to Sam Sanders for involving me in the project that led to this research. I am also grateful to Alexander S. Kechris and Gerald E. Sacks for their brief comments on a preliminary note on the subject, and to the Seminar on Mathematical Logic at the University of Oslo for comments during my presentation there. Sadly, Gerald E. Sacks passed away before the completion of this work.

Furthermore, I am grateful to the two anonymous referees that made valuable comments on the original exposition, including the suggestion by one of them to extend the original results to ITTMs as in Section 4. During the revision of the paper, Sam Sanders made me aware of the paper by Burgess [1], and Philip Welch directed me to the paper by Carl and Schlicht [].

Finally, I am grateful to Sam Sanders for providing useful feedback on the exposition of this paper.

References

J.P.

Burgess, Classical hierarchies from a modern standpoint. Part I. C-sets, Fundam. Math. 115 (1983), 81–95. doi:10.4064/fm-115-2-81-95.

Carl and

Schlicht, Randomness via infinite computation and effective descriptive set theory, J. Symb. Log. 83(2) (2018), 766–789. doi:10.1017/jsl.2018.3.

R.O.

Gandy, General recursive functionals of finite type and hierarchies of functionals, Ann. Fac. Sci. Univ. Clermond-Ferrand 35 (1967), 202–242.

J.D.

Hamkins and

Lewis, Infinite time Turing machines, J. Symb. Log. 65(2) (2000), 567–604. doi:10.2307/2586556.

Herrlich, Axiom of Choice, Lecture Notes in Mathematics, Vol. 1876, Springer, 2006.

P.G.

Hinman, Hierarchies of effective descriptive set theory, Trans. Amer. Math. Soc. 142 (1969), 111–140. doi:10.1090/S0002-9947-1969-0265161-3.

A.S.

Kechris, Classical Descriptive Set Theory, Graduate Texts in Mathematics, Vol. 156, Springer-Verlag, New York, 1995.

S.C.

Kleene, Recursive functionals and quantifiers of finite types I, Trans. Amer. Math. Soc. 91 (1959), 1–52.

Kunen, Set Theory – an Introduction to Independence Proofs, Studies in Logic and the Foundations of Mathematics, Vol. 102, North-Holland, 1980.

10.

J.R.

Longley and

Normann, Higher-Order Computability, Springer Verlag, 2015.

11.

Normann, Higher generalizations of the Turing model, in: Turing’s Legacy, Developments from Turing’s Ideas in Logic,

Downey, ed., Lecture Notes in Logic, Vol. 42, Cambridge University Press, 2014, pp. 397–433. doi:10.1017/CBO9781107338579.012.

12.

Normann, Functionals of type 3 as realisers of classical theorems in analysis, in: Sailing Routes in the World of Computation,

Manea,

R.G.

Miller and

Nowotka, eds, Lecture Notes in Computer Science, Vol. 10936, Springer, 2018, pp. 318–327. doi:10.1007/978-3-319-94418-0_32.

13.

Normann and

Sanders, The strength of compactness in computability theory and nonstandard analysis, Ann. P. Appl. Log. 170(11) (2019). doi:10.1016/j.apal.2019.05.007.

14.

Normann and

Sanders, On the mathematical and foundational significance of the uncountable, Jour. Math. Log. 19(1) (2019). doi:10.1142/S0219061319500016.

15.

Normann and

Sanders, Representations in measure theory: Between a non-computable rock and hard to prove place, submitted arXiv:1902.02756.

16.

G.E.

Sacks, Measure theoretic uniformity in recursion theory and set theory, Trans. Amer. Math. Soc. 124 (1969), 381–420. doi:10.1090/S0002-9947-1969-0253895-6.

17.

G.E.

Sacks, Higher Recursion Theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin-Heidelberg, 1990.

18.

M.E.

Sélivanowski, Sur une class d’ensembles effectifs (ensembles C), Mat. Sb. 35(3–4) (1928), 379–413.

19.

S.E.

Shreve, Probability measures and the C-sets of Selivanovskij, Pac. J. Math. 79(1) (1978), 189–196. doi:10.2140/pjm.1978.79.189.

20.

S.G.

Simpson, Subsystems of Second-Order Arithmetic, Cambridge University Press, 2009.

21.

Solovay, A model of set theory in which every set of reals is Lebesgue-measurable, Ann. of Math. 92 (1970), 1–56. doi:10.2307/1970696.

22.

Tanaka, A basis result for

Π_{1}^{1}

-sets of positive measure, Comment. Math. Univ. St. Paul 16 (1968), 115–127.

23.

P.D.

Welch, The length of infinite time Turing machine computations, Bull. London Math. Soc. 32 (2000), 129–136. doi:10.1112/S0024609399006657.

24.

P.D.

Welch, Transfinite machine models, in: Turing’s Legacy, Developments from Turing’s Ideas in Logic,

Downey, ed., Lecture Notes in Logic, Vol. 42, Cambridge University Press, 2014, pp. 493–529. doi:10.1017/CBO9781107338579.015.

25.

P.D.

Welch, Higher type recursion for transfinite machine theory, in: Computing with Foresight and Industry,

Manea,

Martin,

Paulusma and

Primeiro, eds, Lecture Notes in Computer Science, Vol. 11558, Springer, 2019, pp. 72–83. doi:10.1007/978-3-030-22996-2_7.

Measure-theoretic uniformity and the Suslin functional

Abstract

Keywords

1. Introduction

1.1. Measure, uniformity, and computability

1.2. Definitions and main results

1.2.1. Some definitions from computability theory

Proposition 1.3 (Measure-theoretic uniformity relative to 2 E ).

Proposition 1.4 (Measure-theoretic uniformity relative to S).

1.3. The bigger picture

Remark 1.5 (Related research).

2. The hierarchy of C-sets

2.1. Basic facts about C-sets

Definition 2.1 (C-sets).

3.1. Terminating computations and C-sets

4.1. Infinite time Turing machines

Definition 4.1 (ITTM output classes).

Proposition 4.2 (Hamkins–Lewis, Welch).

Footnotes

Acknowledgements

References

Proposition 1.3 (Measure-theoretic uniformity relative to $^{2} E$ ).