3. ������������ ����������

3.1. �� ������ ����� �� ������ ������������ ����������

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

����, �� ����� ������� ���������� ������ EA, �������� ��������� ���������� ������� ����� ��������� {0,1,2,3,...}.

� 1880-� ��. �.�������� � ��.����� �������������� ������� ����������, ��������� ������������ ��������� 0 (����) � �������������� ������ S (������� ����������: S(x)=x+1):

P1) (Ax)~(0=Sx) (���� �� ������� �� �� ����� ������),

P2) (AxAy)(x<>y -> Sx<>Sy) (������������� ������� ����������),

P3) ���� F - ����� "��������" ����������� �����, ��

F(0) & (Ax)(F(x)->F(Sx)) -> (Ax)F(x)

(������� �������������� ��������).

���� �� �� ���������� ����������� ���������� ����������� ����� � ������ �������� ZF (��. ������ 2.3), �� ����� �� ���������� 0 ��� ������ ���������, Sx - ��� xU{x} �, ���� �� ������ ��������� w, ����� �� �������� ������� ����� ��� ������� ZF. ������ �������� F ������������ �� ����� ������������ ������������ w:

(Az)(z<=w & 0 in z & (Ax)(x in z -> xU{x} in z) -> z=w).

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

���� ����� �� �������� (��� ��.�����) ������ ��������� 0 � �������������� ������ S, �� ������� ����� ������ EA (��� ������� �������� ����� ������ EA0) ������������ ����� ������:

�) ��������� 0 � ����� ���������� - ���� EA0,

�) ���� t - ����, �� St - ����� ���� EA0.

����� �������, ������� ������ ��� ���� ������: SS... S0 (����������� ���������� ����������� �����) � SS... Sx (����������� ������� ���� x+n, ��� n - ���������� ����������� �����). ������������� ��������� EA0 ����� ������� ������ ��������� (t1 =t2 ), ��� t1, t2 - ����� EA (����� �������, EA0 �� ����� ����������� ����������� ��������). �� ������������ ������ � ������� ���������� ������ ~, &,V,-> � ��������� A, E �������� ����� ������� ������� EA0. � �������� ������ EA0 ����������� ������� P1,P2, � ������ P3 - ����� ������:

B(0) & (Ax)(B(x) -> B(Sx)) -> (Ax)B(x),

��� B(x) - ������� �� ����� EA0 � ����� ���������� ��������� ���������� x. ����� x ������� B ����� ��������� � ������ ��������� ���������� (���������).

������ EA0 ����������� ����� ������.

���������� 3.1. (�������� ������). ��������, ��� � ������ EA0 ���������� ���������� �������� �������� ����������� ����� - ���������� �������, ���������� x+y=z, �.�.������� PLUS(x,y,z) �����, ���

EA0 |- PLUS(x,0,x), (x+0=x),

EA0 |- (Au)(PLUS(x,y,u)->PLUS(x,Sy,Su)). (x+Sy=S(x+y))

������� ����� ��������, ����������� �� ��������� ������� ����� EA ����������, ��������� �� ��� �� ������ ������ EA0 (� ���������, ��� ������ ����� ������� ���� ���������, ���� �����������) (��. �.��������, �.������� [1934]). �������� �� ����������� �������, ���������� ��������� x<y?

����� �������, ������ EA0 �� ����� ������������ ���������� �������� - � ��� ���������� ��������� ���� �������� �������� ����������� �����. ���������� ��� ������ - �������� � ����� EA0 "�����������" �������������� ������ "+" ��� �������� ��������. � ���� ������ ����������� ����� (����� ������, ������� ����� ���������� ����� EA1) �������� ���:

�) ��������� 0,1 � ����� ���������� - ����� EA1 (������ ������� S ������ ��������� 1, ��������� �������� �������� ��������� �������� Sx � ���� x+1),

�) ���� t1 , t2 - ����� EA , �� (t1+t2) - ����� ���� EA1. �������������� �� ������ �������� � ��������� �������:

P1) ~(0=x+1),

P2) ~(x=y) -> ~(x+1=y+1),

P3) x+0=x,

P4) x+(y+1)=(x+y)+1,

