Conjunto definible

En lógica matemática , un conjunto definible es una relación n -aria en el dominio de una estructura cuyos elementos satisfacen alguna fórmula en el lenguaje de primer orden de esa estructura. Un conjunto puede definirse 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: ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle M}$ ${\displaystyle X}$ ${\displaystyle M}$ ${\displaystyle m}$

• Un conjunto es definible con parámetros de si y sólo si existe una fórmula y elementos tales que para todo , ${\displaystyle A\subseteq M^{m}}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle X}$ ${\displaystyle \varphi [x_{1},\ldots ,x_{m},y_{1},\ldots ,y_{n}]}$ ${\displaystyle b_{1},\ldots ,b_{n}\in X}$ ${\displaystyle a_{1},\ldots ,a_{m}\in M}$

${\displaystyle (a_{1},\ldots ,a_{m})\in A}$Si y sólo si ${\displaystyle {\mathcal {M}}\models \varphi [a_{1},\ldots ,a_{m},b_{1},\ldots ,b_{n}].}$

La notación entre corchetes aquí indica la evaluación semántica de las variables libres en la fórmula.

• Un conjunto es definible sin parámetros si es definible con parámetros del conjunto vacío (es decir, sin parámetros en la fórmula de definición). ${\displaystyle A}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {M}}}$
• Una función es definible en (con parámetros) si su gráfico es definible (con esos parámetros) en . ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {M}}}$
• Un elemento es definible en (con parámetros) si el conjunto singleton es definible en (con esos parámetros). ${\displaystyle a}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle \{a\}}$ ${\displaystyle {\mathcal {M}}}$

Ejemplos

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

Sea la estructura que consta de los números naturales con el orden habitual ^{[ se necesita aclaración ]} . Entonces, todo número natural es definible sin parámetros. El número se define mediante la fórmula que establece que no existen elementos menores que x : ${\displaystyle {\mathcal {N}}=(\mathbb {N} ,<)}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle 0}$ ${\displaystyle \varphi (x)}$

${\displaystyle \varphi =\neg \exists y(y<x),}$

y un número natural se define mediante la fórmula que establece que existen exactamente elementos menores que x : ${\displaystyle n>0}$ ${\displaystyle \varphi (x)}$ ${\displaystyle n}$

${\displaystyle \varphi =\exists x_{0}\cdots \exists x_{n-1}(x_{0}<x_{1}\land \cdots \land x_{n-1}<x\land \forall y(y<x\rightarrow (y\equiv x_{0}\lor \cdots \lor y\equiv x_{n-1})))}$

Por el contrario, no se puede definir ningún entero específico sin parámetros en la estructura que consiste en los enteros con el orden habitual (véase la sección sobre automorfismos a continuación). ${\displaystyle {\mathcal {Z}}=(\mathbb {Z} ,<)}$

Los números naturales con sus operaciones aritméticas

Sea la estructura de primer orden que consiste en 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 . ${\displaystyle {\mathcal {N}}=(\mathbb {N} ,+,\cdot ,<)}$

El campo de los números reales

Sea la estructura que consiste en el cuerpo de los números reales ^{[ aclaración necesaria ]} . Aunque la relación de ordenación habitual no está incluida directamente en la estructura, existe una fórmula que define el conjunto de los reales no negativos, ya que estos son los únicos reales que poseen raíces cuadradas: ${\displaystyle {\mathcal {R}}=(\mathbb {R} ,0,1,+,\cdot )}$

${\displaystyle \varphi =\exists y(y\cdot y\equiv x).}$

Por lo tanto, cualquier 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 utilizar para definir el ordenamiento habitual en : para , establece si y solo si es no negativo. La estructura ampliada se denomina extensión definicional 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. ${\displaystyle a\in \mathbb {R} }$ ${\displaystyle {\mathcal {R}}\models \varphi [a]}$ ${\displaystyle {\mathcal {R}}}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {R}}}$ ${\displaystyle a,b\in \mathbb {R} }$ ${\displaystyle a\leq b}$ ${\displaystyle b-a}$ ${\displaystyle {\mathcal {R}}^{\leq }=(\mathbb {R} ,0,1,+,\cdot ,\leq )}$

La teoría de la eliminación de cuantificadores tiene como consecuencia que los conjuntos definibles sean combinaciones booleanas de soluciones de igualdades y desigualdades polinómicas; estos se denominan conjuntos semialgebraicos . La generalización de esta propiedad de la línea real conduce al estudio de la o-minimalidad . ${\displaystyle {\mathcal {R}}^{\leq }}$

Invariancia bajo automorfismos

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

Sea una -estructura con dominio , , y definible en con parámetros de . Sea un automorfismo de que es la identidad en . Entonces, para todos los , ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle M}$ ${\displaystyle X\subseteq M}$ ${\displaystyle A\subseteq M^{m}}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle X}$ ${\displaystyle \pi :M\to M}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle X}$ ${\displaystyle a_{1},\ldots ,a_{m}\in M}$

${\displaystyle (a_{1},\ldots ,a_{m})\in A}$Si y sólo si ${\displaystyle (\pi (a_{1}),\ldots ,\pi (a_{m}))\in A.}$

Este resultado puede usarse a veces para clasificar los subconjuntos definibles de una estructura dada. Por ejemplo, en el caso de arriba, cualquier traducción de es un automorfismo que preserva el conjunto vacío de parámetros y, por lo tanto, es imposible definir cualquier entero particular en esta estructura sin parámetros en . De hecho, dado que dos enteros cualesquiera se trasladan entre sí mediante una traducción y su inverso, los únicos conjuntos de enteros definibles en sin parámetros son el conjunto vacío y él mismo. En contraste, hay infinitos conjuntos definibles de pares (o de hecho n -tuplas para cualquier n fijo > 1) de elementos de : (en el caso n = 2) combinaciones booleanas de los conjuntos para . En particular, cualquier automorfismo (traducción) preserva la "distancia" entre dos elementos. ${\displaystyle {\mathcal {Z}}=(\mathbb {Z} ,<)}$ ${\displaystyle {\mathcal {Z}}}$ ${\displaystyle {\mathcal {Z}}}$ ${\displaystyle {\mathcal {Z}}}$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle {\mathcal {Z}}}$ ${\displaystyle \{(a,b)\mid a-b=m\}}$ ${\displaystyle m\in \mathbb {Z} }$

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.
• Marker, David. Teoría de modelos: una introducción , Springer, 2002.
• Rudin, Walter . Principios de análisis matemático , 3.ª ed. McGraw-Hill, 1976.
• Slaman, Theodore A. y Woodin, W. Hugh . Lógica matemática: el curso de pregrado de Berkeley . Primavera de 2006.