Loading AI tools
З Вікіпедії, вільної енциклопедії
Теорема Геделя про неповноту і друга теорема Геделя[~ 1] (англ. Gödel's incompleteness theorems) — дві теореми математичної логіки про принципові обмеження формальної арифметики і, як наслідок, будь-якої формальної системи, в якій можливо визначити основні арифметичні поняття: натуральні числа, 0, 1, додавання та множення.
Перша теорема стверджує, що, якщо формальна арифметика є несуперечливою, то в ній існує невивідна і неспростовна формула.
Друга теорема стверджує, що якщо формальна арифметика є несуперечливою, то в ній є невивідною деяка формула, яка змістовно стверджує несуперечливість цієї арифметики.
Обидві ці теореми було доведено Куртом Геделем 1930 року (опубліковано 1931 року), вони мають безпосередній стосунок до другої проблеми[en] зі знаменитого списку Гільберта.
У своєму формулюванні теореми про неповноту Гедель використовував поняття ω-несуперечливої формальної системи — сильніша умова, ніж просто несуперечливість. Формальна система називається ω-несуперечливою, якщо для будь-якої формули A(x) цієї системи неможливо одночасно вивести формули А(0), А(1), А(2), … і ∃x¬A(x) (іншими словами, з того, що для кожного натурального числа n виведено формулу A(n), випливає невивідність формули ∃x ¬A(x)). Легко показати, що ω-несуперечливість спричиняє просту несуперечливість (тобто, будь-яка ω-несуперечлива формальна система є несуперечливою)[6].
У процесі доведення теореми будується така формула A арифметичної формальної системи S, що[6]:
Формулу A іноді називають геделевою нерозв'язною формулою[7].
В стандартній інтерпретації[~ 3] формула A означає «не існує виведення формули A», тобто стверджує свою власну невивідність в S. Отже, за теоремою Геделя, якщо тільки система S є несуперечливою, то ця формула і справді є невивідною в S і тому істинною в стандартній інтерпретації. Таким чином, для натуральних чисел формула A є правильною, але невивідною в S[8].
У процесі доведення теореми будується така формула B арифметичної формальної системи S, що[9]:
Формулу B іноді називають россеровою нерозв'язною формулою[10]. Ця формула трохи складніша за геделеву.
В стандартній інтерпретації[~ 3] формула B означає «якщо існує виведення формули B, то існує виведення формули ¬B». Згідно ж теореми Геделя у формі Россера, якщо формальна система S є несуперечливою, то формула B в ній є невивідною; тому, якщо система S є несуперечливою, то формула B є правильною в стандартній інтерпретації[11].
Доведення теореми Геделя зазвичай проводять для конкретної формальної системи (не обов'язково однієї й тієї ж), відповідно твердження теореми виявляється доведеним тільки для однієї цієї системи. Дослідження достатніх умов, яким повинна задовольняти формальна система для того, щоб можливо було провести доведення її неповноти, веде до узагальнень теореми на широкий клас формальних систем. Приклад узагальненого формулювання[12]:
Зокрема, теорема Геделя справедлива для кожного несуперечливого скінченно аксіоматизовного розширення арифметичної формальної системи S.
Після того, як Юрій Матіясевіч довів діофантовість будь-якої ефективно зліченної множини і було знайдено приклади універсальних діофантових рівнянь, з'явилася можливість сформулювати теорему про неповноту в поліноміальному (або діофантовому) вигляді[13][14][15][16]:
Степінь даного рівняння можливо знизити до 4 ціною збільшення кількості змінних.
Детальніші відомості з цієї теми ви можете знайти в статті Начерк доведення першої теореми Геделя про неповноту[en].
У своїй статті Гедель дає начерк основних ідей доведення[17], який наведено нижче з незначними змінами.
Кожному примітивному символові, виразу і послідовності виразів деякої формальної системи[~ 4] S поставмо у відповідність певне натуральне число[~ 5]. Математичні поняття і твердження таким чином стають поняттями і твердженнями про натуральні числа, і, отже, їх самі може бути виражено в символізмі системи S. Можливо показати, зокрема, що поняття «формула», «виведення», «вивідна формула» може бути визначено всередині системи S, тобто можливо відновити, наприклад, формулу F(v) в S з однієї вільної натурально-числової змінної v таку, що F(v), в інтуїтивній інтерпретації, означає: v — вивідна формула. Тепер побудуймо нерозв'язне речення системи S, тобто речення A, для якого ані A, ані не-A невивідні, таким чином:
Формулу в S з рівно однією вільної натурально-числовою змінною назвімо клас-виразом. Впорядкуймо клас-вирази в послідовність будь-яким чином, позначмо n-й через R(n), і зауважмо, що поняття «клас-вираз», також як і відношення впорядкування R, можливо визначити в системі S. Нехай α — довільний клас-вираз; через [α;n] позначмо формулу, яка утворюється з клас-виразу α заміною вільної змінної символом натурального числа n. Тернарне відношення x = [y;z] теж виявляється визначним в S. Тепер визначмо клас K натуральних чисел таким чином:
де Bew x означає: x — вивідна формула[~ 6]. Оскільки всі визначальні поняття з цього визначення можливо виразити в S, то це ж правильно і для поняття K, яке з них побудовано, тобто є такий клас-вираз C, що формула [C;n], інтуїтивно інтерпретована, позначає, що натуральне число n належить K. Як клас-вираз, C ідентичний деякому певному R(q) в нашій нумерації, тобто
виконується для деякого певного натурального числа q. Тепер покажімо, що речення [R(q);q] нерозв'язне в S. Так, якщо припускається, що речення [R(q);q] є вивідним, то воно виявляється істинним, тобто, відповідно до сказаного вище, q буде належати K, тобто, відповідно до (*), буде виконано ¬Bew [R(q);q], що суперечить нашому припущенню. З іншого боку, якщо припустити вивідність заперечення [R(q);q], то матиме місце ¬q∈K, тобто Bew[R(q);q] буде істинним. Отже, [R(q);q] разом зі своїм запереченням буде вивідним, що знову є неможливим.
В стандартній інтерпретації[~ 3] геделева нерозв'язна формула A означає «не існує виведення формули A», тобто стверджує свою власну невивідність в системі S. Таким чином, A є аналогом парадоксу брехуна. Міркування Геделя в цілому дуже схожі на парадокс Рішара[en]. Більше того, для доведення існування невивідності тверджень може бути використано будь-який семантичний парадокс[17].
Слід зазначити, що виражене формулою A твердження не містить порочного кола, оскільки спочатку стверджується тільки те, що деяка конкретна формула, явний запис якої отримати нескладно (хоч і громіздко), є недовідною. «Тільки згодом (і, так би мовити, з волі випадку) виявляється, що ця формула — саме та, якою виражено саме це твердження»[17].
У формальній арифметиці S можливо побудувати таку формулу, яка в стандартній інтерпретації[~ 3] є істинною в тому і тільки в тому випадку, коли теорія S є несуперечливою. Для цієї формули виконується твердження другої теореми Геделя:
Іншими словами, несуперечливість формальної арифметики не може бути доведено засобами цієї теорії. Однак, можуть існувати доведення несуперечливості формальної арифметики, що використовують засоби, які неможливо виразити в ній.
Спочатку будується формула Con, яка змістовно виражає неможливість виведення в теорії S якоїсь формули разом з її запереченням. Тоді твердження першої теореми Геделя виражається формулою Con ⊃ G, де G — геделева нерозв'язна формула. Всі міркування для доведення першої теореми може бути виражено і проведено засобами S, тобто в S є вивідною формула Con ⊃ G. Звідси, якщо в S є вивідною Con, то в ній є вивідною й G. Проте, згідно першої теореми Геделя, якщо S є несуперечливою, то G в ній є невивідною. Отже, якщо S є несуперечливою, то в ній є невивідною й формула Con.
23 жовтня 1930 року результати Геделя було представлено Віденській академії наук Гансом Ганом. Основну статтю було отримано для публікації 17 листопада 1930 року і опубліковано на початку 1931 року[18].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.