Simple and immune amounts

Simple and immune sets are classes of subsets of natural numbers and provide important counterexamples in computability theory . They are closely related to the concept of recursive enumerability ( RE ): While immune sets are precisely the countable infinite sets of natural numbers that do not have an infinite recursively enumerable subset, the simple sets are the recursively enumerable complements of immune sets. The definitions can be further strengthened and thus lead to the concept of hyper- or even hyper-hypersimple sets .

Emil Post already suspected the existence of simple sets in the 1940s, but it was not until 1956 and 1957 that this could be proven (independently of one another) by Richard Friedberg and Albert Muchnik .

definition

Let it be an effective numbering of all recursively enumerable sets. ${\displaystyle \{W_{n}\}_{n\in \mathbb {N} }}$

A lot of natural numbers are called immune , if true . ${\displaystyle A\subseteq \mathbb {N} }$ ${\displaystyle \vert A\vert =\vert \mathbb {N} \vert \land \forall n\in \mathbb {N} \colon \vert W_{n}\vert =\vert \mathbb {N} \vert \Rightarrow W_{n}\nsubseteq A}$

(i.e. is countably infinite, but does not have an infinite recursively enumerable subset). Here denote the cardinality of a set. ${\displaystyle A}$ ${\displaystyle \vert \cdot \vert }$

A set is simply called if it is itself recursively enumerable and its complement is immune. ${\displaystyle B\subseteq \mathbb {N} }$ ${\displaystyle {\overline {B}}=\mathbb {N} \setminus B}$

history

When Post in 1944 began to compare problems according to their decidability , the question quickly arose whether every recursively enumerable set that is no longer decidable is automatically already complete for the enumerable sets. Now complements RE -complete sets (more precisely all productive sets ) have an infinite enumerable subset. That is, the existence of simple sets is already sufficient for the negative answer to the above question. Post himself suspected this existence, but has not yet been able to prove it. Only when Friedberg and Muchnik solved the (more general) Post problem in 1956/57 , they constructed the first simple set en passant. This was also the first proof in the history of the theory of computation that was carried out using the priority method. Today, however, much simpler constructions of simple sets are known.

example

According to the prerequisite, there is a Turing machine (or an algorithm in an alternative computability model ) that enumerates the set when entered . Now be the partial number function in which is always the first element found by , for which applies if such an element exists. Then it is obviously (partially) calculable and its range of values is simple. ${\displaystyle M}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle W_{n}\subseteq \mathbb {N} }$ ${\displaystyle f\colon \mathbb {N} \rightsquigarrow \mathbb {N} }$ ${\displaystyle f(n)}$ ${\displaystyle M}$ ${\displaystyle y\in W_{n}}$ ${\displaystyle y>2n}$ ${\displaystyle f\in {\mathcal {P}}}$ ${\displaystyle range(f)}$

In the same way, other simple sets can also be constructed.

properties

• Immune sets are not recursively enumerable, otherwise they would contain themselves as an infinite enumerable subset.
• An infinite set is immune if and only if it does not contain an infinite decidable subset.
• Simple sets are therefore not decidable.
• Immune sets are not productive by construction and simple sets are therefore not creative either .
• After Myhill simple amounts are therefore not RE -complete.
• There are a couple of simple sets that make up the natural numbers . ${\displaystyle A;B\subseteq \mathbb {N} }$ ${\displaystyle A\cup B=\mathbb {N} }$

Hyper-simple and hyperimmune quantities

It is said that an ordered set of natural numbers is majorized by a number function if it holds that the function value is always at least as large as the smallest value of . ${\displaystyle A=\{z_{1}<z_{2}<z_{3}<\cdots \}\subseteq \mathbb {N} }$ ${\displaystyle h\colon \mathbb {N} \to \mathbb {N} }$ ${\displaystyle \forall x\in \mathbb {N} \colon h(x)\geq z_{x}}$ ${\displaystyle h(x)}$ ${\displaystyle x}$ ${\displaystyle A}$

A lot is called hyperimmune ( hi ) if it is not dominated by any totally calculable function . ${\displaystyle A}$ ${\displaystyle h\in {\mathcal {R}}}$

A set is then called hypersimple ( hs ; from English hypersimple ) if it can be enumerated recursively and its complement is hi. ${\displaystyle B\subseteq \mathbb {N} }$

