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

[epros]

Maslov в сообщении #558380 писал(а):

По-моему, Вы слишком вольно обращаетесь понятием "аксиома". Употребление слова "аксиома" для утверждений типа "самолеты не падают" или "Солнце вращается вокруг Земли" говорит только о степени нашей уверенности и истинности этих утверждений и к использованию этого термина при построении формальных теорий отношения не имеет.

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

Maslov в сообщении #558380 писал(а):

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

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

Maslov в сообщении #558380 писал(а):

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

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

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

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

Получаем well-defined действительное число...

Что значит "well-defined"?

Алгоритма, который бы по любому $n$ указывал, чему равен $n$-ый разряд этого числа, у Вас нет! Так в каком смысле Вы его "задали"? Явно не в конструктивном.

А диагонализировать я тоже умею, дядя Кантор научил

[epros]

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

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

Получаем well-defined действительное число...

Что значит "well-defined"?

Значит, что указанный объект существует и единственный. В смысле классической логики. Ровно в том же смысле, в котором существует функция $\Sigma(n)$.

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

Алгоритма, который бы по любому $n$ указывал, чему равен $n$-ый разряд этого числа, у Вас нет! Так в каком смысле Вы его "задали"? Явно не в конструктивном.

Конечно не в конструктивном. С точки зрения конструктивного анализа это число не определено. Так же, как не определена и функция $\Sigma(n)$. Точнее, не доказана ее всюду определенность. Если я правильно понимаю.

[Lukin]

О "Busy Beaver" на русском языке:
Задача поиска усердных бобров и ее решения
Занятой бобер

[Lukin]

Разделим Тьюринг-машины на классы по числу состояний.
Предположим, в классе Тьюринг-машин $T_n$ с некоторым конечным числом состояний $n$ (например, с учетом задачи о бобрах, $n=6$), существует Тьюринг-машина, $t_n$ моделирующая класс таких же Тьюринг-машин с $n$ состояниями, или даже машин с $n+1$ состояниями.

Замечу, что задачу останова такая машина не решает и не известно, остановится ли она.
Также замечу, что для моделирования $T_4$ на $T_3$ или $T_5$ на $T_4$ или $T_5$ на $T_5$, задача заведомо невыполнима, т.к. число состояний $T_{n+1}, n <6$ больше числа единиц, которые может выписать самый "усердный бобер" класса $T_n$, т.е. ни какая $T_n, n<6$ просто не сможет занумеровать все функции переходов $T_n$ или $T_{n+1}$.

В случае с $T_6$ мы не знаем, максимальное число единиц, которые может выписать "усердный бобер", но располагаем оценкой снизу $> 4,640 \cdot 10^{1439}$. Это, заведомо больше, числа функций переходов $T_n, n<8$, а значит, какая-то конкретная машина класса $T_6$ по крайне мере, потенциально, вполне может занумеровать все функции переходов $T_n, n<8$, после чего продолжить свою основную работу.
В более общем случае, это можно вывести из невычислимости функции "усердного бобра". Она растет быстрее любой вычислимой функции (см. ссылки), а т.к. функция числа переходов между состояниями машины Тьюринга класса $n$ вычислима, значит, существует конечное $n$ при котором число "усердного бобра" превзойдет число переходов между состояниями Тьюринг-машины класса $n$ на любую, сколь угодно большую, наперед заданную величину. Я всего лишь предположил, что $n=6$.

Если в классе машин $T_n$ существует машина обладающая свойством моделировать машины класса $T_{n+1}$, то база индукции есть.
Если из этого следует, что и в классе $T_{n+1}$ есть машина обладающая таким же свойством, то это верно для всех $T_n, n \in \mathbb{N}$.
Это доказать низя, в такое можно только верить.

Применительно к задаче "усердных бобров" это означает, что после некоторого конечного $n$ (возможно $n=6$), функция $\Sigma (n)$ не определена, т.к. не определена модель "веры".
В стандартной интерпретации я бы сказал, что она не существует, т.к. утверждение о ее существовании равносильно утверждению о существовании наибольшего натурального числа.
В нестандартной интерпретации, функция возвращает нестандартные бесконечно большие "натуральные числа", каждое из которых больше любого стандартного (алгоритм, естественно, "висит").


