Metateoría: introducción

Resumen

Esta clase abre la cuarta y última unidad de contenido del curso, dedicada a la metateoría. Presenta sus tres clases y el hilo que las une: las dos unidades anteriores construyeron, sobre la misma lengua, dos nociones de lo que se sigue de unas premisas, la deducción $\Gamma \vdash \varphi$ y la consecuencia semántica $\Gamma \models \varphi$ , y esta unidad demuestra que coinciden, primero para premisas finitas (corrección, lema de Kalmár y completitud), después para premisas cualesquiera (teorema de compacidad y completitud fuerte), y ofrece por último un tercer modo de decidir la consecuencia, el método de resolución, del que demuestra también que es correcto y completo. Explica por qué la compacidad se demuestra antes de la completitud fuerte, y no al revés; muestra con dos ejemplos las preguntas que ni la búsqueda de deducciones ni la tabla de verdad pueden responder por sí solas; precisa lo que se toma de las tres unidades anteriores y da consejos para estudiarla.

Objetivos de aprendizaje

Describir la secuencia de las tres clases de la unidad, explicar qué resultados de cada una usa la siguiente y justificar que la compacidad se demuestre, por un argumento semántico, antes de la completitud fuerte.
Distinguir las dos caras del curso, la deducibilidad $\Gamma \vdash \varphi$ , existencial y finita, y la consecuencia semántica $\Gamma \models \varphi$ , universal sobre infinitas valoraciones, y enunciar la corrección y la completitud en sus tres grados.
Explicar por qué la coincidencia de ambas relaciones no puede establecerse caso por caso, sino con metateoremas, y reconocer qué instrumentos de las unidades anteriores (inducciones, prueba por casos, teoremas de deducción, lema de coincidencia, formas conjuntivas) usará cada demostración.
Leer deducciones sobre deducciones y argumentos semánticos de la unidad distinguiendo en cada paso la relación de que se habla, y organizar el estudio a partir de la evaluación de entrada.

Evaluación de entrada

Antes de recorrer la unidad conviene medir el punto de partida. Esta evaluación es una autoevaluación: no se califica, y su único propósito es orientar el estudio. Sus quince preguntas son de dos clases. Las seis primeras tocan lo que la unidad da por sabido de las anteriores: la definición de la consecuencia semántica y su reducción a la insatisfacibilidad, el valor de la negación conjunta, el lema de coincidencia, el carácter finito de la deducción y la prueba por casos; quien falle alguna debe repasar, antes de seguir, la clase que la pregunta nombra. Las nueve restantes tocan, en orden, las tres clases de esta unidad, tres cada una. Quien nunca haya estudiado la metateoría de un sistema lógico no debe esperar acertarlas, y no importa: cada respuesta, acertada o no, explica el punto y nombra la clase que lo trata. Las mismas destrezas se vuelven a medir al final, en la clase de síntesis.

Evaluación de entrada

Antes de comenzar la unidad, mide tu punto de partida. Es una autoevaluación breve: no se califica y su resultado se guarda solo en tu navegador.

