Принцип математической индукции

[nide9]

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

Цитата:

Пусть $P(x,y_1, … ,y_k)$ - какое-нибудь отношение на множестве неотрицательных целых чисел. В частности, $P$ может содержать только одну переменную $x$, то есть быть свойством. Если $P(0,y_1, … ,y_k)$ выполнено и для любого $n$ из $P(n,y_1, … ,y_k)$ следует $P(n+1,y_1, … ,y_k)$, то $P(x,y_1, … ,y_k)$ для всех целых неотрицательных $x$.

Если $y_1, … , y_k$ - переменные, то $P(0,y_1, … ,y_k)$ может быть выполнено для одних значений $y_1, … , y_k$ и не выполнено для других. Или подразумевается, что отношение должно быть выполнено при любых игреках?
Далее:

Цитата:

Если отношение $P$ содержит переменные $y_1, … , y_k$, отличные от $x$, то говорят, что доказательство утверждения «при любом $x$ $P(x)$» ведется индукцией по $x$.

Тут, наверное, имеется ввиду «при любом $x$ $P(x,y_1, … , y_k)$», раз отношение содержит и другие переменные ?

[Connector]

nide9
Кстати, откуда эти цитаты? В какой книге содержатся такие формулировки?

[nide9]

Connector в сообщении #1411817 писал(а):

nide9
Кстати, откуда эти цитаты? В какой книге содержатся такие формулировки?

Мендельсон, Введение в математическую логику, 16 страница

[arseniiv]

nide9 в сообщении #1411814 писал(а):

Если $y_1, … , y_k$ - переменные, то $P(0,y_1, … ,y_k)$ может быть выполнено для одних значений $y_1, … , y_k$ и не выполнено для других.

Да, предполагается, что мы нашли какие-то $y_1,\ldots, y_k$, для которых $P(0, y_1,\ldots ,y_k)$ (и дальше они всегда одни и те же). Это параметры.

[nide9]

arseniiv в сообщении #1411821 писал(а):

nide9 в сообщении #1411814 писал(а):

Если $y_1, … , y_k$ - переменные, то $P(0,y_1, … ,y_k)$ может быть выполнено для одних значений $y_1, … , y_k$ и не выполнено для других.

Да, предполагается, что мы нашли какие-то $y_1,\ldots, y_k$, для которых $P(0, y_1,\ldots ,y_k)$ (и дальше они всегда одни и те же). Это параметры.

Если $y_1,\ldots ,y_k$ - параметры, то не сводится ли $P(x, y_1,\ldots ,y_k)$ к одноместному отношению? Просто во всех остальных источниках индукция определяется через свойство натуральных чисел $P(n)$, а не через отношение с несколькими аргументами, и я не вижу необходимости в этом излишестве.

[arseniiv]

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

[nide9]

arseniiv в сообщении #1411829 писал(а):

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

Большое спасибо за ответ

[george66]

Например, если мы доказываем по индукции равенство
$n+m=m+n$
то начинаем с доказательства
$n+0=0+n$
а потом из предположения
$n+m=m+n$
как-то выводим
$n+(m+1)=(m+1)+n$
Здесь индукция по $m$, но $n$ тоже нужен.

[iifat]

Таки можно конкретную цитату, чтоб не искать по всему Мендельсону?

[Dan B-Yallay]

iifat в сообщении #1411858 писал(а):

Таки можно конкретную цитату, чтоб не искать по всему Мендельсону?

nide9 в сообщении #1411818 писал(а):

Мендельсон, Введение в математическую логику, 16 страница

Вот тут есть вроде:
https://www.slideshare.net/mobile/Yuriy ... 6-58792903