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

[K Y S K A]

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

[Altair]

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

[K Y S K A]

а СТРОГО?? мНЕ БЫ ХОТЕЛАСЬ ХОТЯБЫ ИДЕЯ, КАК ЭТО ЭТО ДОКАЗАТЬ!

[virt]

а книги по матану нет?

идея такая берем точку С и строим сходящуюся к ней последовательность так :
первый элемент произвольная точка из R кроме С(например меньше С). Следующий элемент a[i] := (C + a[i]) div 2;
a[i] станет равным С только на бесконечности => точке С нельзя дать номер.

[Atos]

To: virt А на какой теореме это доказательство основано? То есть почему нельзя сделать так: точке С присвоить первый номер, а нумерацию остальных элементов последовательности сдвинуть на единицу.
Нет, как-то это не так на первом курсе доказывалось.. Массаракш, не могу идею вспомнить! надо поднять сегодня лекции

[Atos]

Вот:http://school.computerra.ru/offline/2003/12/31198/print.html канторова диагональ

Множество действительных чисел счётно Интере-е-сно...

[virt]

To: Atos
на какой теореме не помню ,но док-во похожее на это.

[Lapp]

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

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

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

[Lapp]

2 Virt :

идея такая берем точку С и строим сходящуюся к ней последовательность так :
первый элемент произвольная точка из R кроме С(например меньше С). Следующий элемент a[i] := (C + a[i]) div 2;
a[i] станет равным С только на бесконечности => точке С нельзя дать номер.

- увы, это не доказательство. Это всего лишь говорит о неправильно выбранной последовательности, оставляя бесконечное количество (хм, не счетное, и даже более того..) для дальнейших попыток. Так же вы можете утверждать, что множество натуральных чисел не счетно: если начать нумерацию с числа 2 (и дальше), то число 1 окажется незанумерованным. Но можно же, например, посчитать это пресловутое число С в начале, первым номером, сместив нумерацию на единицу..

[virt]

lapp
да ,не то доказательство привел.

пусть [0,1] счетно x1 x2 x3 ...
берем отрезок [0,1] делим на 3 равные части
x1 <- [0,1] A1 - отрезок (х1 </- A1)
делим A1 на 3 части х2 <- A1 (x2 </- A2)
продолжим процесс An n <- N
1)для всех n <- N (xn </- An)
2)An+1 <- An
3)/An/ = 1/3^n --> 0

пересечение An = {c} ,c <- [0,1].
существует n (c = xn) (все точки занумерованы)
это противоречит пункту 1) c = xn </- An

[Lapp]

2 Virt:
Да, это доказательсво работает.
Я долго пытался понять значки, но все же преуспел в этом , весьма оригинально!
Фактически доказательство не отличается от приведенных Атосом и мной, хотя и делает упор на графическую итерпретацию. Главная отличительная особенность в том, что оно использует ТРОИЧНУЮ систему счисления ;). Десятичная (мое доказательство) привычна всем людям, двоичная (Атос) - программистам, которых тут должно быть достаточно. Троичная вряд ли служит наглядности , но в смысле доказательства ничем не хуже!
Кто предложит семиричную? Или, скажем - дветысячишестиричную - в честь приближающегося Нового года!