Кіріспе

Математикалық логикадағы мәлімдеме – математикалық логикадағы түсінік.

Математикалық логикада диагональдық лемма (диагонализация леммасы, өзіне сілтеме жасау леммасы немесе бекітілген нүкте теоремасы деп те аталады) табиғи сандардың белгілі бір формальды теорияларында өзіне сілтемелі сөйлемдердің бар екенін дәлелдейді, атап айтқанда, барлық есептелетін функцияларды бейнелей алатын жеткілікті күшті теорияларда. Диагональдық лемма арқылы бар екені қамтамасыз етілген сөйлемдер, өз кезегінде, Гёдельдің толық еместік теоремалары және Тарскидің анықталмау теоремасы сияқты маңызды шектеулер туралы нәтижелерді дәлелдеуге қолданылуы мүмкін.

Өмірбаян

Let - бұл натурал сандар жиыны. Арифметика тіліндегі бірінші реттік теория, егер тілінде "граф" формуласы болса, есептеу функциясын көрсетеді, яғни кез келген үшін формула болады. Мұнда - бұл натурал санға сәйкес келетін сан, ол ішіндегі презумпцияланған бірінші санның -шы мұрагері ретінде анықталады. Диагональдық лемма сонымен қатар әр формулаға табиғи санды (сонымен қатар ) тағайындаудың жүйелі тәсілін қажет етеді, ол оның Гёдель саны деп аталады. Формулалар осыдан кейін олардың Гёдель сандарына сәйкес келетін сандар арқылы ішінде көрсетіледі. Мысалы, - бұл арқылы көрсетіледі.

Диагональдық лемма барлық примитивті рекурсивті функцияларды бейнелей алатын теорияларға қолданылады. Мұндай теорияларға бірінші реттік Пеано арифметикасы және одан әлсіз Робинсон арифметикасы, тіпті R деп аталатын одан да әлсіз теория жатады. Лемманың кең таралған тұжырымы (төменде келтірілгендей) теория барлық есептелетін функцияларды көрсете алады деген күшейтілген талап қояды, бірақ аталған барлық теориялардың да осындай мүмкіндігі бар.

Лемманың мәлімдемесі

Интуитивті түрде, бұл өзіне-өзі сілтеме жасайтын сөйлем: ол сөйлемнің қасиеті екенін айтады. Сөйлемді берілген сөйлемнің эквиваленттілік класына сол сөйлемнің эквиваленттілік класын тағайындайтын операцияның тұрақты нүктесі ретінде де қарастыруға болады (сөйлемнің эквиваленттілік класы – бұл теорияда дәлелмен балама екені көрсетілген барлық сөйлемдердің жиынтығы). Дәлелдемеде құрастырылған сөйлем сөзбе-сөз бірдей емес, бірақ теорияда оған балама екені дәлелденеді.

Тарих

Лемма "диагональды" деп аталады, себебі ол Кантордың диагональдық аргументімен кейбір ұқсастықтарға ие. "Диагональдық лемма" немесе "тұрақты нүкте" терминдері Курт Гёдельдің 1931 жылғы мақаласында немесе Альфред Тарскидің 1936 жылғы мақаласында кездеспейді. Рудольф Карнап (1934) жалпы өзіне сілтеме жасайтын лемманы алғаш рет дәлелдеді, ол белгілі бір шарттарды қанағаттандыратын теория T-дегі кез келген формула F үшін, T-де ψ ↔ F(°#(ψ)) формуласының дұрыс екенін көрсетеді. Карнаптың жұмысы балама тілде жазылған, өйткені 1934 жылы есептеуге болатын функциялар туралы түсінік толыққанды қалыптаспаған. Мендельсон (1997, 204-бет) Карнаптың Гёдельдің ойлауында диагональдық лемма сияқты нәрсе болғанын алғаш айтқанын санайды. Гёдель 1937 жылға қарай Карнаптың еңбегімен таныс болған. Диагональдық лемма есептеу теориясындағы Клейннің рекурсия теоремасымен тығыз байланысты, және олардың дәлелдемелері ұқсас.