Axiomas de Peano

Axiomas para los números naturales.

En lógica matemática , los axiomas de Peano ( / p i ˈ ɑː n oʊ / , ^[1] [peˈaːno] ), también conocidos como axiomas de Dedekind-Peano o postulados de Peano , son axiomas para los números naturales presentados por el siglo XIX. El matemático italiano Giuseppe Peano . Estos axiomas se han utilizado casi sin cambios en una serie de investigaciones metamatemáticas , incluida la investigación sobre cuestiones fundamentales sobre si la teoría de números es consistente y completa .

La importancia de formalizar la aritmética no fue bien apreciada hasta el trabajo de Hermann Grassmann , quien demostró en la década de 1860 que muchos hechos en aritmética podían derivarse de hechos más básicos sobre la operación sucesora y la inducción . ^{[2] [3]} En 1881, Charles Sanders Peirce proporcionó una axiomatización de la aritmética de números naturales. ^{[4] [5]} En 1888, Richard Dedekind propuso otra axiomatización de la aritmética de números naturales, y en 1889, Peano publicó una versión simplificada de ellos como una colección de axiomas en su libro Los principios de la aritmética presentados por un nuevo método ( latín : Arithmetices principia, nova método exposita ).

Los nueve axiomas de Peano contienen tres tipos de enunciados. El primer axioma afirma la existencia de al menos un miembro del conjunto de los números naturales. Las cuatro siguientes son declaraciones generales sobre la igualdad ; en los tratamientos modernos, estos a menudo no se toman como parte de los axiomas de Peano, sino más bien como axiomas de la "lógica subyacente". ^[6] Los siguientes tres axiomas son enunciados de primer orden sobre números naturales que expresan las propiedades fundamentales de la operación sucesora. El noveno y último axioma es una declaración de segundo orden del principio de inducción matemática sobre los números naturales, lo que acerca esta formulación a la aritmética de segundo orden . Un sistema de primer orden más débil llamado aritmética de Peano se obtiene sumando explícitamente los símbolos de las operaciones de suma y multiplicación y reemplazando el axioma de inducción de segundo orden con un esquema de axioma de primer orden .

Formulación histórica de segundo orden

Cuando Peano formuló sus axiomas, el lenguaje de la lógica matemática estaba en su infancia. El sistema de notación lógica que creó para presentar los axiomas no resultó ser popular, aunque fue la génesis de la notación moderna para pertenencia a conjuntos (∈, que proviene de la ε de Peano). Peano mantuvo una clara distinción entre símbolos matemáticos y lógicos, que aún no era común en matemáticas; tal separación había sido introducida por primera vez en el Begriffsschrift de Gottlob Frege , publicado en 1879. ^[7] Peano desconocía el trabajo de Frege y recreó de forma independiente su aparato lógico basándose en el trabajo de Boole y Schröder . ^[8]

Los axiomas de Peano definen las propiedades aritméticas de los números naturales , generalmente representados como un conjunto N o Los símbolos no lógicos de los axiomas consisten en un símbolo constante 0 y un símbolo de función unaria S. ${\displaystyle \mathbb {N} .}$

El primer axioma establece que la constante 0 es un número natural:

1. 0 es un número natural.

La formulación original de los axiomas de Peano usaba 1 en lugar de 0 como "primer" número natural, ^[9] mientras que los axiomas en Formulario matemático incluyen el cero. ^[10]

Los siguientes cuatro axiomas describen la relación de igualdad . Dado que son lógicamente válidos en lógica de primer orden con igualdad, no se consideran parte de "los axiomas de Peano" en los tratamientos modernos. ^[8]

2. Para todo número natural x , x = x . Es decir, la igualdad es reflexiva .
3. Para todos los números naturales x e y , si x = y , entonces y = x . Es decir, la igualdad es simétrica .
4. Para todos los números naturales x , y y z , si x = y y y = z , entonces x = z . Es decir, la igualdad es transitiva .
5. Para todos a y b , si b es un número natural y a = b , entonces a también es un número natural. Es decir, los números naturales son cerrados en igualdad.

Los axiomas restantes definen las propiedades aritméticas de los números naturales. Se supone que los naturales están cerrados bajo una función " sucesora " de valor único S.

6. Para todo número natural n , S ( n ) es un número natural. Es decir, los números naturales son cerrados bajo S.
7. Para todos los números naturales myn , si S ( m ) = S ( n ) , entonces m = n . Es decir, S es una inyección .
8. Para todo número natural n , S ( n ) = 0 es falso. Es decir, no existe ningún número natural cuyo sucesor sea el 0.

La cadena de fichas de dominó claras, comenzando por la más cercana, puede representar N , ^{[nota 1] [11] [12]} sin embargo, los axiomas 1 a 8 también se satisfacen con el conjunto de todas las fichas de dominó claras y oscuras. ^{[nota 2]} El noveno axioma ( inducción ) limita N a la cadena de piezas ligeras ("sin basura") ya que solo las fichas de dominó ligeras caerán cuando se derribe la más cercana. ^[13]

Los axiomas 1, 6, 7, 8 definen una representación unaria de la noción intuitiva de números naturales: el número 1 se puede definir como S (0), 2 como S ( S (0)), etc. Sin embargo, considerando la noción de Los números naturales definidos por estos axiomas, los axiomas 1, 6, 7, 8 no implican que la función sucesora genere todos los números naturales diferentes de 0.

La noción intuitiva de que cada número natural se puede obtener aplicando el sucesor a cero un número suficiente de veces requiere un axioma adicional, que a veces se denomina axioma de inducción .

