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

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

принимаются в EA. Для определения наиболее существенных свойств мы вводим
собственные аксиомы EA:
Собственные аксиомы (схемы аксиом) элементарной арифметики:
P
1
: (P(0) & ∀x(P(x)⊃P(S(x)))⊃∀zP(z) (принцип математической индукции, P –
произвольная формула),
P
2
: S(t
1
) = S(t
2
) ⊃ t
1
= t
2
,
P
3
: ¬( S(t)=0),
P
4
: t
1
= t
2
⊃ (t
1
= t
3
⊃ t
2
= t
3
),
P
5
: t
1
= t
2
⊃ S(t
1
) = S(t
2
),
P
6
: t+0 = t,
P
7
: t
1
+ S(t
2
)
= S(t
1
+ t
2
),
P
8
: 0×t = 0,
P
9
: S(t
1
) × t
2
= t
1
× t
2
+ t
2
.
Аксиомы P
4
и P
5
обеспечивают некоторые необходимые свойства равенства.
Аксиомы P
3
и P
2
обеспечивают существование нуля и операции «непосредственно
следующий». Аксиомы P
6
–P
9
представляют собой рекурсивные равенства, служащие
определениями операций сложения и умножения.
С помощью MP из схемы аксиом P
1
мы можем получить следующее правило
индукции: из P(0) и ∀x(P(x) ⊃P(S(x))) выводится ∀xP(x).
Терм S(…S(0)…), где символ S повторяется k раз, кратко будем обозначать k.
Таким образом, натуральное число k в EA интерпретируется как терм k. Термы такого
рода 0, 1, 2
, … принято называть нумералами – стандартными обозначениями конкретных
натуральных чисел. Очевидно, термы EA – это обозначения полиномов (от нескольких,
вообще говоря, переменных) с натуральными коэффициентами. Например, терм
((x×x)+((2×x)×y))+(y×y) представляет полином x
2
+2xy+y
2
. Мы будем рассматривать теорию
EA только в стандартной интерпретации.
Сейчас удобно на примере системы EA пояснить, почему необходима аксиома A
4
для определения теории первого порядка – она предотвращает коллизию переменных.
Для теории первого порядка должна выполняться аксиома
A
4
: ∀x A(x) ⊃A(t), где A(t) есть формула теории T и t есть терм теории T, свободный для x в
A(x).
Рассмотрим теорию EA. Пусть A(x) ≡∃b(b=x+1). Тогда ∀xA(x) ≡∀x∃b(b=x+1) –
истинная формула при стандартной интерпретации EA. Возьмем терм
t ≡ b, тогда для
терма t имеем следующую формулу ∀x∃b(b=x+1) ⊃ ∃b(b=b+1). Формула ∃b(b=b+1) ложна
при стандартной интерпретации EA, следовательно, формула ∀x A(x) ⊃A(t) – не
общезначима.
Вывод в теории EA организован таким образом, что все теоремы элементарной
арифметики
являются истинными утверждениями математики[17].
Основным средством вывода теорем в теории EA является, как и следовало
ожидать, схема индукции. Рассмотрим в качестве примера вывод формулы 0+x=x (она
отличается от аксиомы x+0=x!). Обозначим 0+x=x через A(x). Сначала мы должны
доказать A(0), т.е. 0+0
=0, но это частный случай упомянутой только что аксиомы. Теперь
можем доказать A(x)⊃A(S(x)). Предполагая воспользоваться теоремой дедукции, возьмем
A(x) в качестве гипотезы:
A(x) или 0+x=x (гипотеза),
0+S(x)=S(0+x) (частный случай аксиомы),
0+x=x ⊃ S(0+x
)=S(x) (свойство равенства),
S(0+x)=S(x) (modus ponens),
0+S(x)=S(x) или A(S(x)) (транзитивность равенства).

Страницы