# Can any computably enumerable set be generated by a prefix-free set?

Downey and Hirschfeldt seem to assume that any computably enumerable set of sequences can be generated from some prefix-free set (in the sense that the set of all extensions of the strings in the prefix-free set is equal to the first set). I don't understand why this would be so.

Specifically, in a proof that a sequence is Martin-Löf random iff is there is no c.e. martingale on the sequence that produces infinite profit, on page 236, D&H assume that for each class $$U_n$$ that makes up a Martin-Löf test, there is a "prefix-free generator" $$R_n$$ (which I take to be what I described above, cf. p. 4). D&H's definition of Martin-Löf test is on 231: the sequence of $$U_n$$ is merely required to be uniformly c.e. s.t. $$\mu(U_n)\leq 2^{-n}$$.

I don't understand why such a generator must always exist.

For example, let $$U_n$$ be$$\{00000\ldots\}$$ for all $$n$$. Then each $$U_n$$ is null with respect to the uniform measure, so this is a Martin-Löf test. However, any finite sequence of zeros that would include a sequence of all zeros as an extension, would also have extensions such as $$01\ldots$$, $$001\ldots$$, etc., which are not in $$U_n$$. So there is no generator of $$U_n$$.

Clearly I am misunderstanding something (or have not noticed some constraint on Martin-Löf tests?).

Downey and Hirschfeldt prove (2.19.2, p. 74) that every $$\Sigma^0_1$$ set of infinite sequences is one that can be generated by a c.e. set of finite strings. Moreover, they define Martin-Löf randomness in terms of a sequence of $$\Sigma^0_1$$ sets $$U_n$$ of infinite sequences. This is why they have the right to assume that every such $$U_n$$ can be generated by such a set of finite strings.
In my gloss of D&H's description of a Martin-Löf test, I stated the requirement that the test sets be $$\Sigma^0_1$$ as a requirement that they be computably enumerable. One can see the equivalence of $$\Sigma^0_1$$ and c.e. as implied by D&H's proposition 2.19.2, but it's proved directly by, for example, Nies, 1.4.12, p. 22. So the way that I characterized D&H's description of Martin-Löf tests was correct.
While it's true that $$U_n=\{000\ldots\}$$ can't be generated by finite strings, my mistake was thinking that such a $$U_n$$ is computably enumerable. It was surprising to me to realize that such a trivially simple set is not c.e. After all, the set has only one element, and a Turing machine that generates it or checks for it is trivial. The crucial point, though, is that that machine cannot halt on $$000\ldots$$, since the sequence of zeros is infinite. No program can ever successfully list or accept even (the) one member of this set. Thus my sequence of sets $$U_n$$ do not form a Martin-Löf test.
(It is possible to define a Martin-Löf test that excludes only $$000\ldots$$ from the random sequences, but that test has to consist of sets such as, for example, $$U_n=\{x:$$ the first $$n$$ digits of $$x$$ are 0$$\}$$. Each such set contains an uncountably infinite number of infinite sequences, but each is a subset of previous sets $$U_1, U_2, \ldots, U_{n-1}$$. The one sequence contained in each of them is $$000\ldots$$ .)