Cardinalidad eficaz

Question

Considerar el $X,Y \subseteq \mathbb{N}$.

Decimos que $X \equiv Y$ iff allí existe una biyección entre $X$y $Y$.

Decimos que $X \equiv_c Y$ iff existe una función computable biyectiva entre $X$y $Y$.

¿Me puede mostrar algunos ejemplos en los que los dos conceptos no están de acuerdo?

Answer 1

Deje $X = \omega$, el número natural. Deje $\bar{K}$ ser el complemento de la $K = \{e : \phi_e(e)\downarrow\}$, la detención conjunto de problemas. Es decir, $K$ $e$ de manera tal que el $e^\text{th}$ Máquina de Turing en la entrada de $e$ converge.

Supongamos que existe una computable bijection de $\omega \rightarrow \bar{K}$. A continuación, $\bar{K}$ sería un c.e. conjunto.

Es bien sabido que $K$ no es computable, pero c.e. Por lo tanto, $\bar{K}$ no es c.e. (Esto se deduce del hecho de que si un conjunto $A$ $\bar{A}$ c.e., a continuación, $A$ es computable.)

Por supuesto, ya que $\bar{K}$ es un subconjunto infinito de $\omega$, es evidente que existe un bijection entre el$\omega$$\bar{K}$.

---

También no estoy seguro de si $\equiv_c$ como usted la ha definido como una relación de equivalencia. Si $f: X \rightarrow Y$ es una computable bijection, entendemos por "computable" aquí significa que hay algunos $f' : \omega \rightarrow \omega$ que es computable en el sentido ordinario tal que la restricción de $X$ da la bijection $f: X \rightarrow Y$. El único problema es que no desea $f' : \omega \rightarrow \omega$ a ser bijective, es decir, lo que se llama una computable de permutación. Si no, yo no estoy seguro de si $\equiv_c$ es simétrica. Sin embargo, si la demanda que $f' : \omega \rightarrow \omega$ también se bijective, entonces la relación es simétrica con la inversa de ser el testigo.

Answer 2

La estructura con la equivalencia computable (que se define como el $A\leq_T B$ y $B \leq_T A$) se llama Turing grados y tiene una estructura muy rica (a diferencia de la habitual biyección).