� � � � � � � � � � I

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

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

��� ��� ������� � ������ �������� � �������� ���������� ������ - � ��� ���������� ������� �������. � ���� ������ ������� ������������ � ������ ������ �������� �����������, ����������� ��� ������ ��������. �������������� ���� �����������, ������� ��������������� ����, ����� ������������� � ������ ZFC. ����� �������, ��� ������ ������� - ��� ������������ ���������� ������ � ���������� ZFC.

���� � ����� ������������ ������������ ���������, ������ ������� ��������� ���������� ������, ��������� �������������. ����� L - ��������� ���� ���������� ������ (������ ������ - ���� ������� �������, ��. ������ 1.5), ������� ��������� c1, ..., ck, �������������� ������� f1, ..., fm, ����������� ������� p1, ..., pn. �������������� I ����� L ������� �������� ����� ��������� ��������:

�) ������� ������������� - ��������� �������� ��������� DI (��� ������ �������� ��������� ���������� ����� L),

�) ����������� intI , ��������������:

- ������ ��������� ci ��������� ������� ��������� DI : intI(ci ) = ci in DI; ��� ����������� - ���� ��������� "��������" ���������� ���������� ������� � ������� �������������,

- ������� ��������������� ������� fi ��������� ������� �� DI � DI , �.�. intI(f1) = fi, ��� fi: DI x...x DI -> DI (�����������, ���������� ���������� intI(fi) ��������� � ����������� ���������� fi),

- ������� ������������ ������� pi ��������� ��������� �� DI, �.�. intI(pi) = pi <=DI x...x DI (�����������, ���������� ���������� intI(pi) ��������� � ����������� ���������� pi).

� �������� ������� ���������� ��� ���������� ����������� ������������� S ������������ ���������� EA:

�) ������� ������������� DS ={0, 1, 2, ... }, �.�. DS = w � �������� ZF,

�) ����������� intS ������������: ��������� 0 - ����� 0 (������ ���������), ��������� 1 - ����� 1 (��������� {0}), ��������������� ������� "+" - ������� x+y (�������� ����������� �����), ��������������� ������� "*" - ������� x*y (��������� ����������� �����), ������������ ������� "=" - ��������� x=y (��������� ����������� �����).

��� �������� ������������� I (���������� ����� L) ������������ ������� ���������� ������ ����� L. ����������� ���������� � ������������� ������ � ���� ������� �� DI � DI. ������ ���� ����� �������� ���� ����������, ���� ����������, ���� �����������, ������������ �������������� �������. � ������ ���� ������� �������������� ����� ���������� ���� ���������� ������� c(x) = ci , ���� ������������� ������� e(x) = x, � � ��������� ������, ���� t=f(t1, ..., tn), �� intI(t) - �������, ���������� ����� ����������� ������� intI(t1), ..., intI(tn) � ������� intI(f). ��������, �������������� ����� (x+y)*(x+y) �������� ������� (x+y)2 .

����� ������������ ������� ������������ ���������� ������������ ������ (��� �������� ��������� ��������� ���������� �� ������� DI): ���������� ������� pi(t1, ..., tn) ��������������� ����� "����������" �������� ������ t1, ..., tn � ������������ ���� �������� � ��������� intI(pi). ��������� � ��������� ���������� ����� ����������� - ���� ����������, ��������, ������� x=1 ������� �� ����������� �������� x.

�������, ����� "����������" ������� ���������� ��� ������������ ������ ����� L ��� ������ ������������� I (�����, �����������, ��� �������� ��������� ��������� ���������� �������):

- ������ �� ���������� ������ ~A, A&B, AVB, A->B ����������� ������� �������� � ������� �� ���������� ������ A, B,

- ������� (Ax)A(x) �������, ���� ������� A(x) ������� ��� ����� �������� ���������� x �� ������� DI,

- ������� (Ex)A(x) �������, ���� ������� A(x) ������� ��� ���� �� ����� �������� ���������� x �� ������� DI.

���������� ���������, ��� � ������ ����������� ������� DI ������� ���������� � ����� ������������� ����������� ����������������: ��������, �������� ���������� ������� (Ax)A(x) ������� �������� ���������� A(x) ��� ������������ ����� ���������� �������� x (��. ����������� � ������� 3.1 �� ���������� ������ ������������ ����������). ��� ����� ��������������� ������� ���������� ������ ���� (AxEy)B(x,y), (AxEyAz)C(x,y,z) � �.�.

������� ����� L ���������� ������������ �������� ��� ������ ������������� I, ���� ��� ������� ��� ����� (������ �� DI) ��������� ����� ��������� ����������.

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

A->A, (A->B)->((B->C)->(A->C)), (Ax)(C->D(x))->(C->(Ax)D(x)),