P5) B(0) & (Ax)(B(x)->B(x+1)) -> (Ax)B(x).

����� B(z) - ������� ��� �� ����� EA1, �.�. ����� ������ �������� � ������ EA1 ������ ���� "�������" ����� �������� � EA1.

��� ������������� ���. ������ EA1 ��� ���������� ������. ���, ��������, � ��� ����� ���������� �������� ��������� x<y:

x<y <-> (Ez)x+z+1=y.

� 1929 �. ������ EA ���� �������� ����������� �.������������, ������� �� ������� �������� ����������� �����������. ������ ����� �.���������� �������� ��������, ������� ��������� ��� ������ ��������� ������� �� ����� EA1 ����������, "�������" �� ��� ��� ����� ������������ ��������� ������ EA1. ���� ���� ��������, ����� ��������, ��� ������ ��������� ������� �� ����� EA1 ���� ���������, ���� ����������� �� ������ ������ EA1. ������������ ���� �������� ������������������ EA1, ������ � ���� �������������� ���� ������������ ������ ��������, ����������� � ��������� ���������. ��� ���� ��� ������ ������������� ����������. ���������� � 1929 �., ��� ��� ������ �������� ���� �.��������� � ������������� ��� ��������� (���� � ����������� �������������� ������������������ ���� ���������� � ������� �������� ������� �����������). ��������, ������� ��� ���� ����� ��������������, ���� � ���������� ������� ���, - � ���� ����� ����������. ������ ��� � 1930 �. ����������� ������ ����������� ��������...

���������� 3.2. (�������� ������). ������� �������� ����������� (��. �.��������, �.������� [1934]) � ��������, ��� ���������� �������, ���������� x*y=z, �.�. ������� MULT(x,y,z) �����, ���

EA1 |- MULT(x,0,0) (x*0=0),

EA1 |- (AuAv)(MULT(x,y+1,u)&MULT(x,y,v)->u=v+x) (x*(y+1)=(x*y)+x).

� 1974 �. �.����� � �.����� ��������, ��� �������� ���������� ��� ������ EA1 ����� ������: ������� ������� �� ���������� ������� ����� n ������� 2**2**cn ������ ������� (��. �.����� [1977], "**" ���������� �������� ���������� � �������).

����, ������ EA1 ����� �� ����� ��� �������������: � ��� ���������� ��������� �������� ��������� ����������� ����� � ��� ����� - ������� �������� ����� � ������ ������ ������� ������ �����. ��-��������, �� ������ ������� ��� ���� ���: ������ �������������� ������ "*" ��� �������� ���������, �������� ����������� ����� (� ����� ������, ������� ����� ���������� ������ ����� EA):

�) ��������� 0,1 � ����� ���������� - ���� EA,

�) ���� t1, t2 - �����, �� (t1+t2) � (t1*t2) - ����� ����� EA.

��������, ����� EA - ��� ����������� ��������� (�� ����������, ������ ������, ����������) � ������������ ��������������. ��������, ���� (((x*x)+(((1+1)*x)*y))+(y*y))

������������ ������� x2+2xy+y2 .

������ EA ���������� ������ ����������� ������ ��������� "=" (���������� ��� ��������� ����������� �����). ���� t1, t2 - ����� EA, �� (t1=t2) - ������������ ������� EA. �� ������������ ������ � ������� ���������� ������ � ��������� �������� ����� ������� ������� EA, ������ Ex �� �������� ��� "���������� ����������� �����", � Ax - ��� "��� ���� ����������� �����".

���������� ����� EA ����� ������������ ���������� ����������� � ��������� ����������� �����, ��������

"x - ������ �����" <-> (Ey)x=y+y,

"x - ������� �����" <-> 1<x & ~(EyEz)(y<x & z<x & x=y*z),

"���������� ���������� ����� ������� �����" <->

<->(Ax)(Ey)(x<y & "y - ������� �����").

���������� 3.3. ���������� ���������� ����� EA ��������� �����������: "���������� ���������� ����� ������� �����- ���������", "��� ������� x �� y ���������� ������� z", "x � y �� ����� ����� ���������".

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

E1) ~(0=x+1),

E2) ~(x=y) -> ~(x+1=y+1),