Внешний алфавит $\{0,1\}$, внутренний $\{0,1,2,3,4,5\}$.
Сначала выполняется алгоритм машины $t_6$, заполняющий пустую ленту строкой состояний машин класса $T_7,\{0,1,2,3,4,5,6\}$
Затем выполняется алгоритм, выписывающий на ленту строки всех неповторяющихся переходов машин класса $T_7$ из одного состояние в другое, с учетом алфавита ленты $\{(0,0) \to (0,0,N)\}, \{(0,0) \to (0,0,R)\}, …\}$
После нумерации всех переходов между состояниями начинает выполняться основной алгоритм $T_6$.
На вход машины $t_n, n>5$ подается "таблица" переходов любой машины класса $T_{n+1}$, которую нужно смоделировать и лента на которой она будет выполняться (для простоты и близости к задаче "усердных бобров" можно считать ее пустой).
Машина $t_n$ считывает начальное состояние машины $t_{n+1}$ и сверяет полученную строку со строками в таблице состояний, найдя искомую, $t_n$ считывает начальное значение на ленте и ищет в таблице переходов искомую комбинацию $\{(0,0) \to (0,0,N)\}, \{(0,0) \to (0,0,R)\}, …\}$.
Если комбинация найдена - значит нам не подсунули под видом $T_{n+1}$, какую-нибудь другую Тьюринг-машину, большего класса.
После этого $t_n$ переписывает состояние машины $t_{n+1}$, в соответствии с программой (найденной строкой перехода) и выполняет передвижение по ленте в соответствии с указанным в ней значением. Процесс повторяется.
Если строка перехода не найдена, машина $t_6$ завершает работу в состоянии "Машина не соответствует классу".

Возможность такого процесса следует из примитивности (алгоритмической разрешимости) построения таблиц состояний и переходов, сравнения строк, а главное - из предположения о бесконечности ленты, т.к. исходные строки состояний и таблицу переходов машины $t_n$ можно смещать между "тактами" моделирования, сколь угодно далеко от области действия моделируемой машины $t_{n+1}$. На любом шаге ленты будет достаточно, чтобы уместить обе области действия машин.

[LaTeXScience]

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

Не стоит абсолютизировать. Бывает, что от веры отступаются.

Вы не понимаете. В какой-то промежуток времени человек верит во что-то. Да, он может по каким-то причинам потом ``вылечиться'' и перестанет верить. И тут нет противоречия.

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

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

Это составная часть методологии науки, которая помогает бороться с лженаукой и прочим мракобесием.

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

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

Не передергивайте. Мы говорим сейчас о Вашем понимании, что такое ``создать теорию''.

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

Попробуйте теперь сказать, что мат. индукция - не предмет вашей ВЕРЫ.

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

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

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

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

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

Разумеется, мы, юзеры, можем обходиться без программеров.

Это невозможно! Если не будет программера, то не будет и библиотеки процедур у юзера, а значит, не будет создана теория.

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

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

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

[PayMay]

(Оффтоп)

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

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

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

Вы несете полную чушь. Это бред. Ужас.
Во-первых, это некорректная аналогия. Во-вторых, теоремы в математике доказываются, а не просто основываются на ``мнении'' мозга математика. В-третьих, она (процедура в мозге) не может работать правильно наверняка. В-четвертых, Вы обманываете, что не понимаете этой процедуры.
Короче, Вы придумываете все более и более нелепые оправдания своей идеи.

Ти-ши---н..а….а…
LaTeXScience скорее готов признать противоречивость своих рассуждений, чем противоречивость МАШИНЫ (Тьюринга) (чего-то непонятно, чего вычисляющего, и непонятно, останавливающегося или нет.

[epros]

LaTeXScience, Вы что-то резко утратили с адекватность. Я даже не знаю, стоит ли далее комментировать этот клубок наивных воззрений: и про «настоящих учёных», которые якобы ни во что не верят, а исключительно «истину познают», и про якобы принципиальные отличия «чистой» матлогики от того, что мы применяем в повседневной жизни…

Ладно, не буду. Лучшее давайте вернёмся к тому, с чего начали: К Вашей ВЕРЕ в то, что без матиндукции никак невозможно обойтись. Как я понял, Вы обосновываете её тем, что без матиндукции якобы невозможно «создать» ни одной теории. Я Вам отвечаю, что создать теорию - это не значит формально определить её в терминах некой мета-теории. Это значит где-то раздобыть (и выложить для всеобщего пользования) процедуры: распознавания высказываний, в частности - аксиом, а также вывода (проверки доказательств). Мета-теория здесь совершенно не нужна. Потребность в ней возникает только тогда, когда мы хотим проанализировать теорию (например, выяснить, какие вопросы в ней неразрешимы). Для выводов в рамках теории мета-теория не нужна. Хочу ещё раз подчеркнуть следующие моменты:

1) Это всё применимо к любым теориям, в том числе, к слабо формализованным, а не только к формальным математическим теориям. Т.е. в качестве языка теории может выступать естественный язык, в качестве аксиом - бездоказательно принятые субъектом утверждения и т.п.

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

