РЕФЕРАТ
на тему: В«ТЕОРЕМА Геделя В»
Курт Гедель
Курт Гедель - найбільший фахівець з математичної логіки - народився 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 невиводимість в ній).
Це пояснення на звичайному природному мовою, а тому не зовсім математично строго. Для надання строгого доказу, Гедель пронумерував висловлювання за допомогою натуральних чисел. У цьому випадку теорія, що описує числа, також належить безлічі висловлювань. Питання про доказовою висловлювань представимо в даному випадку у вигляді питань про властивості натуральних чисел, які повинні бути вичіслімості, якщо теорія повна. У цих термінах вислів Геделя свідчить, що не існує числа з деяким певною властивістю. Число з цією властивістю буде доказом суперечливість теорії. Якщо таке число існує, теорія суперечлива всупереч початковим припущенням. Так що припускаючи, що теорія несуперечлива (як передбачається в посилці теореми), виходить, що такого числа не існує, і вислів Геделя істинно, але в рамках теорії цього довести неможливо (отж...
