Completness of Presburgers arithmetic

The subject of this paper is to present the Presburger's Arithmetic and proof of the most important fact connected with it – its completeness. In 1929, Moses Presburger proved that the theory of adding integers is complete and decidable. Since his work was very revealing, the arithmetic of adding naturals was named after Presburger. The fundamental content of the proof of completeness is to show that all the formulas of the theory can be transformed into a non-quantifier form. Then it is proved that every sentence or its negation is a theorem of the theory. This method, called the elimination of quantifiers, developed by Presburger, is a significant contribution to the development of logic and the foundations of mathematics.

Przedmiotem niniejszej pracy jest przedstawienie arytmetyki Presburgera oraz dowodu najważniejszego faktu z nią związanego jaką jest jej zupełność. W 1929 roku Mojżesz Presburger udowodnił, że arytmetyka samego dodawania liczb całkowitych jest zupełna i rozstrzygalna. Doniosłość tego odkrycia przyczyniła się do nazwania arytmetyki dodawania liczb naturalnych jego nazwiskiem. Zasadniczą treścią dowodu zupełności jest pokazanie, że wszystkie formuły omawianej teorii można przekształcić do postaci bezkwantyfikatorowej. Następnie dowodzi się, że każde zdanie, albo jego zaprzeczenie, jest twierdzeniem teorii. Metoda ta, nazywana eliminacją kwantyfikatorów, opracowana przez Presburgera, jest znaczącym wkładem w rozwój logiki i podstaw matematyki.