§ 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) - кульова структура. Припустимо, що існують конфінальна лінійно впорядкована послідовність <an>nÎw елементів множини P і послідовність <xn>nÎw  елементів множини X, такі що сім'я куль {B*(xn,an): nÎw} диз'юнктна. Тоді кульова структура B w-розкладна.

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

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

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