��� ������� C �� �������� ���������� x. ����� �������, ������������ �������� ��� ����� ������������� (�.�. ��������� ����� �����), ������� �������� ��������� �������������. ������� �������� ������� ������������������ ����� ������� - �� ��� ���������������� ������� ���������� ����� ������������� ������� "��� ���� �������������".

����� ���������, ��� ���������� ������� � ������� ������, ���������������� � ������� 1.5, ��������� ���������� ������ ��������� ������������ �������. �� ����� ��������� �������� ������ - ������ �� ��������� ������������ ������� ����� �������� � ������� ���� ������? �������� ����� �� ��� ������, �� ��� ��� � 1929 �. �.�������:

������� ������ � �������. � ����� ����� ������� ������� ������� �������� ��������� ������������, ���� � ������ ���� �� ����� �������� � ������� ���������� ������ � ������ ������ �� ������� 1.5.

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

����� T - ���������� ������. ������������� I (����� T) ���������� ������� ������ T, ���� ��� ���� ������������� ������������ ������� ��� ������� (� ��� �������) ������. ����� ������� ������ ��������� ��������: � ���������� �������� ���� ������ ������ ������� ������� �������, ������������ ���������� � �.�., � ����� - ��������! ���, ������, ������������ ������ �������������� ������.

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

�������� ��� ������� ������ - ������������� � �������� ��� ������� �������� DI. ����� ������� ����� ��� ������� ��������� ���: ���� � ������ ��� ������������, �� �� "����������" ������� - ��� ��������� �����-�� "�������������� ����������".

���������� �������������� ������� � ������������� ������, ������������� �.������� � �.�����������, ��. � ����� �.����������� [1976].

���� ������� � ������������� ������ ��������, �� ������� ������ � ������� ����������� ������� �� ����������. � ����� ����, ��, ��� ��� ������� ���������� ����� ������� ������� L, ��������� � ������� ���������� ������ � ������ ������, �������� ��������� �������������, ����� ����� ���������, ��������� �� ��������. ������ ��������, ��� �����-���� ��������� ������������ ������� F �� ����� L ������ �������� � ������� ���������� ������ � ������ ������. ��� ������, ��� ������ T (�� ����� L), ������������ ����������� �������� ������� �������� ������� ~F, ����� ���������������� (���� ��� �������������� - ��� �������� �� ������������ "�� ����������" ������� F ����� ����������� ����������). ����� �������, ���������� ������ ������ T, �.�. �������������, � ������� ������������ ������� ��� ������� T, � ��� ����� ������� ~F. ������ � ���� ������������� ������ ���� ������������ �������� � (��������� ������������) ������� F! ������� F � ~F �� ����� ���� ��������� � ����� � ��� �� ������, �.�. ���� ������������� ������� � ������� F ����� �������� � ������� ���������� ������ � ������ ������, ��� � �����������.

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

���������� 1. ������ ���������������� �����, � ���������, �����������. ��� ������� � 1936 �. �.����, ���� �������������, ��������, ���� EA, �� �� ���������� ���������, ������� ����������, �������� �� ������ ������� ����� ��������� ������������ (������� ����� � �������������� ���������� ����������, ��. �.���������� [1976]).

���������� 2. ������� � ������������� ������ ������� ���� �������� � ����� ������ �����: ���� ���������� ������ ����� �����-���� ������, �� ��� ����� � �������� ��� ������� ������ (������� ����������-�������, ���������� �.����������� � 1915 �. � �.�������� � 1920 �.).

� �������� ����������-������� ������ �������� �������. ���� ������������, ��� ������ ZFC ����� �����-���� ������, �� �������� ���� ������� ��� ����� � ������, ��������� �� �������� ����� ��������� (������ ZFC �� ����� ���� �������� ��-�� ������� �������������, ������� ������ ����������� � ������). �� ���� � ������ ZFC ����� �������� ������������� ��������� ��������, ��� �� ��� ����� ����� ������� ������?

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

�� ����� ���� �������� ������� ����� ����� ������� ����������, �� ����������� ����� ��� �����-���� ����������. ����� I - ������������� ������ ZFC �� ������� �������� DI. � ZFC ����� ��������, ���, ��������, ��������� ���� �����- ��������� ����� R ��������, �.�.

1-1

~(Ef) f: R -> N, (1)

��� N - ��������� ���� ����������� �����, f - ��������������� �������. ����������, ���� ����� ������������� N � R: intI(N)=n in DI, intI (R)=r in DI, �� n, r <= DI � ��������� n, r ��� ����������� ��������, �.�.

1-1

(Ef) f: r-->n.

������ �������������� ������� (1) �������� �����������

1-1

~(Ef in DI) f: r-->n,

������� ������������ ����� �� ���������: ��������������� ������� ���� f: r-->n ����������, �� �� ���� �� ��� �� ���������� � ������! "����������� �� �������" ��� ��������� ������ ������� ��������, ������ "�����������", ����������� "������ ������", ��������� ������� "�� �����", ������� ��������� ������� ��������� ��� �������������� ����������.

