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

1. У первісній формі [ правити | правити код ]
2. Інтерпретація нерозв'язною формули [ правити | правити код ]
3. У формі Россера [ правити | правити код ]
4. Інтерпретація нерозв'язною формули [ правити | правити код ]
5. Узагальнені формулювання [ правити | правити код ]
6. Поліноміальна форма [ правити | правити код ]
7. Малюнок докази [ правити | правити код ]
8. Зв'язок з парадоксами [ правити | правити код ]
9. Малюнок докази [ правити | правити код ]

Теорема Геделя про неповноту і друга теорема Геделя [~ 1] - дві теореми математичної логіки про принципові обмеження формальної арифметики і, як наслідок, будь-якої формальної системи , В якій можна визначити основні арифметичні поняття: натуральні числа , 0 , 1 , складання і множення .

Перша теорема стверджує, що якщо формальна арифметика несуперечлива, то в ній існує невиводимість і незаперечна формула.

Друга теорема стверджує, що якщо формальна арифметика несуперечлива, то в ній невиведені деяка формула, змістовно яка стверджує несуперечність цієї арифметики.

Обидві ці теореми були доведені Куртом Геделем в 1930 році (опубліковані в 1931) і мають безпосереднє відношення до другий проблеми з знаменитого списку Гільберта .

У первісній формі [ правити | правити код ]

У своїй формулюванні теореми про неповноту Гедель використовував поняття ω-несуперечливої ​​формальної системи - більш сильне умова, ніж просто несуперечливість. Формальна система називається ω-несуперечливої, якщо для будь-якої формули A (x) цієї системи неможливо одночасно вивести формули А (0), А (1), А (2), ... і ∃ x ¬ A (x) (іншими словами, з того, що для кожного натурального числа n виведена формула A (n), слід невиводимість формули ∃ x ¬ A (x)). Легко показати, що ω-несуперечливість тягне просту несуперечність (тобто, будь-яка ω-несуперечлива формальна система несуперечлива) [6] .

У процесі доведення теореми будується така формула A арифметичної формальної системи S, що [6] :

S несуперечлива, то формула A невиведені в S; якщо система S ω-несуперечлива, то формула ¬A невиведені в S. Таким чином, якщо система S ω-несуперечлива, то вона неповна [~ 2] і A є прикладом нерозв'язною формули.

Формулу A іноді називають гёделевой нерозв'язною формулою [7] .

Інтерпретація нерозв'язною формули [ правити | правити код ]

У стандартній інтерпретації [~ 3] формула A означає «не існує виведення формули A», тобто стверджує свою власну невиводимість в S. Отже, за теоремою Геделя, якщо тільки система S несуперечлива, то ця формула і справді невиведені в S і тому істинна в стандартній інтерпретації. Таким чином, для натуральних чисел формула A вірна, але в S невиведені [8] .

У формі Россера [ правити | правити код ]

У процесі доведення теореми будується така формула B арифметичної формальної системи S, що [9] :

Якщо формальна система

S несуперечлива, то в ній невиведені обидві формули B і ¬B; інакше кажучи, якщо система S несуперечлива, то вона неповна [~ 2] , І B є прикладом нерозв'язною формули.

Формулу B іноді називають россеровой нерозв'язною формулою [10] . Ця формула трохи складніше гёделевой.

Інтерпретація нерозв'язною формули [ правити | правити код ]

У стандартній інтерпретації [~ 3] формула B означає «якщо існує висновок формули B, то існує висновок формули ¬ B». Згідно ж теоремі Геделя в формі Россера, якщо формальна система S несуперечлива, то формула B в ній невиведені; тому, якщо система S несуперечлива, то формула B вірна в стандартній інтерпретації [11] .

Узагальнені формулювання [ правити | правити код ]

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

Будь-яка досить сильна рекурсивно аксіоматізіруемая несуперечлива теорія першого порядку неповна.

Зокрема, теорема Геделя справедлива для кожного несуперечливого звичайно аксіоматізіруемого розширення арифметичної формальної системи S.