9. Si K es un conjunto tal que:
   • 0 está en K , y
   • para cada número natural n , el hecho de que n esté en K implica que S ( n ) está en K ,
   entonces K contiene todos los números naturales.

El axioma de inducción a veces se expresa de la siguiente forma:

9. Si φ es un predicado unario tal que:
   • φ (0) es verdadera, y
   • para cada número natural n , que φ ( n ) sea verdadero implica que φ ( S ( n )) es verdadero,
   entonces φ ( n ) es verdadera para todo número natural n .

En la formulación original de Peano, el axioma de inducción es un axioma de segundo orden . Ahora es común reemplazar este principio de segundo orden por un esquema de inducción de primer orden más débil. Existen diferencias importantes entre las formulaciones de segundo orden y de primer orden, como se analiza en la sección § Aritmética de Peano como teoría de primer orden a continuación.

Definición de operaciones y relaciones aritméticas.

Si usamos el axioma de inducción de segundo orden, es posible definir la suma , la multiplicación y el orden total (lineal) en N directamente usando los axiomas. Sin embargo, con la inducción de primer orden, esto no es posible ^{[ cita necesaria ]} y la suma y la multiplicación a menudo se suman como axiomas. Las respectivas funciones y relaciones se construyen en teoría de conjuntos o lógica de segundo orden y se puede demostrar que son únicas utilizando los axiomas de Peano.

Suma

La suma es una función que asigna dos números naturales (dos elementos de N ) a otro. Se define recursivamente como:

${\displaystyle {\begin{aligned}a+0&=a,&{\textrm {(1)}}\\a+S(b)&=S(a+b).&{\textrm {(2)}}\end{aligned}}}$

Por ejemplo:

${\displaystyle {\begin{aligned}a+1&=a+S(0)&{\mbox{by definition}}\\&=S(a+0)&{\mbox{using (2)}}\\&=S(a),&{\mbox{using (1)}}\\\\a+2&=a+S(1)&{\mbox{by definition}}\\&=S(a+1)&{\mbox{using (2)}}\\&=S(S(a))&{\mbox{using }}a+1=S(a)\\\\a+3&=a+S(2)&{\mbox{by definition}}\\&=S(a+2)&{\mbox{using (2)}}\\&=S(S(S(a)))&{\mbox{using }}a+2=S(S(a))\\{\text{etc.}}&\\\end{aligned}}}$

La estructura ( N , +) es un monoide conmutativo con elemento de identidad 0. ( N , +) también es un magma cancelador y, por tanto, integrable en un grupo . El grupo más pequeño que incluye N son los números enteros .

Multiplicación

De manera similar, la multiplicación es una función que relaciona dos números naturales con otro. Dada la suma, se define recursivamente como:

${\displaystyle {\begin{aligned}a\cdot 0&=0,\\a\cdot S(b)&=a+(a\cdot b).\end{aligned}}}$

Es fácil ver que es la identidad multiplicativa correcta : ${\displaystyle S(0)}$

${\displaystyle a\cdot S(0)=a+(a\cdot 0)=a+0=a}$

Para demostrar que también es la identidad multiplicativa por la izquierda se requiere el axioma de inducción debido a la forma en que se define la multiplicación: ${\displaystyle S(0)}$

• ${\displaystyle S(0)}$es la identidad izquierda de 0: . ${\displaystyle S(0)\cdot 0=0}$
• Si es la identidad izquierda de (es decir ), entonces también es la identidad izquierda de : . ${\displaystyle S(0)}$ ${\displaystyle a}$ ${\displaystyle S(0)\cdot a=a}$ ${\displaystyle S(0)}$ ${\displaystyle S(a)}$ ${\displaystyle S(0)\cdot S(a)=S(0)+S(0)\cdot a=S(0)+a=a+S(0)=S(a+0)=S(a)}$

Por lo tanto, según el axioma de inducción , es la identidad multiplicativa por la izquierda de todos los números naturales. Además, se puede demostrar que la multiplicación es conmutativa y se distribuye sobre la suma: ${\displaystyle S(0)}$

${\displaystyle a\cdot (b+c)=(a\cdot b)+(a\cdot c)}$.

Por tanto, es un semiring conmutativo . ${\displaystyle (\mathbb {N} ,+,0,\cdot ,S(0))}$

Desigualdades

La relación de orden total habitual ≤ en números naturales se puede definir de la siguiente manera, suponiendo que 0 es un número natural:

Para todo a , b ∈ N , a ≤ b si y solo si existe algún c ∈ N tal que a + c = b .

Esta relación es estable bajo suma y multiplicación: para , si a ≤ b , entonces: ${\displaystyle a,b,c\in \mathbb {N} }$

• a + c ≤ b + c , y
• a · c ≤ b · c .

Así, la estructura ( N , +, ·, 1, 0, ≤) es un semianillo ordenado ; debido a que no existe un número natural entre 0 y 1, es un semianillo ordenado discreto.

El axioma de inducción a veces se expresa de la siguiente forma que utiliza una hipótesis más fuerte, haciendo uso de la relación de orden "≤":

Para cualquier predicado φ , si

• φ (0) es verdadera, y
• para cada n ∈ N , si φ ( k ) es verdadero para cada k ∈ N tal que k ≤ n , entonces φ ( S ( n )) es verdadero,
• entonces para cada n ∈ N , φ ( n ) es cierto.

Esta forma del axioma de inducción, llamada inducción fuerte , es una consecuencia de la formulación estándar, pero a menudo es más adecuada para razonar sobre el orden ≤. Por ejemplo, para demostrar que los naturales están bien ordenados ( cada subconjunto no vacío de N tiene un elemento mínimo ), se puede razonar de la siguiente manera. Sea un X ⊆ N no vacío y supongamos que X no tiene elemento mínimo.

