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

[vek88]

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

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

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

Как общественность смотрит на подобную шизу? Интересно ли это кому-нибудь?

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

Короче, начинаю думать, какой/какие из начальных разделов матана формализовать в К-системе.

Может быть общественность подскажет что-то конкретное?

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

Я догадываюсь, что Вы не расположены к дискуссиям со мной ...

epros

Вполне расположен. Просто до сих пор у нас это не получалось - ИМХО вопросы были до сих пор не вполне конкретные и нечетко сформулированные.

А теперь появился шанс в связи с конкретным математическим вопросом - представлением вполне понятных вещей (начальных понятий матана) в конкретной нефинитной формальной системе (в К-системе).

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

[vek88]

Сказано - сделано - флаг в руки и вперед с песней.

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

post283784.html#p283784
post284210.html#p284210
post284468.html#p284468

К-системы мы используем в качестве средства построения теорий.

Обращаю внимание, что всякий новый объект или новое понятие вводится (=определяется, представляется) правилами К-системы, которые вводят (=определяют, представляют) этот объект или понятие.

Разумеется, мы вправе строить метатеории над нашими теориями.

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

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

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

[vek88]

Забыл напомнить методологию, которой придерживаюсь в этой теме - см. post283539.html#p283539.

Итак, попробую вспомнить "студенческие ощущения о теории множеств". Для меня это были ощущения наивной теории множеств. Да, иногда кто-то где-то сообщал о парадоксах наивной теории множеств. Однако честно скажу - до меня они не доходили, что парадокс Рассела, что Кантора. Я воспринимал их как некую экзотику, не имеющую отношения к любимой математике. Соответственно, у меня не возникало необходимости (и желания) соваться в аксиоматическу теорию множеств.

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

В общем у меня была настолько сильная убежденность в надежности "наивной" математики, что ... облом - не подходи ко мне.

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

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

Поясню это на примере определения в полной К-системе операции объединения множеств. Это определение вводится правилами

$$\frac{x \in X}{x \in X \cup Y},\frac{x \in Y}{x \in X \cup Y}.$$

Почему это определение не нарушает полноты? Очень просто - предположим, что дана произвольная полная К-система $E$, определяющая предикат $x \in y$. Дополнив К-систему $E$ вышеуказанными двумя правилами, мы снова получаем полную К-систему. Разумеется, мы предполагаем, что в "исходной" К-системе $E$ знак $\cup$ не входит в алфавит. Другими словами, только вышеприведенные два правила определяют операцию объединения в построенной К-системе.

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

Для подтверждения этой мысли рассмотрим далее еще несколько примеров. А затем попытаемся "опровергнуть" эту мысль - и посмотрим, почему это не может быть сделано в полных К-системах.

[vek88]

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

$$(x \in X \cup Y) \leftrightarrow ((x \in X) \vee (x \in Y)).$$

Доказывали мы это рассуждая в точности так же, как если бы доказывали эту метатеорему в К-системе. Т.е. говорим стандартную мантру "предположим истинна левая часть". Это значит (в К-системе), что имеется И-вывод данного утверждения. В этом И-выводе в корне хотя бы одна из двух схем предыдущего поста. Значит, хотя бы одно из утверждений правой части нашей метатеоремы истинно. Истинность правой части доказана.

Влево аналогично. Предположим, что $x \in X$ истинно. Тогда есть И-вывод этого утверждения. Достроим его первой схемой предыдущего поста - получим И-вывод левой части теоремы, т.е. левая часть истинна.

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

[vek88]

В качестве следующего примера на уровне первого курса рассмотрим, следуя 3-х-томному Фихтенгольцу, введение иррациональных чисел. Итак, пусть $a, b, c, ...$ обозначают рациональные числа. Предполагается, что мы - "первокурсники" - уже знаем все необходимое о них.

Рассмотрим разбиение множества всех рациональных чисел на два непустые множества $A, A'$. Мы будем называть такое разбиение сечением, если выполняются условия:
1. Каждое рациональное число попадает в одно и только одно из множеств $A$ или $A'$.
2. Каждое число $a$ множества $A$ меньше каждого числа $a'$ множества $A'$.

Рассмотрим как это определить в К-системе. При этом мы не будем заморачиваться на тщательном уточнении нашего синтаксиса, полагаясь на интуитивную самоочевидность всех конструкций. Мы даже не будем записывать в явном виде правило, определяющее понятие сечения $A | A'$, а ограничимся лишь словесными пояснениями, из которых будет следовать полнота рассматриваемого определения.

Итак, в заключении правила записан образец (=терм) утверждения о том, что некоторый объект $A | A'$ является сечением. А посылками этого правила являются образцы (=термы), утверждающие, что:
1. $A, A'$ - множества рациональных чисел.
2. $\forall a ((a \in A \wedge a \notin A') \vee (a \in A' \wedge a \notin A))$.
3. $\forall a \forall a' ((a \in A) \wedge (a' \in A') \rightarrow (a < a'))$.

