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

имеют настолько важное значение в математике и логике, что признаны одним из выдающихся открытий XX в. Но удивительно в открытиях Гё­ деля то, что несостоятельность, ограниченность логических методов до­ казаны с помощью этих же формальных логических методов! о • Что это, очередной логический парадокс? Противоречие? Ответом на этот вопрос служат знаменитые слова О. Хевисайда: «Ло­ гика непобедима, потому что одолеть ее можно только с помощью ло­ гики!» В отличие от Гильберта, Рассела и других математиков и логиков К. Гё­ дель, используя в своих рассуждениях такой сильный метод, как абст­ ракция актуальной бесконечности, смог доказать два важных положе­ ния. 1. Всякая естественная непротиворечивая формализация 5 арифмети­ ки натуральных чисел или другой математической теории, содержащей арифметику (например, теории множеств),—неполная и непополнимая, в том смысле, что: • в S имеются содержательно истинные формулы f такие, что ни f ни / не являются выводимыми в S ,т.е. являются неразрешимыми в S; • любые попытки расширить систему S каким бы то ни было конеч­ ным множеством дополнительных аксиом Д S приводят к тому, что в новой системе S' неизбежно появятся свои неразрешимые формулы. 2. Если формализованная арифметика натуральных чисел в действи­ тельности непротиворечива, то доказательство этого утверждения, про­ веденное средствами, формализуемыми в ней самой, невозможно. Хотя утверждение о ее непротиворечивости может быть выражено на ее соб­ ственном языке. Следствием теорем Гёделя явилось установление связи между форма­ лизацией доказательства непротиворечивости арифметики и использо­ ванием понятия бесконечности. Дело в том, что когда вопрос о непротиворечивости разных разделов математики был сведен к проблеме доказательства не­ противоречивости арифметики натуральных чисел, дальнейшим обобщением могло быть лишь сведение к непротиворечивости те­ ории множеств как к самой абстрактной математической конст­ рукции. А как мы знаем из гл. 1, теория множеств как раз и содер­ жит в себе ряд противоречий (определение операций над множе­ ствами через логические функции и наоборот), неразрешимых на данном уровне развития науки. Познакомившись с правилами построения формальных сис­ тем, сравним с ними известные формальные системы для того, чтобы увидеть в действии эти теоретические положения. Уточним, что такой подход к построению формальных систем называется аксиоматическим. Стремление математиков формализо­ вать различные математические теории (иногда их называют мате­ матическими конструкциями) вызвано желанием найти общий ме­ тод не только для имеющихся теорий, но и для конструирования 218