§ 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, то покладаємо B1 B2.

Відображення f: X1 ® X2 називається -відображенням, якщо для кожного a Î P1 існує b Î P2 , таке що

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

для кожного x Î X1. Якщо існує ін'єктивне -відображення X1 в X2, то покладаємо B1 B2.

Бієкція 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 Î P 1. Виберемо b Î P 2 так, що f(B1(x,a))Í B2(f(x),b) для кожного x Î P 1. Візьмемо довільний елемент 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. Зафіксуємо довільні b 1, b 2 Î P2. Оскільки f – бієкція, досить довести, що існує b Î P2, таке що

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

для кожного x Î X1.

Оскільки f – -відображення, то існують a 1,a 2 Î P1, такі що

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

для кожного x Î X1.

Оскільки B1 мультиплікативна, то існує a Î P1, таке що B1(B1(x,a 1),a 2 )Í 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),b 1),b 2). Знайдемо f(y)Î B2(f(x),b 1) для якого f(z)Î B2(f(y),b 2). Тоді

y Î B1(x,a 1), z Î B1(y,a 2), z Î B1(B1(x,a 1),a 2).

Отже, 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 послідовність <a n>n Î w, така що a 0£a 1£…£a n £….

Лема 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 Î P 2. Оскільки 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 послідовність <a n>n Î w. Покладемо b 0=a 0 і виберемо b 1 Î P так, що

b 1 ³ a 1, b 1 ³ b 0, b 1 ³ g(b 0, b 0)

де g – функція з означення мультиплікативності. Припустимо, що ми вже вибрали елементи b 0, b 1,…, b n. Виберемо елемент b n+1 Î P так, що

b n+1 ³ a n+1 , b n+1 ³ b n, b n+1 ³ g(b i, b j)

для всіх i,j Î{0, 1, …, n}. Тоді <b n>n Î w – неспадна конфінальна послідовність в P і

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

для всіх x Î X, n,m Î N.

Визначимо відображення d: X´X ®w за таким правилом: d(x,x)=0 і

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

для всіх різних елементів x,y Î X. Оскільки послідовність <b n>n Î w конфінальна в P і B зв’язна, то відображення d визначено коректно. Для того, щоб переконатись у тому, що d – метрика, досить перевірити нерівність трикутника. Нехай x, y, z – різні елементи множини X, d(x,y)=n, d(y,z)=m. Оскільки, y Î B(z,b m) , x Î B(y,b n) то x Î B(B(z,b m),b n)Í B(z,b n+m). Звідси випливає, що d(x,z)£n+m.

Розглянемо кульову структуру B(X,d) і помітимо, що Bd(x,n)=B(x,b n)Ç B*(x,b n). Оскільки кульова B симетрична, то тотожне відображення множини X являється ізоморфізмом між B і B(X,d).

Зауважимо, що побудована метрика цілочисельна.

Задача 7.1. Довести, що для довільної кульової структури B існує метричний простір (X,d), такий що B B(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: X 1®X 2 – ізоморфізм між B1 і B2. Виберемо a Î P, так що B1 a-зв'язна і зафіксуємо відповідне відображення m: P 1®w. Оскільки f є -відображенням, то існує b Î P2, таке що

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

для кожного x Î X1. Оскільки f є -відображенням, то існує відображення h: P 2®P 1. , таке що

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

для всіх x Î X1, l Î P 2.

Зафіксуємо довільний елемент l Î P 2 і припустимо, що f(x)Î B 2(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 довжини £m h(l). Значить, f(x)=f(x0),f(x1), …, f(xm) b-шлях довжини £m h(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. Охарактеризувати кульові структури, ізоморфні кульовим структурам орієнтовних графів.