Из свойств замкнутости полных К-систем относительно логических связок и кванторов следует, что для любых полных определений множеств рациональных чисел $A, A'$ утверждение о том, что объект $A | A'$ является сечением, либо истинно, либо ложно. Это и означает, что данное определение корректно, т.е. не выводит нас из класса полных К-систем.

Впрочем, а как же может быть иначе - ведь здесь все просто и очевидно.

Дав определение сечения - в К-системах посредством введения вышеописанного правила - мы расширили "теорию первокурсника". Соответственно, мы очевидным образом может доказать новые метатеоремы над нашей "очередной версией К-системы". Например, о том, что всякое рациональное число, меньшее числа $a$ нижнего класса, также принадлежит нижнему классу.

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

[vek88]

Цитата:

И тишина ... а вдоль дороги мертвые с косами.

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

В качестве простейшего примера множества множеств рассмотрим счетное множество подмножеств множества натуральных чисел $N$. Конечно, традиционно первокурсники рассматривают диагональные построения на примере действительных чисел ..., но мне лень писать слишком громоздкие формулы ... поэтому ушел в подмножества $N$. Да и здесь, опять же от лени, схитрю - в качестве счетного множества подмножеств множества $N$ буду рассматривать произвольное бинарное отношение $R$ на множестве $N$. Таким образом, для любого $n \in N$ ему соответствует множество $A_n$ всех $m$ таких, что $n R m$ (число $m$ находится в отношении $R$ с числом $n$).

Традиционное диагональное построение в К-системе очевидно и вводится правилом

$$\frac{\ominus x R x}{x \in D}.$$

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

[vek88]

Построенное множество натуральных чисел $D$ (для порядка надо было бы добавить в определение $D$ посылку $x \in N$, или оговорить тип переменной $x$) по определению не совпадает ни с одним из множеств $A_n$.

Докажем это. Предположим противное - $D = A_n$. Тогда, если $n \in D$, то значит существует И-вывод этого утверждения, т.е. применение правила предыдущего поста для $x=n$. Но это возможно тогда и только тогда, когда $n R n$ ложно, т.е. $n \notin A_n$ и значит $n \notin D$. И наоборот, если $n \notin D$, то значит $n \in D$ ложно, следовательно $n R n$ истинно, т.е. $n \in A_n$ и значит $n \in D$ . Таким образом, предположение о равенстве $D$ и $A_n$ приводит к противоречию - число $n$ одновременно принадлежит и не принадлежит множеству $D$.

Рассмотренное диагональное построение показывает, что множество всех подмножеств множества $N$ не является счетным - и его мощность больше мощности множества $N$. Действительно, для любого счетного множества $M$ подмножеств множества $N$ мы посредством этого диагонального построения строим новое подмножество $N$, т.е. подмножество, отсутствующее в $M$.

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

Но ... - интрига нарастает, фанаты ликуют, передние ряды ... потеряли дар речи.

Продолжение следует.

[vek88]

Итак, создается ощущение, что для любого множества множеств $M$ всегда можно построить множество, отсутствующее в $M$. Однако все не так просто - и именно здесь К-система засверкает яркими красками - никто иной нам не поможет разобраться с наклевывающейся парадоксальной ситуацией. Однако идем по порядку - и для начала максимально упростим ситуацию.

Пример 1. Рассмотрим конечное множество множеств ${A,B,C}$, определяемых единственной аксиомой $A \in A$ (мы опять опускаем подробности, касающиеся уточнения алфавита и прочих "мелочей", полагаясь на интуицию). Поскольку для утверждений $B \in B, C \in C$ отсутствуют выводы, эти утверждения ложны, следовательно, $B \notin B, C \notin C$.

В этом случае правило

$$\frac{\ominus x \in x}{x \in D}$$

работает правильно - множество $D = \{B,C \}$ и, следовательно, отлично от всех трех множеств $A,B,C$.

А теперь маленькое объявление. Внимание! Наш самолет входит в зону повышенной турбулентности. В целях безопасности просьба пристегнуть ремни.

Пример 2. Рассмотрим конечное множество множеств ${A,B,C,D}$, определяемых аксиомами (и только ими) $A \in A, B \in D, C \in D, D \in D$. Снова для утверждений $B \in B, C \in C$ отсутствуют выводы, эти утверждения ложны, следовательно, $B \notin B, C \notin C$.

Теперь правило

$$\frac{\ominus x \in x}{x \in D}$$

работает неправильно - множество $D = \{B,C,D \}$ и, следовательно, отлично от всех трех множеств $A,B,C$, но совпадает с $D$!

Нам не удалось построить "новое" множество с помощью традиционного диагонального построения.

Почему так? Очень просто - в построенной К-системе имеются два вывода утверждения $D \in D$ - применение аксиомы

$$D \in D$$

и применение нашего правила

$$\frac{\ominus D \in D}{D \in D}.$$

Первый вывод является И-выводом, поскольку не имеет исключений, следовательно, утверждение $D \in D$ истинно. А второй вывод является Л-выводом, поскольку имеет в качестве исключения И-вывод. Но это уже никого не волнует, поскольку истинность $D \in D$ установлена.

Другими словами, мы пытались построить новое множество, но поскольку это множество уже было в исходной системе множеств, К-система не дала нам переопределить это множество.

Контрольное упражнение в голову. Рассмотрим конечное множество множеств ${A,B,C,D}$, определяемых аксиомами (и только ими) $A \in A, B \in D, C \in D$. Здесь для утверждений $B \in B, C \in C, D \in D$ отсутствуют выводы, эти утверждения ложны, следовательно, $B \notin B, C \notin C, D \notin D$.

Покажите, что теперь вышерассмотрнное диагональное построение приводит к нарушению полноты - утверждение $D \in D$ оказывается неразрешимым. Следовательно, в данном случае диагональное построение вообще некорректно, поскольку выводит нас из класса полных К-систем.

ЗЫ. Не слышу визга восторженных фанатов. Или кто-то хочет выступить с разоблачениями?

[vek88]

Попытаюсь уточнить мораль предыдущего поста. Возможно еще менее строго, но зато ИМХО более понятно.

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

Если же такая коллизия возникает, то, в лучшем случае, мы не сможем построить "новое" множество. А в худшем случае мы вообще выйдем за пределы полных К-систем, что в традиционной трактовке означает парадокс.

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

Да и уважаемый Рассел зря старался по тем же причинам. Ведь он множество всех множеств достроил правилом

$$\frac{x \notin x}{x \in D}.$$

Т.е. он хотел построить "новое" множество. Но это не получается в К-системе: в лучшем случае это множество уже есть (тогда $D \in D$), либо определение Рассела не корректно, поскольку нарушает полноту К-системы.

[AlexDem]

Я вот пробовал разобраться с материалом, но пока не совсем понимаю даже в каком смысле Вы с Xaositect понимаете полноту К-систем (был такой разговор где-то в начале темы)...

Нашёл достаточно лёгкую для прочтения книгу К.М. Подниекса "Вокруг теоремы Гёделя". Там определена причина парадоксов (разделы 2.2 - 2.3) как:

Цитата:

Г.Кантор писал в свое время: "Множество - это многое, мыслимое нами как единое". Но каким образом многое можно мыслить как единое? Только задав отличительный признак того, что входит в многое. Это и будет тем единым, что может связать многое вместе. Обозначения, отражающие такой подход, прочно вошли в математику, например $K=\{x | K(x)\}$, где $K$ - свойство "быть крокодилом". По этому поводу принято говорить, что $K$ - "множество всех крокодилов", и обращаться с ним как с единым объектом.

Немецкий математик Готлоб Фреге (первый ученый, достигший серъезных успехов в формализации математики) в своей формальной системе реализовал эту идею объединения многого в единое. На современном нам языке принцип Кантора-Фреге формулируется в виде так называемой схемы аксиом свертывания. Пусть $F(y)$ - формула на языке теории множеств (кроме переменной y она может содержать и другие свободные переменные, тогда мы будем считать их параметрами). На $F(y)$ можно смотреть как на утверждение: "множество y обладает свойством $F$". Следуя подходу Кантора-Фреге, все множества y, обладающие свойством $F$, можно объединить в единое множество $x=\{y | F(y)\}$.
...
Как ни странно, оказалось, что некоторые из аксиом свертывания приводят к противоречиям. Это значит, что в самом общем виде схема свертывания не может служить основой теории множеств.
...
Решающая идея принадлежит Эрнсту Цермело. Он предложил принять в качестве аксиом теории множеств только те варианты аксиом свертывания, которые реально используются в математике. К 1908 г. Э.Цермело уже завершил "переучет" средств, которые используются в математике для образования множеств, и опубликовал свой вариант аксиом теории множеств. Оставим пока в стороне вопрос о том, какие конкретные аксиомы содержала эта система. Понятно, что аксиомы $Z2\{(y \not \in y)\}$, приводящей к парадоксу Рассела, в ней не было, поскольку рассуждения такого рода в математической практике не встречаются.

А что нового дают в понимании парадоксов K-системы? Определение Рассела ведь сформулировано ничем не хуже других - взять все множества, обладающие свойством $F$. Чем нарушение полноты здесь лучше возникновения парадокса в обычной теории?

[vek88]

AlexDem в сообщении #430488 писал(а):

