Докажите что канторово множество имеет мощность континуума

Множества мощности континуума

Существуют бесконечные множества, элементы которых нельзя перенумеровать. Такие множества называются несчетными.

Теорема Кантора. Множество всех точек отрезка [0, 1] несчетно.

Множество, эквивалентное множеству всех точек отрезка [0, 1] называется множеством мощности континуума.

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

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

Из рис. 1.8 следует, что множество точек параболы y = x 2 эквивалентно множеству точек прямой –¥

Источник

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки

Правила форума

В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе «Помогите решить/разобраться (М)».

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Как доказать, что множество Кантора имеет мощность континуум

Последний раз редактировалось PAV 29.05.2012, 10:11, всего редактировалось 1 раз.

Заслуженный участник

Последний раз редактировалось alcoholist 15.02.2012, 22:43, всего редактировалось 1 раз.

множество последовательностей 0 и 1

постройте биекцию с единичным отрезком

Заслуженный участник

Заслуженный участник

Заслуженный участник

Последний раз редактировалось Vladimir Gorlin 15.02.2012, 23:02, всего редактировалось 1 раз.

Да, я читал доказательство с троичной системой, но там не доказывается, почему элементы мно-ва К. представляются без двойки, и вообще хотелось бы чего-нибудь покрасивее.

Заслуженный участник

Последний раз редактировалось ИСН 15.02.2012, 23:03, всего редактировалось 1 раз.

Последний раз редактировалось Asker Tasker 09.06.2012, 17:53, всего редактировалось 2 раз(а).

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

На концах интервалов возникнет небольшая проблема. Вернёмся к первому шагу: концы выкинутого интервала имеют двойное представление в троичной системе:
1/3 = 0,100.
2/3 = 0,122.
Договоримся использовать для таких точек ту форму записи, в которой отсутствуют единицы. Также отметим, что этих точек счётное число: имеем счётное число шагов и на каждом таких «точек деления» конечное количество, то есть всего их число счётное.

Что делается дальше, точно не помню, но, кажется, как-то так. В итоге получим, что множество Кантора состоит из точек, троичная запись которых допускает представление без единиц. Между точками, которые в принципе единиц не содержат, построим биекцию с двоичными дробями (из отрезка [0; 1]), допускающими однозначное представление. А дробей, допускающих двоякое представление, число счётное. Между ними и «точками деления» множества Кантора (которых тоже число счётное) биекцию построить просто.

Заслуженный участник

Последний раз редактировалось Asker Tasker 12.06.2012, 20:23, всего редактировалось 1 раз.

A если привести такой контрпример:

При каждом разбиении образуются отрезки, концами которых являются рациональные числа. Поставим в соответствие каждому отрезку рациональное число являющееся, скажем, началом отрезка. Множество рациональных чисел счетно, следовательно множество отрезков то же счетно. Выходит совершенное канторово множество счетно.

Возникло противоречие с утверждением, что оно континуально.

Где ошибка в таком доказательстве?

Заслуженный участник

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей

Источник

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки

Правила форума

В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе «Помогите решить/разобраться (М)».

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Как доказать, что множество Кантора имеет мощность континуум

Последний раз редактировалось taburet 01.08.2012, 15:10, всего редактировалось 1 раз.

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

И получается, что вроде как всякая точка канторова множества есть общая рациональная точка какой-нибудь последовательности вложенных отрезков, т.е. канторово множество счетно.

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

Заслуженный участник

Наверняка остаются. Т.е. идея моего поста заключается в том, что хочу получить доказательство, которое меня убедит и которым я смогу убедить другого болвана.

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

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

Заслуженный участник

Последний раз редактировалось svv 02.08.2012, 19:01, всего редактировалось 3 раз(а).

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

В Вашей последовательности даже не все рациональные числа из содержатся. Например, отсутствует , в двоичной записи это

Заслуженный участник

Последний раз редактировалось taburet 02.08.2012, 20:22, всего редактировалось 9 раз(а).

Таким образом очевидно нет.

