Простая задачка про множества

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

Пусть $\mathcal{E}$ --- не более чем счётное семейство подмножеств натурального ряда. Доказать, что существует бесконечное множество $X \subseteq \mathbb{N}$, такое что для каждого $E \in \mathcal{E}$ одно из множеств $X \cap E$, $X \setminus E$ конечно.

[Юстас]

После оговорок насчет того, что достаточно рассматривать только бесконечные множества $A_i$ с бесконечными дополнениями, строим следующий процесс: если таких множеств не имеем, то $B:=\mathbb{N}$; иначе, $B_1=A_1$. Если $|B_i\cap A_{i+1}|<\infty$, то $B_{i+1}=B_{i}$, иначе $B_{i+1}=B_i\cap A_{i+1}$. Для каждого $i$ множество $B_i$ удовлетворяет нужному свойству для набора $A_1,\dots,A_i$. Имеем последовательность $B_i$ вложенных множеств, каждое из которых бесконечно, тогда $B=\bigcap\limits_{1}^{\infty}B_i$ - искомое.

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

Не согласен с этим решением.

Множество $B$ не обязано быть бесконечным. Пусть, к примеру,

$$ A_i = \{ k \cdot 2^i : k \in \mathbb{N} \} $$

Согласно Вашей конструкции $B_i = A_i$ для всех $i \in \mathbb{N}$ и

$$ \bigcap_{i \in \mathbb{N}} B_i = \varnothing $$

Это, конечно, если начинать натуральный ряд с единицы А если с нуля, то

$$ \bigcap_{i \in \mathbb{N}} B_i = \{ 0 \} $$

--- тоже ничего хорошего

[Юстас]

Да, я только для конечного набора доказал.

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

Эх, надо было в "помогите решить/разобраться" постить задачу, за 5 минут бы расщёлкали.

А я-то уже размечтался: дам простую для затравки, когда решат --- сформулирую более сложный вариант. А тут простое третий день решают

[Someone]

Не могу смотреть, как человек страдает.

Выкинем из семейства $\mathcal E$ все конечные множества и все множества с конечным дополнением, так как для них любое бесконечное $X\subseteq\mathbb N$ годится: либо $X\cap E$ конечно (если $E$ конечно), либо $X\setminus E$ конечно (если $\mathbb N\setminus E$ конечно). Оставшиеся перенумеруем в произвольном порядке, и получим семейство $\mathcal E'=\{E_k:k\in\mathbb N\}$ (я считаю, что натуральный ряд начинается с единицы).

Замечание. Может оказаться, что множество $\mathcal E'$ конечно или даже пусто, поскольку такая ситуация в условии не оговорена. Чтобы не возиться отдельно с этим случаем, с самого начала расширим множество $\mathcal E$, добавив в него всевозможные арифметические прогрессии из натуральных чисел с разностью, большей единицы, тогда $\mathcal E'$ заведомо будет бесконечным.

Заметим, что для любого $E\in\mathcal E'$ оба множества $E$ и $\mathbb N\setminus E$ бесконечны.

Далее полагаем $B_1=E_1$ (или $B_1=\mathbb N\setminus E_1$), берём любую точку $x_1\in\mathbb N\setminus B_1$ и полагаем $X_1=\{x_1\}$.
Если для некоторого $k\in\mathbb N$ множества $B_k$ и $X_k$ уже построены, причём, $B_1\supseteq B_2\supseteq\ldots\supseteq B_k$, $|B_k|=\aleph_0$, $X_1\subseteq X_2\subseteq\ldots\subseteq X_k$, $|X_k\setminus B_j|\leqslant j$ при $1\leqslant j\leqslant k$, и либо $B_k\subseteq E_k$, либо $|X\cap E_k|\leqslant k$, то в качестве $B_{k+1}$ берём то из множеств $B_k\cap E_{k+1}$ или $B_k\setminus E_{k+1}$, которое бесконечно (любое из них, если оба бесконечны; если $B_{k+1}=B_k\cap E_{k+1}$, то $B_{k+1}\subseteq E_{k+1}$; если $B_{k+1}=B_k\setminus E_{k+1}$, то $B_{k+1}\cap E_{k+1}=\varnothing$); если при этом $B_k\setminus B_{k+1}=\varnothing$, то полагаем $X_{k+1}=X_k$; если же $B_k\setminus B_{k+1}\neq\varnothing$, то выбираем любую точку $x_{k+1}\in B_k\setminus B_{k+1}$ и полагаем $X_{k+1}=X_k\cup\{x_{k+1}\}$.
Выполнив это построение для всех $k\in\mathbb N$, получим две последовательности множеств $B_1\supseteq B_2\supseteq\ldots\supseteq B_k\supseteq\ldots$ и $X_1\subseteq X_2\subseteq\ldots\subseteq X_k\subseteq\ldots$ таких, что $|B_k|=\aleph_0$, $|X_k|\leqslant k$ и $|X_k\setminus B_j|\leqslant j$ для всех $k\in\mathbb N$ и $1\leqslant j\leqslant k$.

