Теорема Геделя про неповноту
Мабуть, теорема Геделя про неповноту є справді унікальною. Унікальна в тому, що на неї посилаються, коли хочуть довести "все на світі" - від наявності богів до відсутності розуму. Мене завжди цікавило більш "первинне питання" - а хто з тих, хто посилається на теорему про неповноту, зміг би не тільки сформулювати її, а й довести? Я публікую цю статтю з тієї причини, що в ній викладено цілком доступне формулювання теореми Геделя. Рекомендую попередньо ознайомитись зі статтею Тулліо Редже Курт Гедель та його знаменита теорема
. висновок про неможливість універсального критерію істини є безпосереднім наслідком результату, отриманого Тарським шляхом з'єднання теореми Геделя про нерозв'язність з його власною теорією істини, згідно з яким універсального критерію істини не може бути навіть для відносно вузької галузі теорії чисел, а отже, і для будь-якої науки, яка використовує арифметику. Природно, що це результат застосовний a fortiori до поняття істини у будь-якій нематематичної області знання, у якій широко використовується арифметика.
Успенський Володимир Андрійович народився 27 листопада 1930 р. в Москві. Закінчив механіко-математичний факультет МДУ (1952). Доктор фізико-математичних наук (1964). Професор, завідувач кафедри математичної логіки і теорії алгоритмів механіко-математичного факультету (1966). Читає курси лекцій "Вступ до математичної логіки", "Обчислювані функції", "Теорема Геделя про повноту". Підготував 25 кандидатів та 2 докторів наук
1. Постановка задачі
Теорема про неповноту, точне формулювання якої ми дамо в кінці цього розділу, а можливо пізніше (у разі виникнення до цього інтересу у читача) і доказ, стверджує приблизнонаступне: за певних умов у будь-якій мові існують справжні, але недоказні твердження.
Коли ми в такий спосіб формулюємо теорему, майже кожне слово потребує певних пояснень. Тому ми почнемо з того, що пояснимо значення слів, які ми використовуємо в цьому формулюванні.
Ми не даватимемо найбільш загального з можливих визначень мови, вважаючи за краще обмежитися тими мовними концепціями, які нам знадобляться згодом. Є два таких поняття: "алфавіт мови" та "безліч справжніх тверджень мови".
Під алфавітом ми розуміємо кінцевий набір елементарних знаків (тобто речей, які неможливо розбити на складові). Ці символи називаються буквами алфавіту. Під словом алфавіту ми розуміємо кінцеву послідовність букв. Наприклад, прості слова в англійській мові (включаючи власні імена) є словами 54-хлітерного алфавіту (26 маленьких літер, 26 великих, тире і апостроф). Інший приклад - натуральні числа в десятковому записі є словами 10-тибуквенного алфавіту, чиї літери - знаки: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Для позначення алфавітів ми використовуватимемо прості великі літери. Якщо L – алфавіт, то L? буде позначати безліч всіх слів алфавіту L, - слів, утворених із його літер. Ми припустимо, що будь-яка мова має свій алфавіт, тому всі вирази цієї мови (тобто - імена різних об'єктів, твердження щодо цих об'єктів тощо) є словами цього алфавіту. Наприклад, будь-яка пропозиція англійської мови, так само як і будь-який текст, написаний англійською, може розглядатися як слово розширеного алфавіту з 54-х букв, що включає також знаки пунктуації, міжмовну прогалину, знак червоного рядка і, можливо, деякі інші корисні знаки. Припускаючи, що вирази мовиє словами деякого алфавіту, ми, таким чином, виключаємо з розгляду "багатошарові" вирази типу . f(x)dx. Однак, це обмеження не надто суттєве, оскільки будь-яке подібне вираження, при використанні відповідних конвенцій, може бути "розтягнуте" у лінійну форму. Будь-яка множина М, що міститься в L? називається ніби множиною алфавіту L. Якщо ми просто говоримо, що М - ніби множина, то ми маємо на увазі, що воно є словом деякого алфавіту. Тепер сформульоване вище припущення про мову може бути перефразовано наступним чином: у будь-якій мові будь-яка множина виразів є ніби множиною.
1.1.2. Безліч справжніх тверджень
Ми припустимо, що нам задано підмножину Т множини L? (де L алфавіт деякої мови, що розглядається нами), яке називається безліччю "істинних тверджень" (або просто "істин"). Переходячи безпосередньо до підмножини Т, ми опускаємо наступні проміжні кроки міркування: по-перше, які саме слова алфавіту L є коректно освіченими виразами мови, тобто мають певне значення в нашій інтерпретації цієї мови (наприклад, 2+3, х+3, х=у, х=3, 2=3, 2=2 є коректно освіченими виразами, тоді як вирази типу +=х такими є); по-друге, які вирази є формулами, тобто. можуть залежати від параметра (наприклад, х=3, х=у, 2=3, 2=2); по-третє, які з формул є закритими формулами, тобто. твердженнями, які не залежать параметрів (наприклад, 2=3, 2=2); і, нарешті, які саме закриті формули є істинними твердженнями (наприклад, 2=2).
1.1.3. Фундаментальна пара мови
Для наших цілей буде достатньо вважати, що мова задана повністю своїм алфавітом L та безліччюістинних тверджень Т - підмножиною множини L?. Ми називатимемо будь-яку таку пару фундаментальною парою мови.
"Недоказувані" означає не мають доказів.
Незважаючи на те, що термін "доказ" є, можливо, одним з найважливіших в математиці (Бурбаки починають свою книгу "Підстави математики" словами: "З часу давніх греків сказати "математика" означало те ж, що сказати "доказ""), він немає своєї точної дефініції. У цілому нині, поняття докази з його смисловими відгалуженнями належить, скоріш, до галузі психології, ніж до математики. Але як би там не було, доказ - це просто аргумент, який ми знаходимо цілком переконливим для того, щоб переконати всіх інших.
Будучи записано, доказ стає словом у певному алфавіті Р, як і будь-який англійський текст є словом алфавіту L, приклад якого було наведено вище. Безліч всіх доказів утворюють підмножину (і досить велике підмножина) множини Р?. Ми не намагатимемося дати точне визначення цієї одночасно "наївної" та "абсолютної" концепції доказу, або - що рівносильно - дати визначення відповідному підмножині Р?. Натомість ми розглянемо формальний аналог цього смутного поняття, для позначення якого надалі ми все ж таки користуватимемося терміном "доказ". Цей аналог має дві дуже важливі особливості, які відрізняють його від інтуїтивного поняття (хоча інтуїтивна ідея доказу все ж таки відображає певною мірою ці особливості). Насамперед ми припустимо, що є різні концепції докази, тобто - допустимі різні підмножини доказів у Р?, і навіть більше того: ми, насправді, припускатимемо, що сам алфавіт доказів Р може змінюватися.Далі ми вимагаємо, щоб для кожної такої концепції доказу існував ефективний метод, тобто алгоритм, який би з необхідністю визначав, чи є дане слово алфавіту Р доказом чи ні. Ми також припустимо, що існує алгоритм, за допомогою якого завжди можна визначити, яке саме твердження доводить цей доказ. (У багатьох ситуаціях твердженням, що доводиться, просто є останнє твердження в послідовності кроків, що утворюють доказ.)
Таким чином, наше остаточне формулювання визначення виглядає так:
(1) Ми маємо алфавіт L (алфавіт мови) і алфавіт Р (алфавіт доказу).
(2) Нам дано безліч Р, що є підмножиною Р?, Чиї елементи називаються "доказами". Надалі ми будемо припускати, що також у нас є алгоритм, який дозволяє нам визначити, чи є довільне слово алфавіту Р елементом множини Р, тобто доказом, чи ні.
(3) Також у нас є функція? (для знаходження того, що саме було доведено), чия область визначення? задовольняє умові Р. Р?, і чия область значень перебуває у Р?. Ми припускаємо, що у нас є алгоритм, який обчислює цю функцію (точне значення слів "алгоритм обчислює функцію" таке: значення функції виходять за допомогою цього алгоритму – набору спеціальних правил перетворення). Ми говоритимемо, що елемент р ? Р є доказ слова? (р) алфавіту L.
Трійка , що відповідає умовам (1)-(3) називається дедуктивною системою над алфавітом L.
Для читача, знайомого із звичайним способом визначення "докази" в термінах "аксіома" та "правило виведення", ми зараз пояснимо, як цей метод може розглядатися якспеціального випадку визначення, наведеного в параграфі 1.3.2. Тобто - доказ зазвичай визначається як послідовність таких виразів мови, кожне з яких є або аксіомою, або раніше отриманим з існуючих тверджень за допомогою одного з правил виведення. Якщо ми додамо нове слово * до алфавіту нашої мови, ми зможемо записати такий доказ у вигляді слова складеного за допомогою отриманого в результаті такої модифікації алфавіту: послідовність виразів стає словом C1*C2*. *Cn. У такому разі, функція, що визначає, що саме було доведено, своїм значенням має частину цього слова, що стоїть одразу за останньою у послідовності буквою *. Алгоритм, існування якого потрібно у частині 1.3.2. визначення, може легко бути сконструйований, як тільки ми точно визначимо якесь із прийнятих значень слів "аксіома" та "правила виведення".