Мощность множества всех последовательностей натуральных чисел

Одной из задач теории множеств является определение числа элементов множества и исследование вопроса о сравнении друг с другом двух множеств по количеству элементов.

Для конечных множеств самой разной природы эта задача легко решается непосредственным подсчетом. Для бесконечных – с помощью взаимно однозначного (биективного) отображения. Рассмотрим примеры построения такого отображения.

Задача 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. Какова мощность множества всех последовательностей натуральных чисел?

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Как то на паре, один преподаватель сказал, когда лекция заканчивалась – это был конец пары: "Что-то тут концом пахнет". 8516 – | 8101 – или читать все.

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. , то есть построена биекция.

Мой вопрос: каких же чисел больше: четных или нечетных — не вызвал большого ажиотажа )))
Отвечаю на него сама.
Начну с теории.
И этот вопрос подведет нас к понятию самой «простой» бесконечности.
Истоки того, о чем сейчас пойдет речь, лежат в теории множеств, но в нее я сейчас углубляться не буду.
Расскажу только, что любое множество состоит из некоторых элементов. Количество элементов может быть конечным или бесконечным. Множество яблок в корзинке, множество квартир в доме, множество книг на полке… — всё это примеры конечных множеств. Если в корзинке 10 яблок, — число элементов множества яблок в корзинке равно десяти.
Как же определяется число элементов в бесконечном множестве?
Обобщенным понятием количества элементов на произвольные множества является понятие мощности.
Т.е. в примере с корзинкой речь идет о мощности множества яблок. И эта мощность равна 10.
Мощность множества на самом деле — это абстракция. Она определяется как то общее, что есть у всех множеств, (количественно) эквивалентных данному.
И вот тут самое главное:

Читайте также:  Мощность всасывания пылесоса томас

Два множества называются эквивалентными, если между ними можно установить взаимнооднозначное соответствие.

Помните пример с овцами?

Первая вышедшая овца — 1
Вторая вышедшая овца — 2
Третья вышедшая овца — 3
Четвертая вышедшая овца — 4
Пятая вышедшая овца — 5
Шестая вышедшая овца — 6

Это и есть пример взаимнооднозначного соответствия между множеством, состоящим из шести овец и множеством чисел: <1, 2, 3, 4, 5, 6>.
*Это нам пригодится чуть ниже, как только мы закончим с теорией.

Мощности часто называются кардинальными числами.

Наименьшей бесконечной мощностью является мощность НАТУРАЛЬНЫХ чисел. Обозначается она алеф-нуль.

Так вот, теперь посмотрим, что мы можем сказать о четных, нечетных и других числах.
Согласно очень красивой теории бесконечных чисел, автором которой является отец-основатель теории множеств Георг Кантор, мощности множеств четных чисел, нечетных чисел, чисел делящихся на три, пять, десять, сто, миллион, и т.д., СОВПАДАЮТ и равны алеф-нуль!
То есть, «количество» всех этих чисел одинаково!
Невероятно?
Это еще не всё.
Может создаться впечатление, что, скажем, целых чисел больше, чем натуральных, потому что целые числа могут быть как положительными, так и отрицательными, а натуральные только положительны! А еще более «очевидным» кажется тот «факт», что ДРОБЕЙ больше, чем натуральных чисел!
НЕТ!

Общее количество всех целых чисел, натуральных чисел и дробей равны одному и тому же бесконечному кардинальному числу алеф-нуль!

Чтобы доказать любое из этих утверждений достаточно установить взаимнооднозначное соответствие между множеством натуральных чисел и конкретным множеством, мощность которого мы хотим найти. Если такое соответствие есть, множества эквивалентны по данному выше определению.

Построим соответствие, предположим, для четных чисел.
Получим (Ч — четные числа; Ц — целые):

Заметим, что каждое число в левом и правом столбцах встречаются один и только один раз. Соответствие взаимнооднозначно.
Это и доказывает ОДИНАКОВОСТЬ количества элементов множества четных и всех натуральных чисел.
Со всеми остальными множествами (кроме дробей) разобраться столь же легко.
С дробями (рациональными числами) разбираться будем потом. Но их количество, как это ни парадоксально, — тоже равно алеф-нуль.

Читайте также:

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Adblock detector