5 votos

Lógica intermedia y completitud algebraica fuerte

Como configuración, supongamos que tenemos un lenguaje proposicional habitual $\mathcal L$ sobre un conjunto de variables proposicionales $Var$ y con símbolos $\land,\lor,\rightarrow,\bot$ de la forma habitual. Dejemos que $L$ sea una lógica intermedia sobre $\mathcal L$ es decir, un conjunto de $\mathcal L$ -fórmulas que contienen lógica proposicional intuicionista $IPC$ , estando contenida en la lógica proposicional clásica $CPC$ y ser cerrado bajo modus ponens y sustitución de variables proposicionales.

Una semántica común para la lógica intermedia es a través de las álgebras de Heyting $\mathbf A$ y las evaluaciones correspondientes $f:Var\to\mathbf A$ que se extienden a todo el lenguaje proposicional utilizando las operaciones del álgebra de Heyting. Escribo $(\mathbf A,f)\models\phi$ para $\phi\in\mathcal L$ si el valor de $\phi$ en el marco de esta ampliación de $f$ en $\mathbf A$ es el elemento superior del álgebra de Heyting. Además, escribo $(\mathbf A,f)\models\Gamma$ para $\Gamma\subseteq\mathcal L$ si $(\mathbf A,f)\models\gamma$ para todos $\gamma\in\Gamma$ .

Mi pregunta es si cada lógica intermedia $L$ tiene un teorema de completitud algebraica fuerte, con respecto a alguna clase de álgebras de Heyting, en el sentido de lo siguiente: ¿existe una clase de álgebras de Heyting $\mathsf C$ (en relación con $L$ ) tal que

$$\Gamma\vdash_L\phi\text{ iff }\forall\mathbf A\in\mathsf C\forall f:Var\to\mathbf A:(\mathbf A,f)\models\Gamma\Rightarrow (\mathbf A,f)\models\phi?$$

3voto

Mark Kamsma Puntos 371

Sí, podemos hacerlo, e incluso de una forma muy precisa. Este es un resultado bien conocido, pero por alguna razón no conozco directamente una buena referencia para esto (¿alguien?). Así que sería bueno tener esto por escrito.


La mayoría de nuestras herramientas y definiciones provienen del ámbito del álgebra universal, pero sólo nos interesará la parte de las álgebras de Heyting.

Definición. A variedad es una clase de álgebras que satisfacen un conjunto fijo de ecuaciones.

En particular, para el lenguaje de las álgebras de Heyting, se trata de un conjunto de expresiones de la forma $\varphi = \psi$ . Donde $\varphi$ y $\psi$ son fórmulas proposicionales y esta expresión debe interpretarse como "cuando asignamos elementos de nuestra álgebra (Heyting) a las variables proposicionales, entonces $\varphi$ y $\psi$ debe evaluarse al mismo elemento en nuestra álgebra (de Heyting)". Si cada álgebra de la variedad es un álgebra de Heyting, entonces $\varphi = \psi$ equivale a $\varphi \leftrightarrow \psi = \top$ . Por lo tanto, podemos suponer que las ecuaciones son de la última forma.

La clase de álgebras de Heyting es una variedad: es precisamente la clase de álgebras que satura $IPC$ .

Definición. Dejemos que $\mathsf{HA}$ denotan la variedad de álgebras de Heyting. Para un álgebra de Heyting $A$ , escriba $A \models \varphi$ si $\varphi$ evuala al elemento superior para cada evaluación en $A$ .

Para una subvariedad $V \subseteq \mathsf{HA}$ y una fórmula proposicional $\varphi$ escribimos $V \models \varphi$ si $A \models \varphi$ por cada $A \in V$ . Definimos $$ L_V = \{\varphi \in \mathcal{L} : V \models \varphi \}. $$

Desde $V \subseteq \mathsf{HA}$ se comprueba fácilmente que $L_V$ es una lógica intermedia.

Definición. Dada una lógica intermedia $L$ dejamos que $V_L$ sea la variedad correspondiente al conjunto de ecuaciones $\{ \varphi = \top : \varphi \in L \}$ .

Por construcción $V_L \models L$ y $V_L \subseteq \mathsf{HA}$ . Además, debe quedar claro que para $V \subseteq V'$ tenemos $L_V \supseteq L_{V'}$ . Y para $L \supseteq L'$ tenemos $V_L \subseteq V_{L'}$ .

Teorema. Las operaciones $L \mapsto V_L$ y $V \mapsto L_V$ son inversos entre sí.

En particular, si dejamos que $\mathcal{H}$ sea la colección de todas las subvariedades de $\mathsf{HA}$ y dejamos que $\mathcal{I}$ sea la colección de lógicas intermedias. Entonces los órdenes parciales $(\mathcal{H}, \subseteq)$ y $(\mathcal{I}, \supseteq)$ son isomorfas.

Lo siguiente será útil en la demostración del teorema.

Definición. Para una lógica intermedia $L$ , dejemos que $A_L$ sea el álgebra de Heyting definida como sigue. Sus elementos son clases de equivalencia de fórmulas proposicionales, donde las fórmulas $\varphi$ y $\psi$ son equivalentes si $\varphi \leftrightarrow \psi \in L$ . Denote por $[\varphi] \in A_L$ la clase de equivalencia de $\varphi$ . La orden sobre $A_L$ viene dada por $[\varphi] \leq [\psi]$ si $\varphi \to \psi \in L$ . Llamamos $A_L$ el Álgebra de Lindenbaum-Tarski para $L$ .

Tenga en cuenta que $A_L \models L$ Así que, en particular $A_L \in V_L$ .

Prueba del teorema. Primero demostramos $L = L_{V_L}$ . Desde $V_L \models L$ tenemos $L \subseteq L_{V_L}$ . Para $\varphi \in L_{V_L}$ debemos tener $V_L \models \varphi$ y, por lo tanto, en particular $A_L \models \varphi$ . S $[\varphi] = [\top]$ en $A_L$ y por lo tanto $\varphi \in L$ .

Ahora demostramos $V = V_{L_V}$ . Sea $A \in V$ entonces $A \models L_V$ por lo que $A \in V_{L_V}$ . Para la otra inclusión, dejemos $\Sigma$ sea un conjunto de ecuaciones tales que $V$ consiste en todas aquellas álgebras que satisfacen $\Sigma$ . Entonces $\Sigma \subseteq L_V$ . Por lo tanto, para $A \in V_{L_V}$ tenemos $A \models \Sigma$ y por lo tanto $A \in V$ . Esto completa la prueba.

Nota. No he excluido la variedad trivial que contiene el álgebra degenerada (formada por un solo punto). Esto corresponde a la lógica inconsistente. Si quieres considerar sólo las lógicas consistentes (es decir, las lógicas contenidas en $CPC$ ), entonces en el otro lado tenemos que restringir a todas las variantes que contienen la variedad de álgebras booleanas.


En su pregunta original también aparece un $\Gamma$ . Sin embargo, esto no es realmente hacer nada. Para una lógica intermedia $L$ , dejemos que $\langle L, \Gamma \rangle$ sea la lógica intermedia generada por $L$ y $\Gamma$ (es decir, la intersección de todas las lógicas intermedias que contienen tanto $L$ y $\Gamma$ ). Entonces tenemos $\Gamma \vdash_L \varphi$ si $\emptyset \vdash_{\langle L, \Gamma \rangle} \varphi$ . Así que la clase que le interesa es la variedad $V_{\langle L, \Gamma \rangle}$ .

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X