64 votos

¿Por qué es compacticidad en lógica llamado compacidad?

En lógica, una semántica que se dice para ser compacto iff si cada subconjunto finito de un conjunto de oraciones tiene un modelo, entonces para qué todo el conjunto.

La mayoría de la lógica de los textos no explicar la terminología, o que aluden a la topológico de la propiedad de compacidad. Veo una analogía como, dado un espacio topológico X y un subconjunto de S, S es compacto si para cada abierto de la cubierta de S, hay un número finito de subcover de S. Pero, no parece lo suficientemente fuerte como para justificar la terminología.

Hay más en la elección de la terminología en la lógica de esta analogía?

11voto

Judah Himango Puntos 27365

La analogía con el teorema de compacidad para proposicional, el cálculo es como sigue. Deje de $p_i $ ser variables proposicionales; juntos, que toma valores en el espacio del producto $2^{\mathbb{N}}$. Supongamos que tenemos una colección de declaraciones de $S_t$ en estas variables booleanas tal que cada subconjunto finito es válido. Entonces yo reclamo que podemos demostrar que todos ellos son simultáneamente conste que mediante el uso de una compacidad argumento.

Deje que $F$ ser un conjunto finito. Entonces el conjunto de toda la verdad de asignaciones (esto es un subconjunto de $2^{\mathbb{N}}$) que satisfacen $S_t$ para $t \in F$ es un conjunto cerrado $V_F$ de asignaciones de la satisfacción de las sentencias de $F$. La intersección de cualquiera de un número finito de la $V_F$ es no vacío, así que por la intersección finita de la propiedad, la intersección de todos ellos es no vacío (ya que el espacio del producto es compacto), de donde alguna verdad en esta intersección satisface todas las declaraciones.

No sé cómo funciona esto en la lī ogica.

8voto

sickgemini Puntos 2001

Un lema que se relaciona con el (y a veces es cierto) es que "las pruebas son finitos". En la mayoría de los sistemas de lógica bajo consideración, la declaración y una prueba de la declaración son finitos cadenas de símbolos. Uno puede pensar en ellos como "compacto" representados. Qué bueno entonces que en algunos sistemas se va a permitir siempre una prueba para encontrar si es que hay uno. Mientras esto no se dé una estrecha relación con la topología, se sugiere (y hay que trabajar esto a través de su propio ser convencido) de que ciertos infinito anormalidades (como un infinito prueba) no se producirá. Una similar topológico reclamo es que, para compact establece, de una infinita cadena inclusive de ciertos subconjuntos tienen intersección no vacía, tal afirmación fácilmente visible a false para algunos no-compacto de conjuntos, tales como la colección { C_n | C_n = {x | x >= n y x es un número real } para n un entero no negativo } .

6voto

Dour High Arch Puntos 11896

Lema: Un espacio topológico $X$ es compacto si y sólo si para cada una de las colecciones de $\mathcal{C}$ de conjuntos cerrados con la intersección finita de la propiedad tiene intersección no vacía sobre la colección.

La proposición: $\mathbb{M}(\mathcal{L})$ es compacto si y sólo si cada finitely conste que $\mathcal{L}$-teoría es válido.

Prueba: Consideremos el espacio de $\mathbb{M}(\mathcal{L})=\{\Phi \; | \; \Phi \; \text{es una máxima} \; \mathcal{L} \text{-teoría}\}$. Por cada $\mathcal{L}$la sentencia $\varphi$ let $[(\varphi)]=\{ \Phi \in \mathbb{M}(\mathcal{L}) \; | \; \varphi \en \Phi\}$. Una subbase de $\cal{B}$ para una topología en $\mathbb{M}(\mathcal{L})$ es dada por los conjuntos $[(\varphi)]$. Es decir, el abrir los subconjuntos de $\mathbb{M}(\mathcal{L})$ es la unión de las intersecciones finitas de elementos de $\mathcal{B}$. A ver que $\mathcal{B}$ define una topología en cuenta que $[(\forall x(x\neq x))]=\emptyset$ y $[(\forall x(x=x))]=\mathbb{M}(\mathcal{L})$. Además, arbitraria sindicatos ya están definidas para estar en la topología y finito intersecciones en la topología desde $[(\varphi)]\cap [(\theta)]=[(\varphi \wedge \theta)]$, que se define a ser abierto.