Поліноміальна форма [ правити | правити код ]

Після того як Юрій Матіясевіч довів диофантово будь-якого ефективно перечислимого безлічі і були знайдені приклади універсальних діофантових рівнянь , З'явилася можливість сформулювати теорему про неповноту в полиномиальной (або диофантово) формі [13] [14] [15] [16] :

Для кожної несуперечливої теорії

T можна вказати таке ціле значення параметра K, що рівняння (elg 2 + α - (b - xy) q 2) 2 + (q - b 5 60) 2 + (λ + q 4 - 1 - λ b 5) 2 + (θ + 2 z - b 5) 2 + (u + t θ - l) 2 + (y + m θ - e) 2 + (n - q 16) 2 + ((g + eq 3 + lq 5 + (2 (e - z λ) (1 + xb 5 + g) 4 + λ b 5 + λ b 5 q 4) q 4) (n 2 - n) + (q 3 - bl + l + θ λ q 3 + (b 5 - 2) q 5) (n 2 - 1) - r) 2 + (p - 2 ws 2 r 2 n 2) 2 + (p 2 k 2 - k 2 + 1 - τ 2 ) 2 + (4 (c - ksn 2) 2 + η - k 2) 2 + (r + 1 + hp - h - k) 2 + (a - (wn 2 + 1) rsn 2) 2 + (2 r + 1 + φ - c) 2 + (bw + ca - 2 c + 4 α γ - 5 γ - d) 2 + ((a 2 - 1) c 2 + 1 - d 2) 2 + ((a 2 - 1) i 2 c 4 + 1 - f 2) 2 + (((a + f 2 (d 2 - a)) 2 - 1) (2 r + 1 + jc) 2 + 1 - (d + of) 2 ) 2 + (((z + u + y) 2 + U) 2 + y - K) 2 = 0 {\ displaystyle {\ begin {aligned} & (elg ^ {2} + \ alpha - (b-xy) q ^ {2}) ^ {2} + (qb ^ {5 ^ {60}}) ^ {2} + (\ lambda + q ^ {4} -1- \ lambda b ^ {5}) ^ {2} + \\ & (\ theta + 2z-b ^ {5}) ^ {2} + (u + t \ theta -l) ^ {2} + (y + m \ theta -e) ^ {2} + (nq ^ {16}) ^ {2} + \ \ & ((g + eq ^ {3} + lq ^ {5} + (2 (ez \ lambda) (1 + xb ^ {5} + g) ^ {4} + \ lambda b ^ {5} + \ lambda b ^ {5} q ^ {4}) q ^ {4}) (n ^ {2} -n) + \\ & (q ^ {3} -bl + l + \ theta \ lambda q ^ {3} + (b ^ {5} -2) q ^ {5}) (n ^ {2} -1) -r) ^ {2} + \\ & (p-2ws ^ {2} r ^ {2} n ^ {2}) ^ {2} + (p ^ {2} k ^ {2} -k ^ {2} + 1 \ tau ^ {2}) ^ {2} + \\ & (4 (c- ksn ^ {2}) ^ {2} + \ eta -k ^ {2}) ^ {2} + (r + 1 + hp-hk) ^ {2} + \\ & (a- (wn ^ {2 } +1) rsn ^ {2}) ^ {2} + (2r + 1 + \ phi -c) ^ {2} + \\ & (bw + ca-2c + 4 \ alpha \ gamma -5 \ gamma - d) ^ {2} + \\ & ((a ^ {2} -1) c ^ {2} + 1-d ^ {2}) ^ {2} + ((a ^ {2} -1) i ^ {2} c ^ {4} + 1-f ^ {2}) ^ {2} + \\ & (((a + f ^ {2} (d ^ {2} -a)) ^ {2} -1) (2r + 1 + jc) ^ {2} + 1- (d + of) ^ {2}) ^ {2} + \\ & (((z + u + y) ^ {2} + u ) ^ {2} + yK) ^ {2} = 0 \ end {aligned}}} не має рішень в невід'ємних цілих числах, але цей факт не може бути доведений в теорії T. Більш того, для кожної несуперечливої теорії безліч значень параметра K, що володіють такою властивістю, нескінченно і алгоритмічно неперечіслімо .

