Lista de teorías de primer orden

Teorías en lógica matemática

En la lógica de primer orden , una teoría de primer orden se da mediante un conjunto de axiomas en algún lenguaje. En esta entrada se enumeran 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 existe una signatura σ 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 signatura σ existe un lenguaje de primer orden único L _σ que puede utilizarse 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 _σ , llamadas axiomas de la teoría.
2. Proporcione 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 cuerpos finitos" consiste en todas las oraciones en el lenguaje de los cuerpos que son verdaderas en todos los cuerpos finitos.

Una teoría L _{σ puede:}

• Sea coherente: no existe prueba de contradicción;
• ser satisfacible: existe una σ-estructura para la cual las oraciones de la teoría son todas verdaderas (por el teorema de completitud , la satisfacibilidad es equivalente a la consistencia);
• ser completo: para cualquier enunciado, tanto él como su negación son demostrables;
• tener eliminación de cuantificador ;
• eliminar imaginarios ;
• ser finitamente axiomatizable ;
• ser decidible : Hay un algoritmo para decidir qué afirmaciones son demostrables;
• ser axiomatizable recursivamente;
• ser modelo completo o submodelo completo;
• ser κ-categórico : Todos los modelos de cardinalidad κ son isomorfos;
• ser estable o inestable;
• ser ω-estable (lo mismo que totalmente trascendental para las teorías contables );
• ser superestable
• tener un modelo atómico ;
• tener un modelo primordial ;
• tener un modelo saturado .

Teorías de identidad pura

La firma de la teoría de la identidad pura está vacía, sin funciones, constantes ni 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 se da por un conjunto infinito de axiomas que establecen que hay al menos 2 elementos, hay al menos 3 elementos, y así sucesivamente:

• ∃ x ₁ ∃ x ₂ ¬ x ₁ = x ₂ , ∃ x ₁ ∃ x ₂ ∃ x ₃ ¬ x ₁ = x ₂ ∧ ¬ x ₁ = x ₃ ∧ ¬ x ₂ = x ₃ ,...

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

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

Cualquier enunciado de la teoría de la identidad pura es equivalente a σ( N ) o a ¬σ( N ) para algún subconjunto finito N de los enteros no negativos , donde σ( N ) es el enunciado de que el número de elementos está en N . Incluso es posible describir todas las teorías posibles en este lenguaje de la siguiente manera. Cualquier teoría es o bien la teoría de todos los conjuntos de cardinalidad en N para algún subconjunto finito N de los enteros no negativos, o bien la teoría de todos los conjuntos cuya cardinalidad no está en N , para algún subconjunto finito o infinito N de los enteros no negativos. (No hay teorías cuyos modelos sean exactamente conjuntos de cardinalidad N si N es un subconjunto infinito de los enteros). Las teorías completas son las teorías de conjuntos de cardinalidad n para algún n finito , 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 modelos en absoluto. Por el teorema de completitud de Gödel, es la única teoría (para cualquier lenguaje dado) sin modelos. ^[1] 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 sea 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 para 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 puede expresarse mediante un conjunto de enunciados 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 que es superestable pero no totalmente trascendental .

Relaciones de equivalencia

La signatura de las relaciones de equivalencia tiene un símbolo de relación infijo binario ~, ninguna constante ni ninguna función. Las relaciones de equivalencia satisfacen los axiomas:

• Reflexivo ∀ x x ~ x ;
• Simétrico ∀ x ∀ y x ~ y → y ~ x ;
• Transitiva : ∀ x ∀ y ∀ z ( x ~ y ∧ y ~ z ) → x ~ z .

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 la inversa no es necesariamente cierta. Las teorías de las relaciones de equivalencia no son tan difíciles ni interesantes, pero a menudo ofrecen ejemplos o contraejemplos fáciles para diversas afirmaciones.

Las siguientes construcciones se utilizan a veces para producir ejemplos de teorías con ciertos espectros ; de hecho, al aplicarlas 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 lenguaje, definimos una nueva teoría 2 ^T añadiendo una nueva relación binaria al lenguaje y añadiendo axiomas que establezcan 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 T. Es posible iterar esta construcción de forma transfinita : dado un ordinal α, definir una nueva teoría añadiendo una relación de equivalencia E _β para cada β<α, junto con axiomas que establezcan que siempre que β<γ entonces cada clase de equivalencia E _γ es la unión de infinitas clases de equivalencia E _β , y cada clase de equivalencia E ₀ es un modelo de T. De manera informal, se pueden visualizar modelos de esta teoría como árboles de ramificación infinita de altura α con modelos de T asociados a todas las hojas.

