Lista de teorías de primer orden - List of first-order theories

En lógica matemática , una teoría de primer orden viene dada por un conjunto de axiomas en algún lenguaje. Esta entrada enumera algunos de los ejemplos más comunes utilizados en la teoría de modelos y algunas de sus propiedades.

Preliminares

Para cada estructura matemática natural hay una firma σ que enumera las constantes, funciones y relaciones de la teoría junto con sus aridades , de modo que el objeto es naturalmente una estructura σ . Dada una firma σ, existe un lenguaje único de primer orden L σ que se puede utilizar para capturar los hechos expresables de primer orden sobre la estructura σ.

Hay dos formas comunes de especificar teorías:

  1. Enumere o describa un conjunto de oraciones en el lenguaje L σ , llamados axiomas de la teoría.
  2. Dé un conjunto de σ-estructuras y defina una teoría como el conjunto de oraciones en L σ que se cumplen en todos estos modelos. Por ejemplo, la "teoría de los campos finitos" consta de todas las oraciones en el lenguaje de los campos que son verdaderas en todos los campos finitos.

Una teoría L σ puede:

Teorías de identidad pura

La firma de la teoría de la identidad pura está vacía, sin funciones, constantes o relaciones.

La teoría de la identidad pura no tiene axiomas (no lógicos). Es decidible.

Una de las pocas propiedades interesantes que se pueden enunciar en el lenguaje de la teoría de la identidad pura es la de ser infinito. Esto viene dado por un conjunto infinito de axiomas que indican que hay al menos 2 elementos, hay al menos 3 elementos, y así sucesivamente:

  • ∃ x 1 ∃ x 2 ¬ x 1 = x 2 , ∃ x 1 ∃ x 2 ∃ x 3 ¬ x 1 = x 2 ∧ ¬ x 1 = x 3 ∧ ¬ x 2 = x 3 , ...

Estos axiomas definen la teoría de un conjunto infinito .

La propiedad opuesta de ser finito no puede establecerse en lógica de primer orden para ninguna teoría que tenga modelos finitos arbitrariamente grandes: de hecho, tal teoría tiene modelos infinitos según el teorema de la compacidad . En general, si una propiedad puede establecerse mediante un número finito de oraciones de lógica de primer orden, entonces la propiedad opuesta también puede establecerse en lógica de primer orden, pero si una propiedad necesita un número infinito de oraciones, entonces su propiedad opuesta no puede establecerse. en lógica de primer orden.

Cualquier declaración de teoría de la identidad pura es equivalente a cualquiera de σ ( N ) o para · Iniciar ( N ) para algunos finito subconjunto N de los números enteros no negativos , donde σ ( N ) es la declaración de que el número de elementos es en N . Incluso es posible describir todas las teorías posibles en este lenguaje de la siguiente manera. Cualquier teoría es la teoría de todos los conjuntos de cardinalidad en N para algún subconjunto finito N de los enteros no negativos, o la teoría de todos los conjuntos cuya cardinalidad no está en N , para algún subconjunto finito o infinito N de los números no negativos enteros. (No hay teorías cuyos modelos sean exactamente conjuntos de cardinalidad N si N es un subconjunto infinito de enteros.) Las teorías completas son las teorías de conjuntos de cardinalidad n para algunos n finitos , y la teoría de conjuntos infinitos.

Un caso especial de esto es la teoría inconsistente definida por el axioma ∃ x ¬ x = x . Es una teoría perfectamente buena con muchas buenas propiedades: es completa, decidible, finitamente axiomatizable, etc. El único problema es que no tiene ningún modelo. Según el teorema de completitud de Gödel, es la única teoría (para cualquier lenguaje dado) sin modelos. No es lo mismo que la teoría del conjunto vacío (en versiones de lógica de primer orden que permiten que un modelo esté vacío): la teoría del conjunto vacío tiene exactamente un modelo, que no tiene elementos.

Relaciones unarias

Un conjunto de relaciones unarias P i para i en algún conjunto I se llama independiente si por cada dos subconjuntos finitos disjuntos A y B de I hay algún elemento x tal que P i ( x ) es verdadero para i en A y falso para i en B . La independencia se puede expresar mediante un conjunto de declaraciones de primer orden.

La teoría de un número contable de relaciones unarias independientes es completa, pero no tiene modelos atómicos . También es un ejemplo de una teoría superestable pero no totalmente trascendental .

Relaciones de equivalencia

La firma de las relaciones de equivalencia tiene un símbolo de relación infijo binario ~, sin constantes ni funciones. Las relaciones de equivalencia satisfacen los axiomas:

Algunas propiedades de primer orden de las relaciones de equivalencia son:

  • ~ tiene un número infinito de clases de equivalencia ;
  • ~ tiene exactamente n clases de equivalencia (para cualquier entero positivo fijo n );
  • Todas las clases de equivalencia son infinitas;
  • Todas las clases de equivalencia tienen un tamaño exactamente n (para cualquier entero positivo fijo n ).

La teoría de una relación de equivalencia con exactamente 2 clases de equivalencia infinitas es un ejemplo fácil de una teoría que es ω-categórica pero no categórica para ningún cardinal mayor .

La relación de equivalencia ~ no debe confundirse con el símbolo de identidad '=': si x = y entonces x ~ y , pero lo contrario no es necesariamente cierto. Las teorías de las relaciones de equivalencia no son tan difíciles o interesantes, pero a menudo dan ejemplos fáciles o contraejemplos para varias declaraciones.

Las siguientes construcciones se utilizan a veces para producir ejemplos de teorías con ciertos espectros ; de hecho, aplicándolos a un pequeño número de teorías explícitas T se obtienen ejemplos de teorías contables completas con todos los espectros incontables posibles. Si T es una teoría en algún idioma, definimos una nueva teoría 2 T agregando una nueva relación binaria con el idioma y agregando axiomas que indiquen que es una relación de equivalencia, de modo que hay un número infinito de clases de equivalencia, todas las cuales son modelos de camiseta . Es posible iterar esta construcción de manera transfinita : dado un α ordinal , defina una nueva teoría agregando una relación de equivalencia E β para cada β <α, junto con axiomas que indiquen que siempre que β <γ, entonces cada clase de equivalencia E γ es la unión de un número infinito de e ß equivalencia clases, y cada e 0 clase de equivalencia es un modelo de camiseta . De manera informal, uno puede visualizar modelos de esta teoría como árboles infinitamente ramificados de altura α con modelos de T adheridos a todas las hojas.

Pedidos

La firma de órdenes no tiene constantes ni funciones, y un símbolo de relación binaria ≤. (Por supuesto, es posible usar ≥, <o> en su lugar como la relación básica, con los cambios menores obvios en los axiomas.) Definimos x ≥ y , x < y , x > y como abreviaturas para y ≤ x , x ≤ y ∧¬ y ≤ x , y < x ,

Algunas propiedades de primer orden de los pedidos:

  • Transitivo : ∀ x ∀ y ∀ z x ≤ y ∧ y ≤ z → x ≤ z
  • Reflexivo : ∀ x x ≤ x
  • Antisimétrico : ∀ x ∀ y x ≤ y ∧ y ≤ x → x = y
  • Parcial : Transitivo ∧ Reflexivo ∧ Antisimétrico;
  • Lineal (o total ): Parcial ∧ ∀ x ∀ y x ≤ y ∨ y ≤ x
  • Denso : ∀ x ∀ z x < z → ∃ y x < y ∧ y < z ("Entre 2 elementos distintos hay otro elemento")
  • Hay un elemento más pequeño: ∃ x ∀ y x ≤ y
  • Hay un elemento más grande: ∃ x ∀ y y ≤ x
  • Todo elemento tiene un sucesor inmediato: ∀ x ∃ y ∀ z x < z ↔ y ≤ z

La teoría DLO de órdenes lineales densos sin puntos finales (es decir, sin elemento más pequeño o más grande) es completa, ω-categórica, pero no categórica para ningún cardinal incontable. Hay otras tres teorías muy similares: la teoría de los órdenes lineales densos con un:

  • El elemento más pequeño pero no más grande;
  • Elemento más grande pero no más pequeño;
  • Elemento más grande y más pequeño.

Estar bien ordenado ("cualquier subconjunto no vacío tiene un elemento mínimo") no es una propiedad de primer orden; la definición habitual implica cuantificar todos los subconjuntos .

