6
$\begingroup$

Consider $X,Y \subseteq \mathbb{N}$.

We say that $X \equiv Y$ iff there exists a bijection between $X$ and $Y$.

We say that $X \equiv_c Y$ iff there exist a bijective computable function between $X$ and $Y$.

Can you show me some examples in which the two concepts disagree?

  • 0
    Probably relevant: http://en.wikipedia.org/wiki/Myhill_isomorphism_theorem2012-07-10

2 Answers 2

4

Let $X = \omega$, the natural number. Let $\bar{K}$ be the complement of the $K = \{e : \phi_e(e)\downarrow\}$, the halting problem set. That is, $K$ is set of $e$ such that the $e^\text{th}$ Turing Machine on input $e$ converges.

Suppose there exists a computable bijection from $\omega \rightarrow \bar{K}$. Then $\bar{K}$ would be a c.e. set.

It is well known that $K$ is not computable, but c.e. Therefore, $\bar{K}$ is not c.e. (This follows from the fact that if a set $A$ and $\bar{A}$ are c.e., then $A$ is computable.)

Of course since $\bar{K}$ is an infinite subset of $\omega$, there is clearly a bijection between $\omega$ and $\bar{K}$.


Also I am not sure if $\equiv_c$ as you defined it is even an equivalence relation. If $f: X \rightarrow Y$ is a computable bijection, we understand "computable" here to mean that there is some $f' : \omega \rightarrow \omega$ which is computable in the ordinary sense such that the restriction of $X$ gives the bijection $f: X \rightarrow Y$. The only problem is that do you want $f' : \omega \rightarrow \omega$ to be bijective, i.e. what is called a computable permutation. If not, I am not sure if $\equiv_c$ is symmetric. However, if you demand that $f' : \omega \rightarrow \omega$ also be bijective, then the relation is symmetric with the inverse being the witness.

0

The structure with the computable equivalence (which is defined as $A\leq_T B$ and $B \leq_T A$) is called Turing degrees and has a very rich structure (unlike the usual bijection).

  • 0
    The version defined by OP is not even symmetric. The right version is the computable equivalence w.r.t. many-one Turing reductions. One can also consider one-one Turing reductions but that is less natural.2012-06-13