Математическая индукция

[epros]

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

Предикате от множества.

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

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

Мы доказываем утверждение о множествах конечных мощностей

Это условие без логики второго порядка точно нельзя сформулировать.

Может всё же попробовать переформулировать доказываемое утверждение в логике первого порядка (даже если смысл слегка изменится)?

Вообще, индукция второго порядка - это очень спорная вещь.

[arseniiv]

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

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

Да обычная логика, ведь никто не говорит, что тут речь об индукции—схеме аксиом или аксиоме. Она каким-то образом дана, не важно откуда. Может, мы в ZFC и её доказали за нас, но не сказали как, чтобы не отвлекать.

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

Может всё же попробовать переформулировать доказываемое утверждение в логике первого порядка (даже если смысл слегка изменится)?

Можно, но фокус-то не на этом, а на ошибке более простого вида, видимой без переформулировки. А сидя в арифметике первого порядка мы застрянем выражая «число $m$ является $n$-кой натуральных чисел и все элементы этой $n$-ки равны $a$».

[TOTAL]

Neopoznanno в сообщении #1459515 писал(а):

Вы утверждаете, что ошибка в том, что нет лошадей с номерами от 2 до $n - 1$, а здесь не работает такая логика:
В случае $n = 2$ множество этих лошадей пусто, а про пустое множество можно сказать всё что угодно, в том числе и что это множество лошадей одной масти?

Ошибка в том, что отсутствует предмет которому равна первая и вторая лошадь.
Если рост Пети равен длине швабры и рост Васи равен длине той же швабры, то рост у Пети и Васи одинаковый. А если швабры нет, то надо думать.

[Mihr]

Neopoznanno в сообщении #1459515 писал(а):

про пустое множество можно сказать всё что угодно

Именно так. И в этом, видимо, корень Вашей ошибки.
Может быть, Вам поможет такое рассуждение. Давайте рассмотрим два высказывания:
1. Если бы Бармаглот существовал, то он был бы красного цвета.
2. Если бы Бармаглот существовал, то он был бы синего цвета.
Предположим, нам откуда-то известно, что оба высказывания 1 и 2 истинны. Какой мы сделаем вывод?
Я предлагаю такой: Бармаглота не существует.
Можно, конечно, предложить и второй (альтернативный) вывод: "красный" = "синий". Но первый вариант как-то убедительнее, Вы согласны?

[mihaild]

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

Это условие без логики второго порядка точно нельзя сформулировать

Можно, в ZF. Точное утверждение такое: если $f$ - функция на натуральных числах, то $\forall x, y \in \mathbb N: f(x) = f(y)$. И принцип индукции в ZF есть, для натуральных чисел он выглядит примерно так: $((0 \in X) \wedge (\forall x: x \in X \rightarrow x + 1 \in X)) \rightarrow \mathbb N \subseteq X$.

[epros]

mihaild в сообщении #1459609 писал(а):

Можно, в ZF. Точное утверждение такое: если $f$ - функция на натуральных числах, то $\forall x, y \in \mathbb N: f(x) = f(y)$. И принцип индукции в ZF есть, для натуральных чисел он выглядит примерно так: $((0 \in X) \wedge (\forall x: x \in X \rightarrow x + 1 \in X)) \rightarrow \mathbb N \subseteq X$.

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

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

Можно, но фокус-то не на этом, а на ошибке более простого вида, видимой без переформулировки.

Лично я не могу увидеть ошибку, пока не увижу формулировку. А формулировку, которую я увидел на словах, формализовать в логике первого порядка невозможно (как и известное утверждение Гича-Каплана: "Некоторые критики восхищаются только друг другом").

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

Если бы формулировка была первого порядка, например: "Для любой пары лошадей истинно бинарное отношение Одинаковой масти", - то я бы сразу спросил, как Вы собираетесь доказывать ЭТО по индукции?

[iifat]

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

Если бы формулировка была первого порядка, например: "Для любой пары лошадей истинно бинарное отношение Одинаковой масти", - то я бы сразу спросил, как Вы собираетесь доказывать ЭТО по индукции?

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

[epros]

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

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

Хотелось бы увидеть конкретно. Там под квантором всеобщности ДВЕ переменных. По какой из них будем осуществлять индукцию? Или по обеим по очереди?

[mihaild]

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

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