• Debido a que 0 es el elemento mínimo de N , debe ser que 0 ∉ X.
• Para cualquier n ∈ N , supongamos que para cada k ≤ n , k ∉ X . Entonces S ( n ) ∉ X , pues de lo contrario sería el elemento menor de X .

Así, por el principio de inducción fuerte, para cada n ∈ N , n ∉ X . Por lo tanto, X ∩ N = ∅ , lo que contradice que X sea un subconjunto no vacío de N . Por tanto, X tiene un elemento mínimo.

Modelos

Un modelo de los axiomas de Peano es un triple ( N , 0, S ) , donde N es un conjunto (necesariamente infinito), 0 ∈ N y S : N → N satisface los axiomas anteriores. Dedekind demostró en su libro de 1888, La naturaleza y el significado de los números ( en alemán : Was sind und was sollen die Zahlen?, es decir, "¿Qué son los números y para qué sirven?") que dos modelos cualesquiera de los axiomas de Peano ( incluido el axioma de inducción de segundo orden) son isomórficos . En particular, dados dos modelos ( N _A , 0 _A , S _A ) y ( N _B , 0 _B , S _B ) de los axiomas de Peano, existe un homomorfismo único f  : N _A → N _B que satisface

${\displaystyle {\begin{aligned}f(0_{A})&=0_{B}\\f(S_{A}(n))&=S_{B}(f(n))\end{aligned}}}$

y es una biyección . Esto significa que los axiomas de Peano de segundo orden son categóricos . (Este no es el caso de ninguna reformulación de primer orden de los axiomas de Peano, que se describen a continuación).

Modelos de teoría de conjuntos

Los axiomas de Peano pueden derivarse de construcciones teóricas de conjuntos de los números naturales y axiomas de la teoría de conjuntos como ZF . ^[14] La construcción estándar de los naturales, debida a John von Neumann , parte de una definición de 0 como el conjunto vacío, ∅, y un operador s en conjuntos definido como:

${\displaystyle s(a)=a\cup \{a\}}$

El conjunto de números naturales N se define como la intersección de todos los conjuntos cerrados bajo s que contienen el conjunto vacío. Cada número natural es igual (como conjunto) al conjunto de números naturales menores que él:

${\displaystyle {\begin{aligned}0&=\emptyset \\1&=s(0)=s(\emptyset )=\emptyset \cup \{\emptyset \}=\{\emptyset \}=\{0\}\\2&=s(1)=s(\{0\})=\{0\}\cup \{\{0\}\}=\{0,\{0\}\}=\{0,1\}\\3&=s(2)=s(\{0,1\})=\{0,1\}\cup \{\{0,1\}\}=\{0,1,\{0,1\}\}=\{0,1,2\}\end{aligned}}}$

etcétera. El conjunto N junto con 0 y la función sucesora s  : N → N satisface los axiomas de Peano.

La aritmética de Peano es equiconsistente con varios sistemas débiles de teoría de conjuntos. ^[15] Uno de esos sistemas es ZFC con el axioma del infinito reemplazado por su negación. Otro sistema de este tipo consiste en la teoría general de conjuntos ( extensionalidad , existencia del conjunto vacío y el axioma de conjunción ), aumentada por un esquema de axioma que establece que una propiedad que se cumple para el conjunto vacío y se cumple para un adjunto siempre que se cumple para el adjunto debe mantenerse para todos los conjuntos.

Interpretación en la teoría de categorías.

Los axiomas de Peano también pueden entenderse utilizando la teoría de categorías . Sea C una categoría con objeto terminal 1 _C y defina la categoría de sistemas unarios puntiagudos , US ₁ ( C ) de la siguiente manera:

• Los objetos de US ₁ ( C ) son triples ( X , 0 _X , S _X ) donde X es un objeto de C y 0 _X  : 1 _C → X y S _X  : X → X son C -morfismos.
• Un morfismo φ  : ( X , 0 _X , S _X ) → ( Y , 0 _Y , S _Y ) es un C -morfismo φ  : X → Y con φ 0 _X = 0 _Y y φ S _X = S _Y φ .

Entonces se dice que C satisface los axiomas de Dedekind-Peano si US ₁ ( C ) tiene un objeto inicial; este objeto inicial se conoce como objeto de número natural en C. Si ( N , 0, S ) es este objeto inicial, y ( X , 0 _X , S _X ) es cualquier otro objeto, entonces el mapa único u  : ( N , 0, S ) → ( X , 0 _X , S _X ) es tal que

${\displaystyle {\begin{aligned}u(0)&=0_{X},\\u(Sx)&=S_{X}(ux).\end{aligned}}}$

Ésta es precisamente la definición recursiva de 0 _X y S _X.

Consistencia

Cuando se propusieron por primera vez los axiomas de Peano, Bertrand Russell y otros coincidieron en que estos axiomas definían implícitamente lo que entendemos por "número natural". ^[16] Henri Poincaré fue más cauteloso y dijo que sólo definían los números naturales si eran consistentes ; Si hay una prueba que parte únicamente de estos axiomas y deriva una contradicción como 0 = 1, entonces los axiomas son inconsistentes y no definen nada. ^[17] En 1900, David Hilbert planteó el problema de demostrar su coherencia utilizando únicamente métodos finitistas como el segundo de sus veintitrés problemas . ^[18] En 1931, Kurt Gödel demostró su segundo teorema de incompletitud , que muestra que tal prueba de consistencia no puede formalizarse dentro de la propia aritmética de Peano, si la aritmética de Peano es consistente. ^[19]

