Conjunto aritmético

Em lógica matemática, um conjunto aritmético é um conjunto de números naturais que pode ser definido por uma fórmula de primeira ordem da aritmética de Peano. Os conjuntos aritméticos são classificados pela hierarquia aritmética.

A definição pode ser estendida para um conjunto contável A arbitrário  (i.e. um conjunto de n-uplas de inteiros, um conjunto de números racionais, um conjunto de fórmulas em alguma linguagem formal, etc.) utilizando números de Gödel para representar elementos do conjunto e declarando um subconjunto de A como sendo aritmético se o conjunto dos correspondentes números de Gödel forem aritméticos.

A função ${\displaystyle f:\subseteq \mathbb {N} ^{k}\to \mathbb {N} }$ é chamada de aritmeticamente definível se o gráfico de ${\displaystyle f}$ é um conjunto aritmético.

Um número real é chamado de aritmético se o conjunto de todos os menores números racionais é aritmético. Um número complexo é chamado aritmético se suas partes real e imaginária são ambas aritméticas.

Definição formal

Um conjunto X de números naturais é aritmético ou aritmeticamente definível se há uma fórmula φ(n) na linguagem da aritmética de Peano tal que cada número n está em X se e somente se φ(n) está contido no modelo padrão da aritmética. Similarmente, uma relação k-ária ${\displaystyle R(n_{1},\ldots ,n_{k})}$ é aritmética se existe uma fórmula ${\displaystyle \psi (n_{1},\ldots ,n_{k})}$ tal que ${\displaystyle R(n_{1},\ldots ,n_{k})\Leftrightarrow \psi (n_{1},\ldots ,n_{k})}$ é válida para todas as k-uplas ${\displaystyle (n_{1},\ldots ,n_{k})}$ de números naturais.

Uma função finita sobre os números naturais é chamada de aritmética se o seu gráfico é uma relação binária aritmética.

Um conjunto A é dito ser aritmético em um conjunto B se A é definível por uma fórmula aritmética que tem B como um parâmetro de conjunto.

Exemplos

• O conjunto de todos os números primos é aritmético.
• Todo conjunto recursivamente enumerável é aritmético.
• Toda função computável é aritmeticamente definível.
• O conjunto que codifica o Problema da Parada é aritmético.
• A Constante de Chaitin é um número real aritmético.
• O Teorema da indefinibilidade de Tarski demonstra que o conjunto de fórmulas aritméticas verdadeiras de primeira ordem não é aritmeticamente definível.

Propriedades

• O complemento de um conjunto aritmético é um conjunto aritmético.
• O Salto de Turing de um conjunto aritmético é um conjunto aritmético.
• A coleção de conjuntos aritméticos é contável, mas não há uma sequência aritmeticamente definível que enumera todos os conjuntos aritméticos.
• O conjunto de números reais aritméticos é contável, densamente ordenável e isomorficamente ordenável para o conjunto dos números racionais.

Conjuntos implicitamente aritméticos

Cada conjunto aritmético tem uma fórmula aritmética que diz se determinados números estão no conjunto. Uma noção alternativa de definibilidade permite a uma fórmula que não informa se determinados números estão no conjunto, dizer se o conjunto em si satisfaz alguma propriedade aritmética. 

Um conjunto Y de números naturais é implicitamente aritmético ou implícito-aritmeticamente definível se ele é definível por uma fórmula aritmética que é capaz de usar Y como um parâmetro. Isso é, se há uma fórmula ${\displaystyle \theta (Z)}$ na linguagem da aritmética de Peano sem variáveis livres, um novo parâmetro de conjunto Z , e uma relação ${\displaystyle \in }$ associada ao conjunto, tal que Y é o único conjunto Z, tal que ${\displaystyle \theta (Z)}$ é válida.

Todo conjunto aritmético é implicitamente aritmético; se X é definido aritmeticamente por φ(n) então ele é definido implicitamente pela fórmula

${\displaystyle \forall n[n\in Z\Leftrightarrow \phi (n)]}$.

Todavia, nem todo conjunto implicitamente aritmético é aritmético. Em particular, o conjunto verdade de primeira ordem é implicitamente aritmético, mas não é aritmético.

Veja também

• Hierarquia aritmética
• Conjunto recursivo
• Número computável

Referências

• Rogers, H. (1967). Theory of recursive functions and effective computability. McGraw-Hill. OCLC 527706