• Hyper-simple sets are necessarily infinite.
• Hyperimmune quantities are always immune, and therefore hyper-simple quantities are always simple.
• There are simple sets that are not hyper-simple.
• The intersection of two hyper-simple sets is again hyper-simple.
• The union of a hyperimmune and an immune set is again hyperimmune.

Hyperhyping Simple and Hyperhyperimmune Quantities

There is a characterization of hi sets that is sometimes used as an alternative definition:

Let it be an effective numbering of all finite subsets of (e.g. for ). ${\displaystyle \{D_{i}\}_{i\in \mathbb {N} }}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle D_{i}=\{x_{1};x_{2};\dots ;x_{n}\}}$ ${\displaystyle i=2^{x_{1}}+2^{x_{2}}+\dots +2^{x_{n}}}$

An infinite set is hyperimmune if and only if there is no totally calculable function such that it holds. ${\displaystyle A}$ ${\displaystyle f\in {\mathcal {R}}}$ ${\displaystyle (\forall x;y\colon \ x\neq y\Rightarrow D_{f(x)}\cap D_{f(y)}=\emptyset )\land (\forall x\colon \ D_{f(x)}\cap A\neq \emptyset )}$

In other words, an infinite set is hi if there is no computable list - in canonical indices - of pairwise disjoint finite sets that all intersect. ${\displaystyle A}$ ${\displaystyle A}$

If one now moves from the canonical -indices to the more general -indices introduced above , the definition of hyperhyperimmune sets results. It turned out that this is actually stronger. ${\displaystyle D}$ ${\displaystyle W}$

An infinite set is hot hyperhyperimmune ( hhi ), if there is no totally computable function , so that for each the set is finite and holds. ${\displaystyle A}$ ${\displaystyle f\in {\mathcal {R}}}$ ${\displaystyle x\in \mathbb {N} }$ ${\displaystyle W_{f(x)}}$ ${\displaystyle (\forall x;y\colon \ x\neq y\Rightarrow W_{f(x)}\cap W_{f(y)}=\emptyset )\land (\forall x\colon \ W_{f(x)}\cap A\neq \emptyset )}$

A set is hhi if it is infinite and there is no computable list - in -indices - of pairwise disjoint finite sets that all intersect this set. ${\displaystyle W}$

A set of sets is then called hyperhypsimple ( hhs ) if it is recursively enumerable and its complement is hhi. ${\displaystyle B}$

• Hyperhyperimmune quantities are always hyperimmune, since -indexes can be converted into -indexes in a calculable manner. ${\displaystyle D}$ ${\displaystyle W}$
• There are hyperimmune amounts that are not hyperhyperimmune.

literature

• H. Rogers Jr .: Theory of recursive functions and effective computability . 2nd Edition. MIT Press, Cambridge, MA 1987, ISBN 0-262-68052-1 .
• P. Odifreddi : Classical Recursion Theory . Elsevier, 1989, ISBN 0-444-87295-7 .

Individual evidence

1. ↑ E. Post: Recursively enumerable sets of positive integers and Their decision problems. Bulletin of the American Mathematical Society, Vol. 50 (1944), No. 5, pp. 284-316 (online, PDF file; 4.0 MB) .
2. ^ R. Friedberg: Two recursively enumerable sets of incomparable degree of unsolvability (solution of Post's problem 1944) . In: Proceedings of the National Academy of Sciences . tape 43 , p. 236-238 ( pnas.org [PDF]).
3. ↑ A. Muchnik: About the unsolvability of the problem of reducibility in the theory of algorithms. (Russian) . In: Doklady Akademii Nauk SSSR (NS) . tape 108 , 1956, pp. 194-197 .
4. ↑ Put with analogously to , but with . ${\displaystyle S=range(g)}$ ${\displaystyle g\in {\mathcal {P}}}$ ${\displaystyle f}$ ${\displaystyle g(n)>3n}$
5. ↑ Add and , with from the example above. ${\displaystyle A=S\cup 2\mathbb {N} }$ ${\displaystyle B=S\cup 2\mathbb {N} +1}$ ${\displaystyle S}$
6. ↑ Take the set from the example above, it is simple, but its complement is majorized by. ${\displaystyle S}$ ${\displaystyle h(x)=\lceil 3/2\ x\rceil }$