Anexo:Teorías de primer orden

En lógica de primer orden, una teoría de primer orden está dada por un conjunto de axiomas en algún idioma. El presente artículo enumera algunos de los ejemplos más comunes utilizados en teoría de modelos, así como algunas de sus propiedades.

Introducción

Para cada estructura matemática natural existe una simbología σ enumerando las constantes, funciones y relaciones de la teoría junto con sus aridades, de modo que el objeto sea naturalmente una estructura σ. Dada una simbología σ existe un lenguaje de primer orden único L_σ que se puede utilizar para captar los hechos expresables de primer orden sobre la estructura γ.

Hay dos formas comunes de especificar teorías:

1. Enumerar o describir un conjunto de sentencias en el lenguaje L_σ, llamados axiomas de la teoría.
2. Proporcionar un conjunto de estructuras γ y definir 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 del lenguaje de campos que son verdaderas en todos los campos finitos.

Una teoría L_σ puede:

• Ser coherente: no existe prueba de contradicción.
• Ser satisfacible: existe una estructura γ para la que las oraciones de la teoría son todas verdaderas (según el teorema de completitud de Gödel, satisfacibilidad es equivalente a consistencia).
• Ser completo: cualquier asimbologíación, ya sea ella o su negación, es demostrable.
• Poseer eliminación de cuantificadores.
• Eliminar imaginarios.
• Ser finitamente axiomatizable;
• Ser decidible, es decir, existe un algoritmo para decidir qué asimbologíaciones son demostrables.
• Ser recursivamente axiomatizable.
• Ser un modelo completo o un submodelo completo.
• Ser κ categórico, es decir, todos los modelos de cardinalidad κ son isomorfos.
• Ser estable o inestable.
• Ser ω estable (equivalente a totalmente transcendental para las teorías numerables).
• Ser superestable
• Tener un modelo atómico.
• Tener un modelo primordial.
• Tener un modelo saturado.

Teorías de la identidad pura

La simbología 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 infinita. Esto viene dado 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 se puede establecer en lógica de primer orden para ninguna teoría que tenga modelos finitos arbitrariamente grandes: de hecho, cualquier teoría de este tipo tiene modelos infinitos según el teorema de compacidad. En general, si una propiedad puede expresarse mediante un número finito de oraciones de lógica de primer orden, entonces la propiedad opuesta también puede expresarse en lógica de primer orden, pero si una propiedad necesita un número infinito de oraciones, entonces su propiedad opuesta no puede expresarse 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 N finito de los números naturales, donde σ(N) es la sentencia que indica 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 la teoría de todos los conjuntos de cardinalidad en N para algún subconjunto finito N de 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 enteros no negativos (no existen teorías cuyos modelos sean exactamente conjuntos de cardinalidad N si N es un subconjunto infinito de números 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 es la teoría inconsistente definida por el axioma ∃x ¬x = x. Es una teoría perfectamente coherente con muchas propiedades deseables: es completa, decidible y finitamente axiomatizable entre otras propiedades. 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 idioma determinado) 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 está completa, pero no tiene modelos atómicos. También es un ejemplo de una teoría que es superestable pero no totalmente trascendente.

Relaciones de equivalencia

La simbología de la relación de equivalencia se expresa mediante un signo de relación infija binaria ~, sin constantes ni funciones. Las relaciones de equivalencia satisfacen los axiomas:

• Reflexiva ∀x x~x;
• Simétrica ∀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 clase 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 sencillo de una teoría que es ω-categórica pero no categórica para cualquier cardinal más grande.

La relación de equivalencia ~ no debe confundirse con el símbolo 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 ni interesantes, pero a menudo dan ejemplos o contraejemplos sencillos para diversas sentencias.

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 lenguaje, se define una nueva teoría 2^T agregando una nueva relación binaria al lenguaje y agregando axiomas que indiquen que es una relación de equivalencia, tal que hay un número infinito de clases de equivalencia, siendo todas ellas modelos de T. Es posible iterar esta construcción transfinitamente: dado un ordinal α, se define una nueva teoría agregando una relación de equivalencia E_β para cada β<α, junto con axiomas que indiquen que siempre que β<γ entonces cada E_γ la clase de equivalencia es la unión de infinitas clases de equivalencia E_β, y cada clase de equivalencia E₀ es un modelo de T. Informalmente, se pueden visualizar los modelos de esta teoría como árboles infinitamente ramificados de altura α con modelos de T adheridos a todas las hojas.

Órdenes

La simbología de órdenes no tiene constantes ni funciones, y solo un símbolo de relación binaria ≤ (por supuesto, es posible utilizar ≥, < o > en su lugar como relación básica, con los cambios menores obvios en los axiomas). Se definen x ≥ y, x < y, x > y como abreviaturas de y ≤ x, x ≤ y ∧¬y ≤ x, y < X,

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

