набрел случайно на бесконечности (по книге "Ловкость ума") и воткнул.
1) "Гранд-отель" (бесконечность Гилберта), да и парадокс Банаха-Тарского говорит нам о том что и счетные, и несчетные бесконечности биективны, а значит имеют одинаковые мощности. Например, что |[0;1]| == |[0;2]|
2) И тут же теорема Кантора гласит что для Х:|X| < |P(X)|, что мощность показательного множества строго больше мощности исходного множества и в качестве доказательства приводится приведение к небиективности.
Почему же нельзя тот же доказательство из 2) использовать для опровержения 1)?
Здравствуйте, pva, Вы писали:
pva>1) "Гранд-отель" (бесконечность Гилберта), да и парадокс Банаха-Тарского говорит нам о том что и счетные, и несчетные бесконечности биективны, а значит имеют одинаковые мощности.
Нет. Счётные бесконечности между собой равномощны, и все они (по определению счётности) равномощны ℕ.
Между бесконечными счётным и несчётным множествами нет биекции. И между некоторыми несчётными тоже, например, между множеством вещественных чисел и множеством всех подмножеств вещественных чисел.
pva>Например, что |[0;1]| == |[0;2]|
спасибо за ответ. Q>Нет. Счётные бесконечности между собой равномощны, и все они (по определению счётности) равномощны ℕ. Между бесконечными счётным и несчётным множествами нет биекции.
Не понял к чему относится "Нет". Там мое утверждение немного неоднозначно. Имелось в виду что счетные бесконечности равномощны между собой, а несчетные равномощны между собой.
Q> И между некоторыми несчётными тоже (нет биекции), например, между множеством вещественных чисел и множеством всех подмножеств вещественных чисел. pva>>Например, что |[0;1]| == |[0;2]| Q>В этом случае да.
Вот мой вопрос и заключался, по сути, в том чем этот случай несчетной бесконечности (или с удвоением шаров) отличается от случая с показательным множеством? И почему нельзя применить противоречие от доказательства второго для опровержения первого?
pva>>Например, что |[0;1]| == |[0;2]| Q>В этом случае да.
Попутно еще вопрос: вот имеем мы несчетное бесконечное X0;1). Для любого х из Х мы можем сопоставить n из N откинув начальный "0." и получив из несчетного бесконечного счетное. Так-то интуитивно понятно что всякие иррациональные не представимы таким образом, но у нас то счетное бесконечное.
А, блин, они там используют диагонализацию для доказательства невозможности такой биекции. Но как-то неочевидно это из их доказательства.
Чтобы понять логику Кантора, представьте, что вы пишете бесконечный список всех иррациональных чисел в двоичном виде. Предположим, что пос ле огромных, изнурительных усилий вы считаете, что завершили список и включили в него все иррациональные числа. Пометьте каждое число в том порядке, в котором оно приведено в списке: назовите первое число n1, второе n2 и т. д. Теперь определите функцию f(), которая берет ваш упорядоченный список и выводит число, где n-й разряд противоположен n-му разряду n-го числа в вашем списке. Поскольку функция выводит иррациональное число, которое отличается от любого другого иррационального числа в вашем списке по крайней мере одним разрядом, следовательно, этого нового числа нет в списке. Первоначальный список нельзя считать полным. Двоичная версия этого доказательства распространяется на любое другое основание.
Ну ок, вводят они функцию f(n), которая по сути является генератором X -> X. Ну так что мешает нам задать счетность над этой функцией? В итоге получив из несчетной бесконечности счетную поскольку n-то у нас принадлежит N.
pva>Ну ок, вводят они функцию f(n), которая по сути является генератором X -> X. Ну так что мешает нам задать счетность над этой функцией? В итоге получив из несчетной бесконечности счетную поскольку n-то у нас принадлежит N.
А толку от этой полученной счетной бесконечности? Тут же нет гарантии, что она будет покрывать все возможные элементы множества X.
Здравствуйте, D. Mon, Вы писали:
pva>>Ну ок, вводят они функцию f(n), которая по сути является генератором X -> X. DM>Что за Х? Функция та из списка делает одно число.
Она из заданного подмножества несчетного бесконечного множества порождает еще один элемент этого же множества. Чем это отличается от заселения еще одного гостя в гранд-отель?
pva>> Ну так что мешает нам задать счетность над этой функцией? DM>Что это значит? Счетность — это свойство множества.
Нуууу.. если прям вглубь, то это значит определить биекцию между этим несчетным бесконечным множеством и счетным бесконечным множеством.
Здравствуйте, klopodav, Вы писали:
pva>>Ну ок, вводят они функцию f(n), которая по сути является генератором X -> X. Ну так что мешает нам задать счетность над этой функцией? В итоге получив из несчетной бесконечности счетную поскольку n-то у нас принадлежит N. K>А толку от этой полученной счетной бесконечности? Тут же нет гарантии, что она будет покрывать все возможные элементы множества X.
А какая гарантия что [0;1) покрывает [0;2)? Тем не менее, покрывает жеж. И тот же самый вариант с удвоением шаров.
Здравствуйте, pva, Вы писали:
pva>Она из заданного подмножества несчетного бесконечного множества порождает еще один элемент этого же множества.
Откуда подмножество?
Диагональный аргумент он про: если бы то множество было счетным, то ... получаем противоречие, потому оно не счетное. Т.е. изначально предполагается, что список содержит все множество целиком.
pva> Чем это отличается от заселения еще одного гостя в гранд-отель?
Тем, что про "отель" (список) изначально заявлено, что он содержит всех людей, новому гостю взяться неоткуда. Когда там конструируют "гостя", отличного от всех имеющихся, тут и возникает противоречие.
pva>>> Ну так что мешает нам задать счетность над этой функцией? DM>>Что это значит? Счетность — это свойство множества. pva>Нуууу.. если прям вглубь, то это значит определить биекцию между этим несчетным бесконечным множеством и счетным бесконечным множеством.
Т.е. использовать ту функцию в качестве биекции? Еще раз на тип ее я предлагаю посмотреть, какие два множества она связывает. И какие должна для биекции.
...
в целом мне понятны ваши аргументы. похоже, у меня проблемы с понятием несчетного множества.
и похоже, что я провалился в континуум-гипотезу. меня вот смущает в википедии такое объяснение
Другими словами, гипотеза предполагает, что мощность континуума — наименьшая, превосходящая мощность счётного множества, и «промежуточных» мощностей между счетным множеством и континуумом нет. В частности, это предположение означает, что для любого бесконечного множества действительных чисел всегда можно установить взаимно-однозначное соответствие либо между элементами этого множества и множеством целых чисел, либо между элементами этого множества и множеством всех действительных чисел.
Но если возможно установить такое соответствие (выделено жирным), то оно ведь будет счетным.
Здравствуйте, pva, Вы писали:
pva>Но если возможно установить такое соответствие (выделено жирным), то оно ведь будет счетным.
Да, там речь не про R, множество всех действительных чисел, а какое-то бесконечное множество действительных чисел. Например, множество всех действ. чисел, заканчивающихся на .123 .
Здравствуйте, pva, Вы писали:
pva>Здравствуйте, klopodav, Вы писали:
pva>>>Ну ок, вводят они функцию f(n), которая по сути является генератором X -> X. Ну так что мешает нам задать счетность над этой функцией? В итоге получив из несчетной бесконечности счетную поскольку n-то у нас принадлежит N. K>>А толку от этой полученной счетной бесконечности? Тут же нет гарантии, что она будет покрывать все возможные элементы множества X. pva>А какая гарантия что [0;1) покрывает [0;2)?
а разве равная мощность множеств означает покрытие? [0;2) — [0;1) = [1;2), и их биекция не означает покрытие
pva>Тем не менее, покрывает жеж. И тот же самый вариант с удвоением шаров.
это про экспоненту ?
Здравствуйте, D. Mon, Вы писали:
pva>>Но если возможно установить такое соответствие (выделено жирным), то оно ведь будет счетным. DM>Да, там речь не про R, множество всех действительных чисел, а какое-то бесконечное множество действительных чисел. Например, множество всех действ. чисел, заканчивающихся на .123 .
Попробую все-таки обобщить.
Вот есть счетные бесконечные с равномощностью А0, и несчетные с равномощностью А1 (== 2^A0, что само по себе странно). Промежуточных мощностей внутри нет.
Есть у нас гранд-отель для счетных, в который, несмотря на заполненность, всегда можно впихнуть новый элемент множества и его равномощность не изменится.
Есть у нас "принцип масштабирования" для несчетных как в одной размерности (с интервалами), так и по размерностям (шары, гиперразмерности?), который показывает что несчетные биективны (?) и равномощны.
И теорема Кантора нам говорит что мощность показательного множества для счетного множества — несчетное множество.
вот здесь у меня разрыв, ведь показательное множество, по сути, комбинация элементов счетного множества и согласно гранд-отелю, мы всегда можем добавить новую комбинацию к списку имеющихся не меняя мощности.
Здравствуйте, pva, Вы писали:
pva>Промежуточных мощностей внутри нет.
Кто сказал?
pva>вот здесь у меня разрыв, ведь показательное множество, по сути, комбинация элементов счетного множества и согласно гранд-отелю, мы всегда можем добавить новую комбинацию к списку имеющихся не меняя мощности.
Почему ты решил что только счетное множество обладает свойством N+1=N?
Здравствуйте, ребусоид, Вы писали:
pva>>А какая гарантия что [0;1) покрывает [0;2)? Р> а разве равная мощность множеств означает покрытие? [0;2) — [0;1) = [1;2), и их биекция не означает покрытие
Ну, если под покрытием понимать эквивалентность, то, вероятно, нет. Но с точки зрения биективности это же равномощные множества, а значит одним можно накрыть другое.
pva>>Тем не менее, покрывает жеж. И тот же самый вариант с удвоением шаров. Р> это про экспоненту?
Это про парадокс Банаха-Тарского.
Здравствуйте, pva, Вы писали:
pva>Есть у нас гранд-отель для счетных, в который, несмотря на заполненность, всегда можно впихнуть новый элемент множества и его равномощность не изменится. pva>Есть у нас "принцип масштабирования" для несчетных как в одной размерности (с интервалами), так и по размерностям (шары, гиперразмерности?), который показывает что несчетные биективны (?) и равномощны.
Ага, тут везде один и тот же метод по сути используется: мы строим функцию-биекцию, взаимно-однозначное соответствие. Она связывает два множества поэлементно как застежка-молния, демонстрируя их равномощность. Для отеля эта функция сопоставляет старый и новый номер комнаты для каждой комнаты. Для интервалов, шаров и пр. — отображает точки, тоже по сути говорит кто куда переезжает, просто вместо номера комнаты там координаты точки. Можно еще заметить, что для мощности множества "размерность" множества не важна, в 1Д отрезке столько же точек, сколько в 2Д квадрате или 3Д шаре. Можно сконструировать функцию-биекцию, это показывающую.
pva>И теорема Кантора нам говорит что мощность показательного множества для счетного множества — несчетное множество. pva>вот здесь у меня разрыв, ведь показательное множество, по сути, комбинация элементов счетного множества и согласно гранд-отелю, мы всегда можем добавить новую комбинацию к списку имеющихся не меняя мощности.
Тут предлагаю опять смотреть на типы. Множество подмножеств уже имеет другой тип элементов по сравнению с оригинальным множеством, это уже совсем другое множество. Поэтому "не меняя" тут сказать нельзя — мы не пытаемся что-то менять, добавляя, мы изначально с другим объектом дело имеем.
Интуитивно можно так на это посмотреть. Счетное множество можно представить мысленно как бесконечный ряд комнат, имеющий начало, и уходящий в бесконечность. Одно его подмножество можно закодировать, поставив 1 рядом с комнатами, что входят в подмножество, и 0 рядом с теми, что не входят. Получаем последовательность из нулей и единиц, допишем перед ней "0." и получим вещественное число в двоичном представлении в интервале [0, 1]. Одно вещественное число кодирует целое подмножество нашего исходного счетного множества. А множество всех таких подмножеств — это множество всех таких вот вещественных чисел, т.е. это интервал [0, 1] в R. Который равномощен R. Вот и выходит, что 2^N = R.
Здравствуйте, T4r4sB, Вы писали:
pva>>Промежуточных мощностей внутри нет. TB>Кто сказал? Иерархия алефов и континуум-гипотеза.
pva>>вот здесь у меня разрыв, ведь показательное множество, по сути, комбинация элементов счетного множества и согласно гранд-отелю, мы всегда можем добавить новую комбинацию к списку имеющихся не меняя мощности. TB>Почему ты решил что только счетное множество обладает свойством N+1=N?
Я такого не утверждал. Я только высказал непонимание почему множество комбинаций элементов бесконечного счетного множества является несчетным множеством, если гранд-отель позволяет растить счетное множество бесконечно.
И пока пришел только к тому что это "по определению".
Здравствуйте, D. Mon, Вы писали:
pva>>И теорема Кантора нам говорит что мощность показательного множества для счетного множества — несчетное множество. pva>>вот здесь у меня разрыв, ведь показательное множество, по сути, комбинация элементов счетного множества и согласно гранд-отелю, мы всегда можем добавить новую комбинацию к списку имеющихся не меняя мощности. DM>Тут предлагаю опять смотреть на типы. Множество подмножеств уже имеет другой тип элементов по сравнению с оригинальным множеством, это уже совсем другое множество. Поэтому "не меняя" тут сказать нельзя — мы не пытаемся что-то менять, добавляя, мы изначально с другим объектом дело имеем.
Да, мы переходим от типа "элементы множества" к типу "комбинации элементов". Давай введем функцию f(n), которая для заданного множества выдает n-ю комбинацию из исходного множества. И таки да, эта функция по сути будет то что ты описал ниже — разложением n в двоичный вид. При этом n:N, а значит |f(n)| == |N|?
Edit: получается счетно-бесконечное количество комбинаций из счетно-бесконечного множества элементов составляет несчетно-бесконечное множество? Интересно, а нельзя ли добавить сюда еще один уровень вложенности?
DM>Интуитивно можно так на это посмотреть. Счетное множество можно представить мысленно как бесконечный ряд комнат, имеющий начало, и уходящий в бесконечность. Одно его подмножество можно закодировать, поставив 1 рядом с комнатами, что входят в подмножество, и 0 рядом с теми, что не входят. Получаем последовательность из нулей и единиц, допишем перед ней "0." и получим вещественное число в двоичном представлении в интервале [0, 1]. Одно вещественное число кодирует целое подмножество нашего исходного счетного множества. А множество всех таких подмножеств — это множество всех таких вот вещественных чисел, т.е. это интервал [0, 1] в R. Который равномощен R. Вот и выходит, что 2^N = R.
Вчера, я приходил уже к подобной гипотезе, когда разбирал диагонали с иррациональными числами, но в обратном направлении. В упрощенном виде: возьмем [0; 1) и откинем "0." — получим бесконечное счетное множество? Опровержение строилось на доказательстве через иррациональные. Италиком я выделил где потенциально у тебя ошибка: переход из счетного бесконечного, представимого натуральными к несчетному бесконечному, которое включает непредставимые натуральными (например, 1/3?). Тоесть, там не биекция, а инъекция.
>Я только высказал непонимание почему множество комбинаций элементов бесконечного счетного множества является несчетным множеством
потому что это и есть суть теоремы кантора: мощность булеана всегда больше мощности исходного множества. При чём тут отсылка к гранд-отелю — непонятно.
но можно и без теоремы кантора: прямо показать, что множество всех подмножеств счетного множества несчетно
> гранд-отель позволяет растить счетное множество бесконечно.
гранд-отель не позволяет "растить" множество: количество элементов в нём не меняется — это доказывается биекцией элементов исходного гранд-отеля и типа "увеличенного" и после добавления новых элементов
а в общем — ну, бесконечности, они такие, не всё и не всегда очевидно. И не всегда есть просто объяснение на пальцах
Здравствуйте, pva, Вы писали:
pva>Здравствуйте, T4r4sB, Вы писали:
pva>>>Промежуточных мощностей внутри нет. TB>>Кто сказал? pva>Иерархия алефов и континуум-гипотеза.
Это отдельный факт который из классической теории множеств не следует
pva>>>вот здесь у меня разрыв, ведь показательное множество, по сути, комбинация элементов счетного множества и согласно гранд-отелю, мы всегда можем добавить новую комбинацию к списку имеющихся не меняя мощности. TB>>Почему ты решил что только счетное множество обладает свойством N+1=N? pva>Я такого не утверждал. Я только высказал непонимание почему множество комбинаций элементов бесконечного счетного множества является несчетным множеством, если гранд-отель позволяет растить счетное множество бесконечно.
То что ты можешь добавить в счетное множество любое конечное или счетно-бесконечное число посетителей, никак не позволит ему стать континумом
pva>И пока пришел только к тому что это "по определению".
Нет это по теореме доказывающейся через диагонализацию
Здравствуйте, Вумудщзук, Вы писали:
В>потому что это и есть суть теоремы кантора: мощность булеана всегда больше мощности исходного множества. При чём тут отсылка к гранд-отелю — непонятно.
Выше я несколько раз в различных вариантах описал причем здесь отсылка к гранд-отелю.
В какой момент 2^n из счетного переходит в несчетное?
В>но можно и без теоремы кантора: прямо показать, что множество всех подмножеств счетного множества несчетно
Было бы здорово, если подобное показательство вы изложили бы для средних умов — "на пальцах".
>> гранд-отель позволяет растить счетное множество бесконечно. В>гранд-отель не позволяет "растить" множество: количество элементов в нём не меняется — это доказывается биекцией элементов исходного гранд-отеля и типа "увеличенного" и после добавления новых элементов В>а в общем — ну, бесконечности, они такие, не всё и не всегда очевидно. И не всегда есть просто объяснение на пальцах
Я потому-то тему и завел, что образования не хватает, а хотелось бы понять или хотя бы проследить цепочку рассуждений, приводящих к нужному выводу.
Здравствуйте, T4r4sB, Вы писали:
TB>Это отдельный факт который из классической теории множеств не следует
Так я про классическую ТМ, вроде бы, ничего и не заявлял.
TB>То что ты можешь добавить в счетное множество любое конечное или счетно-бесконечное число посетителей, никак не позволит ему стать континумом
Ну вот мы берем счетное бесконечное и начинаем составлять из его элементов комбинации и... бац! количество этих комбинаций — несчетно-бесконечное, сравнимое по мощности с континуумом.
1, 2, ... 1000... оопс..
pva>>И пока пришел только к тому что это "по определению". TB>Нет это по теореме доказывающейся через диагонализацию.
Ок, попробую перечитать ее еще раз.
Здравствуйте, pva, Вы писали:
pva>Ну вот мы берем счетное бесконечное и начинаем составлять из его элементов комбинации и... бац! количество этих комбинаций — несчетно-бесконечное, сравнимое по мощности с континуумом.
Ну да. И? Это не значит что ты можешь их все добавить в исходное множество и сохранить его мощность
Если в счетное множество добавишь континум элементов то будет континум
Здравствуйте, pva, Вы писали:
pva>Да, мы переходим от типа "элементы множества" к типу "комбинации элементов". Давай введем функцию f(n), которая для заданного множества выдает n-ю комбинацию из исходного множества. И таки да, эта функция по сути будет то что ты описал ниже — разложением n в двоичный вид. При этом n:N, а значит |f(n)| == |N|?
Да, |f(n)| == |N|, но такая f(n) не даст нам _все_ подмножества.
Нужна f(s), где s:R. Тогда |f(s)| == |R|. Там будут все.
Если мы берем только натуральные числа и смотрим на их бинарное представление, у нас всегда будут конечные последовательности. А раскладывая действительные числа, у нас будет еще больше бесконечных.
pva>Edit: получается счетно-бесконечное количество комбинаций из счетно-бесконечного множества элементов составляет несчетно-бесконечное множество?
Нет. Что именно мы считаем тут? Счетное множество строк остается счетным. А несчетное — несчетным. Какое построишь.
pva>Вчера, я приходил уже к подобной гипотезе, когда разбирал диагонали с иррациональными числами, но в обратном направлении. В упрощенном виде: возьмем [0; 1) и откинем "0." — получим бесконечное счетное множество?
Нет, откуда ему счетным стать? Как нам его пересчитать, какой элемент там первый, какой второй?
Здравствуйте, D. Mon, Вы писали:
pva>>Да, мы переходим от типа "элементы множества" к типу "комбинации элементов". Давай введем функцию f(n), которая для заданного множества выдает n-ю комбинацию из исходного множества. И таки да, эта функция по сути будет то что ты описал ниже — разложением n в двоичный вид. При этом n:N, а значит |f(n)| == |N|? DM>Да, |f(n)| == |N|, но такая f(n) не даст нам _все_ подмножества.
Почему не даст-то? Ведь двоичное представление n и будет определять состав подмножества (либо элемент присутствует, либо нет). Ведь это эквивалент твоему описанию
Счетное множество можно представить мысленно как бесконечный ряд комнат, имеющий начало, и уходящий в бесконечность. Одно его подмножество можно закодировать, поставив 1 рядом с комнатами, что входят в подмножество, и 0 рядом с теми, что не входят.
DM>Нужна f(s), где s:R. Тогда |f(s)| == |R|. Там будут все.
Каким образом f(s:R) должна определять выбранную комбинацию?
DM>Если мы берем только натуральные числа и смотрим на их бинарное представление, у нас всегда будут конечные последовательности. А раскладывая действительные числа, у нас будет еще больше бесконечных.
Для n:N => f(0) = (0); f(1) = 1(0); f(2) = 01(0); f(3) = 11(0); etc
А как это должно работать для s:R?
pva>>Edit: получается счетно-бесконечное количество комбинаций из счетно-бесконечного множества элементов составляет несчетно-бесконечное множество? DM>Нет. Что именно мы считаем тут? Счетное множество строк остается счетным. А несчетное — несчетным. Какое построишь.
Это я все никак не могу смириться с тем что количество комбинаций из счетно-бесконечного (2^A0) — несчетно-бесконечное (== A1).
pva>>Вчера, я приходил уже к подобной гипотезе, когда разбирал диагонали с иррациональными числами, но в обратном направлении. В упрощенном виде: возьмем [0; 1) и откинем "0." — получим бесконечное счетное множество? DM>Нет, откуда ему счетным стать? Как нам его пересчитать, какой элемент там первый, какой второй?
Отличный вопрос, а теперь перечитай свое
... Получаем последовательность из нулей и единиц, допишем перед ней "0." и получим вещественное число в двоичном представлении в интервале [0, 1]. Одно вещественное число кодирует целое подмножество нашего исходного счетного множества. А множество всех таких подмножеств — это множество всех таких вот вещественных чисел, т.е. это интервал [0, 1] в R. Который равномощен R. Вот и выходит, что 2^N = R.
Если бы это была биекция, то работало бы в обе стороны. Выходит что процитированное утверждение содержит ошибку.
Здравствуйте, T4r4sB, Вы писали:
pva>>Ну вот мы берем счетное бесконечное и начинаем составлять из его элементов комбинации и... бац! количество этих комбинаций — несчетно-бесконечное, сравнимое по мощности с континуумом. TB>Ну да. И? Это не значит что ты можешь их все добавить в исходное множество и сохранить его мощность TB>Если в счетное множество добавишь континум элементов то будет континум
Так в том то и вопрос, добавляю ли я туда континум элементов или нет. У нас есть исходное X:N — счетно-бесконечное. Составляем из его элементов комбинации и заполняем наш отель: каждая комбинация — гость. В какой же момент количество этих комбинаций станет континумом вместо счетно-бесконечного?
Здравствуйте, pva, Вы писали:
pva>Здравствуйте, ребусоид, Вы писали:
pva>>>А какая гарантия что [0;1) покрывает [0;2)? Р>> а разве равная мощность множеств означает покрытие? [0;2) — [0;1) = [1;2), и их биекция не означает покрытие pva>Ну, если под покрытием понимать эквивалентность, то, вероятно, нет. Но с точки зрения биективности это же равномощные множества, а значит одним можно накрыть другое.
ну скажем накрыть, или покрыть скорее ближе звучит к включению, ну впрочем уж ладно, разговор о терминах.
Здравствуйте, pva, Вы писали:
DM>>Да, |f(n)| == |N|, но такая f(n) не даст нам _все_ подмножества. pva>Почему не даст-то?
Нет такого n:N, для которого его двоичная запись бесконечна. В множестве всех f(n) будут только конечные подмножества (их кодировки). А нам нужно закодировать массу бесконечных подмножеств тоже.
Например, 010101010101.... или 001001001001... или 010010001000010000010.....
DM>>Нужна f(s), где s:R. Тогда |f(s)| == |R|. Там будут все. pva>Каким образом f(s:R) должна определять выбранную комбинацию?
Через двоичное представление s. Главная разница в том, что для большинства s:R их двоичное представление — бесконечная последовательность (и речь не про хвост из нулей, там бесконечно много единиц и нулей в разных комбинациях). Такие нам и нужны. См. определение действительных чисел.
pva>>>Вчера, я приходил уже к подобной гипотезе, когда разбирал диагонали с иррациональными числами, но в обратном направлении. В упрощенном виде: возьмем [0; 1) и откинем "0." — получим бесконечное счетное множество? DM>>Нет, откуда ему счетным стать? Как нам его пересчитать, какой элемент там первый, какой второй? pva>Отличный вопрос, а теперь перечитай свое pva>
... Получаем последовательность из нулей и единиц, допишем перед ней "0." и получим вещественное число в двоичном представлении в интервале [0, 1]. Одно вещественное число кодирует целое подмножество нашего исходного счетного множества. А множество всех таких подмножеств — это множество всех таких вот вещественных чисел, т.е. это интервал [0, 1] в R. Который равномощен R. Вот и выходит, что 2^N = R.
pva>Если бы это была биекция, то работало бы в обе стороны.
Оно и работает в обе стороны. Каждому подмножеству N (т.е. не каждому числу, а каждому набору чисел, в том числе бесконечному) я однозначно ставлю в соответствие одно действительное число.
Например, число 0.0011 кодирует множество {2,3}. А число 0.1001001001001001001(001) кодирует бесконечное множество {0, 3, 6, 9, 12, ... } — все, что делятся на 3.
Таких кодировок несчетно много. Их ровно столько сколько действительных чисел от 0.00000... до 0.11111....
Но это множество чисел/кодировок, не последовательность, я не могу выписать их все по очереди и пронумеровать. Если бы мог — это было бы счетное множество. Но как нет самого маленького положительного числа, так нет и первого или второго по порядку числа в этом наборе. Мы можем с ним работать как с множеством, но не как со списком.
Здравствуйте, pva, Вы писали:
pva>Так в том то и вопрос, добавляю ли я туда континум элементов или нет. У нас есть исходное X:N — счетно-бесконечное. Составляем из его элементов комбинации и заполняем наш отель: каждая комбинация — гость. В какой же момент количество этих комбинаций станет континумом вместо счетно-бесконечного?
Если ты будешь добавлять гостей по одному то у тебя в любой момент будет добавлено не более конечного количества гостей. Например если ты каждую секунду будешь добавлять одного гостя то через час у теья будет добавлено только 3600 гостей. То есть ты просто никогда не "заселишь" все элементы континуума.
А если ты думаешь что можно сказать "давай закидывать их одного потом другого и так далее" то так нельзя обращаться с бесконечностями.
Мне кажется ты слишком нестрого понимаешь смысл слова "запустим процес будем чтото делать, ну и так далее". В математике нет такого понятия, любой переход внутри конечного числа элементов делается по аксиоме индукции а переход в бесконечность тоже через отдельные аксиомы.
И если математик говорит "и так далее" то он это делает только когда в контексте есть очевидное индукционное предположение или функция отображения.
>В какой момент 2^n из счетного переходит в несчетное?
в какой момент чего?
В>>но можно и без теоремы кантора: прямо показать, что множество всех подмножеств счетного множества несчетно pva>Было бы здорово, если подобное показательство вы изложили бы для средних умов — "на пальцах".
оно ж излагается во всех учебниках по теории множеств....
ну, во1х, все счетные множества равномощны N, поэтому можно рассматривать именно его и множество его подмножеств.
каждому подмножеству N можно поставить в соответствие бесконечную последовательность из нулей и единиц, где единицы стоят на позициях под теми номерами, из которых и состоит подмножество:
(3,4,8) -> (0,0,1,1,0,0,0,1,0,0...)
очевидно, что это отношение биективно: каждому подмножеству однозначно ставится в соответствие последовательность, и по каждой последовательности очевидным образом восстанавливается подмножество.
А множество таких бесконечных последовательностей из 0 и 1 несчетно.
Это сам по себе результат известный. Ну или доказывается тем же диагональным методом, или так: к каждой последовательности припишем слева "0,". Все получившиеся строчки вида 0,0100101010101... — это двоичные представления всех чисел от 0 до 1. Это тоже очевидно: каждому числу соответствует его двоичное представление и наоборот.
Т.о. построено взаимно однозначное отображение всех подмножеств N на отрезок [0,1] — несчетное множество.
(тут есть момент, что у некоторых чисел существует два двоичных разложения по аналогии с десятичной системой: есть 0.5, а есть 0.4(9) — число одно, а разложения 2, но множество таких чисел счетно, поэтому принципиально оно картины не меняет)
в этих бесконечностях не всегда интуитивно понятно, когда одно переходит в другое. Вот множество всех конечных подмножеств N — счетно как счетное объединение счетных множеств. А вот множество всех подмножеств уже несчетно, т.е несчетным является именно множество бесконечных подмножеств N. Что-то для интуиции тут тоже есть: наверняка на этой же идее, что и выше, можно построить биекцию множества конечных подмножеств N на Q (рациональные числа), а бесконечных — на иррациональные.
Здравствуйте, D. Mon, Вы писали:
DM>Нет такого n:N, для которого его двоичная запись бесконечна. В множестве всех f(n) будут только конечные подмножества (их кодировки). А нам нужно закодировать массу бесконечных подмножеств тоже. DM>Через двоичное представление s. Главная разница в том, что для большинства s:R их двоичное представление — бесконечная последовательность (и речь не про хвост из нулей, там бесконечно много единиц и нулей в разных комбинациях). Такие нам и нужны. См. определение действительных чисел.
Ага!.. вот это похоже на недостающий кусок паззла. По крайней мере тепло. )
Но разве для n == +inf разложение не будет бесконечным? По сути это же и есть наш отель — его двоичная запись бесконечна и мы можем с его помощью задать любой из вариантов бесконечного разложения.
Другой вопрос что если представить что в таком случае это будет только один вариант из бесконечного множества вариантов — тогда да. Получается что R задает "второе измерение" для нашего линейного отеля.
Перечитал твое
Одно вещественное число кодирует целое подмножество нашего исходного счетного множества. А множество всех таких подмножеств — это множество всех таких вот вещественных чисел, т.е. это интервал [0, 1] в R. Который равномощен R. Вот и выходит, что 2^N = R.
и похоже это почти то же самое что я выше написал. И похоже что T4r4sB пишет о том же.
Здравствуйте, pva, Вы писали:
pva>Но разве для n == +inf разложение не будет бесконечным?
Нет такого натурального числа, +inf. Есть бесконечно много конкретных натуральных чисел, но каждое из них конечно, записывается конечным набором цифр, содержит конечное количество информации.
А действительные числа качественно другие — большинство из них таят в себе бесконечно много информации, их запись/кодировка бесконечна, для одного конкретного числа. Что и позволяет взять любое бесконечное множество натуральных чисел и закодировать его одним единственным вещественным числом. Т.е. это такие качественно более емкие объекты. И разнообразие их качественно выше, мощность множества всех вещ. чисел принципиально выше.
pva>По сути это же и есть наш отель — его двоичная запись бесконечна и мы можем с его помощью задать любой из вариантов бесконечного разложения.
Тут нужно аккуратнее что именно чем именно представляем. Если мы хотим множество всех четных номеров, это одно подмножество N, но бесконечное. Одним натуральным числом его не представишь. А одним действительным — запросто. 0.1010(10)
TB>>То что ты можешь добавить в счетное множество любое конечное или счетно-бесконечное число посетителей, никак не позволит ему стать континумом pva>Ну вот мы берем счетное бесконечное и начинаем составлять из его элементов комбинации и... бац! количество этих комбинаций — несчетно-бесконечное, сравнимое по мощности с континуумом. pva>1, 2, ... 1000... оопс..
а множество цифр так вообще конечное. Но как начинаем составлять из него комбинации и — бац — получаем все числа, т.е. несчетное множество. А если приплести сюда функции, можно получить ещё более мощное множество. Ужос, що творится...
с канторовым множеством похожая фигня: на каждом шаге его построения имеем конечное множество отрезков, а в пределе (после счетного количества шагов) получаем несчетное множество. Хотя на первый взгляд должно быть счетным, но неть. Причём множество нигде не плотное, но при этом закрытое.
Здравствуйте, Вумудщзук, Вы писали:
В>а множество цифр так вообще конечное. Но как начинаем составлять из него комбинации и — бац — получаем все числа, т.е. несчетное множество. А если приплести сюда функции, можно получить ещё более мощное множество. Ужос, що творится...
Описка? Ведь не существует более мощного чем А1.
В>с канторовым множеством похожая фигня: на каждом шаге его построения имеем конечное множество отрезков, а в пределе (после счетного количества шагов) получаем несчетное множество.
Так в этом же и был мой изначальный вопрос. С одной стороны отель, в который можно добавлять бесконечное количество счетных множеств, сохраняя мощность, а с другой — теорема Кантора. Но выше уже объяснили, что комбинации элементов помимо счетных содержат несчетно-бесконечные для которых отель нерепрезентативен.
pva>Описка? Ведь не существует более мощного чем А1.
неть, не описка: мощность множества всех функций, скажем, заданных на [0, 1] (хотя это неважно) — A2.
это всё та же теорема кантора: булеан множества мощней самого множества. Т.е. построение в цикле булеана от множества с предыдущего шага даёт всё более мощные множества.
Здравствуйте, pva, Вы писали:
pva>набрел случайно на бесконечности (по книге "Ловкость ума") и воткнул. pva>1) "Гранд-отель" (бесконечность Гилберта), да и парадокс Банаха-Тарского говорит нам о том что и счетные, и несчетные бесконечности биективны, а значит имеют одинаковые мощности. Например, что |[0;1]| == |[0;2]| pva>2) И тут же теорема Кантора гласит что для Х:|X| < |P(X)|, что мощность показательного множества строго больше мощности исходного множества и в качестве доказательства приводится приведение к небиективности. pva>Почему же нельзя тот же доказательство из 2) использовать для опровержения 1)?
А есть учебник или учебный курс(хоть ютуб), где все это(теория множеств и соотв. парадоксы) объясняется?
Здравствуйте, Вумудщзук, Вы писали:
В>неть, не описка: мощность множества всех функций, скажем, заданных на [0, 1] (хотя это неважно) — A2. В>это всё та же теорема кантора: булеан множества мощней самого множества. Т.е. построение в цикле булеана от множества с предыдущего шага даёт всё более мощные множества.
Да понял уже. Почему-то решил что континуум является пределом для мощности, хотя это нигде и не сказано.
Здравствуйте, Sharov, Вы писали:
S>А есть учебник или учебный курс(хоть ютуб), где все это(теория множеств и соотв. парадоксы) объясняется?
А черт его знает. Учебник найти, вероятно, не проблема. Проблема — найти нескучный учебник, да еще и чтоб "на пальцах".
Было бы здорово еще найти описание примеров приложения подобных вещей в реальной жизни.
>А черт его знает. Учебник найти, вероятно, не проблема. Проблема — найти нескучный учебник, да еще и чтоб "на пальцах". >Было бы здорово еще найти описание примеров приложения подобных вещей в реальной жизни.
на пальцах — это вряд ли, это ж учебник, а не tiktok challange. В учебниках просто излагается материал, подразумевая при некоторую основу (ну, там, матан какой-нть), от простого к сложному.
А в нескучной манере дальше каких-нть примеров не продвинешься. Как собссно и в любой науке.
а так — ну есть же всяческие популяризаторы, излагающие отдельные темы, то в тытрубке, то в дзене каком. В тытрубке вот есть у т-ща vsauce пара роликов — про парадокс банаха-тарского и вроде про ординалы/кардиналы (how to count past infinity). В последнем, наверно, и про гранд-отель должно быть, не помню
приложения в реальной жизни, особенно в отношении бесконечных множеств — как это можно себе представить ? теория множеств — это скорее база для других разделов математики, какая тут реальная жизнь...
Здравствуйте, Вумудщзук, Вы писали:
В>приложения в реальной жизни, особенно в отношении бесконечных множеств — как это можно себе представить ? теория множеств — это скорее база для других разделов математики, какая тут реальная жизнь...
Это же не движение ради движения. Даже если применение опосредованное (позволяет доказать там то-то или то-то или задать предел применимости другой теории, без чего не работало бы вот то-то) — это тоже дело.
В противном случае все это превращается в мартышкин труд, а такая мотивация весьма сомнительна для любого ученого.
Здравствуйте, D. Mon, Вы писали:
DM>А действительные числа качественно другие — большинство из них таят в себе бесконечно много информации, их запись/кодировка бесконечна,
А можно сказать по простому(на чайниковском уровне), что вещественные числа — это просто пошаговые процедуры деления отрезка на части и выбор одной из частей, на следующем шаге он снова делится ? На бесконечном по счету шаге появляется вещественное(трансцендентное) число.
Когда записываем вещественное число в десятичном виде. Очередной шаг — дописать очередной знак после запятой — это разделить текущий отрезок на 10 частей и выбрать одну из них.
То как вводится трансцендентная константа "e" (через 2 замечательный предел), тоже похоже на пошаговую процедуру.
Задача Ахиллес и черепаха
Тоже похожа на введение трансцендентного числа через пошаговую процедуру.
Здравствуйте, Silver_S, Вы писали:
S_S>А можно сказать по простому(на чайниковском уровне), что вещественные числа — это просто пошаговые процедуры деления отрезка на части и выбор одной из частей, на следующем шаге он снова делится ? На бесконечном по счету шаге появляется вещественное(трансцендентное) число.
Если сильно прищуриться, то можно. Бесконечная последовательность цифр и аналогичная последовательность шагов, их производящая.
Но придется отказаться от классического определения алгоритма и допустить бесконечно длинные программы/процедуры.
Множество всех вычислимых чисел является счётным множеством. https://en.wikipedia.org/wiki/Computable_number
pva>Это же не движение ради движения. Даже если применение опосредованное (позволяет доказать там то-то или то-то или задать предел применимости другой теории, без чего не работало бы вот то-то) — это тоже дело. pva>В противном случае все это превращается в мартышкин труд, а такая мотивация весьма сомнительна для любого ученого.
вовсе нет. это всё применимо к прикладным направлениям, когда нужно решить нечто конкретное: уравнения/систему и т.д. А в фундаментальных дисциплинах целью является именно познание, поиск каких-то новых сущностей, их связей с другими сущностями в т.ч из других дисциплин (что периодически случается). Что-то может вылиться в конечном итоге в прикладные направления, но они не являются целью.
и теория множеств — это именно сугубо теоретическое направление и база для других направлений.
да, блин, даже такая, казалось бы, конкретика, как поиск ответа на вопрос, бесконечно ли множество простых близнецов — какое у него прикладное значение? Да никакого, это лишь ещё один кирпичик в теорию чисел, в которой он тоже сам по себе чего-то может значить, но до какой-то применимости тут далеко. Но интересно, и именно это и движет людьми
а тот лютейший матан, на котором построена теория струн — казалось бы, физика, наука об окружающем мире — его до сих пор с реальным миром толком связать не могут, кроме каких-то очень отдельных моментов. И непохоже, что в ближайшее время такая связь появится. Т.е. практически в чистом виде самурайство: нет цели, есть только путь. И ничего, штурмуют
0;1). Для любого х из Х мы можем сопоставить n из N откинув начальный "0." и получив из несчетного бесконечного счетное. Так-то интуитивно понятно что всякие иррациональные не представимы таким образом, но у нас то счетное бесконечное.
? теория множеств — это скорее база для других разделов математики, какая тут реальная жизнь...
