Множества

На балу присутствует равное число юношей и девушек. Известно, что для любой группы юношей найдётся по крайней мере столько же девушек, каждая из которых имеет знакомого в этой группе. Можно ли составить пары из знакомых друг с другом партнёров так, чтобы танцевали все участники бала?

Пусть последовательность $\left\{ r_{n}\right\}$ определена следующим образом:

Докажите, что отображение $n \mapsto r_{n}$ есть биекция множества $\mathbb {N}$ на множество $\mathbb {Q}_{+}=\mathbb {Q} \cap (0,+\infty )$.

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

Рис. 1

Рис. 2

Птичьим следом будем называть множество на плоскости, являющееся объединением трёх (лежащих на различных лучах) отрезков, имеющих общий конец — вершину следа (рис. 3). Докажите, что на плоскости можно расположить лишь не более чем счётное множество попарно непересекающихся птичьих следов.

Под Т-образной фигурой будем понимать объединение двух взаимно перпендикулярных отрезков, середина одного из которых является концом другого. Оцените сверху число $N$ попарно непересекающихся Т-образных фигур, образованных отрезками единичной длины и содержащихся в квадрате со стороной $a$.

Рис. 3

Докажите, что в пространстве можно расположить лишь не более чем счётное множество попарно непересекающихся «обручей» цилиндрических колец фиксированного радиуса (толщина обручей равна нулю).

После проигрыша всех соревнований Балде бесы (которых было бесконечно много) решили заняться физкультурой и организовали спортивные секции. В каждую секцию входило лишь конечное число бесов, но секций было так много, что в любой бесконечной компании бесов можно было указать по крайней мере двух, записавшихся в одну секцию. Докажите, что за исключением конечного числа бесов-лентяев каждый из бесов был записан в бесконечное множество секций.

Будем говорить, что последовательность $\left\{ A_{n}\right\}$ конечных подмножеств множества $\mathbb {N}$ густо покрывает $\mathbb {N}$, если для любого бесконечного множества $B \subset \mathbb {N}$ найдётся такой номер $m$, что $\operatorname {card}\left(B \cap A_{m}\right) \geqslant 2$. Докажите, что

Докажите, что если $\left\{ A_{n}\right\} ,\left\{ B_{n}\right\}$ - две последовательности конечных множеств, каждая из которых густо покрывает $\mathbb {N}$ (см. задачу 1.8), то найдутся такие номера $p$ и $q$, что $\operatorname {card}\left(A_{p} \cap B_{q}\right) \geqslant 2$.

Двоичной последовательностью называется последовательность, «состоящая из нулей и единиц», т. е. последовательность $\varepsilon =\left\{ \varepsilon_{k}\right\}$, где $\varepsilon_{k}=0$ или 1 при любом $k \in \mathbb {N}$. Множество всевозможных двоичных последовательностей мы будем обозначать буквой Ξ.

Говоря о множествах, элементами которых, в свою очередь, являются множества, мы будем использовать термин «система множеств».

Пусть $\mathscr {P}(\mathbb {N})$ — система всевозможных подмножеств множества $\mathbb {N}$. Докажите, что

Докажите, что множество Ξ имеет мощность континуума.

Докажите, что множества $\mathbb {R}^{2}$ и $\mathbb {R}^{3}$ имеют мощность континуума.

Докажите, что множество $\mathbb {R}^{\mathbb {N}}$ всех последовательностей вещественных чисел имеет мощность континуума.

Докажите, что множество непрерывных функций, заданных на отрезке $\left[a, b\right]$, имеет мощность континуума.

Существует ли система $\mathfrak {A}$ подмножеств множества $\mathbb {N}$, удовлетворяющая условиям:

Существует ли система $\mathfrak {A}$ подмножеств множества $\mathbb {N}$, удовлетворяющая условиям:

Существует ли система $\mathfrak {A}$ подмножеств множества $\mathbb {N}$, удовлетворяющая условиям:

Пусть $\mathscr {F}(\mathbb {N})=\left\{ A \subset \mathbb {N} \mid \operatorname {card}(A)<+\infty \right\}$ — система всех конечных подмножеств множества $\mathbb {N}$. Докажите, что

Пусть $S^{1}=\left\{ z \in \mathbb {C} \mid \left|z\right|=1\right\}$. Множества $A, B \subset S^{1}$ называются конгруэнтными, если существует такое число $\alpha \in \mathbb {R}$, что $B=\left\{ z e^{i \alpha } \mid z \in A\right\}$, т.е. «множество $B$ получается из множества $A$ поворотом на угол $\alpha$ ». Докажите, что существует такая последовательность $\left\{ E_{n}\right\}$ попарно непересекающихся конгруэнтных множеств, что $S^{1}=\bigcup_{n \geqslant 1} E_{n}$.

Пусть $E \subset \mathbb {R}$ и $\frac{x+y}{2} . \in E$ для любых $x, y \in E$.

Найдите все предельные точки множеств

Пусть $E \subset \mathbb {R}_{+}, E \neq \varnothing$. Докажите, что если $\sqrt{x^{2}+y^{2}} \in E$ и $\frac{x}{2} \in E$ для любых $x, y \in E$, то $\bar{E}=[0,+\infty )$.

Пусть $E \subset \mathbb {R}^{2}$. Докажите, что

Пусть $E \subset \mathbb {N}, \operatorname {card} E=+\infty$. Докажите существование такого числа $a>1$, что бесконечно много чисел $\left[a^{k}\right](k \in \mathbb {N})$ содержится в $E$.

Пусть $G$ — открытое, не ограниченное сверху множество в $\mathbb {R}$. Существует ли такое положительное число $x_{0}$, что множество $G$ содержит бесконечно много точек вида $n x_{0}(n \in \mathbb {N})$ ?

Пусть $\left\{ G_{m}\right\}$ — последовательность открытых, не ограниченных сверху подмножеств множества $\mathbb {R}$. Докажите, что существует такое число $x_{0}>0$, что каждое множество $G_{m}$ содержит бесконечно много точек вида $n x_{0}(n \in \mathbb {N})$.

В задачах $1.29-1.34$ изучаются канторово множество и его обобщения. Эти множества часто встречаются в анализе и теории функций. Классическое канторово множество $C$ можно кратко описать следующим образом. Оно получается удалением из промежутка $\left[0,1\right]$ счётного семейства интервалов. Сначала выбрасывается один интервал — центральная треть исходного промежутка $\left[0,1\right]$ (т.е. $\left(\frac{1}{3}, \frac{2}{3}\right)$), затем из оставшихся двух сегментов удаляются их центральные трети и т.д. Точки из $\left[0,1\right]$, не попавшие ни в один из удаляемых интервалов, образуют канторово множество $C$.

Рассмотрим подробнее обобщение описанной конструкции (вводимые при этом обозначения будут в дальнейшем неоднократно использоваться). Пусть $\Delta =\left[a, b\right]$ — произвольный невырожденный сегмент. Множество $K_{1}$ получается удалением из $\Delta$ непустого интервала $\delta =(p, q)$, концы которого не совпадают с $a$ и $b$. Иными словами, $K_{1}$ есть объединение двух невырожденных сегментов $\Delta_{0}=\left[a, p\right]$ и $\Delta_{1}=\left[q, b\right]$, которые мы будем называть сегментами первого ранга. Множество $K_{2}$ получается после удаления из сегментов $\Delta_{0}$ и $\Delta_{1}$ интервалов $\delta_{0}, \delta_{1}$, концы которых не совпадают с концами $\Delta_{0}$ и $\Delta_{1}$ соответственно. Разность $\Delta_{\varepsilon } \backslash \delta_{\varepsilon }(\varepsilon =0,1)$ состоит из двух невырожденных сегментов, из которых левый мы обозначим $\Delta_{\varepsilon 0}$, а правый — $\Delta_{\varepsilon 1}$. Таким образом, $K_{2}$ есть объединение четырёх сегментов $\Delta_{00}, \Delta_{01}, \Delta_{10}, \Delta_{11}$, которые мы будем называть сегментами второго ранга. Дальнейшее построение продолжается по индукции. Пусть построено множество $K_{n}$, состоящее из сегментов $n$-го ранга. «Нумерацию» сегментов $n$-го ранга удобно производить с помощью индексов $\varepsilon_{1}, \ldots , \varepsilon_{n}$, где $\varepsilon_{j}$ может принимать значение 0 или 1. Индексы сегментов первого и второго рангов уже указаны, дальнейшая индексация производится следующим образом. При построении сегментов $(n+1)$-го ранга из каждого сегмента $n$-го ранга $\Delta_{\varepsilon_{1} \ldots \varepsilon_{n}}$ удаляется непустой интервал $\delta_{\varepsilon_{1} \ldots \varepsilon_{n}}$, концы которого не совпадают с концами сегмента $\Delta_{\varepsilon_{1} \ldots \varepsilon_{n}}$. Разность $\Delta_{\varepsilon_{1} \ldots \varepsilon_{n}} \backslash \delta_{\varepsilon_{1} \ldots \varepsilon_{n}}$ состоит из двух сегментов $(n+1)$-го ранга, из которых левый обозначается $\Delta_{\varepsilon_{1} \ldots \varepsilon_{n} 0}$, а правый — $\Delta_{\varepsilon_{1} \ldots \varepsilon_{n} 1}$. Множество $K_{n+1}$ есть объединение всех сегментов $(n+1)$-го ранга. Пусть, наконец, $K=\bigcap_{n \geqslant 1} K_{n}$. Если множество $K$ не имеет внутренних точек, то оно называется обобщённым канторовым множеством.

Важный пример обобщённого канторова множества мы получим, если длины всех сегментов данного ранга одинаковы. В этом случае длины всех интервалов $\delta_{\varepsilon_{1}, \ldots \varepsilon_{n}}$ (при фиксированном $n$) также одинаковы и эти интервалы расположены симметрично относительно середин сегментов $\Delta_{\varepsilon_{1} \ldots \varepsilon_{n}}$. Такие множества мы будем называть однородными обобщёнными канторовыми множествами. Положим $\left|\Delta \right|=l_{0},\left|\Delta_{\varepsilon_{1} \ldots \varepsilon_{n}}\right|=l_{n}$, где символ $\left|\omega \right|$ обозначает длину промежутка $\omega$. Последовательность $\left\{ l_{n}\right\}_{n \geqslant 0}$ будем называть определяющей последовательностью обобщённого однородного канторова множества. Легко видеть, что всякая положительная последовательность $\left\{ l_{n}\right\}_{n} \geqslant 0$, удовлетворяющая условию $2 l_{n}<l_{n-1}$ при всех $n \in \mathbb {N}$, может быть определяющей для некоторого обобщённого канторова множества, которое единственно с точностью до конгруэнтности. Если величина $\theta =\frac{l_{n}}{l_{n-1}}$ одна и та же при всех $n \in \mathbb {N}$, то определяемое последовательностью $\left\{ l_{n}\right\}_{n \geqslant 0}$ обобщённое канторово множество будем называть множеством с постоянным отношением. Очевидно, $\theta$ может быть любым числом из интервала ($0, \frac{1}{2}$). Классическое канторово множество $C$ мы получаем, когда $\Delta =\left[0,1\right]$ и $\theta =\frac{1}{3}$.

Докажите, что

Пусть $K$ — множество с постоянным отношением $\theta$, построенное на промежутке $\Delta =\left[0, L\right]$. Пусть $\varepsilon =\left\{ \varepsilon_{1}, \varepsilon_{2}, \ldots \right\}$ — произвольная двоичная последовательность, а $t(\varepsilon )$ — единственная точка из пересечения $\bigcap_{n \geqslant 1} \Delta_{\varepsilon_{1} \ldots \varepsilon_{n}}$. Докажите, что

Рассмотрим множество $K$, описанное при построении обобщённого канторова множества. Докажите, что оно

Докажите, что у любых двух точек однородного обобщённого канторова множества $K$, не являющихся концами дополнительных интервалов, достаточно малые относительные окрестности конгруэнтны (относительная окрестность точки $x \in K$ есть пересечение $K$ с интервалом, содержащим $x$).

Пусть $\nu =\left\{ n_{k}\right\}$ — строго возрастающая последовательность натуральных чисел,

Докажите, что

Пусть множество $E \subset \mathbb {R}$ обладает свойством: между любыми двумя его точками найдётся третья точка из этого множества. Обязательно ли замыкание множества $E$ содержит непустой интервал?

Постройте на плоскости дискретное множество (см. задачу 1.25), замыкание которого имеет мощность континуума. Существует ли на прямой дискретное множество с таким же свойством?

Пусть $\left\{ \Delta_{\varepsilon_{1} \ldots \varepsilon_{n}}\right\}$, где $n \in \mathbb {N}$, а $\varepsilon_{j}$ принимают значения 0 или $1$, — семейство непустых ограниченных открытых промежутков, удовлетворяющих условиям: 1) $\Delta_{\varepsilon_{1} \ldots \varepsilon_{n}} \supset \Delta_{\varepsilon_{1} \ldots \varepsilon_{n} 0} \cup \Delta_{\varepsilon_{1} \ldots \varepsilon_{n} 1}$; 2) при каждом $n \in \mathbb {N}$ интервалы $\Delta_{\varepsilon_{1} \ldots \varepsilon_{n}}$ и $\Delta_{\varepsilon_{1}^{\prime } \ldots \varepsilon_{n}^{\prime }}$ не пересекаются, если $\left(\varepsilon_{1} \ldots \varepsilon_{n}\right) \neq \left(\varepsilon_{1}^{\prime } \ldots \varepsilon_{n}^{\prime }\right)$.

Положим

Докажите, что множество $A=\bigcap_{n \geqslant 1} G_{n}$ имеет мощность континуума.

Докажите, что непустой интервал нельзя представить в виде объединения последовательности попарно непересекающихся замкнутых множеств.

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

Пусть объединение множеств $E_{n} \subset \mathbb {R}(n \in \mathbb {N})$ имеет внутреннюю точку. Докажите, что замыкание хотя бы одного множества $E_{n}$ имеет внутреннюю точку.

Докажите, что множество иррациональных чисел не является объединением последовательности замкнутых множеств.