E3) x+0=x,

E4) x+(y+1)=(x+y)+1,

E5) x*0=0,

E6) x*(y+1)=(x*y)+x,

E7) B(0) & (Ax)(B(x)->B(x+1)) -> (Ax)B(x).

����� ������������� � �������� EA ������� ����������� ����������� ��������� (������� E5,E6), � � ����� ������ �������� (E7) � �������� ������� B ����� ��������� ����� ������� B(x) ����� EA � ���������� ��������� ���������� x (��� ���� ����� x ������� ����� ��������� � ������ ��������� ���������� - ���������).

����, ��� ������ EA ��� "�������" EA1. � ����� ���������� ������-������ � ��������� ������������ ��������� ��� EA1 (��. ����), � ��� ���� ������ ��������� ����� �������� ��� EA (� � ������� 6.4 ����� ��������, ��� �� ������ ����������). �� ����� �� ���������� ���� ����, ���� ����� ���������, ��� � EA ���������� ���������� �������� ���������� � �������:

x0 =1, y+1 y

xy+1 =(xy)*x ?

� ������� 3.3 ����� �������� ������� � ��������������, �������� ������� � EA ����� ���������� (� ������� ���������� �������) ����� ���������� �������, �.�. ���������� ����� EA ������ ��������������� ��������� ������ � "��������" ������ EA ��������� �� �����. ��� ��������������� � ����������� ��������� ���� ������ ������� �����������, ������� �������� � �������� EA.

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

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

�) ������������ ������� EA ����� ��� (t1=t2), �.�. ��� ����������� � ��������� �������� ���������. ��� ����� ���������� ��������� ����������, �������� � ����� t1, t2, �� �������� ����� ���� ��������� � ��� ����� ����� ���� ����� ������ �� ���������� ��������� t1=t2.

�) � ������ EA ������� ������ ���������� ������: ~,&,V,->. ���� ����� ������ �� ���������� ������ A, B, �� �� ������� �������� ������� ������ �������� ������ �� ���������� ~B, A&B, AVB, A->B.

�) � ������ EA ������� ��� ��������: E,A. ������� (Ex)C(x) ��������� ��������, ���� ������� C(x) ������� ��� ���� �� ����� �������� ���������� x. ������� (Ax)C(x) ��������� ��������, ���� C(x) ������� ��� ����� �������� ���������� x.

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

�������, ������, ��� � ����� ����������� "����������" ������ �� ��������������� ��������� ���� "C(x) ������� ��� ����� �������� x". �������� ������ ������������ ��������� ������� ����������� �����, ������������ �������� x ���������� ���������� �����, �.�. �� �� ����� ���������� "����������" (Ax)C(x) ������� ��������� "����������" C(x) ��� ���������� �������� x. ���������� (Ax)C(x) �� � ��������� ���������� (���� ��� ������ �������) ������ ������������� ����� - ��������� ��� ����������� �� ������ �����-���� ������, �.�. � ������������ ������ (��������, EA ��� ZF). ����� �� �� ����������, ��� ������ ��������� ������� EA ����� ���� "������������ ��������", ���� "������������ ������������"? ��� �������� �� ��� ����������..., �� ����� ���������� ������ �� ����� � ���� ��� ���� - EA, ZF ��� ������? ����� ������� ������ ����������� "����������" ������ �����, �� ������ ������� �����, ����� ����������� ����� ������ � �������.

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

EA |- AV~A

��� ����� ������� A. ������ ������� �� ������, ��� ���� A - ��������� �������, �� ���� EA |- A, ���� EA |- ~A? �� ������� ������ � ��������� ��������, ��� �� EA, �� ZF, �� �����-���� ������ ��������� �������������� ������ ���� ��������� ��������� �������� �� ����� - �������� �� �������������� ������ ������������ �������� � �� ��������! (��������� ��. ������ 5.)

�������� ��������� ������ ������ � ������ EA ��������, ��� � ��������� �������, ����� ��������. ���������� � �������� ������� ����� ������� 0+x=x (��� ���������� �� ������� x+0=x!). ��������� 0+x=x ����� A(x). ������� �� ������ �������� A(0), �.�. 0+0=0, �� ��� ������� ������ ���������� ������ ��� �������. ������ ����� �������� A(x)->A(x+1). ����������� ��������������� �������� ��������, ������� A(x) � �������� ��������:

A(x) ��� 0+x=x (��������),

0+(x+1)=(0+x)+1 (������� ������ �������),

0+x=x -> (0+x)+1=x+1 (�������� ���������),

(0+x)+1=x+1 (MODUS PONENS),

0+(x+1)=x+1 ��� A(x+1) (�������������� ���������).

�� ������� �������� ������ ������� EA |- A(x)->A(x+1), � ����� EA |- (Ax)(A(x)->A(x+1)). ��� ��� A(0) ��� ��������, �� �� ����� �������� �������� EA |- (Ax)A(x) ��� EA |- 0+x=x.

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

���������� 3.4. �������� ��������������� ���������, ������ ��������� ���� ������ (�������������� �� ����� �.����������� [1976]):

x=y -> x+z=y+z, x+z=y+z -> x=y,

0+x=x, (x+1)+y=(x+y)+1, x+y=y+x, (x+y)+z=x+(y+z),

x=y -> x*z=y*z, 0*x=0, (x+1)*y=(x*y)+y, x*y=y*x.

� ������ EA ����� �������� ��� ������� �������� ��������� x<y, ������������� �������� (Ez)(x+z+1=y). � ���������, ����� �������� ����� ������, ������������ ����� ��������, - ��� ���������� ������� ����������� �����:

EA |- ~(Ax)C(x) -> (Ey)(~C(y)&(Az<y)C(z)).

� ������ EA ����� �������� ���������� ��������� �����. ���� ����� R(x,y,z) ���������� ������� (Eu)(x=y*u+z & z<y), �.�. "��� ������� x �� y ���������� ������� z", �� ����� ��������, ���

EA |- 0<y -> (Ez)R(x,y,z),

EA |- R(x,y,z1) & R(x,y,z2) -> z1 = z2,

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

��� ����������� ����� �������������� ����� ����� � ����� �.����������� [1976], � ������� �������� ���������� ������ �� ������ EA �������� ������� ����������� �����. ����� ����, ��� ���������� EA �������������� ������ ������, ����� ���������� � ����������� �������������� ��� ����� ��������� ������, �������� � ������������� ���������� ������� �����. �������� ������������ ������, �� ����� �� "������������" ���������� EA ��� �������, ������������ � ������������ ��������� ������ �����. ��� ����������� ������ �� ����� ��������� �� �����. ������� �� ����� ���, ��� ��� �������� �� - ��� ���� � ��� ���. ����, ��������� ����������� �������� ����������� ������������� ������: ��� ����������� ������� (�����������) ������ �����, ������� �� ���������� � ������������ �������������� ������ � ��������, ����� ���� ��������� �������������� � EA.

������ ������ ����������� ��� ��������� ����������� ������ EA: 2 - ��� (1+1), 3 - ��� ((1+1)+1) � �.�. ����� ������ ���� ������� �������� ���������� - ������������ ������������� ���������� ����������� �����. ��������, ������������ � ������ ������ EA, ����� ���������� ����� k, l, m, n, p, q, r.

������� ������ ��� ������� ������� ��������� "<", ������� ����������� ��� � ����������. ���� k>0, ��

EA |- x<k <-> (x=0)V(x=1)V... V(x=k-1),

EA |- (Ex<k)C(x) <-> C(0)VC(1)V... VC(k-1),

EA |- (Ax<k)C(x) <-> C(0)&C(1)&... &C(k-1).

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

���������� 3.5. ���� � ������������ ������� t1=t2, ���������� ���������� ("�����������"), ��� ��������� ������ ����� ��������� � �����, �� ������� ���������� ��������� (��. ������ 4.1). ��� ���������� ������� ����� ��������� � ����������� ������. ��������, ��� ���� ������� ���������� ������� (b1, b2,..., bn) ��������� t1 = t2 , ��

EA |- (Ex1Ex2... Exn)t1 = t2.

(��������: ������� ��������� �� ��������� ������ ��������, ��� � EA ��������� ����� �������� ������� t1 = t2, �� ���������� ����������.)

 