Я вот пробовал разобраться с материалом, но пока не совсем понимаю даже в каком смысле Вы с Xaositect понимаете полноту К-систем (был такой разговор где-то в начале темы)...

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

[AlexDem]

Я нашёл, здесь:

Цитата:

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

Прошу прощения за неточность - я уже тоже забыл просто...

-- Сб апр 02, 2011 21:52:00 --

Мой вопрос, пожалуй, был связан вот с чем - в К-системах всё выводимое истинно, невыводимое - ложно. Почему не может оказаться выводимой формула, которая в классическом случае - ложна? Я прошу прощения, если вопросы элементарны, просто самому во всём разобраться сложно.

[vek88]

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

Теперь буду отвечать на Ваши вопросы - они ИМХО вполне конструктивны и бьют в самую точку. Поскольку не хочу Ваши хорошие вопросы испортить своими плохими ответами, мне потребуется определенное время для ответа на них.

[vek88]

AlexDem

Наконец, подумав над Вашими вопросами, смог выделить достаточно времени, чтобы без спешки и обстоятельно ответить на них. Отвечать буду по порядку их поступления и начну с Вашего поста post430488.html#p430488.

Прежде всего о приведенной Вами цитате из книги К.М. Подниекса. Она ИМХО коротко и ясно отражает ситуацию в математике, возникшую в результате появления парадоксов. Однако рецепт избавления от парадоксов - аксиоматизация теории множеств - мне не очень нравится по ряду причин. В частности:

1. Мало ли что может взбрендить математикам (в хорошем смысле) по мере развития математики. А мы, сочинив конкретную аксиоматизацию теории множеств, закрыли им возможность развития теории множеств в будущем. Спрашивается - а имеем ли мы право лишать математиков такой возможности?

2. В реальной математической практике мы ИМХО, действуя интуитивно (=наивно), не оглядываемся ни на какую аксиоматизацию теории множеств. Спрашивается - а почему никаких парадоксов у нас не получается и наши математические построения даже и не думают глючить?

3. Ну да ладно, приняли некую аксиоматизацию. Спрашивается - а где гарантия, что в ней нет противоречия? Ведь мы не доказали ее непротиворечивость?

4. Вот Вы цитируете:

Цитата:

Решающая идея принадлежит Эрнсту Цермело. Он предложил принять в качестве аксиом теории множеств только те варианты аксиом свертывания, которые реально используются в математике. К 1908 г. Э.Цермело уже завершил "переучет" средств, которые используются в математике для образования множеств, и опубликовал свой вариант аксиом теории множеств.

Да, 100 лет назад, видимо, было реально провести "инвентаризацию" математических средств образования множеств. Но как-то сомнительно, что это практически возможно сегодня - ведь математика сегодня ИМХО представляет собой нечто необъятное.

-- Пн апр 04, 2011 16:46:38 --

Далее Вы пишете:

AlexDem в сообщении #430488 писал(а):

А что нового дают в понимании парадоксов K-системы? Определение Рассела ведь сформулировано ничем не хуже других - взять все множества, обладающие свойством $F$. Чем нарушение полноты здесь лучше возникновения парадокса в обычной теории?

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

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

А с помощь К-систем мы (надеемся) формализовать - практически в неизменном виде - наше интуитивное (=наивное) математическое мышление. Другими словами, мы (надеемся) объяснить почему у нас все клево в наивной математике.

А заодно мы надеемся и объяснить сбои этого наивного мышления типа парадоксов Кантора и Рассела.

Вот это "маленькое" различие ИМХО очень важно и интересно.

-- Пн апр 04, 2011 17:03:10 --

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

Мой вопрос, пожалуй, был связан вот с чем - в К-системах всё выводимое истинно, невыводимое - ложно. Почему не может оказаться выводимой формула, которая в классическом случае - ложна? Я прошу прощения, если вопросы элементарны, просто самому во всём разобраться сложно.

Да, такое возможно. Но ИМХО только в случае ошибки при построении К-системы - если мы неправильно представили нашу интуицию в виде К-системы.

[vek88]

AlexDem

Совсем забыл, что Вы программер. С учетом этого ИМХО полезна аналогия с программированием.

Итак, пишем мы программы, а к нам приходит некто и говорит что-то типа.

Цитата:

Господа! Вы все делаете не так. Вот и программы у вас глючат, зависают и зацикливаются. Все, заканчивайте так писать программы - теперь будете программировать вот в этой формальной системе (и вываливает нам некую "аксиоматику программирования").

Что мы такому умнику ответим? Наверно это будет такой ответ.

Цитата:

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

Согласитесь, мы бы послали этого умника. А что ж мы уже сто лет носимся с аксиоматикой теории множеств, как с писаной торбой? Ну да, интересный раздел математики ... но не более того. Да, мы готовы поговорить об этом ... на досуге. Но в плане практической математической деятельности аксиоматика теории множеств нам ничего не дает.

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