Falcão (falcao) wrote in ru_math,
Falcão
falcao
ru_math

Categories:

К парадоксу Банаха -- Тарского

Под "катом" -- обсуждение известного парадокса Банаха -- Тарского, а также схема его доказательства.


Не так давно где-то вспоминали этот старый добрый парадокс. Собственно, парадоксального в нём ничего нет: статус парадокса -- это лишь ставшая привычной "этикетка". Само утверждение является очень красивым математическим результатом. Удивительным там является, на мой взгляд, не нарушение "законов сохранения", а тот факт, что при конечном разбиении удаётся фигуру одной формы превратить в фигуру совершенно другой формы, например, шар в куб (пусть даже объёмы их были и одинаковы). Я припоминаю даже какие-то олимпиадные задачи, связанные с разрезанием. Там разрезание производится на "правильные" части, поэтому не удивительно, что не удаётся превратить круг в квадрат, "состыковав" между собой кривые куски.

Мне кажется, неплохо было бы освежить в голове доказательство (хотя бы схематично), чтобы было ясно, откуда происходит удивительный эффект "превращения форм". Часто при упоминании Парадокса говорят лишь о его частном случае, когда из одного арбуза при помощи умелого оперирования ножом удаётся собрать два таких же. Но наиболее общая формулировка может быть дана следующим образом.

Теорема. Любые два ограниченных подмножества в R^3, каждое из которых содержит шар некоторого (положительного) радиуса, эквиваленты при конечном разбиении.

Под эту формулировку подходит и превращение одного арбуза в два, и превращение куба в шар, и многое другое.

Для начала следовало бы несколько уточнить формулировку, заодно дав одно более общее определение. Пусть даны два подмножества А и B в R^3. Говорят, что они эквивалентны при конечном разбиении, если при некотором n можно представить их в виде дизъюнктных объединений вида A=\cup A_i и B=\cup B_i соответственно, где A_i конгруэнтно B_i (i=1,...,n). Говоря о конгруэнтности фигур, можно ограничиться только вращениями R^3. Проверка транзитивности определённого выше отношения не составляет труда.

Несколько обобщая ситуацию, потребуем то же самое, за исключением условия B=\cup B_i, заменяя его на более слабое условие "B содержит \cup B_i". Теперь мы имеем вместо эквивалентности отношение частичного порядка, заключающееся попросту говоря в том, что A можно разрезать на конечное число кусков, а сами эти куски так переместить, что их удастся расположить в B без наложений. За неимением лучшего термина и за отсутствием приемлемой символики, будем выражать такое свойство в форме "A не больше B".

Надо заметить, что если A -- "большая", а B -- "маленькая" фигура (в смысле объёма), то утверждение о том, что A может оказаться не больше B, выглядит не так уж и удивительно. В самом деле, мы можем, грубо говоря, "перемолоть" A в такую "труху", что полученные части удастся как-то впихнуть в шар небольшого объёма без наложений. По крайней мере, это выглядит намного менее удивительным, нежели точная упаковка, превращающая куб в шар.

За счёт чего же достигается "волшебный эффект"? Оказывается, всего лишь за счёт теоремы Кантора -- Бернштейна. Последняя, если выявить суть, оказывается утверждением вполне "дискретным", "конструктивным", несмотря на то, что речь может идти об "очень больших" множествах. Теорема гласит, что если имеется некоторое инъективное отображение множества A во множество B, а также некоторая инъекция из B в A, то можно построить биекцию A на B. Оборот "можно построить" здесь вовсе не случаен, так как это утверждение принципиально отличается от существенно неконструктивной теоремы, утверждающей, что любые два множества сравнимы по мощности. Более того, биекция действительно строится, причём строится из "обрезков" двух имеющихся инъекций. Это означает, что если два элемента a \in A и b \in B соответствуют друг другу при биекции, то либо $a$ переходил в $b$, либо $b$ переходил в $a$ при одной из инъекций.

Такая несколько усиленная форма теоремы Кантора -- Бернштейна сразу же доказывает, что из условий "A не больше B" и "B не больше A" мгновенно вытекает, что A и B эквиваленты при конечном разбиении. То есть едва ли не самая удивительная особенность Парадокса (точное совпадение форм) вытекает не из аксиомы выбора, а из самой что ни на есть "конструктивной" теоремы!

