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 matemático italiano del siglo XIX Giuseppe Peano . Estos axiomas se han utilizado casi sin cambios en varias investigaciones metamatemáticas , incluidas las investigaciones sobre cuestiones fundamentales de si la teoría de números es consistente y completa .

La axiomatización de la aritmética proporcionada por los axiomas de Peano se denomina comúnmente aritmética de Peano .

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 methodo 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 números naturales. Los cuatro siguientes son enunciados generales sobre la igualdad ; en los tratamientos modernos, a menudo no se los considera parte de los axiomas de Peano, sino más bien como axiomas de la "lógica subyacente". ^[6] Los tres axiomas siguientes son enunciados de primer orden sobre los números naturales que expresan las propiedades fundamentales de la operación sucesora. El noveno axioma, el último, es un enunciado de segundo orden del principio de inducción matemática sobre los números naturales, lo que hace que esta formulación se acerque a la aritmética de segundo orden . Se obtiene un sistema de primer orden más débil añadiendo explícitamente los símbolos de las operaciones de adición y multiplicación y reemplazando el axioma de inducción de segundo orden por un esquema axiomático de primer orden . El término aritmética de Peano se utiliza a veces para nombrar específicamente a este sistema restringido.

Formulación histórica de segundo orden

Cuando Peano formuló sus axiomas, el lenguaje de la lógica matemática estaba en pañales. El sistema de notación lógica que creó para presentar los axiomas no resultó popular, aunque fue la génesis de la notación moderna para la pertenencia a conjuntos (∈, que proviene del ε de Peano). Peano mantuvo una clara distinción entre símbolos matemáticos y lógicos, que todavía no era común en matemáticas; dicha 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 , usualmente representados como un conjunto N o Los símbolos no lógicos para 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 utilizaba 1 en lugar de 0 como el "primer" número natural, ^[9] mientras que los axiomas del Formulario mathematico incluyen el cero. ^[10]

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

2. Para cada 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 e 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 bajo 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 " univaluada S .

6. Para cada número natural n , S ( n ) es un número natural. Es decir, los números naturales son cerrados respecto de S .
7. Para todos los números naturales m y n , 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 dominós claros de la derecha, comenzando por el más cercano, puede representar el conjunto N de números naturales. ^{[nota 1] [11] [12]} Sin embargo, los axiomas 1 a 8 también se satisfacen para el conjunto de todos los dominós, ya sean claros u oscuros, tomados en conjunto. ^{[nota 2]} El noveno axioma ( inducción ) limita N a la cadena de piezas claras ("sin basura") ya que solo caerán los dominós claros cuando se caiga el más cercano. ^[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 puede definirse como S (0), el 2 como S ( S (0)), etc. Sin embargo, considerando la noción de números naturales como definida 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 puede obtenerse aplicando el sucesor a cero suficientes 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 , n estando 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 enuncia de la siguiente forma:

9. Si φ es un predicado unario tal que:
   • φ (0) es verdadero, y
   • para cada número natural n , el hecho de que φ ( n ) sea verdadero implica que φ ( S ( n )) es verdadero,
   entonces φ ( n ) es verdadero 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 y primer orden, como se analiza en la sección § La aritmética de Peano como teoría de primer orden más adelante.

Definición de operaciones y relaciones aritméticas

Si utilizamos el axioma de inducción de segundo orden, es posible definir la adición , la multiplicación y el ordenamiento total (lineal) en N directamente utilizando los axiomas. Sin embargo, con la inducción de primer orden, esto no es posible ^{[ cita requerida ]} y la adición y la multiplicación a menudo se agregan como axiomas. Las respectivas funciones y relaciones se construyen en la teoría de conjuntos o la 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}}}$

Para demostrar la conmutatividad de la adición, primero demuestre y , cada uno por inducción sobre . Usando ambos resultados, luego demuestre por inducción sobre . La estructura ( N , +) es un monoide conmutativo con elemento identidad 0. ( N , +) es también un magma cancelativo y, por lo tanto, integrable en un grupo . El grupo más pequeño que integra N es el de los enteros . ^{[ cita requerida ]} ${\displaystyle 0+b=b}$ ${\displaystyle S(a)+b=S(a+b)}$ ${\displaystyle b}$ ${\displaystyle a+b=b+a}$ ${\displaystyle b}$

Multiplicación