Pregunta 1De unidades anteriores¿Qué significa $\Gamma \models \varphi$ ?
Que toda valoración que satisface todas las fórmulas de $\Gamma$ satisface $\varphi$ .
Que existe una deducción de $\varphi$ desde $\Gamma$ .
Que alguna valoración satisface a la vez $\Gamma$ y $\varphi$ .
Que $\varphi$ es consecuencia de alguna fórmula de $\Gamma$ tomada sola.
Pregunta 2De unidades anteriores¿Cuál de las afirmaciones siguientes equivale a $\Gamma \models \varphi$ ?
Que $\Gamma \cup \{\neg\varphi\}$ es insatisfacible.
Que $\Gamma \cup \{\varphi\}$ es satisfacible.
Que $\Gamma \cup \{\neg\varphi\}$ es satisfacible.
Que $\neg\varphi$ es insatisfacible.
Pregunta 3De unidades anterioresSi una valoración $v$ da a $\alpha$ el valor $1$ , ¿qué valor da a $(\alpha \downarrow \beta)$ ?
$0$ , cualquiera que sea el valor de $\beta$ .
Depende de $\beta$ : vale $1$ si $\beta$ vale $0$ .
$1 - v(\beta)$ .
$1$ , porque una de las componentes es verdadera.
Pregunta 4De unidades anterioresLas variables de $\varphi$ son $v_{2}$ y $v_{7}$ . Dos valoraciones $v$ y $w$ dan los mismos valores a $v_{2}$ y a $v_{7}$ , y valores opuestos a todas las demás variables. Si $v(\varphi) = 1$ , ¿qué puede afirmarse de $w(\varphi)$ ?
Que $w(\varphi) = 1$ .
Nada, porque $v$ y $w$ difieren en infinitas variables.
Que $w(\varphi) = 0$ , porque $w$ invierte casi todos los valores de $v$ .
Que $w(\varphi) = 1$ solo si $v$ y $w$ coinciden también en $v_{1}, \ldots, v_{6}$ .
Pregunta 5De unidades anterioresSea $\Gamma$ un conjunto infinito de fórmulas tal que $\Gamma \vdash \varphi$ . ¿Qué puede afirmarse?
Que algún subconjunto finito de $\Gamma$ deduce $\varphi$ .
Que $\varphi$ es un teorema.
Que la deducción usa todas las fórmulas de $\Gamma$ .
Nada sin el teorema de compacidad, porque $\Gamma$ es infinito.
Pregunta 6De unidades anterioresSe sabe que $\Gamma \cup \{p\} \vdash \chi$ y que $\Gamma \cup \{\neg p\} \vdash \chi$ . ¿Qué permite concluir la prueba por casos?
Que $\Gamma \vdash \chi$ .
Nada, mientras no se sepa si $\Gamma$ deduce $p$ o deduce $\neg p$ .
Que $\Gamma \vdash (p \leftrightarrow \chi)$ .
Solo que $\Gamma \cup \{p, \neg p\} \vdash \chi$ .
Pregunta 7El sistema del curso es correcto. ¿Qué afirma esa propiedad?
Que, para todo conjunto $\Gamma$ , si $\Gamma \vdash \varphi$ , entonces $\Gamma \models \varphi$ .
Que si $\Gamma \models \varphi$ , entonces $\Gamma \vdash \varphi$ .
Que no existe ninguna fórmula $\varphi$ con $\vdash \varphi$ y $\vdash \neg\varphi$ .
Que toda fórmula verdadera es un teorema.
Pregunta 8Sea $v$ la valoración que da $1$ a $p$ y $0$ a $q$ . ¿Qué afirma el lema de Kalmár, con las variables $p$ y $q$ , para la fórmula $(p \leftrightarrow q)$ ?
Que $\{p, \neg q\} \vdash \neg(p \leftrightarrow q)$ .
Que $\{p, \neg q\} \vdash (p \leftrightarrow q)$ .
Que $\{p, q\} \vdash \neg(p \leftrightarrow q)$ .
Que $\vdash \neg(p \leftrightarrow q)$ .
Pregunta 9¿Puede un sistema deductivo ser correcto sin ser completo?
Sí: el sistema de Łukasiewicz, sin la regla RDN, es correcto y no deduce la tautología $((v_{1} \downarrow v_{2}) \rightarrow \neg v_{1})$ .
No: la corrección y la completitud se infieren una de la otra.
No: un sistema cuyos axiomas son tautologías deduce todas las tautologías.
Sí, pero solo si el sistema es inconsistente.
Pregunta 10¿Qué afirma el teorema de compacidad?
Que un conjunto de fórmulas es satisfacible si y solo si todo subconjunto finito suyo es satisfacible.
Que un conjunto de fórmulas es satisfacible si y solo si cada una de sus fórmulas es satisfacible.
Que todo conjunto infinito de fórmulas es satisfacible.
Que un conjunto es satisfacible si algún subconjunto finito suyo lo es.
Pregunta 11Sea $\Gamma$ un conjunto infinito de fórmulas tal que $\Gamma \models \varphi$ . ¿Qué asegura la compacidad?
Que $\Gamma_{0} \models \varphi$ para algún subconjunto finito $\Gamma_{0}$ de $\Gamma$ .
Que $\varphi$ es consecuencia de alguna fórmula de $\Gamma$ tomada sola.
Que $\varphi$ es consecuencia de todo subconjunto finito de $\Gamma$ .
Que $\varphi$ es válida.
Pregunta 12La primera clase demuestra la completitud para conjuntos finitos de premisas. ¿Por qué no basta el carácter finito de la deducción para extenderla a un conjunto infinito $\Gamma$ ?
Porque el carácter finito habla de $\Gamma \vdash \varphi$ , y lo que se tiene es $\Gamma \models \varphi$ : hace falta que la consecuencia, no la deducción, se reduzca a una parte finita, y eso es la compacidad.
Sí basta: si $\Gamma \models \varphi$ , el carácter finito da un $\Gamma_{0}$ finito con $\Gamma_{0} \models \varphi$ .
Porque el lema de Kalmár no vale para fórmulas con infinitas variables.
Porque la completitud es falsa para conjuntos infinitos de premisas.
Pregunta 13¿Cuál es el resolvente de las cláusulas $\{p, \neg q, r\}$ y $\{q, s\}$ ?
$\{p, r, s\}$ .
$\{p, \neg q, r, q, s\}$ .
$\{p, r\}$ .
No tienen resolvente, porque no comparten ningún literal.
Pregunta 14Para decidir por resolución si $\{(p \vee q), \neg p\} \models q$ , ¿qué conjunto de cláusulas se intenta refutar?
$\{\{p, q\}, \{\neg p\}, \{\neg q\}\}$ .
$\{\{p, q\}, \{\neg p\}, \{q\}\}$ .
$\{\{p, q\}, \{\neg p\}\}$ .
$\{\{\neg p, \neg q\}, \{p\}, \{\neg q\}\}$ .
Pregunta 15¿Puede derivarse por resolución la cláusula vacía $\Box$ del conjunto $\{\{p, q\}, \{\neg p, \neg q\}\}$ ?
No: el conjunto es satisfacible, y la resolución es correcta.
Sí, en un solo paso, eliminando a la vez los dos pares complementarios.
Sí, en dos pasos: primero sobre $p$ y después sobre $q$ .
No, porque ninguna de las dos cláusulas es unitaria.