¿Gödel Integridad del Teorema todavía se mantienen incluso si el conjunto de variables es finito?

Question

Deje $L$ ser de primer orden lenguaje con un conjunto finito de variables. Deje $T$ ser un conjunto coherente de fórmulas de $L$. De lo anterior se sigue que existe un modelo para $T$?

Answer 1

No creo que esto es posible de una manera significativa.

El punto de completitud de Gödel es el teorema que relaciona en el sintáctico y semántico nociones muy bien juntos. Sin embargo, no es difícil darse cuenta de que usted podría incluso venir para arriba con un sintáctica nociones en este caso: Aquí está un ejemplo: Supongamos que su lenguaje tiene dos constantes símbolos $a_{1},a_{2}$ $T$ dice que $a_{1}\neq{a_{2}}$. Ahora en una prueba razonable del sistema sería de esperar que las reglas le permiten a la conclusión de que $\exists{x_{1}},{x_{2}}$ $\text{s.t.}x_{1}\neq{x_{2}}$. Pero si usted dice que sólo hay una variable permitido, realmente no se puede decir que.

Edit: creo que la verdadera pregunta aquí es que si la conclusión se refiere únicamente a $n$ variables, hay una prueba de que sólo involucra $\leq{n}$ variables? Si ese fue el caso de lo que estás intentando tendría sentido. Pero creo que los siguientes pueden ser estudiados dar un contraejemplo.

Supongamos que sólo tenemos dos variables para jugar con y que el lenguaje tiene un predicado unario $P$. Supongamos que $T=\{\exists{!x_{1}}\text{ s.t. }Px_{1}\} \cup$ $\{\forall{x_{1}}Px_{1}\}$. Ahora, cualquier modelo de $M$ $T$ debería modelo que el universo tiene exactamente un elemento. Pero una prueba de que yo no creo que sea posible sin referencia a una tercera variable (de este no estoy seguro de cómo probar, y probablemente requiere una prueba de análisis que no estoy seguro de cómo hacerlo).

Nota: no tengo Manin del libro. Sin embargo, él habría restricciones en donde sustituciones se pueden hacer y el intento de probar el resultado por el supuesto de la existencia de dos elementos fallará debido a estas reglas (Ver mi respuesta aquí: Un problema con la interpretación de Kleene (Lógica Matemática) restricciones a la deducción en FOL). Sin embargo, con el fin de mostrar ninguna prueba de que es posible requeriría una especie de prueba de análisis en el espíritu de la incompletitud de Gödel, que no estoy seguro de cómo hacerlo.

Answer 2

Esto es no una respuesta, sino un largo comentario.

Estoy de acuerdo con Danul la respuesta de que una oferta limitada del individuo variables puede limitar mucho la expresiva, la capacidad de la lengua.

Pero es bien sabido que el f-o la lógica no es capaz de expresar "todo"; en particular, no es capaz de discriminar entre modelos con diferentes infinito cardinalidades.

Por lo tanto, podemos suponer que, con sólo 100 variables, la supuesta "finito" f-o lógica no puede discriminar entre los modelos con más de 100 objetos.

Pero tenemos f-o de matemáticas de la teoría, como la teoría de grupo, el cual necesita de un muy limitado número de variables : tres (véase Herbert Enderton, Matemáticas, Introducción a la Lógica (2º - 2001), página 93).

Para f-o la teoría de los números [ver S. C. Kleene, Introducción a la Metamathematics (1952), página 82, o Peter Smith, Una Introducción a Gödel de Teoremas (1ª ed - 2007), página 77], dos variables suficiente.

Como se explicó en el Asaf comentario, para afirmar la infinitud de los modelos de $\mathsf {PA}$ sólo necesitamos dos variables $x,y$ y el constante símbolo $0$, porque depende de los dos axiomas :

$∀x∀y(S(x)=S(y)→x=y)$ $∀x(x≠0→∃y(x=S(y)))$ .

Por lo tanto, mi perplejidad es que, dejando aparte las cuestiones de la cardinalidad, no puedo "ver" lo que son los "impactos" de las limitaciones anteriores: acerca de la consistencia, integridad, etc.

¿Qué acerca de la inducción axioma de la teoría de los números (sólo tenemos una cantidad finita de wf fórmulas en el "finito" f-o lógica) ?

El único libro de texto moderno que yo sé, con una discusión acerca de la "ontología" de las variables es :

