¿Qué es un teorema mágico en lógica?

Question

Algunos teoremas son mágicos: sus hipótesis son fáciles de cumplir y, cuando se invocan (como lemas) en medio de una demostración rutinaria, ofrecen la conclusión deseada más o menos directamente, como si se sacara un conejo de la chistera. He aquí cinco ejemplos. Algunos son ajenos a la lógica, pero cada uno de ellos suele ser útil dentro de la lógica.

Teorema de la categoría Baire. En cualquier espacio topológico completamente metrizable, cada conjunto abierto no vacío es no-meager.

El lema diagonal de Gödel. Si una teoría $T$ interpreta relativamente la aritmética de Robinson, entonces para cada fórmula de primer orden $\varphi(x,v_1,\dots,v_n)$ en la lengua de $T$ Hay un $\psi(v_1,\dots,v_n)$ tal que $T$ demuestra la sentencia $\forall v_1 \dots \forall v_n[\psi(v_1,\dots,v_n) \leftrightarrow \varphi(\overline\psi,v_1,\dots,v_n)]$ , donde $\overline\psi$ es el código de $\psi$ .

El lema del árbol de König. Todo árbol de división finita de altura infinita tiene una rama infinita.

Teorema de Knaster-Tarski. Todo operador monótono no decreciente sobre el conjunto de potencias de un conjunto tiene un punto fijo.

Lemma de colapso de Mostowski. Si $E$ es una relación de clase binaria bien fundada, similar a un conjunto, y extensional sobre una clase $M$ entonces existe una única clase transitiva $N$ tal que $(M, E)$ es isomorfo a $(N, \in)$ .

Enumeremos otros teoremas mágicos que todo lógico puede esgrimir. De este modo, los estudiantes conocerán resultados útiles que, de otro modo, podrían escapar a su atención hasta mucho más tarde. (Hay una cuestión relacionada aquí . Pero ésta y la mayoría de sus respuestas no se centran en teoremas útiles en lógica). Por favor, trata sólo un teorema por respuesta, y escribe tantas respuestas como quieras. No te limites a poner un enlace a la Wikipedia o lo que sea; da una declaración concisa. Si es posible, que sea informal. Bonificación si el teorema no es muy conocido, o si lo muestras en acción.

Answer 1

El Teorema de la compacidad

Es curioso que nadie lo haya mencionado hasta ahora. En realidad, el Teorema de la Compactación me parece mágico:

Una teoría de primer orden $T$ tiene un modelo si y sólo si todo subconjunto finito de $T$ tiene un modelo.

Esto te permite derivar la forma finita del teorema de Ramsey a partir de la forma infinita. Eso es mágico. Para la mayoría de las aplicaciones de este tipo, el teorema de la compacidad para el cálculo proposicional es realmente suficiente.

La compacidad para la lógica de primer orden y la lógica proposicional son realmente equivalentes (sobre ZF). De hecho, existe una colección bastante amplia de resultados equivalentes:

• Teorema del ideal primo booleano
• El lema del ultrafiltro
• El teorema de la representación de la piedra
• Teorema de Tychonoff para espacios compactos de Hausdorff

El teorema de la compacidad es estrictamente más débil que el axioma de elección, pero no es demostrable en ZF simple. Esto se utiliza a menudo para mostrar que ciertos resultados son más débiles que el axioma de elección. Por ejemplo, se puede utilizar para mostrar que la existencia de conjuntos no medibles es más débil que el Axioma de Elección (por un viejo resultado de Sierpiński).

Answer 2

Creo que el hecho de que un topos elemental tenga colimits finitos es mágico. La definición de topos sólo pide límites finitos, pero ¡abracadabra! El mago saca colímites finitos de la chistera.

(¿Qué es lo que he oído decir? ¿No crees que la teoría de los topos forma parte de la lógica moderna? ¿De verdad? ¿De verdad? Pues ya sabes dónde está el botón "abajo").

Answer 3

El Teorema de la Absolutidad de Shoenfield

$\Pi^1_2$ y $\Sigma^1_2$ Los enunciados son absolutos para los modelos transitivos de la teoría de conjuntos.

