5. ������� � ���������

 

5.1. �������� �����

������������ ������ ��������� ����� �������� ������������ �������� (IV �. �� �.�.): "� ���". ������� ��������� ����� ���������� ����������, �������� �� ��� ������������ �������� ��� ������. � ��� �� ����������? ���� ������������, ��� ������������ �������, ��� �������� ��, ��� ������� ����, �.�. ��� ��� ������������ �����. ���� �� ������������, ��� ������������ �������� �����, ��� �������� ��, ��� �� �� ����, �.�. ��� �� ������� ������ � ������� ��� ������������ �������.

�������� ��, ����������� ����� "� ����" ��� ������ ����� ������������ �������� ���������� (������� ��� �����). "� ���" �������� ����� �� ������������, ������ ��� ������ ��������� �� ����������, �� ��������, �� ������ � ������������. ��������� ������ ���� �������� ������� ����� ��� ��� ����� ���� ����� ���. � ����� �������, ������� ������ "������� ���������� ����", ������� ������������ �������� "��������" (� ������� ��� ������ ������ ������� �������������). � ������ �������, ������ ����� ������������� ����� ����� �� ������������ �������� (���� ��� ����������� ������ � ����������� ����� � ������ ���������� ������������, ���� ��� ����������� ���� ���������, �� ����������� ������). ��� ����� ����� ������������ ������ ��� ������ �������, ��� ��� ��� ���������� ���������� ���������, ����������� � ����������.

����� ������� ����������, ��� ������������ �������� "������� ������" (�� ����, ��������� �� ��� � ���� ��� � ������ ������������� ��������, ��������� � ������� ��� �����), ����������� ����� XIV �. ����� ������� ��������� ��������� ����� ���������: ��������� ����� p ������������, ������������ � �����:

p: p �����

����� ��� �� ����� ���� ������� ��������, ��� � ���� ���������, �� ������������ ��� ����� ���������.

��� ���, ��� ����� �� �������� ������������ �������� ������������ ��� ����������� � ������ ���� ("���������������"), �������� ����� XIV �. ������� ���������� ��������� ��������� ���������:

p1: p2 �����

p2: p1 �������

q1: q2 �����

q2: q3 �����

q3: q1 �����

����� ������ ������������ ��������� �� � ����, � � ������� ������������. � ��� �� ����� �� ���� �� ��� ������ �������� �������� ��� ������, �� ������ � ������������.

���������� 5.1. ���������, ��� ��� ������������� ���. (��������� � ���������� �� ������ ���������� � ������� ���� ��. ����� �.�.�������� [1967]. )

�� ����� ���������� "�������" �������� �����, ����� �����, ����� ����������� ������������� ������������ (������ �������� ������������� �� �������� � ������):

�) �������� ������������,

�) ������ ������������,

�) ������������, �� ������� �������� ����������.

������ ���, ������� ������ ������������

q: q ����� ��� q �� ����� �������� ����������

���� q �������,�� q �� ����� � q ����� �������� ����������. ��� ������, ��� ������������, ������������ � �����, �������� ������ ..., �� ��� � ���� q! ����������, ���� q �����, �� q �������. �������, ���� q �� ����� �������� ����������, �� q �������! ���� ������������� ������������ ����� �� �������� �������������. (��������� �������� ������� �������� ��������� ������.)

���������� 5.2. ����� ���� �������������, �� �� �������� �������� �������� ������� ���������� ������ �����������. � ���� ����� ������, ���� - �������� ����������, ��������� ���� - �������� ����������� ������. ������������� ����������� ��������� ��� �������������� ������ � �.�.

 

5.2. ����� �� �����������

���������� ������������� ������������� ���� ��������� ���������� ������ EA. ����� ������������� ������������ �������� �����, �� ������ ��������� ������� Q, "�����������" ������� �������� �� � ���, ��� "Q ����� ������������ � EA" (� ������ EA ������ ��������� ��, ��� ����� ������������ ������ �� ������). �� ��� ��������, ����� ������� ���������� � ���� �����, "�������� � ����"?

������� EA "����� ��������" ������ � ����������� ������. ����� ������� Q ����� �������� "� �������� � � ����", ��� ������� ������ ���� ������������ ������������ �������. � ���� ����� �������� ������� ��� ������� ����� EA (����� �������, ��� ���������� EA ���������� �� �������� x, a ��������� �������: x, xa, xaa,... ):

X a 0 1 + * = ( ) ~ & v -> E A

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

����� ������ ������� EA ���������� ������������������� ����������� �����, ��������, x=1 ������������ � 0,6,3. � ������� ����-������� ������ ����� ����� ������������������ ����� ������������ ����� ������������ ������� (������� ������ ������������������ �������� �� �����). ������� x=1, ��������, �������� ����� a, b �����, ���

beta(a, b, 0)=3 (����� �������),

beta(a, b, 1)=0, beta(a, b, 2)=6, beta(a, b, 3)=3.

�� �����, ��� ����� ����� a, b ����������. ���� (a, b) ����� ������������ ����� ������, ��������

c = (a+b)2 +a

���������� 5.3. �) ��������, ��� �� ����� c ������������ ����� a, b.

�) ������� ������ ��� ������� 0+1=1.