Положим $B_0=\bigcap\limits_{k\in\mathbb N}B_k$ и $X_0=\bigcup\limits_{k\in\mathbb N}X_k$. Заметим, что если множество $X_0$ конечно, то найдётся такой номер $k_0$, что $B_k=B_{k_0}$ при всех $k\geqslant k_0$, но тогда множество $B_0=B_{k_0}$ бесконечно.

Множество $X=X_0\cup B_0$ - искомое, так как при любом $k\in\mathbb N$ имеем $|X\setminus B_k|\leqslant k$, то есть, либо $|X\setminus E_k|\leqslant k$ (если $B_k\subseteq E_k$), либо $|X\cap E_k|\leqslant k$ (если $B_k\cap E_k=\varnothing$).

Прошу прощения, текст несколько сумбурный, поскольку писал экспромтом.

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

Спасибо Вам за то, что прервали мои страдания

Someone писал(а):

Прошу прощения, текст несколько сумбурный, поскольку писал экспромтом.

Текст действительно сумбурный и в нём много лишнего. Сразу отмечу, что конечные множества и множества с конечными дополнениями выкидывать не надо, они ничем не мешают. Изложу то же самое чуть короче.

Пусть $E_0, E_1, \ldots$ --- перечисление всех множеств из $\mathcal{E}$ (возможно, с повторениями). Образуем последовательность бесконечных множеств $B_0 \supseteq B_1 \supseteq \ldots$ следующим образом:

1) $B_0 = \mathbb{N}$;
2) если $B_i \cap E_i$ бесконечно, то полагаем $B_{i+1} = B_i \cap E_i$, в противном случае полагаем $B_{i+1} = B_i \setminus E_i$.

Теперь определим последовательность $b_0, b_1, \ldots$ следующим образом:

1) $b_0 = 0$;
2) пусть $b_0, \ldots, b_i$ определено. Так как $B_{i+1}$ бесконечно, то в нём найдётся элемент, отличный от $b_0, \ldots, b_i$. Полагаем $b_{i+1}$ равным одному из таких элементов.

Легко проверить, что множество $X = \{ b_0, b_1, \ldots \}$ обладает нужными свойствами.

-------------------------

А теперь более интересная (но и более сложная) задача.

Предположим, что двое играют в следующую игру. Ходы делаются по очереди. Перед началом игры имеется корзина, в которой сложены шары с номерами $0,1,2, \ldots$, по одному шару на каждый номер. В начале каждого хода первый игрок сообщает второму игроку произвольную упорядоченную пару натуральных чисел. После этого второй игрок может либо пропустить ход, либо выкинуть какой-то один шар из корзины.

Скажем, что множество $X \subseteq \mathbb{N}$ является сжатым по отношению к семейству $\mathcal{E}$ подмножеств натурального ряда, если $X$ бесконечно и для любого $E \in \mathcal{E}$ одно из множеств $X \cap E$, $X \setminus E$ конечно.

По результатам игры (после завершения всех шагов $0,1,\ldots$) формируются:

1) Для каждого $n \in \mathbb{N}$ множество $E_n$, состоящее из всех таких $x$, что пара $\langle n,x \rangle$ была написана первым игроком на одном из шагов в процессе игры;

2) Семейство $\mathcal{E} = \{ E_0, E_1, \ldots \}$;

3) Множество $X$, состоящее из номеров тех шаров, которые остаются в корзине после окончания игры (то есть тех шаров, которые не выкидываются из корзины ни на каком шаге).

Игрок номер 2 выигрывает, если множество $X$ является сжатым по отношению к $\mathcal{E}$.

Докажите, что для игрока номер 2 существует выигрышная стратегия (то есть что он может выиграть всегда, какие бы ходы ни делал первый игрок).