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

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

Аксиомы


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

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

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