"Индуктивное предположение" у Шенфилда

[AlexeyM]

Помогите, пожалуйста, разобраться с терминологией в книге Шенфилда "Математическая логика". Из-за непонимания его трактовки словосочетания "индуктивное предположение" никак не могу понять его доказательства

Если брать метод мат. индукции для доказательства какого-либо утверждения, то все авторы пишут, мол, индуктивное предположение - это доказываемое утверждение при $n=k$. И нужно доказать истинность утверждения при $n=k+1$. Однако ни формулировки самого утверждения, ни перехода к $k+1$ я у Шенфилда найти не могу.

Вот, например, со страницы 33:

Честно говоря, никак не могу взять в толк: где именно это "индуктивное предположение", согласно которому всё так очевидно. И почему после высказывания предположения не делается переход к третьему шагу метода мат. индукции? Запутался...

[gefest_md]

Как я понял, здесь используется стронг индакшн, т.е надо доказать формулу вида $\forall n[\forall k<nP(n)\to P(n)].$ Часть $\forall k<nP(n)$ - это индуктивное предположение. В лемме как раз $k<n.$

-- Сб авг 23, 2014 23:25:16 --

Не так. Длина $v_1\ldots v_k$ меньше длины $u_1\ldots u_n.$

[arseniiv]

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

Это ещё что, иногда вообще утверждение приводят, а следом — «легко доказывается по индукции».

[AlexeyM]

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

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

Получается, так все что угодно можно доказать: например, 2 - простое число. Пусть некое целое $k$ - тоже простое число. Следовательно, по "индуктивному предположению", все числа - простые. Может, у англичан (или это американец, не знаю) индукция какая-то иная?

[Xaositect]

Используется такая форма индукции:
1) Доказываем, что утверждение верно для указателя из 1 символа. (в обоих случаях это утверждение тривиально и про него ничего не пишется)
2) В предположении, что утверждение верно для всех указателей длины меньше $n$, доказываем, что утверждение верно для произвольного указателя длины $n$.
3) PROFIT! Получаем, что утверждение верно для любого указателя.

[AlexeyM]

Xaositect, пожалуй, вы правы, но я никак не могу восстановить полное доказательство. Например, для леммы 2 про вхождение любого символа в указатель. Мы рассматриваем указатель $u$ в виде $vv_1v_2\ldots v_k$. Если мы говорим о первом символе указателя, т.е. про символ $v$, то он действительно начинает сам указатель $u$, так как первый символ любого указателя по Шенфилду - это предикатный или функциональный символ.

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

Следовательно, теперь нам нужно на основании сделанного предположения доказать это утверждение для указателей, длина которых равна $k$. А Шенфилд просто пишет вывод безо всякого доказательства, ограничившись словом "следовательно".

Вы не могли бы подсказать книгу по мат. логике от нашего автора? :) Чтобы стиль и полнота изложения были как у Фихтенгольца в матане :)

[Xaositect]

Ну вот давайте запишем подробно.
1) Тривиально.
2) Пусть в указателях длины меньше $n$ любой символ начинает вхождение некоторого указателя.
Рассмотрим указатель $u = vv_1\dots v_k$ индекса $k$ и длины $n$. Каждый из указателей $v_1,\dots,v_k$ имееет длину меньше $n$, поэтому для них можно использовать индуктивное предположение.
Первый символ $v$ начинает вхождение самого указателя $u$ в себя - для него утверждение верно.
Если символ входит в какой-то указатель $v_i$, то он по индуктивному предположению начинает вхождение некоторого указателя в $v_i$, а значит, и в $u$ - опять же утверждение верно.

-- Вс авг 24, 2014 22:38:42 --

AlexeyM в сообщении #899455 писал(а):

Вы не могли бы подсказать книгу по мат. логике от нашего автора?

Колмогоров-Драгалин, Ершов-Палютин.

[AlexeyM]

Ок, давайте распишем подробно Попробую расписать своими словами, если будет неправильно - скажите, пожалуйста.

Мы рассматриваем указатели $u$ и проводим индукцию по длине этих указателей.

1. При $n=0$ указатель - это переменная, которая начинает вхождение указателя сама в себя. Ну, или как-то так

2. Пусть для всех указателей, длина которых меньше $n$, утверждение верно, т.е. каждое вхождение любого символа в указатель $v_i$, длина которого меньше $n$, начинает вхождение некоторого указателя в $v_i$.

3. Исходя из пункта 2 нужно доказать, что вхождение любого символа в указатель длины $n$ начнёт новый указатель. Любой указатель длины $n$ имеет вид $u=vv_1\ldots v_k$, где $v$ - предикатный или функциональный символ, а остальные $v_i$ ($i=\overline{1,k}$) - указатели. При этом длины всех$v_i$ меньше $n$. Следовательно, согласно п.2 для всех $v_i$ утверждение истинно: какой бы из $v_i$ мы не рассматривали, в каждом из них вхождение любого символа начинает новый указатель. Тогда в указателе $u=vv_1\ldots v_k$ остаётся лишь символ $v$, который начинает вхождение указателя $u$ в себя. Следовательно, утверждение доказано для всех указателей длины $n$.

Это верные рассуждения или не очень?

За рекомендованных авторов - спасибо огромное, сегодня же скачаю.

[Xaositect]

AlexeyM в сообщении #899479 писал(а):

Это верные рассуждения или не очень?

Да.

[AlexeyM]

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