Pedidos

La firma de órdenes no tiene constantes ni funciones, y una relación binaria simboliza ≤. (Por supuesto, es posible utilizar ≥, < 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 de y ≤ x , x ≤ y ∧¬ y ≤ x , y < x ,

Algunas propiedades de primer orden de los órdenes:

• Transitiva : ∀ 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 ("Entre dos elementos distintos hay otro elemento"): ∀ x ∀ z ( x < z) → ∃ y ( x < y) ∧ ( y < z)
• Hay un elemento más pequeño: ∃ x ∀ y ( x ≤ y)
• Hay un elemento más grande: ∃ x ∀ y ( y ≤ x)
• Cada 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. Existen otras tres teorías muy similares: la teoría de órdenes lineales densos con:

• 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 sobre todos los subconjuntos .

Celosías

Las redes pueden considerarse como tipos especiales de conjuntos parcialmente ordenados, con una firma que consiste en un símbolo de relación binaria ≤, o como estructuras algebraicas con una firma que consiste en dos operaciones binarias ∧ y ∨. Los dos enfoques pueden relacionarse definiendo a ≤ b como a ∧ b = a .

Para dos operaciones binarias los axiomas para una red son:

Para una relación ≤ los axiomas son:

• Axiomas que establecen ≤ es un orden parcial, como el anterior.
• ${\displaystyle \forall a\forall b\exists c\;c\leq a\wedge c\leq b\wedge \forall d\;d\leq a\wedge d\leq b\rightarrow d\leq c}$(existencia de c = a∧b)
• ${\displaystyle \forall a\forall b\exists c\;a\leq c\wedge b\leq c\wedge \forall d\;a\leq d\wedge b\leq d\rightarrow c\leq d}$(existencia de c = a∨b)

Las propiedades de primer orden incluyen:

• ${\displaystyle \forall x\forall y\forall z\;x\vee (y\wedge z)=(x\vee y)\wedge (x\vee z)}$( redes distributivas )
• ${\displaystyle \forall x\forall y\forall z\;x\vee (y\wedge (x\vee z))=(x\vee y)\wedge (x\vee z)}$( celosías modulares )

Las álgebras de Heyting pueden definirse como redes con ciertas propiedades adicionales de primer orden.

La completitud no es una propiedad de primer orden de las redes.

Gráficos

La firma de los gráficos no tiene constantes ni funciones, y un símbolo de relación binaria R , donde R ( x , y ) se lee como "hay una arista de x a y ".

Los axiomas para la teoría de grafos son

• Simétrica : ∀ x ∀ y R ( x , y )→ R ( y , x )
• Antirreflexivo : ∀ x ¬ R ( x , x ) ("sin bucles ")

La teoría de grafos aleatorios 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 fijo , es fácil escribir esta afirmación en el lenguaje de los grafos).

La teoría de grafos aleatorios es categórica, completa y decidible, y su modelo contable se denomina grafo de Rado . Un enunciado en el lenguaje de los grafos es verdadero en esta teoría si y solo si la probabilidad de que un grafo aleatorio de n vértices modele el enunciado tiende a 1 en el límite cuando n tiende a infinito.

Álgebras de Boole

Existen varias firmas y convenciones diferentes que se utilizan para las álgebras de Boole :

1. La signatura 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 siguiente 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 para un álgebra de Boole son entonces solo los axiomas para un anillo con 1 más ∀ x x ² = x . Desafortunadamente, esto choca con la convención estándar en la teoría de conjuntos dada anteriormente.

Los axiomas son:

• Los axiomas para una red distributiva (ver arriba)
• ∀a a ∧¬ a = 0, ∀a a ∨¬ a = 1 (propiedades de la negación)
• Algunos autores añaden 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 atom( x ) como abreviatura de ¬ x = 0 ∧ ∀ y y ≤ x → y = 0 ∨ y = x , que se lee como " x es un átomo", en otras palabras, un elemento distinto de cero sin nada entre él y 0. Estas son algunas propiedades de primer orden de las álgebras de Boole:

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

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

Para cualquier álgebra de Boole B , hay varios invariantes definidos de la siguiente manera.

• El ideal I ( B ) consiste en elementos que son la suma de un elemento atómico y un elemento no atómico (un elemento sin átomos debajo de él).
• Las álgebras cocientes B ⁱ de B se definen inductivamente por B ⁰ = B , B ^{k +1} = B ^k / I ( B ^k ).
• El invariante m ( B ) es el entero más pequeño tal que B ^{m +1} es trivial, o ∞ si no existe tal 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 sólo si sus invariantes l , m y n son iguales. En otras palabras, los valores de estos invariantes clasifican las posibles compleciones de la teoría de las álgebras de Boole. Por lo tanto, las posibles teorías completas son:

• El álgebra trivial (si está permitido; a veces se incluye 0≠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 aridad 1 (la inversa) cuyo valor en t se denota por t ⁻¹ , y una función de aridad 2, que suele omitirse de los términos. Para cualquier entero n , t ⁿ es una abreviatura del término obvio para la n ésima potencia de t .

Los grupos se definen por los axiomas

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

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

• Abeliano : ∀ x ∀ y xy = yx .
• Libre de torsión : ∀ x x ² = 1→ x = 1, ∀ x x ³ = 1 → x = 1, ∀ x x ⁴ = 1 → x = 1, ...
• Divisible : ∀ x ∃ y y ² = x , ∀ x ∃ y y ³ = x , ∀ x ∃ y y ⁴ = x , ...
• Infinito (como en la teoría de la identidad)
• Exponente n (para cualquier entero positivo fijo n ): ∀ x x ⁿ = 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 grupos abelianos es decidible. ^[2] La teoría de grupos abelianos infinitos divisibles y libres de torsión es completa, al igual que la teoría de grupos abelianos infinitos de exponente p (para p primo ).

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

Las propiedades de ser finito, o libre , o simple , o 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 los 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 por izquierda y 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 dados aquí tienen solo 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 inversa es nuevamente un grupo. Dado que la firma de los cuerpos no suele incluir inversas multiplicativas y aditivas, los axiomas para inversas no son universales y, por lo tanto, una subestructura de un cuerpo cerrado bajo adición y multiplicación no siempre es un cuerpo. Esto se puede remediar agregando funciones inversas unarias al lenguaje.

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

• ∀ a ₁ ∀ a ₂ ... ∀ a _n ∃ x (...(( x + a ₁ ) x + a ₂ ) x +...) x + a _n = 0

Campos perfectos

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

Campos algebraicamente cerrados de característica p

Los axiomas para cuerpos, más para cada n positivo 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órica en todos los cardinales incontables. La teoría ACF _p tiene una propiedad de dominio universal , en el sentido de que toda estructura N que satisface los axiomas universales de ACF _p es una subestructura de un cuerpo algebraicamente cerrado suficientemente grande , y además cualesquiera dos de tales incrustaciones N → M inducen un automorfismo de M . ${\displaystyle M\models ACF_{0}}$

Campos finitos

La teoría de cuerpos finitos es el conjunto de todos los enunciados de primer orden que son verdaderos en todos los cuerpos finitos. Se pueden dar ejemplos significativos de tales enunciados, por ejemplo, aplicando el teorema de Chevalley-Warning a los cuerpos 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 para campos más, para cada entero positivo n , el axioma:

• ∀ a ₁ ∀ a ₂ ... ∀ a _n a ₁ a ₁ + a ₂ a ₂ + ...+ a _n a _n =0 → a ₁ =0∧ a ₂ =0∧ ... ∧ a _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 cuerpos cerrados reales es efectiva y completa y, por lo tanto, decidible ( teorema de Tarski-Seidenberg ). La adición de otros 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 campos p -ádicos es decidible y dieron un conjunto de axiomas para ella. ^[3]

Geometría

Los axiomas de los distintos sistemas de geometría suelen utilizar un lenguaje tipificado, en el que los distintos tipos corresponden a distintos objetos geométricos, como puntos, líneas, círculos, planos, etc. La signatura suele consistir en relaciones de incidencia binarias entre objetos de distintos tipos; por ejemplo, la relación de que un punto se encuentra sobre una línea. La signatura puede tener relaciones más complicadas; por ejemplo, la geometría ordenada puede tener una relación de "intermediación" ternaria para 3 puntos, que indica si uno se encuentra entre otros dos, o una relación de "congruencia" entre 2 pares de puntos.

Algunos ejemplos de sistemas axiomatizados de geometría incluyen la geometría ordenada , la geometría absoluta , la geometría afín , la geometría euclidiana , la geometría proyectiva y la geometría hiperbólica . Para cada una de estas geometrías existen muchos sistemas de axiomas diferentes y no equivalentes 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 para la geometría proyectiva utilizan dos 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 mayúsculas y minúsculas, y un incidente a A se escribe como aA , entonces un conjunto de axiomas es

• ${\displaystyle \forall a\forall b\;\lnot a=b\rightarrow \exists C\;aC\land bC}$(Hay una línea que pasa por dos puntos distintos a , b ...)
• ${\displaystyle \forall a\forall b\forall C\forall D\;\lnot a=b\land aC\land bC\land aD\land bD\rightarrow C=D}$(...lo cual es único)
• ${\displaystyle \forall a\forall b\forall c\forall d\forall e\forall G\forall H\;aH\land bH\land eH\land cG\land dG\land eG\rightarrow \exists f\exists I\exists J\;aI\land cI\land fI\land bJ\land dJ\land fJ}$(Axioma de Veblen: si ab y cd se encuentran en líneas que se intersectan, entonces también lo están ac y bd ).
• ${\displaystyle \forall A\exists b\exists c\exists d\;bA\land cA\land dA\land \lnot b=c\land \lnot b=d\land \lnot c=d}$(Cada línea tiene al menos 3 puntos)

Euclides no enunció todos los axiomas de la geometría euclidiana de forma explícita, y la primera lista completa la dio Hilbert 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 cuerpos reales cerrados.

Álgebra diferencial

• La teoría DF de campos diferenciales .

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

${\displaystyle \forall u\forall v\,\partial (uv)=u\,\partial v+v\,\partial u}$

${\displaystyle \forall u\forall v\,\partial (u+v)=\partial u+\partial v\ .}$

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 a continuación).

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 se tiene el axioma: ${\displaystyle k=\{u\in K:\partial (u)=0\}.}$

${\displaystyle \forall u\,\partial (u)=0\land p1=0\rightarrow \exists v\,v^{p}=u}$

(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 que el campo constante sea perfecto añadiendo un nuevo símbolo r a la firma con los axiomas.

${\displaystyle \forall u\,\partial (u)=0\land p1=0\rightarrow r(u)^{p}=u}$

${\displaystyle \forall u\,\lnot \partial (u)=0\rightarrow r(u)=0.}$

• La teoría de campos diferencialmente cerrados (DCF) es la teoría de campos diferencialmente perfectos con axiomas que dicen que si f y g son polinomios diferenciales y el separante de f es distinto de cero y g ≠0 y f tiene un orden mayor que el de g , entonces hay alguna x en el campo con f ( x )=0 y g ( x )≠0.

Suma

La teoría de los números naturales con función sucesora tiene como firma 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 sucesora 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 adición, con signatura formada por una constante 0, una función unaria S y una función binaria +. Es completa 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 a teorías consistentes recursivamente enumerables completas. Esto ya no es cierto para la mayoría de las teorías siguientes; 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í mismas, lo que implica que se aplica el teorema de incompletitud de Gödel y 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:

• La constante 0;
• La función unaria , la función sucesora , aquí se denota con el prefijo S , o con el prefijo σ o el sufijo ′ en otros lugares;
• Dos funciones binarias , denotadas por los infijos + y ×, llamadas "suma" y "multiplicación".

Algunos autores toman la firma como si contuviera una constante 1 en lugar de la función S y luego definen S de la manera obvia como St = 1 + t .

Aritmética de Robinson (también llamada Q ). Los axiomas (1) y (2) rigen 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 la adición; (6) y (7) hacen lo mismo para la multiplicación. La aritmética de Robinson puede considerarse como la 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 aritmética de Peano de primer orden con inducción restringida a fórmulas Σ n (para n = 0, 1, 2, ...). La teoría IΣ ₀ se denota a menudo por IΔ ₀ . Se trata de una serie de fragmentos cada vez más potentes 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 funciones exponenciales (EFA) es IΣ ₀ 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 mencionados anteriormente, junto con el esquema axiomático de inducción:

• ${\displaystyle \phi (0)\wedge (\forall x\phi (x)\rightarrow \phi (Sx))\rightarrow (\forall x\phi (x))}$para cualquier fórmula φ en el lenguaje de PA . φ puede contener variables libres distintas de x .

El artículo de Kurt Gödel de 1931 demostró que PA es incompleto y no tiene terminaciones enumerables recursivamente consistentes.

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

En el caso de 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 cuando se agregan 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 que varían sobre números enteros y subconjuntos de los números 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 es incompleta). La firma será típicamente la firma 0, S , +, × de la aritmética, junto con una relación de pertenencia ∈ entre números enteros y subconjuntos (aunque hay numerosas variaciones menores). Los axiomas son los de la aritmética de Robinson , junto con los esquemas axiomáticos de inducción y comprensión .

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