Aunque se afirma ampliamente que el teorema de Gödel descarta la posibilidad de una prueba de consistencia finitista para la aritmética de Peano, esto depende de lo que se entienda exactamente por prueba finitista. El propio Gödel señaló la posibilidad de dar una prueba de consistencia finitista de la aritmética de Peano o sistemas más fuertes mediante el uso de métodos finitistas que no son formalizables en la aritmética de Peano, y en 1958, Gödel publicó un método para probar la consistencia de la aritmética usando la teoría de tipos . ^[20] En 1936, Gerhard Gentzen dio una prueba de la consistencia de los axiomas de Peano, utilizando inducción transfinita hasta un ordinal llamado ε 0 . ^[21] Gentzen explicó: "El objetivo del presente artículo es demostrar la coherencia de la teoría elemental de números o, más bien, reducir la cuestión de la coherencia a ciertos principios fundamentales". La prueba de Gentzen es posiblemente finitista, ya que el ordinal transfinito ε ₀ puede codificarse en términos de objetos finitos (por ejemplo, como una máquina de Turing que describe un orden adecuado en los números enteros, o más abstractamente como consistente en árboles finitos , adecuadamente ordenados linealmente) . No está claro si la prueba de Gentzen cumple o no los requisitos que Hilbert imaginó: no existe una definición generalmente aceptada de qué se entiende exactamente por una prueba finitista, y el propio Hilbert nunca dio una definición precisa.

La gran mayoría de los matemáticos contemporáneos cree que los axiomas de Peano son consistentes y se basan en la intuición o en la aceptación de una prueba de consistencia como la prueba de Gentzen . Un pequeño número de filósofos y matemáticos, algunos de los cuales también defienden el ultrafinitismo , rechazan los axiomas de Peano porque aceptarlos equivale a aceptar la colección infinita de números naturales. En particular, se supone que la suma (incluida la función sucesora) y la multiplicación son totales . Curiosamente, existen teorías autoverificables que son similares a la PA pero tienen resta y división en lugar de suma y multiplicación, que están axiomatizadas de tal manera que evitan probar oraciones que corresponden a la totalidad de la suma y la multiplicación, pero que aún pueden para probar todos los teoremas verdaderos de PA y, sin embargo, puede extenderse a una teoría consistente que demuestre su propia consistencia (expresada como la inexistencia de una prueba al estilo de Hilbert de "0=1"). ^[22] ${\displaystyle \Pi _{1}}$

La aritmética de Peano como teoría de primer orden.

Todos los axiomas de Peano, excepto el noveno axioma (el axioma de inducción), son enunciados en lógica de primer orden . ^[23] Las operaciones aritméticas de suma y multiplicación y la relación de orden también se pueden definir utilizando axiomas de primer orden. El axioma de inducción anterior es de segundo orden , ya que cuantifica predicados (de manera equivalente, conjuntos de números naturales en lugar de números naturales). Como alternativa, se puede considerar un esquema de axioma de inducción de primer orden. Tal esquema incluye un axioma por predicado definible en el lenguaje de primer orden de la aritmética de Peano, lo que lo hace más débil que el axioma de segundo orden. ^[24] La razón por la que es más débil es que el número de predicados en el lenguaje de primer orden es contable, mientras que el número de conjuntos de números naturales es incontable. Por tanto, existen conjuntos que no pueden describirse en lenguaje de primer orden (de hecho, la mayoría de los conjuntos tienen esta propiedad).

Las axiomatizaciones de primer orden de la aritmética de Peano tienen otra limitación técnica. En la lógica de segundo orden, es posible definir las operaciones de suma y multiplicación a partir de la operación sucesora , pero esto no se puede hacer en el entorno más restrictivo de la lógica de primer orden. Por tanto, las operaciones de suma y multiplicación se incluyen directamente en la firma de la aritmética de Peano, y se incluyen axiomas que relacionan las tres operaciones entre sí.

La siguiente lista de axiomas (junto con los habituales axiomas de igualdad), que contiene seis de los siete axiomas de la aritmética de Robinson , es suficiente para este propósito: ^[25]

• ${\displaystyle \forall x\ (0\neq S(x))}$
• ${\displaystyle \forall x,y\ (S(x)=S(y)\Rightarrow x=y)}$
• ${\displaystyle \forall x\ (x+0=x)}$
• ${\displaystyle \forall x,y\ (x+S(y)=S(x+y))}$
• ${\displaystyle \forall x\ (x\cdot 0=0)}$
• ${\displaystyle \forall x,y\ (x\cdot S(y)=x\cdot y+x)}$

Además de esta lista de axiomas numéricos, la aritmética de Peano contiene el esquema de inducción, que consiste en un conjunto de axiomas recursivamente enumerables e incluso decidibles . Para cada fórmula φ ( x , y ₁ , ..., y _k ) en el lenguaje de la aritmética de Peano, el axioma de inducción de primer orden para φ es la oración

${\displaystyle \forall {\bar {y}}{\Bigg (}{\bigg (}\varphi (0,{\bar {y}})\land \forall x{\Big (}\varphi (x,{\bar {y}})\Rightarrow \varphi (S(x),{\bar {y}}){\Big )}{\bigg )}\Rightarrow \forall x\varphi (x,{\bar {y}}){\Bigg )}}$

donde es una abreviatura de y ₁ ,..., y _k . El esquema de inducción de primer orden incluye todos los casos del axioma de inducción de primer orden; es decir, incluye el axioma de inducción para cada fórmula φ . ${\displaystyle {\bar {y}}}$

Axiomatizaciones equivalentes

La axiomatización anterior de la aritmética de Peano utiliza una firma que solo tiene símbolos para cero, así como las operaciones sucesoras, de suma y de multiplicación. Hay muchas otras axiomatizaciones diferentes, pero equivalentes. Una de esas alternativas ^[26] utiliza un símbolo de relación de orden en lugar de la operación sucesora y el lenguaje de semirings ordenados discretamente (axiomas 1-7 para semirings, 8-10 sobre orden, 11-13 sobre compatibilidad y 14-15 sobre discreción) :

1. ${\displaystyle \forall x,y,z\ ((x+y)+z=x+(y+z))}$, es decir, la suma es asociativa .
2. ${\displaystyle \forall x,y\ (x+y=y+x)}$, es decir, la suma es conmutativa .
3. ${\displaystyle \forall x,y,z\ ((x\cdot y)\cdot z=x\cdot (y\cdot z))}$, es decir, la multiplicación es asociativa.
4. ${\displaystyle \forall x,y\ (x\cdot y=y\cdot x)}$, es decir, la multiplicación es conmutativa.
5. ${\displaystyle \forall x,y,z\ (x\cdot (y+z)=(x\cdot y)+(x\cdot z))}$, es decir, la multiplicación se distribuye sobre la suma.
6. ${\displaystyle \forall x\ (x+0=x\land x\cdot 0=0)}$, es decir, cero es una identidad para la suma y un elemento absorbente para la multiplicación (en realidad superfluo ^{[nota 3]} ).
7. ${\displaystyle \forall x\ (x\cdot 1=x)}$, es decir, uno es una identidad para la multiplicación.
8. ${\displaystyle \forall x,y,z\ (x<y\land y<z\Rightarrow x<z)}$, es decir, el operador '<' es transitivo .
9. ${\displaystyle \forall x\ (\neg (x<x))}$, es decir, el operador '<' es irreflexivo .
10. ${\displaystyle \forall x,y\ (x<y\lor x=y\lor y<x)}$, es decir, el ordenamiento satisface la tricotomía .
11. ${\displaystyle \forall x,y,z\ (x<y\Rightarrow x+z<y+z)}$, es decir, el orden se conserva al agregar el mismo elemento.
12. ${\displaystyle \forall x,y,z\ (0<z\land x<y\Rightarrow x\cdot z<y\cdot z)}$, es decir, el orden se conserva al multiplicar por el mismo elemento positivo.
13. ${\displaystyle \forall x,y\ (x<y\Rightarrow \exists z\ (x+z=y))}$, es decir, dados dos elementos distintos, el mayor es el menor más otro elemento.
14. ${\displaystyle 0<1\land \forall x\ (x>0\Rightarrow x\geq 1)}$, es decir, cero y uno son distintos y no hay ningún elemento entre ellos. En otras palabras, 0 está cubierto por 1, lo que sugiere que estos números son discretos.
15. ${\displaystyle \forall x\ (x\geq 0)}$, es decir, cero es el elemento mínimo.

La teoría definida por estos axiomas se conoce como PA ⁻ . También es incompleto y una de sus propiedades importantes es que cualquier estructura que satisfaga esta teoría tiene un segmento inicial (ordenado por ) isomorfo a . Los elementos de ese segmento se denominan elementos estándar , mientras que otros elementos se denominan elementos no estándar . ${\displaystyle M}$ ${\displaystyle \leq }$ ${\displaystyle \mathbb {N} }$

Finalmente, la PA aritmética de Peano se obtiene sumando el esquema de inducción de primer orden.

Indecidibilidad e incompletud

Según los teoremas de incompletitud de Gödel , la teoría de la PA (si es consistente) es incompleta. En consecuencia, hay oraciones de lógica de primer orden (FOL) que son verdaderas en el modelo estándar de AP pero no son consecuencia de la axiomatización de FOL. La incompletitud esencial ya surge en teorías con axiomas más débiles, como la aritmética de Robinson .

Estrechamente relacionado con el resultado de incompletitud anterior (a través del teorema de completitud de Gödel para FOL), se deduce que no existe un algoritmo para decidir si una oración FOL dada es consecuencia de una axiomatización de primer orden de la aritmética de Peano o no. Por tanto, la AP es un ejemplo de teoría indecidible . La indecidibilidad surge ya para las oraciones existenciales de PA , debido a la respuesta negativa al décimo problema de Hilbert , cuya prueba implica que todos los conjuntos computablemente enumerables son conjuntos diofánticos y, por lo tanto, definibles mediante fórmulas existencialmente cuantificadas (con variables libres) de PA . Las fórmulas de PA con rango de cuantificador más alto (más alternancias de cuantificadores) que las fórmulas existenciales son más expresivas y definen conjuntos en los niveles superiores de la jerarquía aritmética .

Modelos no estándar

Aunque los números naturales habituales satisfacen los axiomas de PA, también existen otros modelos (llamados " modelos no estándar "); El teorema de la compacidad implica que la existencia de elementos no estándar no puede excluirse en la lógica de primer orden. ^{[27] El} teorema ascendente de Löwenheim-Skolem muestra que existen modelos no estándar de PA de todas las cardinalidades infinitas. Este no es el caso de los axiomas de Peano originales (de segundo orden), que tienen un solo modelo, hasta el isomorfismo. ^[28] Esto ilustra una forma en que el sistema de primer orden PA es más débil que los axiomas de Peano de segundo orden.

Cuando se interpreta como una prueba dentro de una teoría de conjuntos de primer orden , como ZFC , la prueba de categoricidad de Dedekind para PA muestra que cada modelo de teoría de conjuntos tiene un modelo único de los axiomas de Peano, hasta el isomorfismo, que incluye como segmento inicial de todos otros modelos de PA contenidos dentro de ese modelo de teoría de conjuntos. En el modelo estándar de teoría de conjuntos, este modelo más pequeño de PA es el modelo estándar de PA; sin embargo, en un modelo no estándar de teoría de conjuntos, puede ser un modelo no estándar de PA. Esta situación no se puede evitar con ninguna formalización de primer orden de la teoría de conjuntos.

Es natural preguntarse si se puede construir explícitamente un modelo contable no estándar. La respuesta es afirmativa ya que Skolem en 1933 proporcionó una construcción explícita de dicho modelo no estándar . Por otro lado, el teorema de Tennenbaum , demostrado en 1959, muestra que no existe un modelo no estándar contable de PA en el que la operación de suma o multiplicación sea computable . ^[29] Este resultado muestra que es difícil ser completamente explícito al describir las operaciones de suma y multiplicación de un modelo contable no estándar de PA. Sólo existe un tipo de pedido posible para un modelo no estándar contable. Si ω es el tipo de orden de los números naturales, ζ es el tipo de orden de los números enteros y η es el tipo de orden de los racionales, el tipo de orden de cualquier modelo contable no estándar de PA es ω + ζ · η , que puede ser visualizado como una copia de los números naturales seguida de un orden lineal denso de copias de los números enteros.

Derrame

Un corte en un modelo no estándar M es un subconjunto C no vacío de M , de modo que C está cerrado hacia abajo ( x < y y y ∈ C ⇒ x ∈ C ) y C está cerrado bajo el sucesor. Un corte adecuado es un corte que es un subconjunto propio de M. Cada modelo no estándar tiene muchos cortes adecuados, incluido uno que corresponde a los números naturales estándar. Sin embargo, el esquema de inducción en la aritmética de Peano impide que se pueda definir cualquier corte adecuado. El lema del desbordamiento, demostrado por primera vez por Abraham Robinson, formaliza este hecho.

Lema de desbordamiento ^[30]  :  Sea M un modelo no estándar de PA y sea C un corte adecuado de M. Supongamos que es una tupla de elementos de M y es una fórmula en el lenguaje de la aritmética de modo que ${\displaystyle {\bar {a}}}$ ${\displaystyle \phi (x,{\bar {a}})}$

${\displaystyle M\vDash \phi (b,{\bar {a}})}$para todo b ∈ C .

Entonces hay un c en M que es mayor que cada elemento de C tal que

${\displaystyle M\vDash \phi (c,{\bar {a}}).}$

Ver también

• Portal de filosofía
• Portal de matemáticas

• Fundamentos de las matemáticas
• teorema de frege
• teorema de goodstein
• Neologicismo
• Modelo no estándar de aritmética.
• Teorema de París-Harrington
• aritmética de presburger
• aritmética de robinson
• Aritmética de segundo orden
• Teoría tipográfica de números

Notas

1. la pieza de luz más cercana correspondiente a 0 y una pieza vecina correspondiente al sucesor
2. El conjunto no contiguo satisface el axioma 1 porque tiene un elemento 0, 2-5 porque no afecta las relaciones de igualdad, 6 y 8 porque todas las piezas tienen un sucesor, excluye el elemento cero y el axioma 7 ya que no se caen dos fichas de dominó , o son derribados por, la misma pieza.
3. " " se puede demostrar a partir de los otros axiomas (en lógica de primer orden) de la siguiente manera. En primer lugar, por distributividad e identidad aditiva. En segundo lugar, por el Axioma 15. Si entonces por adición del mismo elemento y conmutatividad, y por tanto por sustitución, contradiciendo la irreflexividad. Por lo tanto debe ser así . ${\displaystyle \forall x\ (x\cdot 0=0)}$ ${\displaystyle x\cdot 0+x\cdot 0=x\cdot (0+0)=x\cdot 0=x\cdot 0+0}$ ${\displaystyle x\cdot 0=0\lor x\cdot 0>0}$ ${\displaystyle x\cdot 0>0}$ ${\displaystyle x\cdot 0+x\cdot 0>x\cdot 0+0}$ ${\displaystyle x\cdot 0+0>x\cdot 0+0}$ ${\displaystyle x\cdot 0=0}$

Referencias

Citas

1. "Peano". Diccionario íntegro de Random House Webster .
2. Grassmann 1861.
3. Wang 1957, págs. 145, 147, "Es bastante conocido, gracias al reconocimiento del propio Peano, que Peano [...] hizo un uso extensivo del trabajo de Grassmann en su desarrollo de los axiomas. No es tan conocido que Grassmann tenía esencialmente la caracterización del conjunto de todos los números enteros, ahora habitual en los textos de álgebra moderna, de que forma un dominio integral ordenado en el que cada conjunto de elementos positivos tiene un miembro mínimo. […] [El libro de Grassmann] fue probablemente el primer libro serio y bastante exitoso intento de poner los números sobre una base más o menos axiomática".
4. Peirce 1881.
5. Escudos 1997.
6. Van Heijenoort 1967, pág. 94.
7. Van Heijenoort 1967, pág. 2.
8. Van Heijenoort 1967, pág. 83.
9. Peano 1889, pag. 1.
10. Peano 1908, pag. 27.
11. Matt DeVos, Inducción Matemática, Universidad Simon Fraser
12. Gerardo con Diaz, Inducción matemática Archivado el 2 de mayo de 2013 en Wayback Machine , Universidad de Harvard
13. Meseguer & Goguen 1986, apartados 2.3 (p. 464) y 4.1 (p. 471).
14. Suppes 1960, Hatcher 2014
15. Tarski y Givant 1987, sección 7.6.
16. Fritz 1952, pág. 137
    Un ejemplo de "interpretación" es la propia definición de Russell de "número cardinal". El sistema no interpretado en este caso son los axiomas de Peano para el sistema numérico, cuyas tres ideas primitivas y cinco axiomas, creía Peano, eran suficientes para permitir derivar todas las propiedades del sistema de números naturales. En realidad, sostiene Russell, los axiomas de Peano definen cualquier progresión de la forma de la cual la serie de los números naturales es un ejemplo. ${\displaystyle x_{0},x_{1},x_{2},\ldots ,x_{n},\ldots }$
