5.2: El lenguaje, la estructura y los axiomas del N

Última actualización
Guardar como PDF

Page ID: 113543

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

Trabajamos en el lenguaje de la teoría de números

\[\mathcal{L}_{NT} = \{ 0, S, +, \cdot, E, < \},\]

y seguiremos trabajando en este idioma para los dos capítulos siguientes. \(\mathfrak{N}\)es el modelo estándar de los números naturales,

\[\mathfrak{N} = \left( \mathbb{N}, 0, S, +, \cdot, E, < \right),\]

donde las funciones y relaciones son las funciones estándar y las relaciones sobre los números naturales.

Ahora estableceremos un conjunto de axiomas no lógicos,\(N\). Notarás que los axiomas son claramente oraciones que son verdaderas en la estructura estándar, y así si\(T\) es algún conjunto de axiomas tal que\(T \vdash \sigma\) para todos\(\sigma\) tales que\(\mathfrak{N} \models \sigma\), entonces\(T \vdash N\). Entonces, como demostramos de que se pueden derivar varios tipos de fórmulas\(N\), recordemos que esas mismas fórmulas también son derivables de cualquier conjunto de axiomas que tenga alguna esperanza de proporcionar una axiomatización de los números naturales.

El sistema de axiomas\(N\) se introdujo en el Ejemplo 2.8.3 y se reproduce aquí. Estos 11 axiomas establecen algunos de los hechos básicos sobre la función sucesora, la suma, la multiplicación, la exponenciación y el\(<\) ordenamiento sobre los números naturales.

Chaf: Para ser honestos, aquí no se necesitan el símbolo\(E\) y los axiomas sobre la exponenciación. Es posible hacer todo lo que hacemos en los próximos capítulos definiendo la exponenciación en términos de multiplicación, e introduciendo\(E\) como abreviatura en el idioma. Esto tiene la ventaja de mostrar de manera más explícita lo poco que se necesita para probar los teoremas de incompletitud, pero agrega algunas complicaciones a la exposición. Hemos decidido introducir la exponenciación explícitamente y añadir un par de axiomas, que nos permitirán movernos un poco más limpiamente a través de las pruebas de nuestros teoremas.

Los axiomas de\(N\)

\[\begin{align} &1. \left( \forall x \right) \neg Sx = 0. \\ &2. \left( \forall x \right) \left( \forall y \right) \left[ Sx = Sy \rightarrow x = y \right]. \\ &3. \left( \forall x \right) x + 0 = x. \\ &4. \left( \forall x \right) \left( \forall y \right) x + Sy = S \left( x + y \right). \\ &5. \left( \forall x \right) x \cdot 0 = 0. \\ &6. \left( \forall x \right) \left( \forall y \right) x \cdot Sy = \left( x \cdot y \right) + x. \\ &7. \left( \forall x \right) xE0 = S0. \\ &8. \left( \forall x \right) \left( \forall y \right) xE \left( Sy \right) = \left( xEy \right) \cdot x. \\ &9. \left( \forall x \right) \neg x < 0. \\ &10. \left( \forall x \right) \left( \forall y \right) \left[ x < Sy \leftrightarrow \left( x < y \lor x = y \right) \right].\\ &11. \left( \forall x \right) \left( \forall y \right) \left[ \left( x < y \right) \lor \left( x = y \right) \lor \left( y < x \right) \right]. \end{align}\]

Ejercicios

Ya has visto que no\(N\) es lo suficientemente fuerte como para acreditar la ley conmutativa de la adición (Ejercicio 8 en la Sección 2.8). Use esto para mostrar que no\(N\) está completo mostrando eso
\[N \nvdash \left( \forall x \right) \left( \forall y \right) x + y = y + x\]
y
\[N \nvdash \neg \left[ \left( \forall x \right) \left( \forall y \right) x + y = y + x \right].\]
Supongamos que\(\Sigma\) proporciona una axiomatización de\(Th \left( \mathfrak{N} \right)\). Supongamos que\(\sigma\) es una fórmula tal que\(N \vdash \sigma\). \(\Sigma \vdash \sigma\)Demuéstralo.
Supongamos que\(\mathfrak{A}\) es un modelo no estándar de aritmética. Si\(Th \left( \mathfrak{A} \right)\) es la colección de oraciones que son verdaderas en\(\mathfrak{A}\), ¿está\(Th \left( \mathfrak{A} \right)\) completa? ¿\(Th \left( \mathfrak{A} \right)\)Proporciona una axiomatización de\(\mathfrak{N}\)? De\(\mathfrak{A}\)?