George Tourlakis, Conferencias en Lógica y Teoría de conjuntos. Volumen 1 : la Lógica Matemática (2003), página 10.

Sugiero una reflexión sobre este pasaje [página 12] :

Si somos Platónicos, entonces tenemos disponible en la metatheory todo tipo de conjuntos, incluidos los conjuntos infinitos, en particular, el conjunto de todos los números naturales. Podemos utilizar cualquiera de estos elementos, que hablan de ellos, etc., como nos plazca, cuando estamos describiendo o la construcción de la teoría formal dentro de nuestra metatheory.

Ahora, si no somos Platónicos, nuestro "verdadero" mundo matemático es mucho más restringido. En un extremo, tenemos no hay conjuntos infinitos. [nota : Un finitist – y no olvides que Hilbert-estilo metatheory fue finitary, aparentemente por razones políticas – te permitirá tener tantos enteros como te gusta en una porción, siempre y cuando la porción es finito. Si usted pide más, usted puede tener más, pero nunca el conjunto de todos los números enteros o un subconjunto infinito de los mismos.]

Podemos todavía se las arreglan para definir nuestro lenguaje formal! Después de todo, el "nonending" secuencia de variables de objeto $v_0, v_1, v_2,$ . . . puede ser finitely generado en al menos dos maneras diferentes, como ya hemos visto. Así podemos explicar (a un cierto formalismo o finitist) que "no secuencia final" fue un desafortunado desliz de la lengua, y que en realidad la intención de dar un procedimiento de cómo generar en la demanda de una nueva variable de objeto, diferente de lo que nosotros ya puede tener.

Una final "tonto" comentario. Creo que tenemos al menos un "pragmático" refutación de la "finita" f-s idioma: ¿por qué detenerse en 10, o 100, o mil millones de variables individuales ? tenemos ninguna razón para elegir un "específico" límite... por lo tanto, asumir un ilimitado suministro de ellos.

Agregado De Abril, 27 De

Acerca de la pregunta original :

Sea L ser de primer orden lenguaje con un conjunto finito de variables. Deje $T$ ser un conjunto coherente de fórmulas de L. No se sigue que no existe un modelo para $T$?

Yo creo que SÍ.

Considerar el lenguaje para la f-o número de thoery, y "restringir" a dos individuales variables : $v_0, v_1$; obviamente, de esta manera, se puede formar sólo un número finito de wf fórmulas.

Considere ahora el llamado sistema $Q$ de Robinson Aritmética, sin la inducción del esquema [ver a Pedro Smith, página 55]; sus siete axiomas necesidades de sólo dos variables.

Si nos "restringir" $Q$ a "finito" f-o idioma con sólo dos variables, tenemos una sub-teoría de la $Q^-$, que es el sonido ($\mathbb N$ es un modelo de la misma) y consistente, si $Q$ es (porque si podemos demostrar una contradicción en $Q^-$, esta prueba es ipso facto también una prueba en $Q$).

La noción de validez de la fórmula no cambia : una fórmula con sólo dos variables es válida si es verdadera en todos los modelos.

La cuestión de la integridad del correo.g.de dos variables "finito" f-o lógica es más difícil.

Somos capaces de demostrar el teorema de completitud ? es decir, que todas las fórmulas válidas con sólo dos variables son demostrables ?

Answer 3

Por una rápida lectura de Manin del libro, creo que la respuesta a su pregunta es sí, por el teorema de completitud.

De hecho Manin prueba no parece ser necesario el conjunto de variables a ser infinito.

No obstante yo también suponga que la siguiente afirmación de ser verdad:

Deje $L$ $L'$ dos lenguas, de tal manera que $L \subseteq L'$ $L'$ es obtenido por $L$ sólo la adición de un conjunto infinito de variables. Para cada $L$-fórmula $\varphi$ $L$- teoría de la $T$ $T \vdash \varphi$ en el idioma $L$ si y sólo si $T \vdash \varphi$ en el idioma $L'$.

Una implicación es trivial. La idea de demostrar que el otro implicación debe proceder de la siguiente manera:

• demostrar que para cualquier prueba que utiliza fórmulas con variables en $L' \setminus L$ podemos sustituir las fórmulas con otros obtenidos por la sustitución de la mal variables con términos adecuados de $L$, obteniendo así una prueba de la misma fórmula en el lenguaje de $L$;
• por definición de provability a la conclusión de la reclamación.

Por supuesto, esto no es una prueba, pero espero que le puede dar una idea de por qué se debe trabajar.