� ��������� ��.����� (��. ������ ������� 3.1) ������ ��� ���� ������������� ������������. ��� ���� ������ ����� �������� ������� � ��������������, ������� ����������, ��� "������ ��� ������, � ������� ����������� ������� �����, ���������". ������� ������ ���������� ����� ����� ������������� � ������ ZF: ��� ������ (v,o,s), ��� v - ��������� (��� �������� ��������� "������������ �������" ������), o - ������� v ("����"), s - ������� ���� v->v (s(x) ������ ���� ������� x+1). ����� ��������, ��� � ������ (v,o,s) ����������� ������� �����, ����

P1: ~(s(x)=o) ��� ���� x in v,

P2: s(x)=s(y) -> x=y ��� ���� x, y in v,

P3: ���� u<=v, ��

o in u & (Ay)(y in u -> s(y) in u) -> u=v.

������������ ������� ���������� ����� ����������� ��������� w ���� ����������� ����� �� ��. ��� ������� (��. ������ 2.3), ��� ����� �������� ������ ��������� 0, � ���� s(x) ������ xU{x}. ��� ������ ������� �������� ����������� �������. �������, ����� ��������, ��� ������ (v,o,s) ��������� ����������� ������, ���� ���������� ����������� f: w->v �����, ���

�) f(0)=o,

�) n in w -> f(n+1)=s(f(n)) (���� x ������������� n, �.�. x=f(n), �� s(x) ������������� n+1, �.�. s(x)=f(n+1)),

�) ������� �������� rng(f)=v,

�) f - ��������������� �������. ������ �� ����� �������������� ���������� �������.

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

� � � � � � � � � � � � � �. ����, ����� � ������ (v, o, s) ����������� ������� �����. ��������� �� �������� ��������� ����������� f ���� w->v:

f(0)=o, f(1)=s(o), f(2)=s(s(o)),..., f(k+1)=s(f(k)),...

�������, ��� f �������� ������������:

�) f(0)=o �� �����������,

�) f(k+1)=s(f(k)) �� �����������,

�) ������� �������� rng(f) ���������� � v, ��� o in rng(f), � ���� y in rng(f), �� y=f(k) ��� ���������� k, � ������� s(y)=s(f(k))=f(k+1) in rng(f). ��� ��� � ������ (v,o,s) ����������� ������� P3, �� ������ ��������, ��� rng(f)=v,

�) �������, ��� f(m)=f(n) -> m=n, �.�. ��� ������� f ��������������. ����, ����� f(m)=f(n). �������� ��� ������:

�1) m=n=0 (��� ����),

�2) m=0, n>0. ����� f(m)=o, ������ f(n)=s(f(n-1))<>o ��-�� ������� P1, ������� ����������� � ������ (v,o,s),

�3) m, n>0. ����� f(m)=s(f(m-1))=f(n)=s(f(n-1)), � �� ������� P2 ����������, ��� f(m-1)=f(n-1). ��������� � ����� ����, �������� ���� � ������ �1), ���� � �2).

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

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

