# 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
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

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