比奇算术

基数为k的比奇算术是自然数的一阶理论，有加法和函数它被定义为k的xxx幂除以x，为纪念瑞士数学家JuliusRichardBüchi而命名。Büchi算术的签名只包含加法运算。和平等，完全省略了乘法运算。与Peano算术不同，Büchi算术是一个可解理论。这意味着，对于比奇算术语言中的任何句子，都可以有效地确定该句子是否可以从比奇算术的公理中得到证明。

一个子集在基数为k的Büchi算术中是可定义的，当且仅当它是可识别的。如果n=1{displaystylen=1}，这意味着整数集是可以被识别的。这意味着基数为k的X的整数集被一个自动机所接受。同样地，如果n>1{displaystylen>1}存在一个自动机，可以读取xxx个数字。存在一个自动机，它读取基数为k的n个整数的xxx个数字，然后是第二个数字，以此类推，如果这n个整数在关系式X中，则接受这些字。

如果k和l是乘法依赖的，那么基数为k和l的Büchi算术具有相同的表达能力。事实上此外，根据Cobham-Semënov定理，如果一个关系在k和lBüchi算术中都可以定义，那么它在Presburger算术中也可以定义。