¿Existe una fórmula explícita describiendo cada secuencia posible de números?

Question

Este hilo fue anteriormente titulado "¿ un Conjunto Requieren de una Fórmula Explícita para Existir?".

Estoy leyendo H. Enderton los Elementos de la Teoría de conjuntos y de trabajo a través de la comprensión de la Zermelo-Fraenkel axiomas. Durante la lectura, la siguiente pregunta relativa a la naturaleza de los conjuntos se me ocurrió.

Supongamos que te doy un conjunto infinito de números enteros, que parece no tener definibles por el patrón. Por ejemplo, supongamos que empezar a hacer una lista de los elementos del conjunto: \begin{equation*} S=\{3,4,11,199,205,6090,11238,...\} \end{ecuación*} Simplemente he elegido los números completos al azar y les ordenó. Que yo sepa, no hay ninguna fórmula que describe esos números. Supongamos que este conjunto continúa para siempre.

De acuerdo a la teoría de conjuntos, hace de este conjunto existen? Parece difícil decir que no existe, después de todo, he empezado a escribir ya, así que ¿cómo puede no existir?

Sin embargo, creo que la teoría de conjuntos requiere establece de forma explícita la fórmula. Entonces la pregunta es: dado cualquier secuencia de números como el que he mencionado (sin aparente "patrón"), ¿existe una fórmula que describe la secuencia?

Me doy cuenta de que esto es un poco de la pregunta filosófica, y que provienen de un nuevo lector de la teoría de conjuntos. Sin embargo, este parece ser el tipo de pregunta que la teoría de conjuntos fue inventado para responder. Gracias por sus pensamientos y explicaciones!

---

Edit: Gracias a Yuval por su respuesta! Su respuesta planteadas algunas reflexiones que quería agregar a la pregunta.

Dado un conjunto arbitrario de números enteros, aunque no puedo encontrar una fórmula que describa, ya que el conjunto de TODOS los enteros que existe, entonces por el poder establecido axioma cualquier subconjunto de la misma debe existir.

Así, podría ser que no soy lo suficientemente inteligente como para formular una fórmula explícita para mi arbitraria conjunto de números enteros, pero dicha fórmula (tan complicado como puede ser!) en realidad existe? Tal vez la existencia de una fórmula que describe cualquier tipo de secuencia de números es tomada como un axioma, o quizás todo lo contrario es cierto y se puede comprobar que existe una secuencia sin una fórmula.

También me pregunto, aunque sé muy poco acerca de ella - ¿a esta pregunta tiene nada que ver con el Axioma de Elección?

Gracias de nuevo por tus pensamientos y explicaciones!

Answer 1

La existencia es una propiedad semántica, que nos obligan a hablar de un modelo (internamente a ese modelo, o externamente a ese modelo). Existe algo en el modelo, si es que en el modelo. No hay otra manera de decirlo.

A veces podemos demostrar que ciertos objetos existen, incluso si no tenemos explícito de los medios de producción. Este, por ejemplo, es como el axioma de elección de las obras. Esto demuestra que hay una cierta función de elección sin que nos da una fórmula explícita la definición de la misma. La negación del axioma de elección funciona igualmente no de manera constructiva, nos dice que hay algunos de la familia de conjuntos que no admiten una función de elección, pero no nos dice lo familiar que es.

Así, es cada conjunto definible? Cada set $A$ satisface la fórmula con $A$ como parámetro, $A=\{x\mid x\in A\}$, pero estoy asumiendo que te refieres a algo menos "evidente". La respuesta es posiblemente negativo, y posiblemente positivo. Depende del modelo que hemos de tomar.

Answer 2

Decir que un conjunto $x$ es definible si no hay una fórmula "$\phi$" en el lenguaje de la teoría de conjuntos $\mathcal L_\in$ con sólo una variable libre, tales que: para todos los $z$, $z\in x$ iff "$\phi$" es de $z$. A continuación, una forma simple de leer la pregunta es:

Pregunta: Es todo el conjunto definible?

Para hacer esta pregunta, tenemos que decir lo que significa para una fórmula en $\mathcal L_\in$ a "en espera" de un conjunto. Pero podemos hacerlo fácilmente mediante la adición de una satisfacción predicado, $Sat$,$\mathcal L_\in$, la adición de sus asociados axiomas, y la expansión de la sustitución y de la separación de los axiomas de ZFC el nuevo idioma. En particular, en esta nueva teoría, podemos decir que un conjunto $x$ es definible si no hay una fórmula "$\phi$ " $\mathcal L_\in$ con una variable libre, tales que: para todos los $z$, $z\in x$ iff $Sat(``\phi", z)$.

A continuación, podemos mostrar:

Teorema: Hay indefinible conjuntos.

Prueba. Como User4894 y Yuval señaló, hay más conjuntos de fórmulas en $\mathcal L_\in$.

Answer 3

Por el poder establecido axioma, el juego de poder de la set $\mathbb{Z}$ de los números enteros (que existe, esencialmente, por el axioma de infinitud) existe. Así que todos los conjuntos de números enteros existen. Por supuesto, si usted no puede escribir el conjunto, no tiene sentido preguntar si el conjunto existe. La cuestión formal "¿el conjunto de $S$ existe", o más exactamente "¿el conjunto descrito por $\varphi$ existen" tiene la formulación de $\exists x \varphi(x)$ (es decir, es esta declaración derivable en ZF). Si usted no puede describir mediante una fórmula, ni siquiera se puede preguntar si es que existe.

Answer 4

El verdadero problema es "supongamos que este conjunto continúa para siempre". Si sigue usted decir con elecciones al azar, a continuación, el conjunto que se describe no existe en ZF. Usted puede crear subconjuntos de un conjunto dado sólo con la primera orden de fórmulas. Si se puede seleccionar cualquier subconjunto independientemente de las propiedades, no habría necesidad de que el axioma de elección: Dada una familia de conjuntos que sólo podría crear un subconjunto con un elemento de cada elemento de la familia. De manera que los conjuntos son creados usando los axiomas y casi todo axioma de alguna manera crea un conjunto. Por ejemplo, si se ha demostrado que dos conjuntos son diferentes, axioma de extensionality "crea" un conjunto que pertenece a uno solo de ellos (incluso si no podemos presentar uno). Algunos juegos (como el Omega y el conjunto vacío) han axiomas sólo para ellos. El axioma de especificación nos permiten separar una parte del conjunto que satisface una determinada primer orden, la lógica de la fórmula, sino que pertenece a un conjunto no necessaraly implica la existencia.