Aritmética de primer orden - First-order arithmetic

En la teoría de conjuntos y la lógica matemática, la aritmética de primer orden es una colección de sistemas axiomáticos que formalizan los números naturales y subconjuntos de los naturales. Es una opción para la teoría axiomática como base para muchas matemáticas, pero no todas. El axioma principal de primer orden es la aritmética de Peano , creada por Giuseppe Peano :

  • : 0 es un número natural.
  • : La igualdad es reflexiva .
  • : La igualdad es simétrica .
  • : La igualdad es transitiva .
  • : Los números naturales están cerrados bajo igualdad.
  • : Los números naturales se cierran bajo S (la operación sucesora).
  • : S es una inyección .
  • : No hay un número natural cuyo sucesor sea cero.
  • : Si K es un conjunto tal que 0 está en K, y para cada número natural n, n estar en K implica que S (n) está en K, entonces K contiene todos los números naturales.

La aritmética de Peano tiene un ordinal de teoría de la prueba de .

Más sobre aritmética de Peano

Las diversas axiomatizaciones de la aritmética de Peano son muy diferentes, pero equivalentes. Mientras que algunas axiomatizaciones, como la descrita recientemente (la definición original) usan una firma que contiene solo símbolos de 0, sucesor, adición y multiplicación, otras axiomatizaciones usan el lenguaje de semianillo ordenado, incluido un símbolo de relación de orden adicional. Una de esas axiomatizaciones comienza con los siguientes axiomas que describen un semirriado discretamente ordenado:

  1. , es decir, la adición es asociativa .
  2. , es decir, la suma es conmutativa .
  3. , es decir, la multiplicación es asociativa.
  4. , es decir, la multiplicación es conmutativa.
  5. , es decir, la multiplicación se distribuye sobre la suma.
  6. , es decir, cero es una identidad para la suma y un elemento absorbente para la multiplicación.
  7. , es decir, uno es una identidad para la multiplicación.
  8. , es decir, el operador '<' es transitivo .
  9. , es decir, el operador '<' es irreflexivo .
  10. , es decir, el pedido satisface la tricotomía .
  11. , es decir, el orden se conserva añadiendo el mismo elemento.
  12. , es decir, el orden se conserva al multiplicar por el mismo elemento positivo.
  13. , es decir, dados dos elementos distintos, el más grande es el más pequeño más otro elemento.
  14. , es decir, cero y uno son distintos y no hay ningún elemento entre ellos.
  15. , es decir, cero es el elemento mínimo.

Estos axiomas se conocen como PA - ; la teoría PA se obtiene sumando el esquema de inducción de primer orden . Una característica importante de PA - 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.

Aritmética de Robinson Q

La aritmética de Robinson es un fragmento de primer orden finitamente axiomatizado de la aritmética de Peano (PA), producido por primera vez en 1950 por RM Robinson . A menudo se le conoce como Q. Q es casi idéntico a PA sin el esquema de axioma de inducción matemática (PA - ). Q es más débil que PA, pero su lenguaje es el mismo y las dos teorías están incompletas . La lógica de fondo de Q es lógica de primer orden con identidad, denotada por el infijo '='. Los individuos, llamados números naturales, son miembros de un conjunto llamado N con un miembro distinguido 0, llamado cero. Hay tres operaciones sobre N:

  • Una operación unaria llamada sucesor y denotada por el prefijo S;
  • Dos operaciones binarias, suma y multiplicación, denotadas por infijo + y ·, respectivamente.

Los axiomas son:

  • : 0 no es el sucesor de ningún número.
  • : Si el sucesor de x es idéntico al sucesor de y, entonces xey son idénticos.
  • Todo número natural es 0 o el sucesor de algún número.

La aritmética de Robinson tiene un ordinal de teoría de la prueba de .

Definiciones inductivas iteradas

El sistema de definiciones inductivas iteradas es una jerarquía de fuertes sistemas matemáticos desarrollados por el matemático alemán Wilfried Buchholz, conocido por crear la función psi de Buchholz . ID ν extiende PA por ν puntos fijos mínimos iterados de operadores monótonos. Si ν = ω, los axiomas son:

  • Los axiomas de la aritmética de Peano
  • para cada L ID- fórmula F (x)

Para ν ≠ ω, los axiomas son:

  • Los axiomas de la aritmética de Peano
  • para cada L ID- fórmula F (x) y todo u <ν

es una versión debilitada de . En el sistema de , un conjunto se llama en cambio definido inductivamente si para algún operador monótono , es un punto fijo de , en lugar del punto menos fijo. Esta sutil diferencia hace que el sistema sea significativamente más débil:, while .

