Возможности математики без математической индукции

[LaTeXScience]

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

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

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

[epros]

LaTeXScience в сообщении #553812 писал(а):

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

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

LaTeXScience в сообщении #553812 писал(а):

Более конкретный пример я уже приводил -- теорема дедукции.

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

А вообще Вы меня заинтересовали.

[Профессор Снэйп]

Я вот не совсем понимаю суть основного вопроса.

В современной математике принцип матиндукции не постулируют, а выводят из теоретико-множественных аксиом. И в чём, собственно, вопрос: как выглядела бы "старая" математика без матиндукции или как будет выглядеть "новая" математика без аксиомы регулярности? Или что-то третье?

[epros]

Профессор Снэйп в сообщении #554031 писал(а):

В современной математике принцип матиндукции не постулируют, а выводят из теоретико-множественных аксиом.

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

[Профессор Снэйп]

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

Я знаю, что есть такая математика, которая занимается исследованиями того, без какой аксиоматики можно обойтись.

Ага, есть. Называется "Reverse mathematics".

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

И, насколько я понимаю, при желании без большей части теоретико-множественной аксиоматики вполне можно обойтись.

По крайней мере, Вы согласны с тем, что аксиоматика должна быть теоретико-множественной

(Оффтоп)

Не раз замечал, что математики, работающие в "прикладных" (или в чистых, но сугубо "непрерывных") областях, недолюбливают математическую логику. Часто эта нелюбовь проистекает от непонимания и боязни непонятного. Хотя, на самом деле, они часто весьма активно пользуются всем этим...

Впрочем, страх и нелюбовь взаимны. Помню, в магистратуре ходил на спецкурс по топологическим группам и мало что там понимал. Препод меня весь год держал за троечника, поскольку в непрерывные параметрические и ещё что-то там... в общем, во все эти непрерывные хрени я откровенно не мог врубиться. Потом узнал, что у меня средний балл 4.8 и очень удивился. Спросил, где я специализируюсь, а когда я сказал ему, что на матлогике, заявил: "Ой, там же вообще такой ужас, какое-то жуткое нагромождение символов и ничерта не понятно!"

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

А ещё мне ужасно стыдно, но я до сих пор не понимаю, что такое тензор

-- Сб мар 31, 2012 12:46:22 --

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

И зачастую оказывается, что лишимся мы не таких уж важных и бесспорных вещей.

Вот не согласен я с этим!!!

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

[epros]

Профессор Снэйп в сообщении #554071 писал(а):

По крайней мере, Вы согласны с тем, что аксиоматика должна быть теоретико-множественной

Вы меня неправильно поняли.

Профессор Снэйп в сообщении #554071 писал(а):

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

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

Я так полагаю, что более правильно исходить из "минимально достаточных" аксиоматик. Т.е. если нам не нужно знать, что из каких-то бесконечных множеств каких-то немеряных кардинальностей можно построить что-то эдакое ещё большей кардинальности, то и аксиомы соответствующие не нужны. Скажем, для арифметики не нужна аксиома выбора, и слава Богу.

[Профессор Снэйп]

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

Скажем, для арифметики не нужна аксиома выбора, и слава Богу.

Ну, если выбирать из подмножеств натуральных чисел, то действительно не нужна, так как $\mathbb{N}$ вполне упорядочена. Но вообще в арифметике... Не верю, что она нигде не требуется!

Кстати, Вы в курсе, что утверждение "объединение счётного числа счётных множеств счётно" без аксиомы выбора не доказуемо! А это утверждение сильно используется в матане при построении теории меры... И на нём значительный кусок математики покоится!

[epros]

Профессор Снэйп в сообщении #554680 писал(а):

Кстати, Вы в курсе, что утверждение "объединение счётного числа счётных множеств счётно" без аксиомы выбора не доказуемо!

