Теорема Геделя

РЕФЕРАТ

на тему: В«ТЕОРЕМА Геделя В»

Курт Гедель

Курт Гедель - найбільший фахівець з математичної логіки - народився 28 квітня 1906 У Брюнне (нині м. Брно, Чехія). Закінчив Віденський університет, де захистив докторську дисертацію, був доцентом в 1933-1938 рр.. Після аншлюсу емігрував до США. З 1940 по 1963 р. Гедель працював в Прінстонському інституті вищих досліджень. Гедель - почесний доктор Єльського і Гарвардського університетів, член Національної академії наук США та Американського філософського товариства.

У 1951 р. Курт Гедель був удостоєний вищої наукової нагороди США - ейнштейнівська премії. В статті, присвяченій цій події, інший найбільший математик нашого часу Джон фон Нейман писав [1]: В«Внесок Курта Геделя в сучасну логіку воістину монументальний. Це - більше, ніж просто монумент. Це віха, що розділяє дві епохи ... Без жодного перебільшення можна сказати, що роботи Геделя докорінно змінили сам предмет логіки як науки В».

Дійсно, навіть сухий перелік досягнень Геделя в математичній логіці показує, що їх автор по суті заклав основи цілих розділів цієї науки: теорії моделей (1930 р.; так звана теорема про повноту вузького числення предикатів, показує, грубо кажучи, достатність коштів В«формальної логікиВ» для докази усіх висловлюваних на її мові істинних речень), конструктивної логіки (1932-1933 рр..; результати про можливості відомості деяких класів пропозицій класичної логіки до їх интуиционистской аналогам, що поклали початок систематичного вживання В«погружающих операцій В», що дозволяють здійснювати таке зведення різних логічних систем один одному), формальної арифметики (1932-1933 рр..; результати про можливості відомості класичної арифметики в интуиционистской, що показують в деякому сенсі несуперечність першим відносно другої), теорії алгоритмів і рекурсивних функцій (1934 р.; визначення поняття общерекурсівной функції, що зіграв вирішальну роль у встановленні алгоритмічної нерозв'язності низки найважливіших проблем математики, з одного боку. І в реалізації логіко-математичних задач на електронно-обчислювальних машинах - з іншого), аксіоматичної теорії множин (1938 р.; доказ відносної несуперечності аксіоми вибору і континуум-гіпотези Кантора від аксіом теорії множин, що поклало початок серії найважливіших результатів про відносну несуперечності і незалежності теоретико-множинних принципів).

Теорема Геделя про неповноту

Введення

У 1931 р. В одному з німецьких наукових журналів з'явилася порівняно невелика стаття з досить страхітливим назвою В«Про формально нерозв'язних пропозиціях Principia Mathematica і споріднених систем В». Автором її був двадцятип'ятирічний математик з Віденського університету Курт Гедель, згодом працював у Прінстонському інституті вищих досліджень. Робота ця зіграла вирішальну роль в історії логіки і математики. У рішенні Гарвардського університету про присудження Геделя почесною докторського ступеня (1952) вона була охарактеризована як одне з найбільших досягнень сучасної логіки.

Однак в момент опублікування ні назва геделевской роботи. Ні зміст її нічого не говорили більшості математиків. Згадані в її назві Principia Mathematica - це монументальних тритомну трактат Альфреда Норта Уайтхеда і Бертрана Рассела, присвячений математичній логіці та підставами математики; знайомство з трактатом аж ніяк не було необхідною умовою для успішної роботи в більшій частини розділів математики. Інтерес до розбираємо в роботі Геделя питань завжди був долею вельми нечисленної групи вчених. У той же час міркування, наведені Геделем в його доказах, були для свого часу настільки незвичайними. Що для повного їх розуміння потрібно виняткове володіння предметом і знайомство з літературою, присвяченою цим вельми специфічним проблемам.

Перша теорема про неповноту

Перша теорема Геделя про неповноту , по всій видимості, є найбільш знаменним результатом в математичній логіці. Вона звучить таким чином:

Для довільної несуперечливої вЂ‹вЂ‹формальної і обчислюваною теорії, в якій можна довести базові арифметичні висловлювання, може бути побудовано істінноеаріфметіческое висловлювання, істинність якого не може бути доведена в рамках теорії [1] . Іншими словами, будь-яка цілком корисна теорія, достатня для подання арифметики, не може бути одночасно несуперечливої вЂ‹вЂ‹і повної.

Тут слово В«теоріяВ» позначає В«нескінченна безлічВ» висловлювань, деякі з яких покладаються істинними без доказів (такі висловлювання називаються аксіомами), а інші (теореми) можуть бути виведені з аксіом, а тому покладаються (доказуються) істинними. Словосполучення В«Доказовий в теоріїВ» позначає В«виведений з аксіом і примітивів теорії (Константних символів алфавіту) за допомогою стандартної логіки (першого порядку) В». Теорія є несуперечливою (узгодженої), якщо в ній неможливо доказатьпротіворечівое висловлювання. Словосполучення В«може бути побудованоВ» позначає, що існує деяка механічна процедура (алгоритм), яка може побудувати висловлювання на основі аксіом, примітивів і логіки першого порядку. В«Елементарна арифметикаВ» полягає в наявності числами. Результуюче істинне, але недовідне вислів часто позначається для заданої теорії як В«послідовність ГеделяВ», проте існує нескінченно кількість інших висловів в теорії, які мають таке ж властивість: бездоказова в рамках теорії істинність.

Припущення про те, що теорія вичіслімості, позначає, що в принципі можливо реалізувати комп'ютерний алгоритм (Комп'ютерну програму), яка (якщо їй дозволено обчислювати довільно довгий врея, аж до нескінченності) обчислить список всіх теорем теорії. Фактично, достатньо обчислити тільки список аксіом, і всі теореми можуть бути ефективно отримані з такого списку.

Перша теорема про неповноту була озаглавлена ​​як В«Теорема VIВ» у статті Геделя від 1931 року On Formally Undecidable Propositions in Principia Mathematica and Related Systems I . В оригінальній записи Геделя вона звучала як:

В«Загальний висновок про існування нерозв'язних пропозицій полягає в наступному:

Теорема VI .

Для кожного П‰-узгодженого рекурсивного класу k ФОРМУЛ існують рекурсивні ЗНАКИ r такі, що ні ( v Gen r ) , ні В¬ ( v Gen r ) НЕ ЗМІННА 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 істинно (це твердження про те, що воно само недоказово, і воно дійсно недоказово). Якщо система аксіом П‰ -несуперечлива, то заперечення p також не може бути доведено, і таким чином p невичіслімо. У системах, які П‰ -суперечливі (Але несуперечливі), або є така ж ситуація, або твердження В¬ p може бути доведено.

Додавання затвердження p в якості аксіоми не вирішує проблеми, оскільки для такої розширеної системи буде існувати інше твердження Геделя. Такі теорії, як арифметика Пеано, для яких не може бути побудовано перечислимого розширення, називаються істотно неповними .

Список літератури

Гедель математичний теорема неповнота

1. В.А. Успенський. Теорема Геделя про неповноту. - М.: Наука, 1982.

2. Теорема Геделя/Е. Нагель, Дж.Р. Ньюмен. - М.: Красанд, 2010. - 120 с.

3. Традиція. Російська енциклопедія: URL: traditio.ru/wiki/

[1] Цитата збірника статей В«Підстави математикиВ» випущеному в Нью-Йорку на честь 60-річчя К. Геделя.