Основания математики - элементарное рассмотрение

[Someone]

vek88 в сообщении #277515 писал(а):

Знаки: $A$ $\in$
Аксиома: $A \in A$
Правило вывода: если $A \notin A$, то $A \in A$

Здесь определяемое понятие находится как в заключении правила, так и в его посылке. Но ничего страшного при этом не происходит - благодаря аксиоме я заключаю, что $A \in A$.

Здесь $A$ - не определяемое понятие, а символ языка теории. Причём, его роль не определена. Это константа или переменная? Или ещё что-то? Аналогичные вопросы - о символе $\in$.

Символа $\notin$ в алфавите теории также не вижу. Откуда он взялся?

vek88 в сообщении #277601 писал(а):

Например, "кто-то" здесь сказал

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

vek88 в сообщении #277601 писал(а):

А самое главное, с чего я начал, - это слабость мышления у людей. Ведь вот прошел целый век, а мы ломаем копья по поводу парадокса Рассела.

Это Вы ломаете копья по поводу парадокса Рассела, теорем Гёделя, аксиомы выбора и т.п.. Специалисты занимаются более полезными делами. А рассуждения о "слабости мышления" к тематике данного форума отношения не имеют.

[Xaositect]

vek88 в сообщении #277535 писал(а):

Спасибо, Xaositect, за разъяснение Вашей точки зрения.

На мой взгляд, имеют право на существование два подхода: конструктивный и экзистенциальный.

При конструктивном подходе я вижу "букву $A$" и для меня это "множество $A$, определяемое конкретной формальной системой". Для меня нет ничего кроме формальных систем и того, что построено в них. В том числе, метатеории, метаметатеории и т.д. - это тоже формальные системы для рассуждения о теориях более низкого уровня. Разумеется, я не верю в существование каких-то еще множеств вне моих формальных систем. И мне не нужно использовать определения типа "множество $N$ - то множество слов выводимых в такой-то формальной системе". Я просто говорю, что "буква $N$" обозначает множество (или является множеством) натуральных чисел.

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

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

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

Конструктивисты тоже не отождествляют символы (буква "$A$") и смыслы (множество $A$). Для конструктивиста тоже существует два уровня - конструктивные объекты и способ построения этих конструктивных объектов, который является определением некоторого ансамбля объектов.
То есть есть внутренняя теория, порождающая олбъекты, и внешняя, изучающая внутреннюю.
Метатеория тоже может быть формализована, это даже может быть та же самая теория синтаксически (например, в арифметике можно пронумеровать все возможные утверждения любой теории и выразить отношение "утверждение доказуемо"), но это как бы два "экземпляра" теории, два смысла. В арифметике: есть утверждение "$\neg\exists x Prf(x, F)$", где $Prf$ - это сложный предикат, а $F$ - некоторая константа. Но это утверждение может иметь второй смысл, когда оно является утверждением метатеории - оно говорит : "не существует доказательства формулы $0=1$".
У того же Мартин-Лёфа в "Очерках...":

Цитата:

Пусть $a$ обозначает слово в данном алфавите, и пусть $E$ и $F$ — рекурсивно перечислимые множества слов в том же алфавите. Введем следующие определения.
$a\in E$ (читается «$a$ принадлежит $E$» или «$a$ является элементом множества $E$»), если $a$ доказуемо в системе Поста $E$.

и еще похожие определения.
Здесь он говорит о строках и формальных системах вне их самих, в объемлющей теории рекурсивно-перечислимых множеств. Да, формальная система сама по себе - конструктивный объект, можно формализовать теорию р-п множеств и выводить в ней формулы вида $a\in E$, можно изучать внутри нее саму эту теорию, но два уровня смысла никуда не деваются.

[vek88]

Уважаемый, Xaositect!

