Non recursive set that intersects every recursively enumerable set

Question

I'm trying to find a infinite, recursively enumerable and non recursvise set $B$ such that for every $A$ infinite recursively enumerable set, $A \cap B \neq \emptyset$ .

Well, I let $A_1, A_2, ...$ be all the recursively enumerable sets and $A_i=\{f_i(n)| n \in \mathbb{N}\}$.

The first idea was defining $g(n)=f_n(n)$ and let $B=\{g(n)| n \in \mathbb{N}\}$ , but listing in this way makes $g$ a non partial recursive function (Cantor's diagonal argument )

So , I defined $g$ as

• $g(0)=f_0(0)$

• $g(n+1)= f_{n+1}(k)$ where $k=\mu z (f_{n+1}(z)\neq g(m), 0 \leq m \leq n) $

but I guess it has the same problem.

If by chance this $g$ is $\mu$-recursive, I don't know how to prove that $B$ is not recursive.

Thanks in advance for any help.

Answer 1

What you need is a Simple Set. Post defined this notion and built the first simple set as :

1. Enumerate all r.e sets $W_e$
2. Take the first integer $n_e$ in the enumeration of each $W_e$ that verify $n\ge 2.e$.

You can verify that the set of all those integers is simple.