Diferencia entre revisiones de «Teorema de Compacidad»
(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 | 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\} | *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[editar]
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\})}