Честно говоря, не очень в курсе. Мне казалось, что слова "счётное множество" можно заменить словами "последовательность элементов", тогда слова "счётное множество счётных множеств" заменятся на "последовательность последовательностей элементов". После этого можно двойную нумерацию "элементов" с помощью известного диагонального метода заменить на одинарную нумерацию, т.е. продемонстрировать, что "последовательность последовательности элементов" эквивалентна "последовательности элементов". По моим понятиям это вполне равносильно Вашему утверждению, и доказано оно без аксиомы выбора. Хотя возможно, что я упустил какую-то магию, скрытую в словах "объединение", "счётное" или "множество". И этот мой промах не удивителен, поскольку я оставляю за собой право сомневаться, что словосочетанию "счётное множество" соответствует что-то реальное.

Профессор Снэйп в сообщении #554680 писал(а):

А это утверждение сильно используется в матане при построении теории меры...

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

[Someone]

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

Мне казалось, что слова "счётное множество" можно заменить словами "последовательность элементов", тогда слова "счётное множество счётных множеств" заменятся на "последовательность последовательностей элементов".

Вот одно множество можно. А чтобы получить "последовательность последовательностей", нужна аксиома выбора. Хотя бы в счётном варианте.

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

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

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

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

И этот мой промах не удивителен, поскольку я оставляю за собой право сомневаться, что словосочетанию "счётное множество" соответствует что-то реальное.

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

[epros]

Someone в сообщении #554801 писал(а):

Вот одно множество можно. А чтобы получить "последовательность последовательностей", нужна аксиома выбора. Хотя бы в счётном варианте

Любопытно, почему это? Последовательность ведь можно рассматривать как некий объект? А чем тогда последовательность таких объектов принципиально отличается от последовательности любых других элементов?

Someone в сообщении #554801 писал(а):

Счётной аддитивности без аксиомы выбора может не получиться.

Так я не возражаю: когда (и если) понадобится аксиома выбора, то и её можно ввести.

Someone в сообщении #554801 писал(а):

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

Подозреваю, что речь о нестандартных моделях ZF (теории множеств без аксиомы выбора)? И подозреваю, что "множество натуральных чисел" в этих моделях тоже является нестандартным? Если так, то понятие "счётности" множества в таких моделях, очевидно, тоже нестандартно...

Someone в сообщении #554801 писал(а):

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

Ну, почему бы не поскатываться? Интересно же, до чего можно докатиться. В конце концов, если нужно, недостающую аксиоматику всегда можно добавить: хоть всю ZFC в полном объёме.

[Someone]

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

Любопытно, почему это? Последовательность ведь можно рассматривать как некий объект? А чем тогда последовательность таких объектов принципиально отличается от последовательности любых других элементов?

Я, когда был студентом третьего курса, тоже думал: "А почему это?" Ребятам эти свои сомнения высказал. Они мне говорят: "Ну давай, доказывай." Я и начал: "Выберем какую-нибудь нумерацию каждого множества..." - и на этой фразе заткнулся. И всё понял, и больше уже не спрашиваю, почему. Потому что без аксиомы выбора мы можем выбрать нумерации для любого конечного семейства множеств, а для бесконечного - увы, без аксиомы выбора никак.

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

Подозреваю, что речь о нестандартных моделях ZF (теории множеств без аксиомы выбора)?

В каком смысле "нестандартные"? В смысле нестандартного анализа? Нет, в этом смысле они стандартные.

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

Если так, то понятие "счётности" множества в таких моделях, очевидно, тоже нестандартно...

Счётность она и есть счётность, хот и зависит от модели.

[epros]

Someone в сообщении #554821 писал(а):

Я и начал: "Выберем какую-нибудь нумерацию каждого множества..." - и на этой фразе заткнулся.

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

-- Пн апр 02, 2012 17:08:44 --

Someone в сообщении #554821 писал(а):

Счётность она и есть счётность, хот и зависит от модели.

Этого я тоже не очень понимаю. Я так полагаю, что если объекты пронумерованы нестандартными натуральными числами, то множество этих объектов можно считать "счётным" в каком угодно, но только не в стандартном смысле.

[Sender]

Someone в сообщении #554821 писал(а):

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

Но ведь при использовании диагональной процедуры нумерации мы и будем на каждом шаге иметь дело с конечным семейством множеств.

[Someone]

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

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

Извините, но есть стандартная терминология, давайте её и придерживаться. Вы здесь сами себя этой своей терминологией и запутали.

