$A$ are the even numbers, is there a non-computable set $B$ such that $A\nleq_1 B$?

227 Views Asked by At

Assume $A,B\subseteq \omega$, we say $A\leq_1 B$ (1-reducible) if there is a injective computable function $f$ such that, for all $x$, $$x\in A \Leftrightarrow f(x)\in B.$$

Now assume $A$ are the even numbers. I want to construct a non-computable set $B$ such that $A\nleq_1 B$.

I know the intution behind $m$-reducibility, which is the same as above but without the injectivity of $f$, $B$ is more "complicated" than $A$ if $A\leq_m B$. I don't really have an intuition behind non-comparable sets with respect to $\leq_m$ or $\leq_1$. I could show that non-computable c.e. sets are incomparable with respect to $\leq_m$.

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, there are such sets.

Notice first that, if $A\leq_1 B$ then $B$ has to have an infinite computably enumerable subset, namely the image of $A$ under the $1-1$ reduction function. (Similarly, the complement of $B$ must also have an infinite c.e. subset.) There exist infinite sets with no infinite c.e. subsets; they are called immune. So any immune set provides an example of the sort you seek.

More is known about immune sets. For example, there are immune sets whose complement is also immune. On the other hand, there are immune sets whose complement is c.e. (A c.e. set whose complement is immune is called a simple set.)

Now that you know the terminology "immune" and "simple" (and "co-immune" for "having an immune complement") you'll be able to find lots of information about these sets on line --- surely lots more than I know (or ever knew).