Topological perspective of Rice-Shapiro theorem

80 Views Asked by At

Given a Gödel numbering $\phi_n$ of the partial recursive unary functions, the Rice-Shapiro theorem states

Let $\mathcal A$ be a family of partial-recursive unary functions such that its index set $A = \{ x \in \mathbb N\ |\ \phi_x \in \mathcal A \}$ is r. e. Then for any partial recursive unary $f,$ $$f \in \mathcal A \iff \exists \theta \in \mathcal A \text{ finite function with } \theta \subseteq f.$$

Let $\mathcal B = \{U_\theta\ |\ \theta \text{ finite function}\},$ for $$ U_\theta = \{f \text{ partial recursive } |\ \theta \subseteq f \}. $$ Then $\mathcal B$ is the basis of a topology in the set of all partial recursive functions (in fact, this extends to the set of all partial unary functions). Then the content of the Rice-Shapiro theorem as stated is that any such $\mathcal A$ is open with respect to this topology. The corresponding Wikipedia page makes a stronger claim: in this notation,

$\mathcal A$ has r. e. index set iff it is a recursively enumerable union of $U_\theta$.

I'm not $100\%$ sure of what a r. e. union means in this context. I first assumed that for a family $\{ U_\theta\ |\ \theta \in \Theta \}$ it means something like:

There is a (total) recursive function $k(x)$ such that {$\phi_{k(x)}\ |\ x \in \mathbb N\} = \Theta.$

However that does not seem enough, because there must also be an effective way to know what the domain of $\phi_{k(x)}$ is.

So I guess that an appropriate bijective enumeration $\theta_n$ of the set of all finite functions must be used, such that the predicate “$\phi_x \text{ extends } \theta_y$” is partially decidable. Then r. e. subsets of finite functions correspond to r. e. subsets of $\mathbb N.$

If I use that definition I think I can finish the proof for both implications. So my question is, is this the correct definition? If so, I can intuitively see that such enumeration exists, but is there a reference where it's constructed explicitely? For example in Hartley-Roger's book there is a version of the theorem for sets, but not for finite functions.

1

There are 1 best solutions below

5
On BEST ANSWER

Let $\mathscr F$ be the set of all finite functions from $\mathbb N$ to $\mathbb N,$ and think of any $\theta\in\mathscr F$ as a code for the set $U_\theta = \{\varphi\mid\varphi\text{ is partial recursive and }\theta\subseteq\varphi\}.$ The Wikipedia article you linked to calls these sets frusta. $U_\theta$ is the frustum coded by $\theta.$

Having a recursively enumerable union of frusta really means: (1) having a recursively enumerable set of codes for frusta, and (2) taking the union of those particular frusta. (This is all using the specific coding $\theta\mapsto U_\theta$ above.)

In other words, it means that we have an recursively enumerable $W\subseteq\mathscr F$ and we're looking at $\bigcup_{\theta\in W} U_\theta.$

You can look at this in terms of recursive functions (as you were suggesting), but it's just a bit more complicated: You'd start with a recursive function $k:\mathbb N\to\mathscr F,$ and you'd then look at $\bigcup_{n\in\mathbb N} U_{k(n)}.$ However, you'd need to treat the empty set as a special case because the empty set, although r.e., isn't the range of a recursive function.