Счетность и несчетность множеств. Равномощность множеств.
Литература: Сборник задач по математике. Часть 1. Под ред А. В. Ефимова, Б. П. Демидовича.
Множество $X$ называется счетным, если может быть установлено взаимно однозначное соответствие между элементами этого множества и элементами множества $N$ всех натуральных чисел (то есть элементы множества $X$ можно пронумеровать 1, 2, . ).
Примеры.
Доказать, что следующие множества счетны:
Решение.
Установим взаимно однозначное соответствие между элементами этого множества и натуральными числами, например, упорядочив множество $\
$$2, 4, 6, 8, . $$ а затем каждому элементу множества поставив в соответствие его порядковый номер в этой последовательности $$1, 2, 3, 4, . .$$ Таким образом заданное множество является счетным.
Что и требовалось доказать.
Решение.
Множество $\
$$2^1, 2^2, 2^3, 2^4, . $$ далее каждому элементу множества поставив в соответствие его порядковый номер в этой последовательности. Таким образом, установлено взаимно однозначное соответствие между заданнім множеством и множеством натуральніх чисел. Следовательно, множество $$\
Что и требовалось доказать.
1.68. Пусть $X_1, X_2, X_3, . -$ счетные множества. Доказать, что их объеденение $\bigcup\limits_
Решение.
Пусть $X_n=\, x_, . x_. \>.$ Тогда элементы множества $\bigcup\limits_
Занумеруем элементы этой таблицы следующим образом: в качестве первого элемента берем элемент $x_,$ следующие два элемента — элементы стоящие на диагонали $x_$ и $x_,$ затем считаем три элемента стоящие на следующей диагонали $x_,\,\, x_$ и $x_$ и так далее. Таким образом, каждому элементу множества $\bigcup\limits_
Что и требовалось доказать.
1.69.Используя результат задачи 1.68 доказать, что множество всех рациональных чисел $Q=\
Решение.
Множество рациональных чисел можно представить как объединение счетных множеств $X_n=\\, | k\in N \>=\left\,\frac, \frac, \cdots\right\>.$
Каждое множество $X_n$ счетное, поскольку каждому элементу можно поставить в соответствие натуральное число, стоящее в знаменателе. Тогда множество $$Q=\
Что и требовалось доказать.
Множества $A$ и $B$ называются равномощными, если может быть установлено взаимно однозначное соответствие между элементами множества $A$ и элементами множества $B.$ (то есть каждому элементу множества $A$ можно поставить в соответствие один и только один элемент множеста $B,$ а каждому элементу множества $B$ можно поставить в соответствие один и только один элемент множеста $A.$ )
Примеры:
1. Докажите, что отрезки $[0, 1]$ и $[0, 2]$ равномощны.
Доказательство.
Каждому элементу $x\in [0, 1]$ поставим в соответствие число $2x.$ Очевидно $2x\in [0, 2].$ Аналонгично каждому элементу $y\in[0, 2]$ соответствует, и притом единственное, число $\frac\in\,[0, 1].$
Что и требовалось доказать.
2. Докажите, что интервалы $(a, b)$ и $(c, d)$ равномощны.
Доказательство.
Проведем доказательство в несколько этапов:
1) Заметим, что отображение $x\rightarrow x-a$ является взаимно однозначным соответствием между интервалами $(a, \, b)$ и $(0,\, b-a).$
2) Отображение $x\rightarrow\frac$ взаимно однозначно отображает интервал $(0, b-a)$ на $(0, \, d-c).$
3) Отображение $x\rightarrow x+c$ взаимно однозначно отображает интервал $(0, d-c)$ на $(c, d).$
Композиция приведенных отображений $x\rightarrow\frac+c$ является взаимно однозначным отображением между интервалами $(a,\, b)$ и $(c,\, d).$ Следовательно интервалы $(a,\, b)$ и $(c,\, d)$ равномощны.
Что и требовалось доказать.
Домашнее задание.
Доказать, что следующие множества счетны:
1.67. Доказать, что если множество $X$ счетно и $A\subset X$ его бесконечное подмонжество, то множество $A$ так же счето используя этот результат доказать, что множество $$n\in Z | n=k^2-k+1, k\in N$$ счетно.
1.70. Используя результат задачи 1.68, доказать, что множество всех точек плскости с рациональными координатами счетно.
1. Докажите, что полуинтервал $[0,\, 1)$ равномощен полуинтервалу $(0,\, 1].$
2. Докажите, что интервал $(0, 1)$ и луч $(0, \, +\infty)$ равномощны.
Высшая математика. Практика.
- Матрицы, определители и системы линейных уравнений.
- Векторная алгебра
- Алгебраические линии первого порядка на плоскости и в пространстве.
- Алгебраические линии второго порядка на плоскости и в пространстве.
- Некоторые понятия математической логики теории множеств.
- Комплексные числа
- Предел функции.
- Дифференцируемость функции, ее дифференциал и производная.
- Производные и дифференциалы высших порядков. Формула Тейлора.
- Графики функций и кривые
- Неопределенный интеграл.
- Определенный интеграл и его применение.
- Числовые ряды.
- Дифференциальное исчисление функций нескольких переменных.
- Экстремумы функций нескольких переменных.
- Двойные интегралы
- Дифференциальные уравнения
Таблицы
- Таблица производных
- Таблица производных сложных функций
- Таблица производных высших порядков
- Таблица интегралов
- Формулы Тейлора
- Греческий алфавит
- Таблица оригиналов и изображений.
- Сравнение функций O(f) и o(f).
- Тригонометрическая таблица
Книги
Счетность множества рациональных чисел
Теорема: множество рациональных чисел является счётным.
Необходимо доказать, что между множеством рациональных чисел и множеством натуральных чисел можно установить взаимо-однозначное соответствие. Для этого положительные рациональные числа запишем так:
1 строка: 1 2 3 4 5 6 7.
2 строка: ½ 2/2 3/2 4/2 5/2 6/2 7/2.
3 строка: 1/3 2/3 3/3 4/3.
Таким образом, будет записано каждое положительное число. Например, число 7/31 будет записано в 31-й строке в 7-м столбце. Вообще, дробь m/n будет записана в n-й строке m-м столбце.
Для установления взаимно-однозначного соответствия теперь уже нельзя переходить от столбца к столбцу, потому что в каждом столбце содержится бесконечное множество элементов. Для доказательства этой теоремы будем использовать диагональный метод Кантора. Он заключается в том, что мы подходим к каждому рациональному числу и, следовательно, каждому рациональному числу будет поставлено в соответствие какое-либо натуральное число.
Так, с помощью диагонального метода устанавливаем взаимно-однозначное соответствие между множеством положительных рациональных и множеством натуральных чисел, а это значит, что множество положительных рациональных чисел счетно.
Также можно доказать, что множество отрицательных рациональных чисел счётно. Сложив эти два множества и прибавив к ним конечное множество, состоящее из элемента нуль, мы получим всё множество рациональных чисел.
Теорема. Множество всех действительных чисел несчетно.
Доказательство. Для доказательства достаточно установить, что множество действительных чисел интервала образует несчетное множество. Допустим противное, что интервал есть счетное множество, т. е. все его точки можно перенумеровать:
Но это предположение противоречиво. В самом деле, построим вещественное число , где цифры подобраны так, чтобы и . Ясно, что , однако не совпадает ни с одним из чисел , так как иначе должно было бы быть , что не имеет места.
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
Счетность множеств
Самый известный способ доказательства несчетности множества действительных чисел — канторов диагональный процесс. Если мы применим аналогичную процедуру для множества рациональных чисел(каждое число мы можем представить в виде бесконечного : 0.1 = 0.1000000. ) то, соответственно,получим результат, что оно также несчетно, хотя мы знаем, что это утверждение неверно и множество рациональных чисел можно посчитать. Подозреваю, что ошибка в том, что нельзя применять канторов диагональный метоl для рациональных чисел, но почему?
Отслеживать
задан 2 мая 2018 в 13:31
Vlad Kvochin Vlad Kvochin
514 1 1 золотой знак 5 5 серебряных знаков 15 15 бронзовых знаков
1 ответ 1
Сортировка: Сброс на вариант по умолчанию
Потому что все рациональные числа — периодические дроби. А вы получите в результате непериодическую дробь, т.е. ни с одним из рациональных чисел у вас не будет совпадать иррациональное (не рациональное!) число. Что, увы, доказывает только существование иррациональных чисел, и ничего более.
А доказать счетность рациональных чисел очень просто — расположить все первые в первом ряду, вторые (n/2) во втором и так далее, а потом просто пройтись по ним эдакой лесенкой.
И вообще — вы же должны знать, как справиться администратору гостиницы с бесконечным числом номеров, из которых все заполнены, когда прибывает бесконечное количество бесконечных групп туристов? 🙂
дискретная-математика — Дискретная математика
Докажите, что множество конечных подмножеств рациональных чисел счётно.
задан 7 Ноя ’22 0:34
Это тривиальное упражнение. Q счётно, и его можно заменить на N или на NU. А конечные подмножества NU кодируются целыми неотрицательными числами при помощи двоичной системы по принципу -> 2^a+2^b+. +2^c.
(7 Ноя ’22 1:39) falcao
@falcao: Добрый день. А почему это биекция? То есть множество всех чисел вида 2^a+2^b+. +2^c счетно — это понятно, а вот насчет биекции, можете пояснить? Спасибо за ответ.
(7 Ноя ’22 10:46) Cat2021
@falcao: Можно, по-Вашему, эту задачу еще и так решить: множество всех конечных непустых подмножеств Q равномощно множеству всех конечных возрастающих последовательностей натуральных чисел, т.к. Q равномощно N, множество всех конечных возрастающих последовательностей натуральных чисел, как известно, счетно?
(7 Ноя ’22 10:50) Cat2021
@Cat2021: любое число n>=0 имеет однозначное представление в двоичной системе. Поэтому ясно, что будет биекция. Другим способом решать тоже можно (через счётное объединение), но здесь достаточно редкий случай, когда имеется «естественное» кодирование, и этим уместно воспользоваться.