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

арифметики натуральных чисел. Аналогично происходил процесс установления независимости некоторой системы аксиом. Неполнота. Формальная система S как математический объект полностью определяется заданием языка, системы аксиом и пра­ вил вывода. Напомним , что построенная таким образом система S должна обладать свойствами непротиворечивости, полноты, выводимос­ ти, независимости. ? Очень важен также и вопрос о метаязыке: это язык самой системы S или какой-то другой системы, например естественный язык? В поисках ответа на эти вопросы к 1920 г. была разработана так назы­ ваемая программа Гильберта формализации аксиоматических теорий и использования ее для математических доказательств. Известный немец­ кий ученый Давид Гильберт (1862— 1943) предложил развернутую про­ грамму обоснования математики, с помощью которой он собирался до­ казать непротиворечивость классической математики. Кроме этого, программа сведения математики к логике, к возможно­ сти формализации математической системы, в частности арифметики, была предпринята в фундаментальном трехтомном труде английских математиков, философов и логиков Бертрана Рассела (1872— 1970) и Алфреда Уайтхеда (1861 — 1947), который назывался Principia Mathematica (1910 -1913 ) . Однако в 1931 г. в одном из журналов была опубликована статья авст­ рийского ученого Курта Гёделя (1906—1978) «О формально неразреши­ мых противоречиях Principia Mathematica и родственных систем». Вней была доказана невозможность полной формализации не только челове­ ческих знаний и мышления, но и полной формализации арифметики натуральных чисел. Эта статья, содержавшая всего 25 страниц, открыла новую эпоху в истории математики и логики. Рассматривая непротиво­ речивую систему S, которую удалось свести к системе натуральных чи­ сел, Гедель построил формулу / и доказал, что она не может быть выве­ дена в этой системе аксиом. Таким образом, в этой системе с помощью известных аксиом и правил выводов нельзя доказать ни справедливость формулы / , ни справедливость формулы / Поэтому невозможна полная формализация арифметики натуральных чисел —достаточно обширной и известной формальной системы. Вывод о неполноте аксиоматики натуральных чисел одновременно доказывает и невозможность сведения математики к формальной логике. Смысл второй теоремы, доказанной Гёделем, состоит в том, что н е ­ противоречивость любой достаточно мощной математической системы не может быть выявлена средствами этой системы и описана на языке этой системы. Это значит, что необходимо применение языка другой системы для вывода новых формул, т.е. необходимы средства более мощ­ ной формальной системы. Поэтому можно утверждать, что полная фор­ мализация не может осуществиться на некотором этапе развития науки. Эти две теоремы можно обобщить: в любой формальной системе есть формулы, недоказуемые средствами только этой системы. Теоремы Гёделя 217