Interested Article - Арифметика Пресбургера

Арифметика Пресбургера — это теория первого порядка , описывающая натуральные числа со сложением , но в отличие от арифметики Пеано , исключающая высказывания относительно умножения . Названа в честь польского математика Мойжеша Пресбургера , который в 1929 году предложил соответствующую систему аксиом в логике первого порядка , а также показал её разрешимость .

Аксиомы

Язык арифметики Пресбургера включает константы 0, 1, одну операцию + и предикат равенства =. Аксиомы имеют вид:

¬ (0 = x + 1)
x + 1 = y + 1 → x = y
x + 0 = x
( x + y ) + 1 = x + ( y + 1)
( P (0) ∧ ( P ( x )→ P ( x + 1))) → P ( y ), где P — формула первого порядка включающая 0, 1, +, = и одну свободную переменную x .

Следует заметить, что (5) на самом деле не одна аксиома, а схема аксиом , представляющая бесконечное множество аксиом, по одной, для каждой формулы P . (5) является формализацией принципа математической индукции . Она не может быть эквивалентно заменена никакой конечной системой аксиом. Таким образом арифметика Пресбургера не является конечно аксиоматизируемой .

См. также

Литература

Cooper, D. C., 1972, «Theorem Proving in Arithmetic without Multiplication» in B. Meltzer and D. Michie, eds., Machine Intelligence . Edinburgh University Press: 91-100.
, and Charles W. Rackoff, 1979. The Computational Complexity of Logical Theories . Lecture Notes in Mathematics 718. Springer-Verlag .
Fischer, M. J., and , 1974, " » Proceedings of the SIAM-AMS Symposium in Applied Mathematics Vol. 7 : 27-41.
G. Nelson and D. C. Oppen. (англ.) // Proc. 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages : journal. — Apr. 1978. — P. 141—150 .
, 1929, «Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt» in Comptes Rendus du I congrès de Mathématiciens des Pays Slaves . Warszawa: 92-101.
Pugh, William, 1991, « ».
Reddy, C. R., and D. W. Loveland, 1978, « » ACM Symposium on Theory of Computing : 320—325.