10.9: El teorema de la compacidad
- Page ID
- 103562
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Una consecuencia importante del teorema de la completitud es el teorema de la compacidad. El teorema de la compacidad establece que si cada subconjunto finito de un conjunto de oraciones es satisfacible, todo el conjunto es satisfecho, incluso si el conjunto en sí es infinito. Esto está lejos de ser obvio. No hay nada que parezca descartar, al menos a primera vista, la posibilidad de que existan infinitos conjuntos de oraciones que son contradictorias, pero la contradicción sólo surge, por así decirlo, del número infinito. El teorema de la compacidad dice que tal escenario puede descartarse: no hay conjuntos infinitos insatisfactorios de oraciones cada subconjunto finito de las cuales es satisfacible. Al igual que el teorema de la integridad, tiene una versión relacionada con la vinculación: si un conjunto infinito de oraciones conlleva algo, ya un subconjunto finito sí lo hace.
Definición\(\PageIndex{1}\)
Un conjunto\(\Gamma\) de fórmulas es finitamente satisfactorio si y solo si cada finito\(\Gamma_0 \subseteq \Gamma\) es satisfacible.
Teorema\(\PageIndex{1}\): Compactness Theorem
Se mantienen las siguientes sentencias\(\Gamma\) y\(A\):
-
\(\Gamma \Entails A\)si hay un finito\(\Gamma_0 \subseteq \Gamma\) tal que\(\Gamma_0 \Entails A\).
-
\(\Gamma\)es satisfecha si y sólo si es finitamente satisfecha.
Prueba. Demostramos (2). Si\(\Gamma\) es satisfecha, entonces hay una estructura\(\Struct{M}\) tal que\(\Sat{M}{A}\) para todos\(A \in \Gamma\). Por supuesto, esto\({\Struct{M}}\) también satisface cada subconjunto finito de\(\Gamma\), por lo que\(\Gamma\) es finitamente satisfactorio.
Ahora supongamos que eso\(\Gamma\) es finitamente satisfactorio. Entonces cada subconjunto finito\(\Gamma_0 \subseteq \Gamma\) es satisfacible. Por solidez (Corolarios 9.11.2 y 8.12.3), cada subconjunto finito es consistente. Entonces\(\Gamma\) sí mismo debe ser consistente por las Proposiciones 8.8.5 y 9.7.5. Por completitud (Teorema 10.8.1), ya que\(\Gamma\) es consistente, es satisfacible. ◻
Problema\(\PageIndex{1}\)
Demostrar (1) del Teorema\(\PageIndex{1}\).
Ejemplo\(\PageIndex{1}\)
En cada modelo\(\Struct{M}\) de una teoría\(\Gamma\), cada término por\(t\) supuesto escoge un elemento de\(\Domain{M}\). ¿Podemos garantizar que también es cierto que cada elemento de\(\Domain{M}\) es escogido por algún término u otro? En otras palabras, ¿existen teorías que cubran\(\Gamma\) todos los modelos? El teorema de compacidad demuestra que este no es el caso si\(\Gamma\) tiene infinitos modelos. He aquí cómo ver esto: Dejemos\(\Struct{M}\) ser un modelo infinito de\(\Gamma\), y dejemos\(c\) ser un símbolo constante no en el lenguaje de\(\Gamma\). \(\Delta\)Sea el conjunto de todas las oraciones\(\eqN[c][t]\) para\(t\) un término en el lenguaje\(\Lang{L}\) de\(\Gamma\), es decir,\[\Delta = \Setabs{\eqN[c][t]}{t \in \Trm[L]}.\nonumber\] Un subconjunto finito de se\(\Gamma \cup \Delta\) puede escribir como\(\Gamma' \cup \Delta'\), con\(\Gamma' \subseteq \Gamma\) y\(\Delta' \subseteq \Delta\). Dado que\(\Delta'\) es finito, puede contener sólo finitamente muchos términos. Dejar\(a \in \Domain{M}\) ser un elemento de\(\Domain{M}\) no escogido por ninguno de ellos, y dejar\(\Struct{M'}\) ser la estructura que es igual\(\Struct{M}\), pero también\(\Assign{c}{M'} = a\). Ya que\(a \neq \Value{t}{M}\) para todos\(t\) ocurriendo en\(\Delta'\),\(\Sat{M'}{\Delta'}\). Ya que\(\Sat{M}{\Gamma}\)\(\Gamma' \subseteq \Gamma\),, y\(c\) no ocurre en\(\Gamma\), también\(\Sat{M'}{\Gamma'}\). Juntos,\(\Sat{M'}{\Gamma' \cup \Delta'}\) por cada subconjunto finito\(\Gamma' \cup \Delta'\) de\(\Gamma \cup \Delta\). Entonces cada subconjunto finito de\(\Gamma \cup \Delta\) es satisfacible. Por compacidad,\(\Gamma \cup \Delta\) en sí mismo es satisfecha. Entonces hay modelos\(\Sat{M}{\Gamma \cup \Delta}\). Cada tal\(\Struct{M}\) es un modelo de\(\Gamma\), pero no está cubierto, ya que\(\Value{c}{M} \neq \Value{t}{M}\) para todos los términos\(t\) de\(\Lang{L}\).
Ejemplo\(\PageIndex{2}\)
Considere un lenguaje\(\Lang{L}\) que contenga el símbolo predicado\(<\), símbolos constantes\(\Obj{0}\)\(\Obj{1}\), y símbolos de función\(+\),\(\times\),\(-\),\(\div\). Que\(\Gamma\) el conjunto de todas las oraciones en este lenguaje sean verdaderas en\(\Struct{Q}\) con dominio\(\Rat\) y las obvias interpretaciones. \(\Gamma\)es el conjunto de todas las oraciones de\(\Lang{L}\) verdad sobre los números racionales. Por supuesto, en\(\Rat\) (e incluso en\(\Real\)), no hay números que sean mayores que\(0\) pero menores que\(1/k\) para todos\(k \in \PosInt\). Tal número, si existiera, sería un infinitesimal: distinto de cero, pero infinitamente pequeño. El teorema de compacidad muestra que hay modelos de\(\Gamma\) en los que existen infinitesimales: Let\(\Delta\) be\(\{0<c\} \cup \Setabs{c < (\Obj{1} \div \num{k})}{k \in \PosInt}\) (donde\(\num{k} = (\Obj{1} + (\Obj{1} + \dots + (\Obj{1} + \Obj{1})\dots))\)\(k\)\(\Obj{1}\) con's). Para cualquier subconjunto finito\(\Delta_0\) de\(\Delta\) existe\(K\) tal que todas las oraciones\(c < (\Obj{1} \div \num{k})\) en\(\Delta_0\) tienen\(k < K\). Si nos expandimos\(\Struct{Q}\) a\(\Struct{Q'}\) con eso\(\Assign{c}{Q'} = 1/K\) tenemos\(\Sat{Q'}{\Gamma \cup \Delta_0}\), y así\(\Gamma \cup \Delta\) es finitamente satisfactorio (Ejercicio: probar esto en detalle). Por compacidad,\(\Gamma \cup \Delta\) es satisfacible. Cualquier modelo\(\Struct{S}\) de\(\Gamma \cup \Delta\) contiene un infinitesimal, a saber\(\Assign{c}{S}\).
Problema\(\PageIndex{2}\)
En el modelo estándar de aritmética\(\Struct{N}\), no hay ningún elemento\(k \in \Domain{N}\) que satisfaga cada fórmula\(\num{n} < x\) (donde\(\num{n}\) está\(\Obj{0}^{\prime\dots\prime}\)\(n\)\(\prime\) con's). Utilice el teorema de compacidad para mostrar que el conjunto de oraciones en el lenguaje de la aritmética que son verdaderas en el modelo estándar de la aritmética también\(\Struct{N}\) son verdaderas en una estructura\(\Struct{N'}\) que contiene un elemento que sí satisface cada fórmula \(\num{n} < x\).
Ejemplo\(\PageIndex{3}\)
Sabemos que la lógica de primer orden con predicado de identidad puede expresar que el tamaño del dominio debe tener algún tamaño mínimo: La oración\(A_{\ge n}\) (que dice “hay al menos objetos\(n\) distintos”) es verdadera solo en estructuras donde\(\Domain{M}\) tiene al menos \(n\)objetos. Entonces si tomamos\[\Delta = \Setabs{A_{\ge n}}{n \ge 1}\nonumber\] entonces cualquier modelo de\(\Delta\) debe ser infinito. Así, podemos garantizar que una teoría sólo tiene infinitos modelos\(\Delta\) añadiéndole: los modelos de\(\Gamma \cup \Delta\) son todos y sólo los modelos infinitos de\(\Gamma\).
Entonces la lógica de primer orden puede expresar infinitud. El teorema de la compacidad demuestra que no puede expresar finitud, sin embargo. Por supongamos que algún conjunto de oraciones\(\Lambda\) se satisfizo en todas y sólo estructuras finitas. Entonces\(\Delta \cup \Lambda\) es finitamente satisfecha. ¿Por qué? Supongamos que\(\Delta' \cup \Lambda' \subseteq \Delta \cup \Lambda\) es finito con\(\Delta' \subseteq \Delta\) y\(\Lambda' \subseteq \Lambda\). \(n\)Sea el mayor número tal que\(A_{\ge n} \in \Delta'\). \(\Lambda\), satisfecha en todas las estructuras finitas, tiene un modelo\(\Struct{M}\) con finitamente muchos pero\(\ge n\) elementos. Pero entonces\(\Sat{M}{\Delta' \cup \Lambda'}\). Por compacidad,\(\Delta \cup \Lambda\) tiene un modelo infinito, contradiciendo la suposición que sólo\(\Lambda\) se satisface en estructuras finitas.