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

• Predefinição:Citar web

Leitura adicional

• Predefinição:Citar periódico