Хотелось бы напомнить про трехтомник Верещагина и Шеня «Лекции по математической логике и теории алгоритмов» Часть 1. Начала теории множеств https://mccme.ru/free-books/shen/shen-logic-part1-5ed.pdf «Основные понятия теории множеств (мощности, трансфинитная индукция, ординалы) входят в число вещей, которые хорошо бы знать любому грамотному математику (даже если он не является математическим логиком или общим топологом) Обычно про них коротко пишут в первых главах учебников анализа, алгебры или топологии, спеша перейти к основной теме книги А жаль — предмет достаточно интересен, важен и прост, чтобы рассказать о нём не торопясь Именно такой популярный рассказ мы пытались написать, имея в виду самых разных читателей: от подготовленного школьника (захотевшего перейти от побед на олимпиадах к чему-то более осмысленному) до профессионального математика (решившего прочитать по дороге на отдых, что же такое трансфинитная индукция, которую всегда заменяют леммой Цорна)» Часть 2. Языки и исчисления https://mccme.ru/free-books/shen/shen-logic-part2-5ed.pdf «Центральная идея математической логики восходит ещё к Лейбницу и состоит в том, чтобы записывать математические утверждения в виде последовательностей символов и оперировать с ними по формальным правилам. (…) революционная программа Лейбница построения формальных оснований математики осуществилась, но незаметно: под здание математики подвели новый (и довольно прочный) фундамент, но большинство жильцов про это до сих пор не знают (…) В этой книжке мы расскажем об одном из центральных понятий математической логики — языках и исчислениях первого порядка В этих языках используются логические связки «и», «или», «если… то…», а также кванторы «для всех» и «существует» Оказывается, что этих средств достаточно для формализации математических теорий и что можно построить простые формальные правила, полностью отражающие смысл этих логических средств» Часть 3. Вычислимые функции https://mccme.ru/free-books/shen/shen-logic-part3-5ed.pdf «Теория вычислимых (с помощью компьютеров) функций появилась в 1930-е годы, когда никаких компьютеров ещё не было Первые компьютеры были разработаны в 1940-х годах, и среди их разработчиков был английский математик Алан Тьюринг, один из создателей теории вычислимых функций (…) Мы сознательно не касаемся теории сложности вычислений — это большая и отдельная тема Вместо этого мы попытались отобрать центральные понятия и факты общей теории алгоритмов и изложить их понятно, стараясь не заслонять простые общие идеи техническими деталями Мы не предполагаем никаких специальных предварительных знаний, хотя рассчитываем на некоторый уровень математической культуры»