Maksymalna moc rodziny funkcji

[matmatmm]

Niech \(\displaystyle{ n\in\NN}\) oraz zbiór \(\displaystyle{ S}\) będą ustalone. W zbiorze

\(\displaystyle{ \mathcal Z=\left\{f| f: A\to \{0,1\} \text{ dla pewnego } A\subset S \text{ mocy } n\right\}}\)

(wszystkich funkcji częściowych \(\displaystyle{ S\rightarrow \{0,1\}}\) o dziedzinie będącej zbiorem \(\displaystyle{ n}\)-elementowym) definiujemy relację

\(\displaystyle{ f\sim g :\iff (\exists s\in\mathrm{dom} f \cap \mathrm{dom} g) f(s)\neq g(s).}\)

Niech \(\displaystyle{ \mathcal R\subset \mathcal Z}\) będzie rodziną taką, że \(\displaystyle{ f\sim g}\) dla wszystkich \(\displaystyle{ f,g\in\mathcal R, f\neq g}\).

Jak wykazać, że moc rodziny \(\displaystyle{ \mathcal R}\) nie przekracza \(\displaystyle{ 2^n}\)?

[Dasio11]

Treść zadania wygląda trochę jakby ktoś celowo usunął zeń kontekst teoriomiarowy i zostawił czystą kombinatorykę. Ale skoro nie ma jawnego wymogu by nie używać teorii miary:

Na borelowskich podzbiorach* przestrzeni \(\displaystyle{ 2^S}\) (z topologią produktową) istnieje naturalna miara probabilistyczna, taka że zdarzenia

\(\displaystyle{ A_s = \{ x \in 2^S : x(s) = 0 \}}\), \(\displaystyle{ s \in S}\)

mają prawdopodobieństwo \(\displaystyle{ \frac{1}{2}}\) i są niezależne. Dla dowolnej funkcji częściowej \(\displaystyle{ f : S \multimap \mspace{-2mu} \to \{ 0, 1 \}}\) niech \(\displaystyle{ [f] = \{ x \in 2^S : f \subseteq x \}}\). Widać że dla każdego \(\displaystyle{ f \in \mathcal{Z}}\) zbiór \(\displaystyle{ [f] \subseteq 2^S}\) ma miarę \(\displaystyle{ \frac{1}{2^n}}\). Warunek nałożony na rodzinę oznacza, że \(\displaystyle{ [f] \cap [g] = \varnothing}\) dla różnych \(\displaystyle{ f, g \in \mathcal{Z}}\). Stąd już wynika, że \(\displaystyle{ |\mathcal{Z}| \le 2^n}\).

*Wystarczyłaby tu miara skończenie addytywna na ciele zbiorów generowanym przez \(\displaystyle{ \{ A_s : s \in S \}}\). Można taką skonstruować ręcznie bez trudniejszych narzędzi z teorii miary.

[matmatmm]

Zadanie przyszło tak naprawdę z topologii (Ryszard Engelking, Zarys topologii ogólnej, zadanie 11 s. 86). Chodziło o maksymalną rodzinę rozłączną w kostce \(\displaystyle{ 2^S}\) zbiorów otwartych bazowych będących przekrojem dokładnie \(\displaystyle{ n}\) półprzestrzeni. Wydawało mi się właśnie, że sprowadza się do kombinatoryki. Nie wpadłem na pomysł z miarą.

*Wystarczyłaby tu miara skończenie addytywna na ciele zbiorów generowanym przez \(\displaystyle{ \{ A_s : s \in S \}}\). Można taką skonstruować ręcznie bez trudniejszych narzędzi z teorii miary.

Jak to najprościej zrobić? Czy dobrze myślę, że to ciało generowane składa się ze wszystkich możliwych sum skończonych zbiorów z rodziny

\(\displaystyle{ \mathcal F=\{A_{s_1}^{\varepsilon_1}\cap\dots\cap A_{s_n}^{\varepsilon_n}\colon s_1,\ldots,s_n\in S, \varepsilon_1,\ldots,\varepsilon_n\in\{0,1\}, n\in\NN_0\},}\)