Celosías

Las celosías se pueden considerar como tipos especiales de conjuntos parcialmente ordenados, con una firma que consta de un símbolo de relación binaria ≤, o como estructuras algebraicas con una firma que consta de dos operaciones binarias ∧ y ∨. Los dos enfoques se pueden relacionar definiendo a ≤ b para que signifique a ∧ b = a .

Para dos operaciones binarias, los axiomas de una celosía son:

Leyes conmutativas :
Leyes asociativas :
Leyes de absorción :

Para una relación ≤ los axiomas son:

  • Los axiomas que indican ≤ son un orden parcial, como se indicó anteriormente.
  • (existencia de c = a∧b)
  • (existencia de c = a∨b)

Las propiedades de primer orden incluyen:

  • ( celosías distributivas )
  • ( celosías modulares )

Las álgebras de Heyting se pueden definir como celosías con ciertas propiedades adicionales de primer orden.

La integridad no es una propiedad de primer orden de las celosías.

Gráficos

Artículo principal: Lógica de gráficos

La firma de los gráficos no tiene ninguna constante o funciones, y uno binario símbolo de relación R , en donde R ( x , y ) se lee como "no hay un borde de x a y ".

Los axiomas de la teoría de grafos son

La teoría de las gráficas aleatorias tiene los siguientes axiomas adicionales para cada entero positivo n :

  • Para dos conjuntos finitos disjuntos de tamaño n , hay un punto unido a todos los puntos del primer conjunto y a ningún punto del segundo conjunto. (Para cada n fija , es fácil escribir esta declaración en el lenguaje de las gráficas).

La teoría de las gráficas aleatorias es ω categórica, completa y decidible, y su modelo contable se llama gráfica de Rado . Un enunciado en el lenguaje de los gráficos es verdadero en esta teoría si y solo si la probabilidad de que un gráfico aleatorio de n - vértices modele el enunciado tiende a 1 en el límite cuando n va al infinito.

Álgebras booleanas

Hay varias firmas y convenciones diferentes que se utilizan para las álgebras booleanas :

  1. La firma tiene dos constantes, 0 y 1, y dos funciones binarias ∧ y ∨ ("y" y "o"), y una función unaria ¬ ("no"). Esto puede resultar confuso ya que las funciones utilizan los mismos símbolos que las funciones proposicionales de la lógica de primer orden.
  2. En la teoría de conjuntos , una convención común es que el lenguaje tiene dos constantes, 0 y 1, y dos funciones binarias · y +, y una función unaria -. Las tres funciones tienen la misma interpretación que las funciones de la primera convención. Desafortunadamente, esta convención choca gravemente con la próxima convención:
  3. En álgebra , la convención habitual es que el lenguaje tiene dos constantes, 0 y 1, y dos funciones binarias · y +. La función · tiene el mismo significado que ∧, pero a + b significa a ∨ b ∧¬ ( a ∧ b ). La razón de esto es que los axiomas de un álgebra de Boole son entonces solo los axiomas de un anillo con 1 más ∀ x x 2 = x . Desafortunadamente, esto choca con la convención estándar en la teoría de conjuntos dada anteriormente.

Los axiomas son:

  • Los axiomas de una red distributiva (ver arriba)
  • ∀a a ∧¬ a = 0, ∀a a ∨¬ a = 1 (propiedades de la negación)
  • Algunos autores agregan el axioma extra ¬0 = 1, para excluir el álgebra trivial con un elemento.

Tarski demostró que la teoría de las álgebras de Boole es decidible.

Escribimos x ≤ y como abreviatura de x ∧ y = x , y átomo ( x ) como abreviatura de ¬ x = 0 ∧ ∀ y y ≤ x → y = 0 ∨ y = x , se lee como " x es un átomo ", en otras palabras, un elemento distinto de cero sin nada entre él y 0. Aquí hay algunas propiedades de primer orden de las álgebras booleanas:

  • Atómico : ∀ x x = 0 ∨ ∃ y y ≤ x ∧ átomo ( y )
  • Sin átomo : ∀ x ¬atom ( x )

La teoría de las álgebras booleanas sin átomos es ω-categórica y completa.

