Мы показываем, что, в противоположность теореме Тарского о неопределимости1, арифметическая истинность определима в арифметике второго ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Булос Д.N. Вычислимость и логика


Мы показываем, что, в противоположность теореме Тарского о неопределимости1, арифметическая истинность определима в арифметике второго порядка, а некоторые аппроксимации арифметической истинности могут быть определены и в арифметике первого порядка. Затем доказывается теорема Аддисона, гласящая, что класс множеств ( натуральных чисел), определимых в арифметике, сам в арифметике не определим. Затем мы приводим теорему Пресбургера о том, что арифметика становится разрешимой, если убрать из нее умножение. Доказывается интерполяционная лемма Крейга, из которой выводятся теорема Робинсона о непротиворечивости и теорема Бета об определимости. Наконец, мы устанавливаем разрешимость мона-дической логики с равенством и неразрешимость логики без равенства, содержащей единственный двуместный предикатный символ.

(cкачать страницу)

Смотреть книгу на libgen

Мы показываем, что, в противоположность теореме Тарского о неопределимости1, арифметическая истинность определима в арифметике второго порядка, а некоторые аппроксимации арифметической истинности могут быть определены и в арифметике первого порядка. Затем доказывается теорема Аддисона, гласящая, что класс множеств ( натуральных чисел), определимых в арифметике, сам в арифметике не определим. Затем мы приводим теорему Пресбургера о том, что арифметика становится разрешимой, если убрать из нее умножение. Доказывается интерполяционная лемма Крейга, из которой выводятся теорема Робинсона о непротиворечивости и теорема Бета об определимости. Наконец, мы устанавливаем разрешимость мона-дической логики с равенством и неразрешимость логики без равенства, содержащей единственный двуместный предикатный символ.