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

Лекция 10. Конечные и бесконечные множества

10.1.Конечные и бесконечные множества

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

10.3.Счетность множества рациональных чисел.

10.4.Несчетность множества действительных чисел

10.5.Мощность множества.

Программные положения

Лекция посвящена вопросам сравнения бесконечных множеств. Рассматриваются счетные и несчетные множества, вводится понятие мощности как инструмента различения бесконечных множеств

Методические рекомендации

Обратите внимание на различие в определении счетных и несчетных множеств, понятие мощности

Литература

А.В. Дорофеева «Высшая математика» глава XIV стр.330-356

Р.Курант, Г.Роббинс «Что такое математика» глава II § 4, стр. 104-115

Дополнительно:

А.Я.Хинчин «Восемь лекций по математическому анализу». Лекция 1 «Кнтинуум»

Контрольные вопросы

1. Приведите примеры конечных и бесконечных множеств

2. Дайте определение счетного множества (приведите примеры)

3. Дайте определение несчетно множества (приведите примеры)

4.Покажите, что у конечного множества из n элементов 2ⁿ подмножеств

4. Докажите, что множество рациональных чисел счетно

5. Докажите, что множество действительных чисел несчетно

6. Приведите примеры множеств эквивалентных отрезку [0,1]

Конечные и бесконечные множества

 

Рассматривая различные множества, мы замечаем, что иногда можно, если не фактически, то хотя бы примерно, указать число элементов в данном множестве. Таковы, например, множество всех вершин некоторого многогранника, множество всех простых чисел, не превосходящих данного числа, множество всех молекул воды на Земле и т. д. Каждое из этих множеств содержит конечное, хотя, быть может, и неизвестное нам число элементов. С другой стороны, существуют множества, состоящие из бесконечного числа элементов. Таково, например, множество всех натуральных чисел, множество всех точек на прямой, всех кругов на плоскости, всех многочленов с рациональными коэффициентами и т.д.

Определение 10.1.

Говоря, что множество бесконечно, мы имеем в виду, что из него можно извлечь один элемент, два элемента и т.д., причем после каждого такого шага в этом множестве еще останутся элементы.

 

Два конечных множества мы можем сравнивать по числу элементов и судить, одинаково это число или же в одном из множеств элементов больше, чем в другом. Спрашивается, можно ли подобным же образом сравнивать бесконечные множества? Иначе говоря, имеет ли смысл, например, вопрос о том, чего больше: кругов на плоскости или рациональных точек на прямой, функций, определенных на отрезке [0,1], или прямых в пространстве, и т.д.?

 

Сравнение конечных множеств

Сравнивая конечные множества можно поступать двояко:

1) подсчитать и сравнить число элементов

2) попытаться установить биекцию, т. е. взаимно однозначное соответствие между элементами этих множеств, иначе говоря, такое соответствие, при котором каждому элементу одного множества отвечает один и только один элемент другого,

и наоборот. Ясно, что взаимно однозначное соответствие между двумя конечными множествами можно установить тогда и только тогда, когда число элементов в них одинаково.

Например, сравнивая множество студентов 1 курса и множество стульев в аудитории № 1 можно подсчитать количество студентов и стульев, а можно рассадить студентов в аудитории, тем самым попробовав установить взаимно однозначное соответствие между этими множествами. Если мест хватит всем и не останется ни одного лишнего стула, т. е. если будет установлена биекция между этими двумя множествами, то это и будет означать, что число элементов в них одинаково.

 

Замечание 10.1.

Первый способ (подсчет числа элементов) годится лишь для сравнения конечных множеств, второй (установление взаимно однозначного соответствия) пригоден и для

бесконечных.

 

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

 

 

Определение 10.2.(1)

 

Назовем счетным множеством всякое множество, элементы которого можно биективно сопоставить со всеми натуральными числами. Иначе говоря, счетное множество — это такое множество, элементы которого можно занумеровать в бесконечную последовательность: а₁, а₂, а₃, …

 

Примеры 10.2.

 

1. Множество всех целых чисел. Установим соответствие между всеми целыми и всеми натуральными числами по следующей схеме:

вообще, неотрицательному числу n≥0 сопоставим нечетное число

2n + 1, а отрицательному n < 0 — четное число 2n:

 

 

2. Множество всех четных положительных чисел. Соответствие

очевидно: .

3. Множество 2,4, 8,..., 2ⁿ,... степеней числа 2. Здесь соответствие также очевидно. Каждому числу 2ⁿ сопоставляется число n.

4. Множество рациональных чисел (см. п.10.3)

 

 

Пусть X — счетное множество, т. е. существует взаимно однозначное отображение (биекция) множества натуральных чисел N на множество X. Элемент множества X, соответствующий при этом отображении числу n, обозначим, как и в случае последовательности, х_n и будем называть число n его номером. Поэтому можно сказать,

что множество является счетным, если его элементы можно перенумеровать натуральными числами.

Замечание 10.2.

 

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

 

Теорема 10.2(1).

Любое бесконечное множество содержит бесконечное счетное подмножество.

 

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

Пусть X — бесконечное множество; тогда оно во всяком случае непусто, т. е. в нем существует по крайней мере один элемент, обозначим его через х₁. Поскольку множество X бесконечно, то множество X \ {x₁} также непусто, т. е. содержит по крайней мере один элемент, обозначим его х₂. Продолжая этот процесс, на n-м шаге получим элемент х_n. Поскольку X — бесконечное множество, то множество X \{х₁,x₂,...,х_n} непусто, т. е. содержит по крайней мере один элемент, обозначим его х_n+1 и т. д.

Множество { х₁,x₂,...,х_n...} — искомое счетное подмножество множества X.

 

Теорема 10.2(2).

Любое бесконечное подмножество счетного множества счетно.

 

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

Пусть X — счетное множество: X = { х₁,x₂,...,х_n …}и .

Обозначим через у₁ элемент из У, имеющий наименьший номер в X, через y₂ — элемент множества У, имеющий следующий ближайший номер, и т. д. Поскольку каждый элемент множества Y является некоторым элементом х_n множества X и, следовательно, имеет номер n, то через конечное число шагов (не больше, чем n) он получает некоторый номер m и в множестве У, т. е. будет обозначен у_m, причем, поскольку множество Y бесконечно, этот процесс может быть продолжен неограниченно. Таким образом, все элементы множества Y окажутся перенумерованными, что и означает счетность этого множества. |

 

Возникает естественный вопрос, существуют ли несчетные множества, т. е. бесконечные множества, не являющиеся счетными, а если существуют, то интересно построить пример несчетного множества. Соответствующий пример рассмотрен в п.10.4