# Recursive set that contains in a way all the other recursive ones?

I am wondering, whether there a exists a recursive set $S\subseteq \mathbb{N}^2$, such that for every recursive set $T \subseteq \mathbb{N} \ \exists c \in \mathbb{N}: \ T=\left\{n \in \mathbb{N }| (c,n) \in S\right\}$ ? (And by "recursive set" I mean a set that is a projection of a recursive set; and by "recursive set" one whose characteristic function is recursive)

I know a similar proposition holds, if we replace "recursive with "recursively enumerable", but somehow I can't figure this one out...

-
I assume you mean $(c,n)\in S$? Otherwise you don't use $S$ at all. – Apostolos Apr 30 '11 at 21:25

1
You may want to think about universal Turing machines. – André Nicolas Apr 30 '11 at 22:18
And how sure are you about recursive? – André Nicolas Apr 30 '11 at 22:25
I am so sorry - being tired I confused "recursive" with "recursively enumerable" and asked a wrong question: It should have been "recursive" everywhere I wrote "recursive enumerable" - I edited the question now, so that it is really what I was asking. – temo May 1 '11 at 6:03

## 1 Answer

Let \$c_A\$ be a natural number that corresponds to any effective coding (for example: a Truing machine) of a recursively enumerable set \$A\$ and consider \$S = \bigcup_A {c_A} \times A\$.

The answer to your modified question is: no. Let us try to imitate the usual liar paradox. Suppose, that there exists a total Turing machine $U$ that computes $S$. And consider another Turing machine: $$N(x) = \mathit{not}\; U(x, x)$$ By the closure property $N$ is also recursive. So, there is a natural number \$c_N\$ corresponding to $N$ under $U$. Let us see what we get by applying $N$ to itself: $$N(c_N) = \mathit{not}\; U(c_N, c_N) = \mathit{not}\; N(c_N)$$ where the first equality is the definition of $N$ and the second holds by the definition of $S$.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 16, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9281447529792786, "perplexity_flag": "middle"}