Виленкин Рассказы о множествах. Рассказы о множествах 3е издание
 Скачать 9.06 Mb.
|
|
— Уверены ли вы, что этот список полон? — спросил я директо- ра. — Не пропущен ли какой-нибудь вариант? — Не знаю, — ответил он. — Вариантов в списке бесконечно мно- го, и я не понимаю, как проверить, нет ли еще какого-нибудь вари- анта. И тут у меня блеснула идея (впрочем, быть может, я несколь- ко преувеличиваю свои способности, просто беседы с профессором Тарантогой о бесконечных множествах не прошли бесследно). — Могу ручаться, что список неполон. Я берусь указать вариант, который наверняка пропущен. — С тем, что список неполон, я еще соглашусь. А вот пропущен- ного варианта указать не удастся — ведь здесь уже бесконечно много вариантов. Мы заключили пари. Чтобы выиграть его, я предложил прибить каждый вариант на дверь того номера, которому он соответствовал (если читатель помнит, вариантов было составлено именно столь- ко, сколько было номеров в гостинице). А потом я поступил очень просто. Подойдя к двери первого номера, я увидел, что соответ- ствующий вариант начинается с цифры 0. Немедленно в блокноте появилась цифра 1; это и была первая цифра варианта, который мне хотелось составить. Когда я подошел к двери второго номера, то первая цифра соот- ветствующего варианта меня не интересовала, ведь первая цифра моего варианта была уже написана. Поэтому все внимание было обращено на вторую цифру. Увидев, что эта цифра 1, я записал в своем блокноте цифру 0. Точно так же, обнаружив, что третья цифра варианта, прибитого к двери третьего номера, тоже 1, я за- писал в блокноте цифру 0. Вообще, если я обнаруживал, что n-я цифра n-го варианта есть 0, то писал в своем блокноте на n-м ме- сте цифру 1, если же n-я цифра n-го варианта была 1, то я писал у себя 0. Когда я обошел все номера гостиницы 1 , то в блокноте оказалась записанной последовательность нулей и единиц. Войдя в кабинет директора, я сказал: — Вот, полюбуйтесь на пропущенный вариант. 1 Гм, гм, сколько же времени он затратил? 78 Глава II. В мире чудес бесконечного — А откуда известно, что он пропущен? — Он не может быть первым, так как отличается от него первой цифрой; не может быть вторым, так как отличается от него второй цифрой; третьим, так как отличается от него третьей цифрой; и во- обще n-м, так как отличается от него n-й цифрой. Пари было выиграно, и я получил вечное право бесплатного про- живания в этой гостинице. Но одновременно стало ясно, что какое бы счетное множество вариантов ни взять, всегда найдется вариант, не вошедший в это мно- жество (эти варианты всегда можно развесить по дверям номеров). А это и значит, что множество всех вариантов заполнения гости- ницы несчетно, задача, поставленная перед директором, оказалась невыполнимой. Было решено дать об этом телеграмму. Надо сказать, что и те- леграф в необыкновенной гостинице был тоже необычным, он пе- редавал телеграммы, состоящие не из конечного, а из бесконечного (точнее говоря, счетного) множества точек и тире. Например, они имели такой вид: — · — · — — — · и т. д. Я сразу сообразил, что и множество таких телеграмм тоже несчет- но, ведь вместо точек и тире можно ставить нули и единицы, а тогда не будет никакой разницы между телеграммами со счетным множе- ством знаков и множеством всех вариантов заполнения гостиницы. Отправив телеграмму, я тепло попрощался с директором гости- ницы и полетел в галактику РЩ-8067, где должен был произвести астрографическую съемку... Несчетность континуума Теперь уже несложно доказать, что множество всех точек на пря- мой линии несчетно. Вместо этого множества можно говорить о мно- жестве всех действительных чисел, так как каждой точке прямой соответствует действительное число и обратно. Каждое действительное число можно записать в виде бесконеч- ной десятичной дроби вида a, α 1 α 2 α 3 . . . α n Несчетность континуума 79 Некоторые из них имеют даже по две записи, например: 0,500000. . . и 0,49999999. . . — это одно и то же число. Для определенности будем пользоваться записью с нулями. Предположим, что нам удалось каким-то образом перенумеро- вать все действительные числа. Чтобы доказать, что это предполо- жение неверно, достаточно построить хоть одно незанумерованное число. Следуя примеру Йона Тихого, поступим следующим обра- зом. Сначала напишем нуль и поставим после него запятую. Потом возьмем число, получившее первый номер, и посмотрим на его пер- вый десятичный знак после запятой (то есть на число десятых). Если эта цифра отлична от 1, то в числе, которое мы пишем, по- ставим после запятой 1, а если эта цифра равна 1, то поставим после запятой 2. Затем перейдем к числу, получившему второй номер, и посмотрим на его вторую цифру после запятой. Снова, если эта цифра отлична от единицы, то в числе, которое мы пишем, поста- вим на месте сотых цифру 1, если же эта цифра является единицей, то поставим цифру 2. Точно так же будем действовать и дальше, каждый раз обращая внимание лишь на n-ю цифру числа, полу- чившего n-й номер. В результате мы выпишем некоторое число, на- пример: N = 0,1121211. . . Ясно, что это число не получило никакого номера: в первом деся- тичном знаке оно отличается от числа с номером 1, во втором — от числа с номером 2, . . . , в n-м — от числа с номером n и т. д. (см. с. 13). Чтобы читателю стало яснее, как выписывается число, не полу- чившее номера, предположим, что при выбранной нумерации первые пять чисел имеют следующий вид: 4,27364. . . −1,31226. . . 7,95471. . . 0,62419. . . 8,56280. . . Тогда число, не получившее номера, будет начинаться со следующих десятичных знаков: 0,12121. . . Разумеется, не только это, но и многие другие числа не получили номеров (мы могли бы заменять все цифры, кроме 2, на 2, а цифру 2 80 Глава II. В мире чудес бесконечного на 7 или выбрать еще какое-нибудь правило). Но нам достаточно су- ществования одного-единственного числа, не получившего номера, чтобы опровергнуть гипотезу о возможности нумерации всех дей- ствительных чисел. Существование трансцендентных чисел Мы говорили, что алгебраическими числами называют числа, яв- ляющиеся корнями уравнений a 0 x n + a 1 x n−1 + . . . + a n = 0 с целыми коэффициентами. Числа же, не являющиеся корнями та- ких уравнений, называют трансцендентными. В течение долгого времени математики имели дело лишь с ал- гебраическими числами, такими, как 7 15 , 8 √ 10, √ 2 + 3 √ 3 и т. д. Лишь ценой больших усилий французскому математику Лиувиллю уда- лось найти в 1844 году несколько трансцендентных чисел. А до- казательство трансцендентности числа π, проведенное Линдеманом в 1882 году, было большим научным событием: ведь из него следо- вала невозможность квадратуры круга. И вдруг оказалось, что алгебраические числа, которые встре- чаются на каждом шагу, на самом деле являются величайшей редкостью, а трансцендентные числа, которые так трудно стро- ить, — обычным правилом. В самом деле, мы уже видели, что алгебраические числа образуют лишь счетное множество. Множе- ство же всех действительных чисел, как мы только что обнаружили, несчетно. Значит, несчетна и разность множества действительных чисел и множества алгебраических чисел, то есть множество транс- цендентных чисел. Это доказательство существования трансцендентных чисел, про- веденное Г. Кантором в 1873 году, произвело большое впечатление на математиков. Ведь Кантору удалось доказать существование трансцендентных чисел, не строя ни одного конкретного примера таких чисел, а лишь исходя из общих соображений. Но то, что явля- ется достоинством доказательства Кантора, в то же время является и его слабой стороной. Из теорем Лиувилля вытекает простой путь построения конкрет- ных примеров трансцендентных чисел. Например, трансцендентным является число 0,1010010000001. . . , в котором после первой единицы На длинном и коротком отрезках поровну точек 81 стоит один нуль, после второй — два, после третьей — шесть, по- сле n-й — n! нулей. Из доказательства же Кантора нельзя непосред- ственно извлечь никакого конкретного примера трансцендентного числа, это доказательство, как говорят математики, неконструктив- но: здесь приводится к противоречию предположение о несущество- вании трансцендентных чисел и только. На длинном и коротком отрезках поровну точек До тех пор, пока читатель не познакомился с удивительными свойствами бесконечных множеств, ответ на вопрос «где больше точек, на отрезке длиной в 1 мм или на отрезке длиной в 1 м?» Рис. 28 вряд ли вызвал бы у него хоть тень со- мнения — ясно, что на отрезке в 1 м куда больше точек, он ведь в 1000 раз длин- нее. Но теперь, вероятно, читатель поосте- режется делать столь безапелляционные заявления — уж слишком непохожи свой- ства бесконечных множеств на то, чему учит обыденная жизнь. И действительно, на очень коротком и очень длинном от- резках точек поровну! Иными словами, всегда можно установить взаимно однозначное соответствие между точками этих отрезков. Как это сделать, лучше всего видно из рис. 28. Трудно примириться с мыслью, что дорога длиной в миллион световых лет имеет столько же точек, сколько и радиус атомного ядра! Но еще неожиданнее оказалось то, что даже на всей бесконеч- ной прямой не больше точек, чем на отрезке, то есть что между множеством точек на прямой и множеством точек на отрезке можно установить взаимно однозначное соответствие. Мы возьмем даже не весь отрезок, а выбросим из него концы (как говорят, возьмем не отрезок, а промежуток). Как установить взаимно однозначное соответствие между промежутком и прямой, видно из рис. 29. Сначала точки промежутка отображают на по- луокружность, а потом проектируют полуокружность на прямую. Ясно, что при этом каждой точке промежутка соответствует одна и только одна точка прямой, причем ни одна точка на прямой не про- пущена. 82 Глава II. В мире чудес бесконечного Рис. 29 Рис. 30 То же самое соответствие можно установить и по-другому, с по- мощью кривой — тангенсоиды, графика функции y = tg x (рис. 30). Отрезок и квадрат С тем, что на бесконечной прямой столько же точек, сколько и на отрезке, математики, скрепя сердце, примирились. Но следую- щий результат Кантора оказался еще более неожиданным. В поисках множества, имеющего больше элементов, чем отрезок, он обратился к множеству точек квадрата. Сомнения в результате не было: ведь отрезок целиком размещается на одной стороне квадрата, а мно- жество всех отрезков, на которые можно разложить квадрат, само имеет ту же мощность, что и множество точек отрезка. Отрезок и квадрат 83 На протяжении трех лет (с 1871 по 1874) Кантор искал доказа- тельство того, что взаимно однозначное соответствие между точками отрезка и точками квадрата невозможно. Шли годы, а желанный результат не получался. И вдруг совер- шенно неожиданно ему удалось построить соответствие, которое он считал невозможным! Сначала он сам не поверил себе. Математику Дедекинду он писал: «Я вижу это, но не верю этому». Но все же пришлось смириться с тем, что интуиция подвела и здесь, — в квадрате оказалось ровно столько же точек, сколько и на отрезке. Строгое доказательство этого утверждения несколько осложняется из-за неоднозначности десятичной записи чисел. Поэто- му мы дадим лишь эскиз доказательства Кантора. Возьмем отрезок [0; 1] и квадрат со стороной 1. Этот квадрат можно считать расположенным так, как на рис. 31. Нам надо уста- Рис. 31 новить взаимно однозначное соответствие меж- ду точками отрезка и квадрата. Проектирова- ние точек квадрата на отрезок AB здесь не по- могает, ведь при проектировании в одну точку отрезка перейдет бесконечное множество точек квадрата (например, в точку A — все точки от- резка DA.) Решение получается следующим образом. Каждую точку T квадрата ABCD можно за- дать двумя числами — ее координатами x и y (или попросту ее расстояниями до сторон AD и AB). Эти числа можно записать как бесконечные десятичные дро- би. Так как x и y не больше 1, то эти дроби имеют вид x = 0,α 1 α 2 . . . α n . . . , (1) y = 0,β 1 β 2 . . . β n (2) (для простоты мы не берем точек квадрата, лежащих на его сторо- нах, а берем лишь внутренние точки). Здесь α n и β n — десятичные знаки чисел x и y, например, если x = 0,63205. . . и y = 0,21357. . . , то α 1 = 6, α 2 = 3, α 3 = 2 и т. д., β 1 = 2, β 2 = 1, β 3 = 3 и т. д. Нам надо теперь найти точку Q отрезка AB, соответствующую точке T . Достаточно указать длину отрезка AQ. Мы выберем эту длину равной числу z, десятичные знаки которого получаются путем «перетасовывания» десятичных знаков чисел x и y. Иными словами, сделаем из двух записей (1) и (2) третью, написав их десятичные 84 Глава II. В мире чудес бесконечного знаки через один: z = 0,α 1 β 1 α 2 β 2 α 3 β 3 . . . α n β n . . . Например, если x = 0,515623. . . , y = 0,734856. . . , то положим z = 0,571354682536. . . Точка z лежит на отрезке [0; 1], и ясно, что различным точкам квадрата соответствуют при этом разные точки отрезка. Ведь если точки T и T не совпадают, то в десятичных записях чисел x и x или y и y хоть один знак будет разный. Но это приведет к тому, что десятичные записи соответствующих чисел z и z не совпадут. Несколько более подробный анализ показывает, что тогда не совпа- дают и сами эти точки. Всех точек отрезка мы не получим. Например, точка z = = 0,191919. . . должна была бы получиться из пары x = 0,111. . . , x = 0,999. . . , соответствующей точке на стороне квадрата, а такие точки мы условились не брать. Поэтому при отображении квадрата на отрезок точка z не будет образом ни одной точки квадрата. Мы установили, таким образом, взаимно однозначное соответ- ствие между точками квадрата и частью точек отрезка [0; 1]. Это показывает, что множество точек квадрата имеет не большую мощ- ность, чем множество точек отрезка. Но его мощность и не меньше, а потому эти мощности совпадают. Немного изменив рассуждение, можно получить взаимно од- нозначное соответствие между всеми точками квадрата и всеми точ- ками отрезка. Для этого надо несколько осторожнее тасовать цифры координат. Возьмем снова не весь квадрат ABCD, а лишь его часть, полу- чающуюся при отбрасывании сторон BC и CD. Координаты точек этой части удовлетворяют неравенствам 0 x < 1 и 0 y < 1. Эти координаты можно записать в виде бесконечных десятичных дро- бей, причем, в силу сделанного выше условия, эти дроби не могут заканчиваться сплошными девятками. А теперь разобьем цифры, входящие в десятичные записи x и y, на группы, ставя вертикальную черту после каждой цифры, отличной от девятки. Например, если x = 0,3994599967. . . , y = 0,959978090. . . , то разбиение имеет вид x ∼ 3|994|5|9996|7|. . . , y ∼ 95|997|8|0|90|. . . Перетасуем полученные группы цифр так же, как раньше мы тасовали сами цифры. Получим бесконечную последовательность Одна задача почему-то не выходит 85 групп цифр 3|95|994|997|5|8|9996|0|7|90|. . . Поставим впереди этой последовательности нуль и опустим чер- точки. Получим десятичную дробь z = 0,3959949975899960790. . . , соответствующую точке квадрата M (x; y). Можно показать, что это соответствие между точками квадра- та 0 x < 1, 0 y < 1 и промежутка 0 z < 1 взаимно однозначно. Теперь уже легко получить соответствие между точками всего квад- рата ABCD и точками некоторого отрезка. Для этого достаточно взять отрезок длины 3 и взаимно однозначно отобразить часть квад- рата 0 x < 1, 0 y < 1 на промежуток 0 z < 1, а ломаную BCD — на отрезок 1 z 3. Не только квадрат, но и куб имеет столько же точек, сколько и отрезок. Вообще любая геометрическая фигура, содержащая хоть одну линию, имеет столько же точек, сколько и отрезок. Такие мно- жества назвали множествами мощности континуума (от латинского continuum — непрерывный). Мощность континуума имеет и множе- ство бесконечных телеграмм. Одна задача почему-то не выходит Мы познакомились пока что с двумя типами бесконечных мно- жеств. Одни из них имеют столько же элементов, сколько и множе- ство натуральных чисел, а другие — столько же, сколько и множе- ство точек на прямой. Оказалось, что во втором множестве больше элементов. Естественно, возникает вопрос, а нет ли «промежуточ- ного» множества, которое имело бы больше элементов, чем множе- ство натуральных чисел, и меньше, чем множество точек на пря- мой? Этот вопрос получил название проблемы континуума. Над ним думали многие выдающиеся математики, начиная с самого Георга Кантора, но до самого последнего времени проблема оставалась не- решенной. В течение долгих лет думал над проблемой континуума один из крупнейших математиков, основатель отечественной научной школы теории функций действительного переменного, академик Н. Н. Лузин. Но решение ускользало, как мираж в пустыне (правда, 86 Глава II. В мире чудес бесконечного в ходе размышлений над этой проблемой Н. Н. Лузин решил це- лый ряд труднейших задач теории множеств и создал целый отдел математики — дескриптивную теорию множеств). Однажды к Н. Н. Лузину привели пятнадцатилетнего мальчика Льва Шнирельмана, обладавшего исключительными математиче- скими способностями (впоследствии он стал одним из виднейших советских математиков, членом-корреспондентом АН СССР). Чтобы проверить способности юного математика, Н. Н. Лузин предложил ему тридцать труднейших задач. Решения 29 задач он знал, а од- ной была... проблема континуума. Но, увы, через неделю молодой математик пришел к Н. Н. Лузину и грустно сказал: «Одна задача почему-то не выходит». Неудачи попыток решить проблему континуума не были случай- ными. Положение дел здесь напоминает историю постулата о парал- лельных прямых. Этот постулат пытались на протяжении двух ты- сячелетий вывести из остальных аксиом геометрии. После работ Ло- бачевского, Гильберта и других ученых выяснилось, что он не про- тиворечит остальным аксиомам, но и не может быть выведен из них. Точно так же оказалось, что для подходящей аксиоматики теории множеств утверждение о существовании промежуточной мощности не противоречит остальным аксиомам (результат немецкого мате- матика К. Г¨ еделя, 1938 г.), но и не выводимо из них (это почти одновременно и независимо друг от друга доказали американец Ко- эн, 1963–1964 гг. и чех Вопенка, 1964 г.). |