Посоветуйте книгу по матлогике/основаниям

[oleg.k]

Интересно заглянуть поглубже в основания математики. Как это лучше всего сделать? Потребность формировалась давно и постепенно: сначала мне не понравились натуральные числа, как "первоначальные объекты...", затем не понравились кардиналы и ординалы (с наивной точки зрения), сейчас я вообще не уверен в том, какие "формы рассуждений" законны...

Посоветуйте какую-нибудь современную книгу по матлогике (можно на английском), в которой последовательно объяснялись основания. И чтобы не было ничего метафизического. Хотелось бы, чтобы изложение было достаточно абстрактным (например, мне непонятно почему "строки" из символов алфавита обязаны располагаться горизонтально и почему меня заставляют писать слева направо )

[arseniiv]

oleg.k в сообщении #1418856 писал(а):

сначала мне не понравились натуральные числа, как "первоначальные объекты..."

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

Вот есть например разные арифметики первого порядка. Вроде хорошо, удобно, а имеют нестандартные модели (если принимать, что мы видели в глаза стандартную, утверждения о которой и хотели аксиоматизировать этими арифметиками). Мы можем избавиться от нестандартных моделей, перейдя к языку второго порядка, но с логикой второго порядка уже свои проблемы начинаются. Мы можем попытаться описать $\mathbb N$ внутренне, как объект какой-то более широкой теории типа теории множеств ZFC, но проблемы тех же видов просто отодвинутся на уровень этой теории. Мы можем быть хитрее, но всё равно никого не перехитрим (если только себя запутаем); ну например мы можем определять индуктивный тип натуральных чисел и иметь выражения ровно лишь для стандартных натуральных чисел как его элементов, но ровно аналогично языкам арифметики из начала абзаца мы можем иметь у этого типа больше значений.

oleg.k в сообщении #1418856 писал(а):

например, мне непонятно почему "строки" из символов алфавита обязаны располагаться горизонтально и почему меня заставляют писать слева направо

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

oleg.k в сообщении #1418856 писал(а):

сейчас я вообще не уверен в том, какие "формы рассуждений" законны...

Вот это выглядит как торчащая из клубка нитка, за которую можно потянуть. Какие например? Может, что-нибудь вспомнится.

[oleg.k]

arseniiv в сообщении #1418871 писал(а):

Вряд ли вы найдёте что-то более основательное.

Меня натуральные числа по фон Нейману или по Цермело относительно устраивают. Не устраивают лишь определения в духе "мы все знаем эти числа, мы их используем для счета" и все такое.

arseniiv в сообщении #1418871 писал(а):

Всё равно у нас будут или строки конечной (натуральной!) длины из конечного множества символов, или конечные деревья из конечного множества конструкторов, или что-то в том же духе.

А вот это интересно. Где можно почитать матлогику с т.з. деревьев?

arseniiv в сообщении #1418871 писал(а):

строки — это расположения символов какого-то алфавита по конечному числу мест.

А я даже не знаю толком, что такое символ Символ, который реально написан на бумаге? Или "абстрактный" символ? А может и то и другое? Можно так: "абстрактный" символ - это "класс" "похожих" символов (одной формы)? (И что такое тогда "класс"?)

С именами вообще беда. Есть ли "взаимно однозначное соответствие" между именами и их "смыслами"? А между именами и их "объектами"? А между "смыслами" и "объектами"? И как понимать взаимно однозначное соответствие, когда ни функций, ни множеств еще нету? И что если имя содержит дополнительную информацию или не определяет ни один объект? Как быть, когда имя само является объектом? И таких вопросов у меня еще с два десятка.

arseniiv в сообщении #1418871 писал(а):

Какие например? Может, что-нибудь вспомнится.

Ну мне кажется сомнительным modus pones. Кто вообще сказал, что я должен верить, что он работает? Дайте мне точку зрения, где я сам буду решать, что можно использовать, а что нельзя

[epros]

oleg.k в сообщении #1418856 писал(а):

сначала мне не понравились натуральные числа, как "первоначальные объекты..."

В каком смысле "изначальные"? Необходимость в натуральных числах возникает, когда язык начинает нам позволять говорить о неограниченном количестве объектов, и, как следствие, возникает необходимость выразить понятие "конечности". Вот для этого и нужны натуральные числа.