• ${\displaystyle {\mathsf {RCA}}_{0}}$Comprensión recursiva
• ${\displaystyle {\mathsf {WKL}}_{0}}$, Lema de König débil
• ${\displaystyle {\mathsf {ACA}}_{0}}$Comprensión aritmética
• ${\displaystyle {\mathsf {ATR}}_{0}}$Recursión transfinita aritmética
• ${\displaystyle \Pi _{1}^{1}{\mbox{-}}{\mathsf {CA}}_{0}}$, comprensión ${\displaystyle \Pi _{1}^{1}}$

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

Teorías de conjuntos

La característica habitual de la teoría de conjuntos tiene una relación binaria ∈, ninguna constante ni ninguna función. Algunas de las teorías que se describen a continuación 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 la lógica de primer orden con dos tipos.
2. Utilice la lógica de primer orden ordinaria, 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:

• Teorías débiles que carecen de conjuntos de potencias :
  • S' (Tarski, Mostowski y Robinson, 1953); (finitamente axiomatizable)
  • Teoría de conjuntos de Kripke-Platek ; KP;
  • Teoría de conjuntos de bolsillo
  • Teoría general de conjuntos , GST
  • Teoría de conjuntos constructivos , CZF
• Teoría de conjuntos de Mac Lane y teoría de topos elementales
• Teoría de conjuntos de Zermelo ; Z
• Teoría de conjuntos de Zermelo-Fraenkel ; ZF, ZFC;
• Teoría de conjuntos de von Neumann–Bernays–Gödel ; NBG; (finitamente axiomatizable)
• Teoría de conjuntos de Ackermann ;
• Teoría de conjuntos de Scott-Potter
• Nuevas Fundaciones ; NF (finitamente axiomatizable)
• Teoría de conjuntos positivos
• Teoría de conjuntos de Morse-Kelley ; MK;
• Teoría de conjuntos de Tarski-Grothendieck ; TG;

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

• axioma de elección , axioma de elección dependiente
• Hipótesis del continuo generalizado
• Axioma de Martin (generalmente junto con la negación de la hipótesis del continuo), máxima de Martin
• ◊ y ♣
• Axioma de constructibilidad (V=L)
• axioma de fuerza adecuada
• determinación analítica, determinación proyectiva , axioma de determinación
• Muchos axiomas cardinales grandes

Véase también

• Portal de matemáticas

• Glosario de áreas de las matemáticas
• Lista de teorías matemáticas

Referencias

1. Goldrei, Derek (2005), Cálculo proposicional y de predicados: un modelo de argumento: Un modelo de argumento, Springer, pág. 265, ISBN 9781846282294.
2. Szmielew, W. (1955), "Propiedades elementales de los grupos abelianos", Fundamenta Mathematicae , 41 (2): 203–271, doi : 10.4064/fm-41-2-203-271 , MR  0072131.
3. Ax, James ; Kochen, Simon (1965), "Problemas diofánticos sobre cuerpos locales. II. Un conjunto completo de axiomas para la teoría de números p-ádicos.", Amer. J. Math. , 87 (3), The Johns Hopkins University Press: 631–648, doi :10.2307/2373066, JSTOR  2373066, MR  0184931

Lectura adicional

• Chang, CC; Keisler, H. Jerome (1989), Teoría de modelos (3.ª ed.), Elsevier , ISBN 0-7204-0692-7
• Hodges, Wilfrid (1997), Una teoría de modelos más breve , Cambridge University Press , ISBN 0-521-58713-1
• Marker, David (2002), Teoría de modelos: una introducción , Textos de posgrado en matemáticas , vol. 217, Springer, ISBN 0-387-98760-6