| Логические Выводы |
Apr. 24th, 2023|11:08 pm |
Я продолжал изучать теорию рекурсии.
В первую очередь хочу высказаться насчёт арифметической иерархии. В прошлом посте я написал, что она является неким аналогом борелевских множеств, если рекурсивно перечислимые множества. Но более правильной аналогией являются гипер-арифметические множества. И поэтому вынужден извиниться перед читателями.
Дальнейшее изучение теории рекурсии должно было привести к теории сводимости алгоритмов и рекурсивного изоморфизма. Это дело ведет к определению степеней Тьюринга, множества классов алгоритмов по сводимости. Эти степени образуют частично упорядоченное множество и его изучение является серьезным разделом теоретической информатики.
Но кроме классических разделов есть еще и не классические. Например у Манина есть раздел про рекурсивно-порожденные группы. Тут теорема Геделя о неполноте используется для того, чтобы доказать теорему Хигмана, важный результат в комбинаторной теории групп. Вообще такая связь между логикой и комбинаторной алгеброй неудивительно. Потому что в основе обоих наук лежит некая общая теория индукции на множествах с порождающими, о которой я писал в прошлый раз. Манин и в последней главе, которой, кажется, не было в "вычислимое и не вычислимое", он пишет о категории "конструируемых вселенных". Сейчас мне кажется, что это правильная формализация моей теории индукции на множествах с порождающими. Скажу пока только, что тут изучатся кактегории с натуральными объектами, то есть объектами похожими на натуральные числа. Потом Манин применяет эту теорию к изучению... квантовых вычислений.
В результате этой работы я стал полон логики как бочка, наполненная молодым вином. И стал булькать. Поэтому я временно приостанавливаю изучение логики. Но настоящая причина в том, что я запутался в нотации у Белла. И если возвращаться к этой теме, то я хотел бы перезагрузится, и начать читать другую книгу с начала, например Одифредди. Хотя, сегодня я уже не чувствую, что запутался, может и продолжу. Но сейчас теория рекурсии у меня не в приоритете, поэтому я хотел переходить к теории множеств. А что касается, неклассической теории у Манина, особенно то, что касается категории конструируемых миров, но то я хотел бы найти другие источники по этой теме. Но думаю, что сначала нужно разобраться с топосами. Нет, все таки я запутался в Белле (Потому что из кусков теории связаны с вычислениями я изучал по Манину, и очень плохо понимаю часть нотации Белла).
Другая тема в логики, которую я пропускаю, это нестандартные (особенно интуционалистская) и модальные логики. Особенно меня заинтересовала тут тема семантики Крипке и перевода модальных логик в логику первого порядка. Тут с этой темой в философии есть интересная история. У. Квайн был логическим монистом, то есть он считал что есть одна верная логика, и это классическая логика. В частности, он считал модальную логику "метафизически нагруженной" и ненадежной. Считается, что его студент, Саул Крипке использовал логику доказуемости, допускающую ясную арифметическую интерпретации. Поэтому логика доказуемости мне кажется самой интересной из модальных. Я почитал немного Беклемешева и Артемова по этой теме. И оказалось, что есть много разных логик доказуемости. Я не уверен, не опровергает ли это тезис Крипке, или это еще один аргумент против логического монизма. Семантика Крипке отличается от классической логики с булевой семантикой, в той же степени как дифференциальные многообразия от гладких пространств. Еще эту семантику иногда неверно называют семантикой возможных миров.
Репер Крипке состоит из множества "возможных миров" и отношения достижимости. Например, в эпистимической логики отношение достижимости A из B значит, что мир B cоответствует нашим знаниям в мире A. В этической логик отношение достижимости A из B значит, что мир B cоостветствует представлению о должном в мире A. И отсюда и идея о семантике возможных миров. Но какие возможные миры могут быть в логике доказуемости? Тем более если этих логик много, то таких семантик тоже много. Еще у логик доказуемости есть топологические семантики, где высказывания соответствуют множествам в топологическом пространстве. А модальные операторы операторам множества предельных точек.
Касательно интуиционистской логикой, мне понравилась характеристика интуиционистской логики, которую использует Белл: интуционалисты верят, что математические объекты конструируется в разуме математика, и математика это искусство конструирования ментальных объектов, в то время как язык нужна для коммуникации и не необходим для занятия математикой. Поэтому математика не должна завесить от нюансов синтаксиса. Мне очень понравилась идея заниматься математичкой, не используя язык вообще. Похоже на магическую практику. Но Белл просит различать интуиционистскую философию математики и интуиционистскую логику и больше пишет о последней. Там, он кстати тоже используют семантику Крипке.
На последок в качестве бонуса обзор учебников, которыми я пользовался:
J. Bell, M. Machover: Mathematical Logic — Белл меня заинтересовал. Это очень умный автор, который хорошо владеет и философией, и общей топологией. Планирую дальше по нему изучать теорию множеств. По стилю эта книга ближе всего к тому, что я назвал бы аналогом Бурбакизма в логике. Опять же нотация достаточна сложная, чтобы я в ней запутался, но только в разделе алгоритмов. Есть очень интересные задачи. И много глубоких и интересных тем. Когда авторы писали эту книгу, мне кажется, они отчасти придерживались конструвистской философии. Поэтому тут много довольно педантичных доказательств с выводом конструктивности тех или иных объектов. Возможно, я предпочел похожую книгу, но менее конструктивную. Но мне Белл, наверное больше всех в целом понравился.
Yi. I. Manin: A Course in Mathematical Logic for Mathematicians — Это современное переиздание возможно известных вам советских книг "Доказуемое и недоказуемое" и "Вычислимое и невычислимое". Грубо говоря это не совсем учебник, а большой обзор с некоторыми углублениями. С одной стороны, потому что тут нет задач. А с другой стороны, потому что тут очень много внезапных скачков сложности за которыми иногда сложно успевать. То есть в плане педантичности это полная противоположность Белла и Маховера. Однако тут есть интересные темы про пучки и категории, которых в других книгах "про математическую логику" нет.
J. Milleti: Modern Mathematical Logic — Мне понравился подход этого учебника к основам логики и теории моделей, как я уже писал очень динамично. И еще мне понравились интересные примеры. Но все же это undergraduate учебник поэтому он не очень глубокий, и все упражнения там очень легкие. Еще он не очень жирный в плане теории множеств и рекурсии.
P. G. Hinman: Foundations of mathematical logic — А это наоборот очень толстая с материалом на четыре семестра. Тут есть и доказательство теоремы Морли из теории моделей и форсинг. Так как материал по основам логики используется тут как основа для довольно продвинутых тем, это создает необходимость разбирать много нюансов в условном начале. Поэтому я не рекомендовал бы ее новичкам. Тем не менее мне понравился подбор задачек по темам, которые я тут изучал: про логику первого порядка в основном. |
|