17. Gris 2013, pag. 133
    Entonces Poincaré se volvió para ver si el logicismo podía generar aritmética, más precisamente, la aritmética de ordinales. Couturat, dijo Poincaré, había aceptado los axiomas de Peano como definición de un número. Pero esto no servirá. No se puede demostrar que los axiomas están libres de contradicciones encontrando ejemplos de ellos, y cualquier intento de demostrar que estaban libres de contradicciones examinando la totalidad de sus implicaciones requeriría el principio mismo de inducción matemática que Couturat creía que implicaban. Porque (en un pasaje posterior eliminado de S&M) cualquiera de los dos asumió el principio para probarlo, lo que sólo probaría que si es verdadero no es autocontradictorio, lo cual no dice nada; o uno usó el principio en una forma diferente a la establecida, en cuyo caso uno debe demostrar que el número de pasos en su razonamiento era un número entero según la nueva definición, pero esto no se podía hacer (1905c, 834).
18. Hilbert 1902.
19. Godel 1931.
20. Godel 1958
21. Caballeros 1936
22. Willard 2001.
23. Partee, Ter Meulen y Wall 2012, p. 215.
24. Harsanyi (1983).
25. Mendelson 1997, pag. 155.
26. Kaye 1991, págs. 16-18.
27. Hermes 1973, VI.4.3, que presenta un teorema de Thoralf Skolem
28. Hermes 1973, VI.3.1.
29. Kaye 1991, sección 11.3.
30. Kaye 1991, págs. 70 y siguientes.

Fuentes

• Davis, Martín (1974). Computabilidad. Notas de Barry Jacobs . Instituto Courant de Ciencias Matemáticas , Universidad de Nueva York .

• Dedekind, Richard (1888). Was sind und was sollen die Zahlen? [ ¿ Qué son y cuáles deberían ser los números? ] (PDF) . Vereg . Consultado el 4 de julio de 2016 .
  • Dos traducciones al inglés:
    • Beman, Wooster, Woodruff (1901). Ensayos sobre teoría de números (PDF) . Publicaciones de Dover .{{cite book}}: CS1 maint: multiple names: authors list (link)
    • Ewald, William B. (1996). De Kant a Hilbert: un libro de consulta sobre los fundamentos de las matemáticas. Prensa de la Universidad de Oxford . págs. 787–832. ISBN 978-0-19-853271-2.

• Fritz, Charles A. Jr. (1952). La construcción del mundo exterior de Bertrand Russell . Nueva York, Humanities Press.

• Gentzen, Gerhard (1936). Reimpreso en traducción al inglés en sus Obras completas de 1969 , ME Szabo, ed. "Die Widerspruchsfreiheit der reinen Zahlentheorie". Annalen Matemáticas . 112 : 132-213. doi :10.1007/bf01565428. S2CID  122719892.

• Gödel, Kurt (1931). Consulte Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados para obtener detalles sobre las traducciones al inglés. "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I" (PDF) . Monatshefte für Mathematik . 38 : 173–198. doi :10.1007/bf01700692. S2CID  197663120. Archivado desde el original (PDF) el 11 de abril de 2018 . Consultado el 31 de octubre de 2013 .

• Gödel, Kurt (1958). Reimpreso en traducción al inglés en 1990. Obras completas de Gödel , Vol II. Solomon Feferman y otros, eds. "Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes". Dialéctica . Prensa de la Universidad de Oxford . 12 (3–4): 280–287. doi : 10.1111/j.1746-8361.1958.tb01464.x .

• Grassmann, Hermann Günther (1861). Lehrbuch der Arithmetik für höhere Lehranstalten. Verlag von Theod. Chr. P. Enslin.

• Gris, Jeremy (2013). "El ensayista". Henri Poincaré: una biografía científica . Prensa de la Universidad de Princeton . pag. 133.ISBN _ 978-0-691-15271-4.

• Harsanyi, John C. (1983). "Matemáticas, hechos empíricos y necesidad lógica". En Hempel, Carl G.; Putnam, Hilary; Essler, Wilhelm K. (eds.). Metodología, Epistemología y Filosofía de la Ciencia . págs. 167-192. doi :10.1007/978-94-015-7676-5_8. ISBN 978-90-481-8389-0. S2CID  121297669.

• Hatcher, William S. (2014) [1982]. Los fundamentos lógicos de las matemáticas. Elsevier. ISBN 978-1-4831-8963-5.Deriva los axiomas de Peano (llamados S ) de varias teorías de conjuntos axiomáticos y de la teoría de categorías .

• Hermes, Hans (1973). Introducción a la Lógica Matemática . Hochschultext. Saltador. ISBN 3-540-05819-2. ISSN  1431-4657.

• Hilbert, David (1902). Traducido por Winton, Maby. "Mathematische Probleme" [Problemas matemáticos]. Boletín de la Sociedad Matemática Estadounidense . 8 (10): 437–479. doi : 10.1090/s0002-9904-1902-00923-3 .

