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 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...
Let $c_A$ be a natural number that corresponds to any effective coding (for example: a Turing 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$.