Conjunto aritmético - Arithmetical set

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

A definição pode ser estendida a um conjunto contável arbitrário A (por exemplo, o conjunto de n- tuplas de inteiros , o conjunto de números racionais , o conjunto de fórmulas em alguma linguagem formal , etc.) usando números de Gödel para representar elementos do conjunto e declarar um subconjunto de A como aritmético se o conjunto de números de Gödel correspondentes for aritmético.

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

Um número real é denominado aritmético se o conjunto de todos os números racionais menores for aritmético. Um número complexo é denominado aritmético se suas partes reais e imaginárias forem aritméticas.

Definição formal

Um conjunto X de números naturais é aritmético ou aritmeticamente definível se houver uma fórmula φ ( n ) na linguagem da aritmética de Peano tal que cada número n esteja em X se e somente se φ ( n ) for válido no modelo padrão de aritmética. Da mesma forma, um k -ary relação é aritmética se existe uma fórmula tal que vale para todo k -tuples de números naturais. ${\ displaystyle R (n_ {1}, \ ldots, n_ {k})}$${\ displaystyle \ psi (n_ {1}, \ ldots, n_ {k})}$${\ displaystyle R (n_ {1}, \ ldots, n_ {k}) \ iff \ psi (n_ {1}, \ ldots, n_ {k})}$${\ displaystyle (n_ {1}, \ ldots, n_ {k})}$

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

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

Exemplos

• O conjunto de todos os números primos é aritmético.
• Todo conjunto recursivamente enumerável é aritmético.
• Cada função computável é definível aritmeticamente.
• O conjunto que codifica o problema Halting é aritmético.
• A constante de Chaitin Ω é um número real aritmético.
• O teorema da indefinibilidade de Tarski mostra que o conjunto de fórmulas verdadeiras da aritmética 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 a sequência de conjuntos aritméticos não é definível aritmeticamente. Assim, não há fórmula aritmética φ ( n , m ) que seja verdadeira se e somente se m for um membro dos n- ésimos predicados aritméticos.

Na verdade, tal fórmula descreveria um problema de decisão para todos os saltos de Turing finitos e, portanto, pertence a 0 ^(ω) , que não pode ser formalizado na aritmética de primeira ordem , pois não pertence à hierarquia aritmética de primeira ordem .

• O conjunto de números aritméticos reais é contável , denso e de ordem isomórfica ao conjunto de números racionais.

Conjuntos implicitamente aritméticos

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

Um conjunto Y de números naturais é implicitamente aritmético ou implicitamente definível aritmeticamente se for definível com uma fórmula aritmética capaz de usar Y como parâmetro. Isto é, se houver uma fórmula na linguagem da aritmética de Peano sem variáveis ​​de número livre e um novo parâmetro de conjunto Z e relação de pertinência de conjunto tal que Y é o conjunto único Z tal que se mantém. ${\ displaystyle \ theta (Z)}$${\ displaystyle \ in}$${\ displaystyle \ theta (Z)}$

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

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

No entanto, nem todo conjunto aritmético implicitamente é aritmético. Em particular, o conjunto de verdade da aritmética de primeira ordem é implicitamente aritmético, mas não aritmético.

Veja também

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

Leitura adicional

• Rogers, H. (1967). Teoria das funções recursivas e computabilidade efetiva. McGraw-Hill. OCLC  527706