Метка: топология

M1247. О покрытии плоскости квадратами

Задача из журнала «Квант» (1991 год, 3 выпуск)

Условие

Можно ли покрыть всю плоскость квадратами с длинами сторон $1, 2, 4, 8, 16, …$ (без наложения), используя каждый квадрат не более а) десяти раз; б) одного раза?

Доказательство

  1. Можно. Пример покрытия (где квадрат со стороной $1$ используется $4$ раза, а остальные — по $3$ раза) приведен на рисунке $1$.
    Рис. 1
  2. Нельзя. Предположим, что существует покрытие, в котором все квадраты различны. Поскольку сумма всех чисел не превосходящих $2^{n-1}$, меньше $2^n$ $(1+2+2^2+ … +2^{n-1} = 2^n-1)$, то к каждой стороне любого из квадратов нашего покрытия должна примыкать сторона большего квадрата. Отсюда следует, что каждая вершина квадрата должна лежать на стороне большего квадрата (если вершина $B$ квадрата $ABCD$ лежит на стороне большего квадрата, примыкающего к стороне $AB$ (рис. $2$), то вершина $C$ будет лежать на стороне большего квадрата, примыкающего к $BC$, и т.д.).
Рис. 2

Рассмотрим теперь наименьший из всех квадратов покрытия. Четыре квадрата будут примыкать к нему так, как показано на рисунке $3$.

Рис. 3

Рассмотрим больший из этих квадратов — пусть он примыкает к стороне $AB$ наименьшего (на рисунке — это черный квадрат). Тогда вершина $A$ этого квадрата не лежит на стороне большего, чем он, квадрата. Получили противоречие.

Д.Фомин

9.2.1 Открытые множества

Определение. Открытым шаром с центром в точке $x_0$ и радиусом $\rho >0$ называется множество всех точек $x\in \mathbb{R}^n,$ таких, что $|x-x_0|<\rho.$ Этот шар обозначается $B(x_0,\rho)$ и называется также $\rho$-окрестностью точки $x_0.$

Определение. Пусть задано множество $E \subset \mathbb{R}^n.$ Точка $x_0 \in E$ называется внутренней точкой множества $E,$ если существует шар $B(x_0,\rho),$ содержащийся в $E.$ Другими словами, точка $x_0$ называется внутренней точкой множества $E,$ если она входит во множество $E$ вместе с некоторой окрестностью.

Определение. Множество $E$ называется открытым, если все его точки являются внутренними точками этого множества. Условимся также считать пустое множество $\emptyset$ открытым.

Пример 1. Каждый открытый шар $B(x_0,r)$ является открытым множеством.

Действительно, пусть $x \in B(x_0,r).$ Нужно доказать, что существует такая окрестность точки $x,$ которая целиком содержится в шаре $B(x_0,r).$ Положим $\rho = r-|x-x_0|.$ Тогда $\rho > 0,$ так как $|x-x_0|<r.$ Покажем, что $B(x,\rho) \subset B(x_0,r).$ Пусть $y \in B(x,Ѕ).$ Тогда $|y-x|<\rho.$ Оценим расстояние между точками $y$ и $x_0.$ По неравенству треугольника имеем $$|y-x_0|\leqslant|y-x|+|x-x_0|<\rho + |x-x_0|=r$$ что и требовалось доказать.

В частности, при $n = 1$ открытые шары — это интервалы на действительной прямой, и они являются открытыми множествами на прямой.

Пример 2. Рассмотрим открытые $n$-мерные интервалы. Для двух заданных векторов $a,b \in \mathbb{R}^n,$ таких, что $a^i < b^i (i=1,…,n),$ открытым интервалом называется множество всех точек $x,$ координаты которых удовлетворяют условиям $a^i < x^i < b^i (i=1,…,n).$ Такой интервал обозначается через $(a^1,b^1,…,a^n,b^n).$

В частности, в $\mathbb{R}^2$ открытые интервалы — это прямоугольники со сторонами, параллельными координатным осям, а в $\mathbb{R}^3$ — параллелепипеды, ребра которых параллельны координатным осям.

Докажем, что любой открытый интервал в $\mathbb{R}^n$ является открытым множеством.

Пусть $J$ — открытый интервал и пусть $x \in J,$ т. е. $a^i < x^i < b^i (i=1,…,n).$ Обозначим через $\delta^i = min(x^i — a^i,b^i-x^i)(i=1,…,n)$ и $\delta=min(\delta^1,…,\delta^n).$ Покажем, что шар $B(x,\delta)$ содержится в $J.$ Действительно, если $y \in B(x,\delta),$ то $|y-x|<\delta.$ Отсюда следует, что $|x^i-y^i|<\delta$ для всех $i=1,…,n.$ Пользуясь определением числа $\delta,$ видим, что $a^i < y^i < b^i$ для всех $i=1,…,n,$ так что $y \in J,$ что и требовалось доказать.

Пример 3. Множество $S$ всех точек на действительной прямой — открытое.

Рассмотрим некую точку $x,$ которая находится на расстоянии $\rho$ от точки $x_0 = (0),$ затем рассмотрим шар $B(x,\eps).$ Каждая точка, принадлежащая этому шару, также, очевидно, принадлежит всей действительной прямой, т.е. $\forall y \in B(x,\eps): y \in S,$ что означает что любая точка входит в множество $S$ вместе с некоторым шаром, а по определению это значит, что $S$ — открытое множество

Свойства открытых множеств.

Пусть $\mathcal{A}$ — множество индексов, и каждому элементу $\alpha \in \mathcal{A}$ поставлено в соответствие некоторое множество $E_{\alpha}.$ Тогда говорят, что задано семейство множеств $\{E_{\alpha}\}_{\alpha \in \mathcal{A}}.$

Теорема. Система всех открытых множеств в $\mathbb{R}^n$ обладает следующими свойствами:

  1. все пространство $\mathbb{R}^n$ и пустое множество $\emptyset$ открыты;
  2. пересечение любого конечного числа открытых множеств открыто;
  3. объединение любого семейства $\{G_{\alpha}\}_{\alpha \in \mathcal{A}}$ открытых множеств открыто.
  1. Пустое множество $\emptyset$ открыто по определению, а всё пространство $\mathbb{R}^n,$ очевидно, открыто, поскольку любой шар содержится в $\mathbb{R}^n.$
  2. Пусть $G_1,…,G_s$ — открытые множества, $G = \bigcap\limits_{i=1}^s G_i.$ Пусть $x \in G.$ Тогда $x \in G_i$ для всех $i=1,…,s.$ Но каждое из множеств $G_i$ открыто, так что для каждого $i=1,…,s$ найдется шар $B(x,r_i) \subset G_i.$ Среди всех этих шаров выберем шар с наименьшим радиусом $B(x,r),$ где $r = min(r_1,…,r_s).$ Тогда $B(x, r) \subset G_i$ при каждом $i=1,…,s,$ а значит, $B(x,r) \subset G,$ и тем самым доказано, что множество $G$ открыто.
  3. Пусть $G = \bigcup\limits_{\alpha \in \mathcal{A}} G_{\alpha},$ где каждое множество $G_{\alpha}$ открыто. Докажем, что и множество $G$ также открыто. Действительно, пусть $x \in G.$ Тогда $x$ принадлежит по крайней мере одному из множеств $G_{\alpha_0}.$ Так как это множество $G_{\alpha_0}$ открыто, то найдется окрестность $B(x,\rho) \subset G_{\alpha_0} \subset G.$ Таким образом, $G$ — открытое множество.

Замечание. Пересечение бесконечного набора открытых множеств не обязано быть открытым множеством. Например, пусть $B_k$ — открытый шар с центром в нуле и радиусом $\frac{1}{k} (k = 1,2,…).$ Тогда $\bigcap\limits^{\infty}_{k=1} B_k = \{0\}.$ Но множество $\{0\},$ состоящее из одной точки, не является открытым, поскольку оно не содержит в себе ни одного шара.

Определение. Пусть $E$ — непустое множество в $\mathbb{R}^n.$ Тогда совокупность всех его внутренних точек называется внутренностью множества $E$ и обозначается через $\mathring{E}$ или $\text{int} E.$

Теорема. Для любого непустого множества $E$ его внутренность — открытое множество.

Будем предполагать, что $\mathring{E}$ не пусто. Пусть $x \in \mathring{E}.$ Тогда $x$ — внутренняя точка множества $E$ (по определению внутренности). Нужно доказать, что $x$ является также внутренней точкой множества $\mathring{E}.$ Итак, найдется шар $B(x,\rho) \subset E.$ Но поскольку шар — открытое множество, то каждая точка $y \in B(x,\rho)$ содержится в этом шаре вместе с некоторой окрестностью $U_y.$ Значит $U_y \subset E,$ и поэтому $y$ — внутренняя точка множества $E,$ т.е. $y \in \mathring{E}.$ Таким образом, мы получили, что $B(x,\rho) \subset \mathring{E},$ а это означает, что $\mathring{E}$ — открытое множество, и теорема доказана.

Пример 4. Рассмотрим область определения функции $f(x) = \frac{1}{x}.$ $D(f) = (-\infty;0)\cup(0;\infty),$ значит $D(f)$ можно представить в виде объединения двух интервалов $D(f) = A_1 \cup A_2,$ где $A_1 = (-\infty;0); A_2 = (0;\infty),$ то есть в виде объединения двух открытых множеств, так как интервалы — открытые множества по доказанному ранее. А значит, по свойству открытых множеств, множество $D(f)$ — открытое множество.

Пример 5. Рассмотрим область определения функции $f(x) = \sqrt{3x}.$ $D(f)=\{x \in \mathbb{R} | x \geqslant 0\}.$ Это множество не является открытым, докажем это. Рассмотрим точку $x=0.$ $x \in D(f),$ однако не существует такого открытого шара $B(x,\rho),$ который полностью бы лежал в $D(f),$ так как в этом шаре будет присутствовать точка $y,$ такая что $x-\rho < y < x = 0.$ Из этого следует, что $y < 0$ и $y$ не принадлежит $D(f).$ Значит $D(f)$ не является открытым множеством.

9.2.1. Открытые множества

Для закрепления материала предложен тест по теме «Открытые множества».

  1. Коляда В.И., Кореновский А. А. Курс лекций по математическому анализу.- Одесса : Астропринт, 2009. Раздел 9.2.1

Лемма Больцано-Вейерштрасса

Теорема Больцано — Вейерштрасса, или лемма Больцано — Вейерштрасса о предельной точке — фундаментальная теорема математического анализа, гласящая, что из любой ограниченной последовательности точек пространства [latex]\mathbb{R}^n[/latex] можно выделить сходящуюся подпоследовательность. Т. Б. — В., используется при доказательстве многих теорем анализа, например, теоремы о достижении непрерывной на отрезке функцией своих точных верхней и нижней граней. Теорема названа в честь чешского математика Бернарда Больцано и немецкого математика Карла Вейерштрасса, которые независимо друг от друга вывели ее формулировку и доказательство.

Формулировка. Любое бесконечное ограниченное множество [latex]F \subset \mathbb{R}^n[/latex] имеет по крайней мере одну предельную точку. Доказательство. Пусть множество [latex]F[/latex] является бесконечным и ограниченным множеством. Предположим, что оно не имеет предельных точек. Следовательно, оно является замкнутым. Поскольку [latex]F[/latex] еще и ограничено, то, по теореме Гейне – Бореля, [latex]F[/latex] компактно. Для каждой точки [latex]x \in F[/latex] построим такую окрестность [latex]U_x[/latex], в которой нет других точек из [latex]F[/latex], кроме [latex]x[/latex] (если бы для какой-то точки [latex]x[/latex] такой окрестности не было, то эта точка была бы предельной для [latex]F[/latex]). Тогда семейство [latex]\left\{U_x \right\}_{x \in F}[/latex] образует открытое покрытие компактного множества [latex]F[/latex]. Пользуясь компактностью [latex]F[/latex], выберем из него некое конечное подпокрытие, иными словами. конечный набор шаров, в каждом из которых содержится лишь по одной точке из множества [latex]E[/latex]. Но это противоречит тому, что множество [latex]E[/latex] бесконечно.[latex]\square[/latex]
Замечание. Предельная точка, существование которой утверждается в данной теореме, вообще говоря, не обязана принадлежать множеству [latex]E[/latex].

Литература:

Критерий компактности в n-мерном пространстве (Теорема Гейне – Бореля)

Теорема Гейне – Бореля. Чтобы множество [latex]K \subset \mathbb{R}^n[/latex] являлось компактным, необходимо и достаточно, чтобы [latex]K[/latex] было ограниченным и замкнутым.

Доказательство. Достаточность. Пусть [latex]K[/latex] замкнуто и ограничено. Тогда найдется сегмент [latex]I \subset \mathbb{R}^n[/latex], содержащий [latex]K[/latex]. В силу леммы Гейне – Бореля, этот сегмент [latex]I[/latex] компактен. Поэтому, в силу свойств компактных множеств, компактно также его замкнутое подмножество [latex]K[/latex]. Необходимость. Пусть [latex]K[/latex] —  компакт. Докажем, что данное множество ограничено. Обозначим через [latex]B_s[/latex] открытый шар с центром в точке [latex]0[/latex] радиуса [latex]s[/latex]. Тогда последовательность шаров[latex]\left\{B_s\right\}^{\infty}_{s=1}[/latex] покрывает все пространство [latex]\mathbb{R}^n[/latex], а следовательно, и множество [latex]K[/latex]. Так как [latex]K[/latex] компактно, следовательно, оно может быть покрыто конечным набором шаров [latex]B_s[/latex]. Среди всех этих шаров выберем шар с наибольшим радиусом. Пусть это шар [latex]B^{\ast}[/latex]. Тогда ясно, что [latex]K \subset B^{\ast}[/latex], так что [latex]K[/latex] ограничено. Покажем теперь, замкнутость множества [latex]K[/latex]. Для этого достаточно показать, что любая точка [latex]y \notin K[/latex], не будет предельной для [latex]K[/latex]. Итак, пусть [latex]y \notin K[/latex]. Рассмотрим множества [latex]G_k = c\overline{B}(y, \frac{1}{k}) (k = 1,2,…)[/latex]. Так как замкнутый шар [latex]\overline{B}(y, \frac{1}{k})[/latex] – множество замкнутое, следовательно его дополнение [latex]G_k[/latex] открыто. Кроме того, ясно, что[latex] \bigcup^{\infty}_{k=1}G_k = \mathbb{R}^n \setminus \left\{y\right\}[/latex]. Поскольку [latex]y \notin K[/latex], то совокупность множеств [latex]G_k (k = 1,2,…)[/latex] образует открытое покрытие множества [latex]K[/latex]. Пользуясь компактностью [latex]K[/latex], выберем из этого покрытия конечное подпокрытие [latex]\left\{G_{k_1},…,G_{k_s}\right\}[/latex] и положим [latex]\rho = \frac{1}{max\left\{k_1,…,k_s\right\}} > 0[/latex]. Отсюда следует, что шар [latex]B(y,\rho)[/latex] не имеет общих точек с множеством [latex]K[/latex]. Получаем, что точка [latex]y[/latex] не будет предельной для [latex]K[/latex]. [latex]\square[/latex]

Литература:

Лемма Гейне-Бореля

Лемма (Гейне – Бореля). Произвольный сегмент в [latex]\mathbb{R}^n[/latex] является компактным множеством .

Доказательство. Обозначим через [latex]I = [a^1,b^1;…;a^n,b^n][/latex] – сегмент в [latex]\mathbb{R}^n[/latex]. Докажем от противного. Пусть данный сегмент не является компактным. Тогда найдется такое открытое покрытие [latex]\Omega[/latex] сегмента [latex]I[/latex], что никакое конечное подсемейство множеств из [latex]\Omega[/latex] не покрывает [latex]I[/latex]. Все стороны [latex][a^i,b^i][/latex] сегмента [latex]I[/latex] разделим пополам. Таким образом данный сегмент можно разбить на [latex]2^n[/latex] сегментов. По крайней мере один из них не покрывается конечным подсемейством множеств из [latex]\Omega[/latex]. В противном случае, исходный сегмент [latex]I[/latex] также мог бы быть покрытым конечным набором множеств из [latex]\Omega[/latex], что приводит к противоречию. Обозначим через [latex]I_1[/latex] тот из подсегментов [latex]I[/latex], который не может быть покрыт конечным набором множеств из [latex]\Omega[/latex]. Каждую из сторон сегмента [latex]I_1[/latex] опять разделим пополам и среди полученных [latex]2^n[/latex] сегментов, на которые окажется разбитым [latex]I_1[/latex], возьмем тот, который не покрывается конечным подсемейством множеств из [latex]\Omega[/latex]. Обозначим его через [latex]I_2[/latex] и так далее. Продолжая подобные действия, получим последовательность вложенных сегментов [latex]I \supset I_1 \supset I_2 \supset … \supset I_{\nu} \supset …[/latex], таких, что любой из сегментов [latex]I_{\nu}[/latex] не может быть покрыт каким-либо конечным подсемейством множеств из [latex]\Omega[/latex]. Заметим также, что [latex]diam \> I_{\nu} = \frac{diam \> I}{2^{\nu}} \mapsto 0 (\nu \mapsto \infty)[/latex]. Применив к полученной последовательности [latex]I_{\nu}[/latex] лемму о вложенных сегментах, найдем точку [latex]x_0 \in I_{\nu} (\nu = 1,2,…)[/latex]. Поскольку [latex]x_0 \in I[/latex], а [latex]I[/latex] покрыт семейством [latex]\Omega[/latex] открытых множеств, то найдется такое открытое множество [latex]F \in \Omega[/latex], что [latex]x_0 \in F[/latex]. Поскольку множество [latex]F[/latex] открытое и точка [latex]x_0 \in F[/latex], то эта точка внутренняя в [latex]F[/latex]. Это означает, что найдется такая окрестность [latex]B(x_0,\delta)[/latex] точки [latex]x_0[/latex], которая целиком содержится во множестве [latex]F[/latex]. Но поскольку диаметры сегментов [latex]I_{\nu}[/latex] стремятся к нулю при [latex]\nu \mapsto \infty[/latex], то, начиная с какого-то номера [latex]\nu_0[/latex], они будут меньшими, чем [latex]\delta[/latex], то есть. [latex]diam \> I_{\nu} < \delta (\nu \geq \nu_0)[/latex]. Учитывая, что [latex]x_0 \in I_{\nu}[/latex], получаем, что [latex]I_{\nu} \subset B(x_0,\delta)[/latex], а значит, [latex]I_{\nu} \subset F[/latex]. Итак, мы получили, что при [latex]\nu \geq \nu_0[/latex] сегмент [latex]I_{\nu}[/latex] содержится во множестве [latex]F[/latex]. Но это противоречит выбору сегментов [latex]I_{\nu}[/latex], поскольку они были выбраны так, что никакое конечное подсемейство множеств из [latex]\Omega[/latex] не покрывает [latex]I_{\nu}[/latex]. Полученное противоречие завершает доказательство. [latex]\square[/latex]

Литература: