МААТЛОГИКА

iсну¹ алгоритму, за допомогою якого для довiльно¨ формули можна сказати, що вона загальнозначуща або не загальнозначуща. Однак, для деяких спецiальних класiв формул ця задача ма¹ позитивний розв'язок. Далi ми розглянемо лише два з подiбних класiв.

а) Розв'язання проблеми вирiшення для формул у випередженiй нормальнiй формi, якi мiстять квантори загальностi, що передують кванторам iснування.

Розглянемо формулу логiки предикатiв

(8x1) : : : (8xm)(9y1) : : : (9yn)A(x1; : : : xm; y1; : : : ; yn); (3.2.2)

äå A(x1; : : : xm; y1; : : : ; yn) ¹ безкванторна формула.

Теорема 26. Формула (3.2.2) ¹ загальнозначущою тодi i тiльки тодi, коли вона загальнозначуща в полi з m елементiв.

Доведення. Нехай формула (3.2.2) ¹ загальнозначущою, тому вона загальнозначуща в довiльному полi, в тому числi, в полi з m елементiв.

Навпаки, нехай (3.2.2) загальнозначуща в m-елементному полi. Виберемо довiльне поле M потужностi бiльше, нiж m. Розглянемо формулу

(9y1) : : : (9yn)A(x1; : : : xm; y1; : : : ; yn);

(3.2.3)

äå x1; : : : ; xm вже ¹ вiльними предметними змiнними. Очевидно, формули (3.2.2) i (3.2.3) в полi M одночасно загальнозначущi або нi. Розглянемо тепер довiльне приписування

змiнним формули (3.2.3) над полем M, i нехай при цьому xi 7!ai, i = 1; : : : ; m, ai 2 M. В результатi приписування формула (3.2.3) буде мати вид:

(9y1) : : : (9yn)A(a1; : : : am; y1; : : : ; yn): (3.2.4)

Позначимо через M0 множину елементiв fa1; : : : ; amg. За умовою теореми формула (3.2.3) загальнозначуща в M0, тому i формула (3.2.4) загальнозначуща в M0. Очевидно, ùî (3.2.4) â ïîëi M рiвносильна формулi

							A(a1; : : : ; am; b1; : : : ; bn);		(3.2.5)
	(b1	;:::;b )		2		Mn
			_n
яку ми можемо переписати у виглядi:								_
_2	; : : : ; am; b1; : : : ; bn) _								(3.2.6)
A(a1								A(a1; : : : ; am; b1; : : : ; bn):
(b1;:::;bn) M0n								(b1;:::;bn)2MnnM0n
Але оскiльки (3.2.4) загальнозначуща в M0, то, очевидно, формула
							A(a1; : : : ; am; b1; : : : ; bn)
	(b1		;:::;b )		2		Mn
			_n				0

ма¹ значення "iстина", тому вся формула (3.2.6) iстинна. Ми показали, що формула (3.2.2) прийма¹ значення "iстина" при довiльному приписуваннi над полем M. Îòæå,

формула (3.2.2) загальнозначуща. ¤

51

(Qx1)(Qx2) : : : (Qxm)A(P1; : : : ; Pn; x1; : : : ; xm);

б) Проблема вирiшення для формул з одномiсними предикатами.

Теорема 27. Формула логiки предикатiв, яка мiстить n рiзних одномiсних

предикатних змiнних, загальнозначуща тодi i тiльки тодi, коли вона загальнозначуща в полi, що мiстить 2n елементiв.

Доведення. Необхiднiсть теореми очевидна, тому зупинимось лише на доведеннi достатностi. Отже, розглянемо формулу логiки предикатiв у випередженiй нормальнiй формi

(3.2.7)

äå (Qxi) ¹ àáî (8xi), àáî (9xi), i = 1; : : : ; m, а формула A(P1; : : : ; Pn; x1; : : : ; xm) кванторiв не мiстить, де P1; : : : ; Pn одномiснi предикатнi змiннi, а x1; : : : ; xn предметнi змiннi,

що входять в них. Оскiльки кожна предметна змiнна xi		(i = 1; : : : ; n) входить
хоч б в один з предикатiв P1; : : : ; Pn,	то очевидно, що m	6 n, òîìó ìè çàìiñòü
A(P1; : : : ; Pn; x1; : : : ; xm) iнколи будемо	писати A(P1(xi1 ); : : : ; Pn(xin )) äå i1; : : : ; in 2
f1; : : : ; mg.		n елементiв, i покажемо,
Припустимо, що формула (3.2.7) загальнозначуща в полi з 2