gdzie \(\displaystyle{ A^0=A}\) oraz \(\displaystyle{ A^1=2^S\setminus A}\) ? Wtedy zadałbym miarę przez wzór włączeń i wyłączeń, gdyż znana jest miara na zbiorach z \(\displaystyle{ \mathcal F}\).

Dodano po 4 godzinach 40 minutach 6 sekundach:
Mam lepszy pomysł. Każdy element tego ciała można zapisać nawet jako rozłączną sumę zbiorów z \(\displaystyle{ \mathcal F}\). Wystarczy zatem pokazać, że \(\displaystyle{ \sum_{i=1}^k\mu(F_i)=\sum_{j=1}^m\mu(G_j)}\), o ile \(\displaystyle{ \bigcup_{i=1}^kF_i=\bigcup_{j=1}^mG_j}\) dla \(\displaystyle{ F_i, G_j\in\mathcal F}\).

[Dasio11]

Jak to najprościej zrobić? Czy dobrze myślę, że to ciało generowane składa się ze wszystkich możliwych sum skończonych zbiorów z rodziny

\(\displaystyle{ \mathcal F=\{A_{s_1}^{\varepsilon_1}\cap\dots\cap A_{s_n}^{\varepsilon_n}\colon s_1,\ldots,s_n\in S, \varepsilon_1,\ldots,\varepsilon_n\in\{0,1\}, n\in\NN_0\},}\)

gdzie \(\displaystyle{ A^0=A}\) oraz \(\displaystyle{ A^1=2^S\setminus A}\) ? Wtedy zadałbym miarę przez wzór włączeń i wyłączeń, gdyż znana jest miara na zbiorach z \(\displaystyle{ \mathcal F}\).

Opis ciała jest prawidłowy, ale podejście ze wzorem włączeń i wyłączeń wydaje się raczej karkołomne. Chyba lepiej tak: dowolny element ciała \(\displaystyle{ B}\) daje się przedstawić jako rozłączna suma zbiorów postaci \(\displaystyle{ [f]}\), gdzie \(\displaystyle{ f : S_0 \to \{ 0, 1 \}}\) a \(\displaystyle{ S_0 \subseteq S}\) jest zbiorem skończonym wspólnym dla wszystkich składników sumy. Wtedy definiujemy miarę \(\displaystyle{ B}\) jako liczbę tych składników razy \(\displaystyle{ \frac{1}{2^{|S_0|}}}\). Nietrudno pokazać, że taka definicja nie zależy od przedstawienia \(\displaystyle{ B}\), a potem że jest to probabilistyczna miara skończenie addytywna.


Zadanie można też rozwiązać bez teorii miary: załóżmy nie wprost, że w \(\displaystyle{ \mathcal{Z}}\) jest \(\displaystyle{ 2^n+1}\) różnych funkcji. Niech \(\displaystyle{ D \subseteq S}\) będzie (skończoną) sumą dziedzin tych funkcji i \(\displaystyle{ m = |D|}\). Każda ze wspomnianych funkcji ma dokładnie \(\displaystyle{ 2^{m-n}}\) rozszerzeń do elementu \(\displaystyle{ 2^D}\), a wszystkich elementów \(\displaystyle{ 2^D}\) jest \(\displaystyle{ 2^m}\). Z zasady szufladkowej istnieją różne \(\displaystyle{ f, g \in \mathcal{Z}}\) które mają wspólne rozszerzenie do funkcji w \(\displaystyle{ 2^D}\). Wtedy \(\displaystyle{ f \not \sim g}\), co jest sprzeczne z założeniem.

[matmatmm]

Wtedy definiujemy miarę \(\displaystyle{ B}\) jako liczbę tych składników razy \(\displaystyle{ \frac{1}{2^{|S_0|}}}\). Nietrudno pokazać, że taka definicja nie zależy od przedstawienia \(\displaystyle{ B}\)

Na ten moment nie potrafię sprawdzić, że taka definicja nie zależy od przedstawienia. Miałem pomysł

Mam lepszy pomysł. Każdy element tego ciała można zapisać nawet jako rozłączną sumę zbiorów z \(\displaystyle{ \mathcal F}\). Wystarczy zatem pokazać, że \(\displaystyle{ \sum_{i=1}^k\mu(F_i)=\sum_{j=1}^m\mu(G_j)}\), o ile \(\displaystyle{ \bigcup_{i=1}^kF_i=\bigcup_{j=1}^mG_j}\) dla \(\displaystyle{ F_i, G_j\in\mathcal F}\).

ale potrzebuję sprawdzić najpierw, że jeśli \(\displaystyle{ F_i\in\mathcal F}\) oraz \(\displaystyle{ \bigcup_{i=1}^kF_i=F \in\mathcal F}\) (tzn. suma cylindrów jest cylindrem), to \(\displaystyle{ \mu(F)=\sum_{i-1}^k\mu(F_i)}\), gdzie \(\displaystyle{ \mu(A_{s_1}^{\varepsilon_1}\cap\dots\cap A_{s_n}^{\varepsilon_n})=\frac1{2^n}}\).

[Dasio11]

Na ten moment nie potrafię sprawdzić, że taka definicja nie zależy od przedstawienia.

Niech

\(\displaystyle{ B = \bigcup_{i=1}^n [f_i] = \bigcup_{j=1}^m [g_j]}\),

gdzie \(\displaystyle{ f_i : S_1 \to \{ 0, 1 \}}\), \(\displaystyle{ g_j : S_2 \to \{ 0, 1 \}}\) i każda z sum jest rozłączna. Bez zmniejszania ogólności \(\displaystyle{ S_1 \subseteq S_2}\), bo w przypadku ogólnym można dopisać przedstawienie dla \(\displaystyle{ S_1 \cup S_2}\) i stwierdzić, że daje taki sam wynik jak dwa poprzednie na mocy przypadku szczególnego. Dla każdego \(\displaystyle{ 1 \le j \le m}\) istnieje dokładnie jedno \(\displaystyle{ 1 \le i \le n}\), takie że \(\displaystyle{ [g_j] \subseteq [f_i]}\). Zadane w ten sposób przypisanie \(\displaystyle{ \{ 1, \ldots, m \} \to \{ 1, \ldots, n \}}\) ma wszystkie włókna wielkości \(\displaystyle{ 2^{|S_2 \setminus S_1|}}\) (w szczególności jest surjekcją). Stąd \(\displaystyle{ m = 2^{|S_2 \setminus S_1|} \cdot n}\) i dalej

\(\displaystyle{ n \cdot \frac{1}{2^{|S_1|}} = m \cdot \frac{1}{2^{|S_2|}}}\),

czyli oba przedstawienia zadają tę samą wartość.

Miałem pomysł

...identyczny z moją propozycją, minus wymóg aby wszystkie zbiory w sumie były tej samej wielkości. Brak takiego warunku tylko utrudnia dowód że przypisana wartość nie zależy od wyboru przedstawienia (bo wszystkie przedstawienia to właściwy nadzbiór przedstawień spełniających warunek), dlatego trochę się dziwię że upierasz się przy tym pomyśle. Ale skoro tak wolisz, to potrzebny fakt:

jeśli \(\displaystyle{ F_i\in\mathcal F}\) oraz \(\displaystyle{ \bigcup_{i=1}^kF_i=F \in\mathcal F}\) (tzn. suma cylindrów jest cylindrem), to \(\displaystyle{ \mu(F)=\sum_{i-1}^k\mu(F_i)}\), gdzie \(\displaystyle{ \mu(A_{s_1}^{\varepsilon_1}\cap\dots\cap A_{s_n}^{\varepsilon_n})=\frac1{2^n}}\).

można wykazać indukcyjnie względem \(\displaystyle{ k}\). Krok dla \(\displaystyle{ k > 2}\) wynika z faktu, że gdy cylindry \(\displaystyle{ F_1, F_2 \subseteq F}\) są rozłączne, to jeden z nich jest zawarty w \(\displaystyle{ A_s}\) a drugi w jego dopełnieniu dla pewnego \(\displaystyle{ s \in S}\). Takie \(\displaystyle{ A_s}\) dzieli wtedy \(\displaystyle{ F}\) na dwie połówki, z których każda rozkłada się na mniejszą liczbę (rozłącznych) składników.

[matmatmm]

...identyczny z moją propozycją, minus wymóg aby wszystkie zbiory w sumie były tej samej wielkości. Brak takiego warunku tylko utrudnia dowód że przypisana wartość nie zależy od wyboru przedstawienia (bo wszystkie przedstawienia to właściwy nadzbiór przedstawień spełniających warunek),

To zależy jak prowadzimy ten dowód. Z użyciem faktu

jeśli \(\displaystyle{ F_i\in\mathcal F}\) oraz \(\displaystyle{ \bigcup_{i=1}^kF_i=F \in\mathcal F}\) (tzn. suma cylindrów jest cylindrem), to \(\displaystyle{ \mu(F)=\sum_{i-1}^k\mu(F_i)}\), gdzie \(\displaystyle{ \mu(A_{s_1}^{\varepsilon_1}\cap\dots\cap A_{s_n}^{\varepsilon_n})=\frac1{2^n}}\).

można tak: Niech \(\displaystyle{ \bigcup_{i=1}^kF_i=\bigcup_{j=1}^mG_j}\), gdzie \(\displaystyle{ F_i}\) są rozłącznymi cylindrami oraz \(\displaystyle{ G_j}\) są rozłącznymi cylindrami. Wówczas

\(\displaystyle{ \sum_{i=1}^k\mu(F_i)=\sum_{i=1}^k\mu\left(\bigcup_{j=1}^m(F_i\cap G_j)\right)=\sum_{i=1}^k\sum_{j=1}^m\mu(F_i\cap G_j)=\ldots=\sum_{j=1}^m\mu(G_j)}\).

Zaleta jest taka, że z automatu mamy addytywność miary, która wymaga trochę gimnastyki w przypadku Twojej propozycji.

[Dasio11]

To zależy jak prowadzimy ten dowód.

Nie zależy - każdy prawidłowy dowód dla dowolnych przedstawień jest też prawidłowym dowodem dla przedstawień spełniających warunek, bo te drugie tworzą (właściwy) podzbiór tych pierwszych. W szczególności Twój dowód działa również z moją propozycją (z dodatkowego założenia po prostu się nie korzysta), a mój nie działa z Twoją (bo istotnie korzysta z założenia, którego u Ciebie nie ma).

\(\displaystyle{ \sum_{i=1}^k\mu(F_i)=\sum_{i=1}^k\mu\left(\bigcup_{j=1}^m(F_i\cap G_j)\right)=\sum_{i=1}^k\sum_{j=1}^m\mu(F_i\cap G_j)=\ldots=\sum_{j=1}^m\mu(G_j)}\).

Gwoli ścisłości należałoby jakoś uwzględnić, że niektóre z \(\displaystyle{ F_i \cap G_j}\) mogą być zbiorami pustymi - albo uzupełniając (pre-)definicję \(\displaystyle{ \mu}\) dla cylindrów o punkt \(\displaystyle{ \mu(\varnothing) = 0}\), albo usuwając z każdej sumy indeksy/pary indeksów odpowiadające pustym przekrojom.

Zaleta jest taka, że z automatu mamy addytywność miary, która wymaga trochę gimnastyki w przypadku Twojej propozycji.

Nie wymaga żadnej gimnastyki - wystarczy dowodząc równości \(\displaystyle{ \mu(A \cup B) = \mu(A) + \mu(B)}\) wybrać przedstawienia \(\displaystyle{ A}\) i \(\displaystyle{ B}\) tak by zbiór \(\displaystyle{ S_0}\) był dla nich jednakowy, a wtedy dowód jest taki sam.