Доказать что множество рац чисел счетно
Счетность множества рациональных чисел
Теорема: множество рациональных чисел является счётным.
Необходимо доказать, что между множеством рациональных чисел и множеством натуральных чисел можно установить взаимо-однозначное соответствие. Для этого положительные рациональные числа запишем так:
Таким образом, будет записано каждое положительное число. Например, число 7/31 будет записано в 31-й строке в 7-м столбце. Вообще, дробь m/n будет записана в n-й строке m-м столбце.
Для установления взаимно-однозначного соответствия теперь уже нельзя переходить от столбца к столбцу, потому что в каждом столбце содержится бесконечное множество элементов. Для доказательства этой теоремы будем использовать диагональный метод Кантора. Он заключается в том, что мы подходим к каждому рациональному числу и, следовательно, каждому рациональному числу будет поставлено в соответствие какое-либо натуральное число.
Так, с помощью диагонального метода устанавливаем взаимно-однозначное соответствие между множеством положительных рациональных и множеством натуральных чисел, а это значит, что множество положительных рациональных чисел счетно.
Также можно доказать, что множество отрицательных рациональных чисел счётно. Сложив эти два множества и прибавив к ним конечное множество, состоящее из элемента нуль, мы получим всё множество рациональных чисел.
Теорема.Множество всех действительных чисел несчетно.
Доказательство. Для доказательства достаточно установить, что множество действительных чисел интервала 
образует несчетное множество. Допустим противное, что интервал есть счетное множество, т. е. все его точки можно перенумеровать:
Но это предположение противоречиво. В самом деле, построим вещественное число 
, где цифры 
подобраны так, чтобы 
и 
. Ясно, что 
, однако 
не совпадает ни с одним из чисел 
, так как иначе должно было бы быть 
, что не имеет места.
Доказать что множество рац чисел счетно
2. Счетность множества рациональных чисел и несчетность континуума
Одно из первых открытий Кантора в области анализа бесконечного заключалось в том, что множество рациональных чисел (содержащее в качестве правильного подмножества бесконечное множество натуральных чисел и потому само бесконечное) эквивалентно множеству натуральных чисел. На первый взгляд кажется странным, что всюду плотное множество рациональных чисел не более богато элементами, чем множество натуральных чисел, элементы которого «рассеяны» редко и стоят на значительном расстоянии один от другого. И в самом деле, с сохранением порядка возрастания нельзя расположить положительные рациональные числа так, как это можно сделать с натуральными: самое маленькое число а будет первым, следующее за ним по величине b вторым и т. д.; дело в том, что рациональные числа расположены всюду плотно, и потому ни для одного из них нельзя указать «следующего по величине». Но Кантор заметил, что если отказаться от требования «располагать по величине», то тогда оказывается возможным расставить все рациональные числа в ряд r1, r2, r3, r4. подобный ряду натуральных чисел. Такое расположение предметов некоторого множества в виде последовательности часто называют пересчетом («нумерацией») этого множества. Множества, для которых пересчет может быть выполнен, называются счетными или исчислимыми. Указывая один из способов пересчета множества рациональных чисел и устанавливая, таким образом, его счетность, Кантор тем самым показал, что это множество эквивалентно множеству натуральных чисел, так как
схема создает взаимно однозначное соответствие между двумя множествами. Мы опишем сейчас один из возможных способов пересчета множества рациональных чисел.
Рис. 19. Пересчет рациональных чисел
Если мы выбросим теперь все дроби, у которых числитель и знаменатель имеют отличные от 1 общие делители, то останется последовательность, в которой каждое рациональное число встретится в точности один раз:
Так устанавливается, что множество всех рациональных чисел является счетным. Принимая во внимание, что рациональные числа взаимно однозначно связаны с рациональными точками числовой прямой, можно также сказать, что множество рациональных точек на числовой прямой счетно.
Упражнения. 1) Покажите, что множество всех целых, положительных и отрицательных чисел счетно. Покажите, что множество всех рациональных, положительных и отрицательных чисел счетно.
2) Покажите, что если S и Т- счетные множества, то множество S + Т (см. стр. 138) также счетно. То же покажите для суммы трех, четырех и, вообще, n множеств; покажите, наконец, что множество, составленное посредством сложения счетного множества счетных множеств, также счетно.
Однако проведем это рассуждение фактически. Допустим, что все действительные числа, представленные в виде бесконечных десятичных дробей, расположены в виде последовательности, или списка:
где буквы Ni обозначают целую часть, а буквы а, b, с. представляют собой десятичные знаки, стоящие вправо от запятой. Мы допускаем, что эта последовательность дробей охватывает все действительные числа. Существенной частью доказательства является построение с помощью «диагональной процедуры» такого нового числа, относительно которого можно показать, что оно не входит в наш список.
Рис. 20. Взаимно однозначное соответствие между точками согнутого интервала и точками прямой линии
Это новое число z наверняка не входит в наш список; действительно, оно не равно первому числу, стоящему в списке, так как от него отличается первой цифрой после запятой, оно не равно второму числу, так как от него отличается второй цифрой после запятой, и вообще отлично от n-го числа по списку, так как отличается от него n-й цифрой после запятой. Итак, в нашем списке, составленном будто бы из всех действительных чисел, нет числа z. Значит, множество всех действительных чисел несчетно.
Читателю может прийти в голову мысль, что несчетность континуума обусловливается неограниченной протяженностью прямой линии и что конечный отрезок прямой будет содержать лишь счетное множество точек. Чтобы убедиться в ложности такого предположения, достаточно установить, что весь числовой континуум в целом эквивалентен некоторому конечному интервалу, скажем, единичному интервалу от 0 до 1. Получить необходимое для этой цели взаимно однозначное соответствие можно, например, сгибая интервал в точках 
и 
и затем проектируя так, как показано на рис. 20. Отсюда видно, что даже конечный интервал (и, конечно, отрезок) содержит несчетное множество точек.
Упражнение. Показать, что любой отрезок [А, В] числовой прямой эквивалентен любому другому отрезку [С, D] (рис. 21).
Рис. 21. Взаимно однозначное соответствие между точками двух отрезков различной длины
Стоит привести еще другое доказательство несчетности континуума, носящее, пожалуй, более интуитивный характер. Достаточно (принимая во внимание последнее доказанное предложение) сосредоточить внимание на точках единичного отрезка от 0 до 1. Доказательство, впрочем, как и раньше, будет «косвенное». Предположим, что множество всех точек названного отрезка может быть расположено в виде последовательности
Мощность множества, счетные множества и их свойства. Счетность множества рациональных чисел. Несчетность множества действительных чисел
Под множеством понимают объединение в одно целое объектов, связанных между собой неким свойством. Если из элементов двух множеств можно составить пары таким образом, чтобы каждому элементу первого множества соответствовал определенный элемент второго множества, а каждому элементу второго множества соответствовал один и только один элемент первого множества, то говорят, что между такими двумя множествами установлено взаимно однозначное соответствие.
Чтобы установить взаимно однозначное соответствие, необязательно пересчитывать элементы множеств. Например, мы знаем, что американские штаты находятся во взаимно однозначном соответствии с их столицами, хотя можем оставаться в неведении относительно общего их числа. Мы могли бы утверждать: «Столиц штатов ровно столько, сколько штатов».
Конечное множество состоит из конечного числа элементов, например, множество страниц в книге, множество студентов в группе и т.д.
Бесконечное множество состоит из бесконечного числа элементов, т.е. это множество, которое не является ни конечным, ни пустым. Например: множество действительных чисел, множество точек плоскости, множество атомов во Вселенной и т.д.
Мощностью конечного множества называется количество его элементов. Мощность множества A обозначается m (A).
В теории множеств, счётное мно́жество есть бесконечное множество, элементы которого возможно пронумеровать натуральными числами. Более формально: множество <\displaystyle X> 
является счётным, если существует биекция <\displaystyle X\leftrightarrow \mathbb , где <\displaystyle <\mathbb обозначает множество всех натуральных чисел. Другими словами, счётное множество — это множество, равномощное множеству натуральных чисел.
1. Любое подмножество счётного множества не более чем счётно (т.е. конечно или счётно). [1]
2. Объединение конечного или счётного числа счётных множеств счётно. [1]
3. Прямое произведение конечного числа счётных множеств счётно.
4. Множество всех конечных подмножеств счётного множества счётно.
5. Множество всех подмножеств счётного множества континуально и, в частности, не является счётным.
2.2 Свойства счётных множеств
Лемма 1. Объединение двух счётных множеств счётно.
Лемма 4. Множество рациональных чисел Q счетно.
Доказательство. Нам будет удобнее доказать отдельно, что множество неотрицательных ра- циональных чисел счётно и что множество отрицательных рациональных чисел счётно. Тогда счётность множества всех рациональных чисел сразу вытекает из леммы 1. Проведем рассуждение для неотрицательных рациональных чисел. Для отрицательных чи- сел рассуждение аналогично (а можно заметить, что смена знака даёт биекцию между отрица- тельными и положительными числами, а к положительным рациональным числам применить лемму 2). 5 Неотрицательное рациональное число задается парой чисел — числителем и знаменателем. Числитель может быть произвольным натуральным числом, а знаменатель произвольным положительным натуральным числом.
Выпишем все такие числа в виде таблицы, бесконечной вниз и вправо:
Теорема 1. Объединение конечного или счётного числа конечных или счётных множеств конечно или счётно.
Теорема 2. Декартово произведение двух счётных множеств A × B cчётно.
Доказательство. В самом деле, по определению декартово произведение есть множество всех упорядоченных пар вида ha, bi, в которых a ∈ A и b ∈ B. Разделим пары на группы, объединив пары с одинаковой первой компонентой (каждая группа имеет вид ×B для какого-то a ∈ A). Тогда каждая группа счётна, поскольку находится во взаимно однозначном соответствии с B (пара определяется своим вторым элементом), и групп столько же, сколько элементов в A, то есть счётное число.
Теорема 1. Множество всех рациональных чисел счетно.
Доказательство. Рассмотрим сначала положительные рациональные числа 
. Назовем натуральное число 
высотой рационального числа 
. Пусть 
— множество всех рациональных чисел с высотой, равной 
. Множества 
состоят из конечного числа элементов (рациональных чисел), например
.
Легко видеть, что 
,
Перенумеруем числа, записанные в фигурных скобках слева направо, выпуская, впрочем, на каждом этапе нумерации те, которые были уже занумерованы на более раннем этапе. В результате получим последовательность
.
Так как рациональных положительных чисел бесконечно много, то мы используем все натуральные числа. Значит, 
счетно. Далее, очевидно, что 
счетно. Поэтому все множество рациональных чисел 
также счетно.
Теорема 2.Множество всех действительных чисел несчетно.
Доказательство. Для доказательства достаточно установить, что множество действительных чисел интервала 
образует несчетное множество. Допустим противное, что интервал есть счетное множество, т. е. все его точки можно перенумеровать:
Но это предположение противоречиво. В самом деле, построим вещественное число 
, где цифры 
подобраны так, чтобы 
и 
. Ясно, что 
, однако 
не совпадает ни с одним из чисел 
, так как иначе должно было бы быть 
, что не имеет места.
Счетные множества
Множество называется счетным, если оно равномощно множеству 
натуральных чисел, то есть если его можно представить в виде 
(здесь 
— элемент, соответствующий числу 
; соответствие взаимно однозначно, так что все различны).
Например, множество целых чисел 
счетно, так как целые числа можно расположить в последовательность 
, 
, 
, 
, 
, 
, 
, 
(а) Подмножество счетного множества конечно или счетно.
(в) Объединение конечного или счетного числа конечных или счетных множеств конечно или счетно.
(а) Пусть 
— подмножество счетного множества 
. Выбросим из последовательности 
те члены, которые не принадлежат (сохраняя порядок оставшихся). Тогда оставшиеся члены образуют либо конечную последовательность (и тогда конечно), либо бесконечную (и тогда счетно).
(в) Пусть имеется счетное число счетных множеств 
Расположив элементы каждого из них слева направо в последовательность ( 
) и поместив эти последовательности друг под другом, получим таблицу
Замечание. В доказательстве утверждения (б) теоремы 2 есть тонкий момент: на каждом шаге мы должны выбрать один из оставшихся элементов множества 
; такие элементы есть, но у нас нет никакого правила, позволяющего такой выбор описать. При более формальном построении теории множеств тут нужно сослаться на специальную аксиому, называемую аксиомой выбора. Законность этой аксиомы вызывала большие споры в начале 20-го века, но постепенно к ней привыкли, и эти споры сейчас почти не воспринимаются. В середине века великий логик Курт Гедель доказал, что аксиому выбора нельзя опровергнуть, пользуясь остальными аксиомами теории множеств, а в 1960-е годы американский математик Пол Дж.Коэн доказал, что ее нельзя и вывести из остальных аксиом. (Конечно, понимание этих утверждений требует подробного изложения теории множеств как аксиоматической теории.)
30. Такой же тонкий момент (хотя и менее очевидный) есть и в доказательстве утверждения (в). Можете ли вы догадаться, где он? (Ответ: мы знаем, что множества 
счетны, то есть что существует взаимно однозначное соответствие между 
и . Но нужно выбрать и фиксировать эти соответствия, прежде чем удастся построить соответствие между объединением всех и .)
Еще несколько примеров счетных множеств:
31. Докажите, что любое семейство непересекающихся интервалов на прямой конечно или счетно. (Указание: в каждом интервале найдется рациональная точка.)
33. Докажите, что множество точек строгого локального максимума любой функции действительного аргумента конечно или счетно.
Докажите, что множество точек разрыва неубывающей функции Действительного аргумента конечно или счетно.