����, ������ ������� F �� ����� EA �� ����� ���������� ����� ����������� ������. ��������������� ����� ����� ���� EA ����� ���������� ����� F � �������� ��������� ������� F (� ����� �.������, ������� ������ ���� ����������� ������ �������, ����� �������� ����������� "��������" � �������� �� ����� ����������). �� ������� F �� ����� ������� �� ����� F, � �� ������ - ��������������� ���� �������.

���� ������ ��� ��������� ������� A(x) � ������ ������� B ������� ����������, ��� EA|- A(B), ����� �������: � ������ EA ��������, ��� ������� B "�������� ��������� A". ���� �� ������� ���������� -

EA|- B <-> A(B),

�� ���������: ������� B "����������", ���... ��� �������� ��������� A.

����� �� �����������. ��� ����� ������� A(x) �� ����� EA, ������� ������������ ��������� ���������� x, ����� ��������� ��������� ������� B (�� ����� EA), �����, ��� EA|- B <-> A(B).

� � � � � � � � � � � � � �. ������ ��������� ��� ���������� ������� ����������� sub(x,y). �� ��������� �������� ������� ����� �������, ���������� �� ������� � ������� x -������������ ������ ���� ��������� ���������� ����� y. ���� x - �� ����� �������, �� �������� sub(x,y) = 0 ��� ���� y.

��� ������� ��������, sub(x,y) - ���������� �������. � ����� ����, ���� x, ����� ���������, �������� �� x ������� �������. ���� ��� - �������� �������� ������� ������ ����, ���� �������� - ��������������� �� x ������y, ������� �� ��������� ���������� � ����������� ������ ��� ���� y. �������, ������� ����� ���������� �������, ������� � ����� ��������� �������. �� ����� �� �������� ��������� ��� ���������� sub(x,y), ������, �� ����� Pascal (��� ���� �� ������� ������, �� �� ����� �������). ��������� ������� �������� ��� ���������� sub(x,y) ��������� ������ ��������. ���������� � ������� ���� ����� (�������������� �������� ���� ������� �������-������ �������� ������������) �� ����� �� �����. ����� ����� �������� �� ����� �����, �������� �������� ������ �������, ���������� � ����������� ������ ����� �����, ��������� � �� ���������� ������ ��������.

����, ����� �������, ��� ������ ��������, ����������� ������� sub, ���������. ��������� ��� ������ � ������ ������������, ���������� � �������������� ������� � ��������������, ����� ��������� � ����� EA ������� SUB(x,y,z) �����, ��� ��� ���� k, m, n: ���� sub(k,m)=n, ��

�) EA|- SUB(k,m,n),

�) EA|- ~(z=n) -> ~SUB(k,m,z).

���� ������� SUB � A(x), ������, ������ �.������, ������� A1(x):

(Az)(SUB(x,x,z) -> A(z)).

�������� �������� �� ���������� ���������� x - ��� �������� ����! ��� �� "������������" �������� A1(x)? ���� ����� ������� � ������� x � ���������� ������ �� ��������� ���������� ���� x (�.�. ����� ����� �������), �� ��������� �������, ���������� ��������� A. (�� �����, ��� ������� SUB(x, y, z) ������������� ������������ z ��� ������� x, ������� ������� Az �������� ����� �� ����� ��� ����������, �������, ������, ����������, ��������� � ����� EA ��� ������������ ������� ��� ������� sub. ) ����� �������, � ������� A1(x) ���� ���� � ��������� �������� �����������, ������ ������������, ��� ��������� ����������� ����� �������� ��������� A. ���������� ��������� ��� �������� � ����� ������� A1(x). ��������� ����� n ����� ���� ������� � ��������� ���� n ������ x. ���������� ������� A1(n) ��������� ����� B. ��� �� "������������" � B?

"���� ����� ������� � ������� n (�.�. A1(x)) � ���������� ������ x �� ����� (�.�. ���� n), �� ��������� ������� (A1(n), �.�. B), ���������� ��������� A".

����, B "����������", ��� ��� �������� ��������� A! ���������� ��� ���-��� ���� �� ���� ������������.

����� ��������� �������������� ����� �� �����������, �� ������ �������� � EA, ��� ������������� B<->A(B).

1. �������, ��� EA |- B -> A(B). �������� sub(n, n) ����� ������ ������� B, �.�. �� ����������� ��������������

EA|- SUB(n, n, B), EA|- ~(z=B) -> ~SUB(n, n, z) (1)

����� ��������������� �������� ��������, ������� � �������� �������� ������� B, �.�. (Az)(SUB(n, n, z) -> A(z)). �������� (1) ����� z ����� ���� ����� ������ B, �.�. (����� ����������� �������������) �� ������� ������ A(B). �� ������� � �������� ��� ��������, ��� EA |- B -> A(B).

2. �������, ��� EA |- A(B) -> B. ���� A(B) � �������� ��������, �������� ������� SUB(n, n, B) -> A(B). � ������ (1): (Az)(SUB(n, n, z) -> A(z)), �� ��� � ���� ������� B. �� ������� �������� ������ �������, ��� EA |- A(B) -> B.

����� �� ����������� ��������.

����� �������, ��� ������ �������� ������, ������� �� ����� ���������� ���������� EA, ����� ��������� ��������� �������, "������������", ��� ��� ���� ��������� ��������.

�� ���������. � ����� ���������� ������, �������������� � 1931 �., �.������ ����������� �����������, ������� ���������� �������������� ����� �� �����������, ������ � ����� ���� �� ��� ����� �� �������������. �� ����������� ����������� ���� ����� ������������ ������� ������� �������� �.������ (��. �.����� [1965]).

���������� 5.4 (�.����������, 1961 �.). ��������, ��� ���� A(x, y), B(x, y) - ������� EA � ����� ���������� �����������, �� �������� ��������� ������� C, D, �����, ���

EA|- C<->A(C, D), EA|- D<->B(C, D).

���� �� ����� ���� A ������� ������ �� y, � B - ������ �� x, ����������, ��� C � D "������������ ���� �� �����".

 

5.3. ������� ������ � ���������

����, ����� �� ����������� ���������, ��-��������, ������������� �������� ����� ���������� EA. ����� ��� ����� ����� �����������? ������������?

�������-������ ����������� "� ���" ������ ����������: "���� ����� ������������ � EA" (������ ���������� � �������� � EA ���������� ������������ � ��������������). ����

F: "~F ��������� � EA",

��

~F: "~F ����������� � EA",

������� � ��� �� ������� �� ����� ������������� �������

F: "F ����������� � EA", (1)

��� ����� "�����������" ��������� �����. ������ ����� �������� ��������� � ���� ����� �.������, � �� �� ����� �������� ��������.

������� (1) �� ����� �� �������� �� ����� �� �����������, ���� �� ������ ���������� � ���� ������� EA �������� "������� � ������� x ����� �������� � EA".

������� ������� �� ��� "�������" � EA - ������ ������� ���������� ����������� ������ (�� �������). �������������� � ������ EA - ��� ������������������ ������, ��������������� ����������� ��������. ���� ������� ������������ �������, �� �������������� ������������ � ������������������ �����. �������� ��� ��, ��� � ������ ������, �� ����� ������������ ����� ����������� ������ ����� ������������������ ������. ��� ����� ����������� �������� ��������� ������� ������ ������������������.

����������, �� ������ ����� ����������, �������� �� �� ������� ��������������, �������������� ������ EA. � ����� ����, �� ������ ������������������ ����� ������������ ��� �������� � ��� ������� � ������� �� ������������. ����� �� ����� ���������, �������� �� ������ �� ���� ������ �������� EA (���������� ��� �����������) ��� �� ��� �������� �� ���������� ������ ������������������ � ������� ������ ������. ���� ��� ���� ������ ��� ��� - ������������� ����� ������������ ��������������. ����� ��������� ���� ������ ��������, ����������� ��� ��������� �������� ��� ������� ������������� ��������.

����� �� ������� ����� ���������� ������������ ��������� "y �������� ������� EA-�������������� ������� � ������� x". �� ������� � �������������� �������� �������, ���������� � EA ���� ��������. ��������� �� ����� PRF(x, y) (proof - ��������������).

������ ����� ��������� �������, ������� ���������� "���� ������ �������� � EA". ���� � ����� �� ����������� ������� ~(Ey)PRF(x, y) (�.�. "������� � ������� x �� ����� �������������� � EA"), ������� ��������� ������� G, �����, ���

EA|- G <-> ~(Ey)PRF(G,y). (2)

�������������, "�����������" G ������� � ���, ��� "G ����������� � EA".

���������� ������ ��������, ������� ��� ����� ��, ��� G "����������". � ����� ������ ������ EA ������� ��, ��� ��������� �� ������ EA, � ����� - ��, ��� ����������� � ������� ���� ������. -

1. �����������, ��� EA|- G. ����� ����� n - ����� �������������� ������� G. ������� PRF(x, y) �������� � EA �������� "y ���� �������������� ��� x", ������� EA |- PRF(G, n), � ����� - EA |- (Ey)PRF(G, y). ������ �������� (2) ��� ��������� ������� ������������ ~G, �.�. ��������, ��� EA |- ~G.

����, ���� ���� �������������� (���������� EA) ��� ������� G, �� �������� ����� �������������� � ��� ��������� ~G, �.�. ������ EA �������� � ����� ������ ��������������. ��, � "�� ����� ����" - G ��������� � EA? ����� �� �� �����. ���� EA ���������������, �� G ������ �������� � EA. � "�� ����� ����" - EA ���������������? ����� �� ����� �� �����.

2. ����������� ������, ��� EA|- ~G. �������� (2) - EA |- (Ey)PRF(G, y). � ����� ����������� ��������� ������� (Ey)PRF(G, y) ����������, ��� � EA ���������� �������������� ������� G. ��� ����� �� ����� ������ ��������, ��� ������ EA �������������. �� ����� �� ���������, ������, ���, ������� ���������� EA ������� -(Ey)PRF(G, y), ��, ��� �� �����, �� � ��������� ����� ���������� �������� y? �����, ��������� ������: 0,1,2,..., �� �� ������ ������������ ������� �� ����� �������������� G?

� ���������, � ��� ��� ����������� ��������� ��� ������ ����������. ���� �� ������ ����� �������������� G, �� ������ EA �������� ��������������. H� ���� �� ������? ����� ������� n �� ����� ������� EA-�������������� ������� G, �.�. ��� ������ n: EA |- ~PRF(G, n). � ������ �������, �� �����, ��� EA |- (Ey)PRF(G, y). ������������? �� ������, ��������� ������� (Ey)PRF(G, y) ������������ ������� (Ay)~PRF(G, y), �� �� �� ��� �� �������� � EA. ���, ��� �� ����� ����, ��� ����������� ����� ��������� �������������: ��� ~PRF(G, 0), ��� ~PRF(G, 1) � �.�. ����� �� �� ��������� �������� ��� ����� � ������ �������� EA-�������������� ������� (Ay)~PRF(G, y)? �� ��� ��� ��� ������ �� �������.