Para cualquier álgebra de Boole B , hay varios invariantes definidos como sigue.

  • el ideal I ( B ) consta de elementos que son la suma de un elemento atómico y uno sin átomo (un elemento sin átomos debajo de él).
  • Las álgebras del cociente B i de B se definen inductivamente por B 0 = B , B k +1 = B k / I ( B k ).
  • El invariante m ( B ) es el número entero más pequeño tal que B m +1 es trivial, o ∞ si no existe tal número entero.
  • Si m ( B ) es finito, el invariante n ( B ) es el número de átomos de B m ( B ) si este número es finito, o ∞ si este número es infinito.
  • El invariante l ( B ) es 0 si B m ( B ) es atómico o si m ( B ) es ∞, y 1 en caso contrario.

Entonces, dos álgebras de Boole son elementalmente equivalentes si y solo si sus invariantes l , m y n son iguales. En otras palabras, los valores de estos invariantes clasifican las posibles terminaciones de la teoría de las álgebras de Boole. Entonces las posibles teorías completas son:

  • El álgebra trivial (si se permite; a veces se incluye 0 is 1 como axioma).
  • La teoría con m = ∞
  • Las teorías con m un número natural, n un número natural o ∞, y l = 0 o 1 (con l = 0 si n = 0).

Grupos

La firma de la teoría de grupos tiene una constante 1 (la identidad), una función de arity 1 (la inversa) cuyo valor en t se denota por t −1 , y una función de arity 2, que generalmente se omite de los términos. Para cualquier número entero n , t n es una abreviatura para el término obvia para el n ésima potencia de t .

Los grupos están definidos por los axiomas

  • Identidad : ∀ x 1 x = x ∧ x 1 = x
  • Inversa : ∀ x x −1 x = 1 ∧ xx −1 = 1
  • Asociatividad : ∀ x ∀ y ∀ z ( xy ) z = x ( yz )

Algunas propiedades de los grupos que se pueden definir en el idioma de primer orden de los grupos son:

  • Abeliano : ∀ x ∀ y xy = yx .
  • Sin torsión : ∀ x x 2 = 1 → x = 1, ∀ x x 3 = 1 → x = 1, ∀ x x 4 = 1 → x = 1, ...
  • Divisible : ∀ x ∃ y y 2 = x , ∀ x ∃ y y 3 = x , ∀ x ∃ y y 4 = x , ...
  • Infinito (como en la teoría de la identidad)
  • Exponente n (para cualquier entero positivo fijo n ): ∀ x x n = 1
  • Nilpotente de clase n (para cualquier entero positivo fijo n )
  • Resoluble de clase n (para cualquier entero positivo fijo n )

La teoría de los grupos abelianos es decidible. La teoría de infinitos grupos abelianos divisibles sin torsión es completa, al igual que la teoría de infinitos grupos abelianos de exponente p (para p primo ).

La teoría de los grupos finitos es el conjunto de enunciados de primer orden en el lenguaje de los grupos que son verdaderos en todos los grupos finitos (hay muchos modelos infinitos de esta teoría). No es completamente trivial encontrar una afirmación de este tipo que no sea cierta para todos los grupos: un ejemplo es "dados dos elementos de orden 2, o son conjugados o hay un elemento no trivial que conmuta con ambos".

Las propiedades de ser finito, libre , simple o de torsión no son de primer orden. Más precisamente, la teoría de primer orden de todos los grupos con una de estas propiedades tiene modelos que no tienen esta propiedad.

Anillos y campos

La firma de anillos (unitales) tiene dos constantes 0 y 1, dos funciones binarias + y × y, opcionalmente, una función de negación unaria -.

Anillos

Axiomas: la suma convierte el anillo en un grupo abeliano, la multiplicación es asociativa y tiene una identidad 1, y la multiplicación es distributiva a la izquierda y a la derecha.

Anillos conmutativos

Los axiomas para anillos más ∀ x ∀ y xy = yx .

Campos