oleg.k в сообщении #1418856 писал(а):

сейчас я вообще не уверен в том, какие "формы рассуждений" законны...

Да любые, о которых договоримся. Проблема только в однозначности понимания формулировок сего договора.

oleg.k в сообщении #1418856 писал(а):

например, мне непонятно почему "строки" из символов алфавита обязаны располагаться горизонтально и почему меня заставляют писать слева направо

Прямо-таки заставляют?

[oleg.k]

epros в сообщении #1418888 писал(а):

В каком смысле "изначальные"?

Я про "школьное" определение. Там и множество - неопределяемое понятие. И натуральные числа тоже. Предполагается, что у каждого человека есть какая-то интуиция, сформированная опытом, которая позволяет говорить о натуральных числах.

epros в сообщении #1418888 писал(а):

Да любые, о которых договоримся. Проблема только в однозначности понимания формулировок сего договора.

Сложно... Какую книгу посоветуете, чтобы именно про это было подробно рассказано?

[epros]

oleg.k в сообщении #1418885 писал(а):

Символ, который реально написан на бумаге? Или "абстрактный" символ? А может и то и другое? Можно так: "абстрактный" символ - это "класс" "похожих" символов (одной формы)? (И что такое тогда "класс"?)

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

oleg.k в сообщении #1418885 писал(а):

Есть ли "взаимно однозначное соответствие" между именами и их "смыслами"?

Конечно нет. Это - вопрос применения теории, которое всегда может оказаться "не таким как нужно".

oleg.k в сообщении #1418885 писал(а):

А между именами и их "объектами"?

А вопросов о том, что такое "объекты", у Вас не возникает?

oleg.k в сообщении #1418885 писал(а):

Ну мне кажется сомнительным modus pones. Кто вообще сказал, что я должен верить, что он работает?

Во что верить? Это просто соглашение о правилах рассуждений, которые если не хотите - не принимайте. Но тогда те, кто их принял, Ваши рассуждения не поймут.

[oleg.k]

epros в сообщении #1418896 писал(а):

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

Т.е. Вы говорите про какой-то "универсальный" язык, на котором идет общение между собеседниками?

epros в сообщении #1418896 писал(а):

А вопросов о том, что такое "объекты" у Вас не возникает?

Да, возникают. Кто сказал, что существует хотя бы один объект? Могу ли я смотреть на объект безотносительно его природы? (столы и стулья как точки и прямые у Гильберта) Почему я должен быть уверен, что произнося какое-то имя, мой собеседник подумает про этот же самый объект этого имени, что и я? (если объектов у имени может быть больше одного)

[Eule_A]

oleg.k в сообщении #1418894 писал(а):

Там и множество - неопределяемое понятие. И натуральные числа тоже. Предполагается, что у каждого человека есть какая-то интуиция, сформированная опытом, которая позволяет говорить о натуральных числах.

Пусть меня математики поправят, если я не то порекомендую. Есть книга С. Фефермана "Числовые системы". Прочитаете там о натуральных числах - узнаете их, конечно. Но, возможно, не сразу

[epros]

oleg.k в сообщении #1418903 писал(а):

Т.е. Вы говорите про какой-то "универсальный" язык, на котором идет общение между собеседниками?

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

oleg.k в сообщении #1418903 писал(а):

Кто сказал, что существует хотя бы один объект?

Только теория может сказать. Но другая теория может с ней не согласиться.

oleg.k в сообщении #1418903 писал(а):

Могу ли я смотреть на объект безотносительно его природы? (столы и стулья как точки и прямые у Гильберта)

"Смотреть" это уже вопрос применения теории. Теория может говорить, что существуют такие объекты, как стулья, что они обладают такими-то свойствами и т.п. А вот когда Вы смотрите на нечто и думаете: "Вот это - стул", то уже применяете теорию в практической ситуации.

oleg.k в сообщении #1418903 писал(а):

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

Конечно не должны. И недоразумения частенько случаются. Поэтому надо хотя бы постараться исключить все очевидные возможности неправильного понимания.

[oleg.k]

epros в сообщении #1418911 писал(а):

Поэтому возникает вопрос о том основании, на котором должно строиться понимание между собеседниками, когда один теорию излагает, а второй - пытается понять.

