�� ������ �������
��� ���������� ������������� ����������� ������ � ������� ������� ������������ �������������� ������, ������� � �������� ������ ����� �� ���������������: ������� ������ � �������, ������� ����������-�������, ������� � �������������� ������ �����. ��� ���������� � �� ���������������� ����������� (��� ���������� �������) ������ ����������� � ������ ����������.
��� ��� ������� � ������ �������� � �������� ���������� ������ - � ��� ���������� ������� �������. � ���� ������ ������� ������������ � ������ ������ �������� �����������, ����������� ��� ������ ��������. �������������� ���� �����������, ������� ��������������� ����, ����� ������������� � ������ 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, ������� ������ ������� � ������ ������ ���� �������, ���� �����).
������ ������� ������
��������� ������ "������������" �����������, ������� �������� ���������� �������������� ������� (��� ���� ���������� ��������), � �������� � ��������� ����� �������� ���������� �������: "�� ������ ������ �� �������� �������������� ��������, ������� � ������ ���������, ������� �������� ���� � �����!" ��������� "���������������� �����" ��� ����� ��������� �������� �.����� [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]. )