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

[Ales]

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

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

[arseniiv]

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

например, только числа до 1000

Вам придётся отдельно для каждого значения второго слагаемого доказывать верность.

[g______d]

Без аксиомы индукции (или ее аналога) довольно сложно дать определение натуральных чисел. Я, правда, тоже не специалист по логике.

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

Если хочется как-то по-другому, то надо строго объяснить, что значит "запретить правило индукции".

[Xaositect]

Как вариант http://en.wikipedia.org/wiki/Robinson_arithmetic

[hurtsy]

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

Вроде бы, доступна геометрия по Евклиду.

В аксиоматике элементарной геометрии есть аксиома Архимеда, а она, имхо, "генетически" родственна МИ.

Xaositect в сообщении #529762 писал(а):

Как вариант

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

[Ales]

g______d в сообщении #529751 писал(а):

Без аксиомы индукции (или ее аналога) довольно сложно дать определение натуральных чисел.

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

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

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

Аксиома Архимеда не предусматривает вывод по индукции: для любых двух отрезков существует число такое, что первый отрезок увеличенный именно во столько раз превзойдет по длине второй. Это просто универсальное правило, вывод по индукции не применяется.

-- Вс янв 22, 2012 11:35:08 --

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

-- Вс янв 22, 2012 11:42:12 --

Первый случай доказательства по индукции в школьном курсе: сумма арифметической и геометрической прогрессии.
Вопрос: можно ли получить формулу без этого правила вывода?
А формулу для бинома?

-- Вс янв 22, 2012 11:54:36 --

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

[Kallikanzarid]

Ales
Выполнение принципа математической индукции можно доказать, опираясь на элементарные свойства натуральных чисел и множеств. Вот доказательство Ленга из его книги Undergraduate Algebra:

Теорема: Пусть $P$ - утверждение о натуральных числах, $P$ выполняется для $0$ и из истинности $P(n)$ следует истинность $P(n+1)$. Тогда $P$ истинно для любого натурального числа.

Доказательство: Пусть $S \subseteq \mathbb{N}$ - множество натуральных чисел, для которых $P$ ложно. Так как существует минимум $\min S \neq 0$ и $P(\min S)$ ложно, то $P(\min S - 1)$ также ложно, т.е. $\min S - 1 \in S$, что противоречит определению минимума.

Получается, что чтобы отказаться от математической индукции, придется отказаться от каких-то предпосылок, использованных в доказательстве, только вот от каких?

[hurtsy]

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

Аксиома Архимеда не предусматривает вывод по индукции: для любых двух отрезков существует число такое, что первый отрезок увеличенный именно во столько раз превзойдет по длине второй. Это просто универсальное правило, вывод по индукции не применяется.

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

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

Первый случай доказательства по индукции в школьном курсе: сумма арифметической и геометрической прогрессии.
Вопрос: можно ли получить формулу без этого правила вывода?

Если говорить об арифметической прогрессии, то сразу вспоминается школьник Карл Гаусс, написавший под арифметической прогрессией, начиная с конца ту же прогрессию и получил требуемую сумму, чем вызвал восторг не только у своих соучеников но и высокую оценку наставника. Разумеется в этом возрасте понятие бесконечности Гаусс не применял( благодарю ЗУ Munin за науку и терпение ).
С уважением.

[Kallikanzarid]

UPD: в доказательстве мы предполагаем, что $S \neq \varnothing$ и получаем противоречие, забыл указать предположение

[Someone]

Kallikanzarid в сообщении #529813 писал(а):

Так как существует минимум $\min S \neq 0$

Ага. Только это утверждение существенно сильнее принципа индукции в арифметике первого порядка. Что Ленг и демонстрирует в этом доказательстве.

Kallikanzarid в сообщении #529813 писал(а):

Получается, что чтобы отказаться от математической индукции, придется отказаться от каких-то предпосылок, использованных в доказательстве, только вот от каких?

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

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

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

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

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

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

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

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

Первый случай доказательства по индукции в школьном курсе: сумма арифметической и геометрической прогрессии.
Вопрос: можно ли получить формулу без этого правила вывода?

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

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

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

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

[Kallikanzarid]

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

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

И что тогда останется от натуральных чисел? :)

[Someone]

Арифметические операции.

[Ales]

Kallikanzarid в сообщении #529813 писал(а):

Получается, что чтобы отказаться от математической индукции, придется отказаться от каких-то предпосылок, использованных в доказательстве, только вот от каких?

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

[g______d]

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

[Someone]

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

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

Причём здесь конструктивная математика? В конструктивной математике аксиома индукции выполняется. Речь идёт о том, что без аксиомы индукции арифметика получается весьма убогая.