Saltar al contenido principal

# 10.8: El teorema de la integridad

$$\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}$$

Template:MathJaxZach

Teorema$$\PageIndex{1}$$: Completeness Theorem

$$\Gamma$$Dejen ser un conjunto de oraciones. Si$$\Gamma$$ es consistente, es satisfecha.

Prueba. Supongamos que$$\Gamma$$ es consistente. Por Lemma 10.4.1, hay un conjunto consistente saturado$$\Gamma' \supseteq \Gamma$$. Por Lemma 10.5.1, hay un$$\Gamma^* \supseteq {\Gamma'}$$ que es consistente y completo. Desde$$\Gamma' \subseteq \Gamma^*$$, for each formula $$A(x)$$, $$\Gamma^*$$ contains a sentence of the form $$\lexists{x}{A(x)} \lif A(c)$$ and so $$\Gamma^*$$ is saturated. If $$\Gamma$$ does not contain $$\eq[][]$$, then by Lemma 10.6.1,$$\Sat{M(\Gamma^*)}{A}$$ iff$$A \in \Gamma^*$$. De esto se deduce en particular que para todos$$A \in \Gamma$$,$$\Sat{M(\Gamma^*)}{A}$$, así$$\Gamma$$ es satisfecha. Si$$\Gamma$$ does contain $$\eq[][]$$, then by Lemma 10.7.1, for all sentences $$A$$, $$\Sat{\equivclass{M}{\approx}}{A}$$ iff $$A \in \Gamma^*$$. In particular, $$\Sat{\equivclass{M}{\approx}}{A}$$ for all $$A \in \Gamma$$, so $$\Gamma$$ is satisfiable.

Corolario$$\PageIndex{1}$$: Completeness Theorem, Second Version

Para todos$$\Gamma$$ y oraciones$$A$$: si$$\Gamma \Entails A$$ entonces$$\Gamma \Proves A$$.

Prueba. Obsérvese que los$$\Gamma$$'s en Corolario$$\PageIndex{1}$$ y Teorema$$\PageIndex{1}$$ están universalmente cuantificados. Para asegurarnos de que no nos confundimos, replanteemos el Teorema$$\PageIndex{1}$$ usando una variable diferente: para cualquier conjunto de oraciones$$\Delta$$, si$$\Delta$$ es consistente, es satisfecha. Por contraposición, si no$$\Delta$$ es satisfecha, entonces$$\Delta$$ es inconsistente. Utilizaremos esto para probar el corolario.

Supongamos que$$\Gamma \Entails A$$. Entonces no$$\Gamma \cup \{\lnot A\}$$ es satisfecha por la Proposición 5.14.2. Tomando$$\Gamma \cup \{\lnot A\}$$ como nuestro$$\Delta$$, la versión anterior del Teorema nos$$\PageIndex{1}$$ da que$$\Gamma \cup \{\lnot A\}$$ es inconsistente. Por las Proposiciones 8.9.2 y 9.8.2,$$\Gamma \Proves A$$. ◻

Problema$$\PageIndex{1}$$

Utilizar Corolario$$\PageIndex{1}$$ para probar el Teorema$$\PageIndex{1}$$, mostrando así que las dos formulaciones del teorema de integridad son equivalentes.

Problema$$\PageIndex{2}$$

Para que un sistema de derivación esté completo, sus reglas deben ser lo suficientemente fuertes como para demostrar que cada conjunto insatisfactable es inconsistente. ¿Cuáles de las reglas de derivación fueron necesarias para probar la integridad? ¿Alguna de estas reglas no se utiliza en ninguna parte de la prueba? Para responder a estas preguntas, hacer una lista o diagrama que muestre cuáles de las reglas de derivación se utilizaron en qué resultados conducen a la prueba del Teorema$$\PageIndex{1}$$. Asegúrese de anotar cualquier uso tácito de las reglas en estas pruebas.

This page titled 10.8: El teorema de la integridad is shared under a CC BY license and was authored, remixed, and/or curated by Richard Zach et al. (Open Logic Project) .