¿Cuáles son las ideas básicas de la demostración estándar del lema de Lindenbaum?

Question

Tengo una pregunta sobre Lemma de Lindenbaum para la Lógica Propositiva:

Cualquier conjunto coherente $\Gamma$ de fórmulas es un subconjunto de un conjunto coherente máximo $\Gamma^{\prime}$ de fórmulas.

El esquema de la prueba (según el libro de Hunter) es el siguiente:

1. Por teorema de la enumeración una máquina puede mapear todo el conjunto de fórmulas proposicionales en el conjunto de números naturales; sea $\phi_n$ el $n^{th}$ fórmula en este sentido.

2. Definamos recursivamente la función $\Gamma_n$ como

   • $\Gamma_0=\Gamma$ ,
   • $\Gamma_{n+1}=\Gamma_n\cup \{\phi_{n+1}\}$ si $\Gamma_n\not{\vdash}\neg\phi_{n+1}$ y $\Gamma_{n+1}=\Gamma_n$ de lo contrario.

3. Dejemos que $\Gamma'$ sea la unión de $\Gamma_0, \Gamma_1, ..., \Gamma_n, ...$

4. etc.

Vale, lo he entendido. Pero aquí está mi problema:

1. Sería mejor si pudiéramos definir directamente $\Gamma^{\prime}$ como cualquier conjunto s.t. para cualquier fórmula $\phi$ :

   • si ninguno de los dos $\phi$ ni en $\neg\phi$ se puede deducir por $\Gamma$ entonces $\phi$ está en $\Gamma^{\prime}$ ;
   • si $\phi$ se puede deducir por $\Gamma$ entonces $\phi$ está en $\Gamma^{\prime}$
   • si $\neg\phi$ se puede deducir por $\Gamma$ entonces $\neg\phi$ está en $\Gamma^{\prime}$

   De hecho, con esta definición la afirmación del lema se verifica automáticamente. Pero, lo sé, algo está mal. Sin embargo, para "aceptar" esta prueba, necesito encontrar motivaciones de por qué no se puede acortar/simplificar.

2. ¿Son necesarios los pasos 1-3 porque no podemos asegurar de otra manera la existencia del conjunto $\Gamma^{'}$ ?

3. En caso afirmativo, ¿utilizamos el esquema de axiomas de sustitución en el paso 2 y el axioma de unión en el paso 3?

4. En caso afirmativo, ¿cuál es el caso concreto del esquema de axiomas de sustitución que estamos utilizando? En concreto, ¿cuál es el real, exacto ¿fórmula de primer orden que estamos considerando?

Observación. Sé que esto es un metateorema, y por lo tanto su metaprueba no depende estrictamente de ninguna teoría formal (como lo es ZFC), sin embargo es la mejor justificación actual para los pasos 1-3 que he encontrado. Pero no estoy absolutamente convencido de esto, realmente necesito su ayuda para entender.

Gracias.

Answer 1

Su conjunto $\Gamma'$ no funciona. Considere una fórmula $\phi$ de tal manera que ni $\phi$ ni $\neg \phi$ se puede deducir de $\Gamma$ . Entonces, según su definición, $\phi$ estará en $\Gamma'$ . Pero dejar que $\psi=\neg\phi$ También es cierto que ni $\psi$ ni $\neg\psi$ se puede deducir de $\Gamma$ . Así que $\psi$ también estará en $\Gamma'$ . Así que ambos $\phi\in\Gamma'$ y $\neg\phi\in\Gamma'$ y $\Gamma'$ no es coherente.

En términos más generales, aunque modifique su definición para evitar este problema específico, no hay garantía de que su conjunto $\Gamma'$ será coherente. Cada nueva fórmula que se añada será coherente con $\Gamma$ pero pueden no ser coherentes entre sí . Por eso es importante el procedimiento recursivo de los pasos 1-3, para garantizar que el conjunto $\Gamma'$ es realmente consistente. No tiene nada que ver con poder construir formalmente el conjunto.

En detalle, así es como se demuestra el conjunto $\Gamma'$ dado por los pasos 1-3 es consistente. Si fuera inconsistente, algún subconjunto finito $F\subseteq\Gamma'$ sería incoherente. Entonces, para algunos $n$ , $F\subseteq \Gamma_n$ . Pero podemos demostrar por inducción en $n$ que $\Gamma_n$ es consistente para todos los $n$ (ya que si $S\not\vdash \neg\phi$ entonces $S\cup\{\phi\}$ es coherente). Esto es una contradicción, y por lo tanto $\Gamma'$ es consistente.