����, �� ������������� EA |- ~G �� �� ������ ������� ������������ � ������ EA. ��������, ��� �� ����� ����������: ���� EA|- ~G, �� �������� ������� C(y) � ����� ��������� ���������� y �����, ���

�) EA|- (Ey)C(y),

�) ��� ������� n: EA|- ~C(n).

������� C(y) �� ���� "����������" ������������ (�������������� ������� ������ � �� ����������). ������, ���� �������� ������� C(y) �������, ��� �������� ��� ��, ��� � EA "�� ��� � �������". "���������" ������ ���� ������� �������� w-�������������. (��� ������� ���� ������� �.������� � ���� �����������, �������� ����������� ����.)

���������� 5.5. ��������, ��� "���������" ������������ (�.�. ������� D �����, ��� EA|- D � ������������ EA|- ~D) �������� ����� w-������������.

���� �������� ����������

������� ������ � ��������� (��� ������ EA). ����� ��������� ��������� ������� G �� ����� EA, �����, ���

�) ���� G ��������� � EA, �� ������ EA �������������,

�) ���� ~G ��������� � EA, �� ������ EA w-�������������.

������ ���� ������� ��������� ����� ������� ��������? ������� ��������� ������������ ��������. ��������� ������� F �� ����� ������ T �������� ������������ � T, ���� �� F, �� ~F ������ �������� ���������� T (F ������������� ������ ������������ �������� "��������" ������ T, ������ ��� ������������ ������ ���������� T �� ��������, �� ������������).

������, ���������� ������������ �������, ������� �������� ��������. ������ � �������� - "������� � ���������".

�� �������, ������, ������, ��� ���� �������� ��������� ������ EA. �������������� ���������� EA ������� G ����� �������� ������..., ���� ������� ��������, ��� ������ EA w-��������������� (�.�. ��� � ��� �� ����� ��������� w-������������). �� ��� ��� �� ������ ���������� ������, ��� �������� �������������� ������ EA - ��� ������� ���� w-�������������, ���� � �� ������� ������ ������ ��������� ��������, ���������� ����������� ����� (���� ����� �������� �������� � ������� G - �������� �� ��� ���� ��������� � ���, ��� G "����������" ����������� �������������, G - ��������� ������� � ����� EA � ��� ������� �������� ������ ������������ �������� ����������� �����).

������������� ������� ������ ������� ����������������. ����� ����, �� "������" �����-�� ������ �������? ������� ����� ��, ������������ � �������� EA, � � ���������� �� �������... ����������� �������?

� ���������, ����������� �.������ �������� � ��� ������ ���������� EA. ��� �� �� �� ��������� EA, � ���������� ������ ���������� ��� �� ��������� ���������� ������ T (���� ������� ��������� � ������ EA) - �������� "y �������� ������� T-�������������� ������� � ������� x" ������ ���� ����������. (����������� "������������" �������� ������������� �������� �� ������������ ����� ���������� ���������������, - ��� ������������� ����� ���������� ������.) ������ ��������, ��� �������� ������� PRFT(x, y), ���������� � EA ���� ��������. �����, �� ����� �� ����������� ����� ����� �������� ��������� ������� GT, �����, ���

EA|- GT <-> ~(Ey)PRFT(GT, y).

T.�. ������� G "����������", ��� ��� ����������� � ������ T.

���������� 5.6. ��������, ��� ���� � ������ T ��������� ��� ������� EA, ��

�) ���� ������� GT ��������� � T, �� ��� ������ �������������,

�) ���� ~GT ��������� � T, �� ��� ������ w-�������������.

(��������: ��������� - � ����������� - �����������, ������������ ������� ������ ��� EA.)

����� �������, ������� ����� ������� �� ����� �������� � "�����������" ������� ������ ����������. ����� ������ ��������� �������� �������������� �������������� ������ ������� ������ ����������: ������ ����� ������� ��������� �������� ���� w-��������������, ���� ������������� ��� ������� ��������� �������, ���������� ������� ����������� �����.

���� ������ (Kurt Goedel) ������� 28 ������ 1906 �. � �. ���� (� �� ����� ����� ������� � ������ ������-������� � ����� ��������� �����). ������ ����������� ������� � ������� ������������ (������ ���������� � ������). ��� �� � 1930 �. ��� ���� ���������� ������ ������� ������� ���������. ���� ���������� ������� � ��������� �.������ ������� 23 ������� 1930 �. �� ��������� ����� �� ������ ������� �������� ����. ������ � ����������� ���������� ��������� � �������� 17 ������ � ����� � ���������, 1931 �. (������������ ������������ �.������ ��. � ����� �.�.���������� [1982]. �� ������ �����������, ��� ��������� �.������ ��� � ��������� ������� ������������ �.��������� � 1926 �., ��. ������ �.�.��������� [1970]. ) � 1933 �� 1938 �. �.������ ������� �������� ���������� �������� ������������. ������� � ����������-������������� �������� ������ (�.������ � ��.). ����� � 1938 �. ������ �������� �������, �.������ ����������� � ���. � 1940 �. ��������� ������� � ��������� ������ ������������ �.��������� (���� ������ �������� � �.����������). ����������� ��� ������� � 1948 �. � 1949 �. �.������ ��������� ����� ��� ������� ��������� ��������� ����� ������ ���������������, ��� ���� ������� �.���������� ��� "������ �����" � ��� ������. ���� � ��� 14 ������ 1978 �.

