Conjunto definível

Na lógica matemática, um conjunto definível é uma relação n-ária sobre o domínio de uma estrutura cujos elementos são precisamente aqueles elementos que satisfaçam alguma fórmula na língua dessa estrutura. Um conjunto pode ser definido com ou sem parâmetros, que são elementos do domínio que podem ser referenciados na fórmula que define a relação.

Definição

Seja ${\mathcal {L}}$ uma linguagem de primeira ordem, ${\mathcal {M}}$ uma ${\mathcal {L}}$-estrutura com domínio $M$, $X$ um subconjunto fixo de $M$, e $m$ um número natural. Então:

• Um conjunto $A\subseteq M^{m}$ é definido em ${\mathcal {M}}$ com parâmetros de $X$ se e somente se existe uma fórmula $\varphi [x_{1},\ldots ,x_{m},y_{1},\ldots ,y_{n}]$ e elementos $b_{1},\ldots ,b_{n}\in X$ de tal modo que para todos $a_{1},\ldots ,a_{m}\in M$,

$(a_{1},\ldots ,a_{m})\in A$ ise e somente se ${\mathcal {M}}\models \varphi [a_{1},\ldots ,a_{m},b_{1},\ldots ,b_{n}]$

A notação aqui indica o suporte de avaliação semântica das variáveis livres na fórmula.

• Um conjunto $A$ é definido em ${\mathcal {M}}$ sem parâmetros se é definível em ${\mathcal {M}}$ com os parâmetros do conjunto vazio (ou seja, sem parâmetros na fórmula de definição).
• Um função é definida em ${\mathcal {M}}$ (com parâmetros) se o seu grafo é definido (com esses parâmetros) em ${\mathcal {M}}$.
• Um elemento $a$ é definido em ${\mathcal {M}}$ (com parâmetros) se o conjunto vazio $\{a\}$ é definido em ${\mathcal {M}}$ (com esses parâmetros).

Exemplos

Os números naturais com apenas a relação de ordem

Seja ${\mathcal {N}}=(\mathbb {N} ,<)$ a estrutura composta dos números naturais com a ordenação usual. Em seguida, cada número natural é definido em ${\mathcal {N}}$ sem parâmetros. O número $0$ é definido pela fórmula $\varphi (x)$ afirmando que não existem elementos menores do que x:

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

e um natural $n>0$ é definido pela fórmula $\varphi (x)$ afirmando que existe exatamente $n$ elementos menores do que x:

$\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})))$

Em contrapartida, não se pode definir qualquer inteiro específico sem parâmetros na estrutura ${\mathcal {Z}}=(\mathbb {Z} ,<)$ consistindo dos inteiros com a ordenação usual (veja a seção sobre automorfismo abaixo).

Os números naturais com suas operações aritméticas

Seja ${\mathcal {N}}=(\mathbb {N} ,+,\cdot ,<)$ a estrutura de primeira ordem com os números naturais e suas operações aritméticas usuais e relação de ordem. Os conjuntos definidos nesta estrutura são conhecidos como o conjunto de aritmética, e são classificados na hierarquia aritmética. Se a estrutura é considerada na lógica de segunda ordem em vez de lógica de primeira ordem, os conjuntos definidos de números naturais na estrutura resultante são classificados na hierarquia analítica. Essas hierarquias revelar muitas relações entre definibilidade nesta estrutura e na teoria da computabilidade, e também são de interesse na teoria dos conjuntos descritivo.

O campo dos números reais

Seja ${\mathcal {R}}=(\mathbb {R} ,0,1,+,\cdot )$ a estrutura que consiste nos camṕos dos números reais. Embora a relação de ordem usual não está diretamente incluídos na estrutura, não existe uma fórmula que defina o conjunto de reais não-negativos, uma vez que estes são as únicos reais que possuem raízes quadradas:

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

Assim, qualquer $a\in \mathbb {R}$ é não negativo se e somente se ${\mathcal {R}}\models \varphi [a]$. Em conjunto com uma fórmula que define o inverso aditivo de um número real em ${\mathcal {R}}$, pode-se usar $\varphi$ para definir a ordem usual em ${\mathcal {R}}$: para $a,b\in \mathbb {R}$, o conjunto $a\leq b$ se e somente se $b-a$ é não negativo. A estrutura alargada ${\mathcal {R}}^{\leq }=(\mathbb {R} ,0,1,+,\cdot ,\leq )$s é chamado de extensão de definição da estrutura original. Tem o mesmo poder expressivo como a estrutura original, no sentido de que um conjunto é definida através da estrutura alargada a partir de um conjunto de parâmetros se e só se for definida através da estrutura original do que o mesmo conjunto de parâmetros.

A teoria de ${\mathcal {R}}^{\leq }$ tem quantificador de eliminação. Assim, os conjuntos definíveis são combinações booleanas de soluções para igualdades polinomiais e desigualdades; estes são chamados conjuntos semi-algébricos. Generalizando este estabelecimento do eixo real leva ao estudo de o-minimalidade.

Invariância sob automorfismos

Um resultado importante sobre conjuntos definíveis é que eles são preservados sob automorfismo.

Seja ${\mathcal {M}}$ um ${\mathcal {L}}$-com estrutura de domínio $M$, $X\subseteq M$, e $A\subseteq M^{m}$ definido em ${\mathcal {M}}$ com parâmetros de $X$. Seja $\pi :M\to M$ um automorfismo de ${\mathcal {M}}$ que representa a identidade de $X$. Então, para todos $a_{1},\ldots ,a_{m}\in M$,

$(a_{1},\ldots ,a_{m})\in A$ se e somente se $(\pi (a_{1}),\ldots ,\pi (a_{m}))\in A$

Este resultado pode, por vezes, ser utilizados para classificar os subconjuntos definidos de uma dada estrutura. Por exemplo, no caso de ${\mathcal {Z}}=(\mathbb {Z} ,<)$ acima, qualquer tradução de${\mathcal {Z}}$ é um automorfismo preservar o conjunto vazio de parâmetros, e, assim, é impossível definir qualquer inteiro particular nesta estrutura sem parâmetros ${\mathcal {Z}}$. Na verdade, uma vez que quaisquer dois inteiros são transportados para o outro de uma tradução e seu inverso, os únicos conjuntos de números inteiros definidos em ${\mathcal {Z}}$ sem parâmetros são o conjunto vazio e$\mathbb {Z}$ de si mesmo. Em contraste, há uma infinidade de conjuntos definíveis de pares (ou mesmo n - tuplas para qualquer fixo n > 1) de elementos de ${\mathcal {Z}}$, desde que o automorfismo preserve a "distância" entre dois elementos.

Resultados Adicionais

O teste Taski-Vaught é usado para caracterizar as subestruturas elementares de uma dada estrutura.

Referências

• Hinman, Peter. Fundamentals of Mathematical Logic, A. K. Peters, 2005.
• Marker, David. Model Theory: An Introduction, Springer, 2002.
• Rudin, Walter. Principles of Mathematical Analysis, 3rd. ed. McGraw-Hill, 1976.
• Slaman, Theodore A. and W. Hugh Woodin. Mathematical Logic: The Berkeley Undergraduate Course. Spring 2006.