3) Источник (происхождение) процедур тоже не имеет значения. Они могут быть кем-то написаны, скомпиллированы и инсталлированы, они могут самозародиться в голове субъекта или свалиться прямо с небес: Это совершенно неважно, ибо вопрос происхождения этих процедур относится к компетенции мета-теории и в рамках теории рассматриваться не может.

Ещё раз на примере ZFC: Есть понимание в мозге математика того, что является, а что не является правильным высказыванием. Именно это позволяет математику строить правильные доказательства. У кого такого понимания нет, тот и сам правильное доказательство не построит, и чужие доказательства понять не сможет. Вопрос о том, откуда это понимание взялось, выходит за рамки ZFC, т.е. является мета-теоретическим. Так вот, для того, чтобы строить доказательства в рамках ZFC, никакая «встроенная» матиндукция не нужна: достаточно вывести её в рамках ZFC. Однако если субъект не принимает аксиоматику ZFC, то и вывод соответствующий не примет.

[Someone]

PayMay в сообщении #559101 писал(а):

противоречивость МАШИНЫ (Тьюринга)

Что такое противоречивость формальной теории я знаю. А вот что такое "противоречивость машины Тьюринга"?

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

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

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

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

[LaTeXScience]

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

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

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

[epros]

Someone, поднятые Вами вопросы относятся уже не к математике, а … хм, к какой-то около-математической философии. Тем не менее, хочу Вам ответить.

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

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

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

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

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

Мне кажется, что Вы выдумываете какие-то «специфические особенности» математических понятий совершенно на пустом месте. Разумеется, физические объекты, на которые можно было бы указать пальцем и сказать: «вот это группа», существуют. Точно в таком же смысле, в котором существуют объекты, на которые можно было бы указать пальцем и сказать: «вот это яблоко». Например, цветовые заряды кварков составляют группу SU(3), и это - вполне себе физическая реальность, неплохо подтверждённая экспериментом. Кстати, яблоко - это тоже вполне абстрактное понятие, так что когда Вы что-то рассказываете о яблоках, то излагаете теоретические соображения, точно так же, как делает физик, рассуждающий о сильном взаимодействии.

В общем, попробуйте ФОРМАЛЬНО определить различия, будет любопытно послушать.

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

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

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

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

Евклидова геометрия существует сама по себе, окружающий нас мир - сам по себе.

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

-- Чт апр 12, 2012 16:25:31 --

Lukin, я не понял, что Вы хотели сказать. Но если это была попытка прояснить, в каком смысле функция $\Sigma(n)$ может оказаться не определена, то я могу высказать свою точку зрения на этот счет: Классическая логика исходит из соображения, что машина Тьюринга либо останавливается, либо нет. Если мы не можем доказать ни того, ни другого, то это считается нашей личной проблемой, от который «истинное положение вещей» не зависит. А я могу предположить, что для какого-либо $n$ (может даже уже для $n=5$) найдётся такая машина Тьюринга, что вопрос о её остановке окажется неразрешим никакими средствами, которыми располагает математика. Я склонен интерпретировать такую ситуацию как принципиальное отсутствие ответа на вопрос об остановке, а значит, как отсутствие значения функции $\Sigma(n)$ для соответствующего аргумента.

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

[Lukin]

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

Lukin, я не понял, что Вы хотели сказать. Но если это была попытка прояснить, в каком смысле функция $\Sigma(n)$ может оказаться не определена, то я могу высказать свою точку зрения на этот счет: Классическая логика исходит из соображения, что машина Тьюринга либо останавливается, либо нет. Если мы не можем доказать ни того, ни другого, то это считается нашей личной проблемой, от который «истинное положение вещей» не зависит.

Я не думаю, что в данном случае, дело в проблеме остановки.
Из существования универсальной машины Тьюринга следует, что мы не можем сравнить разные машины с $n$ состояниями, где $n$ - минимальное число состояний необходимых для построения универсальной машины, т.к. эти машины эквивалентны.
Остается доказать, что из предположения о существования останавливающейся программы для универсальной машины Тьюринга, реализующей функцию $\Sigma(n)$ следует противоречие. Предположим, что существует программа для универсальной Тьюринг-машины, выписывающая наибольшее количество единиц $\x=\Sigma(n)$ на пустую ленту и останавливающаяся. Добавим к программе строку $x=x+1$ перед выполнение команды остановки. Получили противоречие. Следовательно, такой программы не существует.

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

А я могу предложить, что для какого-либо $n$ (может даже уже для $n=5$) найдётся такая машина Тьюринга, что вопрос о её остановке окажется неразрешим никакими средствами, которыми располагает математика.

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

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

Я склонен интерпретировать такую ситуацию как принципиальное отсутствие ответа на вопрос об остановке, а значит, как отсутствие значения функции $\Sigma(n)$ для соответствующего аргумента.
Вообще-то у этой интерпретации есть тонкое место. Но я не скажу, пусть лучшее кто-нибудь сначала догадается.

Функция - это двухместное отношение с ограничением $\forall a ((a,b) \in f, (a,c) \in f)) \rightarrow b=c$. Если одного из значений нет - нет и функции, если $b \neq c$, то функции тоже нет.

[Someone]

(Оффтоп)

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

Someone

Ну, хочется Вам фигнёй страдать - дело Ваше, мешать не буду.

[LaTeXScience]

Вот что писал Пуанкаре в ``Математика и логика'' по сабжу.

... ``принцип математической индукции'' мне казался необходимым для математики и в то же время не сводимым к логике.

Я видел в этом принципе квинтэссенцию математического рассуждения.

Математика независима от существования материальных предметов. Слово существовать в математике может иметь только один смысл, оно означает именно отсутствие противоречия.

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

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

Эта пятая аксиома (аксиоматики Пеано --примечание LaTeXScience) есть принцип полной индукции.
Г. Кутуюра рассматривает эти аксиомы, как замаскированные определения; они содержат определения посредством постулатов нуля, ``последующего'' и целого числа.
Но, как мы уже знаем, определение посредством постулатов может быть принято лишь, если есть возможность установить, что оно не заключает противоречия.
Таков ли именно настоящий случай? Вовсе нет. Доказательство здесь не может быть дано на примере. Нельзя выбрать часть целых чисел, например, первые три, и доказать, что они удовлетворяют определению.
Если я возьму ряд 0, 1, 2, то я ясно вижу, что он удовлетворяете аксиомам 1, 2, 4 и 5; но для того, чтобы он удовлетворял аксиоме 3-й, необходимо, чтобы и 3 было целым числом и, следовательно, чтобы ряд 0, 1, 2, 3 удовлетворял нашим аксиомам; мы можем убедиться, что он удовлетворяет аксиомам 1, 2, 4, 5, но аксиома 3-я требует кроме того, чтобы 4 было целым числом и чтобы ряд 0, 1, 2, 3, 4 удовлетворял нашим аксиомам, и т.д.
Невозможно, значит, доказать эти аксиомы для нескольких целых чисел, не доказывая их для всех чисел; приходится поэтому отказаться от доказательства на примере.
Следует в таком случае взять все следствия из наших аксиом и посмотреть, не содержат ли они противоречия. Если бы этих следствий было конечное число, то это было бы легко; но их бесконечное множество, это -- вся математика, или, по меньшей мере, вся арифметика.
Как же поступить в таком случае? Может быть, строго говоря, возможно было бы найти некоторый способ доказать, что какое-нибудь новое рассуждение не сможет внести противоречия, если только предположить, что в ряду предыдущих рассуждений мы не встретили до сих пор никакого противоречия.
Если бы это было так, то мы были бы уверены, что нам нечего бояться натолкнуться когда-либо на противоречие.
Но это значило бы пользоваться полной индукцией, и, следовательно, дело шло бы о том, чтобы оправдать принцип полной индукции.

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

[epros]

Lukin в сообщении #559428 писал(а):

Я не думаю, что в данном случае, дело в проблеме остановки.

Именно в ней, поскольку функция $\Sigma(n)$ определена так, что для нахождения её значения нужно проверить все соответствующие машины Тьюринга на остановку.

Lukin в сообщении #559428 писал(а):

Из существования универсальной машины Тьюринга следует...

Универсальная машина тут ни при чём. Функция $\Sigma(n)$ определена не через универсальную машину, а через машины с изначально пустой лентой.

Lukin в сообщении #559428 писал(а):

Остается доказать, что из предположения о существования останавливающейся программы для универсальной машины Тьюринга, реализующей функцию $\Sigma(n)$ следует противоречие.

Так, вроде, Гёдель давно доказал.

Lukin в сообщении #559428 писал(а):

Достаточно найти при каком минимальном $n$ Тьюринг-машина может быть универсальной.

Так вроде при $n =5$?

Lukin в сообщении #559428 писал(а):

Если одного из значений нет - нет и функции

Очевидно. И что из этого следует?

-- Пт апр 13, 2012 10:03:24 --

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