���������� 5.7. ������ ���� ������� � ��������� ���������� �� ���������� �������� �����������, ����������� � ������� 5.1? �������� � ������ ��������� ���������� 5.4.

������� �� w-���������������� ��������� "������" ������� �.������ � ���������. ������ ��� ������ �� ������� ������������ �� ����, ������� ��� ������� ������ �.������� � 1936 �. - � ������� ������� ������ w-���������������� ���������� "�������" ����������������.

������� ������ � ����� �������. � ����� ������ ��������������� ������ T �������� ��������� ������� RT ("����������" ��������� �������� ����������� �����), �����, ��� ���� T|- RT ��� T|- ~RT , �� ������ T �������������.

� ���� ������������ ������� ��� ���� �������� ������� � ���������, �� ������� ��������� � ������ �������. ���� ������� ������ �� ��������� ������ ��� ��� ���������� ������, ���� ������� ��������� � ������ EA, �� ������ ���� ���� � ������ T � ������������ ������. ��� ����������� ��� �� ����������, ��� �������������� �������������� ������ ������� ������ ���������� ������� � ��������� ������ ����� EA. ���� ��� ������ � ������ EA ���� ���������� ����������� ������������ ���� ������ EA, �� ������ - ��� ������ � ������������ ������ - �� ������� ������������� ������������������ EA � ���� �������. � ������� 3.2 �� ������� ����� ������ ����������������.

� � � � � � � � � � � � � �. �� ���������� 1.4 �� �����, ��� ��������������� ������ � ��������� �������� ������ ���������� ������������ ��������� ������ ����� EA. �������� ������ ��������, ������������� ��� �������:

F0 , F1 , F2 , F3 ,.. . (1)

(����� �������, T|- pi(F) ��� ���� n, ��� pi - �����������, ����������� ������� EA � ������� ������ T). ��������

"������� � ������� x ���������� � ������������ (1) ��� Ft"

�������� ����������. ����� ������� PRFT(x, t) �������� � EA ���� �������� (����� ����������� PRFT , �� ��� �� ������� ����� ��������������� ������� x). �������� ����� ��������

"��������� ������� � ������� x ���������� � ������������ ��� Ft".

�������, ���������� � EA ���� ��������, ��������� ����� REFT(x, t) (refutation - ������������).

�������� ���� �.������� �������� � ���������: ������ ������� �.������ GT, ������������: "���� ������ �������� � ������ T", ����� ������� RT , ������������:

"���� ����� ������������, ��� �������� � T".

���� ��� "����������" �������������� ������� �������� ����� �����, � ������� ��� ���������� � ������������ (1), �� ������� �.������� ����� �������� �� ����� �� �����������, ���� � �������� A(x) �������

(At)(PRF (x,t) -> (Ez<t)REF (x,z)).

��������� ��������� ������� QT �� ����� EA, �����, ���

EA|- QT <-> (At)(PRFT(QT, t) -> (Ez<t)REFT(QT, z)). (2)

�������, ��� � �������� ������� ������� RT (� ����� ������ T) ����� ����� pi(QT).

1. �����������, T|- RT . ����� ������� QT ���������� � ������������ (1), ������, ��� ������� n. ������

EA|- PRF (QT , n). (3)

��������� � ������ T ��������� ��� ������� EA (������, �� ��������), �� � ��� ��������� ����� ������� (2), (3) � �� ���������

(Ez<n)REFT(QT, z). (4)

���� ~QT ������������� ���������� � ������������ (1) ��� ������� <n, �� T|- ~RT � ������ T �������������. ���� �� ~QT �� ���������� � ������ n ������ ������������ (1), ��

EA|- ~REFT (QT, 0)&~REFT(QT, 1)& ... &~REFT(QT, n-1).

������

EA|- ~(Ez<n)REFT(QT, z).

��� �������, ��� �� ��� (4), ��������� � ������ T, ������ ��� ���� ������������ � T, ��� � �����������.

2. ����������� ������, T|- ~RT. ����� ������� ~QT ���������� � ������������ (1), ������, ��� ������� n. ������

EA|- REFT (QT, n). (5)

���� ������� Q ���������� � (1) ������ ~Q , �� T|- RT � ���������� ������������ � ������ T. ���� �� QT �� ���������� � ������ n ������ ������������ (1), ��

EA|- ~PRFT(QT, 0)&~PRFT (QT, 1)& ... &~PRFT (QT, n-1),

EA|- ~(Et<n)PRFT(QT, t). (6)

�����, �� (5) ��������, ��� - - -

EA|- (At>n)(PRFT(QT, t) -> (Ez<t)REFT(QT, z)),

��������� ��� t>n � �������� z ����� ����� n. ��������� � (6) ��� ����

EA|- (At)(PRFT(QT, t) -> (Ez<t)REFT(QT, z)).

�������� (2), ����� �������� EA|- QT � T|- RT , ��� ����� �������� ������������ � ������ T.

