|
и
CA
-
множества
без совершенного ядра. Кроме того, он установил, что в той же
системе, начиная с некоторого класса проективных множеств, име-
ют место такие же законы отделимости, как и во втором классе
2
Она формулируется так: Пусть имеется упорядоченное множество
без лакун, характеризующееся тем, что всякая система попарно непересе-
кающаяся его интервалом не более чем счётна. Спрашивается, подобно ли
это множество континууму. (
Прим. автора
)
191
О роли теоретико-множественных концепций в развитии основ математики
про ективных множеств. Впоследствии Аддисон показал, что это
име ет место, начиная с третьего класса.
Таким образом, оказалось, что ряд основных проблем, казав-
шихся недоступными для классической теории множеств, получил
решение в рамках аксиоматики Гёделя. Долгое время было не яс-
но, является ли подход Гёделя единственным возможным.
Наконец, в 1963 году появилась работа Коэна, где вместо ак-
сиом конструктивности Гёделя к обычным аксиомам теории мно-
жеств была присоединена существенно другая аксиома, и тоже бы-
ло доказано, что если исходная система непротиворечива, то добав-
ление новой аксиомы к противоречиям не ведет. Эта аксиома, так
же как и аксиома конструктивности, уточняет возможности транс-
финитной индукции, но делает это не так, как аксиома Гёделя.
В системе Коэна оказалось, что гипотеза континуума неверна
и аксиома Цермело противоречива. Впоследствии были построены
и такие условно-непротиворечивые расширения систем аксиом тео-
рии множеств, в которых всякое несчётное
CA-
множество имеет
совершенное ядро и всякое множество оказывается измеримым.
Есть такие системы аксиом, в которых проблема Суслина имеет
положительное решение, а также такие, в которых она имеет отри-
цательное решение. Таким образом, работы по аксиоматической
теории множеств показали, что те задачи, перед которыми остано-
вилась классическая теория множеств, и, в частности, дескриптив-
ная теория множеств, в классических условиях независимы. Они
не имеют однозначного решения и действительно требуют специ-
альных аксиом, как подозревал Лузин. В частности, отсюда следу-
ет, что дескриптивная теория множеств со своими задачами спра-
вилась полностью. Она сделала всё, что было в её возможностях, и
остановилась перед задачами, которые в её рамках решения не до-
пускают.
Нужно подчеркнуть, что решающую роль в оконтуривании
изнутри возможностей дескриптивной теории множеств сыграл
П.С. Но виков. Именно им были установлены результаты, которые
очертили её возможности изнутри. В этом чрезвычайно глубокое и
непреходящее значение теоретико-множественных работ П.С. Но-
викова. Кроме того, он сам принял деятельное участие и в уста-
новлении границы однозначного сверху
–
он получил ряд важных
результатов, относящихся к аксиоматической теории множеств, ре-
шив ряд задач, не решаемых в классических рамках.
Принципиальная роль дескриптивной теории множеств в ма-
тематике сказалась не только в том, что она подготовила почву
аксиоматической теории множеств. В некотором смысле она под-
192
III. ИЗБРАННЫЕ СТАТЬИ А.А. ЛЯПУНОВА
готовила почву для теории алгоритмов. Для дескриптивной теории
множеств чрезвычайно характерны идеи эффективного построения
всё усложняющихся классификаций и последовательного просле-
живания того, как при продвижении по этой классификации по-
степенно угасают те или иные свойства объектов, а также самих
классов.
Эти же идеи играют огромную роль в теории алгоритмов. Од-
нако в теории алгоритмов на возможности конструирования объ-
ектов накладываются значительно более жёсткие требования эф-
фективности, чем в дескриптивной теории множеств.
Соотношение отделимости, инвариантность классов относи-
тельно тех или других операций, возможность установления тех
или иных отображений одних множеств, принадлежащих к опре-
делённому классу, на другие
–
всё это постановки вопросов, харак-
терные для дескриптивной теории множеств и перешедшие из неё
в теорию алгоритмов.
В то же время, в первый период своего существования теория
алгоритмов была несколько изолирована в рамках математики.
С одной стороны, она дала возможность её создателям (Эрбрану,
Посту, Чёрчу, Клини и Тьюрингу) установить неразрешимость це-
лого ряда проблем. С другой стороны, те проблемы, которые ока-
зались доступными для методов теории алгоритмов, были сфор-
мулированы совершенно искусственным образом. Они не пред-
ставляли сколько-нибудь общематематического интереса. Поэтому
установление их алгоритмической неразрешимости выглядело как
некоторый математический курьёз, заставляющий задуматься, но
не имеющий самодовлеющего значения.
П.С. Новиков заинтересовался возможностями теории алго-
ритмов и получил результат, в корне изменивший её положение
внутри математики. Он установил алгоритмическую неразреши-
мость проблемы тождества в теории групп. За этим результатом
последовала целая серия других результатов, полученных частью
самим П.С. Новиковым, частью его непосредственными ученика-
ми, частью другими математиками. Ими была установлена алго-
ритмическая неразрешимость целой серии задач, долгое время сто-
явших в математике. Большое значение теории алгоритмов в ма-
тематике в целом прояснилось. Однако долгое время она служила
только для установления отрицательных результатов. Возникла
столь характерная для дескриптивной теории множеств проблема
очерчивания границы, отделяющей алгоритмически разрешимое от
алгоритмически неразрешимого. Однако средства теории алгорит-
мов служили лишь для обрисовывания этой границы извне. Изнут-
193
О роли теоретико-множественных концепций в развитии основ математики
ри эта граница обрисовывалась по-прежнему традиционными ма-
тематическими методами.
И здесь опять П.С. Новиков сыграл пионерскую роль. Ис-
пользуя идеи теории алгоритмов, П.С. Новиков вместе с С.И. Адя-
ном получили неожиданное решение классической проблемы Бер-
найса. После этого постепенно теоретико-алгоритмические идеи
стали служить не только для установления алгоритмической нераз-
решимости некоторых проблем, но и для построения алгоритмов,
решающих проблемы. Сейчас идёт интенсивная работа в разных
направлениях по установлению этой границы.
194
III. ИЗБРАННЫЕ СТАТЬИ А.А. ЛЯПУНОВА
Do'stlaringiz bilan baham: |
