Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 53
А вам не кажется, что понятия «больше-меньше» выраженные в конечных величинах на бесконечных множествах выглядят несколько неестественно? Ну как например говорить, что множество целых чисел в «два раза больше» множества натуральных, или множество четных натуральных в «два раза меньше» :) Ведь по факту они имеют одно и то же кардинальное число :)
Статья называется «Как вообразить несчетное множество», поэтому позволю себе такой вопрос: а вы хорошо представляете (воображаете) бесконечное бинарное дерево? Я вот не лучше, чем континуальное множество.
По мне, так дерево лучше чем ничего. Натуральный ряд можно представить (визуализировать) в виде ряда «с одной степенью свободы» (начинается сверху и растет вниз). Дерево позволяет использовать аналогичную же фразу (начинается сверху и выросло вниз) для континуального множества. Хоть какая-то конкретика.
Ну, континуальный ряд можно представить себе как отрезок. Как по мне неплохое представление, которое, например, в отличии от дерева указывает на непрерывность множества (конечно, если вдуматься, то такое дерево тоже указывает, но отрезок очевиднее указывает).
Правда, оба эти представления хорошо подходят для конечных, счетных и континуальных множеств, а все остальные — увы, за бортом. Например, мне лично всегда было интересно как-то представить несчетное неконтинуальное бесконечное подмножество континуума (дополнив ZFC соответствующим образом).
Правда, оба эти представления хорошо подходят для конечных, счетных и континуальных множеств, а все остальные — увы, за бортом. Например, мне лично всегда было интересно как-то представить несчетное неконтинуальное бесконечное подмножество континуума (дополнив ZFC соответствующим образом).
Отрезок не дает представления о структуре и связи между несчетным множеством и счетным. Дерево же в одной «фигуре» сочетает счетное число уровней и несчетное число путей.
>Правда, оба эти представления хорошо подходят для конечных, счетных и континуальных множеств, а все остальные — увы, за бортом.
Сразу три :) уже не мало.
Если же говорить о любопытстве, то кроме множеств с дробным кардинальным числом, неплохо было бы иметь средства для представления множеств с кардинальным числом больше единицы.
>Правда, оба эти представления хорошо подходят для конечных, счетных и континуальных множеств, а все остальные — увы, за бортом.
Сразу три :) уже не мало.
Если же говорить о любопытстве, то кроме множеств с дробным кардинальным числом, неплохо было бы иметь средства для представления множеств с кардинальным числом больше единицы.
Гиперконтинуум тоже представить несложно — как подмножества отрезка, или как множество всех функций на отрезке.
Вот с промежуточной мощностью плохо: у нас нет интуитивного способа доказать, что мощности двух бесконечных множеств различны (то, что мощности одинаковы — доказываем, строя биекцию между ними).
Кстати, дерево непрерывным не является. У него топология канторова множества: например, дерево можно разделить на два поддерева, каждое из которых будет открытым множеством. С отрезком такое не пройдёт.
Вот с промежуточной мощностью плохо: у нас нет интуитивного способа доказать, что мощности двух бесконечных множеств различны (то, что мощности одинаковы — доказываем, строя биекцию между ними).
Кстати, дерево непрерывным не является. У него топология канторова множества: например, дерево можно разделить на два поддерева, каждое из которых будет открытым множеством. С отрезком такое не пройдёт.
Кстати, дерево непрерывным не является. У него топология канторова множества: например, дерево можно разделить на два поддерева, каждое из которых будет открытым множеством. С отрезком такое не пройдёт.Хм, а какую метрику вы использовали, чтобы получить в этом дереве такую топологию? Задавать топологию без метрики — дело нехитрое, ничего не мешает объявить абсолютно все подмножества открытыми :)
Обычная метрика. Если два пути a1,a2,a3,...,an,… и b1,b2,...bn,… в первый раз расходятся в позиции m, то расстояние между ними равно 2^(-m). Та же метрика, что используется в 2-адических числах (только цифры записаны в обратном порядке). Получается топология бесконечного произведения {0,1}^N
Но метрика для топологии не нужна — надо просто описать открытые множества. Например, базу топологии — набор подмножеств, которые все открыты, и любое открытое множество из топологии является объединением каких-то множеств из базы.
Для топологии дерева база состоит из всех его поддеревьев.
Но метрика для топологии не нужна — надо просто описать открытые множества. Например, базу топологии — набор подмножеств, которые все открыты, и любое открытое множество из топологии является объединением каких-то множеств из базы.
Для топологии дерева база состоит из всех его поддеревьев.
Только у вас метрика не на дереве, а на путях в дереве получается.
Так и у автора континуум образовывался путями в дереве, а не вершинами. И канторово множество тоже суть пути, если его в виде дерева представить…
Mrrl говорил о топологии на самом дереве.
И канторово множество состоит все-таки из вещественных чисел, а не путей.
(понятно, что его можно биективно отобразить в множество путей, да и вообще в любое континуальное множество)
И канторово множество состоит все-таки из вещественных чисел, а не путей.
(понятно, что его можно биективно отобразить в множество путей, да и вообще в любое континуальное множество)
Я говорил о топологии на путях — на несчётном множестве, представленном в виде дерева. Можно, конечно, рассмотреть и топологию на множестве вершин, но там я не ожидаю ничего, кроме дискретной топологии.
Кстати, дерево непрерывным не является. У него топология ...
(еще наверное лучше сказать «связным» вместо «непрерывным»)
На самом дереве, как на счетном множестве, можно ввести много интересных топологий. Например, сказать, что открытыми являются множества, состоящие из вершин открытого множества путей (вроде бы это то же самое, что и отождествить вершины с двоично-рациональными числами и взять индуцированную топологию).
(вроде бы это то же самое, что и отождествить вершины с двоично-рациональными числами и взять индуцированную топологию).
Скорее, с вершинами бесконечномерного куба (находящимися на конечном расстоянии от выделенной вершины). Вопрос здесь в том, существуют ли открытые множества, содержащие корень и какие-то точки только из одного поддерева. В случае двоично-рациональных чисел — нет: открытое множество, содержащее 1/2, неизбежно захватит точки и слева, и справа от него. На дереве такую топологию описать весьма сложно. В случае сопоставления с вершинами гиперкуба эффект ещё интереснее: множество, состоящее из корня и правого поддерева будет открытым, а из корня и левого поддерева — нет. А вот если бы оба этих множества были открытыми, то корень был бы изолированной точкой. И любая другая вершина — тоже :(
А какая у вас топология на бесконечномерном кубе (да и как выглядит сопоставление?)
И с двоично-рациональными, и с путями я погорячился — ни то, ни другое не задает топологию. Сопоставление с двоично-рациональными вообще непонятно как сделать взаимно-однозначно, а если взять открытые множества путей как предбазу, то получится дискретная топология.
Вообще нетривиальную хаусдорфову топологию, инвариантную относительно перехода к поддереву, придумать можно. Вот метрику уже не уверен.
И с двоично-рациональными, и с путями я погорячился — ни то, ни другое не задает топологию. Сопоставление с двоично-рациональными вообще непонятно как сделать взаимно-однозначно, а если взять открытые множества путей как предбазу, то получится дискретная топология.
Вообще нетривиальную хаусдорфову топологию, инвариантную относительно перехода к поддереву, придумать можно. Вот метрику уже не уверен.
Топология на вершинах бесконечномерного куба — та же топология бесконечного произведения: базу составляют грани конечной коразмерности (т.е. подмножества, заданные конечным числом уравнений x_k=c_k).
Сопоставление вершин дерева двоично-рациональным числам интервала (0,1):
корень: 1/2
его дети: 1/4 и 3/4
дети вершины m/2^k (m — нечётно): (2*m-1)/2^(k+1) и (2*m+1)/2^(k+1)
Сопоставление взаимно-однозначно, и топологию интервала перенести на дерево, в принципе, можно. Но это будет некрасиво.
Сопоставление вершин дерева вершинам куба — через двоично-рациональные числа. В вершину (0,0,0,...) не отображается никто, в остальные вершины с конечным числом единиц — какие-то вершины дерева. Потомками вершины (*,1,0,0,0...) где * — произвольный набор координат будут (*,0,1,0,0,0...) и (*,1,1,0,0,0...) Элементы базы соответствующей топологии на дереве — произвольная вершина, объединённая со своим правым поддеревом, и левое поддерево произвольной вершины.
Сопоставление вершин дерева двоично-рациональным числам интервала (0,1):
корень: 1/2
его дети: 1/4 и 3/4
дети вершины m/2^k (m — нечётно): (2*m-1)/2^(k+1) и (2*m+1)/2^(k+1)
Сопоставление взаимно-однозначно, и топологию интервала перенести на дерево, в принципе, можно. Но это будет некрасиво.
Сопоставление вершин дерева вершинам куба — через двоично-рациональные числа. В вершину (0,0,0,...) не отображается никто, в остальные вершины с конечным числом единиц — какие-то вершины дерева. Потомками вершины (*,1,0,0,0...) где * — произвольный набор координат будут (*,0,1,0,0,0...) и (*,1,1,0,0,0...) Элементы базы соответствующей топологии на дереве — произвольная вершина, объединённая со своим правым поддеревом, и левое поддерево произвольной вершины.
Сопоставление с двоично-рациональными вообще непонятно как сделать взаимно-однозначноДерево Штерна-Броко не подходит?
Оно рациональные числа распределяет, а не двоично-рациональные.
Впрочем, я неточно выразился — «непонятно, как красиво сделать». Ибо какая-то биекция между счетными множествами вершин дерева двоично-рациональных чисел очевидно есть:)
Впрочем, я неточно выразился — «непонятно, как красиво сделать». Ибо какая-то биекция между счетными множествами вершин дерева двоично-рациональных чисел очевидно есть:)
Да, понял. Забавно получается — исходно-то дерево строилось так, чтобы изобразить отрезок — но в него добавили несколько лишних точек — и евклидова метрика с него сразу же слетела. То есть канторово множество получилось не удалением частей отрезка — а добавлением к отрезку счетного множества точек…
Ничего себе, спасибо. Впечатлен.
Единственное, мне видится что «псевдопарадокса» нет — я не очень понял как вершины «легко» посчитать «сверху вниз», если «вниз» не ограничено (в дереве). Один путь — одно число. Одна вершина — это один знак числа, и для конечной вершины — последний, и тут похоже нельзя делать предельный переход, так как для бесконечной последовательности нет конечного знака.
Единственное, мне видится что «псевдопарадокса» нет — я не очень понял как вершины «легко» посчитать «сверху вниз», если «вниз» не ограничено (в дереве). Один путь — одно число. Одна вершина — это один знак числа, и для конечной вершины — последний, и тут похоже нельзя делать предельный переход, так как для бесконечной последовательности нет конечного знака.
Похоже со мной кто-то не согласен. Хотелось бы всё-таки узнать, какой способ пересчитать все вершины. Потому что если вершин 2^N-1, то их при N к бесконечности, насколько я понимаю, несчетно.
Вершины можно считать справа-налево сверху вниз. Аналогично рациональным дробям, которых счетное количество. Если непонятно вечером рисунком подкреплю.
Каждая вершина в дереве имеет конечную глубину. И их действительно можно занумерновать сверху вниз: корень получает номер 1, его потомки — 2 и 3, вершины следующего ряда — 4, 5, 6, 7 и т.д. У каждой вершины дерева появляется номер — натуральное число. В самом деле, попробуйте предъявить вершину, которая номера не получила. Таких нет: даже в бесконечном пути от корня нет ни одной вершины, находящейся на бесконечной глубине (как в натуральном ряду нет ни одного бесконечного числа). Поэтому, получается, что вершины образуют счётное множество.
А теперь утренняя разминка: n-мерное вещественное пространство заталкиваем в [0;1)
А чего его заталкивать? Сначала пространство сжимаем в куб, а потом рисуем n-мерную кривую Пеано.
Давайте я вам n-мерный куб со стороной, стремящейся к 1 затолкаю, т.е. каждая координата лежит на полуинтервале [0;1). (n-мерное пространство, конечно, тоже можно, но лишние доказательства)
Каждая точка куба имеет координаты (r_1, r_2, …, r_n), ей ставим во взаимооднозначное соответствие число 0,<первая цифра после запятой у r_1>…<первая цифра после запятой у r_n><вторая цифра после запятой у r_1>…
Каждая точка куба имеет координаты (r_1, r_2, …, r_n), ей ставим во взаимооднозначное соответствие число 0,<первая цифра после запятой у r_1>…<первая цифра после запятой у r_n><вторая цифра после запятой у r_1>…
Это у вас не совсем взаимно однозначное отображение получилось. Точнее, совсем не. Вместо цифр надо оперировать блоками, где блок — это произвольная цифра, кроме девятки, после которой идет конечное число девяток. Начальный ноль (который до десятичной запятой) следует включить в первый блок.
Альтернативный вариант — использовать систему счисления, где «проблемы девяток» не возникает, например уравновешенную троичную.
Альтернативный вариант — использовать систему счисления, где «проблемы девяток» не возникает, например уравновешенную троичную.
Простите, не совсем понял в чем проблема. Можете привести пример точки, которой будет соответствовать количество действительных чисел отрезка отличное от 1? Или пример числа которому соответствует отличное от 1 количество точек пространства?
Возьмем случай n=2.
Точке на отрезке (0,515959...) будет соответствовать точка квадрата — (0,5555...; 0,1999...), которая является некорректной записью точки (0,5555...; 0,2000). Но последней соответствует точка отрезка (0,525050...).
Таким образом, мы или получаем «дырку» на месте точки (0,515959...) — или же две точки сливаются в одну, в зависимости от того, разрешены или запрещены бесконечные последовательности девяток в конце числа.
Точке на отрезке (0,515959...) будет соответствовать точка квадрата — (0,5555...; 0,1999...), которая является некорректной записью точки (0,5555...; 0,2000). Но последней соответствует точка отрезка (0,525050...).
Таким образом, мы или получаем «дырку» на месте точки (0,515959...) — или же две точки сливаются в одну, в зависимости от того, разрешены или запрещены бесконечные последовательности девяток в конце числа.
А взаимно однозначного соответствия и не требовалось. Когда мы заталкиваем вещи в чемодан, нам не требуется заполнить весь его объём, не так ли? В отрезке останутся дырки, но две точки пространства в одну точку отрезка не попадут (если требовать, чтобы десятично-рациональные координаты записывались с бесконечным хвостом нулей, а не девяток).
В уравновешенной троичной системе проблема девяток тоже никуда не делась: число 1/2 (точнее, p/pm) можно записать как и как 0.ppppp..., и как p.mmmmm…
А чем блоки помогут построить взаимно-однозначное соответствие — пока непонятно, надо думать. Первое, что приходит в голову — напрямую применить теорему Кантора-Бернштейна: отображение куба в отрезок у нас уже есть, для отображения отрезка в куб преобразуем двоичную запись точки на отрезке (например, без хвоста единиц) в троичную запись координат точки куба. В троичной системе бесконечный хвост единиц — не проблема, а двоек в получившихся координатах не будет.
UPD: прочитал новый комментарий — действительно, так усложнять незачем, отрезок можно пустить по ребру куба.
В уравновешенной троичной системе проблема девяток тоже никуда не делась: число 1/2 (точнее, p/pm) можно записать как и как 0.ppppp..., и как p.mmmmm…
А чем блоки помогут построить взаимно-однозначное соответствие — пока непонятно, надо думать. Первое, что приходит в голову — напрямую применить теорему Кантора-Бернштейна: отображение куба в отрезок у нас уже есть, для отображения отрезка в куб преобразуем двоичную запись точки на отрезке (например, без хвоста единиц) в троичную запись координат точки куба. В троичной системе бесконечный хвост единиц — не проблема, а двоек в получившихся координатах не будет.
UPD: прочитал новый комментарий — действительно, так усложнять незачем, отрезок можно пустить по ребру куба.
Ну, мне как-то не подумалось, что под словом «заталкиваем» скрывается инъекция, а не биекция :)
И с уравновешенной троичной системой я ошибся, вы правы.
А с блоками все просто. Любое число можно разбить на блоки единственным способом — и любая последовательность блоков даст в результате корректное число, без девяток в конце. Только вот с первым нулем я опять пролетел — не в любой точке отрезка второй блок будет с нуля начинаться.
Тут можно или использовать двоичную систему счисления — или отображать отрезок [0; 0,9) в прямоугольник [0; 0,9) x [0; 0,9), вместо единичных (чтобы первая цифра не была девяткой).
И с уравновешенной троичной системой я ошибся, вы правы.
А с блоками все просто. Любое число можно разбить на блоки единственным способом — и любая последовательность блоков даст в результате корректное число, без девяток в конце. Только вот с первым нулем я опять пролетел — не в любой точке отрезка второй блок будет с нуля начинаться.
Тут можно или использовать двоичную систему счисления — или отображать отрезок [0; 0,9) в прямоугольник [0; 0,9) x [0; 0,9), вместо единичных (чтобы первая цифра не была девяткой).
А я думал, что несчетное множество легче всего представить, просто посмотрев на небо в безлунную ночь при ясном небе и вдали от огней. А также подумать: «зачем я? зачем мы? зачем это все?» :)
Увы. На небе вы увидите конечное множество.
Ломоносов вот увидел:
Открылась бездна звезд полна;
Звездам числа нет, бездне дна.
Открылась бездна звезд полна;
Звездам числа нет, бездне дна.
Никаких увы. Во-первых, конечности человек на небе не видит. Во-вторых, я не говорил о конечности, но о несчетности, что и входит в название этого поста. В-третьих, я говорил не о самом небе, а о представлении человека. Представлении — что опять же входит в название поста. В четвертых, не надо спорить с дядей (я про Ломоносова) ;)
«Количество путей максимальной длинны, исходящих из корня двоичного дерева бесконечной высоты несчетно.» — а давайте попробуем считать «несчетные» таким образом: точно так же, как мы считаем узлы дерева, но будем пропускать те вершины, через которые проходит хотя бы один посчитанный нами путь. И кроме того, будем считать вполне конкретные пути — те, которые ведут строго влево от данной вершины и до самого бесконечного низа, а может, даже еще ниже (имеют одни нолики).
Начало последовательности путей будет такое:
1) 0
2) 0.1(0)
3) 0.01(0)
4) 0.11(0)
и так далее.
То есть, мы считаем так же, как и вершины, при этом считаем только те вершины, на которых происходит преломление пути справа налево (поледняя цифра в числе всегда единица, не считая бесконечного цикла нулей в конце).
Похоже, что все прекрасно считается.
Итого: тема несчетного множества в статье не раскрыта. ;)
Итого-итого: звездное небо для воображения несчетного множества все-таки гораздо лучше. В-)
Начало последовательности путей будет такое:
1) 0
2) 0.1(0)
3) 0.01(0)
4) 0.11(0)
и так далее.
То есть, мы считаем так же, как и вершины, при этом считаем только те вершины, на которых происходит преломление пути справа налево (поледняя цифра в числе всегда единица, не считая бесконечного цикла нулей в конце).
Похоже, что все прекрасно считается.
Итого: тема несчетного множества в статье не раскрыта. ;)
Итого-итого: звездное небо для воображения несчетного множества все-таки гораздо лучше. В-)
Вы посчитали не все пути.
Поконкретней можно?
Путь 0.(01) не подсчитан. Как и 0.(0101101).
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как вообразить несчетное множество?