2
$\begingroup$

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

  • 0
    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.2011-05-01

1 Answers 1

3

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