Теория алгоритмов. Зюзысов В.М. - 38 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

У логики один недостаток: она не
останавливается на полпути.
Д. Уиндем День триффидов.
4 Элементарная арифметика и неполнота
4.1 Элементарная арифметика
Теория элементарной арифметики
Попытаемся получить независимую формализацию средств математического
рассуждения, использующих только понятие натурального числа (не упоминая ни
действительных чисел, ни – тем более – произвольных множеств Кантора). Это самая
надежная часть арсенала математики, не скомпрометировавшая себя парадоксами.
Естественно назвать ее элементарной арифметикой (по аналогии с термином
«элементарная теория чисел» – в отличие от аналитической
теории чисел).
Язык элементарной арифметики – это язык первого порядка, который имеет:
предметную константу 0;
двухместные функторы + и ×, одноместный функтор S;.
двухместный предикат =.
В качестве универсума при стандартной интерпретации элементарной
арифметики рассматривается множество натуральных чисел, причем предметной
константе 0 соответствует число ноль. Термы интерпретируются как натуральные числа.
Значение функции S(t) для любого терма t, обозначающего натуральное число,
интерпретируется как (непосредственно) следующее число за t. Термы, имеющие вид S(0),
S(S(0)),
S(S(S(0))) и т. д. интерпретируются как натуральные числа 1, 2, 3 и т.д. Знаки + и
× интерпретируются как обозначения операций сложения и умножения.
Язык элементарной арифметики использует только предикатный символ равенства
«=» (понимаемый как равенство натуральных чисел). Если t
1
, t
2
– термы языка, то t
1
=t
2
–
элементарная формула. Из элементарных формул с помощью логических связок и
кванторов строятся более сложные формулы языка, причем ∃x мы понимаем как
«существует натуральное число», а ∀x – как «для всех натуральных чисел».
Средствами языка элементарной арифметики легко записываются простейшие
утверждения о свойствах натуральных чисел, например:
«x < y» ⇔ ∃z
(¬(z=0)& y=x+z);
«x – четное число» ⇔ ∃y(x=y+y);
«x – простое число» ⇔ «S(0)<x» & ¬∃y∃z(«y<x»& «z<x» & x=y×z);
«существует бесконечно много простых чисел» ⇔ ∀x∃y(«x<y» & «y – простое число»).
Все, что мы до
сих пор говорили о нашем «понимании» языка элементарной
арифметики, является нашим личным делом и к определению теории элементарной
арифметики не относится. Аксиоматическое построение этой дисциплины известно как
теория элементарной арифметики (или система аксиом Пеано, названная в честь автора
Джузеппе Пеано, 1891 г.).
Теория элементарной арифметики EA – это теория первого порядка с языком
элементарной арифметики и аксиомами Пеано. В этой теории о свойствах введенных нами
символов известно только то, что сформулировано в аксиомах. Часть этих свойств уже
содержится в логических аксиомах и правилах вывода, которые безоговорочно

Страницы