Математическая логика и основы теории алгоритмов. Радаев В.Н. - 16 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

VI. Арифметизация процесса логического вывода. Рекурсивная неразрешимость и
дедуктивная неполнота формальной арифметики
15
мулами теоретико-числовой системы Z. Обратная теорема: рекурсивность
функций и предикатов, выразимых средствами теоретико-числовой систе
мы Z.
7. β-функция Геделя β(a, d, i)=R(a, 1+(i+1)d). Представление β-функции
всистемеZ. Применение β-функции для представления примитивно-рекур-
сивных функций.
8. Слабая представимость функций и предикатов средствами теоретико-чис-
ловой системы Z. Теорема о возможности слабой представимости рекур
сивно-перечислимых предикатов формулами теоретико-числовой системы
Z.
9. Неразрешимость теоретико-числовой системы Z (теорема Черча). След
ствие: неразрешимость исчисления предикатов. Неразрешимость любого
рекурсивно-аксиоматизируемого непротиворечивого расширения теоретико--
числовой системы Z.
10. Дедуктивная неполнота теоретико-числовой системы Z (первая теоре
ма Геделя о неполноте). Дедуктивная неполнота любого рекурсивно-аксио-
матизируемого непротиворечивого расширения теоретико-числовой систе
мы Z.
11. ω-противоречивые и ω-непротиворечивые формальные системы. ω-полные
и ω-неполные формальные системы. Геделева неразрешимая формула G(k
pG(y)q
).
ω-неполнота теоретико-числовой системы Z. Неизоморфность моделей ариф
метики.
12. Неразрешимая формула Россера. Первая теорема Геделя в форме Рос
сера.
13. Правило Карнапа (ω-правило).
14. Представление суждения о непротиворечивости системы Z средствами
самой системы. Формула Consis
Z
. Невыводимость в Z суждения о непро
тиворечивости Z (вторая теорема Геделя о неполноте).
15. Непротиворечивость теоретико-числовой системы Z с аксиомой полной
индукции. Теорема Генцена.
Математическая логика и основы теории алгоритмов

Страницы