Вначале мы вводим понятие счетности ( перечислимости, нумеруемости) и устанавливаем существование несчетных множеств Затем определяется ... - Большая Энциклопедия Нефти и Газа
Выдержка из книги
Булос Д.N.
Вычислимость и логика
Вначале мы вводим понятие счетности ( перечислимости, нумеруемости) и устанавливаем существование несчетных множеств Затем определяется понятие вычислимости посредством машин Тьюринга и доказывается, что проблема их остановки неразрешима. Мы вводим еще два понятия вычислимости и доказываем их эквивалентность вычислимости по Тьюрингу. Неразрешимость ( элементарной) логики первого порядка выводится непосредственно из неразрешимости проблемы остановки, без использования арифметичации Затем устанавливаются корректность и полнота некоторой системы логического вывода. Теорема Левенгейма-Сколема в редакции всякая интерпретация обладает элементарно эквивалентной подинтерпретацией со счетной областью устанавливается при доказательстве корректности и полноты.
