(Теорема про нерозв'язність числення предікатів)
Найпростішою логічною системою, у якій знаходять Висвітлення деякі аспекти математичного мислення, є числення вісловлень. У цьом чісленні складні Твердження будуються з Деяк основних вісловлень помощью сімволів, что позначають логічні зв'язки В«неВ», В«іВ», В«чиВ» и В«волочитисяВ». Досить легко переконатіся в тому, что ЯКЩО числення вісловлень визначене й достатньо акуратно, то воно розв'язне. Це означає, что існує ефективна процедура решение питання про ті, чи є ті чі Інше Твердження цього числення (тотожня) істіннім, тоб Справедливість у всех можливіть сітуаціях. Алгоритм цього дається методом істіннісніх таблицю, добро знайомиться багатая читачам.
Більш широкими можливіть, чем числення вісловлень, володіє логічна система, что назівається Чисельність предікатів (Першого порядку). мовою цього числення можна формалізуваті значний Частину всієї математики. Основні Твердження в ньом формуються Із сімволів, что представляються індівідуальні об'єкти (чі елєменти), и предікатів и функцій на них. Складні Твердження будуються з Основна з використаних логічніх сімволів числення вісловлень, а такоже сімволів "і $.
Мається точне Поняття доведення Твердження числення предікатів, причому Твердження доводитися тоді и Тільки тоді, коли воно Істинно. У 1936 году Черч показавши, что доведеність (і, отже, істінність) у чісленні предікатів нерозв'язна на відміну від більш простого пропозіціонального числення. (Гільберт вважаєтся цею результат самим фундаментальної результатом, что стосується нерозв'язності, у всій математіці.)
Просте доведення нерозв'язності проблеми істінності можна дати з використаних МНР, хочай це вімагає Деяк Знайомство з Чисельність предікатів. Читач, что НЕ знайомиться з качанами логікі предікатів, мі Радимо Пропустити привидів нижчих зразок доведення.
5.1. Теорема. Проблема істінності числення предікатів Першого порядку нерозв'язна.
Доведення. (Тім, хто НЕ знайомиться з Чисельність предікатів, рекомендується Пропустити.)
Нехай Р - Деяка программа в стандартному віді, что містіть відряд I 1 , ..., I s , и нехай u = r (P) (визначення див. В§ 2 р. 2). Ми будемо використовуват наступні позначені сімволів числення предікатів:
O - індівідній символ,
'- символ одномісної Функції (Значення Якої на х дорівнює х '),
R-символ ( U +1 ) - місного відношення,
x 1 , x 2 , ..., x a , у - символи індівідніх змінніх.
Далі, для будь-якої відряд I i , можна записатися Твердження числення предікатів t i , что опісує результат Виконання відряд I i. При цьом мі вікорістовуємо символ Г™ для позначені зв'язки В«іВ» и символ В® для позначені імплікації. Твердження t i , візначається в такий способ:
(a) ЯКЩО I i = Z (n), тo t i, є Твердження
" x 1 ... " x u : R (X 1 , ..., x n , ..., x u , i) В® < b> R (x 1 , ..., O, ..., x u , i Вў )
(b) ЯКЩО I i = S (n) , то t i, є Твердження
" x 1 ... " x u : R (X 1 , ..., x n , ..., x u , i) В® < b> R (x 1 , ..., X n Вў , ..., x u , i Вў )
(c) ЯКЩО I i = T (m, n ), тo t i, є Твердження
" x 1 ... " x u : R (X 1 , ..., x n , ..., x u , i) В® < b> R (x 1 , ..., X m , ..., x u , i Вў )
(d) ЯКЩО I i = J (m, n, q ), тo t i, є Твердження
" x 1 ... " x u : R (X 1 , ..., x u , i) В® ((x m = x n В® R (x 1 , ..., x u , q)) Г™ (x m В№ x n В® R (x 1 , ..., X u , i Вў )))
Нехай тепер для будь-якого а ГЋ N символ s a позначає Твердження.
( t 0
