Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 3 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.