Los axiomas para anillos conmutativos más ∀ x (¬ x = 0 → ∃ y xy = 1) y ¬ 1 = 0. Muchos de los ejemplos que se dan aquí solo tienen axiomas universales o algebraicos . La clase de estructuras que satisfacen tal teoría tiene la propiedad de estar cerrada bajo subestructura. Por ejemplo, un subconjunto de un grupo cerrado bajo las acciones grupales de multiplicación e inverso es nuevamente un grupo. Dado que la firma de los campos generalmente no incluye el inverso multiplicativo y aditivo, los axiomas para los inversos no son universales y, por lo tanto, una subestructura de un campo cerrado bajo la suma y la multiplicación no siempre es un campo. Esto puede remediarse agregando funciones inversas unarias al lenguaje.

Para cualquier entero positivo n, la propiedad de que todas las ecuaciones de grado n tienen raíz se puede expresar mediante una sola oración de primer orden:

  • ∀ un 1 ∀ un 2 ... ∀ un n ∃ x (... (( x + un 1 ) x + un 2 ) x + ...) x + un n = 0

Campos perfectos

Los axiomas de los campos, más los axiomas de cada número primo p, indican que si p  1 = 0 (es decir, el campo tiene la característica p ), entonces cada elemento de campo tiene una p- ésima raíz.

Campos algebraicamente cerrados de característica p

Los axiomas de los campos, más para cada positivo n el axioma de que todos los polinomios de grado n tienen una raíz, más los axiomas que fijan la característica. Los ejemplos clásicos de teorías completas. Categórico en todos los incontables cardenales. La teoría ACF p tiene una propiedad universal del dominio , en el sentido de que cada estructura N satisfacer los axiomas universales de ACF p es una subestructura de una suficientemente grande algebraicamente cerrado , y, además, cualquier dos de tales inclusiones N → M inducen una automorphism de M .

Campos finitos

La teoría de los campos finitos es el conjunto de todos los enunciados de primer orden que son verdaderos en todos los campos finitos. Se pueden dar ejemplos significativos de tales afirmaciones, por ejemplo, aplicando el teorema de Chevalley-Warning , sobre los campos primos . El nombre es un poco engañoso ya que la teoría tiene muchos modelos infinitos. Ax demostró que la teoría es decidible.

Campos formalmente reales

Los axiomas de los campos más, para cada entero positivo n , el axioma:

  • ∀ un 1 ∀ un 2 ... ∀ un n un 1 a 1 + un 2 a 2 + ... + a n un n = 0 → un 1 = 0∧ un 2 = 0∧ ... ∧ un n = 0.

Es decir, 0 no es una suma de cuadrados no trivial.

Campos cerrados reales

Los axiomas para campos formalmente reales más los axiomas:

  • ∀ x ∃ y ( x = yy ∨ x + yy = 0);
  • para cada entero positivo impar n , el axioma que establece que todo polinomio de grado n tiene una raíz.

La teoría de los campos cerrados reales es eficaz y completa y, por tanto, decidible (el teorema de Tarski-Seidenberg ). La adición de más símbolos de función (por ejemplo, la función exponencial, la función seno) puede cambiar la decidibilidad .

campos p -ádicos

Ax y Kochen (1965) demostraron que la teoría de los campos p -ádicos es decidible y le dieron un conjunto de axiomas.

Geometría

Los axiomas para varios sistemas de geometría generalmente usan un lenguaje escrito, con los diferentes tipos correspondientes a diferentes objetos geométricos como puntos, líneas, círculos, planos, etc. La firma a menudo consistirá en relaciones de incidencia binarias entre objetos de diferentes tipos; por ejemplo, la relación entre un punto y una línea. La firma puede tener relaciones más complicadas; por ejemplo, la geometría ordenada podría tener una relación de "intermediación" ternaria para 3 puntos, que dice si uno se encuentra entre otros dos, o una relación de "congruencia" entre 2 pares de puntos.

Algunos ejemplos de sistemas de geometría axiomatizados incluyen geometría ordenada , geometría absoluta , geometría afín , geometría euclidiana , geometría proyectiva y geometría hiperbólica . Para cada una de estas geometrías hay muchos sistemas de axiomas diferentes y desiguales para varias dimensiones. Algunos de estos sistemas de axiomas incluyen axiomas de "completitud" que no son de primer orden.

Como ejemplo típico, los axiomas de la geometría proyectiva utilizan 2 tipos, puntos y líneas, y una relación de incidencia binaria entre puntos y líneas. Si las variables de punto y línea se indican con letras minúsculas y mayúsculas, y un incidente de A se escribe como aA , entonces un conjunto de axiomas es

  • (Hay una línea que pasa por 2 puntos distintos a , b ...)
  • (... que es único)
  • (Axioma de Veblen: si ab y cd se encuentran en rectas que se cruzan, entonces también lo hacen ac y bd ).
  • (Cada línea tiene al menos 3 puntos)

Euclides no estableció todos los axiomas de la geometría euclidiana explícitamente, y Hilbert dio la primera lista completa en los axiomas de Hilbert . Esta no es una axiomatización de primer orden, ya que uno de los axiomas de Hilbert es un axioma de completitud de segundo orden. Los axiomas de Tarski son una axiomatización de primer orden de la geometría euclidiana. Tarski demostró que este sistema de axiomas es completo y decidible al relacionarlo con la teoría completa y decidible de los campos cerrados reales.

Álgebra diferencial

La firma es la de los campos (0, 1, +, -, ×) junto con una función unaria ∂, la derivación. Los axiomas son los de campos junto con

Para esta teoría se puede agregar la condición de que la característica sea p , un primo o cero, para obtener la teoría DF p de campos diferenciales de característica p (y de manera similar con las otras teorías siguientes).

Si K es un campo diferencial, entonces el campo de constantes La teoría de campos diferencialmente perfectos es la teoría de campos diferenciales junto con la condición de que el campo de constantes sea perfecto; en otras palabras, para cada primo p tiene el axioma:

(No tiene mucho sentido exigir que todo el campo sea un campo perfecto , porque en una característica distinta de cero esto implica que el diferencial es 0). Por razones técnicas relacionadas con la eliminación del cuantificador , a veces es más conveniente forzar el campo constante para ser perfecto agregando un nuevo símbolo r a la firma con los axiomas

Adición

La teoría de los números naturales con una función sucesora tiene una firma que consta de una constante 0 y una función unaria S ("sucesor": S ( x ) se interpreta como x +1), y tiene axiomas:

  1. ∀x ¬ Sx = 0
  2. ∀x∀y Sx = Sy → x = y
  3. Sea P ( x ) una fórmula de primer orden con una única variable libre x . Entonces la siguiente fórmula es un axioma:
( P (0) ∧ ∀ x ( P ( x ) → P ( Sx ))) → ∀ y P ( y ).

El último axioma (inducción) puede ser reemplazado por los axiomas

  • Para cada entero n > 0, el axioma ∀x SSS ... Sx ≠ x (con n copias de S )
  • ∀x ¬ x = 0 → ∃y Sy = x

La teoría de los números naturales con función de sucesor es completa y decidible, y es κ-categórica para κ incontables pero no para κ contables.

La aritmética de Presburger es la teoría de los números naturales bajo suma, con una firma que consta de una constante 0, una función unaria S y una función binaria +. Es completo y decidible. Los axiomas son

  1. ∀x ¬ Sx = 0
  2. ∀x∀y Sx = Sy → x = y
  3. ∀xx + 0 = x
  4. ∀x∀yx + Sy = S (x + y)
  5. Sea P ( x ) una fórmula de primer orden con una única variable libre x . Entonces la siguiente fórmula es un axioma:
( P (0) ∧ ∀ x ( P ( x ) → P ( Sx ))) → ∀ y P ( y ).

Aritmética

Muchas de las teorías de primer orden descritas anteriormente pueden extenderse para completar teorías consistentes enumerables de manera recursiva. Esto ya no es cierto para la mayoría de las siguientes teorías; Por lo general, pueden codificar tanto la multiplicación como la suma de números naturales, y esto les da suficiente poder para codificarse a sí mismos, lo que implica que se aplica el teorema de incompletitud de Gödel y que las teorías ya no pueden ser completas y recursivamente enumerables (a menos que sean inconsistentes).

La firma de una teoría de la aritmética tiene:

Algunos autores consideran que la firma contiene una constante 1 en lugar de la función S , luego definen S de la manera obvia como St = 1 + t .