Чем вообще матлогика занимается? Этот вопрос про двух собеседников какой-то "ангажированный реальностью"...

-- 03.10.2019, 20:48 --

epros в сообщении #1418911 писал(а):

Поэтому надо хотя бы постараться исключить все очевидные возможности неправильного понимания.

И останутся неочевидные... Как можно доверять противоречивому языку?

-- 03.10.2019, 20:57 --

epros в сообщении #1418896 писал(а):

Это омут без дна, слишком глубоко нырять не стоит.

Я глубоко нырять и не хочу. Мне будет достаточно, когда я смогу рассматривать символы как физические объекты. Когда все математические доказательства будут состоять из букв/стрелок/.../ и правильность доказательства проверялась бы путем непосредственного его рассмотрения как физического объекта.

[epros]

oleg.k в сообщении #1418917 писал(а):

Чем вообще матлогика занимается?

Ну вот этим и занимается: Предоставляет нам правила рассуждений.

oleg.k в сообщении #1418917 писал(а):

И останутся неочевидные... Как можно доверять противоречивому языку?

Всего лишь неоднозначному. Ну и что? Как-то ведь обходимся. А там, где риск неправильного понимания слишком велик, прибегаем к формализации. Но у неё есть своя цена, поэтому злоупотреблять ей тоже не стоит.

[oleg.k]

Благодарю за помощь. Что посоветуете почитать по матлогике?

[epros]

Вообще-то у каждого свой вкус. Ну, например, Верещагин, Шень, Языки и исчисления. Это - второй том сборника, но в принципе полезно и в другие тома заглянуть.

[arseniiv]

oleg.k в сообщении #1418885 писал(а):

Меня натуральные числа по фон Нейману или по Цермело относительно устраивают. Не устраивают лишь определения в духе "мы все знаем эти числа, мы их используем для счета" и все такое.

А, ну тогда вот вам определение: натуральное число — это запись, которую можно получить лишь одним из двух следующих способов: (i) взять запись $0$, (ii) взять натуральное число и приписать слева $S$. После этого мы можем определить равенство (в данном случае просто как совпадение записей) и прочие вещи типа сложения. Наше определение натурального числа — индуктивное, так что мы можем использовать индукцию для доказательств и рекурсию для определений.

Для этого не обязательно читать матлогику, а для установления нижней планки, как уже писал epros, матлогики будет недостаточно — мы должны будем точно так же договориться о том, где у нас дно, используя и матлогику. В конечном счёте она сама полноценный раздел математики.

oleg.k в сообщении #1418885 писал(а):

А вот это интересно. Где можно почитать матлогику с т.з. деревьев?

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

Идея тут настолько же проста, что выше: мы индуктивно определяем интересующие выражения, но с большим числом $n$ альтернатив и возможных способов вхождения подвыражений, и удобно думать о них как о деревьях с $n$ типами вершин, у каждой из которых какое-то конечное число поддеревьев, зависящее лишь от типа вершины, и поддеревья идут в некотором порядке, так что можно говорить о первом, втором и т. д.. Такие «хорошие» деревья легко выделяются из всех упорядоченных деревьев с $n$ типами вершин, которые сами довольно ясно определены, не противны наивным взглядам и не несут противоречий при формализации. Для более реальных по сложности выражений деревья и требования к поддеревьям вершин могут быть ограничены типами из некоторого обозримого множества, так что виды вершин получают типы $T_1\times\ldots\times T_k\to T$, где $T_1,\ldots,T_k$ — требуемые типы поддеревьев вершины, а $T$ — тип дерева, которое получается с такой вершиной в корне. (Возможны и другие усложнения.)

oleg.k в сообщении #1418885 писал(а):

А я даже не знаю толком, что такое символ Символ, который реально написан на бумаге? Или "абстрактный" символ? А может и то и другое? Можно так: "абстрактный" символ - это "класс" "похожих" символов (одной формы)? (И что такое тогда "класс"?)

Как уже написали, тут можно падать бесконечно, так что стоит предъявить к таким понятиям другие требования: во-первых, не очень формальные, потому что при формализации мы провалимся на уровень ниже; во-вторых, операционные: что мы должны уметь делать с этими вещами. Для символов мы должны уметь проверять их равенство, во-первых всегда результативно (не зависать для каких-то пар символов), и во-вторых желательно побыстрее (это более неформальное требование). Кроме того мы должны уметь перечислить все символы и так же, если мы рассматриваем что-то кроме них, уметь (результативно) определить, символ перед нами или что-то ещё.

