Hay un "árbol" de la prueba del teorema de compacidad en el caso de una cantidad no numerable de variables?

Question

Me gusta pruebas usando árboles y König del lexema, ya que son muy visual.

Una de las aplicaciones de König del lexema puede mostrar a los estudiantes es demostrar el teorema de compacidad para el cálculo proposicional, que dice que un conjunto de fórmula es válido si y sólo si cada subconjunto finito es válido.

En esta prueba se tiene que el orden de las declaraciones en su teoría en una secuencia y el orden de las variables en consecuencia. A continuación, se construye un árbol en el que cada vértice corresponde a la verdad de los valores de las variables a partir de las declaraciones de $T_1,\dots,T_n$ y, a continuación, infinito rama le da la interpretación de todas las variables, lo cual es consistente con la teoría en su totalidad.

De esta manera usted puede probar que el teorema de compacidad, bajo el supuesto de que el conjunto de variables contables.

Hay una prueba en el espíritu similar que funciona arbitrarias de conjuntos de variables? (O alguna técnica que puede ser utilizada para obtener innumerables versión si ya tenemos contables versión?)

Estoy interesado principalmente en las pruebas de evitar el uso del teorema de completitud.

Answer 1

No conozco una manera de hacer la prueba de la proposición de compacidad, para innumerables conjuntos de fórmulas, parece un árbol de argumento. Pero si usted va de nuevo a cómo König del Lexema es generalmente demostrar y aplicar ese argumento para el árbol en particular que usted describe, el resultado del argumento proposicional compacidad generaliza bastante directamente, a la siguiente argumento.

Dado un conjunto $S$ de fórmulas proposicionales, bien de orden el conjunto de variables proposicionales que ocurren en estas fórmulas, y proceder por (transfinito) inducción sobre este pedido. Cuando el proceso inductivo llega a una variable $p$, se asigna un valor de verdad a $p$, con el fin de preservar la siguiente hipótesis inductiva:

(*) Para cualquier subconjunto finito $F$$S$, existe una verdad asignación que hace que $F$ cierto y está de acuerdo con todos los valores asignados hasta el momento en su proceso inductivo.

La hipótesis del teorema de compacidad es que (*) sostiene en el principio de su proceso, antes de que se les ha asignado valores a ninguna de las variables. Si (*) sostiene que cuando estás a punto de asignar un valor a $p$, entonces usted puede escoger el valor, a fin de mantener (*). La razón es que si el valor "verdadero" de $p$ no puede trabajar debido a una finito $F_1\subseteq S$ y "falso" falla porque de $F_2$, (*) ya fracasó antes de que usted le dio a $p$ cualquier valor de verdad, porque de $F_1\cup F_2$. También tienes que comprobar que (*) mantiene en el límite de las etapas, pero que es fácil, ya que cualquier fallo en un límite de la etapa, la participación de un número finito de $F$, por lo que sólo un número finito de variables, ya habría sido un fracaso en una etapa anterior.

Después de su inducción transfinita es completa, (*) dice que la verdad específica de los valores que hemos asignado a las variables de satisfacer a todos los subconjuntos finitos de $S$ y por lo tanto satisfacer $S$.

Answer 2

Aquí es una forma de demostrar la compacidad para la lógica proposicional en términos de los árboles. Como Andreas menciona en los comentarios, el árbol de la propiedad para $\omega$ no es suficiente. En su lugar, podemos utilizar una de dos cardenal variación del árbol de la propiedad.

Si $\kappa$ es regular el cardenal y $\lambda \ge \kappa$ $(\kappa,\lambda)$ árbol de $T$ es un conjunto de $2$valores de las funciones cuyos dominios son elementos de $\mathcal{P}_\kappa(\lambda)$ (es decir, subconjuntos de a $\lambda$ del tamaño de la $<\kappa$) tales que

• la restricción de cada función en $T$$T$, y
• cada elemento de a $\mathcal{P}_\kappa(\lambda)$ es el dominio de alguna función en $T$.

Un cofinal rama de $T$ es una función de $f:\lambda \to 2$ tal que $f \restriction s \in T$ por cada $s \in \mathcal{P}_\kappa(\lambda)$. Hay un principio TP$(\kappa,\lambda)$, aislado por Weiss, que dice que cada delgadas $(\kappa,\lambda)$ árbol tiene una rama. No necesitamos utilizar la definición de "fino", porque es automática si $\kappa = \omega$ o más en general, si $\kappa$ es un fuerte límite de cardenal.

Si $\kappa$ es fuertemente inaccesible cardenal, entonces TP$(\kappa,\lambda)$ mantiene si y sólo si $\kappa$ $\lambda$- compacto, por lo que es una gran cardenal de la propiedad. Sin embargo, TP$(\omega,\lambda)$ puede ser probado a mantener en ZFC: Tomar un ultrafilter $U$ $\mathcal{P}_\omega(\lambda)$ que es buena, lo que significa que contiene el conjunto de $\{s \in \mathcal{P}_\omega(\lambda) : \alpha \in s\}$ por cada $\alpha < \lambda$. Porque no estamos requiriendo cualquier cantidad de exhaustividad, una ultrafilter existe por el lema de Zorn. Dado un $(\omega,\lambda)$-árbol de $T$, seleccione para cada conjunto $s \in \mathcal{P}_\kappa(\lambda)$ alguna función $f_s \in T$ dominio $s$. Entonces podemos definir una rama de $f$ $T$ $f(\alpha) = 1$ si y sólo si $f_s(\alpha) = 1$ $U$- casi todos los $s \in \mathcal{P}_\omega(\lambda)$.

Ahora podemos utilizar este árbol de la propiedad de encontrar una verdad de la asignación de un conjunto $S$ de fórmulas proposicionales. Mediante la ampliación de las $S$ podemos asumir que es cerrado bajo subformulas y, en particular, que cada variable proposicional que aparecen en una fórmula en la $S$ es en sí mismo en $S$. Definir un $(\omega, S)$-árbol de $T$ que consta de todo en consonancia verdad tareas definidas en subconjuntos finitos $s$$S$. (Estrictamente hablando, debemos fijar un bijection entre el $S$ $|S|$ aquí). Por consecuente me refiero, por ejemplo, que si las fórmulas $\varphi$, $\psi$, y $\varphi \wedge \psi$ son todos en $s$, $\varphi \wedge \psi$ se asigna el valor de 1 si y sólo si ambas $\varphi$$\psi$. Suponiendo TP$(\omega,|S|)$, este árbol tiene una rama, una rama es una verdad de asignación que satisface todas las fórmulas en la $S$.