�� ������� ������ � ��������� (��. ������ 5.3) ��������, ��� ������� ������ EA (��� ����� ������ ������� ������ �� ����� EA) ���� ��������� �������������� �������� �� �����. � ����� ����, ������� ������ ��� ������ EA ����� ��� ~(Ex)C(x), ������ ���� ������ EA ���������������, �� ��� ������� ����������� ������������ ����� n: EA |- ~C(n), ������ � EA ���������� �������� ~(Ex)C(x). ��� ��������, ��� ���������������� �������� ������ EA' = EA+{(Ex)C(x)}. � ������� ������ EA' ��� ������� "������������" ������������ ����� n ����������� ~C(n) (��� ������� EA, �.�. � EA'), ������ � ���� ������� ���������� ������ q, ��� �������� ����������� C(q). ����� ������� ������� �������� "��������������" ������������ �������, � ������, � ������� ��� ����������, - �������������� �������� ����������.

� ������������, � �������������� ������� � �������������� ����� ����������� � ������ ZF, �.�. ������ "�������������������" � ���� ������� ���� �� �����. ��, � �������� ���������������� �����������, ���������� � ���, �������� ����� ������������ �������� (���� �� ������ ZF: AV~A ��� ����� ������� A, ������� ������ ������� � ������ ������ ���� �������, ���� �����).

 

� � � � � � � � � � 2

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

��������� ������ "������������" �����������, ������� �������� ���������� �������������� ������� (��� ���� ���������� ��������), � �������� � ��������� ����� �������� ���������� �������: "�� ������ ������ �� �������� �������������� ��������, ������� � ������ ���������, ������� �������� ���� � �����!" ��������� "���������������� �����" ��� ����� ��������� �������� �.����� [1971]:

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

������ �� ������� "����������������"? ���������� ������� ������ A, ������� ����������: "� �����������". ��� ������� �������� �������� N (������� ����������� �����. - �.�.), ��������� �� ����� �������� � ������� ��������� � ���������� ������ (�.�. �� ����� EA. - �.�.). ������ ����� �������, ��� A �������, �� �����������, �� ���������� �� �������� N, � �������� ������������ ������� "������������". ����� �������, ��������� � ���, ��� A �������� ������������ � ������, ������ �� ��������� �����: ��������� �������� �������� ��������� ������, ��������� ������������ �������� �������� ����������� ������. ���� ���� ����� ������������� �����, ��� ����������� ����� ������������� � ������������."

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

����� ������� � ��������� ���������� ��������� �������������� ������ ��������� ������� ������� (�������� ����� ������ �������� ���������� ������). � ���� �������� ����� �������������� ������ (��� �������� �������� �� ��������� ������) ��������� ������ ��������� ��� ������������, ��� ��������, ������� � ������ ������ ����� ��������������, �� ���������� ������. ��� � ����� ������������ ������� ���������� ������ ��������, �������� ���������� �������� ������� �������������� ������. �������, � 1963 �. �.���� ������� �������������� �������� ���������� � ������ �������� (��. ������ 2.4). � ��� ��� �������� �������������� ��� ������ ���� ������������ ������� ������ ��������. ������� �� ���������, ��� � ������� ������� �������� �������������� � ��������� ������������ ������� ������ �����, �������� �������� ������� �����-���������.

������ ��������� ����� � ���� ����������� �������� ������������ � 1977 �. �������������� � ������ EA ��� ���������� ��������� �������� ������� ������ (���� �����������, ��� EA ���������������), ������� �������� �������� � ������ �������� (��. ������). ��� ������ ������ ������������� ����������� ����������� � ��������� ������� ����������� �����, ��� �������������� �������� ������������ "�������������" ������� �� ���� ������, ��������������� � ������ EA.

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

�������, ���������� �.������� (1903-1930), ��������� � ������� ������������� ����������.

��� ��������� ��� �������� ��������� M ����� |M| ����� ���������� ���������� ��������� � M.

���������� ��������� ��������. ����� M - �������� ��� ������� ��������� ���������, ������� ����� �������� "��������". ���� e - ����������� �����, �� ������������ M, ���������� ����� e ���������, ����� �������� "e-���������". ����� ������ ��������� ��������� e-������ �� M �� r ���������������� ������� (��������, �� "������ ����"). �.������ �������, ��� ���� ��������� M ����� ���������� �������, �� ��� ����� ��������� e-������ �� M �� r ������� �������� ���������� ������� ������������ H<=M, �����, ��� ��� e-������� �� H �������� � ���� ����� ���������. ����� ������������ H ������� �������� ���������� ��� ������� ���������.

�������� ��������� �������� ���������� ��� e=2. ����� �������� ��������� M ����� ������������ ��������� ������� �����, � 2-������� - ������� �����, ��������� �� � r ������, � ����������� �� ������ ���������, ���� ������ ������� ��������. ���������� ���������� � ���� ������ �������� ������ �������, ��������� �� ����� ������ �����. �������� ������� ������ � ���������� ������� "�������" ������ ����� �������� � ���������� ������� ����������� ������ �������.

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

����������� ������� ������. ����� e,r>0 - ����������� �����. ���� M - ������� ���������, �� ��� ������ ��������� e-������ �� M �� r ������� �������� ����������� ������������ H<=M, ��� e-������� �������� �������� � ���� ����� ���������.

� � � � � � � � � � � � � � (���������� � ������ ZFC, ��. �.������ [1984]). ������������� ��������� �� e.

1) ��� e=1 ����������� ������� �������� (���� M - ����������� ���������, � ����� ������� ��������� �������, �� � ���� �� ������� �������� ����������� ����� ��������� M, ��� � ���� ��������� ���������� ������������ H).

2) ���� ����������� �������������� ����� ����� ��������� ��� e=2. � ���� ������ (��. ����) �������� ������������ "�������" ������ ����. ��������� ��������, ��� � ����������� ������ ����� M, ����� �������� ���������� � r ������, �������� ����������� ������ ������� � ������� ������ �����.

��������� ��������� ������������������ ������ �����, ������ � ���������. ������� �������� ������������ ������� a0 in M. �� ��� ������� ����������� ����� ����� � ��������� �������� �����. ����� ��� �������� ���������� ����� ����� ������ �����, ��������� ���� ���� ����� c0, � (�����������) ��������� �������� ������ ���� ����� - ����� M1 . ����� �������, M1 <= M0 = M, � ������� a0 � ��������� �� M1 ������� ������ ������� ����� c0. ����� �������� ������������ ������� a1 in M1. �� ��� � ������� ��������� ������ M1 ������� ����������� ����� �����, ����� ��� - ����������� ����� ����� ������ �����, ������� ��������� ����� c1. ��������������� (�����������) ��������� �������� ������ ���� ����� ��������� ����� M2 . ����� �������, M2 <= M1 <= M0 , � ������� a1 � ��������� �� M2 ������� ������ ������� ����� c1 . ����� �������� ������������ ������� a2 in M , � �.�.