������� ������� ��������.

������ �� ����� �������������� ������������� �.������� "������� ��������������" � ��� ����� ������� �����: ������ ��������������� ������ ������������ - ��� ���� �������������, ���� ������������ ��� ������� ���� ����������� � ��� �������. ����������������� ������ ����� ����������� - ����������������� ������ ����� ��������� ����������� ��� ������� ���� ����������_� ��� �������. � ����� ������� "���������", ������, ������ �������� ������ ������������ ���� (��� ��������� �������������������, �.�. ������������� ������������� ����������� ������� ������������ �����).

� �������� ������� ����������������� ������ ����� ������� ���������� � ������� 3.1 ���������� �����������. � 1929 �. �.���������� ������� ������� � ������������������ ���� ������ (���������� �� EA ��������� ������� ���������). � ���� ������� ������-������� ��� ����� ���� �������� � �� �������������������.

 

5.4. ������ ������� ������

������ ��� ������� � ���������������� ������ �������������� ��������, ���������� �.�������, ���������� � ������ ����� ����� �������������� ������� �������.

����� T - ����� ��������������� ������ (�.�. ���������� ������, � ������� ����� ������������� ����������� ������� ������������ �����). �� ������ ������-������� � ����� T �������� ��������� ������� RT, ���������� � ��������� ����������� �����. ���� �� RT ������� �������� � ������ T, �� �� ������� ������ ������-������� �� ������ �� ������� � T ������������. ���� ��, � ������ �������, ������� ������� RT ������������ ���������� T, ��, �� ���� �� ������, �� �������� �� � ������ T ������������. ��� ��� ������ - ����� ���������� ������ RT � �����, ������������� ������ T-�������������� ��� T-������������ RT � T-�������������� ������������, � ���������� ����� �������������� ������� ���������� �.������ � �.������� (��� �����-���� ����������� ������).

����, ���� T - ��������������� ������, �� T ���� �������������, ���� ������������ ��� ������� ������� �� ���������� ������� RT (���������� ����������� � ��������� ����������� �����). ��������� ������, ������� ���������� �������� ���� ������������ ��������� ��������� ������� �� ������ �����, ������� �������� ��������, ������� ������-������� ����� �������������� ����� ������: ������ ��������������� ������ ���� �������������, ���� �������.

�� ������ ��� ������� �������� �������� � ���������? ���� ���������� ���� ������ ������ � ������� �� ���� ������� ������� ��� �������, ����� �� ���� ������������ ����� ����� � ������ ���������� ������ T - ���������������� ��� ��������� (�������������� ������ ��������� ����������� "������" - � ��� ��������� ����� �������). �������, ����� �������� "����� ������" ��������� ���� �� ����� ���������� ������, ����� �������� ������������������ ���� ������. �� �� ��� ����� (��. ������ 1.6), ��� � ��������������� ������������������ ������� ����������� ���������� ����� �������, ��� � ������� �������������� ���������������: ���� ������������ ������������������ ������ T, �� �� ������ ������������ ������ �������� �����������, ����� �������� �� ��������� �� ����������, ������������� � ����� T. �� ���� ���� ���� � ������ EA - � ���������� (� ����� ��������) �� ��������������� ������ ����������, �� �������� �� ��� ����� �������� �������� �����������, �� ������������ ��� � EA? ���� ���, �� �� ��������� ���������� ������������������ EA ���������� ����� �� EA (��� �����-���� "�������� ��������" ������ ���� �������). �������� �� ����� - ������ ���������� ���� ����- ������� ������������������?

����� ������� � ������� ����� �������, ������������ ��� ������� ��������, �������� � �������. � �������������� ������� ������-������� �� ��������� ��� ��������������� ������ T ������� PRFT(x, y) (�� ����� EA), ���������� � EA �������� T

"������� � ������� x ���������� � ������������

��������� pi-1(T) ��� ������� t". (1)

��������, ��� pi-1(T) - ��������� ��� ������ EA, ������� (����� �������� � ���� T) ��������� � ������ T, �������, ������� (Et)PRFT(x, t) "����������", ��� ������� EA-������� � ������� x �������� � T.

�� �����, ��� ���� ������ T �������������, �� � ��� ��������� ����� �������, � ���������, ������� ������� 0=1. � ��������, ���� ��������, ��� ������� 0=1 ���������� � T, �� �������� � ������������������ ������ T. ������� ������� ~(Et)PRFT(0=1,t) "����������", ��� ������ T ���������������. ��������� ��� ������� ����� Con(T) (consistent - �����������, ���������������).

������� Con(T) ������� �� ������ ������� PRFT. ���������, �����������, ����� ������� ����� �������, ��� ��������������� Con(T) ���������� ����� ���������� (����� �� ������� ����� �.�.����� [1957], �. 473). ����� PRFT - ����� �������, ���������� � EA �������� (1). ������ ������ ������� PRF'T(x, t), ������������ ��� ����������:

PRFT(x,t) & ~PRFT(0=1,t).

���������� 5.8. ���������, ��� ���� ������ T ��������������� (�.�. ������� ������� 0=1 ���������� � T), �� ������� PRF'T �������� (� ������ �������� ����������� �����������) � EA �������� (1).

��������������� PRF'T ����������� � ������������������ T,��������� ����� Con'(T). � ����������� ���� ��� �������

~(Et)(PRFT(0=1,t) & ~PRFT(0=1,t)).

