Traces, traceability, and lattices of traces under the set theoretic inclusion (Q377460)

The paper is concerned with traces; a trace is a computably enumerable set \(V\) of natural numbers such that every \(V^{[m]}:=\{n \mid \langle n,m\rangle\in V\}\) is finite, where \(\langle , \rangle\) is the pairing function -- i.e., an r.e. system of indexed finite sets. Thinking of functions \(f:\mathbb{N}\rightarrow\mathbb{N}\), one can imagine a trace as `guessing' finitely many values for \(f(n)\); if the correct value is always among these `guesses', the function is `traceable'. Expressing \(A\subseteq\mathbb{N}\) via a function mapping \(n\) to a binary string representing the characteristic function of \(A^{\leq n}\), traces can also be used to `guess' sets. Traces show up at various places in recursion theory, among them algorithmic randomness. Section \(2\) gives basic facts about traces; in particular, it is shown that the set of programs computing traces is not r.e. and in fact \(\Pi_{3}\)-complete. Section \(3\) then looks at traceable functions and sets. Clearly, if a function \(f\) is traceable by a trace \(V\) with \(|V^{[m]}|=1\) for cofinitely many \(m\), then \(f\) is computable; otherwise, functions of arbitrary Turing degree are traceable via \(V\). This suggests investigating the number \(|V^{[m]}|\) of `guesses' a trace \(V\) tracing a function \(f\) or a set \(A\) makes for each \(m\), which is done in a series of results showing e.g. that exactly the computable sets are traceable by a \(V\) with \(|V^{[m]}|\) bounded by a constant, but that already below \(\mathbf{0}^{\prime\prime}\), there are sets that can only be traced by a \(V\) for which \(|V^{[m]}|>2^{m-j}\) for some \(j\); this bound can be considerably improved when \(A\) contains an infinite computable subset. Concerning functions, it is shown that there are \(f\leq\mathbf{0}^{\prime}\) that cannot be traced by any \(V\) for which \(|V^{[m]}|\) is bounded by a recursive function and that this continues to hold even if the finiteness condition in the definition of a trace is relaxed to the demand that \(V^{[m]}\neq\mathbb{N}\) for infinitely many \(m\). Section \(4\) exhibits structural properties of the lattices \(L_{\mathrm{tr}}(V)\) of traces \(W\supseteq V\) with \(V\) a trace ordered by \(\subseteq\). \(L_{\mathrm{tr}}(\emptyset)\) is shown to allow a set of continuum many automorphisms that are far apart from each other in the sense that, for each two \(\Phi_{1},\Phi_{2}\) of them, \(\Phi_{1}(V)\setminus\Phi_{2}(V)\) will be infinite for some \(V\). Some information is given about the relation to \(\mathcal{E}\), the lattice of r.e. sets ordered by \(\subseteq\); finally, it is shown that \(L_{\mathrm{tr}}(V)\) is isomorphic to \(L_{\mathrm{tr}}(\emptyset)\) for computable \(V\), but not in general. The paper is reasonably self-contained and good to read. It is a bit unfortunate that the connection to algorithmic randomness, which appears among the keywords, is not explained, but the paper contains many results and methods that give a good picture of the behaviour of traces and are likely to come in handy when working with them.