на тему: «Теорема Геделя»
У 1951 р Курт Гедель був удостоєний вищої наукової нагороди США - ейнштейнівська премії. У статті, присвяченій цій події, інший найбільший математик нашого часу Джон фон Нейман писав [1]. «Внесок Курта Геделя в сучасну логіку воістину монументальний. Це - більше, ніж просто монумент. Це віха, що розділяє дві епохи ... Без жодного перебільшення можна сказати, що роботи Геделя докорінно змінили сам предмет логіки як науки ».
Теорема Геделя про неповноту
Перша теорема про неповноту
Перша теорема Геделя про неповноту. по всій видимості, є найбільш знаменним результатом в математичній логіці. Вона звучить наступним чином:
Для довільної несуперечливої формальної і обчислюваною теорії, в якій можна довести базові арифметичні висловлювання, може бути побудовано істінноеаріфметіческое висловлювання, істинність якого не може бути доведена в рамках теорії [1]. Іншими словами, будь-яка цілком корисна теорія, достатня для подання арифметики, не може бути одночасно несуперечливої і повної.
Тут слово «теорія» означає «безліч» висловлювань, деякі з яких покладаються істинними без доказів (такі висловлювання називаються аксіомами), а інші (теореми) можуть бути виведені з аксіом, а тому покладаються (доводяться) істинними. Словосполучення «доказовий в теорії» позначає «виведений з аксіом і примітивів теорії (константних символів алфавіту) за допомогою стандартної логіки (першого порядку)». Теорія є несуперечливої (узгодженої), якщо в ній неможливо доказатьпротіворечівое висловлювання. Словосполучення «може бути побудовано» позначає, що існує деяка механічна процедура (алгоритм), яка може побудувати висловлювання на основі аксіом, примітивів і логіки першого порядку. «Елементарна арифметика» полягає в наявності операцій додавання і множення над натуральними числами. Результуюче справжнє, але недоведені висловлювання часто позначається для заданої теорії як «послідовність Геделя», проте існує нескінченно кількість інших висловлювань в теорії, які мають таке ж властивість: бездоказова в рамках теорії істинність.
Припущення про те, що теорія обчислюваності, позначає, що в принципі можливо реалізувати комп'ютерний алгоритм (комп'ютерну програму), яка (якщо їй дозволено обчислювати довільно довгий врея, аж до нескінченності) вирахує список всіх теорем теорії. Фактично, досить обчислити тільки список аксіом, і все теореми можуть бути ефективно отримані з такого списку.
Перша теорема про неповноту була названа «Теорема VI» в статті Геделя від 1931 року On Formally Undecidable Propositions in Principia Mathematica and Related Systems I. В оригінальній записи Геделя вона звучала як:
«Загальний висновок про існування нерозв'язних пропозицій полягає в наступному:
Для кожного # 969; -согласованного рекурсивного класу k ФОРМУЛ існують рекурсивні ЗНАКИ rтакіе, що ні (v Genr), ні ¬ (v Genr) не належать Flg (k) (де v є ВІЛЬНА ЗМІННА r) [2] ».
Позначення Flg походить від нім. Folgerungsmenge - безліч послідовностей, Gen походить від нім. Generalisation - узагальнення.
Грубо кажучи, висловлювання Геделя G стверджує: «істинність G не може бути доведена». Якби G можна було довести в рамках теорії, то в такому випадку теорія містила б теорему, яка суперечить сама собі, а тому теорія була б суперечлива. Але якщо G неможливо довести, то воно істинне, а тому теорія неповна (вислів G невиведені в ній).
Це пояснення на звичайному природною мовою, а тому не зовсім математично строго. Для надання суворого докази, Гедель пронумерував висловлювання за допомогою натуральних чисел. В цьому випадку теорія, яка описувала числа, також належить множині висловлювань. Питання про доказовою висловлювань представимо в даному випадку у вигляді питань про властивості натуральних чисел, які повинні бути обчислюваності, якщо теорія сповнена. У цих термінах висловлювання Геделя свідчить, що не існує числа з деяким певним властивістю. Число з цією властивістю буде доказом суперечливості теорії. Якщо таке число існує, теорія суперечлива всупереч початковим припущенням. Так що припускаючи, що теорія несуперечлива (як передбачається в посилці теореми), виходить, що такого числа не існує, і висловлювання Геделя істинно, але в рамках теорії цього довести неможливо (отже, теорія неповна). Важливе концептуальне зауваження полягає в тому, що необхідно передбачити, що теорія несуперечлива, для того щоб оголосити висловлювання Геделя істинним.
Друга теорема Геделя про неповноту
Друга теорема Геделя про неповноту звучить наступним чином:
Для будь-якої формально рекурсивно лічильної (тобто ефективно генерується) теорії T, включаючи базові арифметичні істінностние висловлювання і певні висловлювання про формальну доказовою, дана теорія T включає в себе твердження про свою несуперечності тоді і тільки тоді, коли теорія T суперечлива.
Іншими словами, несуперечливість досить багатою теорії не може бути доведена засобами цієї теорії. Однак цілком може виявитися, що несуперечливість однієї конкретної теорії може бути встановлена засобами іншої, більш потужної формальної теорії. Але тоді постає питання про несуперечності цієї другої теорії, і т.д.
Використовувати цю теорему для доказу того, що розумна діяльність не зводиться до обчислень, намагалися багато. Наприклад, ще в 1961 році відомий логік Джон Лукас (John Lucas) виступав з подібною програмою. Його міркування виявилися досить уразливими - проте він і завдання ставив більш широко. Роджер Пенроуз використовує дещо інший підхід, який викладається в книзі повністю, «з нуля».
Наслідки теорем зачіпають філософію математики, особливо такі формалізму, які використовують формальну логіку для визначення своїх принципів. Можна перефразувати першу теорему про неповноту наступним чином: «неможливо знайти всеохоплюючу систему аксіом, яка була б здатна довести все математичні істини, і жодної брехні». З іншого боку, з точки зору суворої формальності, ця переформулировка не має особливого сенсу, оскільки вона передбачає поняття «істина» і «брехня» певними в абсолютному значенні, ніж у відносному для кожної конкретної системи.
А ось таке перефразування другий теореми є ще більш тривожним для основ математики:
Якщо неможливо довести несуперечність і повноту системи в рамках неї самої, то ця система суперечлива.
Отже, для встановлення факту несуперечності деякої системи S необхідно використовувати більш потужну систему T. але доказ в рамках T не може бути повністю закінченим, поки не доведена несуперечність самої T (причому без використання системи S).
Спочатку здавалося, що все-таки теореми Геделя залишають трохи надії, оскільки можна створити загальний алгоритм, який вирішує, чи є задане твердження вирішуваним чи ні. Цей алгоритм дозволить математикам обійти всі нерозв'язні проблеми відразу разом. Однак, негативна відповідь на проблеми вибору, отриманий в 1936 році, показав, що такого алгоритму не існує.
Деякі дослідники припускають, що твердження, яке неможливо довести в рамках дедуктивної системи, може бути абсолютно доказові на деякому метамові. А то, що не може бути доведено на цьому метамові, може, в свою чергу, бути доведено на мета-метамові. і так до нескінченності. Застосовуючи такі системи типізованих метамовою спільно з аксіомою редуціруеми, яка по індуктивному припущенню застосовується до всього набору мов, можна для будь-яких галузей знань обходити проблему неповноти.
Необхідно також відзначити, що теореми Геделя застосовні тільки до досить сильним системам аксіом. «Досить сильний» в даному контексті означає, що теорія містить достатньо коштів для представлення даних, необхідних для доказу першої теореми про неповноту. Важливо не тільки те, що для цього потрібні базові аксіоми, що представляють операції додавання і множення, як, наприклад, в арифметиці Робінсона Q. Існують більш слабкі системи аксіом, які сповнені і несуперечливі, наприклад, арифметика Пресбургер, яка доводить істинність тверджень першого порядку тільки щодо складання.
Система аксіом може містити нескінченну кількість аксіом (як, наприклад, арифметика Пеано першого порядку), але для застосування до такої системи теореми Геделя. повинен бути ефективний алгоритм, який дозволяє перевіряти коректність. Наприклад, можна розглянути безліч всіх висловлювань першого порядку, який істинні в стандартній моделі натуральних чисел. Ця система є повною, але теорема Геделя непридатна в даному випадку, оскільки не існує ефективної процедури, яка визначає, чи є задана послідовність аксіомою. Фактично, це так по слідству з першої теореми Геделя про неповноту.
Інший приклад теорії, до якої застосовується перша теорема Геделя про неповноту, може бути побудований таким чином: необхідно впорядкувати всі можливі істинні твердження щодо натуральних чисел сначал по довжині рядка, а потім лексикографічно. Далі система аксіом будується так - спочатку береться система аксіом Пеано, після чого необхідно в списку тверджень вибирати перше по порядку твердження, яке не може бути доведено. Далі це твердження вноситься в список аксіом нової системи. І так до кінця. В кінцевому підсумку цей процес створить повну, несуперечливу і досить потужну формальну систему, яка, однак, не буде лічильної.
Сам Гедель довів технічно більш слабкі версії теорем. Перший доказ теорем в наведених в статті формулюваннях вперше було наведено Д.Б. Россером в 1936 році.
По суті, доказ першої теореми містить процес конструювання затвердження p в рамках формальної системи, яке можна описати на метамові наступним чином:
p = «Це твердження не може бути доведено в розглянутій формальної системі»
Як видно, це, всього лише, сучасний варіант парадокса брехуна, який на відміну від класичного формулювання, не зовсім парадоксальний.
Якщо система аксіом несуперечлива, доказ теореми Геделя показує, що p (і його заперечення) не можуть бути доведені в рамках системи. Отже твердження p істинно (це твердження про те, що вона сама неможливо довести, і воно дійсно неможливо довести). Якщо система аксіом # 969; -непротіворечіва, то заперечення p також не може бути доведено, і таким чином p невичіслімо. У системах, які # 969; -протіворечіви (але несуперечливі), або є така ж ситуація, або твердження ¬p може бути доведено.
Додавання затвердження p як аксіоми не вирішує проблеми, оскільки для такої розширеної системи буде існувати інше твердження Геделя. Такі теорії, як арифметика Пеано, для яких не може бути побудовано перечислимого розширення, називаються істотно неповними.
Гедель математичний теорема неповнота
1.В.А. Успенський. Теорема Геделя про неповноту. - М. Наука, 1982.