що вона загальнозначуща в довiльному полi з бiльшим, нiж 2n, числом елементiв. Нехай D ¹ äîâiëüíå ïîëå òàêå, ùî jDj > 2n. Розглянемо над цим полем довiльне приписування

f формули (3.2.7). Припустимо, що при цьому f: xk 7!ak, k = 1; : : : ; m, f: Pl 7!¸l, l = 1; : : : ; n. Визначимо на D вiдношення еквiвалентностi " таким чином:

df

d1 ´ d2(") Ã! ¸1(d1) = ¸1(d2) ^ ¸2(d1) = ¸2(d2) ^ : : : ^ ¸n(d1) = ¸n(d2):

Нехай ®¹ = (®1; : : : ; ®n) ¹ деякий двiйковий набiр. Поставимо йому у вiдповiднiсть пiдмножину H®¹, яка визнача¹ться умовою:

df

d 2 H®¹ Ã! ¸1(d) = ®1 ^ ¸2(d) = ®2 ^ : : : ^ ¸n(d) = ®n;

¹

äå d 2 D. Очевидно, що d 2 H(¸1(d);:::;¸n(d)) для кожного d 2 D. Äàëi, ÿêùî ®¹ 6= ¯,

òî H®¹ \ H¹ = ?. Отже, сiм'я пiдмножин (H®¹ )i=1;:::;2n утворю¹ розбиття множини D.

¯ i

Причому, якщо d1; d2 2 H®¹, то, очевидно, d1 ´ d2("). Таким чином, D=" = (H®¹i )i=1;:::;2n . Îòæå, ïîëå D=" ì๠2n елементiв. Через [ d ] позначимо "-клас, який мiстить елемент d.

Розглянемо над полем D=" приписування f0, яке визнача¹ться таким чином:

f0:	xk 7![ak]; k = 1; : : : ; m;
(	Pl	¸0l; l = 1; : : : ; n;
		7!

äå ¸0	df
	([ d ]) =
l

приписуваннях

¸l(d). Покажемо тепер, що формула A(P1; : : : ; Pn; x1; : : : ; xm) â f i f0 приймають однаковi iстинностнi значення. Справдi,

A(¸01(xi1 ); : : : ; ¸0n(xin ); [ a1]; : : : ; [ am]) ´

´ A(¸01(ai1 ); : : : ; ¸0n(ain )) = A(¸1(ai1 ); : : : ; ¸n(ain )) ´

´ A(¸1(xi1 ); : : : ; ¸n(xin ); a1; : : : ; am):

52

d1; d2; : : : ; d2n . Таким

(8xm)A(P1; : : : ; Pn; x1; : : : ; xm¡1; xm):

Покажемо тепер, що формула

(Qxm)A(P1; : : : ; Pn; x1; : : : ; xm¡1; xm);

(3.2.8)

äå (Qxm) ¹ (8xm) àáî (9xm), при приписуваннях f i f0 також прийма¹ однаковi iстинностнi значення. Припустимо конкретно, що (Qxm) ¹ (8xm), тодi формула (3.2.8)

набува¹ вигляду:

(3.2.9)

Не втрачаючи загальностi, припустимо далi, що Pn = Pn(xm). Виберемо потiм по одному представнику з кожного "-класу i позначимо ¨х вiдповiдно через

чином, будемо мати D=" = f[ d1]; [ d2]; : : : ; [ d2n ]g. Äàëi ìà¹ìî:

(8xm 2 D=")A(¸01(xi1 ); : : : ; ¸0n¡1(xin¡1 ); ¸0n(xm); [ a1]; : : : ; [ am¡1]; xm) ´ ´ (8xm 2 D=")A(¸01([ ai1 ]); : : : ; ¸0n¡1([ ain¡1 ]); ¸0n(xm)) ´

	2n	¡1([ ain¡1 ]); ¸n0 ([dk])) ´
´	^ A(¸10([ ai1 ]); : : : ; ¸n0
	k=1
	2n
´	^ ^		¡1([ ain¡1 ]); ¸n0 ([d])) ´
	A(¸10([ ai1 ]); : : : ; ¸n0

k=1 d2[dk]

^2n ^

´A(¸1(ai1 ); : : : ; ¸n¡1(ain¡1 ); ¸n(d)) ´

k=1 d2[dk]

^

´A(¸1(ai1 ); : : : ; ¸n¡1(ain¡1 ); ¸n(d)) ´

d2D

´ (8xm 2 D)A(¸1(ai1 ); : : : ; ¸n¡1(ain¡1 ); ¸n(xm)) ´

´ (8xm 2 D)A(¸1(xi1 ); : : : ; ¸n¡1(xin¡1 ); ¸n(xm); a1; : : : ; am¡1; xm):

Отже, формула (3.2.9) при приписуваннях f i f0 приймають однаковi iстинностнi

значення.

ßêùî æ (Qxm) ¹ (9xm), то аналогiчне твердження також справедливе, що

перевiря¹ться подiбними мiркуваннями. Мiркуючи таким же чином i далi, ми в результатi покажемо, що формула (3.2.7) при приписуваннях f i f0 прийма¹ однаковi

iстинностнi значення. Враховуючи тепер, зо (3.2.7) загальнозначуща за умовою теореми в полi D=", оскiльки воно мiстить 2n елементiв, робимо висновок, що формула

(3.2.7) при приписуваннi f0 прийма¹ значення "iстина", тому вона також i при приписуваннi f набува¹ значення "iстина". В силу довiльностi вибору приписування f над полем D, робимо висновок, що формула (3.2.7) прийма¹ значення "iстина"при

довiльному приписуваннi над цим же полем, тобто вона буде загальнозначущою в
ïîëi D. Îñêiëüêè ïîëå D вибиралось також довiльно, лише б jDj	n, òîìi (3.2.7)
	n>, à2тому формула
загальнозначуща у всякому полi з числом елементiв бiльшим, нiж 2	¤
(3.2.7) загальнозначуща, що i треба було довести.
Приклад. Довести, що формула
(8x)P (x) _ (8x)Q(x) ¡! (8x)(P (x) _ Q(x))	(3.2.10)

53

якi називаються посилками, тодi i тiльки тодi, коли формула ¹ загальнозначущою, тобто

предикатiв вважа¹ться логiчним наслiдком формул логiки предикатiв

загальнозначуща.

Справдi, формула (3.2.10) буде загальнозначущою тодi i тiльки тодi, коли вона, згiдно теореми 27, буде загальнозначуща в полi з 22 = 4 (чотирьох) елементiв,

оскiльки вона мiстить двi предикатнi одномiснi змiннi. Розглянемо поле D = fa; b; c; dg i запишемо формулу (3.2.10) над ним у виглядi:

P (a)P (b)P (c)P (d) _ Q(a)Q(b)Q(c)Q(d) ¡!

¡! (P (a) _ Q(a))(P (b) _ Q(b))(P (c) _ Q(c))(P (d) _ Q(d)):

Припустимо, що P; Q ¹ логiчнi функцi¨ при довiльному приписуваннi над D i записана формула хибна. Тодi

jP (a)P (b)P (c)P (d) _ Q(a)Q(b)Q(c)Q(d)j = 1;

j(P (a) _ Q(a))(P (b) _ Q(b))(P (c) _ Q(c))(P (d) _ Q(d))j = 0:

Нехай P (a) _ Q(a) ¹ "õèáà", òîäi jP (a)j = 0 i jQ(a)j = 0. Òîìó jP (a)P (b)P (c)P (d)j = 0 i

jQ(a)Q(b)Q(c)Q(d)j = 0, îòæå, jP (a)P (b)P (c)P (d)_Q(a)Q(b)Q(c)Q(d)j = 0. Ми отримали

протирiччя, яке говорить про те, що наше припущення було невiрним. Таким чином, формула (3.2.10) загальнозначуща в полi D, тому згiдно теореми вона загальнозначуща.

4. Покажемо на прикладах як логiка предикатiв використову¹ться для записування математичних означень та тверджень.

Приклад 1. Нехай змiннi x; y; z приймають значення з множини R дiйсних чисел. Записати символiчно: "Для кожного дiйсного числа x iñíó¹ òàêå y, що для кожного z, ÿêùî ñóìà z i 1 менше y, òî ñóìà x i 2 менше 4".

(8x)(9y)(8z)(z + 1 < y ¡! x + 2 < 4):

Приклад 2. Означення границi послiдовностi:

df

a = lim xn Ã! (8" > 0)(9n0 2 N)(8n 2 N)(n > n0 ¡! jxn ¡ aj < "):

n!1

Приклад 3. Означення границi функцi¨ в точцi:

df

A = lim f(x) Ã! (8" > 0)(9± > 0)(8x)(jx ¡ aj < ± ¡! jf(x) ¡ Aj < "):

x!a

В логiцi предикатiв поняття логiчного наслiдку вводиться таким же самими чином, як це було зроблено в свiй час в логiцi висловлень, а саме, формула B ëîãiêè

A1; A2; : : : ; An, A1 ^A2 ^: : :^An ¡! B

A1; A2; : : : ; An j= B òîäi i òiëüêè òîäi, êîëè j= A1 ^ A2 ^ : : : ^ An ¡! B:

Приклад 4. Деякi хiмiки велосипедисти. Жоден фiлософ не ¹ хiмiком. Отже, деякi велосипедисти не ¹ фiлософами. Чи буде правильним таке мiркування з логiчно¨ точки зору?

54

Розв'язування. Введемо такi позначення: X(x) "x ¹ õiìiê", B(x) "x ¹ велосипедист", ©(x) "x ¹ фiлософ". Тодi умова задачi в символiчнiй формi запишеться

òàê:	(9x)(X(x) ^ B(x)); (8x)(©(x) ¡!» X(x)) j= (9x)(B(x)^ » ©(x))
або таким чином		1: (9x)(X(x) ^ B(x));
		2: (8x)(©(x) ¡!» X(x))
		) (9x)(B(x)^ » ©(x))
Розглянемо формулу логiки предикатiв
	(9x)(X(x) ^ B(x)) ^ (8x)(©(x) ¡!» X(x)) ¡! (9x)(B(x)^ » ©(x))			(3.2.11)

i перевiримо чи буде вона загальнозначущою. Припустимо, що ця формула не ¹ загальнозначущою. Це означа¹, що iсну¹ таке поле D, а на ньому знайдеться таке

приписування ': X(x) 7!X¤(x); B(x) 7!B¤(x); ©(x) 7!©¤(x), при якому формула (3.2.11) ¹ хибною, тобто

j(9x)(X¤(x) ^ B¤(x)) ^ (8x)(©¤(x) ¡!» X¤(x)) ¡! (9x)(B¤(x)^ » ©¤(x))j = 0: (3.2.12)

Умова (3.2.12) означа¹, що ма¹ мiсце наступна система умов:

j(9x)(X¤(x) ^ B¤(x))j = 1;	(3.2.13)
j(8x)(©¤(x) ¡!» X¤(x))j = 1;	(3.2.14)
j(9x)(B¤(x)^ » ©¤(x))j = 0:	(3.2.15)

Рiвнiсть (3.2.13) означа¹, що iсну¹ таке x0 2 D, при якому jX¤(x0) ^ B¤(x0)j = 1, тобто jX¤(x0)j = 1 i jB¤(x0))j = 1. Умова (3.2.14) означа¹, що для кожного x 2 D ì๠ìiñöå j©¤(x) ¡!» X¤(x)j = 1, звiдки виплива¹, що j©¤(x0) ¡!» X¤(x0)j = 1. Îñêiëüêè j » X¤(x0)j = 0, то очевидно j©¤(x0)j = 0, що виплива¹ з означення iмплiкацi¨. Рiвнiсть (3.2.15) означа¹, що для всiх x 2 D викону¹ться jB¤(x)^ » ©¤(x)j = 0, òîìó

jB¤(x0)^ » ©¤(x0)j = 0. Îñêiëüêè j » ©¤(x0)j = 1, очевидно, jB¤(x0))j = 0. Отримане

