Aritmética de Büchi

Aritmética de Büchi de base k é a teoria de primeira ordem dos números naturais com  adição e a função $V_{k}(x)$ que é definida como a maior potência de k dividindo x, denominado em homenagem ao matemático Suíço Julius Richard Büchi. A assinatura da aritmética de Büchi contém apenas a operação de adição, $V_{k}$ e a igualdade, omitindo-se a operação de multiplicação inteiramente.

Ao contrário da aritmética de Peano, a aritmética de Büchi é uma teoria decidível. Isto significa que é possível, efetivamente, determinar para qualquer sentença na linguagem da aritmética de Büchi, se essa sentença é demonstrável a partir de axiomas da aritmética de Büchi .

Aritmética de Büchi e autômato

Um subconjunto $X\subseteq \mathbb {N} ^{n}$ é definível na aritmética de Büchi  de base de k se, e somente se, ele é k-reconhecível.

Se $n=1$ isso significa que o conjunto de números inteiros de X na base k é aceito por um autômato. Da mesma forma, se $n>1$ existe um autômato que lê os primeiros dígitos, os segundos dígitos, e assim por diante, de n números inteiros na base k, e aceita as palavras, se os n números inteiros estão na relação X.

Propriedades da aritmética de Büchi

Se k e l são multiplicativamente dependentes , então, a aritmética de Büchi de base k e l têm a mesma expressividade. De fato, $V_{l}$ pode ser definida em ${\text{FO}}(V_{k},+)$.

Senão, a teoria com ambas funções  $V_{k}$ e $V_{l}$  é equivalente a aritmética de Peano a lógica com a adição e a multiplicação, pois a multiplicação é definível em ${\text{FO}}(V_{k},V_{l},+)$.

Por outro lado, pelo teorema de Cobham-Semenov, se a relação é definível em ambos os k e l a aritmética de Büchi é definível na aritmética de Presburger.

Ver também

• Autômato de Büchi

Referências

• Bès, Alexis. «A survey of Arithmetical Definability». Consultado em 27 de junho de 2012. Arquivado do original em 28 de novembro de 2012 

Leitura adicional

• Bès, Alexis (1997). «Undecidable extensions of Büchi arithmetic and Cobham-Semënov theorem». J. Symb. Log. 62 (4): 1280-1296. Zbl 0896.03011. doi:10.2307/2275643