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

[epros]

Ales в сообщении #529801 писал(а):

Вывод по индукции это - то же, что и рекурсия, или не так?

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

Ales в сообщении #529801 писал(а):

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

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

[LaTeXScience]

Ales в сообщении #529801 писал(а):

Да вроде бы несложно: каждое натуральное число может быть увеличено на единицу, получится тоже натуральное.

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

[epros]

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

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

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

Точно так же и с законом исключенного третьего.

[vicvolf]

Ales в сообщении #529621 писал(а):

Кажется, в древности не знали математической индукции,
и как способ доказательства она появилась, не раньше17 века.
Сейчас индукция (если утверждение верно для 1, и из его верности для N следует верность для N+1, то утверждение верно для всех натуральных чисел) рассматривается как одно из логических правил вывода (я не специалист по логике и могу напутать с терминологией).
Предположим, что мы запретим это правило и окажемся на месте древних математиков.
Что тогда мы сможем доказать и какие теории построить?
Вроде бы, доступна геометрия по Евклиду.
А что будет с арифметикой, алгеброй и анализом?

Например, можно ли достаточно строго доказать коммутативность сложения для всех чисел сразу и вообще можно ли строго рассуждать о натуральных числах, не предполагая, что они ограничены сверху (например, только числа до 1000)?

Дискуссию на эту тему можно развивать в двух направлениях:
1. Ведь в 17 веке (в этом случае время надо уточнить) математики не знали не только аксиому о математической индукции, но находились вообще на уровне знаний 17 века, т.е много чего было не открыто и не сделано. Вот тогда мы окажемся на уровне древних математиков. В этом случае надо сначала сделать срез на 17 век в развитии всех математических дисциплин, а потом уже решать, как могло дальше пойти развитие математики. Это интересно - будет некоторый исторический экскурс.
2. Считать, что все математические дисциплины находятся на современном уровне и попытаться построить их без аксиомы математической индукции. Именно без аксиомы, а не метода, о котором Вы говорите, так он доказывается, как теорема, с использованием данной аксиомы. Это уже совсем другая проблема - проблема построения теории на основании определенной аксиоматики. Вопрос в этом случае стоит следующим образом. Можно ли построить теорию по данной математической дисциплине, если исключить в ней аксиому о математической индукции?

Давайте перед продолжением дискуссии уточним, по какому пути идем, а то мы будем, как лебедь, рак и щука из басни Крылова

[LaTeXScience]

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

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

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

[epros]

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

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

А что же может помешать? Желание использовать арифметику в полном объёме? А если у меня, например, такого желания нет?

[LaTeXScience]

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

А что же может помешать?

Ну, например, без принципа математической индукции Вы не сможете доказать и пользоваться теоремой дедукции:
для любого $n$, если $C_1,\dots,C_{n-1},C_n \vdash R$, то $C_1,\dots,C_{n-1} \vdash C_n \Rightarrow R$.

[epros]

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

Ну, например, без принципа математической индукции Вы не сможете доказать и пользоваться теоремой дедукции:
для любого $n$, если $C_1,\dots,C_{n-1},C_n \vdash R$, то $C_1,\dots,C_{n-1} \vdash C_n \Rightarrow R$.

Правильно, много чего доказать не сможем. Но это не значит, что без этого в принципе нельзя обойтись.

Собственно, что нам даёт математическая индукция? Это всего лишь одна из возможных схем обобщения. Т.е. если мы можем доказать $\varphi(n)$ для любого $n$, то мы хотели бы считать, что $\forall n ~ \varphi(n)$ - истинно. Однако ни в одной теории нет и не может быть такого универсального правила обобщения: Теорема Гёделя показывает, что в языке теории всегда можно сконструировать такую формулу $\varphi(n)$, что хотя она и будет доказуемой для любого $n$, обобщающая формула $\forall n ~ \varphi(n)$ будет недоказуема. Математическая индукция является всего лишь одним из возможных частных обобщающих правил - для случаев, когда $\varphi(n)$ для произвольного $n$ доказуемо не каким угодно способом, а последовательным применением правила modus ponens для $\varphi(i) \to \varphi(i+1)$ вплоть до $i = n$.

[LaTeXScience]

epros
Допустим, что возможно полностью отказаться от принципа математической индукции в каждом своем рассуждении.

Таким образом, верно высказывание: ``можно полностью избавиться от принципа математической индукции в каждом своем $n$-ом рассуждении''. Это высказывание является предикатом от $n$. Доказать его истинность можно только принципом математической индукции. Поэтому, если Вы согласны с этим моим высказыванием, то Вам придется признать принцип математической индукции. Отсюда следует, что Вы должны быть не согласны с ним. А это будет означать, что Вы согласны с его отрицанием, которое означает, что Вы не будете полностью отказываться в своих рассуждениях от принципа математической индукции.

Эти рассуждения доказывают, что сделанное в начале мной допущение не верно. Т.е. Вы не можете полностью отказаться от принципа математической индукции в каждом своем рассуждении.

[epros]

Мне нравится Ваше рассуждение. Но вообще-то оно некорректно.

Во-первых, высказывание: "Можно полностью избавиться от принципа математической индукции в каждом своем n-ом рассуждении", - сначала необходимо выразить в языке той теории, в которой мы пытаемся его доказать или опровергнуть. А это не так очевидно, как кажется. В частности, возникает такой вопрос: Является ли это высказывание одним из тех "рассуждений" о которых оно говорит? Т.е. это высказывание о самом себе, типа: "Это высказывание ложно"?

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

$\varphi(n) \to \varphi(n+1)$.

Каким образом из верности для n-ого рассуждения следует верность для (n+1)-ого рассуждения?

[vicvolf]

Это возможно! Давайте метод математической индукции и заменим методом бесконечного спуска Ферма!

[LaTeXScience]

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

Т.е. это высказывание о самом себе, типа: "Это высказывание ложно"?

Так вот в том-то и дело. Я именно это и хотел Вам сказать, что в высказывании ``Можно полностью избавиться от принципа математической индукции в каждом своем n-ом рассуждении'' не больше смысла, чем в высказывании ``Это высказывание ложно''.

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

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

Ну а как еще, по Вашему, его можно доказать?

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

Я вообще не вижу, каким образом мы здесь можем использовать предпосылку индукции:

$\varphi(n) \to \varphi(n+1)$.

Каким образом из верности для n-ого рассуждения следует верность для (n+1)-ого рассуждения?

Какая мне разница? Ну пусть не следует. И тогда это будет означать, что высказывание $\forall n : \varphi(n)$ ложно.

[epros]

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

Так вот в том-то и дело. Я именно это и хотел Вам сказать, что в высказывании ``Можно полностью избавиться от принципа математической индукции в каждом своем n-ом рассуждении'' не больше смысла, чем в высказывании ``Это высказывание ложно''.

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

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

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

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

Ну а как еще, по Вашему, его можно доказать?

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

[LaTeXScience]

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

Я говорил, что мы можем обойтись без математической индукции в том смысле, что мы можем не захотеть рассматривать теории, в которых есть аксиома индукции, только и всего

Я с этим не спорю и не спорил. См.

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

Какие-то формальные теории может и удастся построить совсем без этого принципа

Я оспаривал с это

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

Но это не значит, что без этого в принципе нельзя обойтись.

что было косвенным ответом на мое

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

Я имел в ввиду, что от принципа математической индукции не удастся избавить в своих рассуждениях вообще

[epros]

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