URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Клини С.К. Введение в метаматематику: Математическая логика и рекурсивные функции. Пер. с англ.
Id: 81400
 
699 руб.

Введение в метаматематику: Математическая логика и рекурсивные функции. Пер. с англ. Изд.2, испр.

URSS. 2009. 528 с. Твердый переплет. ISBN 978-5-397-00105-2.

 Аннотация

Настоящая книга, написанная выдающимся американским математиком Стивеном Клини, является одной из самых обширных из имеющихся монографий по математической логике и теории рекурсивных функций. Этот фундаментальный труд по праву стал настольной книгой для всех, кто занимается математической логикой, рекурсивными функциями и основаниями математики. Цель автора --- дать читателю связное введение в область данных научных дисциплин, а также в исследования по основаниям математики вообще. Первая часть книги содержит необходимый подготовительный материал; далее проведено метаматематическое исследование элементарной арифметики с необходимым материалом из математической логики. В восьмой главе второй части изложены знаменитые теоремы Гёделя о неполноте. Третья часть, содержащая в числе прочего изложение теории обще-рекурсивных и частично-рекурсивных функций, может служить руководством для изучения теории рекурсивных функций.

Книга не предполагает со стороны читателя никаких специальных познаний и поэтому может считаться общедоступной. Тем не менее, она предназначена для глубокого изучения предмета и рассчитана как на специалистов по математической логике и теории рекурсивных функций, так и на лиц, желающих впервые, но серьезно, изучить эти науки.


 Оглавление

От переводчика
Предисловие

Часть первая. ПРОБЛЕМЫ ОСНОВАНИЙ МАТЕМАТИКИ  

Глава I. Теория множеств
 § 1.Счетные множества
 § 2.Канторовский диагональный метод
 § 3.Кардинальное число
 § 4.Теорема эквивалентности, конечные и бесконечные множества
 § 5.Высшие трансфинитные кардинальные числа
Глава II. Некоторые основные концепции
 § 6.Натуральные числа
 § 7.Математическая индукция
 § 8.Система объектов
 § 9.Арифметика и анализ
 § 10.Функции
Глава III. Критика математических рассуждений
 § 11.Парадоксы
 § 12.Первые выводы из парадоксов
 § 13.Интуиционизм
 § 14.Формализм
 § 15.Формализация теории

Часть вторая. МАТЕМАТИЧЕСКАЯ ЛОГИКА  

Глава IV. Формальная система
 § 16.Формальные символы
 § 17.Правила образования
 § 18.Свободные и связанные переменные
 § 19.Правила преобразования
Глава V. Формальный вывод
 § 20.Формальный вывод
 § 21.Теорема о дедукции
 § 22.Теорема о дедукции (окончание)
 § 23.Введение и удаление логических символов
 § 24.Зависимость формул и варьирование переменных
Глава VI. Исчисление высказываний
 § 25.Формулы исчисления высказываний
 § 26.Эквивалентность, замена
 § 27.Эквивалентности, двойственность
 § 28.Оценка, непротиворечивость
 § 29.Полнота, нормальная форма
 § 30.Разрешающая процедура, интерпретация
Глава VII. Исчисление предикатов
 § 31.Предикатные формулы
 § 32.Выводимые правила, свободные переменные
 § 33.Замена
 § 34.Подстановка
 § 35.Эквивалентности, двойственность, предваренная форма
 § 36.Оценка, непротиворечивость
 § 37.Теоретико-множественная логика предикатов, k-образы
Глава VIII. Формальная арифметика
 § 38.Индукция, равенства, замена
 § 39.Сложение, умножение, порядок
 § 40.Дальнейшее построение арифметики
 § 41.Формализованные вычисления
 § 42.Теорема Гёделя

Часть третья. РЕКУРСИВНЫЕ ФУНКЦИИ  

Глава IX. Примитивно-рекурсивные функции
 § 43."Примитивно-рекурсивные функции
 § 44.Явное определение
 § 45.Предикаты, представления с помощью простых множителей
 § 46.Возвратная рекурсия
 § 47.Равномерность
 § 48.beta-функция Гёделя
 § 49.Примитивно-рекурсивные функции и арифметический формализм
Глава X. Арифметизация метаматематики
 § 50.Метаматематика как обобщенная арифметика
 § 51.Рекурсивные метаматематические определения
 § 52.Гёделевская нумерация
 § 53.Индуктивные и рекурсивные определения
Глава XI. Обще-рекурсивные функции
 § 54.Формальное вычисление примитивно-рекурсивных функций
 § 55.Обще-рекурсивные функции
 § 56.Арифметизация формализма рекурсивных функций
 § 57.mu-оператор, нумерация, диагональный процесс
 § 58.Нормальная форма, теорема Поста
 § 59.Обще-рекурсивные функции и арифметический формализм
 § 60.Теорема Чёрча, обобщенная теорема Гёделя
 § 61.Симметричная форма теоремы Гёделя