�� ���� ��� �������������� ���� ������� ����� ���������� ���������� ������������! ���������� ������������ �������� �������� ���������������� ����� ���������� ������? ��, ��������, ���� ���� ���� ������ ������������� - ���� Con'(T) ����� ��������, �� ���� ������ � ������ T. ������� ���� ���� ����� "���������������". �� � ��� �� ������� �� ���������� "������"? � ���, ���, ��������� Con'(T), �� �� ����� ���� �� ����� ����������, ��� ��� ������� �������� ������������������ ������ T. � ���������� 5.8 �� ��������, ��� ������� PRF'T �������� �������� (1), �����������, ��� T ���������������. ����������� ������������������, ��������... �������� �� � ���� ������� Con'(T).

�� ����� ������������ ����� ������� ��� �� ���� ����: ������, �����������, ��������� ������������ (� �����-�� �� �� ���� ������) ������� Con(T), ����������� ������, ��� ��� ������� �������� �� ������������ ������� PRFT, ���������� �������� (1). ��� ����������� ������ ���� �������� � ��� ������� Con'(T), �.�. ��������� ����������� ����� ����� �������� �� �������. ���� �� ���������� �������������, ������ ���������� ����� ��� ������ �������� Con(T), ���� ����������, ����� �������� �������������� ��� ������������ ����, ��� ��������������� ������� PRFT �������� �������� (1).

�����������, ��� ���� ������� PRFT �������� "������������ �����", �.�. ����� ������������� ������ ��������, ������������� pi-1(T) (��� � �������������� ������� � ��������������), �� ��� ������������ ����, ��� ��� ������� �������� �������� (1), ���������� ������� ������ EA. ��������� � ���� � ������ ���������� �������, ���� ������������� ����� ������ ���: ���� ���� ����������� � �������� � ������� �������� ���� � ������ �������, ������� ������������� � EA.

�� ����� �������� �����, ����� �������� ��������������� ("������������") ������� Con(T) (���� ��� ������ ��������, �.�. ���� ������ T "�������������" ���������������)? �����������, ��� ��� ������� �����-�� ������� �������� Con(T). ����� ��������� ����� ������� ������? ������������� ���������� ��� ���������, ������������ ������� ���� �� �����-�� ������ �� ������������������ ������, �������� ������� � ���������. "���� ������ T ���������������, �� ������� ������ GT ����������� � T". �� ���� GT � "����������", ��� ��� ����������� � T! �.�. ���� Con(T), �� GT. ���������, Con(T)->GT.

��� ���������� ����� ���� �� ������ ��������� ��������, �� ������� ��������� � ��������. ���� ������� PRFT (������ �� ������� �������� ��� Con(T), ��� � GT) �������� "������������ �����", �� ������ �����������, ���

EA|- Con(T)->GT. (2)

��� �������������: ���� ����������� �.������ ���������� ������ ������������ �������� (�� � ���������� ���������), ������� ��� ������������� � EA.

���� ����� ����� ����� ������� �� �������� ���������� EA ������� Con(T) (�.�. ������������������ ������ T), �� � ���� (2) ������ ��������� ��, ��� EA|- GT. ��������� T - ��������������� ������, �� �� �������� �� T|- GT. ������ �� ������� ������ � ��������� �� �����, ��� ������������ GT ������ ������������ � ������ T. ����� �������, ���� EA � ��������� �������� ������������������ T ..., �� "�� ����� ����" T �������������. � ���������, ���� ������� �������� ���������� EA ������������������ ����� ������ EA, �� ��� ����� � EA ����� ������� ������������!

���� ����� �.������ (��� ������ ������� � ������������ ������, �������������� � 1931 �.) ����������, ��� ��������� ��������� (��. ������ 1.6) �� ����� ���� ����������� �� �����. ��������, ��� ��������� �������� ��� �����:

�) ���������� ���������� ������, ������������ ��� ������������ ����������,

�) �������������� ������������������ ���������� ������ (� ���� �������������� �.�������� ����������� ������������ ������ �������� �������� �����������, �� ��������� �� ������� EA).

������������� ����� �) ������� - ��������� � ������ 30-� ��. ���������� ������ �������� �������-�������� ������������� ���������� ��� ����������. ������ ���������, ������������� �� ����� �), ��������� ��������������� - ����������, ���������������� � EA, ������ �������� ���� ������������������ ����� EA, �� ������ ��� � �������������� ������������������ ���� ����������.

����� ����, ������� �.��������� ����������� ������� ������� �����������, ������� �� �������� � ��������������� ������������������? ��������� ����������� �.������ ����������, ��� ������� ����� ������� ������. � ���� ���������� �� ������� � ������������ ���� ������ �.��������� (���� ����������� ���� ������������ ������ ������� ������ ������������ �� ����� "��������� ����������", ���������� ��������� �.���������� � �.��������� [1934, 1939]).

������ ������� PRFT(x, t), ���������� �������� (1), ������ � ������������ ������� (Et)PRFT(x, t), ������� ����� ���������� ����� PRT(x). ��������, ��� PRT(x) �������� �����������, ��� ������� (pi-�����) ������� � ������� x �������� � ������ T. �������� �������� ������� ������ GT ����� ������ ����������� ���: GT - ����� �������, ���������� ���������

T |- GT <-> ~PR (GT).

������� Con(T) ���������� ����� PRT(x) ��� ~PRT(0=1), ��� 0=1 - ����� ������� 0=1.

������� ������ � ������������� ������� PRT(x) � ����� ��������, ��� ������ T "��������", ��� ������� Con(T) �������� �� ������������������, ���� ��������������� ������� PRT(x) ������������� ��������� �������� ���������: ��� ����� ������ A, B �� ����� EA

  1. ���� T |- A, �� T |- PRT(A),
  2. T |- PRT(A) -> PRT(PRT(A)),
  3. T |- PRT(A) & PRT(A->B) -> PRT(B).

�� ������� 2) ������ T "�������", ��� ������� PRT �������� ������� T-������������: ���� ����� ���������� 2) -������� � ���, ��� "���� T |- A, �� T |- PRT(A)". �� ������� 3) ������ T "�������", ��� ��������� �� (��������������) ������ �������� ������������ ������� MODUS PONENS: "���� T |-A � T |- A->B, �� T |-B".

������ ������� ������. ����� ��������������� ������ T "��������", ��� ������� Con(T) �������� �� ������������������. ����� ���� T �������������, ���� Con(T) ����������� � T.

� � � � � � � � � � � � � �. �������� ���������� (� ������ T) �������������� ������ ����� ������� ������ � ���������: ���� T|- GT, �� ������ T �������������. ������� �������, �������, ���

T |- PRT (GT) -> PRT(0=1). (3)

��� ��� T|- ~GT <->PRT(GT), �� ������ ����� ���������, ��� T|- Con(T)->GT. ������� ���� T|- Con(T), �� T|- GT, ��� ����� ������ ���������������� ������ T.

����, �������� �������� (3). ������������� �������� ��������: ������� � �������� �������� ������� PRT(GT) � ���������� ������� PRT(0=1). �� ������� 2)

T |- PRT(GT) -> PRT(PRT(GT)).

��� ����� �������� ����� ���������� PRT(PRT(GT)). ��������� ������� ������ �������� ��������� PRT(GT)->~G , �� �� ������� 1)

T |- PRT(PRT(GT)->~GT).

�� ������� 3) �����

T |- PRT(PRT(GT)) & PRT(PRT(GT)->~GT) -> PRT(~GT).

����� �������, �� ����� �������� ��������� ������� PRT(~GT). ������, ���� � ���� ���� �������� PRT(GT), �������, ��� T|- GT ->(~GT ->0=1) ("�� ������������ ������� ���, ��� ������"). �������� ������ ����������� ������ ��� ����������� � �������� 3), �������� ������� PRT(0=1), ��� � �����������. �� ������� �������� ������ ������� (3).

������ ������� ������ ��������.,

�������� ������ � ����� "��������������" ������� Con (T), ������� ����� ���� ���������� ����� � ���������� ������������. ���� �� ������� PR'T(x), ������������ ��� (Et)PRF'T(x, t), ������������� �������� ���������, �� �� ������ ������� ������ ������ ��������� ��, ��� ������ T �������������. � ����� ������ ������ ����������� ��� ��������, ��� ���� T ���������������, �� ��� "�� ��������", ��� Con (T) �������� �� ������������������. ����� �������� Con (T), �� �� �������� ��!

���� �� ������� Con(T) �������� "������������ �����", �� ������ �����������, ��� ������� ��������� ��������� (� ���� ����� ���� - ��� �������������, ������������� ������� ��������� � ���� ��������, ���������� ������� EA). �������������� ��� ����� ������ Con(T) ����������� � ���������� ������ ������� ������: ���� ������ T �������������, ���� Con(T) ������ �������� � T. ����� �������, ���� ��������� ��������������� ������ ����� �������� ���� ����������� ������������������, ��... ��� ������ �������������. ���� ����������� ��������� ����������� ������ ������� �������������� �� ������������������, ���� ����� ����� �������������� ��� ����� ��������: ��������������� ������ �� ����� ���� ���� ����������.

��, � ����������������� ������? ��� �� � ��������� ���� ��������� "������ ������" �������� ������ �����������. ���� �� ���� �� ��������� �������� ���-���� �������� ������� Con(T), ���� (� ������ ���������� �������� �����) �� ������� �� ��������� �������� ��������� � �������� ��������� (�� ����� ������������, ��� ��������, ��� ����� ������ "�� ��������" ���� ������� Con(T)).

� ��������� ������� ���� ��������������� ������ �������� �������� ������������������ ������ ("����� ������"). ���, � ������ �������� ZF ����� �������� ������������������ EA (��������� w ����������� �������, � ������� ����������� ��� ������� EA, ��. ���������� I). ������� Con(EA) ����������� � EA (���� ��� ������ ���������������), ������ ������� �� � ���� ������ �������� ����� �������� � ������� ������ ZF. ������� Con(EA) - ��������� ������� ����� EA, �.�. ������ ������������ ����������� � ��������� ����������� �����. ��� ����������� � EA �����������, �� ��� ����� �������� � ������ ��������. ��� ����� �� ������, ���������������� � ������� 3.2: ��������� ����������� � ��������� ����������� �����, ��������� ��� ����� ������������ ������ ������� ������������ ����� (�, �������� ��, ���������� ������ ���� �����), ������� ��� ������ �������������� ������� �������, �� �������������� � ����� EA (����� ������������ ������ ��. � ���������� 2).