Ступінь даного рівняння може бути знижена до 4 ціною збільшення кількості змінних.

Малюнок докази [ правити | правити код ]

У своїй статті Гедель дає начерк основних ідей докази [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 натуральних чисел наступним чином:

n

∈ K ≡ ¬Bew [R (n); n] (*)

(де Bew x означає: x - виведена формула [~ 6] ). Так як всі визначальні поняття з цього визначення можна виразити в S, то це ж вірно і для поняття K, яке з них побудовано, тобто є таке клас-вираз C, що формула [C; n], інтуїтивно интерпретируемая, позначає, що натуральне число n належить K. Як клас-вираз, C ідентично деякому певному R (q) в нашій нумерації, тобто

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 є аналогом парадоксу брехуна . Міркування Геделя в цілому дуже схожі на парадокс Рішара . Більш того, для доказу існування невиводимість тверджень може бути використаний будь-який семантичний парадокс [18] .

Слід зазначити, що виражається формулою A твердження не містить порочного кола, оскільки спочатку затверджується тільки, що деяка конкретна формула, явну запис якої отримати нескладно (хоч і громіздко), недовідна. «Тільки згодом (і, так би мовити, з волі випадку) виявляється, що ця формула в точності та, якій висловлено саме це твердження» [18] .

У формальної арифметики S можна побудувати таку формулу, яка в стандартній інтерпретації [~ 3] є істинною в тому і тільки в тому випадку, коли теорія S несуперечлива. Для цієї формули справедливе твердження другий теореми Геделя:

Якщо формальна арифметика

S несуперечлива, то в ній невиведені формула, змістовно яка стверджує несуперечність S.

Іншими словами, несуперечливість формальної арифметики не може бути доведена засобами цієї теорії. Однак, можуть існувати доказу несуперечності формальної арифметики, що використовують кошти, невимовні в ній.

Малюнок докази [ правити | правити код ]

Спочатку будується формула Con, змістовно виражає неможливість виведення в теорії S будь-якої формули разом з її запереченням. Тоді твердження першої теореми Геделя виражається формулою Con ⊃ G, де G - Гёделева нерозв'язна формула. Всі міркування для доказу першої теореми можуть бути виражені і проведені засобами S, тобто в S виведена формула Con ⊃ G. Звідси, якщо в S виведена Con, то в ній виводиться і G. Однак, згідно з першою теоремою Геделя, якщо S несуперечлива, то G в ній невиведені. Отже, якщо S несуперечлива, то в ній невиведені і формула Con.

Ще на початку XX століття Давид Гільберт проголосив мету аксіоматизована всю математику, і для завершення цього завдання залишалося довести несуперечність і логічну повноту арифметики натуральних чисел . 7 вересня 1930 року в Кенігсберзі проходив науковий конгрес з підстав математики, і на цьому конгресі 24-річний Курт Гедель вперше оприлюднив дві фундаментальні теореми про неповноту, які показали, що програма Гільберта не може бути реалізована: при будь-якому виборі аксіом арифметики існують теореми, які неможливо ні довести, ні спростувати простими (фінітними) засобами, передбаченими Гильбертом, а фінітного доказ несуперечності арифметики неможливо [19] .

Цей виступ не було заявлено заздалегідь і справило приголомшливий ефект, Гедель відразу став всесвітньою знаменитістю, а програма Гільберта по формалізації основ математики зажадала термінового перегляду. 23 жовтня 1930 року результати Геделя були представлені Віденської академії наук Хансом Ханом . Стаття з обома теоремами ( «Про принципово нерозв'язних положеннях в системі Principia Mathematica і споріднених їй системах») була опублікована в науковому щомісячнику Monatshefte für Mathematik und Physik в 1931 році. Хоча доказ другий теореми Гедель дав тільки у вигляді ідеї, його результат було настільки очевидним і незаперечним, що ні викликав сумнівів ні у кого. Гільберт відразу визнав цінність відкриттів Геделя; перші повні докази обох теорем були опубліковані в книзі Гільберта і Бернайса «Підстави математики» (1938). У передмові до другого тому автори визнали, що для досягнення поставленої мети фінітних методів недостатньо, і додали в число логічних засобів трансфинитное індукцію ; в 1936 році Герхард Генцен зумів довести за допомогою цієї аксіоми несуперечливість арифметики, проте логічна повнота так і залишилася недосяжною [19]

Фахівці дають найрізноманітніші, іноді навіть полярні оцінки історичної значимості теорем Геделя. Частина вчених вважає, що ці теореми «перевернули» підстави математики або навіть всю теорію пізнання , І значення геніального відкриття Геделя буде поступово відкриватися ще довгий час [20] . Інші ж (наприклад, Бертран Рассел ) Закликають не перебільшувати, оскільки теореми спираються на ФІНІТНОГО формалізм Гільберта [21] [22] .

Розглянемо, наприклад, наступний доказ несуперечності арифметики [24] .

З точки зору повсякденної людської логіки, це доказ прийнятно і переконливо. Але воно не може бути записано за правилами теорії доказів Гільберта, оскільки в цих правилах семантика замінена на синтаксис, а істинність - на «виводимість» [24] . У будь-якому випадку теореми Геделя підняли філософію математики на новий рівень.

Коментарі

1. ↑ Іноді згадується як друга теорема Геделя «про докази несуперечності» [1] , «Про неповноту» [2] [3] [4] , «Про неповноту арифметики» [5] .
2. ↑ 1 2 Формальна система, що містить нерозв'язну, тобто не виводиться і незаперечну, формулу, називається неповною.
3. ↑ 1 2 3 4 Інтерпретація формул теорії S називається стандартною, якщо її областю є безліч невід'ємних цілих чисел, символ 0 інтерпретується числом 0, функціональні букви ', +, • інтерпретуються додатком одиниці, складанням і множенням відповідно, предикатна буква = інтерпретується відношенням тотожності.
4. ↑ Гедель використовував систему Principia Mathematica Уайтхед і Рассела із застереженням, що міркування застосовні до широкого класу формальних систем
5. ↑ Подібне зіставлення формул і натуральних чисел називається арифметизации математики і було здійснено Геделем вперше. Ця ідея згодом стала ключем до вирішення багатьох важливих завдань математичної логіки. Див. Гёделева нумерація
6. ↑ «Bew» скор. від нього. «Beweisbar» - доказовий, виведений

джерела

1. ↑ Кліні +1957 с.513
2. ↑ чл.-кор. РАН Лев Дмитрович Беклемішев в «Запровадження в математичну логіку»
3. ↑ Тлумачний словник по обчислювальним системам - Page 205
4. ↑ Доповіді Академії наук СРСР, Volume 262 - Page 799 (1982)
5. ↑ Известия Академии наук СССР, Volume 50 - Page 1140 (1986)
6. ↑ 1 2 Кліні +1957 с.187
7. ↑ Мендельсон тисячі дев'ятсот сімдесят один с.165
8. ↑ Це міркування запозичене з Мендельсон 1 971 с.160
9. ↑ Див., Наприклад, Кліні 1957 с.188
10. ↑ Мендельсон тисячі дев'ятсот сімдесят один с.162
11. ↑ Мендельсон тисячі дев'ятсот сімдесят один с.162-163
12. ↑ Мендельсон тисячі дев'ятсот сімдесят один с.176
13. ↑ Jones JP, Undecidable diophantine equations
14. ↑ Martin Davis, Diophantine Equations & Computation
15. ↑ Martin Davis, The Incompleteness Theorem
16. ↑ К. Поднієкс, Теорема Геделя в диофантово формі
17. ↑ Gödel, Kurt. On Formally Undecidable Propositions of the Principia Mathematica and Related Systems. I. - 1931. в книзі Davis, Martin (ed.). The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. - New York: Raven Press, 1965. - С. 6-8.
18. ↑ 1 2 Гедель 1931
19. ↑ 1 2 Пінєйро, 2015 , С. 13, 48-49, 66, 89-90.
20. ↑ Stephen Hawking . Godel and the End of the Universe (неопр.). Дата обігу 8 квітня 2018.
21. ↑ Михайлова Н. В. Проблема обгрунтування сучасної математики в контексті нових філософсько-методологічних криз // Філософія математики: актуальні проблеми. Математика і реальність. Тези Третьої всеросійської наукової конференції; 27-28 вересня 2013 р . - М.: Центр стратегічної кон'юнктури, 2013. - С. 187. - 270 с. - ISBN 978-5-906233-39-4 .
22. ↑ Музикантський А. .
23. ↑ Лівіо, Маріо. Чи був Бог математиком? Глава «Істина в неповноті». - М.: АСТ, 2016. - 384 с. - (Золотий фонд науки). - ISBN 978-5-17-095136-9 .
24. ↑ 1 2 Пінєйро, 2015 , С. 155-162.

• Бірюков Б. В. , Очеретів В. Н. Жар холодних чисел і пафос безпристрасно логіки. Формалізація мислення від античних часів до епохи кібернетики. - М.: Едіторіал УРСС, 2004. - 232 с. - ISBN 5-354-00310-5 .
• Єршов Ю. Л. Доказовість в математиці , програма А. Гордона від 16 червня 2003 року.
• Єршов Ю. Л. , Палютін Е.А. Математична логіка. - М.: Наука, 1987. - 336 с.
• Кліні Стефен Коул. Введення в метаматематику . - М.: ІЛ, 1957. - 526 с.
• Кліні Стефен Коул. математична логіка . - М.: «Мир», 1973. - 480 с.
• Кордонський М. кінець істини . - ISBN 5-946448-001 -04.
• Коен П. Дж. Про підстави теорії множин // Успіхи математичних наук . - 1974. - Т. 29, № 5 (179). - С. 169-176.
• Мендельсон Елліот. Введення в математичну логіку . - М.: «Наука», 1971. - 320 с.
• Паршин А. Н. Роздуми над теоремою Геделя // Історико-математичні дослідження . - М.: Янус-К, 2000. - № 40 (5). - С. 26-55.
• Пінєйро Г. Е. У інтуїції є своя логіка. Гедель. Теореми про неповноту // Наука. Найбільші теорії. - М.: Де Агостіні, 2015. - Вип. 17. - ISSN 2409-0069 .
• Сосінскій А. Б. теорема Геделя // Літня школа «Сучасна математика» . - Дубна, 2006.
• Успенський В. А. Теорема Геделя про неповноту . - М.: Наука, 1982. - 110 с. - ( Популярні лекції з математики ).
• Успенський В. А. Теорема Геделя про неповноту і чотири дороги, що ведуть до неї // Літня школа «Сучасна математика» . - Дубна, 2007.
• Davis, Martin (ed.). The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems And Computable Functions. - New York: Raven Press, 1965. - 440 p.
• Heijenoort, Jean van (ed.). From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931. - Cambridge, Massachusetts: Harvard University Press, 1967. - 660 p.

• 1931 Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme , I. Monatshefte für Mathematik und Physik 38: 173-198.
• 1931 Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme , I. and On formally undecidable propositions of Principia Mathematica and related systems I in Solomon Feferman , Ed., 1986. Kurt Gödel Collected works, Vol. I. Oxford University Press: 144-195.

Оригінальний німецький текст з паралельним англійським перекладом, з елементарним введенням, написаним Стівеном Кліні .

• 1951 Some basic theorems on the foundations of mathematics and their implications in Solomon Feferman , Ed., 1995. Kurt Gödel Collected works, Vol. III. Oxford University Press: 304-323.