� 7 ������ ���������

 

������� ��������� � �� ����� B=(X,P,B), �� X,P � ��������� ������� � ��� ��� xÎX, aÎP, B(x,a) � ��������� ������� X, �� ���������� ����� ������ a � ������� � ����� x. ��� ����� ����������, ��� xÎB(x,a) ��� ��� xÎX, aÎP.

���������� �� ������ ��������� B1=(X1,P1,B1) � B2=(X2,P2,B2). ³���������� f:X1�X2 ���������� -������������, ���� ��� ������� bÎP2 ���� aÎP1, ���� ��

B2(f(x),b) Í f(B1(x,a))

��� ������� xÎX1. ���� ���� -����������� X1 �� X2, �� ��������� B1B2.

³���������� f: X1 � X2 ����������� -������������, ���� ��� ������� aÎP1 ����� bÎP2 , ���� ��

f(B1(x,a))ÍB2(f(x),b)

��� ������� xÎX1. ���� ���� ��'������� -����������� X1 � X2, �� ��������� B1B2.

������� f:X1�X2 ����������� ������������ �� ��������� ����������� B1, B2, ���� f � ��������� - ������������ �� -������������. ��� ����� B1, B2 ����������� �����������. ���� X1 = X2 � ������� ����������� f:X1�X2 � ������������ �� B1� � B2, �� ������ ��������� B1, B2� ����������� �������������.

���������� P �������� �������� ���������� �������� ����������, ���� ����� ������� ���������, ��������� �� ����� ������� ��������� � ���������� P, ��� �� �� ����������.

������� 7.1. ����� (X,d) � ��������� ������, R+={xÎR: x³0}. ��� ��� xÎX, rÎR+ ����������

Bd(x,r) = {yÎX: d(x,y)£ r}.

������� ��������� (X, R+, Bd) ��������� B(x,d).

������� 7.2. ����� Gr(V,E) � �������� ����. ��� ��� xÎX, rÎR+ ���������

B(x,r) = {yÎV: d(x,y)£ r}.

������� ��������� (V, R+, B) ����������� B(Gr).

������� ��������� B ���������� ������������, ���� B ��������� ������� �������� B(X,d) ������� ���������� �������� (X,d). ������� ��������� B ���������� ��������, ���� B ��������� ������� �������� B(Gr) ������� �������� ����� Gr.

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

������� ��������� B=(X,P,B) ���������� �������, ���� ��� ����-��� ���� x,yÎX ���� aÎP, ���� �� yÎB(x,a), xÎB(y,a).

���� 7.1. ����� B1=(X1,P1,B1), B2=(X2,P2,B2) � ������ ���������, f � -����������� X1� �� X2. ���� B1 ��'����, �� B2 ��� ��'����.

���������. ��� ����� ���� �������� y,zÎX1 ��������� aÎP1 ����, �� yÎB1(z,a), zÎB1(y,a). ������� f � -�����������, �� ���� bÎP2, ���� �� f(B1(x,a))ÍB2(f(x),b) ��� ������� xÎX1. �������, f(y) Î B2(f(z),b), f(z) Î B2(f(y),b). ������� f(X1)=X2 , �� B2 �������.

���� 7.2. ����� B1=(X1,P1,B1), B2=(X2,P2,B2) � ������ ���������, f �� ��'������� -����������� X1 � X2. ���� B1� �������, �� B2 ��� �������.

���������. ��� ����� ���� y,zÎX1 �������� bÎP2 ���, �� f(y) Î B2(f(z),b), f(z) Î B2(f(y),b). ������� f � -�����������, �� ���� aÎP1, ���� �� B2(f(x),b)Íf(B1(x,a)) ��� ������� xÎX1. ������� ����������� f ��'�������, �� yÎB1(z,a), zÎB1(y,a). ����, B2� ������.

����� B=(X,P,B) � ������� ������� ���������. ��� ��� xÎX, aÎP ���������

B*(x,a)={yÎX: xÎB(y,a)}.

������� ��������� B*=(X,P,B*) ���������� �������� �� B. ���������, �� B**=B.

������� ��������� B=(X,P,B)� ���������� �����������, ���� ������ ��������� B, B* �����������. ����, B ���������� ��� � ����� ���, ���� ��� ������� aÎP ���� bÎP, ���� �� B(x,a)Í B*(x,b), � ������� ��� ������� aÎP� ���� bÎP, ���� �� B*(x,a)Í B(x,b).

���� 7.3. ����� B1=(X1,P1,B1), B2=(X2,P2,B2) - ������ ���������, f:X1�X2. ���� f - ����������� B1 � B2 �� f -����������� B*1 ��� B*2 . ���� f � ���������� �� B1 �� B2, �� f � ���������� �� B*1 �� B*2 .