De manera similar, la multiplicación es una función que asigna dos números naturales a 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 es también la identidad izquierda de : , usando la conmutatividad de la adición. ${\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, por el axioma de inducción , la identidad multiplicativa por la izquierda de todos los números naturales es la misma. Además, se puede demostrar ^[14] 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 lo tanto, es un semianillo 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, asumiendo que 0 es un número natural:

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

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

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

Por lo tanto, la estructura ( N , +, ·, 1, 0, ≤) es un semianillo ordenado ; como no hay ningún número natural entre 0 y 1, es un semianillo ordenado discreto.

El axioma de inducción a veces se enuncia en 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 verdadero, 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 verdadero.

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 conjunto no vacío X ⊆ N y supongamos que X no tiene ningún elemento mínimo.

• Como 0 es el menor elemento de N , debe ser que 0 ∉ X .
• Para cualquier n ∈ N , supongamos que para cada k ≤ n , k ∉ X . Entonces S ( n ) ∉ X , porque de lo contrario sería el menor elemento 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 lo tanto, X tiene un elemento mínimo.

Modelos

Un modelo de los axiomas de Peano es una tripleta ( 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 isomorfos . 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 con ninguna reformulación de primer orden de los axiomas de Peano, 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 . ^[15] La construcción estándar de los naturales, debida a John von Neumann , comienza con una definición de 0 como el conjunto vacío, ∅, y un operador s en conjuntos definidos como:

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

El conjunto de los 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 los 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}}}$

y así sucesivamente. 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. ^[16] Uno de estos sistemas es ZFC con el axioma de 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 adjunción ), aumentada por un esquema axiomático que establece que una propiedad que se cumple para el conjunto vacío y se cumple de una adjunción siempre que se cumple del adjunto debe cumplirse 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 definamos 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 un 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 la función única 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}}}$

Esta 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 queremos decir con un "número natural". ^[17] Henri Poincaré fue más cauteloso, diciendo que solo definían números naturales si eran consistentes ; si hay una prueba que parte solo de estos axiomas y deriva una contradicción como 0 = 1, entonces los axiomas son inconsistentes y no definen nada. ^[18] En 1900, David Hilbert planteó el problema de probar su consistencia usando solo métodos finitistas como el segundo de sus veintitrés problemas . ^[19] En 1931, Kurt Gödel demostró su segundo teorema de incompletitud , que muestra que tal prueba de consistencia no puede formalizarse dentro de la aritmética de Peano en sí, si la aritmética de Peano es consistente. ^[20]

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 exactamente lo que uno entiende por una prueba finitista. El propio Gödel señaló la posibilidad de dar una prueba de consistencia finitista de la aritmética de Peano o de 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 utilizando la teoría de tipos . ^[21] En 1936, Gerhard Gentzen dio una prueba de la consistencia de los axiomas de Peano, utilizando la inducción transfinita hasta un ordinal llamado ε 0 . ^[22] Gentzen explicó: "El objetivo del presente artículo es demostrar la consistencia de la teoría de números elemental o, más bien, reducir la cuestión de la consistencia a ciertos principios fundamentales". Se podría argumentar que la prueba de Gentzen es 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 de manera más abstracta como consistente en los árboles finitos , adecuadamente ordenados linealmente). No está claro si la prueba de Gentzen cumple o no los requisitos que Hilbert imaginó: no hay una definición generalmente aceptada de exactamente qué se entiende por una prueba finitista, y el propio Hilbert nunca dio una definición precisa.

La gran mayoría de los matemáticos contemporáneos creen que los axiomas de Peano son consistentes, basándose ya sea 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 abogan por el ultrafinitismo , rechazan los axiomas de Peano porque aceptar los axiomas equivale a aceptar la colección infinita de números naturales. En particular, se supone que la adición (incluida la función sucesora) y la multiplicación son totales . Curiosamente, existen teorías autoverificables que son similares a PA pero tienen resta y división en lugar de adición y multiplicación, que están axiomatizadas de tal manera que evitan probar oraciones que corresponden a la totalidad de la adición y la multiplicación, pero que aún pueden probar todos los teoremas verdaderos de PA, y sin embargo pueden extenderse a una teoría consistente que prueba su propia consistencia (enunciada como la inexistencia de una prueba de estilo Hilbert de "0=1"). ^[23] ${\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 de lógica de primer orden . ^[24] Las operaciones aritméticas de adición 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 sobre predicados (equivalentemente, conjuntos de números naturales en lugar de números naturales). Como alternativa, se puede considerar un esquema axiomático de primer orden de inducción. 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. ^[25] 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 lo tanto, existen conjuntos que no se pueden describir en el 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 contexto más restrictivo de la lógica de primer orden. Por lo 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 axiomas habituales de igualdad), que contiene seis de los siete axiomas de la aritmética de Robinson , es suficiente para este propósito: ^[26]

