¿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

Teorema de recursión de Kleene dice, de manera informal, que cuando escribimos un programa para una función computable podemos asumir que el programa ya tiene acceso a su propio código fuente.

Más formalmente, el teorema dice que si $f\colon \mathbb{N} \to \mathbb{N}$ es una función totalmente computable (que vemos como un método que construye un programa $f(e)$ de un programa $e$ ) hay algún programa $e_0$ tal que la función computable con programa $e_0$ es la misma función que la función con programa $f(e_0)$ .

Una aplicación trivial: si $f(e)$ es un programa que simplemente produce $e$ y se detiene, el programa $e_0$ produce su propio código fuente.

Una de las aplicaciones mágicas del teorema de recursión es el lema sobre la recursión transfinita efectiva en la teoría hiperaritmética, que es una de las herramientas clave en ese entorno.

Answer 2

El lema de la verdad

El resultado dice que lo que es cierto en una extensión forzada $M[G]$ es sólo lo que está obligado a ser cierto por el camino del filtro genérico $G$ . Más concretamente:

Supongamos que $M$ es un modelo transitivo contable de $\text{ZFC}$ , $\mathbb{P} \in M$ un poset forzado, $\varphi(x_1, \dots, x_n)$ una fórmula teórica establecida, y $\tau_1, \dots, \tau_n$ una secuencia de $\mathbb{P}$ -nombres en $M$ . Si un filtro $G$ en $\mathbb{P}$ cumple con cada subconjunto denso de $\mathbb{P}$ en $M$ entonces $\varphi(\tau_1^G, \dots, \tau_n^G)$ tiene en $M[G]$ si $G$ golpea un $p$ que obliga a $\varphi(\tau_1, \dots, \tau_n)$ .

De hecho, $M$ sólo necesita satisfacer una subteoría finita suficientemente rica de $\text{ZFC}$ . (El grado de riqueza depende de $\varphi$ .) Por lo tanto, la existencia de una $M$ se deduce del Teorema de la Reflexión, que se puede demostrar en $\text{ZFC}$ sin asumir que $\text{ZFC}$ tiene un modelo transitivo contable.

Con un resultado conocido como el Lemma de la Definibilidad, el Lemma de la Verdad implica que todo orden parcial obliga a $\text{ZFC}$ . Es decir, $\text{ZFC}$ se mantiene en cada $M[G]$ -sin importar el $M$ , $\mathbb{P}$ o $G$ . Esto es clave para demostrar que $M[G]$ es siempre la menor extensión transitiva de $M$ satisfaciendo $\text{ZFC}$ y que contiene $G$ como elemento. Así, en diversas circunstancias se puede construir el orden parcial $\mathbb{P}$ de intentos de construir un objeto deseado, argumentar que el objeto existe en cualquier extensión de $M$ que contiene un filtro $G$ como en el lema, y así obtener la existencia real del objeto deseado en un modelo en el que los axiomas de ZFC siguen siendo válidos. ¡Mágico!

Answer 3

Teorema de Ramsey

El teorema tiene dos formas.

Forma finita. Para todo lo que no sea cero $n, k, m \in \mathbb{N}$ hay un $r \in \mathbb{N}$ tal que, para cada conjunto $R$ de tamaño $r$ y cada $k$ -coloración del $n$ -subconjuntos de elementos de $R$ existe un conjunto homogéneo de tamaño $m$ .

Forma ininita. Para todo lo que no sea cero $n, k \in \mathbb{N}$ cada conjunto infinito $W$ y cada $k$ -coloración del $n$ -subconjuntos de elementos de $W$ , existe un conjunto homogéneo infinito.

El documento original de Frank Ramsey se titula Sobre un problema de lógica formal Así que no debería sorprender que el famoso teorema y sus generalizaciones tengan aplicaciones mágicas en la lógica. Por ejemplo, el Teorema de Ramsey, el Teorema de Erdős-Rado y sus más esotérico extensiones se utilizan a menudo en la teoría de modelos para establecer la existencia de elementos indiscernibles .

[¡¡¡Por favor, amplíen esto!!!]

Answer 4

Teorema de interpretabilidad de Guaspari-Lindström

En aras de la inteligibilidad, esta afirmación no es todo lo general que podría ser.

Supongamos que $S$ y $T$ son extensiones recursivas consistentes de $\text{ZFC}$ . Entonces $T$ interpreta $S$ si $T$ prueba cada $\Pi_1$ consecuencia de $S$ .

Los teóricos de los conjuntos utilizan esto para medir la fuerza de consistencia de extensiones "naturales" de $\text{ZFC}$ que están (hasta donde se puede decir) preordenados bajo la relación de interpretabilidad. En otras palabras, las extensiones naturales forman una jerarquía bien ordenada de grados de la interpretabilidad. Esto es sorprendente, ya que es fácil construir extensiones naturales que parecen no tener nada en común, por ejemplo, $\text{ZFC + }$ "determinación proyectiva" y $\text{ZFC + }$ "un cardenal supercompacto existe".

[Alguien con experiencia, por favor, edite y amplíe].

Answer 5

Teorema HSP de Birkhoff

Personalmente, me han gustado los teoremas de conservación. El teorema HSP de Birkhoff, que identifica las clases modelo de ciertas teorías ecuacionales como aquellas clases (conocidas en el álgebra universal como variedades) cerradas bajo homomorfismos ( H ), (iso a) subálgebras ( S ), y (iso a) productos ( P ) es el que recuerdo más fácilmente. También hay otras versiones (por ejemplo, para las cuasivariedades). Espero que esto sea lo suficientemente mágico para ti.

Gerhard "Ask Me About System Design" Paseman, 2011.08.29

Editar: François me pidió que incluyera mi comentario en la respuesta de Gerhard. Intentaré ser breve. Al igual que las teorías algebraicas pueden describirse à la Lawvere como ciertas categorías $T$ con productos finitos, y modelos de $T$ como funtores preservadores de productos finitos $T \to Set$ es interesante considerar las "teorías exactas de la izquierda" (también conocidas como "teorías esencialmente algebraicas") que son categorías $T$ con límites finitos, cuyos modelos son funtores finitamente continuos $T \to Set$ . Las teorías de los posets y de las categorías son ejemplos de teorías esencialmente algebraicas.

Se sabe qué categorías son categorías de modelos de alguna teoría esencialmente algebraica, y éste es el contenido de la dualidad Gabriel-Ulmer. De hecho, existe una equivalencia precisa (bicategórica) contravariante entre la bicategoría de categorías finitamente completas y la bicategoría de categorías localmente presentables de forma finita . El concepto de colímite filtrado desempeña un papel crucial en este desarrollo.

Un ejemplo de teorema dentro de esta teoría general que extrapola el Teorema de la Variedad de Birkhoff es que una clase de estructuras sobre una firma funcional multiordenada es una cuasi-variedad finitaria (es decir, definible por cláusulas de Horn sobre predicados ecuacionales) si y sólo si es cerrada bajo productos, subobjetos y colímites filtrados dentro de la categoría de todas las estructuras. Para una referencia, véase Adámek y Rosicky, Locally Presentable and Accessible Categories, teorema 3.22.

Todd "Estoy feliz de obedecer" Trimble