Aritmética de Büchi

La aritmética de Büchi en base k es la teoría de primer orden de los números naturales con suma y la función${\displaystyle V_{k}(x)}$que se define como la mayor potencia de k que divide a x , nombrada en honor al matemático suizo Julius Richard Büchi . La signatura de la aritmética de Büchi contiene únicamente la operación de suma,${\displaystyle V_{k}}$y la igualdad, omitiendo por completo la operación de multiplicación.

A diferencia de la aritmética de Peano , la aritmética de Büchi es una teoría decidible . Esto significa que es posible determinar, para cualquier enunciado en el lenguaje de la aritmética de Büchi, si dicho enunciado se puede demostrar a partir de los axiomas de la aritmética de Büchi.

Un subconjunto${\displaystyle X\subseteq \mathbb {N} ^{n}}$es definible en la aritmética de Büchi de base k si y solo si es k -reconocible .

Si${\displaystyle n=1}$Esto significa que el conjunto de enteros de X en base k es aceptado por un autómata . De manera similar, si${\displaystyle n>1}$Existe un autómata que lee los primeros dígitos, luego los segundos dígitos, y así sucesivamente, de n enteros en base k , y acepta las palabras si los n enteros están en la relación X. 

Si k y l son multiplicativamente dependientes , entonces la aritmética de Büchi de base k y l tiene la misma expresividad. De hecho${\displaystyle V_{l}}$puede definirse en${\displaystyle {\text{FO}}(V_{k},+)}$, la teoría de primer orden de${\displaystyle V_{k}}$y${\displaystyle +}$.

De lo contrario, una teoría aritmética con ambos${\displaystyle V_{k}}$y${\displaystyle V_{l}}$Las funciones son equivalentes a la aritmética de Peano , que tiene tanto suma como multiplicación, ya que la multiplicación es definible en${\displaystyle {\text{FO}}(V_{k},V_{l},+)}$.

Además, según el teorema de Cobham-Semënov , si una relación es definible tanto en la aritmética de Büchi k como en la l , entonces es definible en la aritmética de Presburger . ^{[ 1 ] [ 2 ]}

• Bès, Alexis. "Un estudio sobre la definibilidad aritmética" . Recuperado el 27 de junio de 2012 .{{cite web}}: CS1 maint: servicio de archivado obsoleto ( enlace )

• Bès, Alexis (1997). "Extensiones indecidibles de la aritmética de Büchi y el teorema de Cobham-Semënov". J. Symb . Log . 62 (4): 1280– 1296. CiteSeerX 10.1.1.2.1007 . doi : 10.2307/2275643 . JSTOR 2275643. S2CID 31780865. Zbl 0896.03011 .