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 é chamada de aritmeticamente definível se o gráfico de é 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 é aritmética se existe uma fórmula tal que é válida para todas as k-uplas 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 na linguagem da aritmética de Peano sem variáveis livres, um novo parâmetro de conjunto Z , e uma relação associada ao conjunto, tal que Y é o único conjunto Z, tal que é válida.
Todo conjunto aritmético é implicitamente aritmético; se X é definido aritmeticamente por φ(n) então ele é definido implicitamente pela fórmula . 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.
Ver 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. Categoria:Teoria da computabilidade