Мне кажется, что наша тема уже не развивается "рекурсивным" образом в смысле перечисления новых высказываний, а просто зациклилась на повторении уже сказанного. Причем, на второстепенных вещах. Разве я возражал против очевидного и естественного: теории и метатеории , предназначенной для рассмотрения этой теории.

Хочу также добавить, что данная тема, по всей видимости, исчерпана. Я высказал, что хотел в пику теме "Могут ли машины мыслить?". Другие участники обсуждения тоже смогли высказать все, что думают обо мне и моей теме. Наконец, пассивные читатели данной темы, как мне кажется, получили немалое удовольствие, наблюдая за нашей битвой. Кстати, количество ответов/посещений - 40/400 за двое суток - свидетельствует о высокой популярности темы.

Но при всем при этом хочу заметить, что из моего (пусть "экстремистского") варианта конструктивизма Вы не сможете вывести противоречие. Так же как и я при этом ничем себя не ограничу. Или это не так? Итак, или опровергайте только что сказанное мной в этом абзаце, или давайте, если общественность не возражает, закроем тему.

[vek88]

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

Для них особо рекомендую первую главу упоминавшейся книги Мартин-Лёфа, Очерки по конструктивной математике. Причем даже не всю главу, а до раздела 7 (Универсальная система) включительно.

Затраты времени на изучение (всего-то порядка 30 страниц) с лихвой окупятся. Читатель узнает много интересного и приобретет полезный опыт. В частности, в разделе 7 автор всего на одной странице приводит общепонятное доказательство существования неразрешимого рекурсивно перечислимого множества! В свете универсальной системы кратко обсуждается парадокс Рассела и интуиционистская логика.

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

[vek88]

Если честно, я не очень понимаю, почему такой относительно простой факт (далее - Теорема Чёрча) как существование нерезрешимого рекурсивно перечислимого множества (Church 1936) был доказан позже теоремы Гёделя о неполноте арифметики (1931). Ну да ладно - это мои трудности в понимании трудностей Гёделя и Чёрча.

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

На самом деле надежды Гильберта разрушаются и более простой Теоремой Чёрча, но доказанной почему-то на 5 лет позднее. Ведь в чем "на пальцах" смысл этой теоремы в плане оснований математики:

1. Мы решили найти убежище в рекурсивно перечислимой истине.

2. Но из Теоремы Чёрча следует, что эту истину "невозможно интерпретировать в классической логике".

3. Разумеется, можно эту истину интерпретировать в классической логике на более высоком уровне иерархии множеств, например, из $\Pi_1^1$-множеств.

4. Но там мы снова имеем аналогичную теорему: сужествует $\Pi_1^1$-неразрешимое $\Pi_1^1$-множество (его дополнение не является $\Pi_1^1$-множеством).

И т.д. Таким образом, любая формализация истины неполна.

[Владимир Рогожин]

vek88 в сообщении #278622 писал(а):

Таким образом, любая формализация истины неполна.

1. "...истина должна быть нарисована и предъявлена "неограниченному кругу" зрителей." (А.Зенкин "Научная контрреволюция в математике" http://science.ng.ru/magnum/2000-07-19/5_mathem.html)
Поэтому в рисовании опирайтесь на абсолютные формы существования (материи).
2. У Вас тема "Основания математики-элементарное рассмотрение".
Вопросы нематематика:
- сколько у Вас "оснований"?
- не заметил "элементарности".
Поясните, пожалуйста, что Вы понимаете под "элементарностью"?

[vek88]

Владимир Рогожин в сообщении #279239 писал(а):

vek88 в сообщении #278622 писал(а):

Таким образом, любая формализация истины неполна.

У Вас тема "Основания математики-элементарное рассмотрение".
Вопросы нематематика:
- сколько у Вас "оснований"?
- не заметил "элементарности".
Поясните, пожалуйста, что Вы понимаете под "элементарностью"?

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

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

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

Об элементарности. А разве где-либо я вышел за рамки элементарного? Разве стандартное диагональное построение Кантора по поводу действительных чисел относится к неэлементарным? Это же проходят на первом курсе.

Более точно, элементарность я понимаю в житейском смысле, как нечто простое, ясное и ежу.

[vek88]

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

А может быть реанимировать данную тему в ее прямом смысле? И попытаться для всех страждущих в порядке благотворительности изложить энти самые основания на элементарном уровне?

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

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

[vek88]

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

1. Рассмотрение не будет строго математическим. Это однако не означает, что оно будет некорректным. Моя задача - понятно изложить непростые вещи, как для непрофессионалов, так и для профессионалов. Последние, надеюсь, при желании смогут сформулировать строго математически все сказанное мной.

2. Я предлагаю некий оргинальный подход к основаниям математики. При этом, однако, я не пытаюсь учинить революцию и закрыть Америку.

3. Я не всегда буду следовать общепринятой терминологии или известным подходам. Соответственно, большая просьба не попрекать меня этим. Я буду признавать лишь упреки в непонятности изложения или в некорректности сказанного мной.

4. Я не буду исписывать страницы формулами, а лишь буду указывать наиболее существенное, предполагая, что заинтересованные участники дискуссии смогут сами дописать недостающее.

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

6. Постараюсь объяснить (но не изложить) как взгляд конструктивистов, так и классиков на основания математики.

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

С уважением,
vek88

[hurtsy]

vek88

Цитата:

И сформулировал контрвопрос "Могут ли люди мыслить?".

Могут, но для формализма это не является необходимым.

Цитата:

Ведь на самом деле и ежу понятно,

Тут нет упорядоченности. У ежа и у человека есть своя "ниша существования" в которой они мыслят.

Цитата:

Итак, если я попрошу кого-то решить систему уравнений , $x=0, x=1$

Есть такой метод наименьших квадратов. В математической обработке измерений, в экономических исследованиях и в финансовой математике широко используется. В Вашем профиле видно, что Вы этим интересуетесь.
С уважением,

[vek88]

Тема 1. Канонические системы (исчисления) Поста

Основные факты о канонических системах Поста приведем, следуя книге Мартин-Лёф П. Очерки по конструктивной математике.

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

$$\frac {t_1t_2…t_n}{t},$$

где все $t,t_1, t_2,…,t_n (n \geqslant 0)$ являются термами. Термы $t_1, t_2,…,t_n$ называются посылками, $t$ – заключением правила. Правила без посылок называются аксиомами (черта при записи аксиом не используется).

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

Если дана каноническая система, определим по индукции понятие вывода (слова в этой системе).
1. Применение аксиомы – вывод этого применения.
2. Если $P_1,…,P_n$ – выводы соответственно слов $a_1,…,a_n$ и

$$\frac {a_1…a_n}{a},$$

– применение некоторого правила, то

$$\frac {P_1…P_n}{a},$$

– вывод слова $a$.
Слово, для которого имеется вывод, называется выводимым в данной канонической системе.

[vek88]

Примеры

Чтобы избежать коллизий, далее пустое слово обозначается знаком □.

1. В канонической системе:
Знак $|$
Переменная $x$
Правила □ $\frac{x}{x|}$
выводимы в точности слова □,$|,||, … $, состоящие из произвольного числа знаков $|$.

2. В канонической системе:
Знак $|$
Переменная $x$
Правила □ $\frac{x}{x||}$
выводимы в точности слова □,$||,||||, … $, состоящие из четного числа знаков $|$.

3. В канонической системе:
Знаки $A$ $B$
Переменная $x$
Правила $AB$ $BA$ $\frac{xA}{xAB}$ $\frac{xB}{xBA}$
выводимы слова $AB$, $BA$ и слова, полученные из них поочередным приписыванием справа знаков $A, B$.

[vek88]

Выразительные возможности

Канонические системы мы будем использовать для представления математических объектов, в частности: множеств, отношений, операций. Так, приведенная выше в Примере 1 система представляет (= вводит, определяет) множество натуральных чисел $N$.

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

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

2. Соответственно, мы будем использовать вспомогательные знаки при введении новых объектов для ссылки на уже определенные ранее объекты (по аналогии с идентификаторами в программировании).

Для примера рассмотрим представление целых чисел. Прежде всего, модифицируем определение множества $N$:

Знак $|$
Вспомогательный знак $N$
Переменная $x$
Правила $N$ $\frac{Nx}{Nx|}$
Здесь выводимы в точности слова $N,N|,N||, … $.

Для введения целых чисел теперь используем следующую каноническую систему.

Знаки $|$ $-$
Вспомогательные знаки $N$ $INT$
Переменная $x$
Правила $\frac{Nx}{INT x}$ $\frac{N|x}{INT -x}$

Пдчеркнем, что мы считаем приведенные выше канонические исчисления определениями множеств $N$ и $INT$.

Соответственно, мы не будем произносить мантры типа множество натуральных чисел - это множество тех и только тех слов в алфавите $\{|\}$, которые выводимы в данной канонической системе, поскольку эти мантры в данном контексте представляются нам лишними. Впрочем, если использование этих мантр кому-то нравится, можно продолжать их повторение - ничего страшного при этом не случится.

[vek88]

Выразительные возможности - продолжение

Сложение натуральных чисел в алфавите | сводится к приписыванию двух чисел друг к другу. Ноль представляется пустым словом.

Знаки | + =
Вспомогательный знак $N$
Переменные $x$ $y$
Правило

$$\frac{{Nx} \verb

Пусть в канонических системах уже определены два множества $A$ и $B$. Тогда их объединение $A\cup B$ определяется правилами

$$\frac{Ax}{x},\frac{Bx}{x}.$$

Здесь и далее мы позволим себе не выписывать явно знаки, вспомогательные знаки и переменные.

Чтобы народ не уснул, задачи.

Задача 1. Найдите и исправьте ошибку в определении целых чисел.

Задача 2. Сформулируйте в канонической системе определение пересечения двух множеств $A\cap B$.

[vek88]

Заключение

На интуитивном уровне понятно, что канонические системы в определенном смысле очень похожи на языки программирования. Следовательно, можно предположить, что в этих системах можно «запрограммировать» все, что можно запрограммировать и на развитых языках программирования. А теперь вспомним, что всякая программа – это алгоритм.

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

Возникает естественный вопрос: а РП-множества – это много или мало?

Анекдот. Чебурашка нашел копейку и спрашивает у Гены – а что я могу купить на нее? – Да все что хочешь. – Чебурашка пришел в универсам, набрал полную корзину, хлоп копейку кассирше. – Что, дура, смотришь, гони сдачу!

Так вот, к сожалению, с РП-множествами как с копейкой, – это нечто, но недостаточно для нормальной математической жизни (здесь сторонники конструктивного направления, пожалуй, меня съедят).

В самом деле, мы можем многое определить в канонических системах (то бишь в РП-множествах), например, логические связки $\vee$, $\wedge$ и квантор существования.

Задача 3. Определите в канонической системе связки $\vee$, $\wedge$ и квантор существования.

Но мы не можем в них определить логическое отрицание!?

Для коллег, сомневающихся в этом, следующая задача.

Задача 4. Определите отрицание в канонической системе.

На этом мы заканчиваем рассмотрение канонических систем. Далее будем решать проблему представления отрицания.

Внимание.

Уважаемые Дамы и Господа!

Согласитесь, что излагать материал без обратной связи с аудиторией очень неудобно и неприятно. То ли меня не понимают, то ли не слушают. То ли затаились и ждут какую-нибудь глупость с моей стороны – а уж тогда все заговорят и прибегут меня топить.

Короче, двигаемся дальше только после решения Вами задач из этой темы (Задачи 1 – 4).

С уважением,
vek88