НОУ ІНТУІТ, Лекція, Арифметичність обчислюваних функцій
Теореми Тарського та Геделя
Оскільки графіки функцій, що обчислюються, арифметичні, очевидно, розв'язувані і перераховані множини теж будуть арифметичними. Тим самим ми можемо виправдати назву "арифметична ієрархія" для класів та:
Теорема 68. При будь-якому n будь-яка множина з класу або арифметично (є формула арифметики, що виражає належність цій множині).
Після того, як ми довели арифметичність обчислюваних функцій, все ясно множини з класів і виходять навішуванням кванторів на розв'язувані множини, а розв'язувана безліч арифметично.
Правильне і протилежне:
Теорема 69. Будь-яке арифметичне безліч лежить у класі чи деякого n (і, звісно, всім великих n ).
Формулу, що задає арифметичну множину, приведемо до попередньої нормальної форми (винісши квантори назовні). Ясно, що безкванторна частина задає розв'язувану множину, тому вихідна множина належить якомусь із класів або .
Можна і використовувати попередньої нормальної форми, а застосувати індукцію за довжиною формули і послатися те що, що перетин , об'єднання і доповнення , і навіть проекція не виводять межі арифметичної ієрархії (об'єднання всіх класів і ).
Розглянемо тепер безліч T , елементами якого є всі справжні арифметичні формули без параметрів (точніше, їх номери в якійсь нумерації всіх формул це означає, що за формулою можна алгоритмічно отримати її номер і навпаки).
Теорема 70. Будь-яке арифметичне безліч m-зводиться до безлічі T.
Це твердження майже очевидне. Нехай A довільна арифметична множина. Нехай формула з однією змінною, яка виражає належністьмножині A . Це означає, що істинно при тих і тільки n , які належать A . Тоді обчислювана функція n номер формули, яка є результатом підстановки константи n m зводить A до T .
Теорема 71. Безліч T не арифметична.
Після проведеної нами підготовки це твердження очевидно: якби T було арифметичним, воно лежало б у певному конкретному класі . Оскільки всяка арифметична множина зводиться до T , то за теоремою 53 всі арифметичні множини лежали б у цьому класі. Але ми знаємо, що безліч із вищих класів ієрархії теж арифметичні, але не лежать.
Ця теорема називається теоремою Тарського. Її можна прочитати так: безліч арифметичних істин не є арифметичною. Або: поняття арифметичної істини невимовно в арифметиці.
Теорема 72. Безліч T арифметичних істин неперелічимо.
Насправді, будь-яке перелічене безліч арифметично.
Це твердження називається теоремою Геделя про неповноту. Його можна переформулювати так: будь-яке обчислення, що породжує формули арифметики (е алгоритм , що перераховує деяку кількість таких формул) абонеадекватно(породжує деяку хибну формулу), абонеповно(не породжує деякої істинної формули ).
85. Покажіть, що для будь-якого N безліч усіх істинних замкнутих арифметичних формул, що містять не більше N кванторів, арифметично.
86. Сформулюйте та доведіть аналогічне твердження для формул обмеженої кванторної глибини (число вкладених кванторів) та для формул з обмеженим числом змін кванторів у попередній нормальній формі.
Прямий доказ теорем Тарського та Геделя
У нашому викладі теореми Тарського та Геделя вийшли як простінаслідки визначень та фактів, пов'язаних з теорією алгоритмів. З одного боку, це дозволяє краще зрозуміти місце цих теорем у загальному контексті математичної логіки та теорії алгоритмів. З іншого боку, виникає природне бажання розгорнути ланцюжок та отримати більш прямі докази. Такі ми зараз і наведемо.
Починаючи доводити теорему Тарського, припустимо, що безліч номерів усіх арифметичних формул (без параметрів) арифметично. Нехай T це множина, а відповідна формула. Перенумеруємо також усі формули з одним параметром x; нехай Fn(x) формула, що має номер n у цій нумерації. Розглянемо формулу з єдиним параметром x , що стверджує, що результат підстановки константи x x -у формулу з параметром кладений. Цю формулу можна написати так:
де Subst(p,q,r) формула з трьома параметрами, що виражає таку властивість: p є номер (у нумерації всіх формул без параметрів) тієї формули, яка вийде, якщо в q-ю формулу з одним параметром підставити константу r замість цього параметра". Записане в лапках властивість описує графік деякої обчислюваної функції (що відповідає простим синтаксичним діям і переходу від однієї нумерації до іншої) і тому існує формула, що виражає його.
Отже, написали деяку формулу з єдиним параметром x . Нехай вона має номер N . Підставимо цей номер N замість її параметра. Вийде деяка формула без параметрів. З побудови видно, що ця формула істинна тоді й лише тоді, коли результат підстановки числа N формулу номер N (тобто сама ця формула!) складний.
Отримане протиріччя завершує прямий доказ теореми Тарського. Ми бачимо, що нам знадобилася виразність в арифметиці не будь-яких обчислюваних функцій, а однієїцілком конкретною. При достатньому терпінні відповідну формулу можна написати, і тим самим доказ стане зовсім "відчутним".
Тепер викладемо у тому стилі доказ теореми Геделя. Як ми вже говорили, обчислення це механізм (алгоритм), який дозволяє породжувати деякі формули мови арифметики (для простоти вважатимемо, що породжуються лише формули без параметрів). Таким чином, виникає деяка множина, яку зазвичай задають як проекцію розв'язуваної множини . Саме вводять деяке поняттядокази. При цьому докази є словами у певному алфавіті. Безліч доказів можна розв'язати, тобто алгоритм , який відрізняє справжні докази від текстів, які такими не є. Крім того, є (також можна розв'язати) властивість двох слів x і y , яке свідчить, що x є доказ формули y . Перенумерувавши всі докази та формули і висловивши зазначені розв'язні властивості у мові арифметики, ми приходимо до формули Proof (x,y) , яка є істинною, коли x є номером доказу формули з номером y .
Тепер напишемо формулу з одним параметром x , яка говорить, що результат підстановки числа x замість параметра x -у формулу з одним параметром не має доказу:
Ця формула має єдиний параметр (x); нехай її номер у нумерації таких формул дорівнює N . Підставимо N замість параметра. Вийде формула без параметрів За побудовою формула істинна, коли результат підстановки N до N -ї формули з одним параметром недоказуємо. А цей результат є сама формула, так що вона істинна тоді і тільки тоді, коли недоведена. Значить, наше літочислення або дозволяє довести хибну формулу (якщо хибна; у такому разі його називають неадекватним), або недозволяє довести справжню формулу
Зауважимо, що обидва ці докази нагадують як побудову нерухомої точки, так і класичний парадокс брехуна: