Büchi arithmetic of base ''k'' is the

first-order theory First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...

of the

natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...

s with

addition Addition (usually signified by the plus symbol ) is one of the four basic operations of arithmetic, the other three being subtraction, multiplication and division. The addition of two whole numbers results in the total amount or ''sum'' of ...

and the function

V_k(x)

which is defined as the largest power of ''k'' dividing ''x'', named in honor of the Swiss mathematician

Julius Richard Büchi Julius Richard Büchi (1924–1984) was a Swiss logician and mathematician. He received his Dr. sc. nat. in 1950 at ETH Zurich under the supervision of Paul Bernays and Ferdinand Gonseth. Shortly afterwards he went to Purdue University in Lafa ...

. The

signature A signature (; from la, signare, "to sign") is a Handwriting, handwritten (and often Stylization, stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and ...

of Büchi arithmetic contains only the addition operation,

V_k

and equality, omitting the multiplication operation entirely. Unlike

Peano arithmetic In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly ...

, Büchi arithmetic is a decidable theory. This means it is possible to effectively determine, for any sentence in the language of Büchi arithmetic, whether that sentence is provable from the axioms of Büchi arithmetic.

Büchi arithmetic and automata

A subset

X\subseteq \mathbb  N^n

is definable in Büchi arithmetic of base ''k'' if and only if it is ''k''-recognisable. If

n=1

this means that the set of integers of ''X'' in base ''k'' is accepted by an

automaton An automaton (; plural: automata or automatons) is a relatively self-operating machine, or control mechanism designed to automatically follow a sequence of operations, or respond to predetermined instructions.Automaton – Definition and More ...

. Similarly if

n>1

there exists an automaton that reads the first digits, then the second digits, and so on, of ''n'' integers in base ''k'', and accepts the words if the ''n'' integers are in the relation ''X''.

Properties of Büchi arithmetic

If ''k'' and ''l'' are multiplicatively dependent, then the Büchi arithmetics of base ''k'' and ''l'' have the same expressivity. Indeed

V_l

can be defined in

\text(V_k,+)

, the first-order theory of

V_k

and

+

. Otherwise, an arithmetic theory with ''both''

V_k

and

V_l

functions is equivalent to

, which has both addition and multiplication, since multiplication is definable in

\text(V_k,V_l,+)

. Further, by the Cobham–Semënov theorem, if a relation is definable in both ''k'' and ''l'' Büchi arithmetics, then it is definable in

Presburger arithmetic Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who introduced it in 1929. The signature of Presburger arithmetic contains only the addition operation and equality, omit ...

Büchi arithmetic and automata

Properties of Büchi arithmetic

References

Further reading