Рассуждая о полноте кодатипа в Изабель /HOL

Question

Я хотел бы записать некоторые определения (и доказать несколько лемм!) О путях в графе. Допустим, что граф задан неявно отношением типа 'a => 'a => bool, Чтобы говорить о возможном бесконечном пути в графе, я подумал, что разумно было бы использовать ленивый список типа кодирования, такой как 'a llist как указано в "Определение (Co) типов данных и примитивно (Co) рекурсивных функций в Изабель / HOL" (datatypes.pdf в распределении Изабель).

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

Если бы я использовал 'a list как тип для представления путей, это было бы легко: я бы просто определил предикат, используя primrec, Тем не менее, коиндуктивные определения, которые я могу найти, все, кажется, генерируют или потребляют данные по одному элементу за раз, вместо того, чтобы быть в состоянии утверждать обо всем этом. Очевидно, я понимаю, что полученный предикат не будет вычислимым (потому что он делает утверждение о бесконечных потоках), поэтому он может где-то иметь \ forall, но это хорошо - я хочу использовать его для разработки теории, не генерирует код.

Как я могу определить такой предикат? (И как я могу доказать очевидные связанные леммы введения и исключения, которые делают его полезным?)

Спасибо!

Answer 1

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

type_synonym 'a graph = "'a ⇒ 'a ⇒ bool"

codatatype 'a llist = LNil | LCons 'a "'a llist"

coinductive is_path :: "'a graph ⇒ 'a llist ⇒ bool" for g :: "'a graph" where
  is_path_LNil:
    "is_path g LNil"
| is_path_singleton:
    "is_path g (LCons x LNil)"
| is_path_LCons:
    "g x y ⟹ is_path g (LCons y path) ⟹ is_path g (LCons x (LCons y path))"

Это дает вам правила введения is_path.intros и правило исключения is_path.cases,

Когда вы хотите показать, что индуктивный предикат верен, вы просто используете его правила введения; когда вы хотите показать, что индуктивный предикат подразумевает что-то еще, вы используете индукцию с ее правилом индукции.

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