Глава XII. Частично-рекурсивные функции
 § 62.Тезис Чёрча
 § 63.Частично-рекурсивные функции
 § 64.3-значная логика
 § 65.Гёделевские номера
 § 66.Теорема о рекурсии
Глава XIII. Функции, вычислимые по Тьюрингу
 § 67.Машины Тьюринга
 § 68.Вычислимость рекурсивных функций
 § 69.Рекурсивность вычислимых функций
 § 70.Тезис Тьюринга
 § 71.Проблема тождества для полугрупп

Часть четвертая. МАТЕМАТИЧЕСКАЯ ЛОГИКА (дополнительные разделы)  

Глава XIV. Исчисление предикатов и системы аксисм
 § 72.Гёделевская теорема о полноте
 § 73.Исчисление предикатов с равенством
 § 74.Элиминируемость (устранимость) описательных определений
 § 75.Система аксиом, парадокс Сколема, натуральный ряд чисел
 § 76.Проблема разрешимости
Глава XV. Непротиворечивость; классическая и интуиционистская системы
 § 77.Формальная система Генцена
 § 78.Теорема Генцена о нормальной форме
 § 79.Доказательства непротиворечивости
 § 80.Разрешающая процедура, интуиционистская недоказуемость
 § 81.Редукции классических систем к интуиционистским
 § 82.Рекурсивная реализуемость

ДОБАВЛЕНИЯ ПЕРЕВОДЧИКА  

 Добавление I.Доказательство второй теоремы Гёделя
 Добавление II.Восполнение пробела в §§ 49 и 74
 Добавление III.О формализуемости перехода от (iv) к (v) в доказательстве теоремы 36
 Добавление IV.Построение формулы В примера 2 § 79
 Добавление V.Об устранимости равенства и неопределенных описаний
 Добавление VI.О формализации индукции до порядковых чисел, меньших epsilon0, в системе гл. IV (по Гильберту-Бернайсу [1939,стр.361-366])
 Добавление VII.Доказательство непротиворечивости классической арифметики с помощью индукции до epsilon0 (по Шютте) Результат П. С. Новикова
Библиография
Символы и обозначения
Список сокращений
Предметный и авторский указатель

 От переводчика

Хотя математическая логика существует как наука по крайней мере с середины прошлого столетия, круг специалистов в этой области невелик и результаты ее известны недостаточно широко. Однако за последние десятилетия-и в особенности начиная с 1930 г.-в ней были сделаны важнейшие открытия и развитие ее приняло настолько бурный характер, что теперь трудно уже охватить все полученные результаты одной монографией, во всяком случае, такая монография до сих пор никем не написана. Имеются всё же две монографии, которые играют ведущую роль в мировой литературе по математической логике, это книга Гильберта и Бернайса "Grundlagen der Mathematik" (т.I--1934 г., т.II--1939 г.) и предлагаемая вниманию читателя более современная книга Клини "Введение в метаматематику" (1952 г.).

Написанная одним из крупнейших специалистов, книга Клини содержит очерк современного состояния оснований математики и возникших в этой связи основных направлений.

От читателя не требуется никаких предварительных познаний в логике или математике. Однако подробное проведение всех опущенных автором деталей доказательств требует некоторой тренировки (которую, впрочем, можно приобрести в процессе тщательного изучения этой книги). Таким образом, книгу можно рекомендовать и начинающему-при условии, что он не боится трудностей. Читателю, уже знакомому с излагаемым материалом, книга будет полезна не только благодаря оригинальности изложения и обилию тонких замечаний, но и потому, что она может служить удобным библиографическим источником.

Часть III этой монографии может в основном читаться независимо от остальных частей и служить руководством для изучения теории рекурсивных функций, более сжатым и потому более трудным, чем выпущенная недавно Издательством иностранной литературы книга Р.Петер "Рекурсивные функции", (1951 г.; третья часть книги Клини содержит более полное изложение теории обще-рекурсивных функций и вовсе отсутствующую у Петер теорию частично-рекурсивных функций, но зато монография Петер богаче материалом, связанным с примитивными рекурсиями).

В нескольких местах автор счел возможным отослать читателя за доказательствами к упомянутой книге Гильберта и Бернайса. Мы в специальных добавлениях восполнили эти отсутствующие звенья в изложении автора.

Если принять во внимание сделанные нами добавления и ряд подстрочных примечаний, то по сравнению с материалом, изложенным у Гильберта и Бернайса, в настоящей книге отсутствует теория одноместных предикатов, а также изложенные в последних двух дополнениях к книге Гильберта и Бернайса теория положительных форм (относящаяся к исчислению высказываний) и формальное построение анализа на основе арифметики с переменными функциями (для которого, впрочем, до сих пор не известно никакого доказательства непротиворечивости).

Зато налицо подробное рассмотрение интуиционистских систем, общая теория как обще-, так и частично-рекурсивных функций, исчисление Генцена, реализуемость, т.е. вещи, более современные и заведомо перевешивающие упомянутый не вошедший сюда материал книги Гильберта и Бернайса.

