18 votos

¿Qué es un conjunto definible?

He leído la definición de un montón de veces pero no acabo de entenderlo. ¿Qué se entiende por $(M,\in)$ satisface $\varphi(x;a_1,\ldots)$?

Recordemos que un conjunto $X$ es un definibles a través de un modelo de $(M, \in)$ donde $M$ es un conjunto, si no existe una fórmula $\varphi$ en el conjunto de las fórmulas para el idioma $\{\in\}$, y algunos de los elementos $a_1, \ldots, a_n \in M$ tal que $X=\{ x\in M: (M, \in ) \vDash \varphi[x, a_1, \ldots, a_n]\}$.

Deje $$\operatorname{def}(M) = \{X\subset M : X \text{ is definable over }(M, \in)\}$$

Hay un ejemplo sencillo que hará que sea más claro? Y por qué es un subconjunto de la powerset? Gracias.

33voto

ManuelSchneid3r Puntos 116

Así que, aunque la pregunta habla sobre el lenguaje de la teoría de conjuntos específicamente, permítanme responder a la pregunta más general.

También, voy a hablar de definibles subconjuntos de a $M$, frente a un definibles sbsets de la Cartesiano poderes de $M$ - por ejemplo, podemos preguntar, "Cuando es un conjunto de pares ordenados de elementos de $M$ definibles?" La respuesta es una simple generalización de lo que escribo a continuación, y que es un buen ejercicio.

Primero, permítanme describir definability sin parámetros. Que es, de lo que quiero hablar acerca de abajo va a ser que no , teniendo en cuenta el $a_i$s de su pregunta; voy a llegar a los que más tarde.

Supongamos que tengo de primer orden de la estructura de $M$ en algunos idiomas,$L$. Decir, $L$ es el idioma de los anillos ($+, \times, 0, 1$) y $M$ es el anillo de $\mathbb{Z}$.

A continuación, $M$ (de curso) muchos subgrupos, pero algunos de estos subconjuntos son mucho más agradables que otros, en el sentido de "ser descriptible" el uso de la lengua $L$. Por ejemplo, supongamos $E$ el conjunto de los números pares. A continuación, $E$ es el conjunto de $x$ que "Hay algunos $y$ tal que $x=y+y$." Más formalmente, $E$ es el conjunto de elementos de la $x$ $M$ tal que el enunciado "hay algunos $y$ tal que $x=y+y$" es una declaración verdadera acerca de $M$. Esto es lo que se entiende por "$M$ satisface . . . "Es decir, "... es cierto en $M$." En particular, siendo muy formal, podríamos escribir $$E=\{x: M\models \exists y(x=y+y)\}.$$ The formal definition of "$\Vdash$" is actually somewhat annoying; at first, I think it's better to just think of it informally, so "$M\modelos \varphi$" means "$\varphi$ is a true statement about $M$." Pero ver http://en.wikipedia.org/wiki/First-order_logic#Semantics, o cualquier buen libro de texto de lógica.

Un juego como este - que no es una fórmula $\varphi(x)$ en el idioma $L$, de modo que el conjunto es igual a $\{x: M\models\varphi(x)\}$ - se llama definible sin parámetros. Otros definibles subconjuntos de a $M$ incluyen el conjunto de los cuadrados perfectos, el conjunto de los números positivos (esto toma un poco de trabajo, ya que no tenemos el símbolo "$<$"!), y el conjunto de los números primos.

Tenga en cuenta que el definability de un subconjunto de a $M$ depende de manera crucial en el lenguaje de la $M$. Por ejemplo, considere la estructura de $M'$ cuyo conjunto subyacente es $\mathbb{Z}$ como antes, pero cuyo lenguaje es el vacío del lenguaje (no hay símbolos excepto =). A continuación, ningún subconjunto de $M'$ es definible sin parámetros, excepto la de toda la estructura y el emptyset; esto es una consecuencia del hecho, se puede demostrar por inducción, que definibles conjuntos son preservadas por los automorfismos: si $\alpha$ es un automorphism de $M$ $D$ es definible subconjunto de $M$,$\alpha(D)=D$. La afirmación acerca de la $M'$ ahora de la siguiente manera, ya que cada permutación de $M'$ es un automorphism de $M'$.


OK, ahora ¿qué pasa con los $a_i$s? Bueno, hay un par de maneras para tratar esto.

En primer lugar, dado cualquier conjunto de $A\subset M$ de una estructura en un lenguaje $L$, se puede considerar una ampliación de lenguaje $L_A=L\sqcup\{c_a: a\in A\}$ obtenido por la adición de una nueva constante símbolo de cada elemento de $A$, y la expansión de la $M_A$ $M$ obtenido mediante la toma de $M$, e interpretar el símbolo $c_a$ $a$ por cada $a\in A$.

El hecho de pasar de $M$ $M_A$es todo acerca de la adición de la potencia expresiva. Específicamente, más conjuntos son definibles en $M_A$ que fueron definidos en $M$! Por ejemplo, cada subconjunto finito de $A$ ahora es definible en $M_A$; y podemos conseguir más, además. Por otro lado, porque las definiciones sólo se puede utilizar un número finito de símbolos, el conjunto total $A$ podría no ser definible en $M_A$ (por ejemplo, tome $M'$ desde antes y $A=\{evens\}$).

Es decir, en la definición de un conjunto, sólo hacemos uso de un número finito de símbolos: para un conjunto específico $D\subset M$, $D$ es definible en $M_A$ fib $D$ es definible en $M_{A_0}$ para algunos finito $A_0\subset A$.

Decimos que un conjunto a $D\subset M$ es definible a partir de parámetros (generalmente, sólo decir que "definible") si, para algunos $A$, $D$ es un definibles por el subconjunto de $M_A$. Tenga en cuenta que por el párrafo anterior, podemos suponer $A$ es finito - $A$ es sólo el conjunto de $\{a_0, a_1, . . . , a_n\}$ de su OP!

Así que, a continuación, $Def(M)$ es la colección de definibles-con-los parámetros de subconjuntos de a $M$. Ya que esta es una colección de subconjuntos de a $M$, es un subconjunto de la powerset de $M$.


Alternativamente, si usted no quiere pensar en la expansión de $M$, podemos pensar en una fórmula $\varphi$ $n+1$ variables como describir un montón de juegos, uno para cada una de las $n$-tupla de elementos de $M$: dada la tupla $a_1, . . . , a_n$, obtenemos el conjunto de $$\varphi_{a_1, . . . , a_n}=\{m\in M: M\models \varphi(m, a_1, . . . , a_n)\}.$$ Then a set is definable with parameters if it is of the form $\varphi_{a_1, . . . , a_n}$ for some formula $\varphi$ and tuple of elements of $M$ $a_1, . . . , a_n$.

Me parece que este enfoque más difícil de pensar, pero sin duda es más corto. Por otro lado, una ventaja que tiene es que se conecta muy bien con definibles subconjuntos de mayor Cartesiano poderes: una fórmula $\varphi$ $n+1$ variables define - sin parámetros - un subconjunto de a $M^{n+1}$; luego tenemos que un subconjunto de a $M$ es definible con los parámetros de la fib es una proyección de algunos definibles-sin-parámetros subconjunto de un mayor Cartesiano poder de $M$. Esta es la clase de niza!

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X