Если говорят, что задана последовательность элементов множества $M$, то это означает, что задано некоторое отображение $f\colon\mathbb N\to M$. Когда говорят, что эта последовательность есть нумерация элементов $M$, имеют в виду, что $f$ взаимно однозначно отображает $\mathbb N$ на $M$.

Если говорят, что задано счётное множество $M$, то это означает, что существует хотя бы одна нумерация элементов $M$, но никакая конкретная нумерация не задана. Вам, как стороннику конструктивизма, должна быть понятна разница между этими двумя ситуациями.

Теперь, если у нас есть одно счётное множество, в классической математике мы можем сказать, что, поскольку $M$ счётно, существует нумерация его элементов $f\colon\mathbb N\to M$, и далее работать с этим $f$, никак его не конкретизируя. (В конструктивной математике мы обязаны определить это $f$ явно любым конструктивным способом.) Если у нас есть конечное семейство счётных множеств, то мы можем повторить эту фразу соответствующее число раз. Если же у нас семейство множеств бесконечное, то мы лишаемся этой возможности. Бесконечно длинные рассуждения классическая математика не признаёт и не использует.

Если Вы заглянете в книжку "Теория множеств" К.Куратовского и А.Мостовского, то обнаружите там две теоремы: "Вашу" теорему о счётности множества элементов последовательности последовательностей, которая доказывается без аксиомы выбора, и теорему о счётности объединения счётного множества счётных множеств, доказательство которой требует аксиомы выбора. Роль аксиомы выбора здесь состоит как раз в том, что она позволяет заменить бесконечную совокупность произвольных выборов одним произвольным выбором.

Sender в сообщении #554860 писал(а):

Но ведь при использовании диагональной процедуры нумерации мы и будем на каждом шаге иметь дело с конечным семейством множеств.

Ну, Вы имеете в виду стандартно используемую в математических рассуждениях неформальную "индуктивную" процедуру построения, когда на каждом шаге выбирается очередной произвольный элемент из очередного множества. Это построение в буквальном виде не формализуемо. Более того, нет никакой аксиомы, на основании которой можно было бы утверждать, что совокупность выбранных таким образом элементов будет множеством. Интуитивно я уверен, что такая аксиома была бы много сильнее аксиомы выбора. Использование аксиомы выбора позволяет преобразовать эту "индуктивную" процедуру в настоящую схему определения по индукции, доказуемую в ZF: до начала построения мы выбираем одну функцию выбора, а затем, когда нам в очередном шаге нужно "выбрать" очередной элемент, ссылаемся на эту функцию выбора. Подробности схем определений по индукции (в том числе - трансфинитной), доказуемых в ZF, можно посмотреть в упомянутой выше книге.

[epros]

Someone в сообщении #554930 писал(а):

Если говорят, что задано счётное множество $M$, то это означает, что существует хотя бы одна нумерация элементов $M$, но никакая конкретная нумерация не задана. Вам, как стороннику конструктивизма, должна быть понятна разница между этими двумя ситуациями.

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

Someone в сообщении #554930 писал(а):

Если Вы заглянете в книжку "Теория множеств" К.Куратовского и А.Мостовского, то обнаружите там две теоремы: "Вашу" теорему о счётности множества элементов последовательности последовательностей, которая доказывается без аксиомы выбора, и теорему о счётности объединения счётного множества счётных множеств, доказательство которой требует аксиомы выбора. Роль аксиомы выбора здесь состоит как раз в том, что она позволяет заменить бесконечную совокупность произвольных выборов одним произвольным выбором.

Вот видите, значит мой подход тоже имеет право на существование?

Я понимаю в чём тут роль аксиомы выбора. Но всё дело в том, что я считаю себя вправе уверенно утверждать, что множество в каком-то смысле "существует" и является "счётным" только тогда, когда у меня есть последовательность, нумерующая его элементы. А значит необходимости в выборе уже нет. Если же мне на основании каких-то абстрактных соображений заявляют: "Поверь, вот это множество является счётным, хотя мы не можем тебе пока указать конкретную процедуру его нумерации", - то я полагаю, что никакого счётного множества мне представлено не было, есть только чья-то вера в то, что множество счётно.