протирiччя говорить про те, що наше припущення ¹ невiрним. Отже, формула (3.2.11) ¹ загальнозначущою, що означа¹ правильнiсть мiркування з логiчно¨ точки зору. ¤

55

4 Математичнi теорi¨ першого порядку

4.1 Означення теорi¨ першого порядку. Числення предикатiв

Мова першого порядку. Терми i формули. Логiчнi та спецiальнi аксiоми. Правила виведення. Приклади математичних теорiй. Доведення в теорi¨ першого порядку. Теорема дедукцi¨.

1. Аксiоматичний метод, який, мабуть, був лишньою розкiшшю при вивченнi логiки висловлень, ¹ необхiдним при вивченнi логiки предикатiв, що поясню¹ться в першу чергу вiдсутнiстю алгоритму, за допомогою якого можна було б розпiзнавати загальнозначущi формули. Таким чином, ми приходимо до розглядання теорiй першого порядку (або, iнакше, елементарних теорiй). Вiдмiтимо, що в елементарних теорiях квантори можуть навiшуватись тiльки на предметнi змiннi, i, нi в якому разi, на предикатнi змiннi, а також не дозволяються предикати, якi мають в якостi можливих значень сво¨х аргументiв iншi предикати та функцi¨.

Символами кожно¨ теорi¨ K першого порядку служать: логiчнi зв'язки », ¡!; знаки пунктуацi¨ (, ), ;; непорожня, скiнченна бо зчисленна, множина предикатних

çìiííèõ Anj (n > 0, j > 1); скiнченна (можливо, i порожня) або зчисленна множина функцiональних змiнних fjn (n; j > 1); i, нарештi, скiнченна (можливо, порожня) або

зчисленна множина предметних констант ai (i > 1); 8 квантор загальностi. Верхнiй

iндекс предикатно¨ або функцiонально¨ змiнно¨ вказу¹ число аргументiв, а нижнiй iндекс служить щоб розрiзняти лiтери з одним i тим же числом аргументiв.

Функцiональнi змiннi, що застосовуються до предметних змiнних i констант, породжують терми. А саме,

(a)кожна предметна змiнна або предметна константа ¹ терм;

(b)ÿêùî fin функцiональна змiнна, а t1; : : : ; tn терми, то fin(t1; : : : ; tn) ¹ òåðì;

(c)вираз ¹ термом тiльки у тому випадку, коли вiн виплива¹ з правил (a) i (b).

Предикатнi змiннi, застосованi до термiв, породжують елементарнi формули,
àáî òî÷íiøå: ÿêùî Ain предикатна змiнна, а	t1; : : : ; tn терми, то Ain(t1; : : : ; tn)
елементарна формула.
Формули визначаються таким чином:

(a)кожна елементарна формула ¹ формула;

(b)ÿêùî A i B формули i y предметна змiнна, то кожний з виразiв (» A),

(A ¡! B) i ((8y)A) ¹ формула;

(c) вираз ¹ формулою тiльки в тому разi, коли вiн виплива¹ з правил (a) i (b).

Звiсно, у випадку кожно¨ конкретно¨ теорi¨ K в побудовi термiв i формул беруть участь тiльки тi символи, якi належать теорi¨ K.

Òåðì t назива¹ться вiльним для предметно¨ змiнно¨ xi у формулi A, якщо жодне

вiльне входження xi â A не знаходиться в областi дi¨	жодного		квантора	8xj, äå
	2	(x1; x3)
xj предметна змiнна, що входить в t. Наприклад, терм f1			вiльний для x1 â

(8x2)A21(x1; x2) ¡! A11(x1), але не вiльний для x1 â (9x3)(8x2)A21(x1; x2) ¡! A11(x1).

56

òåîði¨ K, наступнi формули ¹

t òåðì òåîði¨ K, вiльний для

Àêñiîìè òåîði¨ K розбиваються на два класи: логiчнi аксiоми i власнi (або нелогiчнi)

àêñiîìè.

Логiчнi аксiоми: якi б не були формули A, B i C логiчними аксiомами теорi¨ K:

(1) A ¡! (B ¡! A);

(2) (A ¡! (B ¡! C)) ¡! ((A ¡! B) ¡! (A ¡! C));

(3) (» B ¡!» A) ¡! ((» B ¡! A) ¡! B)

(4) (8xi)A(xi) ¡! A(t), äå A(xi) ¹ формула теорi¨ K i

xi â A(xi).

(5) (8xi)(A ¡! B) ¡! (A ¡! (8xi)B), якщо формула A не мiстить вiльних входжень предметно¨ змiнно¨ xi.

Власнi аксiоми: вони не можуть бути сформульованi в загальному випадку, оскiльки змiнюються вiд теорi¨ до теорi¨. Теорiя першого порядку, яка не мiстить власних аксiом, назива¹ться численням предикатiв першого порядку.

Правилами виведення в кожнiй теорi¨ першого порядку ¹:

(a)Modus ponens: ç A i A ¡! B виплива¹ B. (Скорочене позначення МР)

(b)Правило узагальнення: з A виплива¹ (8xi)A. (Скорочене позначення Gen)

2.Приклад 1. Теорiя часткового порядку. Нехай K мiстить одну предикатну змiнну

A21 i не мiстить функцiональних змiнних та предметних констант. Замiсть A21(x1; x2) i » A21(x1; x2) будемо вiдповiдно писати x1 < x2 i x1 x2. Нехай, нарештi, K мiстить двi власнi аксiоми:

(a)	(8x1)(x1 x1) (iррефлексивнiсть);
(b)	(8x1)(8x2)(8x3)(x1 < x2 ^ x2 < x3 ¡! x1 < x3) (транзитивнiсть).

Âiäìiòèìî, ùî ^; _ i Ã! визначаються через »; ¡! точно так, як в численнi висловлень, i (9x)A означа¹ » (8x) » A.

Приклад 2. Теорiя груп. Нехай K ма¹ одну предикатну змiнну A12						, îäíó
функцiональну змiнну f2	i одну предметну константу	a1	. Çàìiñòü A2	(t; s), f2	(t; s), a1
1			1	1

будемо писати вiдповiдно t = s, ts, e. Власними аксiомами теорi¨ K ¹ формули:

(a) (8x1)(8x2)(8x3)(x1(x2x3) = (x1x2)x3); (асоцiативнiсть)

(b) (8x1)(ex1 = x1); (e лiва одиниця)

(c) (8x1)(9x2)(x2x1 = e); (iснування лiвого оберненого елемента)

(d) (8x1)(x1 = x1); (рефлексивнiсть рiвностi)

(e) (8x1)(8x2)(x1 = x2 ¡! x2 = x1); (симетричнiсть рiвностi)

57

(f) (8x1)(8x2)(8x3)(x1 = x2 ¡! (x2 = x3 ¡! x1 = x3));(транзитивнiсть рiвностi)

(g) (8x1)(8x2)(8x3)(x2 = x3 ¡! (x1x2 = x1x3 ^ x2x1 = x3x1)). (пiдстановочнiсть рiвностi)

3. Вiдмiтимо, перш за все, що поняття доведення, вивiдностi з гiпотез залишаються такими ж для теорiй першого порядку, якими ми ¨х давали для довiльних формальних теорiй.

Теорема дедукцi¨, яка доведена в численнi висловлень, не може бути чисто механiчно без вiдповiдно¨ модифiкацi¨ перенесена в теорiю першого порядку K. Наприклад, згiдно

вивiдностi з гiпотез ма¹ мiсце в теорi¨ K твердження A `K (8x1)A äëÿ äîâiëüíî¨

формули A цi¹¨ теорi¨. Однак не завжди `K A ¡! (8x1)A. Справдi, розглянемо поле D = fa; bg i нехай A ¹ A11(x1). Розглянемо над полем D приписування f: A11 7!¸, äå ¸(a) = 1 i ¸(b) = 0, f: x1 7!a. При такому приписуваннi ма¹мо j¸(a)j = 1, j(8x1)¸(x1)j =

0, òîìó j¸(a) ¡! (8x1)¸(x1)j = 0. Ми показали, що формула A11(x1) ¡! (8x1)¸(x1) не ¹ загальнозначущою. Однак деяка послаблена форма теореми дедукцi¨ у випадку теорiй першого порядку може бути доведена.

Нехай A деяка формула, що належить множинi гiпотез ¡, i нехай B1; : : : ; Bn який-небудь вивiд з ¡, надiлений об рунтуванням кожного кроку у ньому. Ми будемо

казати, що Bi залежить вiд A у цьому виведеннi, якщо

(1) Bi ¹ A i об рунтуванням Bi слугу¹ належнiсть Bi äî ¡; àáî

(2) Bi об рунтоване як безпосереднiй наслiдок згiдно МР або Gen деяких попереднiх у цьому виведеннi формул, з яких принаймнi одна залежить вiд A.

Ëåìà 12. Якщо формула A теорi¨ першого порядку K ¹ частинний випадок

тавтологi¨, то A ¹ теорема K i може бути виведена iз застосуванням одних тiльки схем аксiом (1) (3) i правила modus ponens.

Доведення. Нехай A отримана з деяко¨ тавтологi¨ W за допомогою пiдстановок. Тодi, очевидно, iсну¹ вивiд W в численнi висловлень L. Зробимо тепер всюди в цьому

виведеннi пiдстановки за правилом: (a) якщо яка-небудь логiчна змiнна входить в W , òî

на мiсця всiх ¨¨ входжень в кожну формулу виведення пiдставля¹мо ту формулу теорi¨ K, яка пiдставлялася в W на мiсця входжень тi¹¨ ж лiтери при побудовi A; (b) ÿêùî

дана логiчна змiнна не входить в W , то на мiсця всiх ¨¨ входжень у формули виведення пiдставля¹мо довiльну формулу теорi¨ K. Отримана таким чином послiдовнiсть формул i буде виведенням формули A â K, причому виведенням, який використову¹ лише схеми

àêñiîì (1) (3) i ÌÐ.	¤
Ëåìà 13. ßêùî B не залежить вiд A у виведеннi ¡; A ` B, òî ¡ ` B.
Доведення. Нехай B1; : : : ; Bn(= B) виведення B ç ¡ i A, в якому	B íå

залежить вiд A. Вiзьмемо за iндуктивне припущення, що твердження, яке доводиться, справедливе для всiх виведень, довжина яких менше n. ßêùî B належить ¡ àáî ¹ àêñiîìà, òî ¡ ` B. ßêùî B ¹ безпосереднiм наслiдком яких-небудь попереднiх формул, то, оскiльки B не залежить вiд A, то не залежить вiд A жодна з цих формул. Отже, згiдно iндуктивного припущення, з ¡ виводяться цi формули, а разом з ними i B. ¤

58

Теорема 28 (Метатеорема дедукцi¨). Нехай ¡; A ` B, i при цьому нехай iсну¹ таке виведення B ç f¡; Ag, в якому при жодному застосуваннi правила узагальнення до формул, що залежать у цьому виведеннi вiд A, не зв'язу¹ться квантором жодна вiльна змiнна формули A. Òîäi ¡ ` A ¡! B.

Доведення. Нехай B1; : : : ; Bn(= B) виведення B ç f¡; Ag, що задовольня¹ умову теореми. Доведемо iндукцi¹ю, що ¡ ` A ¡! Bi для кожного i 6 n. ßêùî Bi ¹ àêñiîìà або належить ¡, òî ¡ ` A ¡! Bi, îñêiëüêè A ¡! Bi виплива¹ згiдно МР з Bi i àêñiîìè Bi ¡! (A ¡! Bi). ßêùî Bi спiвпада¹ з A, òî ¡ ` A ¡! Bi â ñèëó òîãî, ùî ` A ¡! A (лема 9). Якщо iснують j; k < i òàêi, ùî Bk ¹ Bj ¡! Bi, то, згiдно iндуктивному припущенню, ¡ ` A ¡! Bj i ¡ ` A ¡! (Bj ¡! Bi). Отже, за схемою аксiом (2) i МР ма¹мо ¡ ` A ¡! Bi. Нехай, нарештi, iсну¹ j < i òàêå, ùî Bi ¹ (8xk)Bj. За припущенням ¡ ` A ¡! Bj, i àáî Bj не залежить вiд A, àáî xk не ¹ вiльною предметною змiнною формули A. ßêùî Bj не залежить вiд A, òî â ñèëó ëåìè 13 ìà¹ìî ¡ ` Bj, i òîäi застосовуючи правило Gen, отриму¹мо ¡ ` (8xk)Bj, тобто ¡ ` Bi. За схемою аксiом (1) ìà¹ìî ` Bi ¡! (A ¡! Bi), звiдки за МР отриму¹мо ¡ ` A ¡! Bi.

ßêùî xk не ¹ вiльною предметною змiнною формули A, то за схемою аксiом (5) ма¹мо ` (8xk)(A ¡! Bj) ¡! (A ¡! (8xk)Bj). Îñêiëüêè ¡ ` Bj, то за правилом Gen отриму¹мо ¡ ` (8xk)(A ¡! Bj). Тому за допомогою правила modus ponens ми виводимо ¡ ` A ¡! (8xk)Bj, тобто ¡ ` A ¡! Bi. Цим i завершу¹ться iндукцiя. Покладаючи тепер i = n ми отриму¹мо твердження теореми ¡ ` A ¡! B. ¤

Íàñëiäîê 12. ßêùî ¡; A ` B i iсну¹ виведення, побудоване без використання правила узагальнення до вiльних предметних змiнних формули A, òî ¡ ` A ¡! B.

Íàñëiäîê 13. Якщо формула A замкнена13 i ¡; A ` B, òî ¡ ` A ¡! B.

13 Формула логiки предикатiв назива¹ться замкненою, якщо вона нема¹ вiльних предметних змiнних.

59

i = 1; 2; : : :

4.2 Несуперечнiсть i повнота числення предикатiв

Теорема про несуперечнiсть числення предикатiв першого порядку. Iнтерпретацi¨. Виконуванiсть та iстиннiсть. Моделi. Iзоморфiзм моделей i категоричнiсть. Повнота числення предикатiв першого порядку.

1. Ма¹ мiсце теорема про несуперечливiсть числення предикатiв.

Теорема 29. Числення предикатiв першого порядку ¹ несуперечлива теорiя.

Доведення. Для довiльно¨ формули A позначимо через h(A) вираз, який отриму¹ться в результатi витирання в A всiх кванторiв i термiв разом з вiдповiдними

дужками й комами. По сутi h(A) ¹ формулою числення				висловлень, в якiй
ðîëü	ëîãi÷íèõ	çìiííèõ	грають символи Ajk. Очевидно, що	h(» A) =» h(A)
i h(A	¡! B)	= h(A)	¡! h(B). Для кожно¨ аксiоми A,	яка отриму¹ться за

якою-небудь схемою аксiом (1) (5), h(A) ¹ тавтологi¹ю. Це очевидно для (1)(3). Кожний частинний випадок (8xi)A(xi) ¡! A(t) схеми (4) перетворю¹ться

операцi¹ю h â	тавтологiю виду B	¡! B, а кожний частинний випадок
(8xi)(A ¡! B)	¡! (A ¡! (8xi)B)	схеми (5) перетворю¹ться в тавтологiю виду

(D ¡! E) ¡! (D ¡! E). Нарештi, якщо h(A) i h(A ¡! B) тавтологi¨, то i h(B)

тавтологiя, i якщо h(A) тавтологiя, то i h((8xi)A) тавтологiя, оскiльки результати застосування операцi¨ h äî A i (8xi)A спiвпадають. Отже, якщо A ¹ теорема в численнi предикатiв, то h(A) ¹ тавтологiя. Якби iснувала формула B числення предикатiв така,

ùî ` B i `» B, то обидва вирази h(B) i h(» B) були б тавтологiями, що неможливо. Таким чином, числення предикатiв першого порядку несуперечливе. ¤

2. Формули теорi¨ першого порядку мають змiст, коли iсну¹ яка-небудь iнтерпретацiя символiв, що входять у не¨. Пiд iнтерпретацi¹ю ми будемо розумiти кожну систему, яка склада¹ться з непорожньо¨ множини D, що назива¹ться областю iнтерпретацi¨

(або полем), i деяко¨ вiдповiдностi, яка кожнiй предикатнiй змiннiй Anj припису¹ деяке n-мiсне вiдношення в D, кожнiй функцiональнiй змiннiй fjn деяку n-арну операцiю

â D i кожнiй предметнiй сталiй ai деякий елемент з D. При заданiй iнтерпретацi¨ предметнi змiннi розумiються пробiгаючими область D цi¹¨ iнтепретацi¨, а зв'язкам i

кванторам нада¹ться ¨х звичайний змiст.

При данiй iнтерпретацi¨ кожна формула без вiльних предметних змiнних (або, iнакше замкнена формула) явля¹ собою висловлення, яке iстинне або хибне, а кожна формула з вiльними предметними змiнними визнача¹ деяке вiдношення на областi iнтепретацi¨; це вiдношення може бути виконане (iстинне) для одних значень змiнних iз областi iнтерпретацi¨ i не виконане (хибне) для iнших.

Нехай задана деяка iнтерпретацiя з областю D, i нехай § ¹ множина всiх зчисленних послiдовностей елементiв з D. Будемо казати, що формула A викону¹ться

на послiдовностi s = (b1; b2; : : :) ç § при данiй iнтерпретацi¨, якщо для кожного пiдстановка bi на мiсця всiх вiльних входжень xi â A призводить до iстинного в данiй iнтерпретацi¨ твердження. Формула A назива¹ться iстинною в данiй

iнтерпретацi¨ тодi i тiльки тодi, коли вона викону¹ться на кожнiй послiдовностi з §. Формула A назива¹ться хибною в данiй iнтерпретацi¨, якщо вона не викону¹ться на жоднiй послiдовностi з §.

60