10.3: Completar Conjuntos Consistentes de Sentencias

Última actualización
Guardar como PDF

Page ID: 103587

\( \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}}\)

Template:MathJaxZach

Definición\(\PageIndex{1}\): Complete set

Un conjunto\(\Gamma\) de oraciones es completo iff para cualquier oración\(A\), ya sea\(A \in \Gamma\) o\(\lnot A \in \Gamma\).

Los juegos completos de oraciones no dejan preguntas sin respuesta. Para cualquier frase\(A\),\(\Gamma\) “dice” si\(A\) es verdadera o falsa. La importancia de los conjuntos completos se extiende más allá de la prueba del teorema de la completitud. Una teoría completa y axiomatizable, por ejemplo, siempre es decidible.

Los conjuntos consistentes completos son importantes en la prueba de integridad ya que podemos garantizar que cada conjunto consistente de oraciones\(\Gamma\) esté contenido en un conjunto consistente completo\(\Gamma^*\). Un conjunto consistente completo contiene, para cada oración\(A\), una\(A\) o su negación\(\lnot A\), pero no ambas. Esto es cierto en particular para las oraciones atómicas, por lo que a partir de un conjunto consistente completo en un lenguaje adecuadamente expandido por símbolos constantes, podemos construir una estructura donde se defina la interpretación de los símbolos predicados según la cual las oraciones atómicas están en\(\Gamma^*\). Esta estructura puede entonces mostrarse para hacer verdaderas todas las oraciones en\(\Gamma^*\) (y por lo tanto también todas las de\(\Gamma\)). La prueba de este último hecho requiere que\(\lnot A \in \Gamma^*\) iff\(A \notin \Gamma^*\),\((A \lor B) \in \Gamma^*\) iff\(A \in \Gamma^*\) o\(B \in \Gamma^*\), etc.

En lo que sigue, a menudo utilizaremos tácitamente las propiedades de reflexividad, monotonicidad y transitividad de\(\Proves\) (ver secciones 8.8 y 9.7).

Proposición\(\PageIndex{1}\)

Supongamos que\(\Gamma\) es completo y consistente. Entonces:

Si\(\Gamma \Proves A\), entonces\(A \in \Gamma\).
\(A \land B \in \Gamma\) iff both \(A \in \Gamma\) and \(B \in \Gamma\).
\(A \lor B \in \Gamma\) iff either \(A \in \Gamma\) or \(B \in \Gamma\).
\(A \lif B \in \Gamma\) iff either \(A \notin \Gamma\) or \(B \in \Gamma\).

Comprobante. Supongamos por todo lo siguiente que\(\Gamma\) es completo y consistente.

Si\(\Gamma \Proves A\), entonces\(A \in \Gamma\).

Supongamos que\(\Gamma \Proves A\). Supongamos que al contrario eso\(A \notin \Gamma\). Ya que\(\Gamma\) está completo,\(\lnot A \in \Gamma\). Por las Proposiciones 8.9.3 y 9.8.3,\(\Gamma\) es inconsistente. Esto contradice la suposición que\(\Gamma\) es consistente. De ahí que no pueda darse el caso de que\(A \notin \Gamma\), así\(A \in \Gamma\).
Ejercicio.
Primero demostramos que si\(A \lor B \in \Gamma\), entonces cualquiera\(A \in \Gamma\) o\(B \in \Gamma\). Supongamos\(A \lor B \in \Gamma\) pero\(A \notin \Gamma\) y\(B \notin \Gamma\). Ya que\(\Gamma\) está completo,\(\lnot A \in \Gamma\) y\(\lnot B \in \Gamma\). Por las Proposiciones 8.10.2 y 9.9.2, el ítem (1),\(\Gamma\) es inconsistente, una contradicción. De ahí, ya sea\(A \in \Gamma\) o\(B \in \Gamma\).

Para la dirección inversa, supongamos que\(A \in \Gamma\) o\(B \in \Gamma\). Por las Proposiciones 8.10.2 y 9.9.2, ítem (2),\(\Gamma \Proves A \lor B\). Por (1),\(A \lor B \in \Gamma\), según se requiera.
Ejercicio.

◻

Problema\(\PageIndex{1}\)

Completar el comprobante de Proposición\(\PageIndex{1}\).