Abrir menu principal

Na lógica matemática, um conjunto definido é 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çãoEditar

Seja   uma linguagem de primeira ordem,   uma  -estrutura com domínio  ,   um subconjunto fixo de  , e   um número natural. Então:

  • Um conjunto   é definido em   com parâmetros de   se e somente se existe uma fórmula   e elementos   de tal modo que para todos  ,
  ise e somente se  
A notação aqui indica o suporte de avaliação semântica das variáveis livres na fórmula.
  • Um conjunto   é definido em   sem parâmetros se é definível em   com os parâmetros do conjunto vazio (ou seja, sem parâmetros na fórmula de definição).
  • Um função é definida em   (com parâmetros) se o seu grafo é definido (com esses parâmetros) em  .
  • Um elemento   é definido em   (com parâmetros) se o conjunto vazio   é definido em   (com esses parâmetros).

ExemplosEditar

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

Seja   a estrutura composta dos números naturais com a ordenação usual. Em seguida, cada número natural é definido em   sem parâmetros. O número   é definido pela fórmula   afirmando que não existem elementos menores do que x:

 

e um natural   é definido pela fórmula   afirmando que existe exatamente   elementos menores do que x:

 

Em contrapartida, não se pode definir qualquer inteiro específico sem parâmetros na estrutura   consistindo dos inteiros com a ordenação usual (veja a seção sobre automorfismo abaixo).

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

Seja   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 reaisEditar

Seja   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:

 

Assim, qualquer   é não negativo se e somente se  . Em conjunto com uma fórmula que define o inverso aditivo de um número real em  , pode-se usar   para definir a ordem usual em  : para  , o conjunto   se e somente se   é não negativo. A estrutura alargada  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   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 automorfismosEditar

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

Seja   um  -com estrutura de domínio  ,  , e   definido em   com parâmetros de  . Seja   um automorfismo de   que representa a identidade de  . Então, para todos  ,
  se e somente se  

Este resultado pode, por vezes, ser utilizados para classificar os subconjuntos definidos de uma dada estrutura. Por exemplo, no caso de   acima, qualquer tradução de  é um automorfismo preservar o conjunto vazio de parâmetros, e, assim, é impossível definir qualquer inteiro particular nesta estrutura sem parâmetros  . 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   sem parâmetros são o conjunto vazio e  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  , desde que o automorfismo preserve a "distância" entre dois elementos.

Resultados AdicionaisEditar

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

ReferênciasEditar

  • 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.