Одной из задач теории множеств является определение числа элементов множества и исследование вопроса о сравнении друг с другом двух множеств по количеству элементов.
Для конечных множеств самой разной природы эта задача легко решается непосредственным подсчетом. Для бесконечных – с помощью взаимно однозначного (биективного) отображения. Рассмотрим примеры построения такого отображения.
Задача 1. В качестве множества А рассмотрим интервал на числовой прямой, пусть А=(–1, 1), а в качестве множества В –множество действительных чисел R. Это множества одинаковой мощности, т.к отображение f(x) = tg(px/2), хÎА позволяет установить между ними искомое взаимно-однозначное соответствие.
Задача 2. Пусть А = [–1,1], В = (–1,1). Строим отображение f : A ® B по следующему правилу: выделим в А последовательность –1, 1, 1/2, 1/3, 1/4, . . . , 1/n и положим f(–1)=1/2, f(1)=1/3, f(1/2)=1/4, f(1/3)=1/5, т.е. f(1/n) = 1/(n+2), а все точки, не входящие в эту последовательность отобразим сами в себя, т.е. f(x) = х. Следовательно, открытый и замкнутый интервалы эквивалентны.
Мощность – это то общее, что есть у любых двух эквивалентных множеств. Мощность множества A обозначается m(A) или |A|. Таким образом, m(A) = m(B), если A
Если множество A эквивалентно какому-либо подмножеству множества B, то мощность A не больше мощности B (т.е. m(A)£m(B)). Если при этом множество B не эквивалентно никакому подмножеству множества A, то m(A)
Задача 5. Доказать, что если расстояние между любыми двумя точками множества E на прямой больше единицы, то множество E конечно или счетно.
Решение. Разобьем прямую на счетное множество отрезков точками 0, ±1, ±2, ±3, . . . Каждый отрезок содержит не более одной точки данного множества, следовательно, между точками множества E и некоторым подмножеством построенного множества отрезков существует взаимно однозначное соответствие. Значит, множество E не более чем счетно.
Задача6. Доказать, что множество точек разрыва монотонной функции, заданной на [a, b], не более, чем счетно.
Решение. Каждая точка разрыва монотонной функции f(x) является точкой разрыва первого рода. Действительно, так как функция f(x) монотонна и ограничена на отрезке, то она имеет конечные пределы при x®x±0, где x – произвольная точка разрыва функции f(x).
Назовем скачком функции в точке x разность f(x+0) –f(x–0) этих пределов. Пусть функция f(x) возрастает. Легко проверить, что множество точек разрыва, в которых скачок больше a (где a – произвольное положительное число), конечно, а число этих точек не больше, чем (f(b) – f(a)) /a.
Обозначим через Ek множество точек разрыва со скачком, большим, чем 1/ k. Множество E всех точек разрыва равно объединению всех Ek: E = E1 È E2 È E3 È . . . È Ek È . . .
Так как все Ek конечны, то E не более чем счетно.
Для монотонно убывающей на [a, b] функции доказательство аналогично.
Задача 7. Доказать, что множество всех непрерывных функций на отрезке [a, b] имеет мощность континуума.
Решение. Рассмотрим множество Q всех рациональных точек отрезка [a,b], занумерованных произвольным образом, т.е. Q= =1, r2. >. Поставим в соответствие каждой непрерывной на [a,b] функции f последовательность действительных чисел f(r1), f(r2). Так как непрерывная функция на [a,b] полностью определяется своими значениями в точках множества Q, то тем самым устанавливается взаимно однозначное соответствие между множеством всех непрерывных функций на [a,b] и частью множества всех последовательностей действительных чисел. Значит, в силу результатов задач 11-13 п. 4, мощность множества всех непрерывных функций на [a,b] не больше мощности континуума. С другой стороны, она не может быть меньше мощности континуума, так как все функции, постоянные на [a,b], уже образуют множество мощности континуума. Для завершения доказательcтва остается применить теорему Кантора-Бернштейна (см. п.4).
КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ
1. Найти взаимно однозначное отображение отрезка [0, 1] на отрезок [a, b].
2. Отобразить взаимно однозначно луч [0, +¥) на всю числовую прямую.
3. Построить взаимно однозначное отображение окружности единичного радиуса на отрезок [0, 1].
4. Установить взаимно однозначное соответствие между открытым единичным кругом E=<(x, y) | x 2 +y 2 2 +y 2 £ 1>.
5. Установить взаимно однозначное соответствие между открытым единичным кругом и замкнутым единичным кругом.
6. Установить взаимно однозначное соответствие между окружностью и прямой.
7. Установить взаимно однозначное соответствие между сферой с одной выколотой точкой и плоскостью.
8. Установить взаимно однозначное соответствие между сферой и плоскостью.
9. Установить взаимно однозначное соответствие между множеством всех многочленов с рациональными коэффициентами и множеством всех натуральных чисел.
10. Установить взаимно однозначное соответствие между множеством всех конечных подмножеств натурального ряда чисел и множеством натуральных чисел.
11. Установить взаимно однозначное соответствие между множеством всех последовательностей действительных чисел и множеством всех последовательностей натуральных чисел.
12. Установить взаимно однозначное соответствие между
множеством всех строго возрастающих последовательностей натуральных чисел и множеством всех бесконечных двоичных дробей, которые соответствуют числам интервала (0, 1].
13. Верно ли утверждение: "Если A
D, причем A É B, C É D, то A B
14. Пусть A É C, B É D, C È D
C. Доказать, что A È D
15. Верно ли утверждение: "Если A
B, C É A, C É B, то C A
16. Верно ли утверждение: "Если A
B, A É C, B É C, то A C
17. Какова мощность множества всех рациональных функций с целыми коэффициентами в числителе и знаменателе?
18. Доказать, что множество всех окружностей на плоскости, радиусы и координаты центра которых – рациональные числа, счетно.
19. Какова мощность множества всех многочленов, коэф-фициентами которых служат корни многочленов с целыми коэф-
фициентами (алгебраические числа).
20. Доказать, что множество точек разрыва монотонной функции, заданной на всей числовой прямой, конечно или счетно.
21. Пусть E – какое-либо несчетное множество положительных чисел. Доказать, что найдется такое число t > 0, что множество E Ç(–t, +¥) несчетно.
22. Доказать, что множество всех стационарных последовательностей натуральных чисел счетно. Последовательность называется стационарной, если она состоит из одинаковых элементов.
23. Определить мощности следующих множеств:
а) множество всех треугольников на плоскости, координаты вершин которых выражаются рациональными числами;
б) множество корней многочленов с целыми коэффициентами;
в) множество вещественных чисел от 0 до 1, в десятичном представлении которых 7 стоит на 3-м месте (т.е. числа вида 0.ab7cd. ).
24. На числовой прямой задано неограниченное счетное множество Е. Доказать, что всегда существует вещественное число z, что сдвинув множество Е на z вправо, получим новое множество Е1, которое будет иметь пустое пересечение с Е.
25. Какова мощность множества всех функций, определенных на отрезке [a, b] и разрывных хотя бы в одной точке этого отрезка?
26. Какова мощность множества всех строго возрастающих непрерывных функций, заданных на отрезке [a, b]?
27. Какова мощность множества всех монотонных функций на отрезке [a, b]?
28. Показать, что множество всех перестановок натурального ряда N имеет мощность континуума.
29. Какова мощность множества всех строго возрастающих последовательностей натуральных чисел?
30. Какова мощность множества всех последовательностей натуральных чисел?
Не нашли то, что искали? Воспользуйтесь поиском:
Лучшие изречения: Для студентов недели бывают четные, нечетные и зачетные. 9618 — 
| 7511 — 
или читать все.
91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.
Отключите adBlock!
и обновите страницу (F5)
очень нужно
Рассмотрим бесконечные последовательности из 0,1,2, в которых никакая цифра не встречается два раза подряд. Какая мощность множества таких последовательностей?
задан 27 Янв ’17 16:26
2 ответа
Мощность равна континууму, и это можно доказать разными способами.
Прежде всего, почему мощность не меньше континуума? Возьмём все двоичные последовательности (слово "бесконечные" будем везде подразумевать). "Разбавим" каждую такую последовательность двойками через один символ. Скажем, если было 01110010. то станет 0212121202021202. . Никакие два одинаковых символа не идут подряд.
То, что последовательностей получается не больше континуума, также достаточно очевидно. Даже если разрешить любые действительные числа в качестве членов последовательностей, то получится множество $%mathbb R^<mathbb N>sim(2^<mathbb N>)^<mathbb N>sim2^<mathbb N imesmathbb N>sim2^<mathbb N>simmathbb R$%. А можно для случая символов 0, 1, 2 предложить такое кодирование: 0 заменяем на 01, 1 заменяем на 011, и 2 заменяем на 0111. Тогда всё однозначно раскодируется.
Из того, что мощность не меньше и не больше континуума, следует, что она равна континууму — по теореме Кантора — Бернштейна. Но здесь можно построить и явный вид биекции, что даёт ещё один способ доказательства.
В качестве "образца" континуума рассмотрим множество двоичных последовательностей из 0 и 1. Будем на них смотреть как на закодированные инструкции по выписыванию последовательностей из условия. Если двоичная последовательность начинается с 0, то мы пишем 0. Если с 10, то пишем 1. Если с 11, то пишем 2. Оставшуюся часть двоичной последовательности используем как информацию, какой символ писать очередным. Будем считать, что на 0, 1, 2 у нас введён циклический порядок, то есть за 2 следует 0. У нас написан какой-то символ 0, 1 или 2; какой писать дальше? Если мы в "инструкции" видим 0, то считаем, что нам надо написать "следующий" символ. Если 1, то предыдущий. При этом одинаковые символы не пойдут подряд.
Для примера: если у нас была инструкция в виде 01110010. то ей соответствует 02101212. . Обратно: пусть в условии дана какая-то последовательность — скажем, 2102021012. . Тогда она получается по "инструкции" 11111011100. , то есть построена биекция.
Мощностью конечного множества М называется количество его элементов. Обозначается . Если , то множества А и В называются равномощными.
Если между двумя конечными множествами А и В существует взаимно-однозначное соответствие, то эти множества равномощны. Этот очевидный факт позволяет, во-первых, установить равенство мощности этих множеств, не вычисляя их. Во-вторых, часто можно вычислить мощность множества, установив его однозначное соответствие с множеством, мощность которого известна, либо легко вычисляется.
Теорема 1.1. Если мощность конечного множества А равна , то число всех подмножеств А равно , то есть .
Множество всех подмножеств множества М называется булеаном. Мощность такого множества называется степеньюмножества М и обозначается . Для конечных множеств выполняется: .
Определение. Множества А и В называются равномощными, если между их элементами можно установить взаимно-однозначное соответствие.
Заметим, что для конечных множеств это утверждение легко доказать. Для бесконечных множеств оно определят само понятие равномощности.
Определение. Множество А называется счётным, если оно равномощно множеству натуральных чисел : .
Очень упрощённо можно сказать, что данное бесконечное множество является счётным, если для его элементов можно установить нумерацию с помощью натуральных чисел.
Без доказательства примем ряд важных фактов:
1. Любое бесконечное подмножество множества натуральных чисел является счётным.
2. Множество является счётным.
3. Множество рациональных чисел является счётным (является следствием из предыдущего утверждения).
4. Объединение конечного числа счётных множеств является счётным.
5. Объединение счётного числа конечных множеств является счётным.
6. Объединение счётного числа счётных множеств является счётным.
Все эти утверждения, как можно видеть, позволяют достаточно успешно устанавливать факт, что данное множество является счётным. Однако сейчас будет показано, что не всякое бесконечное множества является счётным; существует множества большей мощности.
Теорема 1.2 (теорема Кантора). Множество всех действительных чисел из отрезка не является счётным.
Допустим, что множество является счётным и существует его нумерация. Поскольку любое действительное число можно представить в виде бесконечной десятичной дроби (периодической или непериодической), то проделаем это с числами данного множества. Расположим их в порядке этой нумерации:
Теперь рассмотрим любую бесконечную десятичную дробь вида , организованную таким образом, что и так далее. Очевидно, что данная дробь не входит в рассматриваемую последовательность, поскольку от первого числа она отличается первой цифрой после запятой, от второго – второй цифрой и так далее. Следовательно, мы получили число из данного интервала, которое не пронумеровано и, таким образом, множество не является счётным. Его мощность называется континуум, а множества такой мощности называются континуальными. Приведённый метод доказательства называется диагональным методом Кантора.
Следствие 1. Множество действительных чисел континуально.
Следствие 2. Множество всех подмножеств счётного множества континуально.
Как показывается в теории множеств (с помощью метода, аналогичного приведённому выше), для множества любой мощности множество всех его подмножеств (булеан) имеет более высокую мощность. Поэтому не существует множества максимальной мощности. Например, множество-универсум , описанное Кантором должно содержать все мыслимые множества, однако оно само содержится в множестве своих подмножеств в качестве элемента (парадокс Кантора). Получается, что множество не является множеством максимальной мощности.