Conjunto definível - Definable set

Na lógica matemática , um conjunto definível é uma relação n- arar no domínio de uma estrutura cujos elementos são precisamente aqueles elementos que satisfazem alguma fórmula na linguagem de primeira ordem 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 uma linguagem de primeira ordem, uma estrutura com domínio , um subconjunto fixo de e um número natural . Então: ${\ displaystyle {\ mathcal {L}}}$${\ displaystyle {\ mathcal {M}}}$${\ displaystyle {\ mathcal {L}}}$${\ displaystyle M}$${\ displaystyle X}$${\ displaystyle M}$${\ displaystyle m}$

• Um conjunto é definível com parâmetros de se e somente se existe uma fórmula e elementos 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}$ se e apenas se ${\ displaystyle {\ mathcal {M}} \ models \ varphi [a_ {1}, \ ldots, a_ {m}, b_ {1}, \ ldots, b_ {n}]}$

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

• Um conjunto é definível sem parâmetros se for definível com parâmetros do conjunto vazio (ou seja, sem parâmetros na fórmula de definição). ${\ displaystyle A}$${\ displaystyle {\ mathcal {M}}}$${\ displaystyle {\ mathcal {M}}}$
• Uma função é definível em (com parâmetros) se seu gráfico é definível (com esses parâmetros) em . ${\ displaystyle {\ mathcal {M}}}$${\ displaystyle {\ mathcal {M}}}$
• Um elemento é definível em (com parâmetros) se o conjunto singleton é definível em (com esses parâmetros). ${\ displaystyle a}$${\ displaystyle {\ mathcal {M}}}$ ${\ displaystyle \ {a \}}$${\ displaystyle {\ mathcal {M}}}$

Exemplos

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

Let Ser a estrutura consistindo dos números naturais com a ordenação usual. Então, todo número natural é definível sem parâmetros. O número é definido pela fórmula que afirma que não existem elementos menores que x : e um número natural é definido pela fórmula que afirma que existem exatamente elementos menores que x : ${\ displaystyle {\ mathcal {N}} = (\ mathbb {N}, <)}$${\ displaystyle {\ mathcal {N}}}$${\ displaystyle 0}$${\ displaystyle \ varphi (x)}$${\ displaystyle \ varphi = \ neg \ exists y (y <x),}$${\ displaystyle n> 0}$${\ displaystyle \ varphi (x)}$${\ displaystyle n}$

${\ displaystyle \ varphi = \ existe x_ {0} \ cdots \ existe 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 contraste, não se pode definir nenhum inteiro específico sem parâmetros na estrutura que consiste nos inteiros com a ordem usual (consulte a seção sobre automorfismos abaixo). ${\ displaystyle {\ mathcal {Z}} = (\ mathbb {Z}, <)}$

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

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

O campo dos números reais

Let Ser a estrutura consistindo do campo de números reais . Embora a relação de ordenação usual não esteja diretamente incluída na estrutura, existe uma fórmula que define o conjunto de reais não negativos, já que estes são os únicos reais que possuem raízes quadradas: ${\ displaystyle {\ mathcal {R}} = (\ mathbb {R}, 0,1, +, \ cdot)}$

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

Portanto, qualquer um é 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 , definir se e somente se for não negativo. A estrutura ampliada s é chamada de extensão de definição da estrutura original. Tem o mesmo poder expressivo da estrutura original, no sentido de que um conjunto é definível sobre a estrutura ampliada a partir de um conjunto de parâmetros se e somente se é definível sobre a estrutura original a partir desse mesmo 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 ba}$${\ displaystyle {\ mathcal {R}} ^ {\ leq} = (\ mathbb {R}, 0,1, +, \ cdot, \ leq)}$

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

Invariância sob automorfismos

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

Vamos ser um -Estrutura com o domínio , e definível em com os parâmetros de . Deixe ser um automorfismo do qual está a identidade ligada . Então, 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 \ a M}$${\ displaystyle {\ mathcal {M}}}$${\ displaystyle X}$${\ displaystyle a_ {1}, \ ldots, a_ {m} \ in M}$

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

Esse resultado às vezes pode ser usado para classificar os subconjuntos definíveis de uma determinada estrutura. Por exemplo, no caso acima, qualquer tradução de é um automorfismo que preserva o conjunto vazio de parâmetros e, portanto, é impossível definir qualquer inteiro particular nesta estrutura sem parâmetros em . Na verdade, uma vez que quaisquer dois inteiros são transportados um para o outro por uma tradução e seu inverso, os únicos conjuntos de inteiros definíveis sem parâmetros são o conjunto vazio e ele mesmo. Em contraste, existem infinitamente muitos conjuntos definíveis de pares (ou mesmo n -tuplos para qualquer n > 1 fixo ) de elementos de , uma vez que qualquer automorfismo (tradução) preserva a "distância" entre dois elementos. ${\ displaystyle {\ mathcal {Z}} = (\ mathbb {Z}, <)}$${\ displaystyle {\ mathcal {Z}}}$${\ displaystyle {\ mathcal {Z}}}$${\ displaystyle {\ mathcal {Z}}}$${\ displaystyle \ mathbb {Z}}$${\ displaystyle {\ mathcal {Z}}}$

Resultados adicionais

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

Referências

• Hinman, Peter. Fundamentals of Mathematical Logic , AK Peters, 2005.
• Marcador, David. Model Theory: An Introduction , Springer, 2002.
• Rudin, Walter. Princípios de Análise Matemática , 3o. ed. McGraw-Hill, 1976.
• Slaman, Theodore A. e W. Hugh Woodin. Lógica matemática: o curso de graduação em Berkeley . Primavera de 2006.