• Kaye, Richard (1991). Modelos de aritmética de Peano . Prensa de la Universidad de Oxford . ISBN 0-19-853213-X.

• Landau, Edmundo (1965). Grundlagen Der Análisis . Deriva los sistemas numéricos básicos a partir de los axiomas de Peano. Vocabulario inglés/alemán incluido. Publicación de AMS Chelsea . ISBN 978-0-8284-0141-8.

• Mendelson, Elliott (diciembre de 1997) [diciembre de 1979]. Introducción a la lógica matemática (Matemáticas discretas y sus aplicaciones) (4ª ed.). Saltador. ISBN 978-0-412-80830-2.

• Meseguer, José; Goguen, Joseph A. (diciembre de 1986). "Inicialidad, inducción y computabilidad". En Maurice Nivat y John C. Reynolds (ed.). Métodos algebraicos en semántica (PDF) . Cambridge: Prensa de la Universidad de Cambridge. págs. 459–541. ISBN 978-0-521-26793-9.

• Partee, Bárbara; Ter Meulen, Alicia ; Muro, Robert (2012). Métodos matemáticos en lingüística. Saltador. ISBN 978-94-009-2213-6.

• Peano, Giuseppe (1908). Formulario Matemático (V ed.). Turín, Bocca frères, cap. Clausen. pag. 27.

• Peirce, CS (1881). "Sobre la lógica del número". Revista Estadounidense de Matemáticas . 4 (1): 85–95. doi :10.2307/2369151. JSTOR  2369151. SEÑOR  1507856.

• Escudos, Paul (1997). "3. Axiomatización de la aritmética de Peirce". En Houser, Nathan; Roberts, Don D.; Van Evra, James (eds.). Estudios de lógica de Charles Sanders Peirce . Prensa de la Universidad de Indiana. págs. 43–52. ISBN 0-253-33020-3.

• Suppes, Patrick (1960). Teoría de conjuntos axiomática . Publicaciones de Dover . ISBN 0-486-61630-4.Deriva los axiomas de Peano de ZFC

• Tarski, Alfred ; Givant, Steven (1987). Una formalización de la teoría de conjuntos sin variables . Publicaciones del Coloquio AMS. vol. 41. Sociedad Matemática Estadounidense . ISBN 978-0-8218-1041-5.

• Van Heijenoort, Jean (1967). De Frege a Godel: un libro de consulta sobre lógica matemática, 1879-1931 . Prensa de la Universidad de Harvard. ISBN 978-0-674-32449-7.
  • Contiene traducciones de los dos artículos siguientes, con valiosos comentarios:
    • Dedekind, Richard (1890). Carta a Keferstein . En P. 100, reafirma y defiende sus axiomas de 1888. págs. 98-103.
    • Peano, Giuseppe (1889). Arithmetices principia, nova Methodo exposita [ Los principios de la aritmética, presentados mediante un nuevo método ]. Un extracto del tratado donde Peano presentó por primera vez sus axiomas y definió recursivamente operaciones aritméticas. Fratres Bocca. págs. 83–97.

• Van Oosten, Jaap (junio de 1999). "Introducción a la aritmética de Peano (incompletitud de Gödel y modelos no estándar)" (PDF) . Universidad de Utrecht . Consultado el 2 de septiembre de 2023 .

• Wang, Hao (junio de 1957). "La axiomatización de la aritmética". La revista de lógica simbólica . Asociación de Lógica Simbólica . 22 (2): 145-158. doi :10.2307/2964176. JSTOR  2964176. S2CID  26896458.

• Willard, Dan E. (2001). "Sistemas de axiomas autoverificantes, el teorema de incompletitud y principios de reflexión relacionados" (PDF) . La revista de lógica simbólica . 66 (2): 536–596. doi :10.2307/2695030. JSTOR  2695030. SEÑOR  1833464. S2CID  2822314.

Otras lecturas

• Buss, Samuel R. (1998). "Capítulo II: Teoría de la aritmética de prueba de primer orden". En Buss, Samuel R. (ed.). Manual de teoría de la prueba . Nueva York: Elsevier Science. ISBN 978-0-444-89840-1.

• Mendelson, Elliott (junio de 2015) [diciembre de 1979]. Introducción a la lógica matemática (Matemáticas discretas y sus aplicaciones) (6ª ed.). Chapman y Hall/CRC. ISBN 978-1-4822-3772-6.

• Smullyan, Raymond M. (diciembre de 2013). El libro de acertijos de Gödel: acertijos, paradojas y pruebas. Publicaciones de Dover. ISBN 978-0-486-49705-1.

• Takeuti, Gaisi (2013). Teoría de la prueba (Segunda ed.). Mineola, Nueva York. ISBN 978-0-486-49073-1.{{cite book}}: CS1 maint: location missing publisher (link)

enlaces externos

• Murzi, Mauro. "Henri Poincaré". Enciclopedia de Filosofía de Internet .Incluye una discusión de la crítica de Poincaré a los axiomas de Peano.
• Podnieks, Karlis (25 de enero de 2015). "3. Aritmética de primer orden". Qué son las matemáticas: el teorema de Gödel y sus alrededores. págs. 93-121.
• "Axiomas de Peano", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Weisstein, Eric W. "Axiomas de Peano". MundoMatemático .
• Burris, Stanley N. (2001). "¿Qué son los números y cuál es su significado?: Dedekind".Comentario sobre la obra de Dedekind.

Este artículo incorpora material de PA en PlanetMath , que tiene la licencia Creative Commons Attribution/Share-Alike License .