§ 8 Комбінаторні розміри підмножин кульових структур

Нехай B=(X,P,B) - кульова структура, А Î X, a Î P. Покладемо

B(A,a)=È a Î A B(a,a), Int (A,a)={x Î X: B*(x,a)Í A}.

Підмножина A називається великою, якщо існує a Î P, таке що X=B(A,a).

Підмножина A називається малою, якщо підмножина X\B(A,a) велика для будь-якого a Î P.

Підмножина A називається надвеликою, якщо підмножина Int(A,a) велика для будь-якого a Î P.

Підмножина A називається кусково великою, якщо існує b Î P, таке що підмножина Int(B(A,b),a) непорожня для будь-якого a Î P.

Лема 8.1. Нехай B=(X,P,B) - кульова структура, А Î X, a Î P. Тоді Int (X\A,a)=X\ B(A,a).

Доведення. Нехай x Î Int(X\A,a). Тоді B*(x,a)Ç A=Æ і x Ï B(a,a) для будь-якого a Î A. Отже, x Î X\B(A,a).

Нехай x Î X\B(A,a). Тоді x Ï B(a,a) для кожного a Î A. Отже, a Ï B*(x,a) для кожного a Î A, B*(x,a)Í X\A і x Î Int(X\A,a).

Лема 8.2. Якщо B=(X,P,B) - мультиплікативна кульова структура і підмножина B(A,a) велика для деякого a Î P, то підмножина A теж велика.

Доведення. Виберемо b Î P так, що B(B(A,a),b)=X. За означенням мультиплікативності знайдеться g(a,b)Î P, таке що B(B(A,a),b)Í B(A,g(a,b)). Отже, B(A,g(a,b))=X.

Теорема 8.1. Для довільної кульової структури B=(X,P,B) і довільної підмножини S Í X наступні твердження 1, 2, 3 еквівалентні. Якщо до того ж B мультиплікативна, то всі чотири твердження еквівалентні

1. S мала;

2. S не являється кусково великою;

3. X\S надвелика;

4. (X\S)Ç L велика для кожної великої підмножини L Í X.

Доведення. 1 Þ 2. Для кожного a Î P виберемо b(a)Î P так, що B(X\B(S,a), b(a))=X. Візьмемо довільний елемент x Î X і виберемо y Î X\B(S,a), такий що x Î B(y,b(a)). Тоді y Î B*(x,b(a)) і B*(x,b(a)) Ç (X\B(S,a) ¹ Æ. Отже, Int(B(S,a),b(a))=Æ і S не є кусково великою.

2 Þ 3. Для кожного a Î P виберемо b(a)Î P, таке що Int(B(S,a),b(a))=Æ. Тоді B*(x,b(a)) Ç (X\B(S,a) ¹ Æ для кожного x Î X. За лемою 8.1

B*(x, b(a)) Ç Int(X \ S,a) ¹ Æ

для кожного x Î X. Значить, X=B(Int(X\S,a), b(a)) і підмножина X\S надвелика.

3 Þ 1. Для кожного a Î P виберемо b(a)Î P так, що B(Int(X\S,a), b(a))=X. За лемою 8.1 B(X\B(S,a), b(a))=X. Отже, підмножина S мала.

3 Þ 4. Позначимо Y=X\S і візьмемо довільну велику підножину L. Виберемо a Î P так, що X=B(L,a). Для кожного x Î Int(Y,a) виберемо y(x)Î L, такий що x Î B(y(x),a), еквівалентно, y(x)Î B*(x,a). Покладемо Y'={y(x): x Î Int(Y\a)} і помітимо, що Y'Í Y Ç L. Оскільки Int(Y\a)Í B(Y',a) і підмножина Int(Y\a) велика, то B(Y',a) велика. За лемою 8.2 Y' велика. Оскільки Y'Í Y Ç L, то Y Ç L велика.

4 Þ 3. Покладемо Y=X\S. Оскільки Y Ç X=Y і підмножина X велика, то Y теж велика. Зафіксуємо a Î P і покажемо, що підмножина Int(Y\a) велика. Для кожного x Î Y\Int(Y,a) виберемо y(x)Î B*(x,a)\Y. Покладемо Y'={y(x): x Î Y\Int(Y,a)}, L=Y'È Int(Y,a). Помітимо, що Y Í B(L,a). Оскільки підмножина Y велика, то підмножина B(L,a) теж велика. За лемою 8.2 підмножина L велика. За умовою підмножина Y Ç L велика. Оскільки Y Ç L=Int(Y\a), то підмножина Int(Y,a) велика.

Теорема 8.2. Нехай B=(X,P,B)- мультиплікативна кульова структура. Якщо підмножини X1, X2, …, Xn множини X надвеликі, то підмножина X1 Ç X2 Ç …Ç Xn теж надвелика. Якщо підмножини X1, X2, …, Xn множини X малі, то підмножина X1 È X2 È …È Xn теж мала. Якщо кусково велику підмножину A множини X розбито на скінченне число підмножин A=A1 È A2 È…È An, то принаймні одна підмножина Ai розбиття кусково велика. Зокрема, множину X не можна розбити на скінченне число малих підмножин.

Доведення. Візьмемо довільну велику підмножину L множини X. З еквівалентності 3 Þ 4 теореми 8.1 випливає, що підмножина Xn Ç L велика. Оскільки (X1 Ç X2 Ç …Ç Xn)Ç L=(X1 Ç X2 Ç …Ç Xn-1)Ç(Xn Ç L), то по індукції підмножина (X1 Ç X2 Ç …Ç Xn)Ç L велика. З еквівалентності 3 Þ 4 випливає, що підмножина X1 Ç X2 Ç …Ç Xn надвелика. Друге твердження теореми випливає з першого і еквівалентності 1 Þ 3 теореми 8.1. Третє твердження випливає з другого і еквівалентності 1 Þ 2 теореми 8.1.

Нагадаємо означення фільтра і ультрафільтра. Сім'я Á підмножини множини X називається фільтром, якщо

(і) Æ Ï Á, X Î Á;

(іі) якщо F Î Á і F Í F' , то F'Î Á ;

(ііі) якщо F1,F2,…, Fn Î Á , то F1 Ç F2 Ç…Ç Fn Î Á .

Множина всіх фільтрів на фіксованій множині X частково впорядкована за включенням. Фільтр, максимальний відносно цього порядку, називається ультрафільтром. Користуючись аксіомою вибору, кожен фільтр можна доповнити до ультрафільтру. Критерій ультрафільтра такий: фільтр Á являється ультрафільтром тоді і тільки тоді, коли для кожної підмножини A Í X виконується одна з двох умов A Î Á, X\A Î Á.

Для мультиплікативної кульової структури B=(X,P,B) позначимо через j(B) сім'ю всіх надвеликих підмножин множини X. З теореми 8.2 випливає, що j(B) - фільтр.

Теорема 8.3. Нехай B=(X,P,B) - мультиплікативна кульова структура, y - ультрафільтр на X, Тоді j(B)Í y тоді і тільки тоді, коли кожна підмножина A Î y кусково велика.

Доведення. Припустимо, що j(B)Í y і візьмемо довільну підмножину A Î y. Припустимо, що A не є кусково великою. За еквівалентністю 1 Û 2 теореми 8.1 підмножина А мала. За еквівалентністю 1 Û 3 теореми 8.1 підмножина X\А надвелика. Отже, X\А Î j(B) що суперечить означенню фільтра.

Припустимо, що кожна підмножина A Î y кусково велика, але j(B)Ë y . Візьмемо довільну підмножину Y Î j(B), Y Ï y. Оскільки y - ультрафільтр, X\A Î y. За еквівалентністю 1 Û 3 теореми 8.1 підмножина X\Y мала, що суперечить еквівалентності 1 Û 2 теореми 8.1.

Для кульової структури B=(X,P,B) позначимо через сім'ю всіх великих підмножин множини X. Підмножина A Í X називається -щільною, якщо A Ç L ¹ Æ для кожної великої підмножини L. Кульова структура B називається w-розкладною, якщо X можна розбити на зліченне число - щільних підмножин.

Теорема 8.4. Нехай B=(X,P,B) - кульова структура. Припустимо, що існують конфінальна лінійно впорядкована послідовність <a n>n Î w елементів множини P і послідовність <xn>n Î w елементів множини X, такі що сім'я куль {B*(xn,a n): n Î w} диз'юнктна. Тоді кульова структура B w-розкладна.

Доведення. Розіб'ємо множину w на зліченне число нескінченних підмножин w=È k Î w Wk. Досить довести, що підмножина Ak=B*(xn, a n) є -щільною для кожного k Î w. Візьмемо довільну велику підмножину L Í X і виберемо a Î P так, що X=B(L,a) . Виберемо n Î Wk, для якого a n >a. Оскільки X=B(L,a n), то xn Î B(L,a n) і B*(xn,a n)Ç L ¹ Æ. Отже, L Ç Ak ¹ Æ.

Теорема 8.5. Нехай B=(X,P,B) - кульова структура, така що множина X нескінченна і кулі B(x,a), B*(x,a) скінченні для всіх x Î X, a Î P. Якщо існує конфінальна лінійно впорядкована послідовність <a n>n Î w елементів множини P, то кульова структура B w-розкладна.

Доведення. Для того, щоб скористатись теоремою 8.4 побудуємо індуктивно послідовність <xn>n Î w елементів множини X, для якої сім'я куль {B*(xn,a n): n Î w } диз'юнктна. Виберемо довільний елемент x0 Î X. Припустимо, що вже визначені елементи x0, x1, …, xn так, що кулі B*(x0,a 0), B*(x1,a 1), …, B*(xn,a n) попарно не перетинаються. Позначимо Y= B*(x0,a 0)È B*(x1,a 1)È …È B*(xn,a n). За умовою теореми підмножина B(Y,a n+1) скінченна. Виберемо довільний елемент xn+1 Î X\B(Y,a n+1). Тоді B*(xn+1,a n+1)Ç Y=Æ.