En lógica de primer orden , una teoría de primer orden está 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.
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 de primer orden único L σ que puede usarse para capturar los hechos expresables de primer orden sobre la estructura σ.
Hay dos formas comunes de especificar teorías:
Una teoría L σ puede:
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 pura de la identidad es la de ser infinito. 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:
Estos axiomas definen la teoría de un conjunto infinito .
La propiedad opuesta de ser finito no puede afirmarse 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 la 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 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 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 no negativos números enteros. (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 de esto es la teoría inconsistente definida por el axioma ∃ x ¬ x = x . Es una teoría perfectamente buena con muchas propiedades buenas: 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 idioma determinado) 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.
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 que es superestable pero no totalmente trascendental .
La firma de las relaciones de equivalencia tiene un símbolo de relación infija binaria ~, sin constantes ni funciones. Las relaciones de equivalencia satisfacen los axiomas:
Algunas propiedades de primer orden de las relaciones de equivalencia son:
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 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 ni interesantes, pero a menudo dan ejemplos o contraejemplos sencillos para diversas afirmaciones.
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, 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 agregando una nueva relación binaria al lenguaje y agregando axiomas que establezcan que es una relación de equivalencia, de modo que haya un número infinito de clases de equivalencia, todas las cuales son modelos de T . Es posible iterar esta construcción infinitamente : dado un ordinal α, definir una nueva teoría agregando 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 0 es un modelo de T . De manera informal, uno puede visualizar los modelos de esta teoría como árboles infinitamente ramificados de altura α con modelos de T unidos a todas las hojas.
La firma de órdenes no tiene constantes ni funciones, y un símbolo de relación binaria ≤. (Por supuesto, es posible utilizar ≥, < o > como 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 pedidos:
La teoría DLO 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 ningún cardinal incontable. Hay otras tres teorías muy similares: la teoría de los órdenes lineales densos con a:
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 .
Las redes pueden considerarse 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 pueden relacionarse definiendo a ≤ b como a ∧ b = a .
Para dos operaciones binarias, los axiomas de una red son:
Para una relación ≤ los axiomas son:
Las propiedades de primer orden incluyen:
Las álgebras de Heyting se pueden definir como redes con ciertas propiedades adicionales de primer orden.
La integridad no es una propiedad de primer orden de las redes.
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 un borde de x a y ".
Los axiomas de la teoría de grafos son
La teoría de gráficos aleatorios tiene los siguientes axiomas adicionales para cada entero positivo n :
La teoría de los grafos aleatorios es ω categórica, completa y decidible, y su modelo contable se llama gráfico de Rado . Una afirmación en el lenguaje de las gráficas es verdadera en esta teoría si y sólo si la probabilidad de que un gráfico aleatorio de n vértices modele la afirmación tienda a 1 en el límite cuando n tiende al infinito.
Hay varias firmas y convenciones diferentes que se utilizan para las álgebras booleanas :
Los axiomas son:
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. A continuación se muestran algunas propiedades de primer orden de las álgebras booleanas:
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.
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 estas invariantes clasifican las posibles completaciones de la teoría de las álgebras de Boole. Entonces las posibles teorías completas son:
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 −1 , y una función de aridad 2, que generalmente se omite en los términos. Para cualquier número entero n , t n es una abreviatura del término obvio para la enésima potencia de t .
Los grupos están definidos por los axiomas.
Algunas propiedades de los grupos que se pueden definir en el lenguaje de grupos de primer orden son:
La teoría de los grupos abelianos es decidible. [2] La teoría de infinitos grupos abelianos divisibles libres de 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 afirmaciones 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 completamente trivial encontrar una afirmación 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.
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 identidad 1, y la multiplicación es distributiva hacia la izquierda y hacia la derecha.
Los axiomas para anillos más ∀ x ∀ y xy = yx .
Los axiomas para anillos conmutativos más ∀ x (¬ x = 0 → ∃ y xy = 1) y ¬ 1 = 0. Muchos de los ejemplos dados aquí sólo tienen axiomas universales o algebraicos . La clase de estructuras que satisfacen tal teoría tiene la propiedad de estar cerradas 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 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 campo cerrada bajo suma y multiplicación no siempre es un campo. 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 raíz se puede expresar mediante una única oración de primer orden:
Los axiomas para campos, más los axiomas para cada número primo p , establecen que si p 1 = 0 (es decir, el campo tiene la 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 raíz, más los axiomas que fijan la característica. Los ejemplos clásicos de teorías completas. Categórico en todos los cardenales incontables. La teoría ACF p tiene una propiedad de dominio universal , en el sentido de que cada estructura N que satisface los axiomas universales de ACF p es una subestructura de un campo algebraicamente cerrado suficientemente grande y, además , dos incrustaciones cualesquiera N → M inducen un automorfismo de M.
La teoría de campos finitos es el conjunto de todas las afirmaciones de primer orden que son verdaderas 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.
Los axiomas para campos más, para cada entero positivo n , el axioma:
Es decir, 0 no es una suma de cuadrados no trivial.
Los axiomas para campos formalmente reales más los axiomas:
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 (p. ej., 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 dieron un conjunto de axiomas para ella. [3]
Los axiomas para varios sistemas de geometría suelen utilizar un lenguaje mecanografiado, y los diferentes tipos corresponden 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 de que un punto se encuentra en una línea. La firma puede tener relaciones más complicadas; 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 de axiomas 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, 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
Euclides no estableció explícitamente todos los axiomas de la geometría euclidiana, y Hilbert dio la primera lista completa en 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 campos cerrados reales.
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; es decir, 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 de cuantificadores , a veces es más conveniente forzar el campo constante ser perfecto agregando un nuevo símbolo r a la firma con los axiomas
La teoría de los números naturales con función sucesora tiene una firma que consiste en una constante 0 y una función unaria S ("sucesora": S ( x ) se interpreta como x +1), y tiene axiomas:
El último axioma (inducción) puede ser reemplazado por los axiomas.
La teoría de los números naturales con una función sucesora es completa y decidible, y es κ-categórica para κ incontable pero no para κ contable.
La aritmética de Presburger es la teoría de los números naturales bajo suma, con firma que consiste en una constante 0, una función unaria S y una función binaria +. Es completo y decidible. Los axiomas son
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 poder para codificarse a sí mismos, 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:
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) 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 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 para la cual se cumple el teorema de incompletitud de Gödel . Axiomas:
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Σ 0 a menudo se denota por IΔ 0 . 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Σ 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 anteriores, junto con el esquema de axiomas de inducción:
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 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, no se aplica el teorema de incompletitud de Gödel . Surgen complicaciones al agregar más símbolos de función (p. ej., exponenciación).
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 está incompleta). La firma normalmente será la firma 0, S , +, × de 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
Estos se definen en detalle en los artículos sobre aritmética de segundo orden y matemáticas inversas .
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 lógica de primer orden:
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:
