Conjunto definible - Definable set

En lógica matemática , un conjunto definible es una relación n -aria en el dominio de una estructura cuyos elementos son precisamente aquellos elementos que satisfacen alguna fórmula en el lenguaje de primer orden de esa estructura. Un conjunto se puede definir con o sin parámetros , que son elementos del dominio a los que se puede hacer referencia en la fórmula que define la relación.

Definición

Sea un lenguaje de primer orden, una estructura con dominio , un subconjunto fijo de y un número natural . Entonces:

  • Un conjunto es definible en con los parámetros de si y sólo si existe una fórmula y los elementos de tal manera que para todos ,
si y solo si
La notación entre corchetes aquí indica la evaluación semántica de las variables libres en la fórmula.
  • Un conjunto se puede definir sin parámetros si se puede definir con parámetros del conjunto vacío (es decir, sin parámetros en la fórmula de definición).
  • Una función se puede definir en (con parámetros) si su gráfico se puede definir (con esos parámetros) en .
  • Un elemento se puede definir en (con parámetros) si el conjunto singleton se puede definir en (con esos parámetros).

Ejemplos de

Los números naturales con solo la relación de orden

Sea la estructura formada por los números naturales con el orden habitual. Entonces, cada número natural se puede definir sin parámetros. El número se define mediante la fórmula que indica que no existen elementos menores que x : y un número natural se define mediante la fórmula que indica que existen exactamente elementos menores que x :

Por el contrario, no se puede definir ningún entero específico sin parámetros en la estructura que consta de los números enteros con el orden habitual (ver la sección sobre automorfismos a continuación).

Los números naturales con sus operaciones aritméticas.

Sea la estructura de primer orden que consta de los números naturales y sus operaciones aritméticas habituales y relación de orden. Los conjuntos definibles en esta estructura se conocen como conjuntos aritméticos y se clasifican en la jerarquía aritmética . Si la estructura se considera en lógica de segundo orden en lugar de lógica de primer orden, los conjuntos definibles de números naturales en la estructura resultante se clasifican en la jerarquía analítica . Estas jerarquías revelan muchas relaciones entre la definibilidad en esta estructura y la teoría de la computabilidad , y también son de interés en la teoría descriptiva de conjuntos .

El campo de los números reales

Sea la estructura que consta del campo de números reales . Aunque la relación de ordenación habitual no se incluye directamente en la estructura, existe una fórmula que define el conjunto de reales no negativos, ya que estos son los únicos reales que poseen raíces cuadradas:

Por lo tanto, any es no negativo si y solo si . Junto con una fórmula que define el inverso aditivo de un número real en , se puede usar para definir el orden habitual en : para , establecer si y solo si no es negativo. La estructura ampliada s se denomina extensión definitoria de la estructura original. Tiene el mismo poder expresivo que la estructura original, en el sentido de que un conjunto es definible sobre la estructura ampliada a partir de un conjunto de parámetros si y solo si es definible sobre la estructura original a partir de ese mismo conjunto de parámetros.

La teoría de tiene cuantificador eliminación . Por tanto, los conjuntos definibles son combinaciones booleanas de soluciones de igualdades y desigualdades polinómicas; estos se denominan conjuntos semi-algebraicos . Generalizar esta propiedad de la línea real conduce al estudio de la o-minimidad .

Invarianza bajo automorfismos

Un resultado importante de los conjuntos definibles es que se conservan bajo automorfismos .

Vamos a ser un -estructura con el dominio , y definible en con los parámetros de . Sea un automorfismo del que está la identidad . A continuación, para todos ,
si y solo si

Este resultado a veces se puede utilizar para clasificar los subconjuntos definibles de una estructura determinada. Por ejemplo, en el caso anterior, cualquier traducción de es un automorfismo que conserva el conjunto vacío de parámetros y, por lo tanto, es imposible definir un entero en particular en esta estructura sin parámetros en . De hecho, dado que dos enteros cualesquiera se transmiten entre sí mediante una traducción y su inverso, los únicos conjuntos de enteros definibles sin parámetros son el conjunto vacío y él mismo. En contraste, hay infinitos conjuntos de pares definibles (o incluso n -tuplas para cualquier n > 1 fijo ) de elementos de , ya que cualquier automorfismo (traslación) preserva la "distancia" entre dos elementos.

Resultados adicionales

La prueba de Tarski-Vaught se utiliza para caracterizar las subestructuras elementales de una estructura dada.

Referencias

  • Hinman, Peter. Fundamentos de lógica matemática , AK Peters, 2005.
  • Marcador, David. Teoría de modelos: una introducción , Springer, 2002.
  • Rudin, Walter. Principios del análisis matemático , 3er. ed. McGraw-Hill, 1976.
  • Slaman, Theodore A. y W. Hugh Woodin. Lógica matemática: el curso de pregrado de Berkeley . Primavera de 2006.