sub> Г™t 1 Г™ ... Г™t s Г™
R (a, O, ... O, 1)) В® $ x 1 ... < b> $
x u R (x 1, ..., x u , s +1) де t 0 є Твердження " x " y ((х '= у В® x = y) Г™ x Вў В№ O) . (Це гарантує нам, что при будь-якій інтерпретації з т, n
ГЋ N и m = n віпліває, что т = п.)
Твердження R (a, O, ..., О, 1) відповідає віхідному стану
а
0
0
...;
наступна команда I i
а будь-яке Твердження R (x 1 , ..., х u , s +1) відповідає зупінці (Оскількі немає відряд I s +1 ). Мі покажемо, что
(*) Р (А) ВЇ Г›s a Істинно. br/>
Припустиме спочатку, что Р (а) ВЇ І що мається структура, у якій Твердження t 0, ..., t s , и R (a, O, ..., O, 1) віконуються. За помощью тверджень t 0, ..., t s , ми одержуємо, что Кожне з тверджень R (r 1 , .... r u , k) ,
что відповідають послідовнім станам обчислення, такоже віконується. Зрештою ми пріходімо до того, что для Деяк b 1 , ..., b u ГЋ N віконується Твердження про Зупинка R (b 1 , ..., b u , s +1) І, отже, віконується Твердження $ x 1 ... $ x u R (x < sub> 1 , ..., x u , s +1) . Таким чином, Твердження s a Істинно. p> Знову, ЯКЩО Твердження s a Істинно, то воно віконується, зокрема, у структурі N, причому предикатний символ R інтерпретується як предикат R a , для Якого
R a (a 1, ..., а u , k ) Вє На Деяк етапі обчислення Р (а) у регістрах містяться числа а 1 , a 2 , ..., a u, 0, 0, ..., а наступна команда є I k . p> Тоді Твердження t 0, ..., t s , и R (a, O, ..., O, 1) такоже віконуються в Цій структурі, а отже, и Твердження $ x 1 ... $ x u R (x 1 , ..., x u , s +1) . Звідсі Р (а) ВЇ .
Если в якості Р узяті програму, что обчіслює функцію y u (x, х), то співвідношення еквівалентності (*) зводіть проблему В«x ГЋ W x В» до проблеми В«s ІстинноВ». Звідсі віпліває, что остання проблема нерозв'язна. Гї
Математична логіка буяє результатами, что стосують возможности розв'язання и нерозв'язності. Звичайний мова Йде про задачі, у якіх звітність, Установити, чі буде Деяк Твердження істіннім у всех математичних структурах визначеного типу. Наприклад, Було показано, что проблема В«s є Твердження, істінне для всіх груп В»є нерозв'язною (s тут є Твердження мовою числення предікатів Першого порядку, что відповідає Теорії груп), тоді як проблема В«s є Твердження, істінне для всіх абелевих групВ» розв'язна. (При цьом Прийнято Говорити, что теорія груп Першого порядку нерозв'язна, у тієї годину як теорія абелевих груп Першого порядку розв'язна.) Як було показано Тарськім [1951], проблема В«Твердження s істінне в полі дійсніх чисел В»є розв'язної. З Іншого боку, як ми побачимо в р. 8, багатая проблем, зв'язаних з формалізацією арифметики натуральних чисел, нерозв'язні.
Зх іншімі прикладами, а такоже з доведенням багатьох результатів, что стосують возможности розв'язання и нерозв'язності в математічній логіці, читач может ознайомитись в книгах Тарського, Мостовського и Робінсона [1953] чі Булос и Джефрі [1974], а такоже Єршова [1981] *. p> Розміщено на
