Расчет транзитивных замыканий

У меня есть следующее определение:

definition someRel :: "nat rel"
where
 "someRel = {(1, 2), (2, 3), (3, 4), (4, 5)}"

Я хочу доказать следующую лемму:

lemma "someRel^*''{1}={1, 2, 3, 4, 5}"

Я разработал следующее доказательство:

proof 
 show "someRel^*''{1} ⊆ {1, 2, 3, 4, 5}" 
 proof 
 fix x
 assume "x ∈ someRel⇧* '' {1}"
 then show "x ∈ {1, 2, 3, 4, 5}"
 using assms someRel_def by (auto elim: rtranclE)
 qed
next
 show "{1, 2, 3, 4, 5} ⊆ someRel^*''{1}" 
 proof 
 fix x
 assume "x ∈ {1::nat, 2, 3, 4, 5}"
 then show "x ∈ someRel⇧* '' {1}" 
 using assms someRel_def Image_singleton by (induction) blast+
 qed
qed

Это доказательство имеет следующие проблемы:

  • Первая часть (show "someRel^*''{1} ⊆ {1, 2, 3, 4, 5}") доказана с использованием правила rtranclE. Это не работает, если я добавлю еще одну пару в отношение someRel (скажем, пару (6, 7))
  • Доказательство второй части (show "{1, 2, 3, 4, 5} ⊆ someRel^*''{1}") не заканчивается.

Может ли кто-нибудь предложить лучшее доказательство? То, что (a) допускает большее количество пар в отношении someRel и (b), завершается.

2 ответа

Оказывается, что для вашего конкретного экземпляра (и некоторых немного больших, которые я пробовал), достаточное количество (найденное, сначала применяя auto а затем исполняемый sledgehammer по оставшимся целям, чтобы идентифицировать полезные факты, например converse_rtrancl_into_rtrancl):

by (auto simp: someRel_def converse_rtrancl_into_rtrancl elim: rtranclE)

Однако в целом может быть лучше сделать одно из следующего:

  1. устройство тактично доказывает такие цели (фактически вычисляя вовлеченное транзитивное закрытие)
  2. вычислить транзитивное замыкание внутри Isabelle/HOL (либо через simp - который может быть медленным, либо через eval - который, насколько я знаю, является своего рода оракулом).

Для последнего может оказаться интересной возможность вступления в силу переходного транзита AFP.

Обновление: я добавил пример simproc, который вычисляет изображения конечных транзитивных замыканий над конечными множествами путем оценки версии разработки AFP. Вместо того, чтобы выполнять исполняемые транзитивные замыкания, я основывался на примере на Executable Transitive Closures of Finit Relations. Ваш пример можно найти в конце теории Finite_Transitive_Closure_Simprocs (как только сайт AFP синхронизируется с основным хранилищем ртути).

Обновление: Обратите внимание, что упомянутый симпрот специально нацелен на шаблоны формы r^* '' x где множества r и x конечны в том смысле, что они заданы в конечных наборах обозначений {x1, x2,..., xN}. Таким образом, для запуска конкретной цели вам может потребоваться добавить дополнительные факты /simp rules/simprocs/..., чтобы нормализовать выражение в этой форме.

Пример: если у вас была цель

"(converse someRel)^* '' {1} = {1}"

вам придется добавить правила, которые фактически "применяют" converse операцию на данном конечном множестве. Следующее:

lemma [simp]:
 "converse (insert (x, y) A) = insert (y, x) (converse A)"
 by auto

Теперь цель может быть решена посредством

by (auto simp: someRel_def)


Добавляя к ответу Криса, вот полная версия, которая использует AFP-запись для транзитивных замыканий и которая использует code-simp вместо eval. code-simp немного медленнее, чем eval, но не полагается на оракулы.

theory Test
imports "$AFP/Transitive-Closure/Transitive_Closure_List_Impl"
begin

lemma to_memo_list: "(set xs)^* '' {a} = set (memo_list_rtrancl xs a)"
 unfolding memo_list_rtrancl Image_def by auto

definition someRel :: "nat rel"
where
 "someRel = {(1, 2), (2, 3), (3, 4), (4, 5), (5,3)}" 

definition someRel_list :: "(nat × nat)list"
where
 "someRel_list = [(1, 2), (2, 3), (3, 4), (4, 5), (5,3)]" 

lemma someRel_list: "someRel = set someRel_list" by code_simp

lemma "someRel^*''{4}={3, 4, 5}"
 unfolding someRel_list to_memo_list by code_simp

end

licensed under cc by-sa 3.0 with attribution.