Así, un $\Pi^1_2$ es verdadera (en $V$ ) si y sólo si es verdadera en $L$ (el universo construible ). Dado que $L$ satisface el Axioma de Elección, todo verdadero $\Pi^1_2$ La afirmación es coherente con el Axioma de la Elección. Este hecho se utiliza a menudo para mostrar que asumir el axioma de elección es a menudo completamente inofensivo en la práctica matemática. Ejemplos de $\Pi^1_2$ los teoremas incluyen

• El teorema del punto fijo de Brouwer (clásico)
• El teorema separable de Hanh-Banach
• Teorema de Ascoli
• La existencia de cierres algebraicos para campos contables
• La existencia de ideales primos o maximales para anillos contables
• Teorema del árbol de König
• Teorema de Ramsey
• Teorema de completitud para lenguajes de primer orden contables

y muchos, muchos más...

El Teorema de la Absolutidad de Shoenfield se utiliza a menudo junto con el forzamiento. En efecto, si un $\Pi^1_2$ o $\Sigma^1_2$ puede ser forzada en una extensión, entonces debe haber sido ya verdadera en el modelo base. Otros resultados absolutos también se utilizan de este modo. Por ejemplo, la prueba original del teorema de Baumgartner-Hajnal (véase aquí y aquí ) combina el forzamiento y el absolutismo de las relaciones bien fundadas.

Answer 4

Eliminación de cortes muestra que si una frase es demostrable en la lógica de primer orden, es demostrable con un tipo de prueba particularmente agradable en un sistema de deducción natural sin la regla de "corte", que es esencialmente modus ponens en ese sistema. En particular, estas pruebas tienen la propiedad de la subfórmula: cada fórmula de la prueba completa es una subfórmula de la fórmula que se demuestra.

El teorema de eliminación de cortes y sus generalizaciones son herramientas clave en la teoría de la prueba. Gentzen demostró la eliminación de cortes en 1934 y la utilizó como parte de su prueba de consistencia de la aritmética de Peano; hay un buen artículo de estudio " El arte del análisis ordinal "por Michael Rathjen en Proc. ICM 2006.

El teorema de la eliminación del corte se puede utilizar para dar buenas pruebas del teorema de la interpolación de Craig y otros teoremas de la lógica; una exposición es Capítulo 6 de "Lógica para la informática" de Jean Gallier.

Answer 5

El Teorema de la base baja

En la pregunta has mencionado el lema del árbol de König. Hay un refinamiento muy útil que es común en la teoría de la computabilidad y áreas relacionadas:

Todo subárbol infinito computable de $\{0,1\}^{<\infty}$ tiene una rama infinita con un grado de Turing bajo.

Un conjunto $A$ tiene un grado de Turing bajo si el problema de detención relativo a $A$ tiene el mismo grado de Turing que el problema de detención (no relativizado). En particular, un conjunto que tiene un grado de Turing bajo es incompleto (no computa el conjunto de parada). Por lo tanto, el Teorema de la Base Baja se utiliza a menudo para mostrar que un problema particular tiene una solución que tiene estrictamente menor complejidad que el problema de detención.

Otra característica interesante del Teorema de la Base Baja es que es iterable. En efecto, el teorema se relativiza muy fácilmente. Dado que ser bajo en relación con un grado bajo es lo mismo que ser simplemente bajo, el teorema puede aplicarse varias veces seguidas para obtener el mismo resultado.

También hay que tener en cuenta que es muy importante que el árbol sea un subárbol de $\{0,1\}^{<\infty}$ (o, más generalmente, que el árbol esté acotado computacionalmente). De hecho, existen subárboles computables de ramificación finita de $\mathbb{N}^{<\infty}$ cuyas ramas infinitas calculan el conjunto de parada. Sin embargo, el Teorema de la Base de Kreisel garantiza que todo subárbol computable de ramas finitas de $\mathbb{N}^{<\infty}$ con altura infinita tiene una rama infinita que es computable a partir del conjunto de parada.

Una aplicación interesante del teorema de la base baja es que la aritmética de Peano (PA), la teoría de conjuntos de Zermelo-Fraenkel (ZF) y todas las demás teorías axiomatizables consistentes tienen terminaciones de bajo grado y, por tanto, no calculan el conjunto de parada.