���������. ����� f � -����������� B1 � B2, aÎP1. �������� bÎP2 ���, �� f(B1(x,a))ÍB2(f(x),b)� ��� ������� xÎP1. ³������ �������� ������� yÎB*1(x,a). ��� xÎB1(y,a) � f(x)ÎB2(f(y),b). ����, f(y)ÎB*2(f(x),b) � f(B*1(x,a))ÍB*2(f(x),b). �� ������, �� f � -������������ B*1 ��� B*2.

����������, �� f � ���������� �� B1 �� B2. �� ��������� ����, f � -������������ B*1 ��� B*2. , � f-1 � -������������ B*2� � B*1 . ����, f-1 �� ���������� �� B*1 �� B*2 .

���� 7.4. ����� B1=(X1,P1,B1), B2=(X2,P2,B2) � ��������� ������ ���������. ���� B1 ����������, �� B2 ��� ����������.

���������. ��������� ����� f1 ���������� �� B1 � B2. ��������� ����� i1: X1�X1, i2: X2�X2 ������� �����������. ��������,� f -1 - ���������� �� B2� � B1 . �� ����� 7.3 f � ���������� �� B*1 �� B*2 . �� ����������� ���� i1 - ���������� �� B1 � B*1. ������� i2=f i1 f -1 , �� i2 � ���������� �� B2 � B*2 .

������� ��������� B=(X,P,B) ���������� ����������������, ���� ��� ����-���� a ,b ÎP� ���� g (a,b)ÎP, ���� ��

B(B(x,a),b )Í B(x,g (a,b))

��� ������� xÎX. ����� B(A,a), AÍX, aÎP ���������� .

��������� ���� 7.5. ���� ������� ��������� B=(X,P,B)� ���������������, �� B* ��� ���������������.

��������� ���������. ��� ����� ���� a,bÎP ���������� g (a,b) ���, �� B(B(x,a),b)ÍB(x,g (a,b)). ³������ �������� ������� zÎB*(B*(x,a),b) � �������� ������� yÎB*(x,a) ����� �� zÎB*(y,b). ��� xÎB(y,a), yÎB(z,b). ����, xÎB(B(z,b),a). ������� B(B(z,b),a)ÍB(z,g(b,a)), �� xÎB(z,g(b,a)). ����, B*(B*(x,a),b )Í B*(x,g (b,a)) � B* ���������������.

��������� ���� 7.6. ����� B1=(X1,P1,B1), B2=(X2,P2,B2) � ��������� ������ ���������. ���� B1 ���������������, �� B2 ��� ���������������.

��������� ���������. ��������� ����� f: X1�X1� ���������� �� B1 � B2. ��������� ������� b1, b2 ÎP2. ������� f � ᳺ����, ������ �������, �� ���� b ÎP2, ���� ��

B2(B2(f(x),b1),b 2)Í B2(f(x,b))

��� ������� xÎX1.

��������� ������� f �� -�����������, �� �������� a1,a2ÎP1, ��� ��

B2(f(x),b1)Í f (B1(x,a1),��� B2(f(x),b 2)Í f(B1(x,b2))

��� ������� xÎX1.

��������� ������� B1 ���������������, �� ���� aÎP1, ���� �� B1(B1(x,a1),a2 )Í B1(x,a) ���� ������� xÎX1.

��������� ������� f �� -�����������, �� ���� b ÎP2, ���� �� f(B1(x,a)) ÍB2(f(x),b ) ��� ������� xÎX1.

��������� ��������� xÎX1 � ������� �������� ������� f(z)ÎB2(B2(f(x),b1),b2). �������� f(y)ÎB2(f(x),b1) ��� ����� f(z)Î B2(f(y),b2). ���

yΠB1(x,a1),�� zΠB1(y,a2),�� zΠB1(B1(x,a1),a2).

��������� ����, zΠB1(x,a) � f(z)ΠB2(f(x),b).

��������� ��������, �� ������������ £ �� ������� X � �� ������ ���������, ��� ����� x£ x � � x£ y, y£ z� �������, �� x£ z .

��������� ��� ������� ��������� B=(X,P,B) ��������� ������������ £ �� ������� P �� ����� �������� a£b ��� � ����� ���, ���� B(x,a)Í B(x,b) ��� ������� xÎX. ϳ�������� P'ÍP ���������� ������������, ���� ��� ������� a Î P ���� bÎ P', ���� �� a£b. �������������� cf B � �� �������� ���������� ������������ �������� ������� P.

��������� ������� ��������� B=(X,P,B) ���������� �����������, ���� ��� ����-���� a, b ÎP ���� gÎP ���� �� g³a, g³b . ���������, �� ����� ��������������� ������� ��������� ����������. ��� ����, �������������� ���������� ��������� £À0 ��� � ����� ���, ���� ���� ����������� � P ������������ <an>nÎw, ���� �� a0£a1£ï¿½£an £ï¿½.

��������� ���� 7.7. ���� ������ ��������� B1=(X1,P1,B1), B2=(X2,P2,B2) ���������, �� cf B1=cf B2.

��������� ���������. ��������� ����� f: X1�X1 ���������� �� B1 � B2. ³������ ������� ����������� ��������� P1ÍP. ������� f � � -������������, �� ���� ������������ h1: P2�P'1 , ���� ��

B2(f(x),b)Í f (B1(x,h1(b))

��� ��� xÎX1, b ÎP2. ������� f � -�����������, �� ���� ����������� h2: P'1� P2, ���� ��

f (B1(x,a)ÍB2(f(x),h2(a))

��� ��� xÎX1, a ÎP'1. �� ����������� ���������� h1, h2 ���������� h2 (P'1) ����������� � P'2. ����, cf B2 £ cf B1.

��������� ������� 7.1. ������� ��������� B=(X,P,B) ����������� ��� � ����� ���, ���� B ������, ����������, ��������������� �

cf B£ À0.

��������� ���������. �������� ����������, �� B ��������� ������� �������� B=(X,a) ������� ���������� �������� (X,d). ��������, �� B(X,d) ����������, �������, ��������������� � cf B£À0. ���������� ���� 1,4,6,7, ����� ������������, �� B �� �� �� ����������.

����������, �� B ������, ����������, ��������������� � B£ À0. ��������� ������� ����������� � P ������������� <an>nÎw. ��������� b0=a0 � �������� b1ÎP ����, ���

b1³a1,� b1³ b0,� b1³ g(b0, b0)

�� g � ������� � ��������� �����������������. ����������, �� �� ��� ������� ��������� b0, b1,�, bn. �������� ������� bn+1ÎP ���, ��

bn+1³an+1 , bn+1³bn, bn+1³g(bi, bj)

��� ��� i,jÎ{0, 1, �, n}. ��� <bn>nÎw � �������� ����������� ������������ � P �

B(B(x,bn),b m)Í B(x,bn+m)

��� ��� xÎX, n,mÎN.

��������� ��������� ����������� d: X´X �w� �� ����� ��������: d(x,x)=0� �

d(x,y)=min {nÎ N: yÎB(x,bn) , xÎ B(y,bn)}

��� ��� ����� �������� x,yÎX. ������� ������������ <bn>nÎw ����������� � P � B ������, �� ����������� d ��������� ��������. ��� ����, ��� ������������ � ����, �� d � �������, ������ ��������� ��������� ����������. ����� x, y, z � ���� �������� ������� X, d(x,y)=n, d(y,z)=m. �������, yÎB(z,bm) , xÎ B(y,bn) �� xÎ B(B(z,bm),b n)Í B(z,bn+m). ����� �������, �� d(x,z)£n+m.

��������� ���������� ������� ��������� B(X,d) � �������, �� Bd(x,n)=B(x,bn)Ç B*(x,bn). ������� ������� B ����������, �� ������� ����������� ������� X ��������� ������������ �� B � B(X,d).

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

��������� ������ 7.1. �������, �� ��� ������� ������� ���������� B ���� ��������� ������ (X,d), ����� �� BB(X,d).

��������� ������ 7.2. ����� B=(X,P,B) � ������� ��������������� ������� ���������, cf B£À0. ������������ ��������� � ��������� ������� 7.1, ��������, �� ���� ������� d �� X, ���� �� ������� ����������� �: X�X � - ������������ B(X,d) �� B.

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

��������� ����� B=(X,P,B) � ������� ������� ���������, aÎP. �������� ������������ x0, x1, �, xn �������� ������� X ���������� a-������ ������� n, ���� xi-1ÎB(xi,a), xiÎB(xi-1,a) ��� ������� iÎ{1,2,�,n}. ������� ��������� B ���������� a � �������, ���� ��� ����-����� bÎP ���� m(b)Îw, ���� �� �� xÎB(y,b), yÎB(x,b) ������� ��������� a-����� ������� £m(b) �� x � y. ���������, �� B(Gr) 1-������ ��� ����-����� �������� ����� Gr.

��������� ������� ��������� B=(X,P,B) ���������� p��������, ���� B a-��'���� ��� ������� aÎP.

��������� ���� 7.8. ����� B1=(X1,P1,B1), B2=(X2,P2,B2)� � ��������� ������ ���������. ���� B1� ��p�������, �� B2 ��� ��p�������.

��������� ���������. ����� f: X1�X2� � ���������� �� B1 �� B2. �������� aÎP, ��� �� B1 a-��'���� � ��������� �������� ����������� m: P1�w. ������� f � -������������, �� ���� bÎP2, ���� ��

f(B1(x,a))Í B2(f(x),b)

��� ������� xÎX1. ������� f � -������������, �� ���� ����������� h: P2�P1. , ���� ��

B2(f(x),l) Í f(B1(x,h(l))

��� ��� xÎX1, lÎP2.

��������� ��������� �������� ������� lÎP2 � ����������, �� f(x)ÎB2(f(y),l), f(y)ÎB2(f(x),l). ������� f-ᳺ����, �� xÎB1(y,h(l), yÎB1(x,h(l). ������� B1 a-������, �� ���� a-���� x=x0, x1,�,xm=y� ������� £mh(l). �������, f(x)=f(x0),f(x1), �, f(xm) �b-���� ������� £mh(l) �� f(x) � f(y).

��������� ������� 7.2. ��� ������� ������� ��������� B �������� ���������� �����������

(�) B ����������� � p-�������;

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

��������� ���������. (��) Þ (�). ����� Gr � ��'����� ����. ��������, �� ������� ��������� B(Gr) ����������� � �������. �� ����� 8 ����-��� ������� ���������, ��������� B(Gr) ��� p-�������.

��������� (�) Þ (�i). ��������� p-������� ��������� ������ (X,d), ����� �� B ��������� B(X,d). �������� mÎw ���, �� ������ (X,d) m-��������. ���������� ���� Gr(X,E) � �������� ����� E, ���������� �� ����� �������� (x,y)ÎE ��� � ����� ���, ���� x¹y � d(x,y)£ m. ������� ������� ��������� B(X,d) p-������, �� ���� Gr �������.

��������� ����� d' � ������� �� ����� Gr . �� �����������, ��� ������� nÎw ���� m(n)Îw , ���� �� � ����� d(x,y)£ n ������� d'(x,y)£ m(n). � ������ ����, � ����� d'(x,y)£ k ������� d(x,y)£ km. �������, ������� ����������� ������� X ��������� ������������ �� ��������� ����������� B(X,d)� �� B(Gr).

��������� ������ 7.3. ������� ������� ���������� �������� (X,d), ��� ����� ������� ��������� B(X,d) �� � ��������.

��������� ������� 7.3. ��� ������� ����� G ��������� ����� Fine(G) ��'� ��� ��������� �������� ����� G, �� ������ ������� e �����. ��� ��� xÎG, FÎFine(G)� ���������

Bl(x,F)=Fx,�� Br(x,F)=xF.

��������� ������ ��������� (G, Fine, Bl) � (G, Fine, Br) ��������� Bl (G) � Br(G). ��������, �� ����������� x� x-1 � ������������ �� Bl (G)� � Br(G) . ����� ����-��� � ��� ���� ���������� �������� �������� ��������� B(G). ���������, �� B(G) ������, ���������� � ���������������.

��������� ������� 7.3. ������� ��������� B(G) ����� G ����������� ��� � ����� ���, ���� |G|£À0.

��������� ������� � ������� 7.1.

��������� ������� 7.4. ��� ������� ����� G �������� ��� ���������� ����������:

(�) ����� G �������� ���������;

(��) ������� ��������� B(G) �������.

��������� ���������. (�) Þ (�i). ��������� ����� S �������� ������� ������ ����� G. ���������� ���� ��� Gr(G,E) ����� G, ���������� �������� ������ S È S-1. �� ���������� (x,y)ÎE ��� � ����� ���, ���� x¹y � x=ty ��� ������� tÎS È S-1. ��������, �� ������� ����������� G � G � ������������� ��� B(G)� �� B(Gr) .

��������� (��) Þ (�). �� �������� 7.2 ���� FÎFine(G), ���� �� B(G) � F-�������. �������, ��� ������� �������� gÎG ���� F-���� �� e �� g. �� ������, �� �������� ��������� F ������� ����� G.

��������� �������� 7.1. ���������������� ������ ���������, ��������� �������� ���������� ����.

��������� � ������ ��������� ������ Gr(V,E) ��������� ���'����� ��

������ ��������� (Gr) = (V,w,) � (Gr) = (V,w,) �� (Gr) (�������� (Gr)) - �� ������� ��� ������ yÎV, ��� ���� ���� ��������� ���� �� x �� y (�������� �� y �� x ) ������� £ m.

��������� �������� 7.2. ���������������� ������ ���������, ��������� �������� ���������� ��������� ������.