Метод математической индукции.

[Sdy]

Возможно, данная тема относится более к Карантину, нежели чем к этому разделу, но всё-таки попробую изложить проблему.
(Под P.N я понимаю последовательно возникшую у меня проблему).
Я знал вот такую формулировку метода математической индукции:

(1).
Пусть имеется некоторое свойство $P(n)$, параметризуемое натуральным числом $n$. Тогда,
если
1.1.Верно P(1).
1.2.$\forall n \in \mathbb{N}$ из верности $P(n)$ следует верность $P(n+1)$.
то $P(n)$ верно для любого $n \geqslant 1$.

Вот её я знал и довольно успешно применял.
Недавно увидел такую формулировку:
(1a).
Пусть имеется некоторое утверждение $A(n)$, параметризуемое натуральным числом $n$.
Тогда, если
1a.1.Утверждение $A(1)$ верно.
1a.2.Для любого натурального числа $n$ из верности утверждения $A(n)$ следует верность утверждения $A(n+1)$.
то это утверждение верно для любого натурального числа $n \geqslant 1$.

Я задумался, а верно ли, что $(1) \sim (1a)$? И не пришел ни к какому другому выводу, кроме как что слова "свойство" и "утверждение" в этом контексте стоит считать синонимами.
P1.Это верно?
В соседней теме Someone дал мне полное определение того, что такое есть свойство, в то время как под утверждением возможно понимается нечто иное? В моей литературе, которая об этом всем говорит на наивном уровне говорилось, что утверждение - просто набор высказываний.

Далее я увидел такую формулировку метода индукции, точнее, как говорилось, метода полной индукции:
(1b).
Пусть имеется некоторое утверждение $A(n)$, параметризуемое натуральным числом $n$.
Тогда, если
1b.1.Утверждение $A(1)$ верно.
1b.2.$\forall n \in \mathbb{N}$ из верности утверждений $A(1), A(2), ..., A(k); k < n$ следует верность утверждения $A(n)$.
то это утверждение верно для любого натурального числа $n \geqslant 1$.

P.2Во первых, я не смог доказать, что $(1)$ эквивалентно $(1b)$. Я даже не смог нормально описать процедуру доказательства. Я умею доказывать равносильность двух утверждений, двух теорем. А тут имеется два метода. И что именно делать, я не понял.
Тогда я начал искать информацию по этому поводу. И нашел следующее утверждение:
(2).
Возьмём произвольное подмножество $S$ множества $\mathbb{N}$.
Если
2.1. $1 \in S$.
2.2.$\forall k$ если $k \in S \Rightarrow k+1 \in S$.
Тогда $S = \mathbb{N}$.

P.3Впал в некий ступор, в силу того что было написано что это тоже самое утверждение $1$, только "переведенное" на язык множеств. Почему они эквиваленты - не доказывалось. Но ведь это надо же доказать?

Далее было перефразированное утверждение $(1b)$.
(2b).
Возьмём произвольное подмножество $S$ множества $\mathbb{N}$.
Если
2b.1. $1 \in S$.
2b.2.$\forall k > 1 : \{n : n < k \} \subseteq S$, тогда $k \in S$.
Тогда $S = \mathbb{N}$.

И ещё одно утверждение:
(3).
Если $A \subseteq \mathbb{N} \wedge A \ne \varnothing \Rightarrow$ в $A$ есть наименьший элемент.

А вот потом уже доказывалась равносильность $(2)$, $(2b)$, $3$. Затем говорилось, что теперь то понятно, что $1$ эквивалентно 1b. Но ведь как таковая равносильность $1$ и $2$ установлена не была.
Соответственно, возникает вопрос (помимо уже озвученных). А можно ли доказать, что 1a равносильно 1b не прибегая к языку теории множеств?

В конспекте по дискретной математике (скорее даже в книге ФКН ВШЭ по этому предмету) в главе об индукции говорится, что момент обсуждения равносильности $1$ и $(1b)$ будет отложен до момента рассмотрения частично упорядоченных множеств, до которого еще пол книги, а до этого момента мы будем и так этим фактом пользоваться.
В других источниках подход в доказательстве этих равносильностей совпадает с написанным выше - из ниоткуда возьмем язык теории множеств и там уже попробуем что-то доказать.

Хотелось бы понять, с чем и в какой последовательности мне нужно разобраться, что научиться доказывать как переводы между "языками", так и сами равносильности этих утверждений? Какой литературой воспользоваться? К какой области математики это вообще относится? Не хотелось глубоко сейчас лезть в математическую логику в силу большой ограниченности во времени. Но в моей литературе об анализе это всё проходит мимо (строгое обоснование), хотя всем там спокойно пользуются. И я сколько лет спокойно пользуюсь. Грустно это, хотелось бы начать уже это понимать.

[george66]

Попробуйте почитать свеженаписанный мной ликбез по нестандартному анализу. Я там начинаю с языков и как ими пользоваться
topic136592.html
Если не понравится, читайте Верещагина и Шеня "Языки и исчисления" (самый первый раздел про сложность логических схем можно пропустить)

[epros]

Sdy в сообщении #1415345 писал(а):

Я задумался, а верно ли, что $(1) \sim (1a)$? И не пришел ни к какому другому выводу, кроме как что слова "свойство" и "утверждение" в этом контексте стоит считать синонимами.

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

[arseniiv]

Sdy
Можно попробовать доказать эквивалентность (1) и (1b) непосредственно, достаточно воспринимать их как большие импликации (ну или почти). Например для этого достаточно показать эквивалентность 1.2 и 1b.2.

Сначала мы показываем, что если есть (1), то есть и (1b), и нужно показать, что из 1b.2 следует 1.2. Это как раз просто с использованием (1) ещё раз.

Потом показываем в обратную сторону, и что из 1.2 следует 1b.2, пользуясь (1b). Честно говоря у меня до этого руки никогда как следует не доходили, но должно быть не так уж сильно сложнее.

[Someone]

Sdy в сообщении #1415345 писал(а):

В соседней теме Someone дал мне полное определение того, что такое есть свойство

Для теорий первого порядка.

Sdy в сообщении #1415345 писал(а):

слова "свойство" и "утверждение" в этом контексте стоит считать синонимами.

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

Sdy в сообщении #1415345 писал(а):

(1b).
Пусть имеется некоторое утверждение $A(n)$, параметризуемое натуральным числом $n$.
Тогда, если
1b.1.Утверждение $A(1)$ верно.
1b.2.$\forall n \in \mathbb{N}$ из верности утверждений $A(1), A(2), ..., A(k); k < n$ следует верность утверждения $A(n)$.
то это утверждение верно для любого натурального числа $n \geqslant 1$.

Как-то нехорошо сформулировано. Давайте попробуем так.

(1b).
Пусть имеется некоторое утверждение $A(n)$, параметризуемое натуральным числом $n$.
Пусть
1b.1. утверждение $A(1)$ верно
1b.2. $\forall n \in \mathbb{N}$ из верности всех утверждений $A(1), A(2),\ldots, A(n)$ следует верность утверждения $A(n+1)$.
Тогда утверждение $A(n)$ верно для любого натурального числа $n \geqslant 1$.

Sdy в сообщении #1415345 писал(а):

Во первых, я не смог доказать, что $(1)$ эквивалентно $(1b)$. Я даже не смог нормально описать процедуру доказательства. Я умею доказывать равносильность двух утверждений, двух теорем. А тут имеется два метода. И что именно делать, я не понял.

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

На самом деле надо понять, что здесь надо делать. (1) и (1b) с точки зрения метатеории — схемы аксиом, в которых $A(n)$ — произвольная формула со свободной переменной $n$. Вам просто надо показать, что если формула $\forall n A(n)$ доказуема одной схемой, то она доказуема и другой схемой (возможно, с какой-то другой формулой $B(n)$ вместо $A(n)$, и, возможно, с какими-нибудь дополнительными рассуждениями).

[beroal]

Sdy в сообщении #1415345 писал(а):

свойство $P(n)$, параметризуемое натуральным числом $n$

Какая-то неуклюжая фраза. Говорят просто «свойство натуральных чисел». А вот следующую фразу я не могу сформулировать более естественно.

Sdy в сообщении #1415345 писал(а):

утверждение $A(n)$, параметризуемое натуральным числом $n$

«Утверждение натуральных чисел» вообще не имеет смысла, «утверждение о натуральных числах» имеет другой смысл.

Sdy в сообщении #1415345 писал(а):

P.2Во первых, я не смог доказать, что $(1)$ эквивалентно $(1b)$. Я даже не смог нормально описать процедуру доказательства. Я умею доказывать равносильность двух утверждений, двух теорем. А тут имеется два метода. И что именно делать, я не понял.

Тем не менее, этот «метод» можно выразить утверждением, пусть не на языке логики первого порядка, но главное, что его можно формализовать. Я не вижу необходимости ограничивать себя на этом этапе в языках. Вы имеете право взять настолько мощный язык, чтобы утверждения и доказательства звучали просто и элегантно.

