Операции над мощностями

Мощности конечных множеств - натуральные числа, и их можно складывать, умножать, возводить в степень. Эти операции можно обобщить и на мощности бесконечных множеств, и делается это так.

Пусть $$A$$ и $$B$$ - два множества. Чтобы сложить их мощности, надо взять мощность множества $$A\hm\cup B$$, если $$A$$ и $$B$$ не пересекаются. Если они пересекаются, то их надо заменить на непересекающиеся равномощные им множества $$A'$$ и $$B'$$. Мощность объединения и будет суммой мощностей множеств $$A$$ и $$B$$.

Замечания.

Последней проблемы не будет при определении произведения мощностей как мощности декартова произведения $$A\hm\times B.$$ (Но остальные замечания остаются в силе.)

Теперь определим возведение в степень. Для этого рассмотрим (для данных $$A$$ и $$B$$ ) множество всех функций вида $$f\colon B\hm\to A$$ (напомним: это означает, что их область определения есть $$B$$, а область значений содержится в $$A$$ ). Это множество обозначается $$A^B$$, и его мощность и будет результатом операции возведения в степень.

Если множества $$A$$ и $$B$$ конечны и содержат $$a$$ и $$b$$ элементов соответственно, то $$A^B$$ содержит как раз $$a^b$$ элементов. В самом деле, определяя функцию $$f\colon B\hm\to A$$, мы должны определить ее значение на каждом из $$b$$ элементов. Это можно сделать $$a$$ способами, так что получаем всего $$a^b$$ вариантов.

66. Чему равно $$0^0$$ согласно нашему определению?

Пример. Обозначим через $$2$$ какое- нибудь множество из двух элементов, например, $$\{0,1\}$$. Что такое $$2^\mathbb{N}$$? По определению это множество функций $$f\colon\mathbb{N}\hm\to\{0,1\}$$. Такие функции - это по существу последовательности нулей и единиц, только вместо $$f_0f_1f_2\dots$$ мы пишем $$f(0), f(1), f(2), \dots$$ (Формально последовательность элементов некоторого множества $$X$$ так и определяется - как функция типа $$\bbN\hm\to X$$.)

Заметим, что $$2^X$$ равномощно $$P(X)$$ (в частном случае $$X\hm=\bbN$$ мы это доказывали; для общего случая доказательство такое же).

Обычные свойства сложения и умножения (коммутативность, ассоциативность и дистрибутивность) сохраняют силу и для арифметики мощностей: $$\begin{align*} % a+b= b+a;\\ % a+(b+c)=(a+b)+c;\\ % a\times b= b\times a;\\ %\end{align*} %\begin{align*} % a\times (b \times c)= (a\times b)\times c;\\ % (a+b)\times c= (a\times c)+(b \times c). % \end{align*}$$

Формально их следует читать, избегая слова " мощность" как самостоятельного объекта: например, $$a\hm\times b\hm=b\hm\times a$$ означает, что $$A\hm\times B$$ и $$B\hm\times A$$ равномощны (и это легко проверить: $$\langle x,y\rangle \hm\mapsto \langle y,x\rangle$$ будет взаимно однозначным соответствием между ними). Остальные свойства доказываются столь же просто. Чуть сложнее свойства, включающие возведение в степень: $$\begin{align*} % a^{b+c}=a^b\times a^c;\\ % (ab)^c=a^c\times b^c;\\ % (a^b)^c=a^{b\times c}. % \end{align*}$$

Проверим первое из них. Из чего состоит $$A^{B+C}$$? (Будем считать, что $$B$$ и $$C$$ не пересекаются.) Его элементами являются функции со значениями в $$A$$, определенные на $$B\hm+C$$. Такая функция состоит из двух частей: своего сужения на $$B$$ (значения на аргументах из $$B$$ остаются теми же, остальные отбрасываются) и своего сужения на $$C$$. Тем самым для каждого элемента множества $$A^{B+C}$$ мы получаем пару элементов из $$A^B$$ и $$A^C$$. Это и будет искомое взаимно однозначное соответствие.

С соответствием между множествами $$(A\times B)^C$$ и $$A^C\hm\times B^C$$ мы тоже часто сталкиваемся. Например, элемент множества $$(\bbR\hm\times\bbR)^{\bbR}$$ есть отображение типа $$\bbR\hm\to\bbR\hm\times\bbR$$, то есть кривая $$t\hm\mapsto z(t)\hm= \langle x(t),y(t)\rangle$$ на плоскости. Такая кривая задается парой функций $$x,y\colon \bbR\hm\to\bbR$$.

Соответствие между $$(A^B)^C$$ и $$A^{(B\times C)}$$ встречается несколько реже. Элемент $$f\hm\in A^{(B\times C)}$$ является отображением $$B\hm\times C\hm\to A$$, то есть, в обычной терминологии, функцией двух аргументов (первый из $$B$$, второй из $$C$$ ). Если зафиксировать в ней второй аргумент, то получится функция $$f_c\colon B\hm\to A$$, определенная соотношением $$f_c(b)\hm=f(b,c)$$ (точнее, $$f(\langle b,c\rangle)$$ ). Отображение $$с\hm\mapsto f_c$$, принадлежащее $$(A^B)^C$$, и соответствует элементу $$f\hm\in A^{(B\times C)}$$. (Отчасти сходная конструкция встречается в алгебре, когда многочлен от двух переменных рассматривают как многочлен от одной переменной с коэффициентами в кольце многочленов от второй переменной.)

Мощность счетного множества символически обозначается $$\aleph_0,$$ мощность континуума (отрезка или множества бесконечных последовательностей нулей и единиц) обозначается $$\mathfrak{c}$$. По определению, $$\mathfrak{c}=2^{\aleph_0}$$.

(Естественный вопрос: каков смысл индекса $$0$$ в $$\aleph_0$$? что такое, скажем, $$\aleph_1$$? Обычно $$\aleph_1$$ обозначает наименьшую несчетную мощность (как мы увидим, такая существует). Гипотеза континуума, о которой мы упоминали ранее, утверждает, что $$\mathfrak{c}=\aleph_1$$.)

Известные нам свойства счетных множеств можно записать так:

Отсюда можно формально получить многие факты манипуляциями с мощностями. Например, цепочка равенств$$\mathfrak{c}\times \mathfrak{c} = 2^{\aleph_0}\times 2^{\aleph_0} = 2^{\aleph_0+\aleph_0} = 2^{\aleph_0} = \mathfrak{c}$$ показывает, что прямая и плоскость равномощны.

Аналогичным образом,$$\mathfrak{c}^{\aleph_0}= (2^{\aleph_0})^{\aleph_0}= 2^{\aleph_0 \times \aleph_0}= 2^{\aleph_0} = \mathfrak{c}.$$

67. Объясните подробно выкладку:

$$\mathfrak{c}+\mathfrak{c} = 1\times\mathfrak{c}+1\times\mathfrak{c}= 2\times\mathfrak{c}=2^1\times 2^{\aleph_0} = 2^{1+\aleph_0} = 2^{\aleph_0} = \mathfrak{c}.$$

68. Проверьте, что $$\aleph_0 \times \mathfrak{c} = \mathfrak{c}$$.

Приведенные нами свойства мощностей полезно сочетать с теоремой Кантора- Бернштейна. Например, заметим, что$$\mathfrak{c} = 2^{\aleph_0} \le {\aleph_0}^{\aleph_0} \le \mathfrak{c}^{\aleph_0} = \mathfrak{c},$$ поэтому $${\aleph_0}^{\aleph_0}= \mathfrak{c}$$ (словами: множество всех бесконечных последовательностей натуральных чисел имеет мощность континуума).

69. Последнее рассуждение неявно использует монотонность операции возведения в степень для мощностей (если $$a_1\hm\le a_2$$, то $$a_1^b \hm\le a_2^b$$ ). Проверьте это и аналогичные свойства для других операций (впрочем, почти очевидные).

70. Установите явное соответствие между последовательностями натуральных чисел и иррациональными числами на отрезке $$(0,1)$$, используя цепные дроби, то есть дроби вида $$1/(n_0\hm+1/(n_1\hm+1/(n_2+\ldots)))$$.

71. Проверьте, что $$\aleph_0 ^\mathfrak{c} \hm= 2^\mathfrak{c}$$. (Напомним, что по теореме Кантора эта мощность больше мощности континуума.)

72. Какова мощность множества всех непрерывных функций с действительными аргументами и значениями? Существенна ли здесь непрерывность?

73. Какова мощность множества всех монотонных функций с действительными аргументами и значениями?

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

Впоследствии мы увидим, что для бесконечных мощностей $$a\hm\times b \hm= a\hm+b \hm= \max(a,b)$$, но пока этого мы доказать не можем. Поэтому в задачах 47, 48, нам пришлось воспользоваться обходным маневром, чтобы доказать, что из $$a\hm+b\hm=\mathfrak{c}$$ следует $$a\hm=\mathfrak{c}$$ или $$b\hm=\mathfrak{c}$$. Следующее утверждение обобщает этот прием:

Теорема 10. Если множество $$A_1\hm\times A_2\hm\times\ldots\times A_n$$ разбито на непересекающиеся части $$B_1, \dots, B_n$$, то найдется такое $$i$$, при котором мощность $$B_i$$ не меньше мощности $$A_i$$.

Доказательство. В самом деле, рассмотрим проекцию множества $$B_i\hm\subset A_1\hm\times\ldots\hm\times A_n$$ на $$A_i$$. Если хотя бы при одном $$i$$ она покрывает $$A_i$$ полностью, то все доказано. Если нет, выберем для каждого $$i$$ непокрытую точку $$x_i$$. Набор $$\langle x_1,\dots,x_n\rangle$$ не входит ни в одно из множеств $$B_i$$, что противоречит предположению.

Заметим, что в формулировке этого утверждения (которое иногда называют теоремой Кенига) говорится о декартовом произведении конечного числа множеств, которое можно определить индуктивно (скажем, $$A\hm\times B\hm\times C$$ будет состоять из троек $$\langle a,b,c\rangle$$, которые суть пары $$\langle \langle a,b\rangle,c\rangle$$ ). Декартово произведение счетного числа множеств уже так не определишь. Выход такой: $$A_0\hm\times A_1\hm\times A_2 \hm\times\ldots$$ (счетное число сомножителей) можно определить как множество всех последовательностей $$a_0, a_1, a_2, \dots$$, у которых $$a_i\hm\in A_i$$, то есть как множество всех функций $$a$$, определенных на $$\bbN$$ со значениями в объединении всех $$A_i$$, причем $$a(i)\in A_i$$ при всех $$i$$. После такого определения теорема 10 легко переносится и на счетные (а также и на любые) произведения.

Переходя к отрицаниям, теорему Кенига можно сформулировать так: если при всех $$i=0,1,2,\ldots$$ для мощностей $$a_i$$ и $$b_i$$ выполнено неравенство $$b_i \hm< a_i$$, то$$b_0 + b_1 + b_2 + \ldots < a_0 \times a_1 \times a_2\times\ldots$$

Учитывая, что $$\mathfrak{c}\hm\times\mathfrak{c}\hm\times\ldots$$ (счетное произведение) равно $$\mathfrak{c}^{\aleph_0}$$, то есть $$\mathfrak{c}$$, можно сформулировать такое следствие теоремы Кенига: если континуум разбит на счетное число подмножеств, то одно из них имеет мощность континуума.

75. Докажите подробно это утверждение.

76. Пусть $$a_0,a_1,a_2,\ldots$$ - мощности, причем $$a_i\ge 2$$ для всех $$i$$. Покажите, что$$a_0 + a_1 + a_2 + \ldots \le a_0 \times a_1 \times a_2\times\ldots$$

77. Пусть $$m_0 < m_1 < m_2 <\dots$$ - возрастающая последовательность мощностей. Докажите, что сумма $$m_0\hm+m_1\hm+m_2\hm+\ldots$$ не представима в виде $$a^{\aleph_0}$$ ни для какой мощности $$a$$.