¿Es el conjunto de todos los subconjuntos definibles de los números naturales recursivamente enumerable?

Question

Ya me había planteado preguntas similares, por ejemplo: "¿Son contables los números reales definibles? Me pareció que el conjunto de todos los objetos definibles explícitamente y sin ambigüedad es "contable", porque podríamos escribir el texto que define un objeto específico en la lengua inglesa. (O utilizar la lengua inglesa para definir un lenguaje formal apropiado para escribir la definición). Pero el inglés no es inequívoco, y el significado de "contable" depende de la teoría de conjuntos utilizada.

Ahora mismo estoy pensando en la lógica de segundo orden. Asumir que los números naturales existen y están bien definidos me parece poco problemático. Sin embargo, la pregunta de qué subconjuntos de los números naturales (deberíamos suponer) existen no tiene una buena respuesta. Si decimos que existen "todos" los subconjuntos, nos encontramos con todo tipo de cuestiones de teoría de conjuntos. Si recurrimos a la teoría axiomática de conjuntos para estas cuestiones, acabamos con el hecho de que los números naturales no pueden definirse hasta el isomorfismo. La alternativa parece ser asumir que sólo existen los subconjuntos definibles de los números naturales. Pero mi opinión es que esto tampoco funcionará, es decir, que el "conjunto de todos los subconjuntos definibles de los números naturales" resulta ser una bestia muy extraña. Pero si es una bestia extraña, supongo que no será recursivamente enumerable.

Pregunta Suponiendo la tesis de Church-Turing (o un análogo adecuado para la definibilidad, o algún otro fundamento suficientemente sólido), ¿qué se puede decir del "conjunto de todos los subconjuntos definibles de los números naturales"? ¿Está bien definido y es recursivamente enumerable?

Editar Se ha señalado que mi uso de "recursivamente enumerable" es ambiguo sin más aclaraciones, especialmente porque tengo que especificar cómo se espera que un subconjunto definible de los números naturales se codifique como un número natural. Dado un número natural, toma su representación binaria y lo interpreta como un documento en el formato " OpenDocument "(ODF). Supongamos que podemos decidir eficazmente si el documento es un ODF válido y si su contenido está escrito de forma suficientemente clara y trata de definir un subconjunto de los números naturales. Llamemos a esto un definición de bien formado . Supongamos además que cada subconjunto definible tiene al menos una definición de bien formado que se puede reconocer a triunfar al definir un subconjunto de los números naturales. Ahora la pregunta es si existe un subconjunto recursivamente enumerable $S$ de los números naturales tal que cada número en $S$ corresponde a un definición de bien formado que tiene éxito y que para cada subconjunto definible el conjunto $S$ contiene la definición correspondiente.

Answer 1

La pregunta es algo ambigua sobre cómo se enumerarían exactamente los conjuntos. La forma natural de leerla en la teoría de la computabilidad es la siguiente, que es el sentido habitual en el que una secuencia de conjuntos puede ser r.e.:

¿Existe una enumeración doble computable $\{ n_{i,j} : i,j \in \omega\}$ tal que para cada conjunto definible $S \subseteq \omega$ hay un $i_0$ tal que $S = \{ n_{i_0,j} : j \in \omega\}$ .

La respuesta a esto es ciertamente "no", porque si fuera cierto entonces todo conjunto definible sería r.e., lo que no es el caso.

Answer 2

Una respuesta corta sería que el concepto de "recursivamente enumerable" es sólo definido para subconjuntos de algunos contable universo, donde ese universo tiene una codificación ("razonable") como cadenas finitas de símbolos que pueden ser introducidos o emitidos por una máquina de Turing. En su caso, el conjunto de "subconjuntos de $\mathbb N$ que son definibles" (sea lo que sea que eso signifique exactamente) no satisface esa condición, porque el universo natural a utilizar sería $\mathcal P(\mathbb N)$ que no es contable.

Así que ni siquiera tiene sentido preguntar si tu conjunto es r.e.

Se podría intentar ampliar las definiciones imaginando un no determinista Máquina de Turing que escribe una secuencia infinita de 0s y 1s en una cinta de salida de sólo escritura, donde esa secuencia puede ser interpretada como un subconjunto de $\mathbb N$ . Se podría entonces declarar que algunos $A\subseteq 2^{\mathbb N}$ es "recursivamente enumerable" si es el conjunto de posible salidas de alguna máquina no determinista.

Sin embargo, aunque se puede argumentar que esto generaliza el concepto ordinario de enumerabilidad recursiva, no sería sea el concepto ordinario de enumerabilidad recursiva.

Answer 3

Mientras cada número "definible" pueda definirse usando una cadena finita en algún alfabeto finito, puedes ordenar esas cadenas por longitud y enumerar los números usando esta ordenación.