10.5: Lema de Lindenbaum

Última actualización
Guardar como PDF

Page ID: 103596

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

Ahora probamos un lema que demuestra que cualquier conjunto consistente de oraciones está contenido en algún conjunto de oraciones que no sólo es consistente, sino también completo. El comprobante funciona añadiendo una frase a la vez, garantizando en cada paso que el conjunto siga siendo consistente. Esto lo hacemos para que por cada$A$, ya sea$A$ o$\lnot A$ se añada en algún momento. La unión de todas las etapas en esa construcción contiene entonces una$A$ o su negación$\lnot A$ y es así completa. También es consistente, ya que nos aseguramos en cada etapa de no introducir una inconsistencia.

Lema$\PageIndex{1}$: Lindenbaum’s Lemma

Cada conjunto consistente$\Gamma$ en un idioma se$\Lang{L}$ puede extender a un conjunto completo y consistente$\Gamma^*$.

Comprobante. Que$\Gamma$ sean consistentes. Que$A_0$,$A_1$,... sea una enumeración de todas las oraciones de$\Lang L$. Definir$\Gamma_0 = \Gamma$, y\[\Gamma_{n+1} = \begin{cases} \Gamma_n \cup \{ A_n \} & \textrm{if $\Gamma_n \cup \{A_n\}$ is consistent;} \\ \Gamma_n \cup \{ \lnot A_n \} & \textrm{otherwise.} \end{cases}\nonumber\] dejar$\Gamma^* = \bigcup_{n \geq 0} \Gamma_n$.

Cada uno$\Gamma_n$ es consistente:$\Gamma_0$ es consistente por definición. Si$\Gamma_{n+1} = \Gamma_n \cup \{A_n\}$, esto se debe a que este último es consistente. Si no lo es,$\Gamma_{n+1} = \Gamma_n \cup \{\lnot A_n\}$. Tenemos que verificar que$\Gamma_n \cup \{\lnot A_n\}$ sea consistente. Supongamos que no lo es. Entonces ambos$\Gamma_n \cup \{A_n\}$ y$\Gamma_n \cup \{\lnot A_n\}$ son inconsistentes. Esto quiere decir que$\Gamma_n$ sería inconsistente por las Proposiciones 8.9.3 y 9.8.3, contrariamente a la hipótesis de inducción.

Para todos$n$ y cada uno$i < n$,$\Gamma_i \subseteq \Gamma_n$. Esto sigue por una simple inducción en$n$. Para$n=0$, no hay$i < 0$, por lo que el reclamo se mantiene automáticamente. Para el paso inductivo, supongamos que es cierto para$n$. Tenemos$\Gamma_{n+1} = \Gamma_n \cup \{A_n\}$ o$= \Gamma_n \cup \{\lnot A_n\}$ por construcción. Entonces$\Gamma_n \subseteq \Gamma_{n+1}$. Si$i < n$, entonces$\Gamma_i \subseteq \Gamma_n$ por hipótesis inductiva, y así$\subseteq \Gamma_{n+1}$ por transitividad de$\subseteq$.

De esto se deduce que cada subconjunto finito de$\Gamma^*$ es un subconjunto de$\Gamma_n$ para algunos$n$, ya que cada uno que$B \in \Gamma^*$ no ya$\Gamma_0$ está en se agrega en alguna etapa$i$. Si$n$ es el último de estos, entonces todos$B$ en el subconjunto finito están en$\Gamma_n$. Entonces, cada subconjunto finito de$\Gamma^*$ es consistente. Por las Proposiciones 8.8.5 y 9.7.5,$\Gamma^*$ es consistente.

Cada frase de$\Frm[L]$ aparece en la lista utilizada para definir$\Gamma^*$. Si$A_n \notin \Gamma^*$, entonces eso es porque$\Gamma_n \cup \{A_n\}$ era inconsistente. Pero entonces$\lnot A_n \in \Gamma^*$, así$\Gamma^*$ está completo. ◻