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