Asumir la lógica de la compacidad. Tenga en cuenta que $\bigcap_{i\in I} [(\varphi_i)]=\emptyset$ si y sólo si no es válido. Deje que $\mathcal{C}$ ser una subcolección de la subbasis de la topología de $\mathbb{M}(\mathcal{L})$, con la intersección finita de la propiedad. A continuación, cada subconjunto finito de $\mathcal{C}$ es válido y por el teorema de compacidad esto implica $\bigcap [(\varphi)]$ que se extiende sobre todos los elementos de $\cal{C}$ es válido, por lo tanto $$ \bigcap_{[(\varphi)] \en \cal{B}} [(\varphi)]\neq \emptyset. $$ Por lo tanto $\mathbb{M}(\mathcal{L})$ es compacto.

Se asume que $\mathbb{M}(\mathcal{L})$ es compacto. Deje que $\Phi$ ser $\mathcal{L}$-teoría en la que se finitely conste. Deje que $\mathcal{C}_\Phi=\{[(\varphi)] \; | \; \varphi \en \Phi\}$. Todos los elementos de $\mathcal{C}_\Phi$ es cerrado y cada subconjunto finito de $\mathcal{C}_\Phi$ tiene intersección no vacía desde $\Phi$ es finitely conste. Desde $\mathbb{M}(\mathcal{L})$ es compacto, $\bigcap_{\varphi \en \Phi} [(\varphi)]\neq\emptyset$, por lo tanto es válido. $\square$

5voto

Ray Puntos 22127

Hasta donde yo sé, el enlace proviene de la teoría sintáctica. Se proporciona un conjunto de símbolos de la sentencia de F = {f_i} y se le permite permite la formación de complejos declaraciones uso de ellos. Usted puede combinar la primaria declaraciones con Y, O, NO los operadores y paréntesis, en la forma usual.

Así se obtiene un conjunto X de oraciones compuestas, como

(f Y g) O (NO h)

o algo como eso.

Sintáctico versión del teorema de compacidad de los estados, el siguiente.

Supongamos que para cada subconjunto finito Y de X puede asignar valores de verdad a la f_i de tal manera que todas las sentencias en la forma Y son verdaderas. Lo que usted puede hacer lo mismo para X.

Prueba

Considerar el espacio topológico Un obtenidas por tomar el producto de {0, 1} en el conjunto F. La topología en Una es el producto de la topología. Por el teorema de Tychonoff, a es compacto. Para cada compuesto declaración de s, el conjunto de verdad de los valores que hacen de cierto s es finito intersección de los cilindros, por lo tanto es un conjunto cerrado de A. La hipótesis de decir que cada finito intersección de estos conjuntos cerrados, para s que van en X, no está vacía. Por tanto, la intersección de todos esos conjunto cerrado no está vacía, lo que significa que uno puede hacer todas las declaraciones en X cierto.

3voto

CodingWithoutComments Puntos 9412

El Teorema de Compacidad es equivalente a la compacidad de la Piedra espacio de Lindenbaum–Tarski álgebra de primer orden lenguaje L. (Este es también el espacio de 0-tipos sobre el vacío de la teoría.)

Un punto en la Piedra espacio SL es una teoría completa de T en el lenguaje L. Es decir, T es un conjunto de oraciones de L , que es cerrado bajo deducción lógica y contiene exactamente una de σ σ o para cada frase σ de la lengua. La topología en el conjunto de tipos tiene por base el abierto de conjuntos U(σ) = {T: σ ∈ T} para cada frase σ de L. Nota que estos son todos los clopen establece desde U(σ) es complementaria a la de U(σ).

Para ver cómo el Teorema de Compacidad implica la compacidad de SL, supongamos que el open básica de conjuntos Ui), i ∈ I, forma una cubierta de SL. Esto significa que cada teoría completa de T contiene al menos una de las frases σyo. Yo reclamo que esta portada tiene un número finito de subcover. Si no, entonces el conjunto {σi: i ∈ I} es finitely coherente. Por el Teorema de Compacidad, el conjunto coherente y, por tanto (por el Lema de Zorn) está contenida en un máximo conjunto coherente T. Esta teoría T es un punto de la Piedra espacio que no está contenida en ninguna Ui), lo que contradice nuestra hipótesis de que el Ui), i ∈ I, forma una cubierta del espacio.

Para ver cómo la compacidad de SL implica el Teorema de Compacidad, supongamos que {σi: i ∈ I} es un conjunto inconsistente de las sentencias en L. Entonces Ui), i ∈ I, forma una cubierta de SL. Esta cubierta tiene un número finito de subcover, que corresponde a un número finito inconsistente subconjunto de {σi: i ∈ I}. Por lo tanto, cada inconsistente conjunto tiene un número finito de incoherente subconjunto, que es el contrapositivo de el Teorema de Compacidad.

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: