В отличие от окружающего нас мира, в котором всё конечно, в математике мы часто сталкиваемся с бесконечными объектами. Например, бесконечны множества натуральных, целых, рациональных, действительных и других чисел. В этой статье мы рассмотрим свойства различных бесконечных множеств и убедимся что бесконечность не самая простая штука, как кажется на самом деле.
Какие множества счетные, а какие нет?
Счетным называют бесконечное множество, между элементами которого и множества натуральных чисел можно построить взаимно однозначное соответствие, то есть биекцию
Если более простым языком, то возьмём какое-нибудь бесконечное множество A. Если мы каждому элементу множества A можем поставить в соответствие натуральное число, так что каждому натуральному числу будет в соответствие ровно один поставлен элемент множества A и каждому элементу множества A поставлен ровно одно натуральное число A, то A - счетное множество.
Несчетным называют бесконечное множество, между элементами которого и множества натуральных чисел нельзя построить биекцию
Может показаться, что раз элементов во множестве бесконечно много и натуральных чисел бесконечно много, то все бесконечные множества являются счётными, ведь как бесконечность может быть не равна сама себе. Но оказывается, что несчетные множества действительно существуют. Это если чуть-чуть забегать вперед.
Примеры счетных множеств
Очевидно, что натуральные числа - счетное множество. Просто каждому натуральному числу ставим в соответствие само себя и получаем биекцию.
Натуральные четные числа
Давайте рассмотрим множество натуральных четных чисел. Кажется, что четных чисел должно быть в два раза меньше чем натуральных, то есть вот оно - несчетное множество. Но нет, мы можем легко построить биекцию: четному числу 2k из множества четных в соответствие ставим число k из натуральных. Так числу 2 из четных мы ставим в соответствие число 1 из натуральных; число 34 из четных ставим в соответствие число 17 из натуральных; числу 100 из четных ставим в соответствие число 50 из натуральных. Нетрудно убедиться, что мы действительно получили биекцию. Значит множество натуральных четных чисел - счетное множество.
Целые числа
А что с целыми числами? Тут кажется, что ну вот их в два раза больше чем натуральных, значит целые числа - несчетное множество! Но тут опять можно построить биекцию: каждому четному числу n из множества натуральных ставим в соответствие n/2 из множества целых; каждому нечетному числу n из множества натуральных ставим в соответствие -(n-1)/2. Тут опять же нетрудно убедиться в том что мы получили биекцию. Значит множество целых чисел - счетное множество.
Простые числа
А как же без всеми любимыми простых чисел? Их счетность доказать достаточно легко. Просто ставим в соответствие каждому простому числу его порядковый номер среди простых, то есть 2 из простых в соответствие ставим 1 из натуральных; 3 из простых ставим в соответствие 2 из натуральных; 5 из простых ставим в соответствие 3 из натуральных и так далее. Остается доказать, что простых чисел - бесконечное количество. Воспользуемся доказательством Евклида: Пусть простых конечное число. Тогда давайте перемножим все эти простые и к этому произведению прибавим 1. Тогда получившееся число даёт остаток 1 при делении на все простые числа, что противоречит Основной Теореме Арифметики. Противоречие. Значит простых бесконечное количество. Биекцию между простыми и натуральными числа построили, значит простые числа - счетное множество.
Операции с счетными множествами
Объединение счетного и конечного
Возьмём счетное множество A и конечное множество B (то есть множество в котором конечное число элементов). Интересно, каким будет множество A∪B - счетным или несчетным? Оказывается, что результат объединения конечного и счетного множества - счетное множество.
Докажем этот факт. Так как A - счетное множество, то мы его элементы можем пронумеровать, начиная с 1. Пусть в множестве B находится k элементов. Пронумеруем элементы во множестве B от 1 до k.
Когда мы объединим эти множества нумерацию во множестве A сдвинем на k, то есть элемент из A с номером 1 в конечном множестве будет иметь номер 1+k. А во множестве B оставим нумерацию от 1 до k.
Мы пронумеровали все элементы итогового множества, то есть построили биекцию с натуральными числами.
Объединение счетного и счетного. Конечное количество объединений счетных множеств.
Пусть у нас есть счетные множества A и B. Так как они счетные, то элементы в этом множестве мы можем пронумеровать.
Посмотрим на объединение этих двух множеств. Посмотрим на элемент a∈A, тогда ему соответствует какое-то натуральное число k, так как A-счетное множество. Давайте тогда в итоговом множестве этому элементу дадим номер 2k. Посмотрим на элемент b∈B, тогда ему соответствует какое-то натуральное число k, так как B-счетное множество. Давайте тогда в итоговом множестве этому элементу дадим номер 2k-1. Тогда четные номера имеют только элементы множества A; нечетные номера - элементы множества B. При этом мы использовали все натуральные числа.
Если мы объединяем какое-то конечное число счетных множеств, например три: A, B и C. Так как объединение - ассоциативная операция (результат не зависит от расстановки скобок. Например: 3*(4*5) = (3*4)*5, то есть умножение - ассоциативная операция), то мы можем сначала объединить множества A и B, получить множество A∪B. Оно по рассуждением выше счетное. А теперь объединяем счетные множества A∪B и C. По рассуждениям выше опять же получим счетное множество.
Если мы хотим доказать для n объединений, то можем воспользоваться индукцией. База для n=1 у нас есть. Пусть, если мы объединили n-1 счетное множество, то получим счетное множество. Тогда если мы объединим результат объединения n-1 счетного множества, что по предположению индукции является счетным множеством и ещё какое-то новое счетное множество, то после объединения двух счетных множеств по рассуждениям выше я также получу счетное множество.
Счетное количество объединений счетных множеств.
Так как у нас счетное количество множеств, то каждому из них мы можем сопоставить натуральное число. Давайте так и называть множества "первое", "второе", "третье" и так далее. Так же так как эти множества счетные, то и их элементы можно пронумеровать. Давайте тогда каждому элементу сопоставим пару чисел (x,y), где x - номер множества, а y - номер этого элемента в множестве с номером x.
Теперь давайте запишем таблицу из этих значений: на первой строке выпишем все первые элементы из каждого множества; на второй строке - все вторые элементы из каждого множества и так далее:
(1;1);(2;1);(3;1);(4;1)...
(1;2);(2;2);(3;2);(4;2)...
(1;3);(2;3);(3;3);(4;3)...
(1:4);(2;4);(3;4);(4;4)...
...
Теперь будем идти по диагоналям и нумеровать их в порядке нашего прохождения. То есть (1;1) - 1; (2;1) - 2; (1;2) - 3; (1;3) - 4; (2;2) - 5; (3;1) - 6... . Так мы пронумеруем абсолютно все элементы получившегося объединения, то есть построим биекцию с множеством натуральных чисел. Значит получившееся множество - счетное.
Ещё пару примеров счетных множеств
Рациональные числа
По определению любое рациональное число имеет вид m/n, где m - целое, а n - натуральное. Тогда любое рационально число вида m/n мы можем представить в виде (m;n). Про такую шифровку мы уже знаем, что таких пар счетное количество. Значит рациональные числа также образуют счетное множество.
Примеры несчетных множеств
Диагональный аргумент Кантора
Это самый классический пример несчетного множества и поэтому мы с него и начнём.
Давайте посмотрим на все бесконечные последовательности из 0 и 1. Предположим, что все они образуют счетное множество, то есть мы их можем как-то занумеровать. Например:
- 001001010...
- 010001010...
- 110010101...
...
А теперь построим такую последовательность, что она от числа в n строке будет отличатся n символом, то есть на первое место мы ставим 1, чтобы первая цифра нашей последовательности отличалась от первой цифры в первой строке; вместо второй цифры мы пишем 0, чтобы вторая цифра этой последовательности отличалась от второй цифры второй последовательности; тогда третьей должна быть цифра 1 и так далее. То есть мы идем по диагонали, поэтому аргумент Кантора и называется диагональным
Получившаяся последовательность будет отличаться от любой занумерованной последовательности, значит мы получили последовательность которую мы не пронумеровали. Противоречие, значит такое множество является несчетным.
Благодаря диагональному аргументу Кантора, мы можем сделать парочку выводов, о других множествах:
- На отрезке [0;1] точек больше, чем натуральных чисел. Это следует из того, что пусть каждый элемент этого несчетного множества представляет собой двоичную часть числа после запятой. А целая часть у всех чисел будет 0. То есть, например последовательности 1110010000...(дальше только 0) мы в соответствии поставим число 0,111001, что в десятичном виде равно 0,78125. Таким образом мы получим все числа на отрезке от [0;1], то есть мы построили биекцию из множества всех бесконечных последовательностей из нулей и единиц во множество точек на отрезке [0;1], значит их одинаковое количество, значит и точек на этом отрезке несчетное число, то есть больше чем натуральных чисел.
- Количество подмножеств из натуральных чисел больше чем натуральных чисел. Здесь мы будем строить следующую биекцию: Если на номере n в последовательности стоит "1", то в это подмножество мы "возьмем" число n. Например последовательность 111001000...(дальше только 0) будет соответствовать подмножеству в которое мы возьмем только 1,2,3 и 6. Опять мы построили взаимно однозначное соответствие от множества бесконечных последовательностей из 0 и 1 во множество всех подмножеств из натуральных чисел, значит подмножества множества натуральных чисел образуют несчетное подмножество. Это утверждение называется Теоремой Кантора.
Континуум
Континуум это количество элементов во множестве (мощность множества), которое состоит из бесконечных последовательностей 0 и 1.
Одна из нерешенных задач математики: есть ли такое несчетное множество мощность которого меньше чем континуум. Это утверждение называется континуум гипотезой. Континуум-гипотеза стала первой из 23 проблем, о которых Гильберт доложил на Международном конгрессе математиков в 1900 году. Поэтому континуум-гипотеза известна также как первая проблема Гильберта
Доказано, что проблема неразрешима в стандартной аксиоматике теории множеств, то есть ZFC(аксиоматике Система Цермело - Френкеля c аксиомой выбора)
Большое спасибо за прочтение статьи :0! Получилось немного сухо, но я старался все разъяснить и пояснить как можно понятней, поэтому если будут какие-то вопросы, то комментарии открыты и я с радостью поясню, что было непонятно ;D
Больше интересного контента каждый день в телеграм канале Сложно-простая математика.
Подписывайтесь, не забывайте ставить лайки и писать комментарии. Надеюсь, что мы не прощаемся :-3!
