Когда можно использовать гипотезу коиндукции?

Question

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

Когда дело доходит до коиндукции, я в замешательстве.

Один из ответов на другой вопрос»Что такое коиндукция?" упоминает, что существует представление о том, что коркурсивное определение должно быть правильно сформулировано.

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

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

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

Есть ли какое-нибудь простое неформальное рассуждение, объясняющее, почему совместная индукция работает для некоторых требований правильности?

Я надеюсь на объяснение, например, если это возможно: https://math.stackexchange.com/questions/432293/well-ordering-and-mathematical-induction/432302#432302.

Answer 1

Во-первых, позвольте мне вспомнить наименьшие и наибольшие неподвижные точки для $\subseteq$.Мы работаем относительно некоторого множества $U$, Вселенная.В случае (ко)индуктивных определений $U$ представляет собой совокупность всех терминов.Функция $f:2^U o2^U$ (из подмножеств $U$ к подмножествам $U$) является монотонный, если $A\subseteq B$ всегда подразумевает $f(A)\subseteq f(B)$.А фиксированная точка из $f$ это набор $А$ такой, что $f(A)=A$.

Для монотонного $f$ всегда есть наименьшая неподвижная точка $\му ф$, а именно пересечение всех $A\subseteq U$ такой, что $f(A)\subseteq A$. Наименее означает, что для произвольных неподвижных точек $Ф$ у нас всегда есть $\mu f\subseteq F$.

Для примера пусть $f_{ t nat}$ определяться $f_{ t nat}(A)=\{0\}\cup\{n+1\mid n\in A\}$.Функция $f_{ t nat}$ — это одношаговая функция замыкания в конструкторах $0$ и $+1$.Состояние $f_{ t nat}(A)\subseteq A$ Значит это $А$ закрыто под конструкторами $0$ и $+1$.Пересечение означает, что $\mu f_{ t nat}$ содержит только те элементы, которые есть в каждом множестве, закрытом относительно конструкторов.Это натуральные числа.В примере показано, как индуктивное определение натуральных чисел является наименее фиксированной точкой замыкания конструкторов натуральных чисел.Как правило, индуктивно определенные множества являются наименее фиксированными точками замыкания при использовании конструкторов.

Двойственно, для монотонного $f$ также существует наибольшая неподвижная точка $ u f$, а именно объединение всех $A\subseteq U$, такой, что $f(A)\supseteq A$. Величайший означает, что для произвольных неподвижных точек $Ф$ у нас всегда есть $ u f\supseteq F$.Для полноты двойственности заметим, что пересечение – это $\subseteq$-infimum и союз $\subseteq$-супремум и, следовательно, $\supseteq$- инфимум.Таким образом, на самом деле наибольшие неподвижные точки для $\subseteq$ это всего лишь наименьшие фиксированные точки для $\supseteq$ и наоборот.(Кроме того, заметим, что требование монотонности одинаково для $\subseteq$ что касается $\supseteq$.)

Теперь о методах доказательства.Начнем с примера индукции по натуральным числам.Чтобы показать, что некоторое свойство $П$ справедливо для всех натуральных чисел, мы покажем, что $П(0)$ и это $P(n)$ подразумевает $P(n+1)$.Viewing $П$ как подмножество $U$ (множество всех элементов, для которых выполняется это свойство), обязанность доказательства для естественной индукции состоит в том, что $П$ закрыт под $f_{ t nat}$.Корректность метода доказательства естественной индукции следует из определения наименьшей неподвижной точки:Если $f_{ t nat}(P)\subseteq P$, затем $П$ является частью пересечения, которое образует $\mu f_{ t nat}$, поэтому свойство сохраняется на протяжении всего $\mu f_{ t nat}$, то есть $\mu f_{ t nat}\subseteq P$.

Индукция — это всего лишь обобщение предыдущего пункта на произвольный монотонный случай. $f$ вместо $f_{ t nat}$.Коиндукция является двойственной индукции:Обязанность доказывания – это $f(P)\supseteq P$.Это означает, что если $П$ держится на каком-то элементе $х$, затем $х$ строится с использованием только базовых элементов, на которых $П$ тоже держит.Таким образом, вместо того, чтобы показывать, что свойство выдерживает применение конструкторов, мы должны показать, что оно выдерживает деконструкцию.Как только обязательство по доказательству выполнено, мы получаем $ u f\supseteq P$.

Что хорошего в заключении $ u f\supseteq P$?Давайте пересмотрим $П$ не как свойство, а как подмножество $U$.Заключение коиндукции устанавливает, что все элементы $П$ являются корректными членами коиндуктивно определенного множества $ u f$.Вот что происходит в примере Что такое коиндукция? показывая forall n, Infinite (from n).Здесь, $f$ является замыканием под конструкторами Infinite (не из colist!) и $П$ представляет собой набор всех термов вида from n для некоторых n.