Aritmética de Robinson (también llamada Q ). Los axiomas (1) y (2) gobiernan el elemento distinguido 0. (3) asegura que S es una inyección . Los axiomas (4) y (5) son la definición recursiva estándar de suma; (6) y (7) hacen lo mismo para la multiplicación. La aritmética de Robinson se puede considerar como aritmética de Peano sin inducción. Q es una teoría débil para la que se cumple el teorema de incompletitud de Gödel . Axiomas:

  1. ∀ x ¬ S x = 0
  2. ∀ x ¬ x = 0 → ∃ y S y = x
  3. ∀ x ∀ y S x = S y → x = y
  4. ∀ x x + 0 = x
  5. ∀ x ∀ y x + S y = S ( x + y )
  6. ∀ x x × 0 = 0
  7. ∀ x ∀ y x × S y = ( x × y ) + x .

IΣ n es la aritmética de Peano de primer orden con inducción restringida a Σ n fórmulas (para n = 0, 1, 2, ...). La teoría IΣ 0 a menudo se denota por IΔ 0 . Se trata de una serie de fragmentos cada vez más poderosos de la aritmética de Peano. El caso n  = 1 tiene aproximadamente la misma fuerza que la aritmética recursiva primitiva (PRA). La aritmética de función exponencial (EFA) es IΣ 0 con un axioma que establece que x y existe para todo x e y (con las propiedades habituales).

Aritmética de Peano de primer orden , PA . La teoría "estándar" de la aritmética. Los axiomas son los axiomas de la aritmética de Robinson anterior, junto con el esquema de axiomas de inducción:

  • para cualquier fórmula φ en el idioma de PA . φ puede contener variables libres distintas de x .

El artículo de Kurt Gödel de 1931 demostró que la PA está incompleta y no tiene terminaciones enumerables recursivamente consistentes.

Aritmética completa (también conocido como verdadera aritmética ) es la teoría del modelo estándar de la aritmética, los números naturales N . Es completo, pero no tiene un conjunto de axiomas enumerables de forma recursiva.

Para los números reales , la situación es ligeramente diferente: el caso que incluye solo la suma y la multiplicación no puede codificar los números enteros y, por lo tanto, el teorema de incompletitud de Gödel no se aplica . Surgen complicaciones al agregar más símbolos de función (por ejemplo, exponenciación).

Aritmética de segundo orden

La aritmética de segundo orden puede referirse a una teoría de primer orden (a pesar del nombre) con dos tipos de variables, consideradas como variables en enteros y subconjuntos de enteros. (También existe una teoría de la aritmética en la lógica de segundo orden que se llama aritmética de segundo orden. Tiene un solo modelo, a diferencia de la teoría correspondiente en la lógica de primer orden, que está incompleta). La firma será típicamente la firma 0, S , +, × de aritmética, junto con una relación de pertenencia ∈ entre enteros y subconjuntos (aunque existen numerosas variaciones menores). Los axiomas son los de la aritmética de Robinson , junto con los esquemas de axiomas de inducción y comprensión .

Hay muchas subteorías diferentes de aritmética de segundo orden que difieren en qué fórmulas se permiten en los esquemas de inducción y comprensión. En orden de resistencia creciente, cinco de los sistemas más comunes son

  • , Comprensión recursiva
  • , Lema de König débil
  • , Comprensión aritmética
  • , Recursión aritmética transfinita
  • , comprensión

Estos se definen en detalle en los artículos sobre aritmética de segundo orden y matemáticas inversas .

Establecer teorías

La firma habitual de la teoría de conjuntos tiene una relación binaria ∈, sin constantes ni funciones. Algunas de las teorías siguientes son "teorías de clases" que tienen dos tipos de objetos, conjuntos y clases. Hay tres formas comunes de manejar esto en la lógica de primer orden:

  1. Utilice lógica de primer orden con dos tipos.
  2. Utilice la lógica ordinaria de primer orden, pero agregue un nuevo predicado unario "Conjunto", donde "Conjunto ( t )" significa informalmente " t es un conjunto".
  3. Utilice la lógica ordinaria de primer orden y, en lugar de agregar un nuevo predicado al lenguaje, trate "Set ( t )" como una abreviatura de "∃ y t ∈ y "

Algunas teorías de conjuntos de primer orden incluyen:

Algunos axiomas adicionales de primer orden que se pueden agregar a uno de estos (generalmente ZF) incluyen:

Ver también

Referencias

Otras lecturas