Это всё. Считать ли буквы разного цвета разными или одинаковыми, определяется уже уровнем рассмотрения, который — пока мы биологические существа вида Homo sapiens — можно задать только неформально в процессе коммуникации с другими сторонами, с которыми мы хотим взаимопонимания.

oleg.k в сообщении #1418885 писал(а):

С именами вообще беда. Есть ли "взаимно однозначное соответствие" между именами и их "смыслами"? А между именами и их "объектами"? А между "смыслами" и "объектами"?

В общем случае значение имени зависит от контекста и действительно может быть не единственным и не существовать. Последние два часто можно «вынести за скобки», но зависимость от контекста обычно полезна. Например, что такое 2? Для довольно большого числа случаев можно сказать, что $2$ определяется как $1+1$, где $1$ и $+$ — это единица и сложение рассматриваемого полукольца. Таким образом мы можем говорить о натуральном числе 2, целом числе 2, комплексном числе 2 и даже о том, что $2 = 0$ в поле характеристики 2 или булевом кольце.

oleg.k в сообщении #1418885 писал(а):

Как быть, когда имя само является объектом?

Обычно когда об этом надо говорить, есть (как минимум?) две альтернативы:
(1) Явно разделают уровни имён и того, что может быть их значениями, и вводят операцию «цитирования», превращающую первое во второе. В таком случае всё просто — имя никогда само по себе не является объектом, но может быть «поднято» (или «спущено», как смотреть) туда, и это уже не будет имя, это будет выражение, содержащее такое имя, и у этого выражения у самого будет имя.
(2) Имена — это значения «имён выше уровнем», уже третьим, и эту башню можно строить и далее ввысь (но редко нужно). Так, иногда говорят о метапеременных, но это может быть полезно как раз для целей матлогики или теорий о языках, но не везде подряд.
Такая эзотерика вам скорее всего не пригодится, она именно что возникает в основном для нужд таких хитрых разделов, а не какого-нибудь там матанализа.

oleg.k в сообщении #1418885 писал(а):

Ну мне кажется сомнительным modus pones. Кто вообще сказал, что я должен верить, что он работает?

А он работает и не всегда, но для этого рассматриваемая логика должна быть или слишком простой и бесполезной, или такой сложной, что там можно сказать MP разными способами и не все из них хороши.

MP идёт всегда в связке с импликацией и выражает часть её смысла: мы не можем принять выводимой импликацию $A\to B$, когда при этом не можем вывести $B$, имея $A$. Аксиоматически мы можем гарантировать обратную сторону монеты: мы обязаны принять выводимой $A\to B$, если из $A$ можем вывести $B$. Но хотя бы одно правило вывода нам понадобится.

-- Пт окт 04, 2019 00:32:13 --

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

[Munin]

arseniiv в сообщении #1418871 писал(а):

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

Между прочим, это довольно глубокий вопрос, от которого не стоит так отмахиваться. Именно на расположении деревьев в виде строк основано фундаментальнейшее свойство алгебры - ассоциативность. (Коммутативность тоже, хотя это не так очевидно: суть коммутативности в том, чтобы упрощать выражения $xyx=x^2y.$) Интересно попробовать придумать алгебру выражений, не вытянутых в одномерную строчку, хотя сложности там наступают на первых же шагах. (Например, взять алгебраическую операцию $f(x,y,z),$ и расположив аргументы треугольником, попробовать для неё придумать содержательный аналог ассоциативности.)

(Оффтоп)

Упоминание этого я слышал в спецкурсе Вавилова Высшие законы композиции, если вообще хоть что-либо правильно понял из первой лекции: https://www.lektorium.tv/course/27193
= https://www.youtube.com/playlist?list=PL-_cKNuVAYAVAONqkAJ7UuOx6dY0y0CY2
к сожалению, это сильно не мой уровень

А почему строки лучше деревьев: они образуют меньшее пространство, и соответственно, более структурированное. А с коммутативностью ещё меньшее пространство: всего лишь $\mathbb{Z}^n.$