Büchiho aritmetika - Büchi arithmetic - Wikipedia

Büchiho aritmetika základny k je teorie prvního řádu z přirozená čísla s přidání a funkce ${ displaystyle V_ {k} (x)}$ který je definován jako největší síla k dělení X, pojmenovaný na počest švýcarského matematika Julius Richard Büchi. The podpis aritmetiky Büchi obsahuje pouze operaci sčítání, ${ displaystyle V_ {k}}$ a rovnost, přičemž operaci násobení zcela vynecháme.

Na rozdíl od Peano aritmetika, Büchiho aritmetika je a rozhodnutelná teorie. To znamená, že u jakékoli věty v jazyce buchi aritmetiky je možné účinně určit, zda je tato věta prokazatelná z axiomů buchi aritmetiky.

Büchiho aritmetika a automaty

Podmnožina ${ displaystyle X subseteq mathbb {N} ^ {n}}$ je definovatelný v Büchi aritmetice základny k právě když je k- rozpoznatelné.

Li ${ displaystyle n = 1}$ to znamená, že množina celých čísel X v základně k je přijímán automat. Podobně pokud ${ displaystyle n> 1}$ existuje automat, který čte první číslice, pak druhé číslice atd. z n celá čísla v základu k, a přijímá slova, pokud n celá čísla jsou ve vztahuX.

Vlastnosti aritmetiky Büchi

Li k a l jsou multiplikativně závislé, pak Büchiho aritmetika základny k a l mají stejnou expresivitu. Vskutku ${ displaystyle V_ {l}}$ lze definovat v ${ displaystyle { text {FO}} (V_ {k}, +)}$, teorie prvního řádu ${ displaystyle V_ {k}}$ a ${ displaystyle +}$.

Jinak aritmetická teorie s oba ${ displaystyle V_ {k}}$ a ${ displaystyle V_ {l}}$ funkce je ekvivalentní s Peano aritmetika, který má sčítání i násobení, protože násobení je definovatelné v ${ displaystyle { text {FO}} (V_ {k}, V_ {l}, +)}$.

Dále tím, že Cobham – Semënovova věta, pokud je vztah definovatelný v obou k a l Büchiho aritmetika, pak je definovatelná v Presburgerova aritmetika.^[1][2]

Reference

• Bès, Alexis. „Průzkum aritmetické definovatelnosti“. Archivovány od originál dne 2012-11-28. Citováno 27. června 2012.

Další čtení

• Bès, Alexis (1997). „Nerozhodnutelná rozšíření Büchiho aritmetiky a Cobham-Semënovovy věty“. J. Symb. Log. 62 (4): 1280–1296. CiteSeerX  10.1.1.2.1007. doi:10.2307/2275643. Zbl  0896.03011.