• 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 ("entre 2 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 OLD de órdenes lineales densos sin puntos finales (es decir, sin elemento más pequeño ni más grande) es completa, ω-categórica, pero no categórica para cualquier cardinal incontable. Hay otras tres teorías muy similares: la teoría de los órdenes lineales densos con un:

• 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.

Poseer un buen orden ("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".

Retículos

Los retículos se puede considerar como tipos especiales de conjuntos parcialmente ordenados, con una simbología que consta de un signo de relación binaria ≤, o como estructuras algebraicas con una simbología que consta de dos operaciones binarias ∧ y ∨. Los dos enfoques pueden relacionarse definiendo a ≤ b significa que a∧b = a.

Para dos operaciones binarias, los axiomas de un retículo son:

Leyes de conmutatividad:		$\forall a\forall b\;a\vee b=b\vee a$		$\forall a\forall b\;a\wedge b=b\wedge a$
Leyes de asociatividad:		$\forall a\forall b\forall c\;a\vee (b\vee c)=(a\vee b)\vee c$		$\forall a\forall b\forall c\;a\wedge (b\wedge c)=(a\wedge b)\wedge c$
Leyes de absorción:		$\forall a\forall b\;a\vee (a\wedge b)=a$		$\forall a\forall b\;a\wedge (a\vee b)=a$

Para una relación ≤ los axiomas son:

• Axiomas que indican que ≤ es un orden parcial, como se indica arriba.
• $\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)
• $\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:

• $\forall x\forall y\forall z\;x\vee (y\wedge z)=(x\vee y)\wedge (x\vee z)$ (retículo distributivo)
• $\forall x\forall y\forall z\;x\vee (y\wedge (x\vee z))=(x\vee y)\wedge (x\vee z)$ (retículo modular)

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

La completitud no es una propiedad de primer orden de los retículos.

Grafos

Lógica de grafos (editar | discusión | historial | enlaces | vigilar | registros | proteger | borrar)

La simbología de grafos no tiene constantes ni funciones, y solo un símbolo de relación binaria R, donde R(x,y) se lee como "existe un enlace desde x a y".

Los axiomas de la teoría de grafos son:

• Simétrico: ∀x ∀y R(x,y)→ R(y' ',X)
• Antireflexivo: ∀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 cualesquiera 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 sentencia en el lenguaje de grafos).

La teoría de los grafos aleatorios es ω categórica, completa y decidible, y su modelo numerable se llama 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 al infinito.

Álgebras de Boole

Hay varias simbologías y convenciones diferentes utilizadas para las álgebras de Boole:

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

Los axiomas son:

• Los axiomas para un retículo distributivo (véase 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.

Se escribe x ≤ y como abreviatura de x∧y = x, y átomo(x) como abreviatura de ¬x = 0 ∧ ∀y y ≤ x → y = 0 ∨ y = x, leído 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 átomos: ∀x ¬átomo(x)

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

Para cualquier álgebra booleana B, existen varios invariantes definidos de la siguiente manera:

• El ideal I(B) consta de elementos que son la suma de un elemento atómico y uno sin átomos (un elemento sin átomos debajo).
• Las álgebras de cociente 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 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 booleanas son elementalmente equivalentes si y solo si sus invariantes l, m y n son iguales. En otras palabras, los valores de estas invariantes clasifican las posibles completaciones de la teoría de las álgebras de Boole. En consecuencia, las posibles teorías completas son:

• El álgebra trivial (si esto está permitido; a veces 0≠1 se incluye 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 simbología 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 ser omitida de los términos. Para cualquier número entero n, tⁿ es una abreviatura del término obvio para la nésima potencia de t.

Los grupos están definidos por los axiomas:

• Identidad: ∀x 1x = x ∧ x1 = 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.
• Sin 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 los grupos abelianos es decidible.​ La teoría de infinitos grupos abelianos divisibles sin torsión está completa, al igual que la teoría de infinitos grupos abelianos de exponente p (para p primo).

La teoría de grupos finitos es el conjunto de expresiones de primer orden en el lenguaje de grupos que son verdaderas en todos los grupos finitos (hay muchos modelos infinitos de esta teoría). No es del todo trivial encontrar una expresió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, o libre, o 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 posee esta propiedad.

Anillos y cuerpos

La simbología de anillos (unitarios) 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 identidad 1, y la multiplicación es distributiva hacia la izquierda y hacia la derecha.

Anillos conmutativos

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

Cuerpos

Los axiomas para anillos conmutativos más ∀x (¬ x = 0 → ∃y xy = 1) y ¬ 1 = 0. Muchos de los ejemplos dados aquí solo tienen axiomas universales o algebraicos. Las clases de estructuras que satisfacen dicha teoría tiene la propiedad de estar cerrados 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 simbología de los campos generalmente no incluye el inverso multiplicativo y aditivo, los axiomas de los inversos no son universales y, por lo tanto, una subestructura de un cuerpo cerrado bajo suma y multiplicación no siempre es un cuerpo. Esto se puede solucionar añadiendo 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

Cuerpos perfectos

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

Cuerpos 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, y más los axiomas que fijan la característica. Los ejemplos clásicos de teorías completas. Categórico en todos los cardinales no numerables. La teoría de cuerpos algebraicamente cerrados CAC_p tiene una propiedad de dominio universal, en el sentido de que cada estructura N que satisface los axiomas universales de CAC_p es una subestructura de un campo algebraicamente cerrado suficientemente grande. $M\models CAC_{0}$ y, además, dos incrustaciones cualesquiera N → M induce un automorfismo de M.

Cuerpos finitos

La teoría de campos finitos es el conjunto de todas las declaraciones de primer orden que son verdaderas en todos los cuerpos finitos. Se pueden dar ejemplos significativos de tales declaraciones, por ejemplo, aplicando el teorema de Chevalley-Warning sobre 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.

Cuerpos formalmente reales

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

• ∀ a₁ ∀ a₂... ∀ a_n a₁a₁+a₂a₂+ . ..+a_na_n=0 → a₁=0∧a₂=0∧ ... ∧a_n=0.

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

Cuerpos reales cerrados

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 cuerpos cerrados reales es coherente y completa y, por lo tanto, decidible (según 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.

Cuerpos p-ádicos

Ax y Kochen (1965) demostraron que la teoría de los cuerpos p-ádicos es decidible y dio un conjunto de axiomas para ello.​

Geometría

Los axiomas para varios sistemas de geometría suelen utilizar un lenguaje categorizado, y los diferentes tipos corresponden a diferentes objetos geométricos como puntos, líneas, círculos, planos, etc. La simbología a menudo consistirá en relaciones de incidencia binarias entre objetos de diferentes tipos; como por ejemplo, la relación de que un punto se encuentra en una línea recta. La simbología puede tener relaciones más complicadas; como por ejemplo, la geometría ordenada podría tener una relación ternaria de "intermediación" 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 axiomáticos incluyen axiomas de "integridad" que no son de primer orden.

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

• $\forall a\forall b\;\lnot a=b\rightarrow \exists C\;aC\land bC$ (Hay una línea que atraviesa un y 2 puntos distintos a,b ...)
• $\forall a\forall b\forall C\forall D\;\lnot a=b\land aC\land bC\land aD\land bD\rightarrow C=D$ (... que es único)
• $\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 rectas que se cruzan, entonces también ac y bd)
• $\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 recta tiene al menos 3 puntos)

Euclides no estableció explícitamente todos los axiomas de la geometría euclidiana, y Hilbert dio la primera lista completa, conocida como los axiomas de Hilbert. Ésta 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, relacionándolo con la teoría completa y decidible de los cuerpos cerrados reales.

Álgebra diferencial

• La teoría CF de cuerpos diferenciales.

La simbología es la de los cuerpos (0, 1, +, −, ×) junto con una función unaria ∂, la derivación. Los axiomas son los de cuerpos junto con:

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

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

A esta teoría se le puede añadir la condición de que la característica sea p, prima o cero, para obtener la teoría CF_p de cuerpos diferenciales de característica p (y de manera similar con las otras teorías siguientes).

Si K es un cuerpo diferencial, entonces el cuerpo de constantes $k=\{u\in K:\partial (u)=0\}.$ La teoría de cuerpos diferencialmente perfectos es la teoría de cuerpos diferenciales junto con la condición de que el cuerpo de constantes sea perfecto; en otras palabras, para cada primo p se tiene el axioma siguiente:

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

(no tiene mucho sentido exigir que todo el cuerpo sea un cuerpo 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 de cuantificadores, a veces es más conveniente forzar que el cuerpo constante sea perfecto agregando un nuevo símbolo r a la simbología con los axiomas:

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

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

• La teoría de cuerpos diferencialmente cerrados (CDC) es la teoría de cuerpos diferencialmente perfectos con axiomas que dicen que si f y g son polinomios diferenciables y el separante de f es distinto de cero y g≠0 y f tiene un orden mayor que el de g, entonces hay algún x en el cuerpo con f(x)=0 y g(x)≠0.

Suma

La teoría de los números naturales con una función sucesor tiene una simbología que consiste en una constante 0 y una función unaria S ("sucesor": S(x) es interpretado como x+1), y tiene los axiomas siguientes:

1. ∀x &no; 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 &no; x = 0 → ∃y Sy = x

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

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

1. ∀x &no; Sx = 0
2. ∀x∀y Sx = Sy → x = y
3. ∀x x + 0 = x
4. ∀x∀y x + 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 se pueden ampliar para completar teorías consistentes enumerables de forma recursiva. Esto ya no es cierto para la mayoría de las siguientes teorías. Normalmente pueden codificar tanto la multiplicación como la suma de números naturales, y esto les da suficiente potencia para codificarse a sí mismos, lo que implica que se aplican los teoremas de incompletitud de Gödel y las teorías ya no pueden ser completas ni recursivamente enumerables (a menos que sean inconsistentes).

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

• La constante 0.
• La función unaria, la función sucesor, aquí indicado por el prefijo S, o por el prefijo σ o el sufijo ′ en algunos textos;
• Dos funciones binarias, indicados por los símbolos + y ×, llamados "suma" y "multiplicación".

Algunos autores consideran que la simbología contiene una constante 1 en lugar de la función S, y después definen S de manera obvia como St = 1 + t.

La aritmética de Robinson (también llamada Q). Los axiomas (1) y (2) gobiernan el elemento distinguido 0. (3) asegura que S es inyectiva. 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 puede considerarse como la aritmética de Peano sin inducción. Q es una teoría débil en la que se cumplem los teoremas de incompletitud de Gödel. Axiomas:

1. ∀x &no; Sx = 0
2. ∀x &no; x = 0 → ∃y Sy = x
3. ∀x∀y Sx = Sy → x = y
4. ∀x x + 0 = x
5. ∀x∀y x + Sy = S(x + y)
6. ∀x x × 0 = 0
7. ∀x∀y x × Sy = (x & veces; y) + x.

IΣ_n es aritmética de Peano de primer orden con inducción restringida a las fórmulas Σ_n (para n = 0, 1, 2, ...). La teoría Iσ₀ suele denotarse 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 (ARP). La aritmética de funciones exponenciales (AFE) es IΣ₀ con un axioma que establece que x^y existe para todo x e y (con las propiedades habituales).

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

• $\phi (0)\wedge (\forall x\phi (x)\rightarrow \phi (Sx))\rightarrow (\forall x\phi (x))$ para cualquier fórmula φ en el idioma de la AP. &fi; puede contener variables libres distintas de x.

El artículo de Kurt Gödel de 1931 demostró que la AP es incompleta 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 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, los Teoremas de incompletitud de Gödel y el teorema de Tarski-Seidenberg no son aplicables. Surgen complicaciones al agregar más símbolos de funciones (por ejemplo, la 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, que se consideran variables entre números enteros y subconjuntos de números enteros. También existe una teoría de la aritmética en 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 lógica de primer orden, que es incompleta. La simbología normalmente será la simbología 0, S, +, × de la aritmética, junto con una relación de pertenencia ∈ entre números 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 la 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 fuerza creciente, cinco de los sistemas más comunes son:

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

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

Teorías de conjuntos

La simbología 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 lógica de primer orden:

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

Algunas teorías de conjuntos de primer orden incluyen:

• Teorías débiles que carecen de conjunto potencia:
  • S' (Tarski, Mostowski y Robinson, 1953); (finitamente axiomatizable)
  • Teoría de conjuntos de Kripke-Platek; kp
  • Teoría de los conjuntos de bolsillo
  • Teoría general de conjuntos; IVA
  • Teoría de conjuntos constructivos; CZF
• Teoría de conjuntos de Mac Lane y topos
• Teoría de conjuntos de Zermelo; z*Axiomas 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
• Nuevos Fundamentos; 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 adicionales de primer orden que se pueden agregar a uno de estos (generalmente ZF) incluyen:

• Axioma de elección, axioma de elección dependiente
• Hipótesis del continuo
• Axioma de Martin (normalmente junto con la negación de la hipótesis del continuo), máximo de Martin
• ◊ y ♣
• Axioma de constructibilidad (V=L)
• Axioma de forzado propio
• Determinación analítica, determinación proyectiva, axioma de determinabilidad
• Varios grandes axiomas cardinales

Véase también

• Glosario de áreas de las matemáticas
• Anexo:Teorías matemáticas

Lectura adicionales

• Chang, C.C.; Keisler, H. Jerome (1989), Model Theory (3 edición), Elsevier, ISBN 0-7204-0692-7 .
• Hodges, Wilfrid (1997), A shorter model theory, Cambridge University Press, ISBN 0-521-58713-1 .
• Marker, David (2002), Model Theory: An Introduction, Graduate Texts in Mathematics 217, Springer, ISBN 0-387-98760-6 .

Enlaces externos

• Portal:Matemática. Contenido relacionado con Matemática.

• Datos: Q2908665