Что же остаётся доказать? Только тот факт, что любое ограниченное множество можно "смолоть" и поместить кусочки без наложений в шар заданного радиуса r. Ясно, что ограниченное множество можно разрезать сначала вполне традиционным способом на куски малого размера, каждый из который помещается в шар радиусом r. После чего остаётся установить, что конечное число шаров радиусом r при "перемалывании" умещаются в одном таком шаре. Индукция по числу шаров сводит это утверждение к случаю, когда "перемолоть" и упаковать надо лишь два шара. Каждый из шаров можно расслоить на сферы, и задача фактически сводится к задаче "удвоения сферы". Соответствующее утверждение было доказано Хаусдорфом сравнительно задолго до Парадокса. Формулировка теоремы Хаусдорфа такова: сферу за вычетом из неё счётного множества точек можно представить в виде дизъюнктного объединения трёх попарно конгруэнтных множеств X, Y, Z так, что объединение X и Y будет конгруэнтно каждому из них.

Фактически, задача теперь свелась к "удвоению" сферы, что в свою очередь можно свести к эффекту удвоения на некоторых дискретных группах. Последняя вещь -- совершенно явная конструкция, которую можно пронаблюдать, что называется, воочию. Что понимается под "удвоением группы"? Речь идёт о представлении группы в виде дизъюнктного объединения конечного числа подмножеств, которые после "перемещений", т.е. умножения справа на фиксированные элементы группы, покроют группу в два слоя. Можно потребовать более слабого условия, чтобы перемещённые куски разбиения покрыли группу не менее чем в два слоя (т.е. каждый элемент "размножился", но не обязательно ровно в двух экземплярах). Несложные соображения вполне дискретного характера показывают, что одно другому эквивалентно.

Рассмотрим теперь граф Кэли свободной группы, который представляет собой регулярное дерево. Для простоты будем считать, что наша свободная группа имеет два образующих. Эффект "удвоения" означает возможность организовать на графе Кэли некое подобие "финансовой пирамиды", выгодной для всех участников. Пусть в каждой вершине графа сидит персонаж. Предположим, что каждый платит доллар одному из соседей. А именно, персонаж из вершины g платит первому, кто находится на пути из вершины g в "столицу", т.е. в вершину, соответствующую единичному элементу. (При этом можно считать, что "столичный" персонаж заплатил доллар сам себе.) Что при этом произойдёт? Доход "столичного мэра" составит 4 доллара. Каждый из остальных отдаст один доллар по направлению к "столице", но зато получит 3 доллара с "периферии", и его чистый доход составит 2 доллара. (Для справки: группы, на которых возможно реализовать подобный эффект, называются неаменабельными.)

Как связана построенная "пирамида" и "удвоение"? Дело в том, что "хозяин" вершины g передал один доллар "хозяину" вершины ga, где a -- образующий элемент или ему обратный (или a=1 в случае "мэра столицы"). Тем самым можно разбить все элементы свободной группы на 5 частей, в зависимости от того, чему равно a (одна из частей будет состоять только из единицы). Тогда при умножении справа на a той части, которая соответствовала значению a, мы получим покрытие группы как минимум в три слоя.

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

Если группа G сама не свободна, но содержит свободную подгруппу H, то разбиение на левые смежные классы по H, являющиеся фактически копиями H, позволяют организовать структуру удвоения на G. В частности, можно проделать это с группой G=Z_2*Z_3 -- свободным произведением циклических групп порядка 2 и 3. Это хорошо известная группа PSL(2,Z). На самом деле, её граф Кэли несложно нарисовать непосредственно, и можно построить некое подобие "финансовой пирамиды" в явной форме, не обращаясь к случаю свободной группы.

Как представить себе граф Кэли группы G? За неимением возможности делать в тексте рисунки, я буду использовать словесное описание. Граф будет планарным, и его можно легко изобразить на плоскости (это рекомендуется сделать тем, у кого под рукой есть бумага и ручка). Прежде всего, обозначим образующие элементы группы G через s,t, где s^2=1, t^3=1. Для начала представим себе изображённое на плоскости регулярное дерево степени 3. Затем заменим каждую из его вершин на правильный треугольник, из вершин которого будет исходить по ребру. Теперь надо расставить метки на рёбрах. Прежде всего, ориентируем стороны каждого из треугольников по часовой стрелке и снабдим эти рёбра графа меткой t, что будет соответствовать соотношению t^3=1. Далее, поскольку s есть инволюция, то для неё нет смысла рисовать два ребра. Поэтому все остальные рёбра графа (соединяющие треугольники между собой) мы оставим неориентированными и снабдим меткой s. Это будет соответствовать тому, что s^2=1.

Итак, граф Кэли группы G построен. (Можно было бы ещё указать вершину для единичного элемента, но нам это не нужно.) Сейчас мы расставим метки вершин графа, относя их к одному из трёх типов: x,y,z. В каждом треугольнике должен будет присутствовать каждый из типов, причём символы x,y,z должны идти также по часовой стрелке. Проделаем это с одним из треугольников. Далее будем придерживаться такого правила. Если непомеченная вершина графа соединена с вершиной типа x или y, то мы ей в обязательном порядке даём метку z. Если же непомеченная вершина соединена с вершиной типа z, то мы можем приписать ей любую из меток -- x или y. (Для определённости можно в этом случае всегда брать метку x.)