• ${\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 cada instancia 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 sólo tiene símbolos para el cero, así como para las operaciones de sucesor, adición y multiplicación. Hay muchas otras axiomatizaciones diferentes, pero equivalentes. Una de esas alternativas ^[27] utiliza un símbolo de relación de orden en lugar de la operación de sucesor y el lenguaje de semianillos ordenados discretamente (axiomas 1-7 para semianillos, 8-10 sobre el orden, 11-13 sobre la compatibilidad y 14-15 sobre la discreción):

1. ${\displaystyle \forall x,y,z\ ((x+y)+z=x+(y+z))}$, es decir, la adición es asociativa .
2. ${\displaystyle \forall x,y\ (x+y=y+x)}$, es decir, la adición 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, el cero es una identidad para la adición 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 bajo la adición del 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 bajo la multiplicación 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, el cero y el uno son distintos y no hay ningún elemento entre ellos. En otras palabras, el 0 está cubierto por el 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 incompleta 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 los demás elementos se denominan elementos no estándar . ${\displaystyle M}$ ${\displaystyle \leq }$ ${\displaystyle \mathbb {N} }$

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

Indecidibilidad e incompletitud

Según los teoremas de incompletitud de Gödel , la teoría de la AP (si es consistente) es incompleta. En consecuencia, hay enunciados de lógica de primer orden (LPO) que son verdaderos en el modelo estándar de la AP pero no son consecuencia de la axiomatización de la LPO. La incompletitud esencial ya surge para 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 hay un algoritmo para decidir si una oración FOL dada es una consecuencia de una axiomatización de primer orden de la aritmética de Peano o no. Por lo tanto, PA es un ejemplo de una 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 por fórmulas cuantificadas existencialmente (con variables libres) de PA . Las fórmulas de PA con mayor rango de cuantificador (más alternancias de cuantificador) 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 usuales satisfacen los axiomas de PA, también existen otros modelos (llamados " modelos no estándar "); el teorema de compacidad implica que no se puede excluir la existencia de elementos no estándar en la lógica de primer orden. ^{[28] El} teorema de Löwenheim-Skolem ascendente 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 solo un modelo, hasta el isomorfismo. ^[29] 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 se incorpora como un segmento inicial de todos los demás 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 preguntar si un modelo no estándar contable puede construirse explícitamente. 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 adición o multiplicación sea computable . ^[30] Este resultado muestra que es difícil ser completamente explícito al describir las operaciones de adición y multiplicación de un modelo no estándar contable de PA. Solo hay un tipo de orden posible de un modelo no estándar contable. Dejando que ω sea el tipo de orden de los números naturales, ζ sea el tipo de orden de los enteros y η sea el tipo de orden de los racionales, el tipo de orden de cualquier modelo no estándar contable de PA es ω + ζ · η , que puede visualizarse como una copia de los números naturales seguida de un ordenamiento lineal denso de copias de los enteros.

Desbordamiento

Un corte en un modelo no estándar M es un subconjunto no vacío C de M de modo que C está cerrado hacia abajo ( x < y y y ∈ C ⇒ x ∈ C ) y C está cerrado bajo sucesor. Un corte propio es un corte que es un subconjunto propio de M . Cada modelo no estándar tiene muchos cortes propios, 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 cualquier corte propio sea definible. El lema de desbordamiento, demostrado por primera vez por Abraham Robinson, formaliza este hecho.

Lema de desbordamiento ^[31]  —  Sea M un modelo no estándar de PA y sea C un corte propio 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 una c en M que es mayor que cada elemento de C tal que

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

Véase 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 Skolem
• Aritmética de Robinson
• Aritmética de segundo orden
• Teoría de números tipográficos

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 ya que tiene un elemento 0, 2 a 5 ya que no afecta las relaciones de igualdad, 6 y 8 ya que todas las piezas tienen un sucesor, excepto el elemento cero, y el axioma 7 ya que no hay dos dominós que derriben o sean 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 lo tanto por sustitución, contradiciendo la irreflexividad. Por lo tanto debe ser que . ${\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 Webster's Unabridged de Random House .
2. Grassman 1861.
3. Wang 1957, pp. 145, 147, "Es bastante conocido, a través del propio reconocimiento de 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 intento serio y bastante exitoso 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, pág. 1.
10. Peano 1908, pág. 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. Para pruebas formales, véase, por ejemplo, Archivo:Pruebas inductivas de propiedades de adición y multiplicación a partir de definiciones recursivas.pdf .
15. Suppes 1960, Hatcher 2014
16. Tarski y Givant 1987, sección 7.6.
17. Fritz 1952, p. 137
    Una ilustración de la "interpretación" es la propia definición de "número cardinal" de Russell. 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 que uno dedujera 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 }$
18. Gray 2013, p. 133
    Así, Poincaré se dedicó a ver si el logicismo podía generar la aritmética, más precisamente, la aritmética de los ordinales. Couturat, dijo Poincaré, había aceptado los axiomas de Peano como una definición de un número. Pero esto no funciona. No se puede demostrar que los axiomas estén libres de contradicción encontrando ejemplos de ellos, y cualquier intento de demostrar que estaban libres de contradicción examinando la totalidad de sus implicaciones requeriría el mismo principio de inducción matemática que Couturat creía que implicaban. Porque (en un pasaje posterior eliminado de S&M) o bien se asumía el principio para probarlo, lo que solo probaría que si es verdadero no es autocontradictorio, lo que no dice nada; o bien se usaba el principio en otra forma que la enunciada, en cuyo caso se debía demostrar que el número de pasos en el razonamiento de uno era un entero según la nueva definición, pero esto no se podía hacer (1905c, 834).
19. Hilbert 1902.
20. Gödel 1931.
21. Gödel 1958
22. Gentzen 1936
23. Villanueva 2001.
24. Partee, Ter Meulen & Wall 2012, pág. 215.
25. Harsanyi (1983).
26. Mendelson 1997, pág. 155.
27. Kaye 1991, págs. 16-18.
28. Hermes 1973, VI.4.3, que presenta un teorema de Thoralf Skolem
29. Hermes 1973, VI.3.1.
30. Kaye 1991, Sección 11.3.
31. Kaye 1991, págs. 70 y siguientes.

Fuentes

• Davis, Martin (1974). Computabilidad. Notas de Barry Jacobs . Courant Institute of Mathematical Sciences , 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 la 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. Oxford University Press . pp. 787–832. ISBN 978-0-19-853271-2.

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

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

• Gödel, Kurt (1931). "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I" (PDF) . Monatshefte für Mathematik . 38 . Véase Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados para obtener detalles sobre las traducciones al inglés: 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). "Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes". Dialéctica . 12 (3–4). Reimpreso en traducción al inglés en 1990. Obras completas de Gödel , Vol II. Solomon Feferman y otros, eds. Prensa de la Universidad de Oxford : 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.

