СЧетные МнОжЕсТвА Опции

[K Y S K A]

Помогите, мне пожалуйста, как доказать что R не счетно!!!!

[Lapp]

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

Рассмотрим все действительные числа на интервале (0,1), т.е. все числа, начинающиеся с "0.". Предположим, что нам удалось их занумеровать. Теперь сконструируем новое число по следующему правилу. Первой цифрой (после запятой) возьмем любую, но не равную первой цифре первого числа, второй - любую, не равную второй цифре второго числа, третьей цифрой - любую цифру, не равную третьей цифре третьего - и т.д. То есть проходим по всей нашей занумерованной последовательности и на n-ном шагу берем n-ную цифру так, чтобы она была не равна n-ной цифре n-ного числа из нашей предположенной нумерации. Сконструированное таким образом число будет отличаться от каждого числа, имеющегося в нашей последовательности. Например, от 100-го числа оно заведомо (по построению) отличается в 100-ом знаке. Таким образом, оно не входит в нашу нумерацию, и следовательно нумерация не полная, что противоречит предположению. Противоречие и доказывает несостоятельность утверждения о возможности пересчитать действительные числа на интервале (0,1). Вывод о ВСЕМ множестве действительных чисел напрашивается сам собой..

Если проиллюстрировать это док-во расположением десятичной записи чисел в столбик сверху вниз, то процесс представит собой прохождение по диагонали из левого верхнего угла направо-вниз, беря каждый раз другую не "диагональную" цифру. Поэтому и называется это Канторовой диагональю (про имя не уточняю, почему ). В упомянутой статье используется двоичная запись, что немного отвлекает. Правда, тут все же следует оговориться, что между действительными числами и их десятичными записями достигнуто однозначное соответствие (это в равной степени касается и двоичной записи). То есть, говоря точнее, это док-во утверждает несчетность множества цифровых последовательностей.
Уфф..