ビュヒ算術

基数kのBüchi 算術は、加算と関数を備えた自然数の一次理論である。${\displaystyle V_{k}(x)}$これは、 xを割り切るkの最大べき乗として定義され、スイスの数学者ユリウス・リヒャルト・ビューヒにちなんで名付けられました。ビューヒ算術のシグネチャには加算演算のみが含まれています。${\displaystyle V_{k}}$そして等号は、乗算演算を完全に省略して表されます。

ペアノ算術とは異なり、ビューヒ算術は決定可能な理論である。これは、ビューヒ算術の言語で記述された任意の文について、その文がビューヒ算術の公理から証明可能かどうかを効果的に判定できることを意味する。

サブセット${\displaystyle X\subseteq \mathbb {N} ^{n}}$は、 k基数の Büchi 算術で定義可能であるのは、 k認識可能である場合に限る。

もし${\displaystyle n=1}$これは、基数kのXの整数の集合がオートマトンによって受理されることを意味します。同様に、${\displaystyle n>1}$k基数でn 個の整数の最初の桁、次に 2 桁、といったように読み込んで、 n 個の整数が関係Xに含まれる場合に単語を受け入れるオートマトンが存在する。 

kとlが乗法的に依存関係にある場合、基数kとlのBüchi算術は同じ表現力を持つ。実際${\displaystyle V_{l}}$定義できる${\displaystyle {\text{FO}}(V_{k},+)}$、一次理論${\displaystyle V_{k}}$そして${\displaystyle +}$。

そうでなければ、両方の算術理論${\displaystyle V_{k}}$そして${\displaystyle V_{l}}$関数はペアノ算術と同等であり、乗算は定義可能であるため、加算と乗算の両方がある。${\displaystyle {\text{FO}}(V_{k},V_{l},+)}$。

さらに、コブハム・セメノフの定理によれば、ある関係がkおよびlのビューヒ算術で定義可能であれば、プレスバーガー算術でも定義可能である。^{[ 1 ] [ 2 ]}

• ベス、アレクシス。「算術的定義可能性の概観」 。 2012年6月27日取得。{{cite web}}: CS1メンテナンス: アーカイブサービスは非推奨になりました (リンク)

• Bès, Alexis (1997). "Büchi算術の決定不能な拡張と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 .