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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Арифметика Пресбургера — это теория первого порядка описывающая натуральные числа со сложением, но в отличие от арифметики Пеано, исключающая высказывания относительно умножения. Названа в честь польского математика Мозеса Пресбургера, который в 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) является формализацией принципа математической индукции. Она не может быть эквивалентно заменена никакой конечной системой аксиом. Таким образом арифметика Пресбургера не является конечно аксиоматизируемой.

См. также[править | править исходный текст]

Литература[править | править исходный текст]

  • Верещагин, Шень Лекции по математической логике и теории алгоритмов. — МЦНМО, 2002.

Ссылки[править | править исходный текст]

  • Online-Proofer Java-апплет, проверяющий формулы арифметики Пресбургера на истинность.  (нем.)