3.5 Мощность множеств. Счетные и несчетные множества.

3.5.1 Понятие мощности множества. Кардинальные числа.

Определение 3.5.1: Будем говорить, что множества $A$ и $B$ равномощны, если существует биективное отображение $f(x):A\to{B}$.

Утверждение 3.5.1: Понятие равномощности является отношением эквивалентности на классе всех подмножеств.

Доказательство: Обозначим отношение равномощности буквой $\mathcal{R}$, тогда $A\mathcal{R}B$ тогда и только тогда, когда существует биективное отображение $f(x):A\to{B}$. Докажем, что отношение равномощности является отношением эквивалентности.

1. Рефлексивность:
   $\forall{X}\in\mathcal{P}(A)(\exists{f}(x):X\to{X}:\forall{x}\in{X}(f(x)=x))$
   Отображение $f(x)$ биективно, следовательно, $X\mathcal{R}X$.
2. Симметричность:
   Для любых $X, Y\in\mathcal{P}(A)$ таких что $X\mathcal{R}Y$ существует биективное отображение $f(x):X\to{Y}$. Так как отображение $f(x)$ биективно, то существует обратное ему отображение $f^{-1}(x):Y\to{X}$, которое тоже будет биективным и, следовательно, $Y\mathcal{X}$.
3. Транзитивность:
   Для любых $X, Y, Z\in\mathcal{P}(A)$ таких, что $X\mathcal{R}Y, Y\mathcal{R}Z$ существуют биективные отображения $f(x):X\to{Y}, g(x):Y\to{Z}$. Докажем, что их композиция $(g\circ{f})(x):X\to{Z}$ тоже будет биективной. Действительно по сюръективности отображений $f(x),g(x)$ имеем $f(X)=Y, g(Y)=Z$, тогда $(g\circ{f})(X)=g(f(X))=g(Y)=Z$, то есть отображение $(g\circ{f})(x)$ - сюръективно. И по инъективности отображений $f(x),g(x)$ имеем $$\forall{x}_1,x_2\in{X}((g\circ{f})(x_1)=(g\circ{f})(x_2)\Rightarrow{g}(f(x_1))=g(f(x_2))\Rightarrow{f}(x_1)=f(x_2)\Rightarrow{x}_1=x_2),$$ то есть отображение $(g\circ{f})$ инъективно, а следовательно и биективно. Таким образом $X\mathcal{R}Z$.

Отношение равномощности принято отображать символом "$\sim$".
Согласно известной из курса алгебры теоремы отношение эквивалентности заданное на множестве разбивает множество на взаимно не пересекающиеся подмножества. Поэтому будет корректно следующее определение.

Определение 3.5.2: Мощность множества.
Мощностью множества $X$ будем называть подмножество, которому принадлежит множество $X$ в смысле введенного выше отношения равномощности.

Смысл определения в том, что мы отождествляем все множества равномощные данному. Мощность множества $X$ обозначают $card{X}$ и называют также кардинальным числом $X$. Таким обрзаом $$X\sim{Y}\Leftrightarrow{c}ard{X}=card{Y}$$

Определение 3.5.3: Говорят, что кардинальное число множества $X$ не больше кардинального числа множества $Y$, то есть $cardX\leq{c}ardY$, если существует $Y'\subset{Y}$ такое, что $cardY'=cardX$

Из определения следует, что для любых множеств $X,Y$ таких, что $X\subset{Y}$ $cardX\leq{c}ardY$.

Определение 3.5.4:Будем говорить, что множество $X$ состоит из $n\in\mathbb{N}$ элементов и $card{X}=n$, если $cardX=card\{\overline{1,n}\}$
По определению будем считать, что $card\varnothing:=0$

Определение 3.5.5: Будем говорить, что множество $X$ конечно, если оно пусто или $cardX\in\mathbb{N}$.

Определение 3.5.6:Множество бесконечно, если оно не конечно.

Определение бесконечного множества по Додекинду: множество $X$ бесконечно, если существует не пустое $X_0\subsetneq{X}$ такое что $cardX_0=cardX$.

Теорема 3.5.1: Основные свойства кардинальных чисел.

1. $\forall{X}(cardX\leq{c}ardY)$
2. Теорема Шредера - Бернштейна.
   $\forall{X},Y((cardX\leq{c}ardY\wedge{c}ardY\leq{c}ardX)\Rightarrow{c}ardX=cardY)$
3. $\forall{X},Y,Z((cardX\leq{c}ardY\wedge{c}ardY\leq{c}ardZ)\Rightarrow{c}ardX\leq{c}ardZ)$
4. $\forall{X},Y(cardX\leq{c}ardY\vee{c}ardY\leq{c}ardX)$

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

1. Следует из того, что $X\sim{X}$ и $X\subset{X}$.
2. С доказательством теоремы Шредера-Бернштейна можно ознакомится в Википедии.
3. $cardX\leq{c}ardY\Rightarrow\exists{Y'}\subset{Y}:cardX=cardY'$
   $cardY\leq{c}ardZ\Rightarrow\exists{Z'}\subset{Z}:cardY=cardZ'$
   То есть существуют биективные отображения $f(x):X\to{Y'}, g(x):Y\to{Z'}$, тогда отображение $g'(x):Y'\to{g}(Y')\subset{Z'}\subset{Z}$ тоже будет биективно. Так как выше было доказано, что композиция биективных отображений биективно, то $(f\circ{g}):X\to{g}(Y')\subset{Z}$ будет биективно и, следовательно, $cardX\leq{c}ardY$
4. Зорич т. 1 стр. 31 ссылается на какую-то теорему Кантора.

Таким образом отношение "$\leq$" на множестве кардинальных чисел является отношением линейного порядка.
Если отображение $f(x):X\to{Y}$ инъективно, то $cardX=cardf(X)\subset{Y}$ и, следовательно, $cardX\leq{c}ardY$.

Определение 3.5.7: $cardX<cardY:=cardX\leq{c}ardY\wedge{c}ardX\neq{c}ardY$.

Теорема 3.5.2: Теорема Кантора.
$$X\neq\varnothing\Rightarrow{c}ardX<card\mathcal{P}(X)$$

Доказательство: Поскольку множество $\mathcal{P}(X)$ содержит все одноэлементные подмножества множества $X$, которые можно биективно отобразить на множество элементов на множества $X$, то $cardX\leq{c}ard\mathcal{P}(X)$.
Докажем от противного, что $cardX\neq{c}ard\mathcal{P}(X)$. Допустим $cardX=card\mathcal{P}(X)$, тогда существует биективное отображение $f(x):X\to\mathcal{P}(X)$. Рассмотрим множество $A:=\{x\in{X}\:|\:x\notin{f}(x)\}$. Отображение $f(x)$ биективно, следовательно, оно сюръективно, следовательно, существует $a\in{X}$ такой, что $f(a)=A$.
Если $a\in{A}$, то $a\in{f}(a)$, так как $A=f(a)$, но тогда по построению множества $A$: $a\notin{A}$
Если $a\notin{A}$, то $a\notin{f}(a)$, так как $A=f(a)$, но тогда по построению множества $A$: $a\in{A}$. Таким образом обе альтернативы не возможны, получено противоречие.

3.5.2 Счетные и несчетные множества.

Определение 3.5.8: Множество $X$ называют счетным если $cardX=card\mathbb{N}$.

Другими словами, множество $X$ счетно, если существует биективное отображение $f(x):X\to\mathbb{N}$.

Теорема 3.5.3: Основные свойства счетных множеств.

1. Бесконечное подмножество счетного множества - счетно.
2. Если $X$ - счетно, то $cardX^2=cardX$.
3. Конечное или счетное объединение счетных множеств - счетно.

Доказательство: Не теряя общности можно доказывать все свойства на примере эталонного счетного множества - множества натуральных чисел $\mathbb{N}$.

1. Пусть $X\subset\mathbb{N}$ и $X$ - бесконечно. Опишем алгоритм.
   1) Поскольку $X\subset\mathbb{N}$, то $X$ - ограничено снизу, следовательно, в $X$ существует минимальных элемент $e_1:=\min{X}$.
   2) $X\backslash\{e_1\}$ - не пустое и бесконечное подмножество $\mathbb{N}$, следовательно, существует $e_2:=\min{X}\backslash\{e_1\}$.
   ...
   n) $X\backslash\{e_1,e_2,...,e_n\}$ - не пустое и бесконечно подмножество $\mathbb{N}$, следовательно, существует $e_n:=\min{X}\backslash\{e_1,e_2,...,e_n\}$
   ...
   Описанный алгоритм не остановится на конечном шаге, то есть каждому натуральному числу $n$ поставлено в соответствие $e_n\in{X}$. Отображение $f(x):\mathbb{N}\to{X}: f(n)=e_n$ инъективно в силу единственности минимального элемента, докажем его сюръективность. Действительно:
   $\forall{e}\in{X}(M_e:=\{x\in{X}\:|\:x\leq{e}\})$
   $X\subset\mathbb{N}\Rightarrow{M}_e\subset\{\overline{1,e}\}\Rightarrow{c}ardM_e\leq{c}ard\{\overline{1,e}\}=e\Rightarrow \exists{m}=cardM_e\in\mathbb{N}:f(m)=e$
2. Докажем, что $card\mathbb{N}^2=card\mathbb{N}$
   $\forall{x},y\in\mathbb{N}(x\neq{y}\Rightarrow\exists(1,x),(1,y)\in\mathbb{N}^2:(1,x)\neq(1,y))\Rightarrow{c}ard\mathbb{N}\leq{c}ard\mathbb{N}^2$
   Рассмотрим отображение $g:\mathbb{N}^2\to\mathbb{N}:g(m,n)=\frac{(m+n)(m+n-1)}{2}-m+1$.
   Докажем инъективность отображения $g$, то есть докажем, что $$\forall{m},n,p,q\in\mathbb{N}((m+n)(m+n-1)-2m=(p+q)(p+q-1)-2p\Rightarrow(m=p\wedge{n}=q)$$ Делаем замену: $k:=m+n>m,r:=p+q>p$, получим что надо доказать $(k(k-1)-2m=r(r-1)-2p\wedge{k}>m\wedge{r}>p)\Rightarrow(m=p\wedge{k}=r)$.
   Докажем от противного, пусть $$k(k-1)-2m=r(r-1)-2p\wedge{k}>m\wedge{r}>p\wedge(m\neq{p}\vee{k}\neq{r}).$$ $$(m\neq{p}\vee{k}\neq{r})\Leftrightarrow((m\neq{p}\wedge{k}=r)\vee(m=p\wedge{k}\neq{r})\vee(m\neq{p}\wedge{k}\neq{r}))$$
   • В первом случае приходим к противоречию, так как $k=r\Rightarrow-2m=-2p\Rightarrow{m}=p$
   • Во втором случае приходим к противоречию так как $m=p\Rightarrow{k}(k-1)=r(r-1)\Rightarrow{k}^2-r^2-(r-k)=0\Rightarrow$ $ (r-k)(r+k-1)=0\Rightarrow{k}=r$, так как $k+r-1>0$.
     
   • Рассмотрим третий случай $$(m\neq{p}\wedge{k}\neq{r})\Leftrightarrow((m\neq{p}\wedge{k}>r)\vee(m\neq{p}\wedge{k}<r))$$ Рассмотрим случай $m\neq{p}$ и $k>r$ $$k>r\Rightarrow\exists{t}\in\mathbb{N}:k=r+t$$ Докажем индукцией по $t$, что для любых $r,t,m,p\in\mathbb{N}$ таких что $k=r+t>m$ верно $(r+t)(r+t-1)-2m>r(r-1)-2p$.
     При $t=1,k=r+1$ имеем $(r+1)r-2m-(r(r-1)-2p)=2r-2m+2p=2k-2-2m+2p>0$, так как $k>m,p\geq1$.
     Если верно неравенство $(r+s)(r+s-1)-2m>r(r-1)-2p$, то будет верно и неравенство $(r+s+1)(r+s)-2m>r(r-1)-2p$, так как левая часть неравенства растет с ростом $s$, а правая от $s$ не зависит.
     Аналогичным образом доказывается, что при $m\neq{p}$ и $k<r$ $k(k-1)-2m<r(r-1)-2p$.
   Таким образом отображение $g$ инъективно, следовательно, $card\mathbb{N}^2\leq{c}ard\mathbb{N}$ и тогда $card\mathbb{N}^2=card\mathbb{N}$.
3. Пусть $X_1,X_2,...,X_n,...$ - счетная совокупность счетных множеств. Обозначим элементы множеств следующим образом: $X_m=\{x_{m1},x_{m2},...,x_{mn},...\}$. $$X:=\bigcup_{m\in\mathbb{N}}X_m$$ $\forall{x}\in{X}(\exists{m},n\in\mathbb{N}:x=x_{mn}\Rightarrow\exists{f}(x):X\to\mathbb{N}^2:\forall{x}\in{X}(f(x)=(m,n)))$
   Отображение $f(x)$ инъективно, следовательно, $cardX=cardf(X)\leq{c}ard\mathbb{N}^2=card\mathbb{N}$.
   С другой стороны $$X_1\subset{X}\Rightarrow(cardX_1\leq{c}ardX\wedge{c}ardX_1=card\mathbb{N})\Rightarrow{c}ard\mathbb{N}\leq{X}.$$

Определение 3.5.9:Будем называть множество не более чем счетным, если оно конечно или счетно.

Следствие 1:

1. Множества $\mathbb{Z},\mathbb{Q}$ счетны.
2. Множества $\mathbb{Z}^2,\mathbb{Q}^2$ счетны.
3. Множество алгебраических чисел счетно.
4. Если множество $X$ бесконечно, то $card\mathbb{N}\leq{c}ard{X}$. То есть всякое бесконечное множество содержит счетное подмножество, таким образом среди бесконечных кардинальных чисел $card\mathbb{N}$ минимально.
5. Если множество $X$ бесконечно и $cardY\leq{c}ard\mathbb{N}$, то $card{X\cup{Y}}=card{X}$
6. $card(\mathbb{R}\backslash\mathbb{Q})=card\mathbb{R}$
7. Если $T$ множество трансцендентных чисел, то $cardT=card\mathbb{R}$

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

1. Рассмотрим отображение $f(x):\mathbb{N}\to\mathbb{Z}$ такое, что $f(1)=0$, $\forall{k}\in\mathbb{N}(f(2k)=k,f(2k+1)=-k)$. Отображение $f(x)$ биективно, следовательно, $card\mathbb{Z}=card\mathbb{N}$
   Множество $\mathbb{Q}$ счетно так как существует инъективное отображение из $\mathbb{Q}$ в $\mathbb{Z}^2$, в силу того, что любое рациональное число задается парой взаимно простых целых чисел.
2. Множества $\mathbb{Z}^2$ и $\mathbb{Q}^2$ счетны как квадраты счетных.
3. Так как множество корней любого многочлена конечно (не превосходит степени многочлена) и мощность множества многочленов степени $n\in\mathbb{N}$ равна $\mathbb{Q}^n$, то множество корней многочленов степени $n$ счетно. Следовательно, множество алгебраических чисел счетно, как мощность счетной совокупности счетных множеств.
4. Предположим противное, то есть множество $X$ бесконечно, $cardX\leq{c}ard\mathbb{N}$ и $cardX\neq{c}ard\mathbb{N}$, тогда $$cardX\leq{c}ard\mathbb{N}\Rightarrow\exists{M}\subset\mathbb{N}:cardM=cardX\Rightarrow{M} - бесконечно\Rightarrow{c}ardM=card\mathbb{N}\Rightarrow cardX=card\mathbb{N}$$
5. Рассмотрим случай, когда множества $X$ и $Y$ не пересекаются.
   Множество $X$ - бесконечно, следовательно, по пункту 4 $card\mathbb{N}\leq{c}ardX$, тогда $$\exists{M}\subset{X}:cardM=card\mathbb{N}\Rightarrow{c}ard(M\cup{Y})=card\mathbb{N}$$ Следовательно, существует биективное отображение $g(x):M\to{M}\cup{Y}$. Рассмотрим отображение $f(x):X\to{X}\cup{Y}: f(x)=\begin{cases} g(x),\:x\in{M}\\x,\quad\;\:x\notin{M} \end{cases}$. Докажем, что отображение $f(x)$ инъективно.
   • $\forall{x},y\in{M}(x\neq{y}\Rightarrow{f}(x)=g(x)\neq{g}(y)=f(y))$ (по инъективности $g$)
   • $\forall{x},y\notin{M}(x\neq{y}\Rightarrow{f}(x)=x\neq{y}=f(y))$
   • $\forall{x}\in{M},\forall{y}\notin{M}(x\neq{y}\Rightarrow(f(x)=g(x)\in{M}\cup{Y}\wedge{f}(y)=y\notin{M}\wedge{y}\notin{Y}\Rightarrow f(x)\in{M}\cup{Y}\wedge{f}(y)\notin{M}\cup{Y}\Rightarrow{f}(x)\neq{f}(y))$.
   Докажем, что отображение $f(x)$ сюръективно.
   $y\in{M}\cup{Y}\Rightarrow\exists{x}=g^{-1}(y):f(x)=y$
   $y\notin{M}\cup{Y}\Rightarrow{y}\notin{M}\Rightarrow\exists{x}=y:f(x)=y$.
   Таким образом отображение $f(x)$ биективно и, следовательно, $card(X\cup{Y})=cardX$.
   Если множества $X$ и $Y$ пересекаются, то $card(X\cup{Y})=card(X\cup(Y\backslash{X})$, где множество $X$ - бесконечно, $card(Y\backslash{X})\leq{c}ardY\leq{c}ard\mathbb{N}$ и множества $X$ и $Y\backslash{X}$ не пересекаются, следовательно, можно повторить приведенное выше доказательство для множеств $X$ и $Y\backslash{X}$.
6. Множество $\mathbb{R}\backslash\mathbb{Q}$ бесконечно так как бесконечно множество $\{k\sqrt{2}\:|\:k\in\mathbb{N}\}$. Тогда по пункту 5: $card(\mathbb{R}\backslash\mathbb{Q})=card((\mathbb{R}\backslash\mathbb{Q})\cup\mathbb{Q})=card\mathbb{R}$
7. Если $M$ множество алгебраических чисел, то $T=\mathbb{R}\backslash{M}$. Так как $M$ - счетно, то утверждение следует из пункта 5 аналогично пункту 6.

Определение 3.5.10: Число $card\mathbb{R}$ будем называть континуумом или числовым континуумом.

Так как $\mathbb{N}\subset\mathbb{R}$, то $card\mathbb{N}\leq{c}ard\mathbb{R}$.
Теорема Кантора, которая будет доказана в следующем разделе после доказательства принципа Коши - Кантора, утверждает, что имеет место строгое неравенство $card\mathbb{N}<card\mathbb{R}$.

Определение 3.5.11: Всякое множество удовлетворяющее условию $cardX>card\mathbb{N}$ называется несчетным.

Гипотеза (проблема) континуума: существует ли множество $M$ такое что: $card\mathbb{N}<cardM<card\mathbb{R}$. То есть существует ли несчетное множество менее мощное чем континуум. В 1963 году Питер Коуэн доказал, что в рамках существующей аксиоматики гипотезу континуума нельзя ни доказать, ни опровергнуть.

previous contents next