Описанное правило позволяет разметить все вершины графа. На первом шаге у нас было три помеченные вершины. С использованием наших правил, мы далее пометим ещё три (те, которые соединены с уже помеченными). Новые три вершины принадлежат разным треугольникам. Зная метку одной из вершин, мы однозначно восстанавливаем (см. предыдущий абзац) метки двух оставшихся вершин треугольника. Продвигаясь от центра на периферию, мы разметим весь граф, получая симпатичную картинку.

Теперь можно разбить все вершины графа (т.е. элементы группы) на три класса X,Y,Z в соответствии с их метками. Что произойдёт, если элемент группы умножить справа на t? Ясно, что множества X,Y,Z циклически перейдут друг в друга. Далее, что произойдёт с элементами объединения множеств X и Y при умножении справа на s? Легко видеть, что они перейдут в элементы множества Z, причём будет иметь место биекция. Этим мы подготовили почву для "удвоения сферы" по Хаусдорфу.

Чтобы завершить рассуждение, проведём через центр сферы две прямые, образующие угол \theta. Пусть s -- поворот на 180 градусов вокруг одной из осей, а t -- поворот на 120 градусов вокруг другой. Ясно, что s^2=1, t^3=1. В общем случае между s, t могут существовать другие соотношения, не сводимые к двум выписанным. Но несложный анализ показывает, что при этом косинус или синус угла \theta станет корнем некоторого алгебраического уравнения с целыми коэффициентами. Выбирая \theta "очень плохим", мы можем этого избежать, и тогда элементы s, t будут порождать группу G=Z_2*Z_3. Теперь из сферы надо предварительно удалить (счётное) множество F всех точек, неподвижных относительно какого-либо вращения из G. Всё остальное разбивается на одинаково устроенные G-орбиты. Каждая из орбит устроена фактически как сама G, но для использования этого факта необходима фиксация одной точки в каждой из орбит. Эта "акция" напоминает построение неизмеримого множества, когда фиксируется представитель каждого смежного класса группы R по подгруппе Q. Вот единственное место, где используется аксиома выбора в доказательстве Парадокса. Вопреки распространённому мнению, что это чуть ли не ключевое средство, мы видим, что её роль здесь довольно скромна, причём выбирать приходится из не слишком "дикого" семейства множеств. (По крайней мере, это выглядит намного более приемлемым, чем использование аксиомы выбора для полного упорядочения континуума.)

Итак, с разбиением сферы без счётного множества точек на орбиты, устроенные так же, как дискретная группа G, мы получаем (c учётом сказанного выше) разбиение сферы без множества F на три части X,Y,Z. Это и даёт конструкцию "удвоения сферы", т.е. теорему Хаусдорфа. В самом деле, вращение t даст нам попарную конгруэнтность X,Y,Z, а вращение s -- конгруэнтность объединения X и Y множеству Z.

Разобьём теперь шар без центра на множества, которые сохранят свои обозначения F,X,Y,Z (все точки радиуса попадают туда, куда попал его конец). Заметим, что ввиду счётности F можно всегда найти вращение пространства, отображающее F в объединение X \cup Y \cup Z. Туда же пристроим "бедного родственника" -- центр шара. В итоге шар мы разрежем на 5 частей и упакуем в шести дизъюнктных экзеплярах, конгруэнтных X. У нас есть второй шар, и с ним поступим аналогично. Теперь два шара упакованы у нас в 12 копий множества X. С учётом попарной конгруэнтности X,Y,Z и конгруэнтности (некоторого) дизъюнктного объединения двух таких множеств одному из них, мы будем постепенно уменьшать количество экземпляров по принципу "два в одном", упаковывая всё при конечном разбиении в один такой экземпляр. Ввиду того, что он был частью шара, мы упаковали при конечном разбиении два шара в один и тем самым завершили доказательство теоремы Банаха -- Тарского.
Subscribe

  • Help

    Дорогие коллеги, помогите, если можете, получить доступ (нужно довольно срочно) к книге М.С Пинскера "Информация и информационная устойчивость…

  • Топологический вопрос о проективном пространстве

    Можно ли на каждой прямой трёхмерного проективного пространства выбрать точку, чтобы точка от прямой зависела непрерывно? При желании трёхмерное…

  • Дело Лузина

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 11 comments

  • Help

    Дорогие коллеги, помогите, если можете, получить доступ (нужно довольно срочно) к книге М.С Пинскера "Информация и информационная устойчивость…

  • Топологический вопрос о проективном пространстве

    Можно ли на каждой прямой трёхмерного проективного пространства выбрать точку, чтобы точка от прямой зависела непрерывно? При желании трёхмерное…

  • Дело Лузина