3.2. ����������� ����� � ������ �������

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

����� ������� �������� � ��������� ���������� ������ T �� �� �����, ������� ��������� � ����������� EA? ���� ������ �������� ����� ����������� � ������� ��� ���������� ������������� �������������. ����� ������������� � ������ T ����������, ������ ����� �����-�� ������� �� ������� �������� ���������� T ������ ���� ��������� ������������ �������. ��� ������� � ���������� � ����� T ��������� ������� N(x) (� ������������ ��������� ���������� x), ������� "����������", ��� x �������� ����������� ������. �����, ���������� ���������� � ������ T ������������ ������� EA, �.�. ������� ���� t1 = t2, ���������� � ��������� ��������� t1, t2 � ������������ ��������������. � ����� ����� ���� ��� ����� ��������� ���������� ����������� pi, ����������� ������ ������������ ������� F �� ����� EA � ������� pi(F) �� ����� T. ��� ���� ����������� ���������, ����� ������� pi(F) ������ ����� � �������� �� ��������� ����������, ������� ����� F. ����� ����������� ����� ������������ ��� ������������ ������ EA:

pi(~A)=~pi(A), pi(A&B)=pi(A)&pi(B),

pi(AVB)=pi(A)Vpi(B), pi(A->B)=pi(A)->pi(B),

pi((Ex)C(x))=(Ex)N(x)&pi(C(x)),

pi((Ax)C(x))=(Ax)(N(x)->pi(C(x))).

���� (N, pi) ����� �������� ������������� �������������� EA � ������ T, ���� ��� ������ ������� A ������ EA

T|- N(x1)&... &N(xk) -> pi(A),

��� x1,..., xk - ��������� ���������� ������� A. ��������, ��� ������� x+1=y+1 -> x=y ���������

T|- N(x)&N(y) -> (pi(x+1=y+1)->pi(x=y)).

��� ��� ������ T �������� ������ ����� ���������� ������� �����������, �� ������ �������, ��� ��� ����� ��������� ������� C �� ����� EA: ���� EA|- C, �� T|- pi(C). ��� ��������, ���, ���� ������������� ������������� EA � T, � ������ T ����� �������� ����� �������� ����������� �����, ������� ��������� � EA. � ���� ��� ���������� ������ "�������������� ����������" ������ T, �� �����, �������� ���������, ���� ������ T|- C ������ T|- pi(C). �������� ���� ������� ����������� ����� � ����������, ���������� ������, � ������� ������������ ��������������� ������ EA (� ������� �������� � ���� ������ ����������� ������� ������������ �����), ����� �������� ��������������� �������. ���������� �� ��������������� ������ ��������, �������, ���� ������ EA.

������ �������� ZF, ����������, ����� ����������� ���������������. ������� N(x), ������������ ������������� ������������� EA � ZF, �������� ����� ������ "x in w", ��� w - ��������� ���� ����������� �����. ������ ���� �������� "x in w" � ����������� ���� ���������� ����� ZF, �� ��������� �������� ������� ������� (��.������ 2.3). ����� �� ������� ����������� � ����������� pi. ����������� ����������� ���������. ��-������, pi(�=�)=(�=�). ��������� ���� ������������ ��� ������ ��������� 0, ������� - ��� {0}, 2 - ��� {0, {0}} � �.�., �� pi(x=0)=(Ay)~(y in x), pi(x=1)=(Ay)(y in x<->pi(y=0)) � �.�. ������� pi(x=2) ���������, ���� ���������� �������

(Ay)(y in x <-> pi(y=0)Vpi(y=1)).

������, � �������� �� ������ ���� ������, ����� ������ ����������������� ��������� �������: �������� ��, ��� ��� ��������� ��������������� ������ T (������� "�������" ������ EA) �������� � ����� EA ������� C �����, ��� T|- C, �� �� EA|- C? ����� �� ���� ������ ����� ������� � ������� 6.5 (��. ����� ���������� 2).

���������� 3.6. ������� ��������� ���������� 1.4, ��������, ��� ��������� pi-1(T) "�������������� ������" ������ ��������������� ������ T �������� ���������� ������������. (�������������� ������������� ����������� pi. )