� ���������� ����� �������� �������� ��� ����������� ������������������:

- ������: a0, a1, ..., an,...,

- ������: c0, c1, ..., cn, ...,

- ����������� ���������: M = M0 >= M1 >= ... >= Mm >= ... ����� ������ ai in Mi -Mi+1, � �� ai � ������� ������ �� Mi+1 ����� ������ ����� ����� ci.

���� �� r ������ ����������� � ������������������ ����������� ����� ���, ��������� ��� ����� c:

c = ci0 = ci1 = ci2 =...

��������� ��������������� ������ ��������� ����� H:

H = {ai0, ai1, ai2, ... }.

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

���� ����������� �������������� ����������� ������� ������ ��� ������ e=2.

3) ������� ������ ����� ������ ���� ��������: ������� �� e-1 � e. �� ������ ��������� ��������� ����������� �.2, ���� ����� �������� ���������

�����. ����� ���� ������� ��������� M � ��������� P e-������ �� M �� r �������. ���� ����������� ������� ������ ����� ��� e-1, �� ��� ������� ������������ ������������ M' <= M � ������� �������� a' in M' �������� ����������� ������������ H' <= M'-{a'}, �����, ��� ��� e-�������, ��������� �� a' � ��������� H', �������� � ���� ����� ��������� P.

������� ��� �����. ������ �� ��������� P �������� ��������� ��������� P' (e-1)-������ �� M' -{a'} �� r �������:

{x1, ..., xe-1} in Pi' <-> {a', x1, ..., xe-1} in Pi.

����� Pi, Pi' ����� ���������� i-� ������ ����� ���������, ��� xj in M'-{a'}. �������� ����������� ������� ������ � (e-1)-�������� �� M'-{a'}, ������� ����������� ������������ H' <= M'-{a'}, �����, ��� ��� (e-1)-������� �� H' �������� � ���� ����� ��������� P'. �������� �� P' � ��������� ��������� P (�.�. �������� ������� a' � ������ (e-1)-������� �� H'), �������� ����������� �����.

���� ����� �����, �� ����� ��������� ����������� �.2. ����� ����� ��� ��������� ������������ ��������� Mi+1 <= Mi -{ai}, ������, ��� ��� e-������� �� Mi+1 U{ai}, ���������� ai , �������� � ���� ����� ��������� P (���� ����� ����� ���������� ����� a ). i

��� ����� ��������� �� e ����������� ������� ������ ����- ���� ���������.

������������ � �������������� ����������� ������� ������ ���������, ����������, � ������ ��������. ��� ������� �����������, ����� �������, �������� ������ ZFC. ��� ������� ����������� ���� �������������� �� ���������� ������ EA, ������� �� ��������� ��������� ������������ ����������� ���������.

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

� ������ EA �����, ������, �������������� � �������� ������ ����������� ������� ������ ��� �������� ��������:

�������� ������� ������. ���������� ���������� ������� R(e, r, k), �����, ��� ��� ����� e, r, k > 0 ��� ������ ��������� ��������� M: ���� |M| >= R(e, r, k), �� ��� ������ ��������� P e-������ �� M �� r ������� �������� ������������ H <= M �����, ��� |H| >= k � ��� e-������� �� H �������� � ���� ����� ��������� P.

� ����� �������� ��������� ����������� �������� ��� e=2: ���������� ������� R(r,k) �����, ��� ����� ������ ����, ������� R(r,k) ������ � �e���, ������������ � r ������, �������� ������ ������� �� k ������, ��� ����� �������� ���������� � ���� ����.

� � � � � � � � � � � � � � (��. �.������ [1984], ��� ����� ������������� � ������ EA).

1) ��� r=1 ����������� ������� ��������: ����� ����� R(1, k) = k.

2) ���������� ������ ������ r=2, ����� ��� e-������� �� M ����������� �� ��� ������. �����������, ����� �������� ��������� ��������� �������: ���������� ���������� ������� R'(e, 2, k1, k2), �����, ��� ��� |M|>=R'(e ,2, k1, k2) ��� ������ ��������� e-������ �� M �� ��� ������ �������� ���� ������������ H1 �����, ��� |H1| = k1 � ��� e-������� �� H1 �������� � ������ ����� ���������, ���� ������������ H2 �����, ��� |H2| = k2 � ��� e-������� �� H2 �������� �� ������ ����� ���������.

���������� �� ��������, �������� �� ������ e-1 � ������� (e, k1-1, k2), (e, k1, k2-1) � ������ (e, k1, k2).