Но в доказательстве, того, что мощность канторова множества имеет мощность континуума Александров П.С. (Введение в общую теорию множеств и функций. с.139) использует другой подход (это распространенное доказательство), а именно (вкратце): так как каждая точка множества принадлежит единственному сегменту разбиения первого ранга, единственному сегменту второго, третьего и т.п., каждой точке соответствует последовательность сегментов образующих систему вложенных отрезков. И что бы занумеровать точку мы составляем бинарный код, который описывает её положение в системе отрезков. Т.о. если в первом разбиении точка принадлежит левому отрезку, пишем в последовательность в первый разряд , иначе , если во втором разбиении этого отрезка точка принадлежит левому отрезку ставим во второй разряд иначе и т.д. Т.о. каждой точке ставится в соответствие бесконечная последовательность вида: или скажем последовательность одних нулей для точки ноль. Далее доказывается, что таких последовательностей несчетное множество.

Правда вот не во взаимно однозначное соответствие. мда. так же, как канторово занумеровать нельзя.

Да что уж там, я и вправду не понимаю этого множества. Оно замкнуто, значит дополнение открыто, значит дополнение можно покрыть открытыми интервалами, причем счетным множеством, само канторово множество отрезков не содержит, как же так? т.е. «дырок» между открытыми интервалами больше чем этих интервалов?

За тупой «контрпример» приношу свои извинения.

Ладно мой вопрос сводится в итоге вот к чему, как найти любую трансцендентную точку в множестве кантора, и построить её приближение десятичной дробью? Ну и тот, что выше.

Заслуженный участник

Последний раз редактировалось svv 02.08.2012, 23:47, всего редактировалось 2 раз(а).

Вы всё время пропускаете дробь . Смотрите, обидится.

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

А конечных — уже не континуум, а только счётное множество. Их можно занумеровать:
1: 1
2: 01
3: 11
4: 001
5: 101
6: 011
7: 111
Кстати, я здесь использовал интересный принцип нумерации. Наши последовательности всегда заканчиваются единицей (последующие нули мы подразумеваем, но не пишем). Прочтем последовательность справа налево, считая, что это натуральное число в двоичной записи. Это число и будет номером.

🙂 да, везде забыл.

А по поводу последовательности, я уже понял, что пример плохой, но всеравно спасибо. 🙂

Ладно, пойду Макарова почитаю, что-то у него там было про совершенные множества.

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей

Источник

Докажите что канторово множество имеет мощность континуума

Классическое множество Кантора, или пыль Кантора, названо по имени Георга Кантора, который описал его в 1883 году. Существование пыли Кантора отмечалось до этого Генри Смитом (Henry Smith) в 1875 году или еще ранее. Это множество хорошо известно студентам из курса математического анализа как пример множества нулевой меры Лебега [41], чья мощность равна мощности континуума [0,1]. Фрактальные свойства пыли Кантора имеют огромное значение, особенно учитывая тот факт, что многие известные фракталы являются близкими родственниками этого множества.

Построение классической пыли Кантора начинается с выбрасывания средней трети (не включая концы) единичного отрезка. То есть исходное множество есть отрезок [0,1], и первый шаг состоит в удалении открытого интервала (1/3,2/3). На следующем и всех остальных шагах мы выкидываем среднюю треть (не включая концы) всех отрезков текущего уровня. Таким образом, мы получаем (рис. 2.20) последовательность множеств:

Рис. 2.20. Построение пыли Кантора

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

Свойства канторовой пыли.

1. Канторова пыль есть самоподобный фрактал размерности

так как соотношение выполняется при .

2. Канторова пыль не содержит интервалов положительной длины. Это очевидно из построения.

3. Сумма длин интервалов, удаленных при построении множества С, в точности равна 1. Чтобы показать это, рассмотрим следующее доказательство. Длина первого интервала, который мы выкинули, составляет 1/3.

Чтобы получить мы выкинули два интервала, каждый длиной . На следующем шаге мы выбросили интервалов, каждый длиной , и т. д. Таким образом, сумма длин удаленных интервалов S составляет:

Но это выражение можно переписать в виде:

и с помощью формулы для суммы геометрической прогрессии, а именно,

Можно предположить, что если в С что-нибудь и осталось после удаления всех этих интервалов, то, наверное, не очень много. Однако это не так, что подтверждается следующим свойством.

4. Удивительный результат сравнения множества Кантора с интервалом состоит в том, что мощности этих множеств равны. Два множества обладают равной мощностью, если существует взаимно однозначное соответствие между точками этих множеств. В случае конечных множеств данное утверждение тривиально. Для бесконечных множеств, таких как интервал или множество Кантора, понятие мощности требует аккуратного обращения. В качестве простой иллюстрации сказанного достаточно заметить, что отрезки [0,1] и [0,2] — равной мощности, несмотря на то, что второй интервал в два раза длиннее первого. Взаимно однозначное соответствие в этом случае задается отображением , где .

Прежде чем приступить к доказательству основной теоремы о мощности множества Кантора, вспомним, как представить точку отрезка [0,1] в системе счисления с основанием . Разобьем отрезок [0,1] на N равных интервалов, каждый длины . Пронумеруем эти интервалы следующим образом: . Если оказалось, что точка принадлежит интервалу с номером 5, то положим Затем разобьем этот интервал на N новых интервалов, каждый длины . Пронумеруем эти интервалы, как и раньше:

Если точка принадлежит новому интервалу с номером 3, то положим . Продолжая таким образом, получим бесконечную последовательность причем каждое значение определяет интервал, содержащий на шаге процесса разбиения. В результате, число может быть представлено бесконечной последовательностью:

и каждое такое представление соответствует некоторой точке отрезка [0,1]. Кратко его записывают следующим образом:

и называют представлением х в системе счисления с основанием N или в -ичной системе. Очевидно, запись числа в десятичной системе счисления, которой мы привыкли пользоваться, является частным случаем данного определения.

Обратим внимание на несколько математических аспектов, требующих особого рассмотрения. Во-первых, некоторые числа имеют более одного -ичного представления. Это числа вида , где j и k — положительные целые. Для таких чисел можно указать два -ичных представления: одно оканчивается всеми нулями, а другое — всеми . Например, в двоичной системе может быть представлено двумя способами:

Любое число вида, отличного от записывается в -ичной системе счисления единственным образом. Также мы оставили без ответа вопрос, соответствует ли произвольное -ичное представление единственному . Этих вопросы решаются точно также, как и в случае обычного десятичного представления.

Теорема 2.3.2. Мощность множества Кантора С равна мощности континуума [0,1].

Доказательство. Нам необходимо установить взаимно однозначное соответствие между точками из С и точками отрезка [0,1]. Для этого нам потребуется рассмотреть двоичное (по основанию 2), а также троичное (по основанию 3) представления точек отрезка [0,1].

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

Замечаем, что точка попадает в множество Кантора С тогда и только тогда, когда в ее троичном представлении отсутствуют единицы, то есть когда в нем присутствуют только нули и двойки. Тогда искомое соответствие точек из С с точками отрезка [0,1] осуществляется заменой всех двоек в троичном представлении х на единицы. Полученное таким образом двоичное представление определяет некоторое вещественное число у. Например, если есть:

Описанная процедура определяет взаимно однозначное соответствие между .

5. Классическая канторова пыль представляет собой пример компактного, совершенного и вполне разрывного множества. Эти понятия объясняются в главе 3. Более того, можно утверждать, что топологически классическое множество Кантора определяется как компактное, совершенное и вполне разрывное множество. Это означает, что любое компактное, совершенное и вполне разрывное множество можно непрерывно преобразовать в пыль Кантора, причем существует обратное преобразование, с помощью которого можно восстановить исходное множество. Любое такое множество принято называть множеством Кантора. Не следует думать, однако, что все множества Кантора самоподобны. Более того, даже фрактальная размерность различных самоподобных множеств Кантора не обязательно совпадает, как показывает следующий пример.

Источник