# Incomputable sets of low degree vs Rices theorem?

I have heard that there are sets that are not computable, but are lower in degree than the halting problem.

How does this not contradict Rice's theorem? Are there any concrete examples of such sets?

• And, as far as I remember, all examples of such sets are constructed for that single purpose, so I don't think you find any "concrete examples" of such sets. (See The Priority Method.) – Pål GD Sep 11 at 13:28
• You should explain why you think there is a contradiction. We have too little information to be able to answer, unless you are willing to accept "Nope, there is no contradiction." – Andrej Bauer Sep 11 at 19:05
• In trying to answer that, I realized why there is no contradiction: Rice's theorem is for predicates on Turing machines - our non-computable set that is lower than the halting set will not be a predicate on Turing machines.. it'll have to be something else. Thanks! – rain1 Sep 11 at 20:18

This is not an answer, but way too long to be a comment. I just wanted to cite Robert I. Soare's Recursively Enumerable Sets and Degrees, Chapter V: Simple Sets and Post's Problem.

1: Immune Sets, Simple Sets, and Post's Construction

The only r.e. degrees constructed so far are $$\textbf{0}$$ and $$\textbf{0}'$$. Post's Problem was to construct other r.e. degrees, i.e., to construct an r.e. set $$A$$ such that $$\emptyset \lt_\text{T} A \lt_\text{T} \emptyset'$$. Post's Program for constructing such a set $$A$$ was to ﬁnd some easily deﬁnable property on $$\overline{A}$$ (compatible with $$A$$ being nonrecursive) which guarantees incompleteness ($$K \not\leq_\text{T} A$$).

Recall (from Theorem II.4.5) that $$K$$ (and hence any creative set) has an inﬁnite r.e. set (and therefore inﬁnitely many inﬁnite r.e. sets) contained in its complement. Post's idea for constructing $$A$$ incomplete was to make $$\overline{A}$$ sufﬁciently "thin" with respect to containment of inﬁnite r.e. sets so that $$\overline{K}$$ could not be Turing reduced to $$\overline{A}$$.

1.1 Deﬁnition. (i) A set is immune if it is infinite but contains no infinite r.e. set.
(ii) A set $$A$$ is simple if $$A$$ is r.e. and $$\overline{A}$$ is immune.

1.2 Proposition. If $$A$$ is simple then:

(i) $$A$$ is not recursive;
(ii) $$A$$ is not creative;
(iii) $$A$$ is not $$m$$-complete (i.e., $$K \not\leq_m A$$).

Proof. (i) $$\overline{A}$$ cannot be r.e., since otherwise it contains an inﬁnite r.e. set (namely $$\overline{A}$$).

(ii) The complement of a creative set does contain an inﬁnite r.e. set (by Theorem II.4.5).

(iii) If $$K \leq_m A$$, then $$A$$ is creative (by Corollary II.4.8). $$\Box$$

1.3 Theorem (Post [1944]). There exists a simple set $$S$$.

Proof. Let $$A = \{(e,x) \;:\; x \in W_e \;\&\; x > 2e \}$$. Now $$A$$ is $$\Sigma_1$$ and hence r.e. Let $$\psi$$ be any p.r. selector function for $$A$$ (in the sense of Theorem II.1.6) and let $$S = \text{rng}\; \psi$$. (Intuitively, enumerate $$W_e$$ until the ﬁrst element $$\psi(e) > 2e$$ appears in $$W_e$$, and then put $$\psi(e)$$ into $$S$$.) The following facts give the simplicity of $$S$$.

(1) $$S$$ is r.e. ($$S$$ is the range or a p.r. function.)

(2) $$\overline{S}$$ is inﬁnite. To see this, note that $$S$$ contains at most $$e$$ elements out of $$\{0,1,2,\dots,2e\}$$, namely $$\psi(0),\psi(1), \dots, \psi(e-1)$$. Hence $$e + 1 \leq \text{card}(\overline{S} \upharpoonright (2e+1))$$, so $$\overline{S}$$ is inﬁnite.

(3) If $$W_e$$, is inﬁnite, then $$W_e \cap S \neq \emptyset$$, because $$(e,x) \in A$$ for some $$x > 2e$$ and so $$\psi(e)$$ is deﬁned and $$\psi(e) \in S \cap W_e$$. $$\Box$$