набрел случайно на бесконечности (по книге "Ловкость ума") и воткнул.
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>И пока пришел только к тому что это "по определению".
Нет это по теореме доказывающейся через диагонализацию
0;1). Для любого х из Х мы можем сопоставить n из N откинув начальный "0." и получив из несчетного бесконечного счетное. Так-то интуитивно понятно что всякие иррациональные не представимы таким образом, но у нас то счетное бесконечное.
