Which are the hereditarily computably enumerable sets?

Question

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\}$.

1. 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$.

2. 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.

3. 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.

4. 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.

5. 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?.

Answer 1

The complexity of h.c.e. sets is quite subtle as the structure of the target set affects our ability to offload complexity to the limiting process. The property of being an h.c.e. code is $Π^1_1$ complete. Each h.c.e. set $A$ is hyperarithmetic, but in the hyperarithmetic hierarchy, the complexity of $x∈A$ is $Σ^0_{\operatorname{rank}(x)+ω}$ (this is not optimal) rather than bounded only by the complexity of $A$. This is because $x∈A$ can be computed recursively using $x∈A ⇔ ∃y∈A \, x=y$ and $x=y⇔x⊆y ∧ y⊆x$ and $x⊆y ⇔ ∀a∈x ∃b∈y \, a=b$.

On the other hand, the complexity of h.c.e. membership can be arbitrarily high in the hyperarithmetic hierarchy. For example, for every computable partial order $≺$ and computable ordinal $α$, there is an h.c.e. set $A$ such that $(x,β)∈A ⇔ β=\min(\operatorname{rank}_{≺}(x),α)$ where $\operatorname{rank}_{≺}(x)=∞$ iff $x$ is not in the well-founded part of $≺$. We get this by parallelizing across all nodes below $x$ and all ordinals $<α$ (and doing it recursively) and collecting all ordinals $<β$ to get $β$. There is no $Δ^1_1$ relation that when restricted to h.c.e. codes gives set equality or membership.

h.c.e. sets and $ℕ$

Every h.c.e. $A⊆ℕ$ is $Σ^0_2$; the converse holds if $A$ has an infinite $Σ^0_1$ or $Π^0_1$ subset. (Thus, h.c.e. sets are not closed under relative complement.) A natural number $n$ is in h.c.e. $A⊆ℕ$ iff unrolling $A$ (by running its program, and its output programs recursively) at some point gives a branch of rank $n$ that never increases its rank afterwards. For the converse, given $x∈A ⇔ ∃m \, ∀n \, φ(x,m,n)$ for bounded quantifier $φ$, for every $m$ and $x$ we launch an instance for $m$ witnessing $x∈A$. The instance will produce $x$ but if some $n$ refutes $φ(x,m,n)$, it will convert $x$ to a larger number in $A$. Note that the h.c.e. process can convert between arbitrary hereditarily finite sets as long as the rank does not decrease.

Despite the above, a set $A$ is the intersection of an h.c.e. set with $ℕ$ iff it is $Σ^0_4$. (Thus, h.c.e. sets are not closed under intersection.) Moreover, for h.c.e. codes, whether the corresponding sets include the same elements of $ℕ$ is $Π^0_5$ complete. In one direction, $n∈A$ iff $∃a∈A \, \operatorname{rank}(a)=n ∧ ∀b∈\operatorname{tc}(\{a\}) \, ∀m < \operatorname{rank}(b) \, ∃c∈b \, \operatorname{rank}(c)=m$ where $\operatorname{tc}$ is transitive closure. Note that the rank of an element being $≤m$ is $Π^0_1$. In the other direction, given $x∈A∩ℕ ⇔ ∃a ∀b ∃c ∀d \, φ(x,a,b,c,d)$ for bounded quantifier $φ$, we let $a$ identify an encoded element of $A$, $b∈a$ a potential bad member, $c∈b$ a witness that $b$ has element of rank 0, and $d$ confirm that $c$ never gets an element.

The above complexity depends on natural numbers being identified with von Neumann ordinals. The intersection of an h.c.e set with {{},{{}},{{{}}},...} is $Σ^0_3$ (using $n∈A$ iff $∃a∈A$ such that all leaves in $a$ have depth $n$), and conversely every $Σ^0_3$ predicate is witnessed this way.

There are non-arithmetic h.c.e. subsets of $V_ω$ (the set of hereditarily finite sets, aka HF). Each increase in rank can encode an extra quantifier: If we can encode arbitrary $Π^0_n$ queries into the choice between getting set $A$ and getting set $B$, we get $Π^0_{n+1}$ from the choice between $\{B\}$ and $\{A,B\}$.

Answer 2

Re question 3: Not every arithmetic real is h.c.e.. In fact, every h.c.e. real is $\Sigma_2^\mathbb{N}$. For fix a program $e$ such that $x_e\subseteq\omega$. Let $n\in\omega$. Then $n\in x_e$ iff there is some $f$ enumerated by $e$ such that $n=x_f$. But we can express "$n=x_f$" here in a $(\Sigma_1\wedge\Pi_1)^{\mathbb{N}}$ manner (this uses the assumption that $x_e\subseteq\omega$). For given $n\in\omega$ and a program $f$ which is enumerated by $e$, we have $n=x_f$ iff there is a tuple $(f_0,f_1,\ldots,f_{n-1})$ of programs such that $f$ enumerates $f_{n-1}$, $f_{n-1}$ enumerates $f_{n-2}$, $\ldots$, $f_1$ enumerates $f_0$, and there is no tuple $(g_0,g_1,\ldots,g_n)$ such that $f$ enumerates $g_n$, $g_n$ enumerates $g_{n-1}$, $\ldots$, $g_1$ enumerates $g_0$.