KNOW INTUIT, Лекция, Аритметика на изчислими функции
Теоремите на Тарски и Гьодел
Тъй като графиките на изчислимите функции са аритметични, очевидно е, че разрешимите и изброимите множества също ще бъдат аритметични. Така можем да оправдаем името "аритметична йерархия" за класовете и :
Теорема 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 е номерът (в номерацията на всички формули без параметри) на формулата, която ще се получи, ако константата r се замести с този параметър в q-тата формула с един параметър". Свойството, изписано в кавички, описва графиката на някаква изчислима функция (съответстваща на прости синтактични операции и преход от едно номериране към друго) и следователно има формула, която го изразява.
И така, ние сме написали някаква формула с един параметър x. Нека има някакво число N . Нека заместим това число N вместо неговия параметър. Ще се получи някаква формула без параметри. От конструкцията се вижда, че тази формула е вярна тогава и само тогава, когато резултатът от заместването на числото N във формулното число N (т.е. самата тази формула!) Е невярно.
Полученото противоречие завършва директното доказателство на теоремата на Тарски. Виждаме, че се нуждаехме от изразимост в аритметиката не на изчислими функции, а на еднадоста специфичен. С достатъчно търпение съответната формула все още може да бъде написана и по този начин доказателството ще стане напълно "осезаемо".
Сега представяме доказателството на теоремата на Гьодел в същия стил. Както вече казахме, смятането е механизъм (алгоритъм), който ви позволява да генерирате някои формули на аритметичния език (за простота ще приемем, че се генерират само формули без параметри). Така възниква някакво изброимо множество, което обикновено се дава като проекция на разрешимо множество. А именно, те въвеждат определено понятиедоказателство. Освен това доказателствата са думи в някаква азбука. Наборът от доказателства е разрешим, т.е. има алгоритъм, който разграничава истинските доказателства от текстове, които не са. В допълнение, има (също разрешимо) свойство на двете думи x и y, което казва, че x е доказателство на формулата y. Преномерирайки всички доказателства и формули и изразявайки посочените разрешими свойства на езика на аритметиката, стигаме до формулата Доказателство (x,y) , която е вярна, когато x е номерът на доказателството на формулата с числото y .
Сега нека напишем формула с един параметър x , която казва, че резултатът от заместването на числото x вместо параметър в x -та формула с един параметър няма доказателство:
Тази формула има един параметър ( x ); нека неговият номер в номерацията на такива формули е равен на N . Заменете N за параметъра. Получава се формула без параметри.По конструкция формулата е вярна,когато резултатът от заместването на N в N -тата формула с един параметър е недоказуем. И този резултат е самата формула, така че е верен тогава и само ако не е доказуем. Това означава, че нашето смятане или ни позволява да докажем невярна формула (ако е невярна, в който случай се нарича неадекватна), или нени позволява да докажем истинската формула
Имайте предвид, че и двете от тези доказателства напомнят както за конструкцията на фиксирана точка, така и за класическия парадокс на лъжеца: