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 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: ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle M}$ ${\displaystyle X}$ ${\displaystyle M}$ ${\displaystyle m}$

• Un conjunto se puede definir con parámetros de si y solo si existe una fórmula y elementos tales que para todos , ${\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 solo 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 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). ${\displaystyle A}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {M}}}$
• Una función se puede definir en (con parámetros) si su gráfica se puede definir (con esos parámetros) en . ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {M}}}$
• Un elemento se puede definir en (con parámetros) si el conjunto singleton se puede definir en (con esos parámetros). ${\displaystyle a}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle \{a\}}$ ${\displaystyle {\mathcal {M}}}$

Ejemplos

Los números naturales con sólo la relación de orden.

Sea la estructura formada por los números naturales con el orden habitual ^{[ se necesita aclaración ]} . Entonces cada número natural se puede definir sin parámetros. El número está definido por la fórmula que indica 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 número entero específico sin parámetros en la estructura que consta de números enteros con el orden habitual (consulte 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 consta de los números naturales y sus operaciones aritméticas habituales y su 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 formada por el cuerpo de los números reales ^{[ se necesita aclaración ]} . Aunque la relación de orden habitual no está incluida 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: ${\displaystyle {\mathcal {R}}=(\mathbb {R} ,0,1,+,\cdot )}$

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

Por tanto, cualquiera es no negativo si y sólo si . Junto con una fórmula que define el inverso aditivo de un número real en , se puede utilizar para definir el orden habitual en : para , establecer si y solo si no es negativo. La estructura ampliada 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 sólo 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 del cuantificador . Así, los conjuntos definibles son combinaciones booleanas de soluciones a igualdades y desigualdades polinómicas; estos se llaman conjuntos semialgebraicos . Generalizar esta propiedad de la recta real conduce al estudio de la o-minimidad . ${\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 con parámetros de . Sea un automorfismo de que es la identidad en . Entonces para todos , ${\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 solo si ${\displaystyle (\pi (a_{1}),\ldots ,\pi (a_{m}))\in A.}$

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 preserva el conjunto vacío de parámetros y, por lo tanto, es imposible definir cualquier número entero particular en esta estructura sin parámetros en . De hecho, dado que dos números enteros cualesquiera se transportan entre sí mediante una traducción y su inversa, los únicos conjuntos de números enteros definibles sin parámetros son el conjunto vacío y él mismo. En contraste, hay infinitos conjuntos definibles de pares (o incluso n -tuplas para cualquier n > 1 fijo) 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 determinada.

Referencias

• Hinman, Pedro. 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 , 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.