Внешнюю - нельзя, внутреннюю - можно (равномощность какому-то элементу $\mathbb N$).

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

Если бы формулировка была первого порядка

Например так: для любого конечного пронумерованного набора лошадей все эти лошади имеют один цвет. Индукция по размеру набора.

[arseniiv]

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

Если бы формулировка была первого порядка, например: "Для любой пары лошадей истинно бинарное отношение Одинаковой масти", - то я бы сразу спросил, как Вы собираетесь доказывать ЭТО по индукции?

Так я выше привёл эскиз:

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

А сидя в арифметике первого порядка мы застрянем выражая «число $m$ является $n$-кой натуральных чисел и все элементы этой $n$-ки равны $a$».

Если обозначить этот предикат как $S(n, m, a)$, а предикат «число $m$ является $n$-кой натуральных чисел» как $T(n, m)$, то доказывается утверждение $\forall n.\, \forall m.\, T(n, m)\to\exists a.\, S(n, m, a)$, и индукцией по $n$.

Да, там везде вместо «является» надо читать «кодирует», конечно.

[iifat]

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

Хотелось бы увидеть конкретно

Это такая форма издевательства — просьба привести конкретное доказательство неверной теоремы?

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

Там под квантором всеобщности ДВЕ переменных. По какой из них будем осуществлять индукцию?

По третьей. $\forall C\forall A,B<C f(A,B)$

[arseniiv]

(Оффтоп)

Кстати благодаря этой теме я обнаружил одну приятненькую кодировку кортежей (не через канторовы пары) вот такую: определим сначала $\mathrm{sum}(c) = \lceil\log_2(c + 1)\rceil$ — прекрасно должно быть выразимо в PA, как и всё следующее; эта функция даёт сумму чисел кортежа с кодом $c$. Собственно конструкция и деструкция: $\mathrm{nil} = 0$, $\mathrm{cons}(n, c) = 2^{n + \mathrm{sum}(c) - 1} + c$, $\mathrm{car}(c) = \mathrm{sum}(c)$, $\mathrm{cdr}(c) = c - 2^{\mathrm{sum}(n) - 1}$. В такие кортежи предполагается засовывать только положительные целые, но их всегда можно сдвинуть на единицу перед cons и после car, который прям в таком виде даже обрабатывает некорректный случай: $\mathrm{car}(\mathrm{nil}) = 0$, что не совпадает со значениями при нормальном использовании; а вот cdr в такой простой формулировке всё же оказывается некорректно определённым, ну это ладно.

Кодирование хорошо тем, что выдаёт кортежи во вменяемом порядке (отсюда я и плясал изначально):

$$();\; (1);\; (2), (1,1);\; (3), (2,1), (1,2), (1,1,1);\; (4), (3,1), (2,2), (2,1,1), (1,3), \ldots$$

и на самом деле довольно тривиальное: кортежу $(a_1 + 1,\ldots,a_n + 1)$ соответствует число с двоичной записью $1\,0^{(a_1)}\,1\,0^{(a_2)}\cdots1\,0^{(a_n)}$.

[epros]

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

Это такая форма издевательства — просьба привести конкретное доказательство неверной теоремы?

Почему издевательство? Вот Вы же привели вполне осмысленную формулировку:

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

По третьей. $\forall C\forall A,B<C f(A,B)$

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

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

[Утундрий]

Mihr в сообщении #1459596 писал(а):

1. Если бы Бармаглот существовал, то он был бы красного цвета.
2. Если бы Бармаглот существовал, то он был бы синего цвета.
Предположим, нам откуда-то известно, что оба высказывания 1 и 2 истинны. Какой мы сделаем вывод?

Когда мы думаем о Бармаглоте как о синем, он - синий. Когда думаем как о красном, он - красный. А когда мы спрашиваем, какого цвета Бармаглот, он предстаёт перед нами в состоянии чистого таинства...

А ещё я бы постарался выяснить, откуда такие сведения об истинности обоих высказываний. Не проделки ли это Бармаглота?

[Mihr]

(Утундрий)

Утундрий в сообщении #1459870 писал(а):

Когда мы думаем о Бармаглоте как о синем, он - синий. Когда думаем как о красном, он - красный.

А когда мы о нём вообще не думаем, он делается прозрачнее вакуума...

Утундрий в сообщении #1459870 писал(а):

Не проделки ли это Бармаглота?

Буджум мамой поклялся, что нет.