# 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 $f:\subseteq \mathbb {N} ^{k}\to \mathbb {N}$ é chamada de aritmeticamente definível se o gráfico de $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 $R(n_{1},\ldots ,n_{k})$ é aritmética se existe uma fórmula $\psi (n_{1},\ldots ,n_{k})$ tal que $R(n_{1},\ldots ,n_{k})\Leftrightarrow \psi (n_{1},\ldots ,n_{k})$ é válida para todas as k-uplas $(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 $\theta (Z)$ na linguagem da aritmética de Peano sem variáveis livres, um novo parâmetro de conjunto Z , e uma relação $\in$ associada ao conjunto, tal que Y é o único conjunto Z, tal que $\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
    $\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