Effective cardinality 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?
 A: 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. 
A: 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).