� � � � � � � � � � � � �. ��� e=1 ����� �����

R'(1, 2, k1, k2 ) = k1 + k2

(� ���� ������ ���� �������� M ����������� �� ��� ������). �����, ������������ ������ ������������� e � ����������� k1, �����: ��� k1=e ����� ����� R'(e ,2, e, k2) = k2 (k2>=e), ��������� ���� ���������� ���� �� ���� e-������� ������� ������, �� ��� ���� � ���������� ��������� H1, � ���� ��� e-������� �� M �������� �� ������ �����, �� ����� ����� H2=M. ���������� ��� k2=e ����� ����� R'(e, 2, k1, e) = k1 (k1>=e).

� � � � � � � � � � �. ����� k1, k2 > e. �������, ��� ����� �����:

R'(e, 2, k1, k2) = 1+R'(e-1, 2, R'(e, 2, k1-1, k2), R'(e, 2, k1, k2-1)).

� ����� ����, ���� |M|>=R'(e, 2, k1, k2), �� �������� ���� ������� a in M � ������������� ��� e-������� �� M, ���������� a: {a, x1, ..., xe-1}. ������ �� ��� ��������� � ������� ��� ������� ������ ��������� P. ��������� ��� (e-1)-������ �� M-{a} �����- ���� ��������� P' �� ��� ������ (i=1, 2):

{x1, ..., xe-1} in P' <-> {a, x1, ..., xe-1} in P .

��������� |M-{a}|>=R'(e-1, 2, T1, T2), ��� T1 = R'(e, 2, k1-1, k2) � T2 = R'(e, 2, k1, k2-1), ��, �� ������� ������ ��� ������ e-1, �������� ������������ M'<=M-{a} �����, ��� ���� |M'|=T1 � ��� (e-1)-������� �� M' �������� � ������ �����, ���� |M'|=T2 � ��� (e-1)-������� �� M' �������� �� ������ �����. � ������ ������

(Ax1, ..., xe-1 in M') {a, x1, ..., xe-1} in P1

(P1 - ������ ����� ��������� P). �� ��� ��� |M'| = T1 = R'(e, 2, k1-1, k2), �� �� ������������� �������� (������ (e, k1-1, k2)) �������� ������������ H<=M' �����, ��� ���� |H|=k1-1 � ��� e-������� �� H �������� � ������ ����� ��������� P (����� HU{a} ����� ������� ������������� ��� ������ (e, k1, k2)), ���� |H|=k2 � ��� e-������� �� H �������� �� ������ ����� ��������� P (����� ��� �� H �������� � ��� ������ (e, k1, k2)).

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

��� ������ r=2 �������� ������� ������ ��������.

3). �������� ������ � ������ ������������� r>=2 � �������� �������� �� r.

� � � � � � � � � � � � �. ��� r=2 �������

R(e, 2, k) = R'(e, 2, k, k).

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

R(e, r, k) = R(e, 2, R(e,r-1,k)).

� ����� ����, ����� |M|>=R(e, r, k) � ������ ��������� ��������� P e-������ �� M �� r �������. ����� �������� �������� � ������ ���� �������, ����������� ���� �� ������� ��������� P (����� �������� ��� ������ �������), � ��������� ��������� (����� �������� ��� ������ �������). ����� �������� ����������� � ������ r=2 �������� ������������ M'<=M �����, ��� |M'|=R(e, r-1, k) � ���� �) ��� e-������� �� M' �������� � ������ �����, ���� �) ��� e-������� �� M' �������� �� ������ �����.

� ������ �), ��������� R(e, r-1, k)>=k, �� ����� �������� H<=M' �����, ��� |H|=k � ��� e-������� H �������� � ���� ����� ��������� P. � ������ �) �������� ��������� e-������ �� M' �� r-1 ����� ��������� P. ��������� |M'|= R(e, r-1, k), �� �������� ������������� �������� (������ r-1) �������� ������������ H<=M' �����, ��� |H|=k � ��� e-������� �� H �������� � ���� ����� ��������� P.

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

���� � �������� ������� ������ ���� ���� �� � ����������� ������, � � ������������ �������� ����������, ��� ������� ����� �������������� � ������ EA. ���������� ������� �����-���� ����������� �������� �������� ������������ �������, �������� � ������� ����-������� ������ (��. ������ 3.3): ����� ��������� {a1, ..., an} ����� ������� ���� ����� a, b �����, ���

beta(a, b, 0)=n, beta(a, b, 1)=a1, ..., beta(a,b,n)=an.

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

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

�� �����, ����� �������, ��� ������� ������:

�) "�����������", ������� ������ �� ��������������, �� (��� �����) �������� � ������������ ���������� (������ EA); ��� ����� ����� ������ �������� (������ ZFC),

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

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

