Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 51
Текст из файла (страница 51)
J. Keisler. Elementary Calculus. Weber and Sсhmidt, Prindle,1976.Предметный указательβ-функция Гёделя 84Compn 27˝1 -аксиоматизируемая теория 197˚1 -аксиоматизируемая теория 197ζ-функция Римана 186k-местная функция 73k-местный предикат 73Sab 85notand 183-значная логика 623-тавтология 63F (false) 8Gen, правило 135majority 32Modus ponens (MP), правило 40, 65N + N 114N + Z 114T (true) 8tertium non datur, закон 45Z × Z 114Z + Z 113, 118ZF 76Автоморфизм интерпретации 86АксиомаАрхимеда 210объёмности(экстенсиональности) 76регулярности(фундирования) 76Аксиомыисчисления высказываний 40исчисления секвенций 55порядка 75равенства 167, 169, 186Алгебраически замкнутоеполе 114, 182Алгебраическое замыкание 169Алгебраическое множество 102Алгоритм проверки простоты 36Алфавит 189Антецедент импликации 8АрифметикаПеано 192Пресбургера 93, 98, 98, 181Арифметический предикат 82Арифметическое множество 82Атомарная формула 74Базис трансцендентности 183Бернайса правила 134, 144Бесконечно близкиегипердействительныечисла 214Бесконечно малоегипердействительноечисло 214Большое множество 201Буква алфавита 189Булева функцияn аргументов 11вычисляемая схемой изфункциональныхэлементов 24монотонная 17сложность 25, 36фиктивный аргумент 31Валентность символа 73Вещественно замкнутое поле 183,213Внутреннее множествогипердействительныхчисел 218Вход 23Предметный указательВывод в исчислениивысказываний 40Вывод из ` 42Выводимая формула 41, 174Выводимостьиз посылок с параметрами 143формулы из ` 142Выигрышная стратегия 204Выполнимая формула 48, 129Выразимый предикат 80Высказывание 8истинное 8истинностное значение 8ложное 8Выход 24Галактика гипердействительногочисла 217Гипердействительное число 211абсолютная величина 213бесконечно малое 214галактика 217гипернатуральное 211гиперцелое 211конечное 213нестандартное 211положительное бесконечнобольшое 213стандартная часть 215стандартное 211Гипердействительные числабесконечно близкие 214Гипернатуральное число 211Гиперцелое число 211Главный фильтр 202Глубина схемы изфункциональныхэлементов 29, 36Двоичное дерево 52Двойное отрицание, снятие 45Диаграмма интерпретации 194Диаграмма семействамногочленов 104229Дизъюнкт 16Дизъюнктивная нормальнаяформа 16, 22, 25Дизъюнкция 9Дискриминант 111Допустимость правила сечения 68Заключение импликации 8Законисключённого третьего 45поглощения 13снятия двойного отрицания 45Законы (правила) Де Моргана 13,17, 61Замкнутая формула 79, 174Замыкание множества 219Замыкание формулы 129Значение переменной 77Значение терма 78Значение формулы 78И (истина) 8Игра Эренфойхта 117Изоморфизм интерпретаций 111Импликация (следование) 9Индивидная переменная 73свободное вхождение 131связанное вхождение 132Интеграл 222Интерпретацииизоморфные 111элементарно эквивалентные 111,175Интерпретация 74, 174автоморфизм 86диаграмма 194нормальная 75, 113, 114, 167, 174носитель 75подструктура 115расширение 115элементарное расширение 115Интуиционистская логика 45, 58Исключённого третьего закон 45230Предметный указательИстинная пропозициональнаяпеременная 64Истинная формула 78, 174Истинное высказывание 8Истинностное значениевысказывания 8Исчислениевысказываний 40, 130вывод 40выводимая формула 41интуиционистское 58классическое 58схемы аксиом 40теорема 41генценовского типа 53гильбертовского типа 53предикатов 48, 128корректность 136секвенций 53аксиомы 55правила вывода 55Канторовское пространство 51Категоричная теория 183Квадрат, разрезание 96Квантор 72область действия 131Кванторная глубина формулы 120Классическое исчислениевысказываний 58Кодирование последовательностейи множеств 84Коконечное подмножество 202Коллизия переменных 132Компактное множество 220Компактность 153, 169Комплексные числа 182Конечно аксиоматизируемаятеория 175Конечное гипердействительноечисло 213Консеквент импликации 8Консерватор (в игреЭренфойхта) 117Константа 74свежая 144Контрапозиция 13Контрпример (к секвенции) 54Конъюнкт 16Конъюнктивная нормальнаяформа 16Конъюнкция 9Корректная подстановка 132, 136Корректность исчисленияпредикатов 136, 144КритерийЛося – Воота 175общая форма 176Поста 20Л (ложь) 8ЛеммаКёнига 52Крейга 18о дедукции 42, 61, 142, 144о добавлении констант 145, 149о расширении 200о свежих константах 144Тарского 199Цорна 50, 203Линейная функция 20Линейный порядок 169Литерал 16Логика высказываний 8Логические связки 8Ложная пропозициональнаяпеременная 64Ложная формула 78, 174Ложное высказывание 8Малое множество 201Мир (в шкале Крипке) 64Множества, элементарнаяэквивалентность 95МножествоПредметный указательалгебраическое 102арифметическое 82большое 201гипердействительных чиселвнутреннее 218замыкание 219компактное 220малое 201однородное 173открытое 219полуалгебраическое 102предельная точка 219экзистенциально замкнутое 124Множество формулнепротиворечивое 48, 148полное 49, 148противоречивое 48, 146совместное 48Модель 146Крипке 63нормальная 174счётная 152теории 144, 174Монада 214Моном 18Монотонная функция 17, 20Мультилинейная функция 20Непрерывная функция 221Непротиворечивая теория 146Непротиворечивое множествоформул 48, 148Несовместность теории 175Нестандартноегипердействительноечисло 211Нестандартный анализ 209Новатор (в игре Эренфойхта) 117Нормальная интерпретация 75,113, 114, 167, 174Нормальная модель 168, 170Нормальная формадизъюнктивная 16231конъюнктивная 16предварённая 157сколемовская 165Носитель интерпретации 75Область действия квантора 131Образующая полугруппы 189Общезначимая формула 128Однозначность разбора 14Однородное множество 173Операция взятиямодифицированногоостатка 106Открытое множество 219Отрицание 9Оценка 77Параполная 68противоречивая 67совместная 67Параметр формулы 77Переменнаязначение 77индивидная 73пропозициональная 10свободная 77свободное вхождение 77связанное вхождение 77Плотное линейно упорядоченноемножество без первого ипоследнего элементов 216Повышение мощности 170, 172Подмножествококонечное 202Подобные формулы 155Подстановкакорректная 132Подстановки правило 43Подструктура 115, 123, 197Поле 20алгебраически замкнутое 114,182232Предметный указательвещественно замкнутое 183, 184,213упорядоченное 183характеристика 114характеристики 0 114Поле частных 195Полиномы (Жегалкина) 18Полная пара 68Полная система связок 15, 17Полная теория 147, 175Полное множество формул 49, 148Полный набор булевыхфункций 24Положительное бесконечнобольшое число 213Полуалгебраическоемножество 102Полугруппа 189с образующими исоотношениями 189свободная 189Польская запись 15Последовательностьпредельная точка 218сходящаяся 219Посылка импликации 8Правила вывода исчислениясеквенций 55Правилоmodus ponens (MP) 40, 65Бернайса 134, 144контрапозиции 13обобщения (Gen) 135подстановки 43сечения 43допустимость 68Штурма 109Предварённая нормальнаяформа 157Предварённая формула 157Предел функции 220Предельная точкамножества 219последовательности 218Предикатk-местный 73арифметический 82выражаемый формулой 80выразимый 80устойчивый 87Предикатный символ 73Предикатов исчисление 128Предполные классы 20Принцип переноса 211Присоединение корнеймногочлена 169Проблема конечного спектра 173Проблема перебора 23, 26Проводник 24Производная функции 222Пропозициональная переменная 10истинная 64ложная 64Пропозициональная формула 10,40Противоречивая пара 67Противоречивое множествоформул 48, 146Противоречивость теории 175Прототип формулы 160Равенства аксиомы 167Равенство 169, 186Равенство (предикатныйсимвол) 74Равномерно непрерывнаяфункция 221Размер схемы 24, 36Размер формулы 36Разрезание квадрата 96Разрешимая теория 95, 102, 175Расширение интерпретации 115Результант 111Рефлексивность 167Самодвойственная функция 20Предметный указательСвободная переменная 77Свободная полугруппа 189Свободное вхождениепеременной 77, 131Связанное вхождениепеременной 77, 132Связки (логические) 8Связки, сохраняющие 0/1 17Секвенция 53представляющая формула 56Семантическое следование 153, 175Сеченияправило 43Сигнатура 73, 174интерпретация 174Символвалентность 73предикатный 73функциональный 73Симметричность 167Скобочный итог 14Сколемизация 165Сколемовская нормальнаяформа 165Сколемовская функция 163, 165Следование семантическое 175Слово алфавита 189Сложение по модулю 2 38Сложение чисел, глубина 29Сложение чисел, сложность 28Сложностьбулевой функции 25, 36типичной булевой функции 25функции голосования 32функции сравнения 26Снятие двойного отрицания 13Совместная пара 67Совместная теория 174Совместное множество формул 48,146Соотношение полугруппы 189Спектр формулы 173Стандартная часть233гипердействительногочисла 215Стандартное гипердействительноечисло 211Стратегия 204выигрышная 204Суждение 79Схема из функциональныхэлементов 22, 24глубина 29, 36размер 24, 36Схема формулы 155Схемы аксиом исчислениявысказываний 40Сходящаясяпоследовательность 219Счётная модель 152Тавтология 11, 40ТеоремаБрауэра о неподвижнойточке 58Гёделя 71Гёделя о неполноте 192Гёделя о неполноте (вторая) 58Гильберта о нулях 116, 116Гливенко 71исчисления высказываний 41компактности 193, 211компактности для ИВ 51компактности для нормальныхмоделей 169компактности, прямоедоказательство 201, 208Левенгейма – Сколема оповышении мощности 170, 210Левенгейма – Сколема обэлементарной подмодели 95,123, 153Лося обультрапроизведениях 206Лося – Тарского 197Морли 176, 178234Предметный указательо выводимости бескванторныхформул 160о компактности для исчисленияпредикатов 153о корректности и полнотеисчисления секвенций 56о корректности ИВ 41о корректности ИВ, втораяформа 48о корректностиинтуиционистского ИВотносительно шкалКрипке 65о корректности исчисленияпредикатов 144о корректности исчисленияпредикатов,переформулировка 144, 146о переименовании связанныхпеременных 155о полиномах Жегалкина 19о полноте для нормальныхмоделей 168о полноте ИВ 40, 41о полноте ИВ, вторая форма 49о полноте интуиционистскогоИВ относительно шкалКрипке 66о полноте исчисленияпредикатов, сильнаяформа 147о полноте исчисленияпредикатов, слабая форма 153о полноте системы связок (∧, ∨,→, ¬) 15, 22о полноте теории алгебраическизамкнутых полейхарактеристики нуль 114о предварённой нормальнойформе 160о разбиении квадрата 96о сколемовской нормальнойформе 165об однозначности разбора 14Ролля 109, 185Тарского 192Тарского – Зайденберга 101, 103,114теории 142, 174Тихонова 52Чёрча 129, 166, 191Чэна – Лося – Сушко 198Эрбрана 161Теория 142, 146, 174˝1 -аксиоматизируемая 197˚1 -аксиоматизируемая 197Th(Q, =, <, +, 0, 1) 180Th(Z, =, <, S, 0) 179Th(Z, =, S, 0) 178абелевых групп 186алгебраически замкнутых полейхарактеристики 0 182вещественно замкнутыхполей 184групп 186категоричная 183категоричная в счётноймощности 175конечно аксиоматизируемая 175линейно упорядоченныхмножеств 186модель 146, 174непротиворечивая 146плотных линейноупорядоченных множеств безпервого и последнегоэлемента 177полная 147, 175полугрупп 189противоречивая 146равенства 186разрешимая 102, 175с равенством 169, 174совместная 146, 174теорема 174Цермело – Френкеля 76Предметный указательэкзистенциально полная 149Терм 74значение 78Транзитивность 167Трёхзначная логика 62Увеличение мощности 169Ультрапроизведение 206Ультрафильтр 202Умножение чисел, сложность 30Упорядоченное поле 183Устойчивая функция 87Устойчивостьотносительно объединенияцепей 198при переходе кподструктурам 197при расширении 197Устойчивый предикат 87Фиктивный аргумент функции 31Фильтр 201главный 202Фильтрованное произведение 205Формальная арифметика 192Формулаатомарная 74выводимая в исчислениивысказываний 41выводимая в теории 174выводимая из ` 42, 142выполнимая 48, 129замкнутая 79, 174замыкание 129значение 78истинная 78, 174кванторная глубина 120ложная 78, 174общезначимая 128параметр 77первого порядка 74предварённая 157представляющая секвенцию 56235пропозициональная 10прототип 160спектр 173схема 155Формула Тейлора 184Формулыподобные 155эквивалентные 11, 129Функциональный символ 73Функцияk-местная 73булева 11голосования 32интеграл 222линейная 20монотонная 20мультилинейная 20непрерывная 221непрерывная на компакте 222предел 220производная 222равномерно непрерывная 221самодвойственная 20сколемовская 163, 165сохраняющая 0/1 20сравнения 26устойчивая 87эрбрановская 165Характеристика поля 114, 182Центрированная системамножеств 52Цепь элементарныхрасширений 199Частичный порядок, продолжениедо линейного 169Числогипердействительное 211Шкала Крипке 63Эквивалентные формулы 11, 129236Предметный указательЭкзистенциально замкнутоемножество 124Экзистенциально полнаятеория 149Элементарная теорияинтерпретации 175Элементарная эквивалентность 95,111, 210Элементарная эквивалентность Rи Q с (=, <, +, 0, 1) 113Элементарная эквивалентность Zи Z + Z 113, 118Элементарное расширение 115, 170Элиминация кванторов 89, 113,178, 192в (Q, =, <) 93в (Z, =, S, 0) 90в (Z, =, <, S) 92в арифметике Пресбургера 98в поле комплексных чисел 110Эрбрановская функция 165Языкивторого порядка 163первого порядка 74Указатель имёнАйтаи (Miklós Ajtai), 02.07.1946, Budapest (Венгрия) : 36Архимед, ок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
