My question is about sets that are computably enumerable with respect to their hereditary membership structure. Specifically, let me define that a *hereditarily computably enumerable* (h.c.e.) set is one whose elements can be enumerated by a computable process, in the sense that the process enumerates programs representing those elements themselves as h.c.e. sets.

That is, program $e$ is a h.c.e. program representing the h.c.e. set $x_e$ if and only if $$x_e=\{x_f\mid f\text{ appears amongst the enumerated output of }e\}.$$ As the program $e$ runs, it may periodically place some numbers $f$ on the output tape, and those numbers are the programs that will themselves represent the sets $x_f$ that are the elements of $x_e$.

For example, a program $f$ that never puts anything on the output tape will represent the empty set $\varnothing$, and a program $e$ that enumerates only $f$ will represent $\{\varnothing\}$, and so forth.

The definition of the h.c.e. sets is recursive, proceeding in a transfinite recursion, and what I intend is that the h.c.e. programs are the smallest collection of programs closed under the feature that if a program enumerates a list of h.c.e. programs, then that program itself is also h.c.e.

When enumerating a set, it is fine for the elements to be duplicated, since for example $\{a,b,a,c\}$ is the same set as $\{a,b,c\}$.

- Which sets are hereditarily computably enumerable?

It is easy to see that every natural number $n$, construed as a von Neumann ordinal $n=\{k\mid k<n\}$, is h.c.e., since we can design program $\check n$ that enumerates programs $\check k$ for $k<n$.

Similarly, every c.e. set $W\subseteq\mathbb{N}$ is h.c.e., since we can start enumerating $W$, and whenever $n$ appears we place $\check n$ into our target set.

It is also easy to see that every computable ordinal is h.c.e., since if I have a computable presentation of a well-order, I can construct from it the programs that enumerate for any element the programs arising in the predecessors of that number with respect to the relation.

It is clear that the h.c.e. sets are closed under pairing $\{x_e,x_f\}$ and union $x_e\cup x_f$, and also the union of any h.c.e. set $\bigcup x_e$ is h.c.e., since this is just the set of sets that are elements of an element of $x_e$, but one can get those by waiting for a program $f$ to be enumerated by $e$ and then waiting for a program $g$ to be enumerated by $f$.

It is much less clear whether the h.c.e. sets are closed under intersection $x_e\cap x_f$ or relative complement $x_e\setminus x_f$.

- Are the h.c.e. sets closed under intersection and relative complement?

This seems difficult to achieve directly, even for intersection, since in general we won't be able to compute the identity relation $x_u=x_v$, and so we can't just check that a set has been enumerated into both, since we often won't be sure whether two programs represent the same set.

Nevertheless, I can imagine that we might get an affirmative answer to this question as a consequence of a robust answer to question 1, similar to how Dan Turetsky proved that the computable surreal numbers are closed under division, not by showing directly how to divide computably, but by showing that the computable surreals are those with hyperarithmetic sign sequences, and division is hyperarithmetic. Perhaps a similar phenomenon will arise here with the h.c.e. sets.

Let me prove at least that the h.c.e. sets include some non-c.e. sets of natural numbers. For example, I claim that every infinite co-c.e. set, such as the complement of the halting problem is h.c.e., as follows. Let $A$ be an infinite co-c.e. set. For each $n$, let $p_n$ be a program that starts by enumerating programs that will produce a copy of the hereditary $\in$-structure of $n$, unless $n$ is enumerated out of $A$, at which time additional elements of those programs are enumerated so as to make it into a copy of $n+1$, and then proceed as $p_{n+1}$ would. (The point here is that the $\in$ structure of $n$ can be enlarged to a copy of $n+1$, and so we can turn $n$ into $n+1$ if we should want to.) We keep proceeding in this way, and every time something is enumerated out of $A$, we turn all the copies of that number into the next number. Eventually, the numbers stablize on the next element of $A$, and so ultimately the only numbers actually in the set we are representing will be the elements of $A$, as desired.

That argument seems fairly general and powerful in a way, but I don't quite see how far it goes.

- Is every arithmetically definable set of natural numbers h.c.e? Is every hyperarithmetic set of natural numbers h.c.e.?

If one thinks about the hereditary membership structure of the h.c.e. sets, what is happening is that there is an underlying well-founded relation, where the top program has the enumerated elements as children, and those programs have their enumerated programs as children, and so forth. This relation will be well-founded, in order for the program to be h.c.e. The recursive definition of $x_e$ I gave above is simply the Mostowski collapse of this relation. In this sense, we can identify the h.c.e. sets with the computable well-founded relations. We can assume the sets arising in the h.c.e. programs are computably decidable rather than merely c.e., by means of Craig's trick, since any program can be replaced by a much larger program, which otherwise works exactly the same, except that the size is large enough that it codes the stage when the smaller version was enumerated into the set. In this way, h.c.e. sets arise by computable sets of programs (and computable well-founded trees) rather than c.e.

Thus, to recognize whether a given program is h.c.e. will be a $\Pi^1_1$ property, and this will be $\Pi^1_1$-complete since we can reduce questions of well-foundedness to it.

Meanwhile, the identity relation $x_e=x_f$ for the h.c.e. sets will correspond to having a bisimilarity on the underlying enumerated relations, and so the identity relation seems to have complexity $\Sigma^1_1$, given that $e$ and $f$ indeed are h.c.e.

- What is the exact complexity of identity $x_e=x_f$?

Similarly, the membership relation $x_e\in x_f$ will correspond to $x_e$ being identical to $e_h$ for one of the programs $h$ enumerated by $f$. So this also is at worst $\Sigma^1_1$, given that these are indeed h.c.e.

- What is the exact complexity of membership $x_e\in x_f$?

Ultimately, the topic and theme here arises as a pure-set analogue of the question I asked recently about the computable surreal numbers, What do we know about the computable surreal numbers?.

9more comments