Conjunto aritmético

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

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[editar | editar código-fonte]

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[editar | editar código-fonte]

Propriedades[editar | editar código-fonte]

  • O complemento de um conjunto aritmético é um conjunto aritmético.
  • 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[editar | editar código-fonte]

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.

Veja também[editar | editar código-fonte]

Referências[editar | editar código-fonte]

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