se debilita aún más. En , no solo usa puntos fijos en lugar de puntos mínimos fijos, sino que también tiene inducción solo para fórmulas positivas. Una vez más, esta sutil diferencia hace que el sistema sea aún más débil:, while .

es la más débil de todas las variantes de , basada en tipos W. La cantidad de debilitamiento en comparación con las definiciones inductivas iteradas regulares es idéntica a la eliminación de la inducción de barras dado un determinado subsistema de aritmética de segundo orden . , mientras .

es un fortalecimiento de "despliegue" de . No es exactamente un sistema aritmético de primer orden, pero captura lo que se puede obtener mediante el razonamiento predicativo basado en definiciones inductivas generalizadas iteradas ν veces. La cantidad de aumento de fuerza es idéntica al aumento de a :, mientras .

es un automorfismo de . , pero aún es más débil que .

es un automorfismo de . , pero aún es más débil que .

es un automorfismo de . , donde es la jerarquía de Veblen con puntos mínimos fijos iterados numerables.

Otros sistemas de primer orden

PA -

PA : es la teoría de primer orden de la parte no negativa de un anillo discretamente ordenado. Un anillo es un conjunto equipado con dos operaciones binarias: (suma) y (multiplicación) que satisfacen los siguientes tres conjuntos de axiomas, llamados axiomas del anillo:

  • es asociativo, es conmutativo, es la identidad aditiva y es el inverso aditivo de .
  • es asociativo y es la identidad multiplicativa .
  • para todos , y en .
  • para todos , y en .

PA : tiene un ordinal de teoría de la prueba de .

RFA

RFA es aritmética de funciones rudimentarias . Una función rudimentaria es una función que se puede obtener de las siguientes operaciones:

  • es rudimentario
  • es rudimentario
  • es rudimentario
  • Cualquier composición de funciones rudimentarias es rudimentaria
  • es rudimentario

Para cualquier conjunto M, sea ​​rud ( M ) el conjunto más pequeño que contiene M ∪ { M } cerrado bajo las operaciones rudimentarias. RFA es una versión de aritmética basada en funciones rudimentarias. RFA tiene un ordinal de teoría de la prueba de ω 2 .

0 / IΣ 1

0 e IΣ 1 son aritmética básica con inducción para Δ 0 - y Σ 1 - predicciones, respectivamente. Tenga en cuenta que cuando las personas se refieren a IΔ 0 , IΔ 0 es aritmética básica con inducción para Δ 0 -predicados, pero sin un axioma que afirme que la exponenciación es total , mientras que IΔ 0 con tal axioma se denomina IΔ 0 + . IΔ 0 n para 1 <n <ω es IΔ 0 + aumentado por un axioma que asegura que cada elemento del n -ésimo nivel de la jerarquía de Grzegorczyk es total. IΔ 0 tiene un ordinal de teoría de la prueba de ω 2 . IΔ 0 + . tiene un ordinal de teoría de la demostración de ω 3 . IΔ 0 n tiene un ordinal teórico de prueba de ω n . IΣ 1 tiene un ordinal de teoría de la prueba de ω ω .

EFA

EFA es aritmética de funciones elementales. Su idioma contiene:

  • dos constantes 0, 1,
  • tres operaciones binarias +, ×, exp, con exp ( x , y ) generalmente escrito como x y ,
  • un símbolo de relación binaria <(Esto no es realmente necesario ya que se puede escribir en términos de las otras operaciones y a veces se omite, pero es conveniente para definir cuantificadores acotados).

Los cuantificadores acotados son aquellos de la forma ∀ (x <y) y ∃ (x <y) que son abreviaturas de ∀ x (x <y) → ... y ∃x (x <y) ∧ ... en la forma habitual camino. Los axiomas de EFA son

  • Los axiomas de la aritmética de Robinson para 0, 1, +, ×, <
  • Los axiomas para la exponenciación: x 0 = 1, x y +1 = x y × x .
  • Inducción para fórmulas cuyos cuantificadores están acotados (pero que pueden contener variables libres).

PRA

PRA es aritmética recursiva primitiva, una formalización libre de cuantificadores de los números naturales . El lenguaje de PRA consiste en:

Los axiomas lógicos de PRA son:

Las reglas lógicas de PRA son modus ponens y sustitución de variables .

Los axiomas no lógicos son:

y ecuaciones de definición recursivas para cada función recursiva primitiva según se desee.

Referencias

  1. van Heijenoort, Jean (1967). De Frege a Gödel . pag. 83. ISBN 978-0-67-432449-7.
  2. ^ Kaye, Richard (1991). Modelos de aritmética de Peano . págs. 16-18.