Книга открывает учрежденную в 1995 г. Сибирским фондом алгебры и логики математическую книжную серию под редакцией академика Ю. Л. Ершова. Все книги серии издаются одновременно на английском языке издательством Plenum Publishing Corporation.
В книге дается новое доказательство теоремы Гёделя о неполноте, основанное на систематическом использовании формул с ограниченными кванторами; новое изложение (на основе теоремы Ганди) теории допустимых множеств с праэлементами. Включены также избранные темы, посвященные Σ-определимости, динамической логике, Σ-предикатам конечных типов.
Для научных работников - специалистов по математической логике, алгебре, теоретическому программированию, информатике и смежным специальностям. Доступна аспирантам и студентам университетов.
Author(s): Ершов Ю.Л.
Series: Сибирская школа алгебры и логики
Publisher: Научная книга
Year: 1996
Language: Russian
Commentary: новый скан (высокого разрешения); внесены все исправления, указанные в Списке замеченных опечаток (Envoy)
Pages: 300
City: Новосибирск
Ершов Ю.Л. Определимость и вычислимость (1996) ......Page 1
Предисловие ......Page 6
Оглавление ......Page 10
1.1. RQ-формулы и Σ-формулы ......Page 12
1.2. Формульная определимость ......Page 25
1.3. Позитивные формулы и монотонные операторы ......Page 32
1.4. Σ-предикаты и Σ-функции на Ω ......Page 38
1.5. Σ-определимость истинности Σ-формул на Ω ......Page 52
1.6. Универсальные Σ-предикаты и универсальные частичные Σ-функции ......Page 66
1.7. Теорема Чёрча и теорема Гёделя о неполноте ......Page 72
2.1. Алгебраические системы Ω и HF(Ø) ......Page 86
2.2. Теория KPU. Допустимые множества ......Page 98
2.3. Принципы Σ-рефлексии, Δ-отделимости и Σ-ограниченности ......Page 106
2.4. Σ-операторы, теорема Ганди и формульная представимость Σ-операторов ......Page 112
2.5. Σ-рекурсивные определения ......Page 121
2.6. Σ-определимость истинности Σ-формул и универсальный Σ-предикат ......Page 130
2.7. KPU-модели ......Page 142
2.8. Сводимости ......Page 154
3.1. Конструируемые множества ......Page 164
3.2. Рекурсивно насыщенные системы ......Page 175
3.3. Уплощение и вынуждение ......Page 182
3.4. Определимость и Σ-определимость алгебраических систем ......Page 199
3.5. Вычислимость в специальных допустимых множествах ......Page 211
3.6. Σ-допустимые семейства ......Page 230
3.7. Динамическая логика ......Page 244
3.8. Σ-предикаты конечных типов ......Page 258
3.9. Эффективные f-пространства ......Page 270
Приложение ......Page 282
Литература (основной список) ......Page 288
Литература (дополнительный список) ......Page 290
Предметный указатель ......Page 292
Обозначения ......Page 296
