[ocultar]

Recuerden subir los archivos a Cuba-Wiki y no linkearlos de servidores externos, siempre siguiendo la convención de nombres descripta acá.

Diferencia entre revisiones de «Teorema de Compacidad»

De Cuba-Wiki
(soy pablo, no estoy logueado :S)
 
 
Línea 7: Línea 7:


Supongamos primero que vale el teorema de compacidad.
Supongamos primero que vale el teorema de compacidad.
Sea <math>\Gamma \subseteq Form</math> y <math>\alpha \in c(\Gamma)</math>. Entonces <math>\Gamma \cup \{\neg \alpha\}</math> es insatisfactible. Por el teorema existe <math>\hat\Gamma \subseteq \Gamma \cup \{\neg \alpha\}</math> finito e insatisfactible. Si <math>\hat\Gamma \subseteq \Gamma</math> entonces <math>\hat\Gamma \cup \{ \neg \alpha\} </math> es insatisfactible y luego <math>\alpha \in c(\hat\Gamma)</math>. Si no, <math>\hat\Gamma</math> contiene a <math>\neg \alpha</math>.
Sea <math>\Gamma \subseteq Form</math> y <math>\alpha \in c(\Gamma)</math>. Entonces <math>\Gamma \cup \{\neg \alpha\}</math> es insatisfactible. Por el teorema existe <math>\hat\Gamma \subseteq \Gamma \cup \{\neg \alpha\}</math> finito e insatisfactible.


<math>\hat\Gamma \cup \{\neg \alpha\} = \hat\Gamma</math>. También se llega a <math>\alpha \in c(\hat\Gamma)</math>.
*Si <math>\hat\Gamma \subseteq \Gamma</math> entonces <math>\hat\Gamma \cup \{ \neg \alpha\} </math> es insatisfactible y luego <math>\alpha \in c(\hat\Gamma)</math>.


<math>\hat\Gamma \setminus \{\neg \alpha\} \subseteq \Gamma</math> y <math>\hat\Gamma \setminus \{\neg \alpha\} \cup \{\neg \alpha\} = \hat\Gamma</math> es insatisfactible.
*Si no, <math>\hat\Gamma</math> contiene a <math>\neg \alpha</math>. <math>\hat\Gamma \cup \{\neg \alpha\} = \hat\Gamma</math>. También se llega a <math>\alpha \in c(\hat\Gamma)</math>: <math>\hat\Gamma \setminus \{\neg \alpha\} \subseteq \Gamma</math> y <math>\hat\Gamma \setminus \{\neg \alpha\} \cup \{\neg \alpha\} = \hat\Gamma</math> es insatisfactible.


Por lo tanto, <math>\alpha \in c(\hat\Gamma \setminus \{\neg \alpha\})</math>
Por lo tanto, <math>\alpha \in c(\hat\Gamma \setminus \{\neg \alpha\})</math>

Revisión actual - 04:24 5 oct 2006

Si Γ es un conjunto de fórmulas tal que todo subconjunto finito de Γ es satisfactible. Entonces Γ es satisfactible

El teorema es equivalente a la siguiente proposición:

  • Sea Γ un conjunto de fórmulas y α una fórmula. Si α es consecuencia lógica de Γ entonces existe un subconjunto finito Γ´ Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \subseteq} Γ tal que α es consecuencia lógica de Γ´

Prueba de la proposición

Supongamos primero que vale el teorema de compacidad. Sea Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Gamma \subseteq Form} y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \alpha \in c(\Gamma)} . Entonces Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \Gamma \cup \{\neg \alpha\}} es insatisfactible. Por el teorema existe Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \hat\Gamma \subseteq \Gamma \cup \{\neg \alpha\}} finito e insatisfactible.

  • Si Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \hat\Gamma \subseteq \Gamma} entonces Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \hat\Gamma \cup \{ \neg \alpha\} } es insatisfactible y luego Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \alpha \in c(\hat\Gamma)} .
  • Si no, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \hat\Gamma} contiene a Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \neg \alpha} . Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \hat\Gamma \cup \{\neg \alpha\} = \hat\Gamma} . También se llega a Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \alpha \in c(\hat\Gamma)} : Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \hat\Gamma \setminus \{\neg \alpha\} \subseteq \Gamma} y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \hat\Gamma \setminus \{\neg \alpha\} \cup \{\neg \alpha\} = \hat\Gamma} es insatisfactible.

Por lo tanto, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \alpha \in c(\hat\Gamma \setminus \{\neg \alpha\})}

Obtenido de «https://www.cubawiki.com.ar/index.php?title=Teorema_de_Compacidad&oldid=462»