Theory Partial_Order_Reduction.Basic_Extensions
section ‹Basics›
theory Basic_Extensions
imports "HOL-Library.Infinite_Set"
begin
subsection ‹Types›
type_synonym 'a step = "'a ⇒ 'a"
subsection ‹Rules›
declare less_imp_le[dest, simp]
declare le_funI[intro]
declare le_funE[elim]
declare le_funD[dest]
lemma IdI'[intro]:
assumes "x = y"
shows "(x, y) ∈ Id"
using assms by auto
lemma (in order) order_le_cases:
assumes "x ≤ y"
obtains (eq) "x = y" | (lt) "x < y"
using assms le_less by auto
lemma (in linorder) linorder_cases':
obtains (le) "x ≤ y" | (gt) "x > y"
by force
lemma monoI_comp[intro]:
assumes "mono f" "mono g"
shows "mono (f ∘ g)"
using assms by (intro monoI, auto dest: monoD)
lemma strict_monoI_comp[intro]:
assumes "strict_mono f" "strict_mono g"
shows "strict_mono (f ∘ g)"
using assms by (intro strict_monoI, auto dest: strict_monoD)
lemma eq_le_absorb[simp]:
fixes x y :: "'a :: order"
shows "x = y ∧ x ≤ y ⟷ x = y" "x ≤ y ∧ x = y ⟷ x = y"
by auto
lemma INFM_Suc[simp]: "(∃⇩∞ i. P (Suc i)) ⟷ (∃⇩∞ i. P i)"
unfolding INFM_nat using Suc_lessE less_Suc_eq by metis
lemma INFM_plus[simp]: "(∃⇩∞ i. P (i + n :: nat)) ⟷ (∃⇩∞ i. P i)"
proof (induct n)
case 0
show ?case by simp
next
case (Suc n)
have "(∃⇩∞ i. P (i + Suc n)) ⟷ (∃⇩∞ i. P (Suc i + n))" by simp
also have "… ⟷ (∃⇩∞ i. P (i + n))" using INFM_Suc by this
also have "… ⟷ (∃⇩∞ i. P i)" using Suc by this
finally show ?case by this
qed
lemma INFM_minus[simp]: "(∃⇩∞ i. P (i - n :: nat)) ⟷ (∃⇩∞ i. P i)"
proof (induct n)
case 0
show ?case by simp
next
case (Suc n)
have "(∃⇩∞ i. P (i - Suc n)) ⟷ (∃⇩∞ i. P (Suc i - Suc n))" using INFM_Suc by meson
also have "… ⟷ (∃⇩∞ i. P (i - n))" by simp
also have "… ⟷ (∃⇩∞ i. P i)" using Suc by this
finally show ?case by this
qed
subsection ‹Constants›
definition const :: "'a ⇒ 'b ⇒ 'a"
where "const x ≡ λ _. x"
definition const2 :: "'a ⇒ 'b ⇒ 'c ⇒ 'a"
where "const2 x ≡ λ _ _. x"
definition const3 :: "'a ⇒ 'b ⇒ 'c ⇒ 'd ⇒ 'a"
where "const3 x ≡ λ _ _ _. x"
definition const4 :: "'a ⇒ 'b ⇒ 'c ⇒ 'd ⇒ 'e ⇒ 'a"
where "const4 x ≡ λ _ _ _ _. x"
definition const5 :: "'a ⇒ 'b ⇒ 'c ⇒ 'd ⇒ 'e ⇒ 'f ⇒ 'a"
where "const5 x ≡ λ _ _ _ _ _. x"
lemma const_apply[simp]: "const x y = x" unfolding const_def by rule
lemma const2_apply[simp]: "const2 x y z = x" unfolding const2_def by rule
lemma const3_apply[simp]: "const3 x y z u = x" unfolding const3_def by rule
lemma const4_apply[simp]: "const4 x y z u v = x" unfolding const4_def by rule
lemma const5_apply[simp]: "const5 x y z u v w = x" unfolding const5_def by rule
definition zip_fun :: "('a ⇒ 'b) ⇒ ('a ⇒ 'c) ⇒ 'a ⇒ 'b × 'c" (infixr "∥" 51)
where "f ∥ g ≡ λ x. (f x, g x)"
lemma zip_fun_simps[simp]:
"(f ∥ g) x = (f x, g x)"
"fst ∘ (f ∥ g) = f"
"snd ∘ (f ∥ g) = g"
"fst ∘ h ∥ snd ∘ h = h"
"fst ` range (f ∥ g) = range f"
"snd ` range (f ∥ g) = range g"
unfolding zip_fun_def by force+
lemma zip_fun_eq[dest]:
assumes "f ∥ g = h ∥ i"
shows "f = h" "g = i"
using assms unfolding zip_fun_def by (auto dest: fun_cong)
lemma zip_fun_range_subset[intro, simp]: "range (f ∥ g) ⊆ range f × range g"
unfolding zip_fun_def by blast
lemma zip_fun_range_finite[elim]:
assumes "finite (range (f ∥ g))"
obtains "finite (range f)" "finite (range g)"
proof
show "finite (range f)" using finite_imageI [OF assms(1), of fst]
by (simp add: image_image)
show "finite (range g)" using finite_imageI [OF assms(1), of snd]
by (simp add: image_image)
qed
lemma zip_fun_split:
obtains f g
where "h = f ∥ g"
proof
show "h = fst ∘ h ∥ snd ∘ h" by simp
qed
abbreviation "None_None ≡ (None, None)"
abbreviation "None_Some ≡ λ (y). (None, Some y)"
abbreviation "Some_None ≡ λ (x). (Some x, None)"
abbreviation "Some_Some ≡ λ (x, y). (Some x, Some y)"
abbreviation "None_None_None ≡ (None, None, None)"
abbreviation "None_None_Some ≡ λ (z). (None, None, Some z)"
abbreviation "None_Some_None ≡ λ (y). (None, Some y, None)"
abbreviation "None_Some_Some ≡ λ (y, z). (None, Some y, Some z)"
abbreviation "Some_None_None ≡ λ (x). (Some x, None, None)"
abbreviation "Some_None_Some ≡ λ (x, z). (Some x, None, Some z)"
abbreviation "Some_Some_None ≡ λ (x, y). (Some x, Some y, None)"
abbreviation "Some_Some_Some ≡ λ (x, y, z). (Some x, Some y, Some z)"
lemma inj_Some2[simp, intro]:
"inj None_Some"
"inj Some_None"
"inj Some_Some"
by (rule injI, force)+
lemma inj_Some3[simp, intro]:
"inj None_None_Some"
"inj None_Some_None"
"inj None_Some_Some"
"inj Some_None_None"
"inj Some_None_Some"
"inj Some_Some_None"
"inj Some_Some_Some"
by (rule injI, force)+
definition swap :: "'a × 'b ⇒ 'b × 'a"
where "swap x ≡ (snd x, fst x)"
lemma swap_simps[simp]: "swap (a, b) = (b, a)" unfolding swap_def by simp
lemma swap_inj[intro, simp]: "inj swap" by (rule injI, auto)
lemma swap_surj[intro, simp]: "surj swap" by (rule surjI[where ?f = swap], auto)
lemma swap_bij[intro, simp]: "bij swap" by (rule bijI, auto)
definition push :: "('a × 'b) × 'c ⇒ 'a × 'b × 'c"
where "push x ≡ (fst (fst x), snd (fst x), snd x)"
definition pull :: "'a × 'b × 'c ⇒ ('a × 'b) × 'c"
where "pull x ≡ ((fst x, fst (snd x)), snd (snd x))"
lemma push_simps[simp]: "push ((x, y), z) = (x, y, z)" unfolding push_def by simp
lemma pull_simps[simp]: "pull (x, y, z) = ((x, y), z)" unfolding pull_def by simp
definition label :: "'vertex × 'label × 'vertex ⇒ 'label"
where "label ≡ fst ∘ snd"
lemma label_select[simp]: "label (p, a, q) = a" unfolding label_def by simp
subsection ‹Theorems for @term{curry} and @term{split}›
lemma curry_split[simp]: "curry ∘ case_prod = id" by auto
lemma split_curry[simp]: "case_prod ∘ curry = id" by auto
lemma curry_le[simp]: "curry f ≤ curry g ⟷ f ≤ g" unfolding le_fun_def by force
lemma split_le[simp]: "case_prod f ≤ case_prod g ⟷ f ≤ g" unfolding le_fun_def by force
lemma mono_curry_left[simp]: "mono (curry ∘ h) ⟷ mono h"
unfolding mono_def by fastforce
lemma mono_split_left[simp]: "mono (case_prod ∘ h) ⟷ mono h"
unfolding mono_def by fastforce
lemma mono_curry_right[simp]: "mono (h ∘ curry) ⟷ mono h"
unfolding mono_def split_le[symmetric] by bestsimp
lemma mono_split_right[simp]: "mono (h ∘ case_prod) ⟷ mono h"
unfolding mono_def curry_le[symmetric] by bestsimp
lemma Collect_curry[simp]: "{x. P (curry x)} = case_prod ` {x. P x}" using image_Collect by fastforce
lemma Collect_split[simp]: "{x. P (case_prod x)} = curry ` {x. P x}" using image_Collect by force
lemma gfp_split_curry[simp]: "gfp (case_prod ∘ f ∘ curry) = case_prod (gfp f)"
proof -
have "gfp (case_prod ∘ f ∘ curry) = Sup {u. u ≤ case_prod (f (curry u))}" unfolding gfp_def by simp
also have "… = Sup {u. curry u ≤ curry (case_prod (f (curry u)))}" unfolding curry_le by simp
also have "… = Sup {u. curry u ≤ f (curry u)}" by simp
also have "… = Sup (case_prod ` {u. u ≤ f u})" unfolding Collect_curry[of "λ u. u ≤ f u"] by simp
also have "… = case_prod (Sup {u. u ≤ f u})" by (force simp add: image_comp)
also have "… = case_prod (gfp f)" unfolding gfp_def by simp
finally show ?thesis by this
qed
lemma gfp_curry_split[simp]: "gfp (curry ∘ f ∘ case_prod) = curry (gfp f)"
proof -
have "gfp (curry ∘ f ∘ case_prod) = Sup {u. u ≤ curry (f (case_prod u))}" unfolding gfp_def by simp
also have "… = Sup {u. case_prod u ≤ case_prod (curry (f (case_prod u)))}" unfolding split_le by simp
also have "… = Sup {u. case_prod u ≤ f (case_prod u)}" by simp
also have "… = Sup (curry ` {u. u ≤ f u})" unfolding Collect_split[of "λ u. u ≤ f u"] by simp
also have "… = curry (Sup {u. u ≤ f u})" by (force simp add: image_comp)
also have "… = curry (gfp f)" unfolding gfp_def by simp
finally show ?thesis by this
qed
lemma not_someI:
assumes "⋀ x. P x ⟹ False"
shows "¬ P (SOME x. P x)"
using assms by blast
lemma some_ccontr:
assumes "(⋀ x. ¬ P x) ⟹ False"
shows "P (SOME x. P x)"
using assms someI_ex ccontr by metis
end