Несогласованные пометки

[AGu]

Рассмотрим произвольное множество (не обязательно счетное)

и условимся называть его элементы клетками.

Пометкой будем называть конечный набор клеток,

каждая из которых помечена либо крестиком, либо ноликом.

Две пометки назовем несогласованными, если существует клетка,

помеченная в одной пометке крестиком, а в другой — ноликом.

Доказать, что любое множество попарно несогласованных пометок счетно.

Чтобы снять возможные двусмысленности, привожу формальную версию.

Пусть $X$ — произвольное множество.
Положим $\Pi=\{(A,B):A,B\subseteq X,\ |A|,|B|<|\mathbb N|,\ A\cap B=\varnothing\}$.
Для $\pi=(A,B)\in\Pi$ и $\pi'=(A',B')\in\Pi$

будем писать $\pi\between\pi'$, если $A\cap B'\ne\varnothing$ или $A'\cap B\ne\varnothing$.

Пусть $P\subseteq\Pi$ и пусть $\pi\between\pi'$ для всех $\pi,\pi'\in P$, $\pi\ne\pi'$.
Тогда $|P|\leqslant|\mathbb N|$.

[RIP]

Докажем индукцией по $n\in\mathbb N$, что для любого множества $P$ попарно несогласованных пометок множество $P_n:=\{(A,B)\in P\mid|A|+|B|\le n\}$ конечно.
Допустим, что $P_n$ бесконечно, $(A_0,B_0)\in P_n$. Без потери общности можно считать, что множество $P':=\{(A,B)\in P_n\mid A_0\cap B\ne\varnothing\}$ бесконечно. Тогда найдётся $a\in A_0$, что множество $P'':=\{(A,B)\in P_n\mid a\in B\}$ бесконечно. Тогда множество $P''':=\{(A,B\setminus\{a\})\mid(A,B)\in P''\}=P'''_{n-1}$ бесконечно, и в нём все пометки попарно несогласованны, что противоречит индукционному предположению.

(Оффтоп)

На самом деле эти грубые рассуждения показывают, что $M_n\le nM_{n-1}+1$, где $M_n=\max_P|P_n|$. Насколько это можно улучшить?
Хмм, не является ли тривиальная оценка $M_n\ge2^n$ точной? Надо как-нить нерво $M_n\le M_{n-1}+M_{n-2}+\ldots+M_0+1$ докть.

[AGu]

Поздравляю, RIP!

Теперь я могу раскрыть карты.
В этой задаче зашифровано утверждение о том, что
топология тихоновской степени $\{0,1\}^X$ имеет счетный тип
(т.е. любое множество попарно непересекающихся
открытых подмножеств $\{0,1\}^X$ счетно).
Это утверждение, в свою очередь, вытекает из того факта, что
топология тихоновского произведения сепарабельных пространств
имеет счетный тип [Энгелькинг, 2.3.18].

К упомянутому утверждению наша задача сводится так.
Для $(A,B)\in\Pi$ положим $F(A,B)=\bigl\{f\in\{0,1\}^X:f|_A\equiv0,\ f|_B\equiv1\bigr\}$.
Как легко видеть, $(A,B)\between(A',B')$ равносильно $F(A,B)\cap F(A',B')=\varnothing$.
Осталось заметить, что $\{F(A,B):(A,B)\in\Pi\}$ — база топологии $\{0,1\}^X$.

[Профессор Снэйп]

RIP в сообщении #275300 писал(а):

Хмм, не является ли тривиальная оценка $M_n\ge2^n$ точной?

Я что-то даже не могу сообразить, почему $M_2 = 4$ Несогласованную систему из четырёх "двухэлементных пар" вижу, а почему из пяти пар невозможна?..

-- Вс дек 27, 2009 07:17:39 --

AGu в сообщении #275401 писал(а):

В этой задаче зашифровано утверждение о том, что
топология тихоновской степени $\{0,1\}^X$ имеет счетный тип

В определении алгоритмической сводимости по Тьюрингу эти несогласованные пары возникают...

[RIP]

Профессор Снэйп в сообщении #275567 писал(а):

RIP в сообщении #275300 писал(а):

Хмм, не является ли тривиальная оценка $M_n\ge2^n$ точной?

Я что-то даже не могу сообразить, почему $M_2 = 4$ Несогласованную систему из четырёх "двухэлементных пар" вижу, а почему из пяти пар невозможна?..

Тупой перебор вариантов.
Вообще, мне кажется, что $M_n=2^n$ --- это какой-то классический результат по комбинаторике.
Предлагаю доказать или опровергнуть (и то, что $M_n=2^n$, и то, что это классический результат по комбинаторике ). Сам немного подумал, кое-какие мысли есть, но пока не смог их довести до чего-нибудь внятного. Даже для $n=3$ пока не проверил.

[AGu]

RIP в сообщении #275569 писал(а):

Вообще, мне кажется, что $M_n=2^n$ --- это какой-то классический результат по комбинаторике.

Можно и комбинаторно, но для начала я попробую объяснить равенство $M_n=2^n$ с помощью теории меры.

Пусть $\Omega=(\{0,1\},\mu)$ — вероятностное пространство, где $\mu(\{0\})=\mu(\{1\})=\frac12$.
Рассмотрим его степень $\Omega^X=(\{0,1\}^X,\mu^X)$. Это тоже вероятностное пространство.
Как и раньше, для $(A,B)\in\Pi$ положим $F(A,B)=\bigl\{f\in\{0,1\}^X:f|_A\equiv0,\ f|_B\equiv1\bigr\}$
и заметим, что $(A,B)\between(A',B')$ равносильно $F(A,B)\cap F(A',B')=\varnothing$.
Слой $F(A,B)(x)=\{f(x):f\in F(A,B)\}$ цилиндра $F(A,B)$ равен $\{0\}$ при $x\in A$,
равен $\{1\}$ при $x\in B$ и равен $\{0,1\}$ при остальных $x\in X$.
Следовательно, $\mu^X\bigl(F(A,B)\bigr)=\prod_{x\in X}\mu\bigl(F(A,B)(x)\bigr)=\mu(\{0\})^{|A|}\times\mu(\{1\})^{|B|}=\frac1{2^{|A|+|B|}}$.
Таким образом, всякому множеству $P$ попарно несогласованных пометок $(A,B)$, $|A|+|B|\leqslant n$,
соответствует множество попарно непересекающихся цилиндров $F(A,B)$,
каждый из которых имеет в $\Omega^X$ меру $\geqslant \frac1{2^n}$, а значит,
количество этих цилиндров, очевидно равное $|P|$, не может превышать $2^n$.
Ну а достижимость этой оценки очевидна.

[maxal]

AGu
Это доказательство самое что ни на есть комбинаторное, а вероятность тут притянута за уши.
Можно просто сказать, что $|F(A,B)|=2^{|X|-|A|-|B|} \geq 2^{|X|-n}$, а так как попарно непересекающиеся множества $F(A,B)$ вложены во множество всех функций $\{0,1\}^X$ мощности $|\{0,1\}^X|=2^{|X|}$, то их количество не превосходит $\frac{2^{|X|}}{2^{|X|-n}}=2^n$.

P. S. Для порядка предварительно еще нужно заметить, что без потери общности можно ограничится рассмотрением конечного X.

[AGu]

Согласен. Браво, maxal!
Теперь и впрямь все совершенно очевидно.

[RIP]

Результат, действительно, оказался не нов. Пока не буду раскрывать карты, а лучше предложу задачу, которую можно вывести из равенства $M_n=2^n$.

Пусть $P$ --- некоторое множество $d$-мерных симплексов в $\mathbb R^d$, причём пересечение любых двух (различных) из них $(d-1)$-мерно. Докажите, что $|P|\le2^{d+1}$.