• Gray, Jeremy (2013). "El ensayista". Henri Poincaré: una biografía científica . Princeton University Press . pág. 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.S2CID121297669  .​

• Hatcher, William S. (2014) [1982]. 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. Springer. ISBN 3-540-05819-2. ISSN  1431-4657.

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

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

• Landau, Edmund (1965). Grundlagen Der Analysis . Deriva los sistemas numéricos básicos a partir de los axiomas de Peano. Incluye vocabulario en inglés y alemán. AMS Chelsea Publishing . 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.). Springer. 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: Cambridge University Press. págs. 459–541. ISBN 978-0-521-26793-9.

• Partee, Barbara; Ter Meulen, Alice ; Wall, Robert (2012). Métodos matemáticos en lingüística. Springer. ISBN 978-94-009-2213-6.

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

• Peirce, C. S. (1881). "Sobre la lógica de los números". American Journal of Mathematics . 4 (1): 85–95. doi :10.2307/2369151. JSTOR  2369151. MR  1507856.

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

• Suppes, Patrick (1960). Teoría de conjuntos axiomáticos . Dover Publications . 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 . AMS Colloquium Publications. Vol. 41. American Mathematical Society . ISBN 978-0-8218-1041-5.

• Van Heijenoort, Jean (1967). De Frege a Gödel: un libro de consulta sobre lógica matemática, 1879-1931 . Harvard University Press. ISBN 978-0-674-32449-7.
  • Contiene traducciones de los dos artículos siguientes, con valiosos comentarios:
    • Dedekind, Richard (1890). Carta a Keferstein . En la pág. 100, reafirma y defiende sus axiomas de 1888. pp. 98–103.
    • Peano, Giuseppe (1889). Arithmetices principia, nova methodo exposita [ Los principios de la aritmética, presentados por un nuevo método ]. Extracto del tratado en el que Peano expuso por primera vez sus axiomas y definió recursivamente las operaciones aritméticas. Fratres Bocca. pp. 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". The Journal of Symbolic Logic . 22 (2). Association for Symbolic Logic : 145–158. doi :10.2307/2964176. JSTOR  2964176. S2CID  26896458.

• Willard, Dan E. (2001). "Sistemas axiomáticos autoverificables, el teorema de incompletitud y principios de reflexión relacionados" (PDF) . The Journal of Symbolic Logic . 66 (2): 536–596. doi :10.2307/2695030. JSTOR  2695030. MR  1833464. S2CID  2822314.

Lectura adicional

• Buss, Samuel R. (1998). "Capítulo II: Teoría de la demostración de primer orden de la aritmética". En Buss, Samuel R. (ed.). Handbook of Proof Theory . 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. Dover Publications. 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. "Los axiomas de Peano". MathWorld .
• 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 está licenciado bajo la Licencia Creative Commons Atribución/Compartir-Igual .