����� ������� � ������������ ��������� �������� ������� ������, �� ������ ������������� � �������� ������� ������ �� ������������ ��������� M, � ���������, ������� ������� �� ������������� �������� "����������" � ���������� �������, �������� �� ��������� ���� ����������� �����. ����� �������� ����������� ���������� �������� ��������� �� ������ �� ���������� ���������, �� � �� ������ ���������. ��������, ����� ������������� "�����������" ��������� H = {a1, a2, ... , an}, ��������� ��������

2a1 <= a1, 2 a2 <= a 2, ..., 2 an <= an,

���, ��������, "�������" ���������:

a1 < a2 < ... < an & a1 <= n

(��� min(H)<=|H|). (�������, ��� � ������ ������ ��������� H ����� ���� "�������" � "�����������" ������������.)

� ������������ ���� ����� �������������� ������� ����� ������� "���������". ��� �� ������ �� ��������������, � �������� �������� ��������� � ���� ����� ����� ����� �������� gamma �������� �������� ����������� �����, ��������������� ���� ��������:

�) ���� H1 <= H2 � gamma(H1), �� gamma(H2 ),

�) ���� H2 - ����������� ��������� ����������� �����, �� �������� �������� ������������ H1 <= H2 , �����, ��� gamma(H1).

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

�������� min(H)<=|H| �������� ���������� �� �������, ��������������� ���� ��������:

- ���� H1 <= H2 � min(H1)<=|H1|, �� min(H2 )<=|H2|,

- ���� H2 - ����������� ��������� � H1 - ��������� ���������� min(H2) ��������� H2 , �� min(H1) <= |H1|.

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

��������� �������� ������� ������. ��� ������� ����������� �������� ��������� gamma ���������� ���������� ������� Rgamma(e, r, k), �����, ��� ��� ����� e, r, k>0 ��� ������ ��������� ��������� M: ���� |M|>=Rgamma(e, r, k), �� ��� ������ ��������� P e-������ �� M �� r ������� �������� gamma-������� ������������ H<=M, �����, ��� |H|>=k � ��� e-������� �� H �������� � ���� ����� ��������� P.

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

� � � � � � � � � � � � � � (���������� � ������ ZFC, ��. ��.�����, �.���������� [1977]). ��������, ����� ������������ ������������� � ���� M �������� ���� {0,1,...,n}, ������� �� ����� �������, ��� M={0,1,...,M-1} (��� � ������� 2.3). ��� ������ e, r ��������������� ��� M>=e.

��� M=e �������� ������ ���� e-������� {0,1,...,e-1} � r �� ��������� �� r �������.

���������� ������ ���������� ���� (M,P), ��� P - ��������� e-������ �� M �� r �������. ���� ������� �� M � M+1, �.�.

M+1 = {0, 1, ..., M-1, M} = MU{M},

�� �� ��������� P ����� �������� ������ �������� ����� ��������� ��������� e-������ �� M+1 �� r �������, ������� �� M ����������� � P. ��������� P' ����������� � P - ��� ��������, ��� ��� ����� e-������� {x1,..., xe} �� M � ������ i (1<=i<=r): 1 e

{x1, ..., xe} in Pi' <-> {x1, ..., xe} in Pi.

��������� P' ���������� �� P, ����� �������, ������ ��� ��� ��� ��������� �� e-�������, ������� �������� ����� M.

���� ������� � M=e, �������� ��������� ��� ���������, �� � ���������� �� ������� ����������� ������ � ��������� �����������:

|-------(e, P0')------ ...

|

|-------(e, P0'')------ ...

|

|------- ...

|

|-------(e, P0(i))------ ... --------(M, P)-------|-------(M+1, P(j)) -----------

|

|------- ...

|

|-------(e, P0(r))------ ...

 

����� ����� P0(i) ���������� ��� ��������� e-������ �� e �� r �������, � ����� P(j) - ������������ ��������� e-������ �� M+1 �� r �������, ������������� � ���������� P. ����� ���������, ��� ������� ����� ������ ���������� ��� ��������� ���� (M, P) (��� ������������� e, r), ������������ ������������ �� ������������ �������.

����� �������� ������� (M, P) "�������", ���� ���������� ������������ H<=M, ���������� ��������� gamma, ����� ��� |H|>=k � ��� e-������� �� H �������� � ���� ����� ��������� P. ����� ���������, ��� ���� (M, P) - "�������" �������, �� ��� (M+1, P(j)) - ����� "�������".

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

� ����� ����, � ����� ������ �� ����� �� ���������� ��������� �������� ���������� �������� ������� Rgamma(e, r, k). ����� ��������� ��� ������ ������ ������, �������� ������ ������� (M, P), "�������" ��� ��� ��� (����� ������� �������� ���� 2M ����������� M). ���� �� �����-�� ������ ��� ������� ��������� "��������", �� ����� M ����� ������ ����� ����� � �������� �������� Rgamma(e, r, k). ����� ������ ��������, ��� ����� ������� ������ ��������.

����, ����������� �� ����������, ��� � ����� ������ ���������� ����� "���������" ������. ���� (M+1, P(j)) - "���������" �������, �� (M, P) - ����� "���������", ������� � ������ �������� ����������� �����, ��������� ������ �� "���������" ������.

���������� 1. �������� ������, ��� ��� ������������� ��� (��� ����� ������: ���� ������ � ��������� ����������� �������� ���������� ����� ������, �� � ��� ������� ����������� �����).

����������� �����, ��������� �� ������������� ��������� (M, PM), ������ ���� ������������ ��������� P' ���� e-������, ��������� �� ����������� �����, �� r �������: ����� e-������� {i1, i2, ..., ie} ���������� ��������� PM , ���

M = max{i1, i2, ..., ie},

� ����������� ��������� PM+1, PM+2, ... �� ����� ��� ����������� ��������, ��������� ��� ����������� � PM.

�������� ������ � ��������� P' (���� e-������ �� ����������� �����) ����������� ������� ������, ������� ����������� ��������� H', ��� e-������� �������� �������� � ���� ����� ��������� P'. "���������" �������� gamma ��������� �������� �������� ������������ H<=H', �����, ��� |H|>=k � gamma(H) (������� ������� ������ �������� ������������, ���������� ��������� gamma, �����, ���� ��� ����������, ��������� ��� �� k ��������� �� H'). ���� ����� M=max(H), �� ��� e-������� �� H �������� � � ����� ������ ��������� PM. ��� ������������ ����, ��� ������� (M, PM) - "���������".

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

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

����� ��������, ��� ��� ����������� �������� gamma (��� min(H)<=|H|) ���� ����� �������������� � ������ EA. � 1977 �. �.����������, �������� �� ����� �����, ������������ �.����� � ��.�������, �������, ��� ��� �������� ��������� min(H)<=|H| ��� ������� ������ �������� � ������ EA (����������, ���� ��� ���������������, ��. ��.�����, �.���������� [1977]). ��� ������ ������, ����� ������� ������ ��������, ��� ��� �������������� ���������� ������������� ����������� ����������� � ��������� ����������� ����� ����� ��������, ��������� �� ����� ������ EA (�� ������ ��� �������� ����, ��������� ����������� ������� ������, �.�. � ������ ZFC). ����� ���������� �������, ��� ������� �����, ������� � ����� ������������ ������ �� ������������� ������� ������������ �����, ������� ������������� � EA, �� ����� �� �������� ����. ����� ����������� ��������� ������ ����� ����������� ������ �������� � XIX �.: �������� �.�������� ������� ������������� ������������ ��������� ���������, ����� �������, ����� ����� ������� ������������ �����.

���� ���������� ��� ��� � ������������ ���� �������������� ����, �� ����� ��������, ��� ���� ��������� ���������� ������� Rgamma(e, r, k), ����������, � ��������� ������ �������� �� ���������. ��� �������� ������������, ����� �������� ���������� ���������: ��� ��������������, ��� � ������ ��������� ���������� �������, ��������� ������ �� "�������" ������ (����� ������� ������ ������ � ���������� ��������� Rgamma(e,r,k)).

������ ��� �������� ���������� ��������� Rgamma(e, r, k) = q �������� ������ �������� �� �����: ���������, ������� �� q-� ������� � ������ ��������� ������ �� "�������" ������ (� (q-1)-� - �������� "���������"), ����� ��� �����-���� �������������� �������������. �������, ������ ������ ������� 3.3, �� ����� �������� ������� Fgamma(e, r, k, q), ���������� � ������ EA �������� Rgamma(e, r, k) = q. �������

(AeArAk)(Eq)Fgamma(e, r, k, q),

� ����� �������, ����������, ��� Rgamma �������� ����� ������������ ��������, � � ������ �������, ��� ����������� ����. ����� �������, ���� ������ EA ���������������, �� � ��� ���������� �������� ����� �������������� ������� Rgamma (� � ������ ZFC ��� ��� ����� �������).

��� ���� ������������ ���� ������ � ������������ ��������� ����� ������� Rgamma. ��� ������� R(e, r, k) �� �������� ������� ������ ������ ����� ������ (���������), ������ Rgamma ����������� � ���� ������ ������ �����������. ����� ��������, ��� ���� � ������ EA ��������� ����� �������������� ������� f(x), �.�.

EA|- (Ax)(Ey)F(x,y),

��� F(x,y) - �������, �������������� � EA ������� f, ��

ZFC |- (Ex0)(Ax>x0)(f(x)< Rgamma(x, x, x+1)).

����� �������, ������� Rgamma(x, x, x+1) ������ ������� ����� �������, ������������ ������� ����� �������� � ������������ ����������! (��. ��.�����, �.���������� [1977]. )