Теория функций действительного переменного/Счётные множества

Теория функций действительного переменного

Определение 1: Множество A называется счётным, если оно эквивалентно множеству $\mathbb {N}$ всех натуральных чисел. Иначе говоря, для счетного множества A существует биекция $f:\mathbb {N} \to A$ , а зто означает, что элементы множества А можно записать в виде последовательности a₁, a₂,... a_n... в котороЙ нет равных членов, и каждый элемент из A равен одному из членов последовательности.

Пример: Множество $\mathbb {Z}$ всех целых чисел счетно ,так как eгo можно записать в виде следующей последовательности: 0,1,-1,2,-2,..n,-n,... Счетны также множества $\{1,{\frac {1}{2}},{\frac {1}{3}}...{\frac {1}{n}},...\}$ , {2, 2²,2³,...2ⁿ...}, {1³,2³,...n³,...}.

Теорема 1: Множество всех пар натуральных чисел счетно, то есть $\mathbb {N} \times \mathbb {N} \sim \mathbb {N}$ .

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

Доказательство проиллюстрируем следующим рисунком (в отличие от русской матем.символики здесь «/» обозначает не дробь, а стоит вместо запятой, обозначая упорядоченную пару-элемент N*N):

.

В результате расстановки, указанной стрелками, все элементы приобретут номер, и, значит, это множество- счётное.

Теорема 2: Декартово произведение конечного числа счетных множеств есть множество счетное.

Доказательство проведём методом математической индукции.
1) Пусть множества A₁ и A₂ счётные, то есть $A_{1}\sim \mathbb {N}$ и $A_{2}\sim \mathbb {N}$ . Тогда по теореме 2 из главы "Эквивалентные множества" $A_{1}\times A_{2}\sim \mathbb {N} \times \mathbb {N}$ . Так как по предыдущей теореме $\mathbb {N} \times \mathbb {N} \sim \mathbb {N}$ , то $A_{1}\times A_{2}\sim \mathbb {N}$ .
2) Допустим, что теорема верна для случая n сомножителей, и докажем её справедливость для (n+1) сомножителя. Пусть множества A₁, A₂,... A_n+1 счётны. Сопоставляя элементу $((a_{1},a_{2},...a_{n}),a_{n+1})$ из элемент $(a_{1},a_{2},...a_{n},a_{n+1})$ из $A_{1}\times A_{2}\times ...\times A_{n}\times A_{n+1}$ , получим биекцию множества $(A_{1}\times A_{2}\times ...\times A_{n})\times A_{n+1}$ на множество $A_{1}\times A_{2}\times ...\times A_{n}\times A_{n+1}$ . Следовательно, $(A_{1}\times A_{2}\times ...\times A_{n})\times A_{n+1}\sim A_{1}\times A_{2}\times ...\times A_{n}\times A_{n+1}$ . Но по предположению индукции $A_{1}\times A_{2}\times ...\times A_{n}\sim \mathbb {N}$ . Поэтому, применяя уже доказанный частный случай теоремы для декартова произведения двух сомножителей, получим $(A_{1}\times A_{2}\times ...\times A_{n})\times A_{n+1}\sim \mathbb {N}$ .Следовательно, и $A_{1}\times A_{2}\times ...\times A_{n}\times A_{n+1}\sim \mathbb {N}$ .
Пример: Множество всех точек на плоскости $\mathbb {N} ^{2}$ с целыми координатами счетно. Действительно, это множество есть $\mathbb {Z} ^{2}=\mathbb {Z} \times \mathbb {Z}$

Теорема 3: Всякое бесконечное множество содержит счетное подмножество.

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

Пусть множество B бесконечно. Тогда оно содержит хотя бы один элемент a₁. В силу бесконечности B в нём найдется элемент a₂, отличный от a₁. Так как злементы a₂ и a₁ не исчерпывают всего множества B, то в нём найдется элемент a₃, отличный и от a₂ и от a₁. Если уже выделено n элементов a₁, a₂,...a_n, то в силу бесконечности B в нём найдётся еще один элемент, который обозначим a_n+1, отличный от всех ранее выбранных элементов. Таким образом, для каждого натурального числа n можно выделить элемент a_n из B, причём все выделенные элементы попарно различны. Выделенные элементы образуют последовательность a₁, a₂,...a_n.... Множество её членов по определению счётно, и это множество есть часть B.

Теорема 4: Всякое бесконечное подмножество счётного множества счётно.

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

Пусть множество A счётно, а B- его бесконечное подмножество. По предыдущей теореме множество B содержит счётное подмножество C. Так как множества A и C оба счётны, то они эквивалентны:A~C . Кроме того, $C\subset B\subset A$ . По теореме 4 главы 1 B~A, то есть множество B эквивалентно счётному множеству и потому само счётно.

Теорему 4 можно перефразировать следующим образом: 4': Всякое подмножество счётного множества конечно или счётно.

Теорема 5: При любом отображении образ счётного множества конечен или счётен.

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

Пусть множество A счётно, а множество B произвольно и f:A→B- некоторое отображение. Требуется доказать, что множество $C=f(A)$ конечно или счётно. Выберем для любого элемента $c\in C$ в его полном прообразе f^-1 произвольным образом точку a_c. В результате образуется множество $A_{1}=\{a_{c}\}_{c\in C}$ , являющееся частью счётного множества A, и потому, согласно <теореме 4'>, конечное или счётное. Так как для различных элементов c и c' из C их полные прообразы f^-1(c) и f^-1(c') не пересекаются, то $a_{c}\neq a_{c'}$ , и, следовательно, соответствие $c\mapsto a_{c}$ является биекцией множества C на множество A₁. Поэтому вместе с множеством A₁ и множество C конечно или счётно.

Теорема 6: Множество $\mathbb {Q}$ счётно.

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

Так как множество $\mathbb {Z}$ счётно, то по теореме 2 и декартово произведение $\mathbb {Z} \times \mathbb {N}$ счётно. Поставим в соответствие произвольному элементу (p,q) из $\mathbb {Z} \times \mathbb {N}$ рациональное число ${\frac {p}{q}}$ . Получившееся отображение $f:\mathbb {Z} \times \mathbb {N} \to \mathbb {Q}$ сюръективно. Действительно, всякое рациональное число r можно представить в виде отношения двух целых чисел: $r={\frac {p}{q}}$ , причём знаменатель можно считать положительным; тогда пара (p,q) является, очевидно, прообразом точки r относительно отображения f. Таким образом, множество $\mathbb {Q}$ счётно как образ счётного множеста при некотором отображении, учитывая при этом, что конечным оно заведомо не является.

Пример: Множество рациональных точек интервала (a,b) счётно. Дейтвительно, это множество бесконечно и является частью счётного множества $\mathbb {Q}$ , поэтому по теоремам 6 и 4 оно счётно.

Теорема 7: Всякое семейство $\{\Delta _{x}\}_{x\in X}$ попарно не пресекающихся непустых интервалов конечно или счётно.

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

Как известно, всякий интервал содержит бесконечно много рациональных точек. Выберем из каждого интервала $\Delta _{x}$ одну рациональную точку r_x. Получившееся множество $A=\{r_{x}\}_{x\in X}$ как часть счётного множества $\mathbb {Q}$ конечно или счётно. Так как исходное множество интервалов $\{\Delta _{x}\}_{x\in X}$ , очевидно, эквивалентно множеству A, то оно тоже конечно или счётно.

Теорема 8: Объединение конечной или счётной совокупности конечных или счётных множеств конечно или счётно.

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

Если $A=\bigcup _{n=1}^{k}A_{n}$ , где все слагаемые являются множествами конечными или счётными, то, полагая для любого натурального числа m>k A_m=A_k, получим $A=\bigcup _{n\in \mathbb {N} }A_{n}$ , то есть случай конечного объединения сводится к случаю счётного объединения, каковой мы и будем дальше предполагать выполненным.

Занумеруем элементы множества A_n в последовательность

a_n1, a_n2,... a_nm…, (*)

причём, если A_n конечно и содержит k_n элементов, то будем считать, что первые k_n членов этой последовательности попарно различны и исчерпывают всё множество A_n, а для m>k_n, полагаем a_nm=a_{nk_n}.

Зададим теперь отображение $f:\mathbb {N} \times \mathbb {N} \to A$ формулой f(n,m)=a_nm.
. Тогда отображение f сюръективно. Действительно, если $a$ есть любой элемент из А , то он принадлежит некоторому слагаемому A_n и потому совпадает с каким-ни6удь членом проследовательиости (*):a=a_nm. Ясно, что в таком случае пара натуральных чисел (n,m) будет проо6разом элемента $a$ относительно отображения $f$ . Итак, А есть образ счетного множества $\mathbb {N} \times \mathbb {N}$ при отображении f. Поэтому А конечно или счетно.

Примеры представления в форме последовательности некоторых объединений:

$\{2,3,4\}\cup \{1,{1 \over 2},...{1 \over n}...\}=\{2,3,4,1,{1 \over 2},...{1 \over n}...\}$
$\{1,2,...n...\}\cup \{{\frac {1}{2}},{\frac {2}{3}}...{\frac {n}{n+1}}...\}=\{1,{\frac {1}{2}},2,{\frac {2}{3}}...n,{\frac {n}{n+1}}...\}$
$\{2,2^{2}...2^{n}...\}\cup \{3,3^{2}...3^{n}...\}\cup \{5,5^{2},...5^{n}...\}=\{2,3,5,2^{2},3^{2},5^{2},...2^{n},3^{n},5^{n}...\}$

Определение 2: Действительное число $x$ называется алгебраическим, если оно является корнем многочлена с целыми коэффициентами. Пример: Всякое рациональное число $r={\frac {p}{q}}$ является алгебраическим, так как оно есть корень многочлена qx-p.

Теорема 9: Множество всех алгебраических чисел счетно

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

Сопоставляя многочлену $a_{0}+a_{1}x+...+a_{n}x^{n}$ с целыми коэффициентами элемент (a₀,a₁,...a_n) из декартова произведения $\mathbb {Z} ^{n+1}$ , получим биекцию между множеством всех многочленов A_n степени не выше n и декартовым произведением $\mathbb {Z} ^{n+1}$ . Отсюда в силу счетности множества $\mathbb {Z} ^{n+1}$ следует счётность множества A_n. Так как множество всех многочленов с целыми коэффициентами представляется, очевидно,в виде $A=\cup _{n\in \mathbb {N} }A_{n}$ , то по теореме 8 множество A счётно. Наконец, учитывая, что многочлен степени n имеет не более n корней, получаем, что множество всех алгебраических чисел представляется в виде счетного объъединения конечных множеств и, следовательно, по теореме 8 конечно или счетно, причем конечность невозможна. так как уже множество рациональных чисел, являющееся подмножеством множества алгебраических чисел, бесконечно.

Теорема 10: Если множество B бесконечно, а А конечно или счетно, то $A\cup B\sim B$ .

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

Согласно теореме 3 множество B содержит счётное подмножество С. Множество A\B как часть конечного или счетного множества A само конечно или счётно. Поэтому по теореме 8 множество $C\cup (A\setminus B)$ счетно. Нетрудно проверить (и это предлагается проделать самостоятельно) справедливость следующих двух равенств:

$A\cup B=(B\setminus C)\cup [C\cup (A\setminus b)]$
$B=(B\setminus C)\cup C$

Очевидно, $(B\setminus C)\cap C=\varnothing$ и $(B\setminus C)\cap [C\cup (A\setminus B)=\varnothing$ . Так как B\C~B\C, и в силу счётности множеств C и $C\cup (A\setminus B)$ они тоже эквивалентны, то по теореме 3 главы 1 $A\cup B\sim B$

Следствие: Если a>b , то (a,b)~(a,b]~[a,b]. Пример биекции f между [0,1] и [0,1) даёт следующая формула $f(n)={\begin{cases}x,&{\mbox{npu }}x\neq {\frac {1}{n}},\;\;n\in \mathbb {N} \\{\frac {1}{n+1}}&{\mbox{npu }}x={\frac {1}{n}}\end{cases}}$ или геометрически:Файл:Файл.

Замечание: Из теоремы 10 следует, что всякое бесконечное множество содержит эквивалентное ему собственное подмножество, конечное же множество таким свойством не обладает. Поэтому свойство множества иметь эквивалентную ему правильную часть можно принять за определение бесконечного множества.

УпражненияПравить

Доказать, что множество всех точек плоскости с рациональными координатами счётно.
Доказать, что множество всех интервалов с рациональными концами счётно.
Пусть A- такое множество вещественных чисел, что расстояние между любыми двумя из этих чисел больше 1. Доказать, что A конечно или счётно.
Доказать, что множество точек разрыва монотонной функции, определенной на всей числовой прямой, конечно или счётно.
Доказать, что всякое множество попарно не пересекающихся кругов на плоскости конечно или счётно.
Пусть A- такое множество точек плоскости, что расстояние между любыми двумя из этих точек больше фиксированного числа a>0. Доказать, что A конечно или счётно.
Показать, что множество всех конечных подмножеств натурального ряда счётно.
Доказать, что множество всех треугольников на плоскости, у которых координаты всех вершин рациональны, счётно.
Доказать, что множество всех многоугольников на плоскости, у которых координаты всех вершин рациональны, счётно.
Будет ли счетным множество всех многочленов, коэффициентами которых служат алгебраические числа?
Установите биекцию между [0,1] и (0,1).
Установить биекцию между (0,2) и $(0.1)\cup (1,2)$ .
Установить биекцию между внутренностью единичного круга на плоскости и его внешностью.
Установить биекцию между внешностью единичного круга и всей плоскостью.