Теперь формализация. 1. $P(1)\land \forall n\in \mathbb{N}(P(n)\implies P(\operatorname{succ}(n)) \implies \forall n\in \mathbb{N}(P(n))$. Здесь $\operatorname{succ}(n)$ означает натуральное число, следующее за $n$. У вас это обозначалось, кажется, $n++$ или $n+1$. Учитывая, что дальше будет сложение, нотация $n+1$ внесёт ненужную путаницу.

Sdy в сообщении #1415345 писал(а):

(1b).
Пусть имеется некоторое утверждение $A(n)$, параметризуемое натуральным числом $n$.
Тогда, если
1b.1.Утверждение $A(1)$ верно.
1b.2.$\forall n \in \mathbb{N}$ из верности утверждений $A(1), A(2), ..., A(k); k < n$ следует верность утверждения $A(n)$.
то это утверждение верно для любого натурального числа $n \geqslant 1$.

Ёлки-палки. Такую формулировку я видел не раз, и её надо искоренять. Дело в том, что условие 1b.1 не нужно. Привожу формализацию элегантного варианта этого принципа. 1c. $\forall n\in \mathbb{N}(\forall k\in \mathbb{N}(k<n\implies P(k)) \implies P(n)) \implies \forall n\in \mathbb{N}(P(n))$.

Sdy в сообщении #1415345 писал(а):

P.3Впал в некий ступор, в силу того что было написано что это тоже самое утверждение $1$, только "переведенное" на язык множеств. Почему они эквиваленты - не доказывалось. Но ведь это надо же доказать?

Они эквивалентны, потому что из любого свойства натуральных чисел можно создать множество натуральных чисел такое, что оно содержит натуральное число тогда и только тогда, когда это число удовлетворяет этому свойству. Так сказать, свойства превращаются в множества. Это следует из аксиомы выделения (axiom schema of specification, axiom schema of separation, axiom schema of restricted comprehension) теории множеств.

Sdy в сообщении #1415345 писал(а):

А можно ли доказать, что 1a равносильно 1b не прибегая к языку теории множеств?

Да. Там нужно придумывать свойства натуральных чисел, придумывать $P$.

Доказать эквивалентность 1, 1c и 3 — хорошее упражнение для логического мышления, не требующее знания теории множеств. Очень советую, расширяет сознание.

[arseniiv]

beroal в сообщении #1415499 писал(а):

Дело в том, что условие 1b.1 не нужно.

Ой, как я проглядел, присоединяюсь.

beroal в сообщении #1415499 писал(а):

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

Но первопорядковая схема аксиом индукции будет слабее, чем «множественная» аксиома, если не ограничиться только подмножествами, выразимыми формулами арифметики первого порядка.

[beroal]

beroal в сообщении #1415499 писал(а):

Доказать эквивалентность 1, 1c и 3 — хорошее упражнение для логического мышления, не требующее знания теории множеств.

Здесь я поспешил. Поскольку в 3 говорится о подмножестве $\mathbb{N}$, в доказательстве всё-таки придётся использовать теорию множеств. Но там просто надо превращать множество в свойство и наоборот, ничего сложного. Сложность в другом.

Превратить множество в свойство можно следующим образом. Пусть $S$ — множество натуральных чисел. Зададим свойство натуральных чисел $P$ следующим образом: $P(n)$ тогда и только тогда, когда $n\in S$.

[Sdy]

george66, спасибо за ответ.

george66 в сообщении #1415351 писал(а):

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

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

george66 в сообщении #1415351 писал(а):

Верещагина и Шеня "Языки и исчисления"

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

epros, спасибо за ответ.
То есть всё-таки "утверждение" - понятие более общее, и стоит руководствоваться именно доказательством с такой формулировкой.

-- 23.09.2019, 04:44 --

Someone, спасибо за ответ.

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

Да. Но только для теорий первого порядка.

Понял.

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

На самом деле надо понять, что здесь надо делать. (1) и (1b) с точки зрения метатеории — схемы аксиом, в которых $A(n)$ — произвольная формула со свободной переменной $n$. Вам просто надо показать, что если формула $\forall n A(n)$ доказуема одной схемой, то она доказуема и другой схемой (возможно, с какой-то другой формулой $B(n)$ вместо $A(n)$, и, возможно, с какими-нибудь дополнительными рассуждениями).

Над этим пока думаю, так пока нет возможности засесть за этим с листом и бумагой.
beroal, спасибо за ответ.

beroal в сообщении #1415499 писал(а):

Теперь формализация.

Да, это понимаю.

beroal в сообщении #1415499 писал(а):

Дело в том, что условие 1b.1 не нужно

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

beroal в сообщении #1415499 писал(а):

axiom schema of specification, axiom schema of separation, axiom schema of restricted comprehension

А вот это нужно разобрать.

beroal в сообщении #1415514 писал(а):

Поскольку в 3 говорится о подмножестве $\mathbb{N}$, в доказательстве всё-таки придётся использовать теорию множеств. Но там просто надо превращать множество в свойство и наоборот, ничего сложного.

Как и это.


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

[epros]

Sdy в сообщении #1416791 писал(а):

То есть всё-таки "утверждение" - понятие более общее, и стоит руководствоваться именно доказательством с такой формулировкой.

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