Спирина, М.С. Дискретная математика

З а д о л г о до создания самой теории множеств, еще в XVIII в., выда­ ю щ и й с я математик, член Петербургской академии наук, уроженец Швей­ царии Леонард Эйлер (1707—1783) предложил изображать множества в виде кругов. Затем Кантор открыл, что не все бесконечные множества имеют одинаковую мощность (т.е. эквивалентны между собой). Суще­ ствуют разные степени эквивалентности, причем мощность любого счет­ н о г о множества меньше мощности несчетного. Так, мощность множе­ ства действительных чисел К больше мощности множества рациональ­ ных чисел Q. ? Как же практически сравнивать множества? Прямым образом установить равномощность можно, если толь­ ко множества действительно равномощны. Но реально не всегда возможно, как учили в школе, совместить и проверить их равен­ ство. Для этого могут помочь некоторые теоремы о мощности мно ­ жеств: 1. Если А с Д, то \А\ < |Д|. 2. Если А ~ С с В, В ~ D с А, то \А\ = |Д|. 3. Если К с М и К несчетно, то М тоже несчетно. п . Какой вывод сделали ученые, сравнив мощности множеств Ъ и Q? Сравните мощности множеств точек единичного отрезка и множества точек единичного квадрата (а = 1). Где больше точек — на отрезке (одно­ мерный континуум) или на плоскости — в квадрате или круге радиуса г = 1 (двумерный континуум)? Так возникает еще один парадокс теории множеств. Нас под­ водит наша интуиция, так как в теории множеств не срабатывают аналогии. Оказывается, между отрезком и квадратом можно уста­ новить взаимно-однозначное соответствие, и эти множества бу­ дут эквивалентны. Кроме математических парадоксов, теория множеств содержит и общелогические парадоксы (рис. 1.12). Проблемы бесконечности, дискретности и непрерывности интересо­ вали древнегреческих философов начиная с VI в. до н. э. Основные поло­ жения теории множеств были заложены в конце XIX в. Георгом Канто­ ром (1845—1918). Важные результаты в области теории множеств были получены Ричардом Дедекиндом (1831 — 1916). Но абстрактная теория множеств встретила резкое неприятие в математических кругах конца XIX в., так как противоречила привычным математическим представле­ ниям. На рубеже XIX и XX вв. математики столк­ нулись с так называемыми парадоксами теории множеств, которые противоречили здравому смыслу. Следствием бурного обсуждения вопро­ са о противоречиях, связанных с теорией мно­ жеств, был глубокий кризис основ математики, Рис. 1.12. Обшелоги- который затронул весь научный мир. На попытки ческий парадокс2 Здесь записано ложное утверждение 2 Дискретная математика 33