Мы глубоко благодарны автору за присланный им перечень опечаток и отдельных мелких погрешностей, имевшихся в английском издании. В русском издании соответствующие места исправлены.

Выражаем благодарность также А.А.Курмитису (Рига), указавшему на одну неточность, допущенную автором (в замечании 1 § 27).

Ряд мелких исправлений внесен нами без специальных оговорок.

В оригинале при переносе формул последний знак, стоящий перед переносом, не повторяется. Следуя установившейся у нас традиции, мы, как правило, повторяем этот последний знак, если он не является знаком отрицания или запятой.

Обращаем особое внимание читателя на различие между двумя шрифтами -- курсив и плантин, которое начинает появляться в IV главе, и особенно начиная с § 40 гл.VIII.

Курсив: а, b, с, d, e, f, g, h, i,..., l, m, n, p, r, s,..., x, у, z

Плантин: a, b, c, d, e, f, g, h, i... l, m, n, p, r, s,..., x, y, z.

(Плантин употребляется для обозначения формальных переменных, а курсив-для содержательных.)

А.С.Есенин-Вольпин

 Предисловие

Две последовательные эры исследований по основаниям математики в девятнадцатом столетии, достигшие своего наивысшего развития в теории множеств и арифметизации анализа, сменились около 1900 г. новым кризисом и новой эрой, отмеченной господством программ Рассела и Уайтхэда, Гильберта и Брауэра.

Появление в 1931 г. двух теорем Гёделя о неполноте, в 1933 г. работы Тарского о понятии истины в формализованных языках, в 1934 г. эрбран-гёделевского понятия "обще-рекурсивной функции" и в 1936 г. связанного с ним тезиса Чёрча возвещает уже новейшую эру, в которой математические средства применяются как для оценки прежних программ, так и в новых, не предвиденных прежде направлениях.

Цель этой книги -- дать связное введение в область математической логики и теории рекурсивных функций и в новейшие исследования по основаниям математики вообще.

Пришлось произвести некоторый отбор. В основном это было сделано с тем, чтобы сосредоточиться после части I на метаматематическом исследовании элементарной арифметики с необходимым материалом из математической логики, оставив в стороне исчисление предикатов высших ступеней, анализ, теорию типов и теорию множеств. Этот отбор был сделан потому, что в арифметике мы находим пример первого и простейшего применения новейших методов и концепций, тогда как распространение их на другие отрасли математики пока еще находится в стадии становления (и будет приобретать, повидимому, все большую и большую важность в ближайшем будущем).

Книга написана с таким расчетом, чтобы она могла служить учебником для аспирантов-математиков первого года обучения (и старше) и для других лиц, достигших этого уровня владения математикой, независимо от их познаний в том или ином разделе математики.

При использовании книги в качестве учебника рекомендуется быстро (в течение двух или трех недель при аудиторных занятиях по три раза в неделю) пройти часть I (главы I--III), которая содержит необходимый подготовительный материал. Интенсивное изучение должно начаться с части II (глава IV), где существенно, чтобы изучающий сосредоточился на приобретении прочного навыка в обращении с метаматематическим методом.

Параграфы, отмеченные звездочкой, могут быть при первом чтении опущены или рассмотрены бегло. К изучению некоторых из них придется в дальнейшем вернуться (например, § 37 нужно изучить перед чтением § 72).

Обе знаменитые теоремы Гёделя о неполноте изложены в главе VIII, причем доказательство одной леммы отложено до главы X. Автору удавалось закончить эти десять глав (а иногда даже несколько больше) в течение семестрового курса, который он неоднократно читал в Висконсинском университете.

Остальные пять глав можно использовать для расширения такого курса до годичного или при параллельном чтении, сопровождающем семинар.

Семестровый курс по рекурсивным функциям при наличии у студентов некоторого предварительного знакомства с математической логикой или под руководством осведомленного преподавателя можно начать с части III (глава IX). Имеются и другие возможности выбора материала; например, тем, кто интересуется преимущественно математической логикой, многое из части IV можно читать непосредственно за частью II или даже за главой VII.

Автор благодарен Сондерсу Маклэйну, склонившему его к написанию этой книги и сделавшему ценные критические замечания в связи с первыми черновиками некоторых глав. Джон Аддисон полностью прочитал гранки с большой тщательностью и независимо от автора. Среди многих других, оказавших помощь, были Эверт Бет, Роберт Бройш, Аренд Рейтинг, Нэнси Клини, Леонард Линский, Дэвид Нельсон, Джеймс Ренно и Джин Роуз. Научные заимствования отмечены ссылками на библиографию; особенно много использована книга Гильберта и Бернайса "Grundlagen der Mathematik" в двух томах, 1934 и 1939 гг.

С. К. Клини.
Июль 1952 г.
 
© URSS 2016.

Информация о Продавце