Что такое коиндукция?

Я слышал о (структурной) индукции. Это позволяет вам строить конечные структуры из более мелких и дает вам доказательные принципы для рассуждений о таких структурах. Идея достаточно ясна.

Но как насчет коиндукции? Как это работает? Как можно сказать что-либо убедительное о бесконечной структуре?

Есть (по крайней мере) два угла для рассмотрения, а именно, коиндукция как способ определения вещей и как метод доказательства.

Что касается коиндукции как метода доказательства, какова связь между коиндукцией и бисимуляцией?

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

• языки (наборы строк в некотором алфавите, которые могут быть конечными);
• древовидные языки (наборы деревьев над алфавитом);
• следы выполнения недетерминированной системы;
• действительные числа;
• наборы целых чисел;
• наборы функций от целых до целых чисел; ...

Коиндуктивность как самая большая точка фиксации

Там, где индуктивные определения строят структуру из элементарных строительных блоков, коиндуктивные определения формируют структуры из того, как их можно деконструировать. Например, тип списков, элементы которых находятся в наборе A, определяется в Coq следующим образом:

Inductive list (A:Set) : Set :=
  | nil : list A
  | cons : A -> list A -> list A.

Неформально listтипа является самым маленьким типом , который содержит все значения , построенные из nilи consконструкторов, с аксиомой , что . И наоборот, мы можем определить самый большой тип, который содержит все значения, построенные из этих конструкторов, сохраняя аксиому дискриминации:$\forall x \, y, \: \mathtt{nil} \ne \mathtt{cons} \: x \: y$

CoInductive colist (A:Set) : Set :=
  | conil : colist A
  | cocons : A -> colist A -> colist A.

listизоморфна подмножеству colist. Кроме того, colistсодержит бесконечные списки: списки с coconsпо cocons.

CoFixpoint flipflop : colist ℕ := cocons 1 (cocons 2 flipflop).
CoFixpoint from (n:ℕ) : colist ℕ := cocons n (from (1 + n)).

flipflopявляется бесконечным (циклический список) ; это бесконечный список натуральных чисел 0 : : 1 : : 2 : : ... .$1::2::1::2::\ldots$from 0$0::1::2::\ldots$

Рекурсивное определение правильно сформировано, если результат построен из меньших блоков: рекурсивные вызовы должны работать на меньших входах. Определение Corecursive будет правильно сформировано, если в результате будут построены более крупные объекты. Индукция смотрит на конструкторов, коиндукция смотрит на деструкторов. Обратите внимание, что дуальность не только меняется с меньшего размера на больший, но и вводится в выходные данные. Например, причина, по которой вышеприведенные определения flipflopи fromопределения являются правильными, заключается в том, что вызов corecursive защищен вызовом coconsконструктора в обоих случаях.

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

CoInductive Infinite A : colist A -> Prop :=
  | Inf : forall x l, Infinite l -> Infinite (cocons x l).

Чтобы доказать, что колисты формы from nбесконечны, мы можем рассуждать путем коиндукции. from nравно cocons n (from (1 + n)). Это показывает, что from nбольше, чем from (1 + n), что является бесконечным по гипотезе коиндукции, следовательно from n, бесконечно.

Схожесть, коиндуктивное свойство

Коиндукция как метод доказательства также применима к конечным объектам. Интуитивно говоря, индуктивные доказательства об объекте основаны на том, как объект построен. Коиндуктивные доказательства основаны на том, как объект может быть разложен.

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

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

$\mathscr{A}$$\mathscr{B}$$S$$L$$\rightarrow$$R \subseteq S \times S$

$$\forall (p,q)\in R, %\forall p'\in S, \forall\alpha\in L, \text{ if } p \stackrel\alpha\rightarrow p' \text{ then } \exists q', \; q \stackrel\alpha\rightarrow q' \text{ and } (p',q')\in R$$

$\mathscr{A}$$\mathscr{B}$$\mathscr{B}$$\mathscr{A}$$R$

$R_1$$R_2$$R_1 \cup R_2$

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

Рекомендации

• Coq и исчисление индуктивных конструкций

  • Ив Берто и Пьер Кастеран. Интерактивное доказательство теорем и разработка программы - Coq'Art: исчисление индуктивных конструкций . Springer, 2004. Ch. 13. [ сайт ] [ амазонка ]
  • Эдуардо Хименес. Применение коиндуктивных типов в coq: проверка протокола чередования битов . В Семинаре по типам доказательств и программ , номер 1158 в Конспектах лекций в области компьютерных наук , стр. 135–152. Springer-Verlag, 1995. [ Google Книги ]
  • Эдуардо Хименес и Пьер Кастеран. Учебник по [Ко] Индуктивные типы в Coq. 2007. [ PDF ]

• Помеченные переходные системы и бисимуляции

  • Робин Милнер. Связь и параллелизм . Прентис Холл, 1989.
  • Давиде Сангиорги. О происхождении бисимуляции и коиндукции . Транзакции ACM по языкам и системам программирования (TOPLAS), том 31, выпуск 4, май 2009 г. [ PDF ] [ ACM ] Связанные слайды курса: [ PDF ] [ CiteSeer ]

  • Давиде Сангиорги. Пи-исчисление: теория мобильных процессов . Издательство Кембриджского университета, 2003. [ Амазонка ]

    • Дополнительные ссылки, предложенные Антоном Труновым

  • Глава в Заверенной программировании с зависимыми типами А. Chlipala

  • Д. Сангиорги. «Введение в бисимуляцию и коиндукцию». 2011. [ PDF ]
  • Д. Сангиорги и Дж. Руттен. Продвинутые темы в бисимуляции и коиндукции . Издательство Кембриджского университета, 2012. [ CUP ]

Рассмотрим следующее индуктивное определение:

$\qquad \displaystyle \begin{align*} &\phantom{\Rightarrow} \quad \varepsilon \in \mathcal{T} \\ w \in \mathcal{T} \quad &\Rightarrow \quad aw \in \mathcal{T}\\ aw \in \mathcal{T} \quad &\Rightarrow \quad baw \in \mathcal{T} \end{align*}$

$\mathcal{T}$$b$

$\qquad \displaystyle \mathcal{T} =\{\varepsilon, a, aa, ba, aaa, aba, \dots\} = \mathcal{L}\left((ba\mid a)^*\right) \subseteq \Sigma^*.$

$\mathcal{T}$$\mathcal{T}=\{a,b\}^*$

$f : 2^{\Sigma^\infty} \to 2^{\Sigma^\infty}$

$\qquad f(T) = T \cup \{\varepsilon\} \cup \{aw \mid w\in T\} \cup \{baw \mid aw \in T\}$

$\mathcal{T}$$f$$f$$\left(2^{\Sigma^\infty},\subseteq\right)$$\{\varepsilon\}$$\mathcal{T}$

$w$$aw$$aw$$w$$\mathcal{T}'$$\mathcal{T}'$$\Sigma^\infty$$bb$$\mathcal{T}'=\mathcal{L}\left((ba\mid a)^\omega\right)$

$f$$\mathcal{T}'$$\mathcal{T}'$$\{\varepsilon\}$$\Sigma^\infty$

---

Обозначения:

• $\Sigma^\infty = \Sigma^* \cup \Sigma^\omega$
• $\Sigma^\omega$$\Sigma$

---

$w \in \mathcal{T} \Rightarrow aw \notin \mathcal{T}$
$\{\varepsilon\}$