subconjuntos de conjuntos recursivos infinitos

Una pregunta reciente del examen fue la siguiente:

$A$ es un conjunto infinito recursivamente enumerable. Demuestre que tiene un subconjunto recursivo infinito. $A$

Deje que sea un subconjunto infinito de recursiva . ¿Debe tener un subconjunto que no es recursivamente enumerable? $C$ $A$ $C$

Respondí 1. ya. Con respecto a 2., respondí afirmativamente y discutí lo siguiente.

Supongamos que todos los subconjuntos de fueran recursivamente enumerables. Como es infinito, el conjunto de potencias de es incontable, por lo que suponiendo que haya incontables muchos conjuntos recursivamente enumerables. Pero los conjuntos recursivamente enumerables están en correspondencia uno a uno con las máquinas de Turing que los reconocen, y las máquinas de Turing son enumerables. Contradicción. Por lo tanto, debe tener un subconjunto que no sea recursivamente enumerable. $C$ $C$ $C$ $C$

¿Es esto correcto?

computability check-my-proof usuario1435
fuente

No es del todo correcto al final, porque cada reinicio se enumera en infinitas máquinas de Turing, no solo en una. Sin embargo, puedes evitar esto.

Carl Mummert

@Carl: Ah, claro, gracias, error tonto. Pero todo lo que necesito es una inyección en los TM, no una biyección, ¿verdad? Y en la definición de Turing-computable con la que trabajó mi clase, cada TM está asociada con una y solo una función. Así que diferentes conjuntos -> diferentes funciones de reconocimiento -> diferentes TMs que los computan.

user1435

! user1435: está invirtiendo las cosas en la última oración. Cada máquina de Turing calcula una sola función, pero cada función computable se obtiene de infinitas máquinas de Turing.

Carl Mummert

Pero si mi función f asigna {funciones de reconocimiento r} a {TMs} a través de f (r) = cualquiera de las infinitas TM que lo calculan, tengo una inyección, ¿verdad? O supongo que podría simplemente particionar {TMs} por una relación de equivalencia ~ que identifica el infinito de TMs que calculan la misma función, y luego mapear r a la clase de equivalencia apropiada.

user1435

Carl tiene razón, no están en correspondencia uno a uno, cada conjunto ce corresponde a infinitas TM. Tener en cuenta otros conjuntos de objetos como lo hace en su comentario no cambia nada, no son el conjunto de TM.

Kaveh

Respuestas:

Es correcto.

Cada conjunto infinito tiene un subconjunto indecidible, puede utilizar el argumento de cardinalidad: . De hecho, la mayoría de sus subconjuntos son indecidibles (y puede reemplazarlo por cualquier clase contable de lenguajes, egce, aritmético , analítico , ...). $\aleph_0\leq C \implies \aleph_0 < 2^C$

Lo malo de este argumento es que no proporciona ninguna información sobre la dificultad del subconjunto. Por lo general, queremos un subconjunto que sea lo más fácil posible. Una forma de obtener esto es usando una diagonalización similar al argumento de cardinalidad usando el hecho de que es decidible: $C$

Definir , donde es el º conjunto ce. Obviamente . Además, puede resolverse con un oráculo para y . Entonces, si es decidible, entonces es un lenguaje común. $D = \{ i \in C \mid i \notin W_i \}$ $W_i$ $i$ $D \subseteq C$ $D$ $C$ $K = \{ i \mid i\notin W_i\}$ $C$ $D$

Kaveh
fuente

"Cada conjunto infinito tiene un subconjunto indecidible". Esto es más débil que la afirmación que intenté probar. Traté de demostrar que C debe tener un subconjunto no RE, no un subconjunto no decidible. ¿Mi reclamo sigue siendo correcto?

user1435

Si. El término "indecidible" está un poco sobrecargado (Wikipedia tiene una buena discusión ). Entonces, esta respuesta probablemente significa lo que estás tratando de probar.

David Lewis

@ user1435, sí, el mismo argumento funciona para cualquier clase contable de idiomas, actualicé la pregunta para aclararla.

Kaveh