Здравствуйте, Вумудщзук, Вы писали:
В>потому что это и есть суть теоремы кантора: мощность булеана всегда больше мощности исходного множества. При чём тут отсылка к гранд-отелю — непонятно.
Выше я несколько раз в различных вариантах описал причем здесь отсылка к гранд-отелю.
В какой момент 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). В последнем, наверно, и про гранд-отель должно быть, не помню
приложения в реальной жизни, особенно в отношении бесконечных множеств — как это можно себе представить ? теория множеств — это скорее база для других разделов математики, какая тут реальная жизнь...
? теория множеств — это скорее база для других разделов математики, какая тут реальная жизнь...
