§ 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.

Розглянемо дві кульові структури B₁=(X₁,P₁,B₁) і B₂=(X₂,P₂,B₂). Відображення f:X₁®X₂ називається -відображенням, якщо для кожного bÎP₂ існує aÎP₁, таке що

B₂(f(x),b) Í f(B₁(x,a))

для кожного xÎX₁. Якщо існує -відображення X₁ на X₂, то покладаємо B₁B₂.

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

f(B₁(x,a))ÍB₂(f(x),b)

для кожного xÎX₁. Якщо існує ін'єктивне -відображення X₁ в X₂, то покладаємо B₁B₂.

Бієкція f:X₁®X₂ називається ізоморфізмом між кульовими структурами B₁, B₂, якщо f є одночасно - відображенням та -відображенням. При цьому B₁, B₂ називаються ізоморфними. Якщо X₁ = X₂ і тотожне відображення f:X₁®X₂ є ізоморфізмом між B₁ і B₂, то кульові структури B₁, B₂ називаються еквівалентними.

Властивість P кульових структур називається кульовою властивістю, якщо кожна кульова структура, ізоморфна до деякої кульової структури з властивістю P, теж має цю властивість.

Приклад 7.1. Нехай (X,d) – метричний простір, R⁺={xÎR: x³0}. Для всіх xÎX, rÎR⁺ покладемо

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

Кульову структуру (X, R⁺, B_d) позначимо 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. Нехай B₁=(X₁,P₁,B₁), B₂=(X₂,P₂,B₂) – кульові структури, f – -відображення X₁ на X₂. Якщо B₁ зв'язна, то B₂ теж зв'язна.

Доведення. Для кожної пари елементів y,zÎX₁ виберемо aÎP₁ так, що yÎB₁(z,a), zÎB₁(y,a). Оскільки f – -відображення, то існує bÎP₂, таке що f(B₁(x,a))ÍB₂(f(x),b) для кожного xÎX₁. Значить, f(y) Î B₂(f(z),b), f(z) Î B₂(f(y),b). Оскільки f(X₁)=X₂ , то B₂ зв’язна.

Лема 7.2. Нехай B₁=(X₁,P₁,B₁), B₂=(X₂,P₂,B₂) – кульові структури, f – ін'єктивне -відображення X₁ в X₂. Якщо B₁ зв’язна, то B₂ теж зв’язна.

Доведення. Для кожної пари y,zÎX₁ виберемо bÎP₂ так, що f(y) Î B₂(f(z),b), f(z) Î B₂(f(y),b). Оскільки f – -відображення, то існує aÎP₁, таке що B₂(f(x),b)Íf(B₁(x,a)) для кожного xÎX₁. Оскільки відображення f ін'єктивне, то yÎB₁(z,a), zÎB₁(y,a). Отже, B₂ зв’язна.

Нехай 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. Нехай B₁=(X₁,P₁,B₁), B₂=(X₂,P₂,B₂) - кульові структури, f:X₁®X₂. Якщо f - відображення B₁ в B₂ то f -відображення B^*₁ в B^*₂ . Якщо f – ізоморфізм між B₁ і B₂, то f – ізоморфізм між B^*₁ і B^*₂ .

Доведення. Нехай f – -відображення B₁ в B₂, aÎP₁. Виберемо bÎP₂ так, що f(B₁(x,a))ÍB₂(f(x),b) для кожного xÎP₁. Візьмемо довільний елемент yÎB^*₁(x,a). Тоді xÎB₁(y,a) і f(x)ÎB₂(f(y),b). Отже, f(y)ÎB^*₂(f(x),b) і f(B^*₁(x,a))ÍB^*₂(f(x),b). Це означає, що f є -відображенням B^*₁ в B^*₂.

Припустимо, що f – ізоморфізм між B₁ і B₂. За доведеним вище, f є -відображенням B^*₁ в B^*₂. , а f^-1 є -відображенням B^*₂ в B^*₁ . Отже, f^-1 – ізоморфізм між B^*₁ і B^*₂ .

Лема 7.4. Нехай B₁=(X₁,P₁,B₁), B₂=(X₂,P₂,B₂) – ізоморфні кульові структури. Якщо B₁ симетрична, то B₂ теж симетрична.

Доведення. Позначимо через f₁ ізоморфізм між B₁ і B₂. Позначимо через i₁: X₁®X₁, i₂: X₂®X₂ тотожні відображення. Очевидно, f ^-1 - ізоморфізм між B₂ і B₁ . За лемою 7.3 f – ізоморфізм між B^*₁ і B^*₂ . За припущенням леми i₁ - ізоморфізм між B₁ і B^*₁. Оскільки i₂=f i₁ f ^-1 , то i₂ – ізоморфізм між B₂ і B^*₂ .

Кульова структура 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. Нехай B₁=(X₁,P₁,B₁), B₂=(X₂,P₂,B₂) – ізоморфні кульові структури. Якщо B₁ мультиплікативна, то B₂ теж мультиплікативна.

Доведення. Позначимо через f: X₁®X₁ ізоморфізм між B₁ і B₂. Зафіксуємо довільні b₁, b₂ ÎP₂. Оскільки f – бієкція, досить довести, що існує b ÎP₂, таке що

B₂(B₂(f(x),b₁),b ₂)Í B₂(f(x,b))

для кожного xÎX₁.

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

B₂(f(x),b₁)Í f (B₁(x,a₁), B₂(f(x),b ₂)Í f(B₁(x,b₂))

для кожного xÎX₁.

Оскільки B₁ мультиплікативна, то існує aÎP₁, таке що B₁(B₁(x,a₁),a₂ )Í B₁(x,a) для кожного xÎX₁.

Оскільки f – -відображення, то існує b ÎP₂, таке що f(B₁(x,a)) ÍB₂(f(x),b ) для кожного xÎX₁.

Зафіксуємо xÎX₁ і візьмемо довільний елемент f(z)ÎB₂(B₂(f(x),b₁),b₂). Знайдемо f(y)ÎB₂(f(x),b₁) для якого f(z)Î B₂(f(y),b₂). Тоді

yÎ B₁(x,a₁), zÎ B₁(y,a₂), zÎ B₁(B₁(x,a₁),a₂).

Отже, zÎ B₁(x,a) і f(z)Î B₂(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 . Зауважимо, що кожна мультиплікативна кульова структура напрямлена. Крім того, конфінальність напрямленої структури £À₀ тоді і тільки тоді, коли існує конфінальна в P послідовність <a_n>_nÎw, така що a₀£a₁£…£a_n £….

Лема 7.7. Якщо кульові структури B₁=(X₁,P₁,B₁), B₂=(X₂,P₂,B₂) ізоморфні, то cf B₁=cf B₂.

Доведення. Позначимо через f: X₁®X₁ ізоморфізм між B₁ і B₂. Візьмемо довільну конфінальну підмножину P₁ÍP. Оскільки f є – -відображенням, то існує відображення h₁: P₂®P'₁ , таке що

B₂(f(x),b)Í f (B₁(x,h₁(b))

для всіх xÎX₁, b ÎP₂. Оскільки f є -відображення, то існує відображення h₂: P'₁® P₂, таке що

f (B₁(x,a)ÍB₂(f(x),h₂(a))

для всіх xÎX₁, a ÎP'₁. За визначенням відображень h₁, h₂ підмножина h₂ (P'₁) конфінальна в P'₂. Отже, cf B₂ £ cf B_1.

Теорема 7.1. Кульова структура B=(X,P,B) метризована тоді і тільки тоді, коли B зв’язна, симетрична, мультиплікативна і

cf B£ À₀.

Доведення. Спочатку припустимо, що B ізоморфна кульовій структурі B=(X,a) деякого метричного простору (X,d). Очевидно, що B(X,d) симетрична, зв’язна, мультиплікативна і cf B£À₀. Враховуючи леми 1,4,6,7, можна стверджувати, що B має всі ці властивості.

Припустимо, що B зв’язна, симетрична, мультиплікативна і B£ À₀. Зафіксуємо довільну конфінальну в P послідовність <a_n>_nÎw. Покладемо b₀=a₀ і виберемо b₁ÎP так, що

b₁³a₁, b₁³ b₀, b₁³ g(b₀, b₀)

де g – функція з означення мультиплікативності. Припустимо, що ми вже вибрали елементи b₀, b₁,…, 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) і помітимо, що B_d(x,n)=B(x,b_n)Ç B*(x,b_n). Оскільки кульова B симетрична, то тотожне відображення множини X являється ізоморфізмом між B і B(X,d).

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

Задача 7.1. Довести, що для довільної кульової структури B існує метричний простір (X,d), такий що BB(X,d).

Задача 7.2. Нехай B=(X,P,B) – зв’язна мультиплікативна кульова структура, cf B£À₀. Застосовуючи міркування з доведення теореми 7.1, показати, що існує метрика d на X, така що тотожне відображення і: X®X є - відображенням B(X,d) на B.

Для характеризації графових кульових структур введемо ще одне означення.

Нехай B=(X,P,B) – довільна кульова структура, aÎP. Скінченна послідовність x₀, x₁, …, x_n елементів множини X називається a-шляхом довжини n, якщо x_i-1ÎB(x_i,a), x_iÎB(x_i-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. Нехай B₁=(X₁,P₁,B₁), B₂=(X₂,P₂,B₂) – ізоморфні кульові структури. Якщо B₁ p–зв’язна, то B₂ теж p–зв’язна.

Доведення. Нехай f: X₁®X₂ – ізоморфізм між B₁ і B₂. Виберемо aÎP, так що B₁ a-зв'язна і зафіксуємо відповідне відображення m: P₁®w. Оскільки f є -відображенням, то існує bÎP₂, таке що

f(B₁(x,a))Í B₂(f(x),b)

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

B₂(f(x),l) Í f(B₁(x,h(l))

для всіх xÎX₁, lÎP_2.

Зафіксуємо довільний елемент lÎP₂ і припустимо, що f(x)ÎB₂(f(y),l), f(y)ÎB₂(f(x),l). Оскільки f-бієкція, то xÎB₁(y,h(l), yÎB₁(x,h(l). Оскільки B₁ a-зв’язна, то існує a-шлях x=x₀, x₁,…,x_m=y довжини £mh(l). Значить, f(x)=f(x₀),f(x₁), …, f(x_m) 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 позначимо через Fin_e(G) сім'ю усіх скінченних підмножин групи G, що містять одиницю e групи. Для всіх xÎG, FÎFin_e(G) покладемо

B_l(x,F)=Fx, B_r(x,F)=xF.

Кульові структури (G, Fin_e, B_l) і (G, Fin_e, B_r) позначимо B_l (G) і B_r(G). Очевидно, що відображення x® x^-1 є ізоморфізмом між B_l (G) і B_r(G) . Надалі будь-яку з цих двох ізоморфних кульових структур позначаємо B(G). Зауважимо, що B(G) зв’язна, симетрична і мультиплікативна.

Теорема 7.3. Кульова структура B(G) групи G метризована тоді і тільки тоді, коли |G|£À₀.

Доведення випливає з теореми 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ÎFin_e(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. Охарактеризувати кульові структури, ізоморфні кульовим структурам орієнтовних графів.