Buchi aritmetik

Büchi aritmetik av bas k är första ordningens teori för de naturliga talen med addition och funktionen $V_{k}(x)$ som definieras som den största potensen av k dividerande x , namngiven i den schweiziske matematikern Julius Richard Büchis ära . Signaturen för Büchi-arithmetik innehåller endast additionsoperationen, $V_{k}$ och likhet, vilket utelämnar multiplikationsoperationen helt.

Till skillnad från Peano aritmetik är Büchi aritmetik en avgörbar teori . Detta betyder att det är möjligt att effektivt avgöra, för vilken mening som helst på språket för Büchi-arithmetik, om den meningen är bevisbar från axiomen för Büchi-aritmetiken.

Büchi aritmetik och automater

En delmängd $X\subseteq \mathbb {N} ^{n}$ är definierbar i Büchi-aritmetiken av basen k om och endast om den är k -igenkännbar .

Om $n=1$ betyder detta att mängden heltal av X i basen k accepteras av en automat . På liknande sätt om $n>1$ finns det en automat som läser de första siffrorna, sedan de andra siffrorna, och så vidare, av n heltal i basen k , och accepterar orden om de n heltal är i relationen X .

Egenskaper för Büchi aritmetik

Om k och l är multiplikativt beroende , då har Büchi-aritmetiken för basen k och l samma uttrycksförmåga. ${\displaystyle V_{l}} kan$ faktiskt definieras i ${\displaystyle {\text{FO}}(V_{k},+)} ,$ första ordningens teori för $V_{k}$ och $+$ .

Annars är en aritmetisk teori med både $V_{k}$ och $V_{l}$ funktioner ekvivalent med Peano-aritmetik , som har både addition och multiplikation, eftersom multiplikation är definierbar i ${\text{FO}}(V_{k},V_{l},+)$ .

Vidare, enligt Cobham-Semënov-satsen , om en relation är definierbar i både k och l Büchi-aritmetik, då är den definierbar i Presburger-aritmetik .

• Bès, Alexis. "En undersökning av aritmetisk definierbarhet" . Arkiverad från originalet 2012-11-28 . Hämtad 27 juni 2012 .

Vidare läsning

•    Bès, Alexis (1997). "Oavgörliga förlängningar av Büchis aritmetik och Cobham-Semënovs teorem". J. Symb. Logga . 62 (4): 1280–1296. CiteSeerX 10.1.1.2.1007 . doi : 10.2307/2275643 . Zbl 0896.03011 .