Theory C_Algebras
section ‹C-Algebras›
theory C_Algebras
imports Kleene_Algebra.Dioid
begin
no_notation
times (infixl "⋅" 70)
subsection ‹C-Monoids›
text ‹We start with the c-monoid axioms. These can be found in Section~4 of~\<^cite>‹"FurusawaS15a"›.›
class proto_monoid =
fixes s_id :: "'a" ("1⇩σ")
and s_prod :: "'a ⇒ 'a ⇒ 'a" (infixl "⋅" 80)
assumes s_prod_idl [simp]: "1⇩σ ⋅ x = x"
and s_prod_idr [simp]: "x ⋅ 1⇩σ = x"
class proto_bi_monoid = proto_monoid +
fixes c_id :: "'a" ("1⇩π")
and c_prod :: "'a ⇒ 'a ⇒ 'a" (infixl "∥" 80)
assumes c_prod_idl [simp]: "1⇩π ∥ x = x"
and c_prod_assoc: "(x ∥ y) ∥ z = x ∥ (y ∥ z)"
and c_prod_comm: "x ∥ y = y ∥ x"
class c_monoid = proto_bi_monoid +
assumes c1 [simp]: "(x ⋅ 1⇩π) ∥ x = x"
and c2 [simp]: "((x ⋅ 1⇩π) ∥ 1⇩σ) ⋅ y = (x ⋅ 1⇩π) ∥ y"
and c3: "(x ∥ y) ⋅ 1⇩π = (x ⋅ 1⇩π) ∥ (y ⋅ 1⇩π)"
and c4: "(x ⋅ y) ⋅ 1⇩π = x ⋅ (y ⋅ 1⇩π)"
and c5 [simp]: "1⇩σ ∥ 1⇩σ = 1⇩σ"
begin
text ‹Next we define domain explicitly as at the beginning of Section 4 in~\<^cite>‹"FurusawaS15a"›
and start proving the algebraic facts from Section 4. Those involving concrete multirelations, such as Proposition 4.1,
are considered in the theory file for multirelations.›
definition (in c_monoid) d :: "'a ⇒ 'a" where
"d x = (x ⋅ 1⇩π) ∥ 1⇩σ"
lemma c_prod_idr [simp]: "x ∥ 1⇩π = x"
by (simp add: local.c_prod_comm)
text ‹We prove the retraction properties of Lemma 4.2.›
lemma c_idem [simp]: "1⇩π ⋅ 1⇩π = 1⇩π"
by (metis c_prod_idr local.c1)
lemma d_idem [simp]: "d (d x) = d x"
by (simp add: local.d_def)
lemma p_id_idem: "(x ⋅ 1⇩π) ⋅ 1⇩π = x ⋅ 1⇩π"
by (simp add: local.c4)
text ‹Lemma 4.3.›
lemma c2_d: "d x ⋅ y = (x ⋅ 1⇩π) ∥ y"
by (simp add: local.d_def)
lemma cd_2_var: "d (x ⋅ 1⇩π) ⋅ y = (x ⋅ 1⇩π) ∥ y"
by (simp add: c2_d local.c4)
lemma dc_prop1 [simp]: "d x ⋅ 1⇩π = x ⋅ 1⇩π"
by (simp add: c2_d)
lemma dc_prop2 [simp]: "d (x ⋅ 1⇩π) = d x"
by (simp add: local.c4 local.d_def)
lemma ds_prop [simp]: "d x ∥ 1⇩σ = d x"
by (simp add: local.c_prod_assoc local.d_def)
lemma dc [simp]: "d 1⇩π = 1⇩σ"
by (simp add: local.d_def)
text ‹Part (5) of this Lemma has already been verified above. The next two statements
verify the two algebraic properties mentioned in the proof of Proposition 4.4.›
lemma dc_iso [simp]: "d (d x ⋅ 1⇩π) = d x"
by simp
lemma cd_iso [simp]: "d (x ⋅ 1⇩π) ⋅ 1⇩π = x ⋅ 1⇩π"
by simp
text ‹Proposition 4.5.›
lemma d_conc6: "d (x ∥ y) = d x ∥ d y"
proof -
have "d (x ∥ y) = ((x ∥ y) ⋅ 1⇩π) ∥ 1⇩σ"
by (simp add: local.d_def)
also have "... = (x ⋅ 1⇩π) ∥ (y ⋅ 1⇩π) ∥ 1⇩σ"
by (simp add: local.c3)
finally show ?thesis
by (metis ds_prop local.c_prod_assoc local.c_prod_comm local.d_def)
qed
lemma d_conc_s_prod_ax: "d x ∥ d y = d x ⋅ d y"
proof -
have "d x ∥ d y = (x ⋅ 1⇩π) ∥ 1⇩σ ∥ d y"
using local.d_def by presburger
also have "... = (x ⋅ 1⇩π) ∥ d y"
using d_conc6 local.c3 local.c_prod_assoc local.d_def by auto
also have "... = ((x ⋅ 1⇩π) ∥ 1⇩σ) ⋅ d y"
by simp
finally show ?thesis
using local.d_def by auto
qed
lemma d_rest_ax [simp]: "d x ⋅ x = x"
by (simp add: c2_d)
lemma d_loc_ax [simp]: "d (x ⋅ d y) = d (x ⋅ y)"
proof -
have "d (x ⋅ d y) = (x ⋅ d y ⋅ 1⇩π) ∥ 1⇩σ"
by (simp add: local.d_def)
also have "... = (x ⋅ y ⋅ 1⇩π) ∥ 1⇩σ"
by (simp add: local.c4)
finally show ?thesis
by (simp add: local.d_def)
qed
lemma d_exp_ax [simp]: "d (d x ⋅ y) = d x ⋅ d y"
proof -
have "d (d x ⋅ y) = d (d x ⋅ d y)"
by (simp add: d_conc6)
also have "... = d (d (x ∥ y))"
by (simp add: d_conc6 d_conc_s_prod_ax)
also have "... = d (x ∥ y)"
by simp
finally show ?thesis
by (simp add: d_conc6 d_conc_s_prod_ax)
qed
lemma d_comm_ax: "d x ⋅ d y = d y ⋅ d x"
proof -
have "(d x) ⋅ (d y) = d (x ∥ y)"
by (simp add: d_conc6 d_conc_s_prod_ax)
also have "... = d (y ∥ x)"
using local.c_prod_comm by auto
finally show ?thesis
by (simp add: d_conc6 d_conc_s_prod_ax)
qed
lemma d_s_id_prop [simp]: "d 1⇩σ = 1⇩σ"
using local.d_def by auto
text ‹Next we verify the conditions of Proposition 4.6.›
lemma d_s_prod_closed [simp]: "d (d x ⋅ d y) = d x ⋅ d y"
by simp
lemma d_p_prod_closed [simp]: "d (d x ∥ d y) = d x ∥ d y"
using c2_d d_conc6 by auto
lemma d_idem2 [simp]: "d x ⋅ d x = d x"
by (metis d_exp_ax d_rest_ax)
lemma d_assoc: "(d x ⋅ d y) ⋅ d z = d x ⋅ (d y ⋅ d z)"
proof -
have "⋀x y. d x ⋅ d y = d (x ∥ y)"
by (simp add: d_conc6 d_conc_s_prod_ax)
thus ?thesis
by (simp add: local.c_prod_assoc)
qed
lemma iso_1 [simp]: "(d x ⋅ 1⇩π) ∥ 1⇩σ = d x"
by (simp add: local.d_def)
text ‹Lemma 4.7.›
lemma x_c_par_idem [simp]: "(x ⋅ 1⇩π) ∥ (x ⋅ 1⇩π) = x ⋅ 1⇩π"
proof -
have "(x ⋅ 1⇩π) ∥ (x ⋅ 1⇩π) = d x ⋅ (x ⋅ 1⇩π)"
using c2_d by auto
also have "... = d (x ⋅ 1⇩π) ⋅ (x ⋅ 1⇩π)"
by simp
finally show ?thesis
using d_rest_ax by presburger
qed
lemma d_idem_par [simp]: "d x ∥ d x = d x "
by (simp add: d_conc_s_prod_ax)
lemma d_inter_r: "d x ⋅ (y ∥ z) = (d x ⋅ y) ∥ (d x ⋅ z)"
proof -
have "(d x) ⋅ (y ∥ z) = (x ⋅ 1⇩π) ∥ y ∥ z"
using c2_d local.c_prod_assoc by auto
also have "... = (x ⋅ 1⇩π) ∥ y ∥ (x ⋅ 1⇩π) ∥ z"
using local.c_prod_assoc local.c_prod_comm by force
finally show ?thesis
by (simp add: c2_d local.c_prod_assoc)
qed
text ‹Now we provide the counterexamples of Lemma 4.8.›
lemma "(x ∥ y) ⋅ d z = (x ⋅ d z) ∥ (y ⋅ d z)"
nitpick
oops
lemma "(x ⋅ y) ⋅ d z = x ⋅ (y ⋅ d z)"
nitpick
oops
lemma "1⇩π ⋅ x = 1⇩π"
nitpick
oops
end
subsection ‹C-Trioids›
text ‹We can now define the class of c-trioids and prove properties in this class. This covers
the algebraic material of Section 5 in~\<^cite>‹"FurusawaS15a"›.›
class proto_dioid = join_semilattice_zero + proto_monoid +
assumes s_prod_distr: "(x + y) ⋅ z = x ⋅ z + y ⋅ z"
and s_prod_subdistl: "x ⋅ y + x ⋅ z ≤ x ⋅ (y + z)"
and s_prod_annil [simp]: "0 ⋅ x = 0"
begin
lemma s_prod_isol: "x ≤ y ⟹ z ⋅ x ≤ z ⋅ y"
by (metis join.sup.boundedE order_prop s_prod_subdistl)
lemma s_prod_isor: "x ≤ y ⟹ x ⋅ z ≤ y ⋅ z"
using local.order_prop local.s_prod_distr by auto
end
class proto_trioid = proto_dioid + proto_bi_monoid +
assumes p_prod_distl: "x ∥ (y + z) = x ∥ y + x ∥ z"
and p_rpd_annir [simp]: "x ∥ 0 = 0"
sublocale proto_trioid ⊆ ab_semigroup_mult c_prod
proof
fix x y z
show "x ∥ y ∥ z = x ∥ (y ∥ z)"
by (rule c_prod_assoc)
show "x ∥ y = y ∥ x"
by (rule c_prod_comm)
qed
sublocale proto_trioid ⊆ dioid_one_zero "(+)" "(∥)" "1⇩π" 0 "(≤)" "(<)"
proof
fix x y z
show "(x + y) ∥ z = x ∥ z + y ∥ z"
by (simp add: local.c_prod_comm local.p_prod_distl)
show "1⇩π ∥ x = x"
using local.c_prod_idl by blast
show "x ∥ 1⇩π = x"
by (simp add: local.mult_commute)
show "0 + x = x"
by (rule add.left_neutral)
show "0 ∥ x = 0"
by (simp add: local.mult_commute)
show "x ∥ 0 = 0"
by (rule p_rpd_annir)
show "x + x = x"
by (rule add_idem)
show "x ∥ (y + z) = x ∥ y + x ∥ z"
by (rule p_prod_distl)
qed
class c_trioid = proto_trioid + c_monoid +
assumes c6: "x ⋅ 1⇩π ≤ 1⇩π"
begin
text ‹We show that every c-trioid is a c-monoid.›
subclass c_monoid ..
subclass proto_trioid ..
lemma "1⇩π ⋅ 0 = 1⇩π"
nitpick
oops
lemma zero_p_id_prop [simp]: "(x ⋅ 0) ⋅ 1⇩π = x ⋅ 0"
by (simp add: local.c4)
text ‹The following facts prove and refute properties related to sequential and parallel subidentities.›
lemma d_subid: "d x = x ⟹ x ≤ 1⇩σ"
by (metis local.c6 local.c_idem local.d_def local.dc local.mult_isor)
lemma "x ≤ 1⇩σ ⟹ d x = x"
nitpick
oops
lemma p_id_term: "x ⋅ 1⇩π = x ⟹ x ≤ 1⇩π"
by (metis local.c6)
lemma "x ≤ 1⇩π ⟹ x ⋅ 1⇩π = x"
nitpick
oops
text ‹Proposition 5.1. is covered by the theory file on multirelations.
We verify the remaining conditions in Proposition 5.2.›
lemma dlp_ax: "x ≤ d x ⋅ x"
by simp
lemma d_add_ax: "d (x + y) = d x + d y"
proof -
have "d (x + y) = ((x + y) ⋅ 1⇩π) ∥ 1⇩σ"
using local.d_def by blast
also have "... = (x ⋅ 1⇩π) ∥ 1⇩σ + (y ⋅ 1⇩π) ∥ 1⇩σ"
by (simp add: local.distrib_right local.s_prod_distr)
finally show ?thesis
by (simp add: local.d_def)
qed
lemma d_sub_id_ax: "d x ≤ 1⇩σ"
proof -
have "d x = (x ⋅ 1⇩π) ∥ 1⇩σ"
by (simp add: local.d_def)
also have "... ≤ 1⇩π ∥ 1⇩σ"
using local.c6 local.mult_isor by blast
finally show ?thesis
by simp
qed
lemma d_zero_ax [simp]: "d 0 = 0"
by (simp add: local.d_def)
text‹We verify the algebraic conditions in Proposition 5.3.›
lemma d_absorb1 [simp]: "d x + (d x ⋅ d y) = d x"
proof (rule order.antisym)
have "d x + (d x ⋅ d y) ≤ d x + (d x ⋅ 1⇩σ)"
by (metis d_sub_id_ax c2_d d_def join.sup.bounded_iff join.sup.semilattice_axioms join.sup_ge1 s_prod_isol semilattice.idem)
thus "d x + (d x ⋅ d y) ≤ d x"
by simp
show "d x ≤ d x + ((d x) ⋅ (d y))"
using join.sup_ge1 by blast
qed
lemma d_absorb2 [simp]: "d x ⋅ (d x + d y) = d x"
proof -
have "x ⋅ 1⇩π ∥ d x = d x"
by (metis local.c1 local.dc_prop1)
thus ?thesis
by (metis d_absorb1 local.c2_d local.p_prod_distl)
qed
lemma d_dist1: "d x ⋅ (d y + d z) = d x ⋅ d y + d x ⋅ d z"
by (simp add: local.c2_d local.p_prod_distl)
lemma d_dist2: "d x + (d y ⋅ d z) = (d x + d y) ⋅ (d x + d z)"
proof -
have "(d x + d y) ⋅ (d x + d z) = d x ⋅ d x + d x ⋅ d z + d y ⋅ d x + d y ⋅ d z"
using add_assoc d_dist1 local.s_prod_distr by force
also have "... = d x + d x ⋅ d z + d x ⋅ d y + d y ⋅ d z"
using local.d_comm_ax by auto
finally show ?thesis
by simp
qed
lemma d_add_prod_closed [simp]: "d (d x + d y) = d x + d y"
by (simp add: d_add_ax)
text ‹The following properties are not covered in the article.›
lemma x_zero_prop: "(x ⋅ 0) ∥ y = d (x ⋅ 0) ⋅ y"
by (simp add: local.c2_d)
lemma cda_add_ax: "d ((x + y) ⋅ z) = d (x ⋅ z) + d (y ⋅ z)"
by (simp add: d_add_ax local.s_prod_distr)
lemma d_x_zero: "d (x ⋅ 0) = (x ⋅ 0) ∥ 1⇩σ"
by (simp add: x_zero_prop)
text ‹Lemma 5.4 is verified below because its proofs are simplified by using facts from the next subsection.›
subsection ‹Results for Concurrent Dynamic Algebra›
text ‹The following proofs and refutation are related to Section 6 in~\<^cite>‹"FurusawaS15a"›.
We do not consider those involving Kleene algebras in this section. We also do not introduce specific
notation for diamond operators.›
text ‹First we prove Lemma 6.1. Part (1) and (3) have already been verified above. Part (2) and (4) require
additional assumptions which are present in the context of concurrent dynamic algebra~\<^cite>‹"FurusawaS15b"›. We
also present the counterexamples from Lemma 6.3.›
lemma "(x ⋅ y) ⋅ d z = x ⋅ (y ⋅ d z)"
nitpick
oops
lemma "d((x ⋅ y) ⋅ z) = d (x ⋅ d (y ⋅ z))"
nitpick
oops
lemma cda_ax1: "(x ⋅ y) ⋅ d z = x ⋅ (y ⋅ d z) ⟹ d((x ⋅ y) ⋅ z) = d (x ⋅ d (y ⋅ z))"
by (metis local.d_loc_ax)
lemma d_inter: "(x ∥ y) ⋅ d z = (x ⋅ d z) ∥ (y ⋅ d z)"
nitpick
oops
lemma "d ((x ∥ y) ⋅ z) = d (x ⋅ z) ⋅ d (y ⋅ z)"
nitpick
oops
lemma cda_ax2:
assumes "(x ∥ y) ⋅ d z = (x ⋅ d z) ∥ (y ⋅ d z)"
shows "d ((x ∥ y) ⋅ z) = d (x ⋅ z) ⋅ d (y ⋅ z)"
by (metis assms local.d_conc6 local.d_conc_s_prod_ax local.d_loc_ax)
text ‹Next we present some results that do not feature in the article.›
lemma "(x ⋅ y) ⋅ 0 = x ⋅ (y ⋅ 0)"
nitpick
oops
lemma d_x_zero_prop [simp]: "d (x ⋅ 0) ⋅ 1⇩π = x ⋅ 0"
by simp
lemma "x ≤ 1⇩σ ∧ y ≤ 1⇩σ ⟶ x ⋅ y = x ∥ y"
nitpick
oops
lemma "x ⋅ (y ∥ z) ≤ (x ⋅ y) ∥ (x ⋅ z)"
nitpick
oops
lemma "x ≤ x ∥ x"
nitpick
oops
text ‹Lemma 5.4›
lemma d_lb1: "d x ⋅ d y ≤ d x"
by (simp add: less_eq_def add_commute)
lemma d_lb2: "d x ⋅ d y ≤ d y"
using d_lb1 local.d_comm_ax by fastforce
lemma d_glb: "d z ≤ d x ∧ d z ≤ d y ⟹ d z ≤ d x ⋅ d y"
by (simp add: d_dist2 local.less_eq_def)
lemma d_glb_iff: "d z ≤ d x ∧ d z ≤ d y ⟷ d z ≤ d x ⋅ d y"
using d_glb d_lb1 d_lb2 local.order_trans by blast
lemma x_zero_le_c: "x ⋅ 0 ≤ 1⇩π"
by (simp add: p_id_term)
lemma p_subid_lb1: "(x ⋅ 0) ∥ (y ⋅ 0) ≤ x ⋅ 0"
using local.mult_isol x_zero_le_c by fastforce
lemma p_subid_lb2: "(x ⋅ 0) ∥ (y ⋅ 0) ≤ y ⋅ 0"
using local.mult_commute p_subid_lb1 by fastforce
lemma p_subid_idem [simp]: "(x ⋅ 0) ∥ (x ⋅ 0) = x ⋅ 0"
by (metis local.c1 zero_p_id_prop)
lemma p_subid_glb: "z ⋅ 0 ≤ x ⋅ 0 ∧ z ⋅ 0 ≤ y ⋅ 0 ⟹ z ⋅ 0 ≤ (x ⋅ 0) ∥ (y ⋅ 0)"
using local.mult_isol_var by force
lemma p_subid_glb_iff: "z ⋅ 0 ≤ x ⋅ 0 ∧ z ⋅ 0 ≤ y ⋅ 0 ⟷ z ⋅ 0 ≤ (x ⋅ 0) ∥ (y ⋅ 0)"
using local.order_trans p_subid_glb p_subid_lb1 p_subid_lb2 by blast
lemma x_c_glb: "z ⋅ 1⇩π ≤ x ⋅ 1⇩π ∧ z ⋅ 1⇩π ≤ y ⋅ 1⇩π ⟹ z ⋅ 1⇩π ≤ (x ⋅ 1⇩π) ∥ (y ⋅ 1⇩π)"
using local.mult_isol_var by force
lemma x_c_lb1: "(x ⋅ 1⇩π) ∥ (y ⋅ 1⇩π) ≤ x ⋅ 1⇩π"
using local.c6 local.mult_isol_var by force
lemma x_c_lb2: "(x ⋅ 1⇩π) ∥ (y ⋅ 1⇩π) ≤ y ⋅ 1⇩π"
using local.mult_commute x_c_lb1 by fastforce
lemma x_c_glb_iff: "z ⋅ 1⇩π ≤ x ⋅ 1⇩π ∧ z ⋅ 1⇩π ≤ y ⋅ 1⇩π ⟷ z ⋅ 1⇩π ≤ (x ⋅ 1⇩π) ∥ (y ⋅ 1⇩π)"
by (meson local.order.trans x_c_glb x_c_lb1 x_c_lb2)
end
subsection ‹C-Lattices›
text ‹We can now define c-lattices and prove the results from Section 7 in~\<^cite>‹"FurusawaS15a"›.›
class pbl_monoid = proto_trioid +
fixes U :: 'a
fixes meet :: "'a ⇒ 'a ⇒ 'a" (infixl "⊓" 70)
assumes U_def: "x ≤ U"
and meet_assoc: "(x ⊓ y) ⊓ z = x ⊓ (y ⊓ z)"
and meet_comm: "x ⊓ y = y ⊓ x"
and meet_idem [simp]: "x ⊓ x = x"
and absorp1: "x ⊓ (x + y) = x"
and absorp2: "x + (x ⊓ y) = x"
begin
sublocale lattice "(⊓)" "(≤)" "(<)" "(+)"
proof
show a: "⋀x y. x ⊓ y ≤ x"
by (simp add: local.absorp2 local.less_eq_def add_commute)
show b: " ⋀x y. x ⊓ y ≤ y"
using a local.meet_comm by fastforce
show " ⋀x y z. x ≤ y ⟹ x ≤ z ⟹ x ≤ y ⊓ z"
by (metis b local.absorp1 local.less_eq_def local.meet_assoc)
qed
lemma meet_glb: "z ≤ x ∧ z ≤ y ⟹ z ≤ x ⊓ y"
by simp
lemma meet_prop: "z ≤ x ∧ z ≤ y ⟷ z ≤ x ⊓ y"
by simp
end
class pbdl_monoid = pbl_monoid +
assumes lat_dist1: "x + (y ⊓ z) = (x + y) ⊓ (x + z)"
begin
lemma lat_dist2: "(x ⊓ y) + z = (x + z) ⊓ (y + z)"
by (simp add: local.lat_dist1 add_commute)
lemma lat_dist3: "x ⊓ (y + z) = (x ⊓ y) + (x ⊓ z)"
proof -
have "⋀x y z. x ⊓ ((x + y) ⊓ z) = x ⊓ z"
by (metis local.absorp1 local.meet_assoc)
thus ?thesis
using lat_dist2 local.absorp2 add_commute by force
qed
lemma lat_dist4: "(x + y) ⊓ z = (x ⊓ z) + (y ⊓ z)"
using lat_dist3 local.meet_comm by auto
lemma d_equiv_prop: "(∀z. z + x = z + y ∧ z ⊓ x = z ⊓ y) ⟹ x = y"
by (metis local.add_zerol)
end
text ‹The symbol $\overline{1}_\pi$ from~\<^cite>‹"FurusawaS15a"› is written nc in this theory file.›
class c_lattice = pbdl_monoid +
fixes nc :: "'a"
assumes cl1 [simp]: "x ⋅ 1⇩π + x ⋅ nc = x ⋅ U"
and cl2 [simp]: "1⇩π ⊓ (x + nc) = x ⋅ 0"
and cl3: "x ⋅ (y ∥ z) ≤ (x ⋅ y) ∥ (x ⋅ z)"
and cl4: "z ∥ z ≤ z ⟹ (x ∥ y) ⋅ z = (x ⋅ z) ∥ (y ⋅ z)"
and cl5: "x ⋅ (y ⋅ (z ⋅ 0)) = (x ⋅ y) ⋅ (z ⋅ 0)"
and cl6 [simp]: "(x ⋅ 0) ⋅ z = x ⋅ 0"
and cl7 [simp]: "1⇩σ ∥ 1⇩σ = 1⇩σ"
and cl8 [simp]: "((x ⋅ 1⇩π) ∥ 1⇩σ) ⋅ y = (x ⋅ 1⇩π) ∥ y"
and cl9 [simp]: "((x ⊓ 1⇩σ) ⋅ 1⇩π) ∥ 1⇩σ = x ⊓ 1⇩σ"
and cl10: "((x ⊓ nc) ⋅ 1⇩π) ∥ 1⇩σ = 1⇩σ ⊓ (x ⊓ nc) ⋅ nc"
and cl11 [simp]: "((x ⊓ nc) ⋅ 1⇩π) ∥ nc = (x ⊓ nc) ⋅ nc"
begin
text ‹We show that every c-lattice is a c-trioid (Proposition 7.1) Proposition 7.2 is again
covered by the theory for multirelations.›
subclass c_trioid
proof
fix x y
show "x ⋅ 1⇩π ∥ 1⇩σ ⋅ y = x ⋅ 1⇩π ∥ y"
by auto
show "x ∥ y ⋅ 1⇩π = x ⋅ 1⇩π ∥ (y ⋅ 1⇩π)"
by (simp add: local.cl4)
show "x ⋅ y ⋅ 1⇩π = x ⋅ (y ⋅ 1⇩π)"
by (metis local.absorp1 local.cl2 local.cl5)
show "1⇩σ ∥ 1⇩σ = 1⇩σ"
by (meson local.cl7)
show x: "x ⋅ 1⇩π ≤ 1⇩π"
by (metis local.absorp1 local.cl2 local.cl5 local.inf_le1 local.s_prod_idl)
show "x ⋅ 1⇩π ∥ x = x"
by (metis x order.eq_iff local.cl3 local.mult_1_right local.mult_commute local.mult_isol local.s_prod_idr)
qed
text ‹First we verify the complementation conditions after the definition of c-lattices.›
lemma c_nc_comp1 [simp]: "1⇩π + nc = U"
by (metis local.cl1 local.s_prod_idl)
lemma c_nc_comp2 [simp]: "1⇩π ⊓ nc = 0"
by (metis local.add_zero_l local.cl2 local.s_prod_annil)
lemma c_0: "x ⊓ 1⇩π = x ⋅ 0"
by (metis c_nc_comp2 local.add_zeror local.cl2 local.lat_dist3 local.meet_comm)
text ‹Next we verify the conditions in Proposition 7.2.›
lemma d_s_subid: "d x = x ⟷ x ≤ 1⇩σ"
by (metis local.cl9 local.d_def local.d_subid local.inf.absorb_iff1)
lemma term_p_subid: "x ⋅ 1⇩π = x ⟷ x ≤ 1⇩π"
by (metis c_0 local.cl6 local.inf.absorb_iff1 local.p_id_term)
lemma term_p_subid_var: "x ⋅ 0 = x ⟷ x ≤ 1⇩π"
using c_0 local.inf.absorb_iff1 by auto
lemma vec_iff: "d x ⋅ U = x ⟷ (x ⋅ 1⇩π) ∥ U = x"
by (simp add: local.c2_d)
lemma nc_iff1: "x ≤ nc ⟷ x ⊓ 1⇩π = 0"
proof
fix x
assume assm: "x ≤ nc"
hence "x = x ⊓ nc"
by (simp add: local.inf.absorb_iff1)
hence "x ⊓ 1⇩π = x ⊓ nc ⊓ 1⇩π"
by auto
then show "x ⊓ 1⇩π = 0"
by (metis assm c_0 c_nc_comp2 local.cl2 local.less_eq_def)
next
fix x
assume assm: "x ⊓ 1⇩π = 0"
have "x = (x ⊓ nc) + (x ⊓ 1⇩π)"
by (metis c_nc_comp1 local.U_def local.add_comm local.lat_dist3 local.inf.absorb_iff1)
hence "x = x ⊓ nc"
using assm by auto
thus "x ≤ nc"
using local.inf.absorb_iff1 by auto
qed
lemma nc_iff2: "x ≤ nc ⟷ x ⋅ 0 = 0"
using c_0 nc_iff1 by auto
text ‹The results of Lemma 7.3 are again at the multirelational level.
Hence we continue with Lemma 7.4.›
lemma assoc_p_subid: "(x ⋅ y) ⋅ (z ⋅ 1⇩π) = x ⋅ (y ⋅ (z ⋅ 1⇩π))"
by (metis c_0 local.c6 local.cl5 local.inf.absorb_iff1)
lemma zero_assoc3: "(x ⋅ y) ⋅ 0 = x ⋅ (y ⋅ 0)"
by (metis local.cl5 local.s_prod_annil)
lemma x_zero_interr: "(x ⋅ 0) ∥ (y ⋅ 0) = (x ∥ y) ⋅ 0"
by (simp add: local.cl4)
lemma p_subid_interr: "(x ⋅ z ⋅ 1⇩π) ∥ (y ⋅ z ⋅ 1⇩π) = (x ∥ y) ⋅ z ⋅ 1⇩π"
by (simp add: local.c4 local.cl4)
lemma d_interr: "(x ⋅ d z) ∥ (y ⋅ d z) = (x ∥ y) ⋅ d z"
by (simp add: local.cl4)
lemma subidem_par: "x ≤ x ∥ x"
proof -
have "x = x ⋅ 1⇩σ"
by auto
also have "... = x ⋅ (1⇩σ ∥ 1⇩σ)"
by auto
finally show ?thesis
by (metis local.cl3 local.cl7)
qed
lemma meet_le_par: "x ⊓ y ≤ x ∥ y"
proof -
have "x ⊓ y = (x ⊓ y) ⊓ (x ⊓ y)"
using local.meet_idem by presburger
thus ?thesis
using local.inf_le1 local.inf_le2 local.mult_isol_var local.order_trans subidem_par by blast
qed
text‹Next we verify Lemma 7.5 and prove some related properties.›
lemma x_split [simp]: "(x ⊓ nc) + (x ⊓ 1⇩π) = x"
proof -
have "x = x ⊓ U"
using local.U_def local.inf.absorb_iff1 by auto
also have "... = x ⊓ (nc + 1⇩π)"
by (simp add: add_commute)
finally show ?thesis
by (metis local.lat_dist3)
qed
lemma x_split_var [simp]: "(x ⊓ nc) + (x ⋅ 0) = x"
by (metis local.c_0 x_split)
lemma s_subid_closed [simp]: "x ⊓ nc ⊓ 1⇩σ = x ⊓ 1⇩σ"
proof -
have "x ⊓ 1⇩σ = ((x ⊓ nc) + (x ⊓ 1⇩π)) ⊓ 1⇩σ"
using x_split by presburger
also have "... = (x ⊓ nc ⊓ 1⇩σ) + (x ⊓ 1⇩π ⊓ 1⇩σ)"
by (simp add: local.lat_dist3 local.meet_comm)
also have "... = (x ⊓ nc ⊓ 1⇩σ) + (x ⊓ 0)"
by (metis c_0 local.meet_assoc local.meet_comm local.s_prod_idl)
finally show ?thesis
by (metis local.absorp1 local.add_zeror local.lat_dist1 local.meet_comm)
qed
lemma sub_id_le_nc: "x ⊓ 1⇩σ ≤ nc"
by (metis local.inf.absorb_iff2 local.inf_left_commute local.meet_comm s_subid_closed)
lemma s_x_c [simp]: "1⇩σ ⊓ (x ⋅ 1⇩π) = 0"
proof -
have "1⇩σ ⊓ 1⇩π = 0"
using c_0 local.s_prod_idl by presburger
hence "1⇩σ ⊓ x ⋅ 1⇩π ≤ 0"
using local.c6 local.inf_le1 local.inf_le2 local.meet_prop local.order.trans by blast
thus ?thesis
using local.less_eq_def local.no_trivial_inverse by blast
qed
lemma s_x_zero [simp]: "1⇩σ ⊓ (x ⋅ 0) = 0"
by (metis local.cl6 s_x_c)
lemma c_nc [simp]: "(x ⋅ 1⇩π) ⊓ nc = 0"
proof -
have "x ⋅ 1⇩π ⊓ nc ≤ 1⇩π"
by (meson local.c6 local.dual_order.trans local.inf_le1)
thus ?thesis
by (metis local.inf_le2 nc_iff2 term_p_subid_var)
qed
lemma zero_nc [simp]: "(x ⋅ 0) ⊓ nc = 0"
by (metis c_nc local.cl6)
lemma nc_zero [simp]: "(x ⊓ nc) ⋅ 0 = 0"
by (meson local.inf_le2 nc_iff2)
text ‹Lemma 7.6.›
lemma c_def [simp]: "U ⋅ 0 = 1⇩π"
by (metis c_nc_comp1 c_0 local.absorp1 local.meet_comm)
lemma c_x_prop [simp]: "1⇩π ⋅ x = 1⇩π"
using c_def local.cl6 by blast
lemma U_idem_s_prod [simp]: "U ⋅ U = U"
by (metis local.U_def order.eq_iff local.s_prod_idl local.s_prod_isor)
lemma U_idem_p_prod [simp]: "U ∥ U = U"
using local.U_def order.eq_iff subidem_par by presburger
lemma U_c [simp]: "U ⋅ 1⇩π = 1⇩π"
by (metis U_idem_s_prod local.c_def zero_assoc3)
lemma s_le_nc: "1⇩σ ≤ nc"
by (metis local.meet_idem sub_id_le_nc)
lemma nc_c [simp]: "nc ⋅ 1⇩π = 1⇩π"
proof (rule order.antisym)
have "nc ⋅ 1⇩π = nc ⋅ 1⇩π ⋅ 0"
by (simp add: zero_assoc3)
also have "... = nc ⋅ 1⇩π ⊓ 1⇩π"
by (simp add: c_0)
finally show "nc ⋅ 1⇩π ≤ 1⇩π"
using local.c6 by blast
show "1⇩π ≤ nc ⋅ 1⇩π"
using local.s_prod_isor s_le_nc by fastforce
qed
lemma nc_nc [simp]: "nc ⋅ nc = nc"
proof -
have "nc ⋅ nc = (nc ⋅ 1⇩π) ∥ nc"
by (metis local.cl11 local.meet_idem)
thus ?thesis
by simp
qed
lemma U_nc [simp]: "U ⋅ nc = U"
proof -
have "U ⋅ nc = (1⇩π + nc) ⋅ nc"
by force
also have "... = 1⇩π ⋅ nc + nc ⋅ nc"
using local.s_prod_distr by blast
also have "... = 1⇩π + nc"
by simp
finally show ?thesis
by auto
qed
lemma nc_U [simp]: "nc ⋅ U = U"
proof -
have "nc ⋅ U = nc ⋅ 1⇩π + nc ⋅ nc"
using local.cl1 by presburger
thus ?thesis
by simp
qed
lemma nc_nc_par [simp]: "nc ∥ nc = nc"
proof -
have "nc ∥ nc = (nc ∥ nc ⊓ nc) + (nc ∥ nc) ⋅ 0"
by simp
also have "... = nc + (nc ⋅ 0) ∥ (nc ⋅ 0)"
by (metis local.meet_comm local.inf.absorb_iff1 subidem_par x_zero_interr)
also have "... = nc + 0 ∥ 0"
by (metis local.absorp1 local.meet_comm nc_zero)
finally show ?thesis
by (metis add_commute local.add_zerol local.annil)
qed
lemma U_nc_par [simp]: "U ∥ nc = nc"
proof -
have "U ∥ nc = nc ∥ nc + 1⇩π ∥ nc"
by (metis c_nc_comp1 local.add_comm local.distrib_right)
also have "... = nc + nc"
by force
finally show ?thesis
by simp
qed
text ‹We prove Lemma 7.8 and related properties.›
lemma x_y_split [simp]: "(x ⊓ nc) ⋅ y + x ⋅ 0 = x ⋅ y"
by (metis c_0 local.cl6 local.s_prod_distr x_split)
lemma x_y_prop: "1⇩σ ⊓ (x ⊓ nc) ⋅ y = 1⇩σ ⊓ x ⋅ y"
proof -
have "1⇩σ ⊓ x ⋅ y = 1⇩σ ⊓ ((x ⊓ nc) ⋅ y + x ⋅ 0)"
using x_y_split by presburger
also have "... = (1⇩σ ⊓ (x ⊓ nc) ⋅ y) + (1⇩σ ⊓ x ⋅ 0)"
by (simp add: local.lat_dist3 add_commute)
finally show ?thesis
by (metis local.add_zeror s_x_zero)
qed
lemma s_nc_U: "1⇩σ ⊓ x ⋅ nc = 1⇩σ ⊓ x ⋅ U"
proof -
have "1⇩σ ⊓ x ⋅ U = 1⇩σ ⊓ (x ⋅ nc + x ⋅ 1⇩π)"
by (simp add: add_commute)
also have "... = (1⇩σ ⊓ x ⋅ nc) + (1⇩σ ⊓ x ⋅ 1⇩π)"
using local.lat_dist3 by blast
finally show ?thesis
by (metis local.add_zeror s_x_c)
qed
lemma sid_le_nc_var: "1⇩σ ⊓ x ≤ 1⇩σ ⊓ x ∥ nc"
proof -
have "1⇩σ ⊓ x = x ⊓ (1⇩σ ⊓ nc)"
by (metis (no_types) local.inf.absorb1 local.inf.commute s_le_nc)
hence "1⇩σ ⊓ x ∥ nc + 1⇩σ ⊓ x = (x ∥ nc + x ⊓ nc) ⊓ 1⇩σ"
using local.inf.commute local.inf.left_commute local.lat_dist4 by auto
thus ?thesis
by (metis (no_types) local.inf.commute local.join.sup.absorb_iff1 meet_le_par)
qed
lemma s_nc_par_U: "1⇩σ ⊓ x ∥ nc = 1⇩σ ⊓ x ∥ U"
proof -
have "1⇩σ ⊓ x ∥ U = 1⇩σ ⊓ (x ∥ nc + x)"
by (metis c_nc_comp1 local.add_comm local.distrib_left local.mult_oner)
also have "... = (1⇩σ ⊓ x ∥ nc) + (x ⊓ 1⇩σ)"
by (metis local.lat_dist3 local.meet_comm)
also have "... = 1⇩σ ⊓ x ∥ nc"
by (metis local.add_comm local.less_eq_def local.meet_comm sid_le_nc_var)
finally show ?thesis
by metis
qed
lemma x_c_nc_split: "(x ⋅ 1⇩π) ∥ nc = (x ⊓ nc) ⋅ nc + (x ⋅ 0) ∥ nc"
by (metis local.cl11 local.mult_commute local.p_prod_distl x_y_split)
lemma x_c_U_split: "(x ⋅ 1⇩π) ∥ U = x ⋅ U + (x ⋅ 0) ∥ U"
proof -
have "x ⋅ U + (x ⋅ 0) ∥ U = (x ⊓ nc) ⋅ U + (x ⋅ 0) ∥ U"
by (metis U_c U_idem_s_prod U_nc local.add_assoc' local.cl1 local.distrib_left local.mult_oner x_y_split)
also have "... = (x ⊓ nc) ⋅ nc + (x ⊓ nc) ⋅ 1⇩π + (x ⋅ 0) ∥ nc + x ⋅ 0"
by (metis add_commute c_nc_comp1 local.cl1 local.combine_common_factor local.mult_1_right local.mult_commute)
also have "... = (x ⋅ 1⇩π) ∥ nc + x ⋅ 1⇩π"
by (metis local.add_ac(1) local.add_commute x_c_nc_split x_y_split)
thus ?thesis
by (metis c_nc_comp1 calculation local.add_comm local.distrib_left local.mult_oner)
qed
subsection ‹Domain in C-Lattices›
text ‹We now prove variants of the domain axioms and verify the properties of Section 8 in~\<^cite>‹"FurusawaS15a"›.›
lemma cl9_d [simp]: "d (x ⊓ 1⇩σ) = x ⊓ 1⇩σ"
by (simp add: local.d_def)
lemma cl10_d: "d (x ⊓ nc) = 1⇩σ ⊓ (x ⊓ nc) ⋅ nc"
using local.cl10 local.d_def by auto
lemma cl11_d [simp]: "d (x ⊓ nc) ⋅ nc = (x ⊓ nc) ⋅ nc"
using local.c2_d by force
lemma cl10_d_var1: "d (x ⊓ nc) = 1⇩σ ⊓ x ⋅ nc"
by (simp add: cl10_d x_y_prop)
lemma cl10_d_var2: "d (x ⊓ nc) = 1⇩σ ⊓ (x ⊓ nc) ⋅ U"
by (simp add: cl10_d s_nc_U)
lemma cl10_d_var3: "d (x ⊓ nc) = 1⇩σ ⊓ x ⋅ U"
by (simp add: cl10_d_var1 s_nc_U)
text ‹We verify the remaining properties of Lemma 8.1.›
lemma d_U [simp]: "d U = 1⇩σ"
by (simp add: local.d_def)
lemma d_nc [simp]: "d nc = 1⇩σ"
using local.d_def by auto
lemma alt_d_def_nc_nc: "d (x ⊓ nc) = 1⇩σ ⊓ ((x ⊓ nc) ⋅ 1⇩π) ∥ nc"
by (simp add: cl10_d_var1 x_y_prop)
lemma alt_d_def_nc_U: "d (x ⊓ nc) = 1⇩σ ⊓ ((x ⊓ nc) ⋅ 1⇩π) ∥ U"
by (metis alt_d_def_nc_nc local.c2_d s_nc_U)
text ‹We verify the identity before Lemma 8.2 of~\<^cite>‹"FurusawaS15a"› together with variants.›
lemma d_def_split [simp]: "d (x ⊓ nc) + d (x ⋅ 0) = d x"
by (metis local.d_add_ax x_split_var)
lemma d_def_split_var [simp]: "d (x ⊓ nc) + (x ⋅ 0) ∥ 1⇩σ = d x"
by (metis d_def_split local.d_x_zero)
lemma ax7 [simp]: "(1⇩σ ⊓ x ⋅ U) + (x ⋅ 0) ∥ 1⇩σ = d x"
by (metis cl10_d_var3 d_def_split_var)
text ‹Lemma 8.2.›
lemma dom12_d: "d x = 1⇩σ ⊓ (x ⋅ 1⇩π) ∥ nc"
proof -
have "1⇩σ ⊓ (x ⋅ 1⇩π) ∥ nc = 1⇩σ ⊓ ((x ⊓ nc) ⋅ 1⇩π + x ⋅ 0) ∥ nc"
using x_y_split by presburger
also have "... = (1⇩σ ⊓ ((x ⊓ nc) ⋅ 1⇩π) ∥ nc) + (1⇩σ ⊓ (x ⋅ 0) ∥ nc)"
by (simp add: local.lat_dist3 local.mult_commute local.p_prod_distl add_commute)
also have "... = d (x ⊓ nc) + d (x ⋅ 0)"
by (metis add_commute c_0 cl10_d_var1 local.add_zerol local.annil local.c2_d local.d_def local.mult_commute local.mult_onel local.zero_p_id_prop x_split)
finally show ?thesis
by (metis d_def_split)
qed
lemma dom12_d_U: "d x = 1⇩σ ⊓ (x ⋅ 1⇩π) ∥ U"
by (simp add: dom12_d s_nc_par_U)
lemma dom_def_var: "d x = (x ⋅ U ⊓ 1⇩π) ∥ 1⇩σ"
by (simp add: c_0 local.d_def zero_assoc3)
text‹Lemma 8.3.›
lemma ax5_d [simp]: "d (x ⊓ nc) ⋅ U = (x ⊓ nc) ⋅ U"
proof -
have "d (x ⊓ nc) ⋅ U = d (x ⊓ nc) ⋅ nc + d (x ⊓ nc) ⋅ 1⇩π"
using add_commute local.cl1 by presburger
also have "... = (x ⊓ nc) ⋅ nc + (x ⊓ nc) ⋅ 1⇩π"
by simp
finally show ?thesis
by (simp add: add_commute)
qed
lemma ax5_0 [simp]: "d (x ⋅ 0) ⋅ U = (x ⋅ 0) ∥ U"
using local.x_zero_prop by presburger
lemma x_c_U_split2: "d x ⋅ nc = (x ⊓ nc) ⋅ nc + (x ⋅ 0) ∥ nc"
by (simp add: local.c2_d x_c_nc_split)
lemma x_c_U_split3: "d x ⋅ U = (x ⊓ nc) ⋅ U + (x ⋅ 0) ∥ U"
by (metis d_def_split local.s_prod_distr ax5_0 ax5_d)
lemma x_c_U_split_d: "d x ⋅ U = x ⋅ U + (x ⋅ 0) ∥ U"
using local.c2_d x_c_U_split by presburger
lemma x_U_prop2: "x ⋅ nc = d (x ⊓ nc) ⋅ nc + x ⋅ 0"
by (metis local.c2_d local.cl11 x_y_split)
lemma x_U_prop3: "x ⋅ U = d (x ⊓ nc) ⋅ U + x ⋅ 0"
by (metis ax5_d x_y_split)
lemma d_x_nc [simp]: "d (x ⋅ nc) = d x"
using local.c4 local.d_def by auto
lemma d_x_U [simp]: "d (x ⋅ U) = d x"
by (simp add: local.c4 local.d_def)
text ‹The next properties of domain are important, but do not feature in~\<^cite>‹"FurusawaS15a"›.
Proofs can be found in~\<^cite>‹"FurusawaS15b"›.›
lemma d_llp1: "d x ≤ d y ⟹ x ≤ d y ⋅ x"
by (metis local.d_rest_ax local.s_prod_isor)
lemma d_llp2: "x ≤ d y ⋅ x ⟹ d x ≤ d y"
proof -
assume a1: "x ≤ d y ⋅ x"
have "∀x y. d (x ∥ y) = x ⋅ 1⇩π ∥ d y"
using local.c2_d local.d_conc6 local.d_conc_s_prod_ax by presburger
hence "d x ≤ d (y ⋅ 1⇩π)"
using a1 by (metis (no_types) local.c2_d local.c6 local.c_prod_comm order.eq_iff local.mult_isol local.mult_oner)
thus ?thesis
by simp
qed
lemma demod1: "d (x ⋅ y) ≤ d z ⟹ x ⋅ d y ≤ d z ⋅ x"
proof -
assume "d (x ⋅ y) ≤ d z"
hence "∀v. x ⋅ y ⋅ 1⇩π ∥ v ≤ z ⋅ 1⇩π ∥ v"
by (metis (no_types) local.c2_d local.s_prod_isor)
hence "∀v. x ⋅ (y ⋅ 1⇩π ∥ v) ≤ z ⋅ 1⇩π ∥ (x ⋅ v)"
by (metis local.c4 local.cl3 local.dual_order.trans)
thus ?thesis
by (metis local.c2_d local.s_prod_idr)
qed
lemma demod2: "x ⋅ d y ≤ d z ⋅ x ⟹ d (x ⋅ y) ≤ d z"
proof -
assume "x ⋅ d y ≤ d z ⋅ x"
hence "d (x ⋅ y) ≤ d (d z ⋅ x)"
by (metis local.d_def local.d_loc_ax local.mult_isor local.s_prod_isor)
thus ?thesis
using local.d_conc6 local.d_conc_s_prod_ax local.d_glb_iff by fastforce
qed
subsection ‹Structural Properties of C-Lattices›
text ‹Now we consider the results from Section 9 and 10 in~\<^cite>‹"FurusawaS15a"›.
First we verify the conditions for Proposition 9.1.›
lemma d_meet_closed [simp]: "d (d x ⊓ d y) = d x ⊓ d y"
using d_s_subid local.d_sub_id_ax local.inf_le1 local.order_trans by blast
lemma d_s_prod_eq_meet: "d x ⋅ d y = d x ⊓ d y"
apply (rule order.antisym)
apply (metis local.d_lb1 local.d_lb2 local.meet_glb)
by (metis d_meet_closed local.inf_le1 local.inf_le2 local.d_glb)
lemma d_p_prod_eq_meet: "d x ∥ d y = d x ⊓ d y"
by (simp add: d_s_prod_eq_meet local.d_conc_s_prod_ax)
lemma s_id_par_s_prod: "(x ⊓ 1⇩σ) ∥ (y ⊓ 1⇩σ) = (x ⊓ 1⇩σ) ⋅ (y ⊓ 1⇩σ)"
by (metis cl9_d local.d_conc_s_prod_ax)
lemma s_id_par [simp]: "x ⊓ 1⇩σ ∥ x ⊓ 1⇩σ = x ⊓ 1⇩σ"
using local.meet_assoc local.meet_comm local.inf.absorb_iff1 meet_le_par by auto
text ‹We verify the remaining conditions in Proposition 9.2.›
lemma p_subid_par_eq_meet: "(x ⋅ 0) ∥ (y ⋅ 0) = (x ⋅ 0) ⊓ (y ⋅ 0)"
by (simp add: local.meet_glb local.order.antisym local.p_subid_lb1 local.p_subid_lb2 meet_le_par)
lemma p_subid_par_eq_meet_var: "(x ⋅ 1⇩π) ∥ (y ⋅ 1⇩π) = (x ⋅ 1⇩π) ⊓ (y ⋅ 1⇩π)"
by (metis c_x_prop p_subid_par_eq_meet zero_assoc3)
lemma x_zero_add_closed: "x ⋅ 0 + y ⋅ 0 = (x + y) ⋅ 0"
by (simp add: local.s_prod_distr)
lemma x_zero_meet_closed: "(x ⋅ 0) ⊓ (y ⋅ 0) = (x ⊓ y) ⋅ 0"
by (metis c_0 local.cl6 local.meet_assoc local.meet_comm)
text ‹The following set of lemmas investigates the closure properties of vectors, including Lemma 9,3.›
lemma U_par_zero [simp]: "(0 ⋅ c) ∥ U = 0"
by fastforce
lemma U_par_s_id [simp]: "(1⇩σ ⋅ 1⇩π) ∥ U = U"
by auto
lemma U_par_p_id [simp]: "(1⇩π ⋅ 1⇩π) ∥ U = U"
by auto
lemma U_par_nc [simp]: "(nc ⋅ 1⇩π) ∥ U = U"
by auto
lemma d_add_var: "d x ⋅ z + d y ⋅ z = d (x + y) ⋅ z"
by (simp add: local.d_add_ax local.s_prod_distr)
lemma d_interr_U: "(d x ⋅ U) ∥ (d y ⋅ U) = d (x ∥ y) ⋅ U"
by (simp add: local.cl4 local.d_conc6)
lemma d_meet:
assumes "⋀ x y z. (x ⊓ y ⊓ 1⇩σ) ⋅ z = (x ⊓ 1⇩σ) ⋅ z ⊓ (y ⊓ 1⇩σ) ⋅ z"
shows "d x ⋅ z ⊓ d y ⋅ z = (d x ⊓ d y) ⋅ z"
proof -
have "(d x ⊓ d y) ⋅ z = (d x ⊓ d y ⊓ 1⇩σ) ⋅ z"
using local.d_sub_id_ax local.meet_assoc local.inf.absorb_iff1 by fastforce
also have "... = (d x ⊓ 1⇩σ) ⋅ z ⊓ (d y ⊓ 1⇩σ) ⋅ z"
using assms by auto
finally show ?thesis
by (metis local.d_sub_id_ax local.inf.absorb_iff1)
qed
text ‹Proposition 9.4›
lemma nc_zero_closed [simp]: "0 ⊓ nc = 0"
by (simp add: local.inf.commute local.inf_absorb2)
lemma nc_s [simp]: "1⇩σ ⊓ nc = 1⇩σ"
using local.inf.absorb_iff1 s_le_nc by blast
lemma nc_add_closed: "(x ⊓ nc) + (y ⊓ nc) = (x + y) ⊓ nc"
using local.lat_dist4 by force
lemma nc_meet_closed: "(x ⊓ nc) ⊓ (y ⊓ nc) = x ⊓ y ⊓ nc"
using local.meet_assoc local.meet_comm local.inf_le1 local.inf.absorb_iff1 by fastforce
lemma nc_scomp_closed: "((x ⊓ nc) ⋅ (y ⊓ nc)) ≤ nc"
by (simp add: c_0 nc_iff1 zero_assoc3)
lemma nc_scomp_closed_alt [simp]: "((x ⊓ nc) ⋅ (y ⊓ nc)) ⊓ nc = (x ⊓ nc) ⋅ (y ⊓ nc)"
using local.inf.absorb_iff1 nc_scomp_closed by blast
lemma nc_ccomp_closed: "(x ⊓ nc) ∥ (y ⊓ nc) ≤ nc"
proof -
have "(x ⊓ nc) ∥ (y ⊓ nc) ≤ nc ∥ nc"
by (meson local.inf_le2 local.mult_isol_var)
thus ?thesis
by auto
qed
lemma nc_ccomp_closed_alt [simp]: "(x ∥ (y ⊓ nc)) ⊓ nc = x ∥ (y ⊓ nc)"
by (metis U_nc_par local.U_def local.inf_le2 local.mult_isol_var local.inf.absorb_iff1)
text ‹Lemma 9.6.›
lemma tarski_prod:
assumes "⋀x. x ⊓ nc ≠ 0 ⟹ nc ⋅ ((x ⊓ nc) ⋅ nc) = nc"
and "⋀x y z. d x ⋅ (y ⋅ z) = (d x ⋅ y) ⋅ z"
shows "((x ⊓ nc) ⋅ nc) ⋅ ((y ⊓ nc) ⋅ nc) = (if (y ⊓ nc) = 0 then 0 else (x ⊓ nc) ⋅ nc)"
proof (cases "y ⊓ nc = 0")
fix x y
assume assm: "y ⊓ nc = 0"
show "(x ⊓ nc) ⋅ nc ⋅ ((y ⊓ nc) ⋅ nc) = (if y ⊓ nc = 0 then 0 else (x ⊓ nc) ⋅ nc)"
by (metis assm c_0 local.cl6 local.meet_comm nc_zero zero_assoc3)
next
fix x y
assume assm: "y ⊓ nc ≠ 0"
have "((x ⊓ nc) ⋅ nc) ⋅ ((y ⊓ nc) ⋅ nc) = (d (x ⊓ nc) ⋅ nc) ⋅ ((y ⊓ nc) ⋅ nc)"
by simp
also have "... = d (x ⊓ nc) ⋅ (nc ⋅ ((y ⊓ nc) ⋅ nc))"
by (simp add: assms(2))
also have "... = d (x ⊓ nc) ⋅ nc"
by (simp add: assm assms(1))
finally show "(x ⊓ nc) ⋅ nc ⋅ ((y ⊓ nc) ⋅ nc) = (if y ⊓ nc = 0 then 0 else (x ⊓ nc) ⋅ nc)"
by (simp add: assm)
qed
text ‹We show the remaining conditions of Proposition 9.8.›
lemma nc_prod_aux [simp]: "((x ⊓ nc) ⋅ nc) ⋅ nc = (x ⊓ nc) ⋅ nc"
proof -
have "((x ⊓ nc) ⋅ nc) ⋅ nc = (d (x ⊓ nc) ⋅ nc) ⋅ nc"
by simp
also have "... = d (x ⊓ nc) ⋅ (nc ⋅ nc)"
by (metis cl11_d d_x_nc local.cl11 local.meet_idem nc_ccomp_closed_alt nc_nc)
also have "... = d (x ⊓ nc) ⋅ nc"
by auto
finally show ?thesis
by simp
qed
lemma nc_vec_add_closed: "((x ⊓ nc) ⋅ nc + (y ⊓ nc) ⋅ nc) ⋅ nc = (x ⊓ nc) ⋅ nc + (y ⊓ nc) ⋅ nc"
by (simp add: local.s_prod_distr)
lemma nc_vec_par_closed: "(((x ⊓ nc) ⋅ nc) ∥ ((y ⊓ nc) ⋅ nc)) ⋅ nc = ((x ⊓ nc) ⋅ nc) ∥ ((y ⊓ nc) ⋅ nc)"
by (simp add: local.cl4)
lemma nc_vec_par_is_meet:
assumes "⋀ x y z. (d x ⊓ d y) ⋅ z = d x ⋅ z ⊓ d y ⋅ z"
shows "((x ⊓ nc) ⋅ nc) ∥ ((y ⊓ nc) ⋅ nc) = ((x ⊓ nc) ⋅ nc) ⊓ ((y ⊓ nc) ⋅ nc)"
proof -
have "((x ⊓ nc) ⋅ nc) ∥ ((y ⊓ nc) ⋅ nc) = (d (x ⊓ nc) ⋅ nc) ∥ (d (y ⊓ nc) ⋅ nc)"
by auto
also have "... = (d (x ⊓ nc) ∥ d (y ⊓ nc)) ⋅ nc"
by (simp add: local.cl4)
also have "... = (d (x ⊓ nc) ⊓ d (y ⊓ nc)) ⋅ nc"
by (simp add: d_p_prod_eq_meet)
finally show ?thesis
by (simp add: assms)
qed
lemma nc_vec_meet_closed:
assumes "⋀ x y z. (d x ⊓ d y) ⋅ z = d x ⋅ z ⊓ d y ⋅ z"
shows "((x ⊓ nc) ⋅ nc ⊓ (y ⊓ nc) ⋅ nc) ⋅ nc = (x ⊓ nc) ⋅ nc ⊓ (y ⊓ nc) ⋅ nc"
proof -
have "((x ⊓ nc) ⋅ nc ⊓ (y ⊓ nc) ⋅ nc) ⋅ nc = (((x ⊓ nc) ⋅ nc) ∥ ((y ⊓ nc) ⋅ nc)) ⋅ nc"
by (simp add: assms nc_vec_par_is_meet)
also have "... = ((x ⊓ nc) ⋅ nc) ∥ ((y ⊓ nc) ⋅ nc)"
by (simp add: nc_vec_par_closed)
finally show ?thesis
by (simp add: assms nc_vec_par_is_meet)
qed
lemma nc_vec_seq_closed:
assumes "⋀x. x ⊓ nc ≠ 0 ⟹ nc ⋅ ((x ⊓ nc) ⋅ nc) = nc"
and "⋀x y z. d x ⋅ (y ⋅ z) = (d x ⋅ y) ⋅ z"
shows "(((x ⊓ nc) ⋅ nc) ⋅ ((y ⊓ nc) ⋅ nc)) ⋅ nc = ((x ⊓ nc) ⋅ nc) ⋅ ((y ⊓ nc) ⋅ nc)"
proof -
have one : "y ⊓ nc = 0 ⟹ (((x ⊓ nc) ⋅ nc) ⋅ ((y ⊓ nc) ⋅ nc)) ⋅ nc = ((x ⊓ nc) ⋅ nc) ⋅ ((y ⊓ nc) ⋅ nc)"
by simp
have "y ⊓ nc ≠ 0 ⟹ (((x ⊓ nc) ⋅ nc) ⋅ ((y ⊓ nc) ⋅ nc)) ⋅ nc = ((x ⊓ nc) ⋅ nc) ⋅ ((y ⊓ nc) ⋅ nc)"
by (simp add: assms(1) assms(2) tarski_prod)
thus ?thesis
using one by blast
qed
text ‹Proposition 10.1 and 10.2.›
lemma iso3 [simp]: "d (d x ⋅ U) = d x "
by simp
lemma iso4 [simp]: "d ((x ⋅ 1⇩π) ∥ U) ⋅ U = (x ⋅ 1⇩π) ∥ U"
by (simp add: local.c3 local.c4 vec_iff)
lemma iso5 [simp]: "((x ⋅ 1⇩π) ∥ U) ⋅ 1⇩π = x ⋅ 1⇩π"
by (simp add: local.c3 local.c4)
lemma iso6 [simp]: "(((x ⋅ 1⇩π) ∥ U) ⋅ 1⇩π) ∥ U = (x ⋅ 1⇩π) ∥ U"
by simp
lemma iso3_sharp [simp]: "d (d (x ⊓ nc) ⋅ nc) = d (x ⊓ nc)"
using d_s_subid local.c4 local.d_def local.inf_le1 by auto
lemma iso4_sharp [simp]: "d ((x ⊓ nc) ⋅ nc) ⋅ nc = (x ⊓ nc) ⋅ nc"
by (simp add: local.c2_d local.c4)
lemma iso5_sharp [simp]: "(((x ⊓ nc) ⋅ 1⇩π) ∥ nc) ⋅ 1⇩π = (x ⊓ nc) ⋅ 1⇩π"
by (simp add: local.c3 local.c4)
lemma iso6_sharp [simp]: "(((x ⊓ nc) ⋅ nc) ⋅ 1⇩π) ∥ nc = (x ⊓ nc) ⋅ nc"
using local.c4 local.cl11 nc_c by presburger
text‹We verify Lemma 15.2 at this point, because it is helpful for the following proofs.›
lemma uc_par_meet: "x ∥ U ⊓ y ∥ U = x ∥ U ∥ y ∥ U"
apply (rule order.antisym)
apply (metis local.c_prod_assoc meet_le_par)
by (metis U_idem_p_prod local.U_def local.c_prod_assoc local.meet_prop local.mult.left_commute local.mult_double_iso)
lemma uc_unc [simp]: "x ∥ U ∥ x ∥ U = x ∥ U"
by (metis local.meet_idem uc_par_meet)
lemma uc_interr: "(x ∥ y) ⋅ (z ∥ U) = (x ⋅ (z ∥ U)) ∥ (y ⋅ (z ∥ U))"
proof -
have "(z ∥ U) ∥ (z ∥ U) = z ∥ U"
by (metis local.c_prod_assoc uc_unc)
thus ?thesis
by (simp add: local.cl4)
qed
text‹We verify the remaining cases of Proposition 10.3.›
lemma sc_hom_meet: "(d x ⊓ d y) ⋅ 1⇩π = (d x) ⋅ 1⇩π ⊓ (d y) ⋅ 1⇩π"
by (metis d_p_prod_eq_meet local.c3 p_subid_par_eq_meet_var)
lemma sc_hom_seq: "(d x ⋅ d y) ⋅ 1⇩π = (d x ⊓ d y) ⋅ 1⇩π"
by (simp add: d_s_prod_eq_meet)
lemma cs_hom_meet: "d (x ⋅ 1⇩π ⊓ y ⋅ 1⇩π) = d (x ⋅ 1⇩π) ⊓ d (y ⋅ 1⇩π)"
by (metis d_p_prod_eq_meet local.d_conc6 p_subid_par_eq_meet_var)
lemma sv_hom_meet: "(d x ⊓ d y) ⋅ U = (d x) ⋅ U ⊓ (d y) ⋅ U"
proof -
have "(d x ⊓ d y) ⋅ U = ((d x) ⋅ U) ∥ ((d y) ⋅ U)"
by (simp add: d_interr_U d_p_prod_eq_meet local.d_conc6)
thus ?thesis
by (simp add: local.c2_d local.c_prod_assoc uc_par_meet)
qed
lemma sv_hom_par: "(x ∥ y) ⋅ U = (x ⋅ U) ∥ (y ⋅ U)"
by (simp add: local.cl4)
lemma vs_hom_meet: "d (((x ⋅ 1⇩π) ∥ U) ⊓ ((y ⋅ 1⇩π) ∥ U)) = d ((x ⋅ 1⇩π) ∥ U) ⊓ d ((y ⋅ 1⇩π) ∥ U)"
proof -
have f1: "⋀x y. x ⋅ 1⇩π ∥ 1⇩σ ⊓ y ⋅ 1⇩π ∥ 1⇩σ = x ∥ y ⋅ 1⇩π ∥ 1⇩σ"
using d_p_prod_eq_meet local.d_conc6 local.d_def by auto
hence "⋀x y. x ⋅ 1⇩π ∥ U ⊓ y ⋅ 1⇩π ∥ U = x ∥ y ⋅ 1⇩π ∥ U"
using local.d_def sv_hom_meet by force
thus ?thesis
using f1 by (simp add: local.d_def)
qed
lemma cv_hom_meet: "(x ⋅ 1⇩π ⊓ y ⋅ 1⇩π) ∥ U = (x ⋅ 1⇩π) ∥ U ⊓ (y ⋅ 1⇩π) ∥ U"
proof -
have "d (x ∥ y) ⋅ U = x ⋅ 1⇩π ∥ U ⊓ y ⋅ 1⇩π ∥ U"
by (simp add: d_p_prod_eq_meet local.c2_d local.d_conc6 sv_hom_meet)
thus ?thesis
using local.c2_d local.c3 p_subid_par_eq_meet_var by auto
qed
lemma cv_hom_par [simp]: " x ∥ U ∥ y ∥ U = (x ∥ y) ∥ U"
by (metis U_idem_p_prod local.mult.left_commute local.mult_assoc)
lemma vc_hom_meet: "((x ⋅ 1⇩π) ∥ U ⊓ (y ⋅ 1⇩π) ∥ U) ⋅ 1⇩π = ((x ⋅ 1⇩π) ∥ U) ⋅ 1⇩π ⊓ ((y ⋅ 1⇩π) ∥ U) ⋅ 1⇩π"
by (metis cv_hom_meet iso5 local.c3 p_subid_par_eq_meet_var)
lemma vc_hom_seq: "(((x ⋅ 1⇩π) ∥ U) ⋅ ((y ⋅ 1⇩π) ∥ U)) ⋅ 1⇩π = (((x ⋅ 1⇩π) ∥ U) ⋅ 1⇩π) ⋅ (((y ⋅ 1⇩π) ∥ U) ⋅ 1⇩π)"
proof -
have "(((x ⋅ 1⇩π) ∥ U) ⋅ ((y ⋅ 1⇩π) ∥ U)) ⋅ 1⇩π = ((x ⋅ 1⇩π) ∥ U) ⋅ (y ⋅ 1⇩π)"
by (simp add: local.c4)
also have "... = (x ⋅ 1⇩π) ∥ (U ⋅ (y ⋅ 1⇩π))"
by (metis assoc_p_subid local.cl8)
also have "... = (x ⋅ 1⇩π) ∥ (nc ⋅ (y ⋅ 1⇩π) + 1⇩π ⋅ (y ⋅ 1⇩π))"
by (metis add_commute c_nc_comp1 local.s_prod_distr)
also have "... = (x ⋅ 1⇩π) ∥ 1⇩π"
by (metis add_commute c_x_prop local.absorp2 local.c4 local.meet_comm local.mult_oner p_subid_par_eq_meet_var)
thus ?thesis
by (simp add: assoc_p_subid calculation)
qed
text ‹Proposition 10.4.›
lemma nsv_hom_meet: "(d x ⊓ d y) ⋅ nc = (d x) ⋅ nc ⊓ (d y) ⋅ nc"
proof (rule order.antisym)
have "(d x ⊓ d y) ⋅ nc ≤ (d x) ⋅ nc"
by (simp add: local.s_prod_isor)
hence "(d x ⊓ d y) ⋅ nc ≤ (d x) ⋅ nc"
by blast
thus "(d x ⊓ d y) ⋅ nc ≤ (d x) ⋅ nc ⊓ (d y) ⋅ nc"
by (simp add: local.s_prod_isor)
have "(d x) ⋅ nc ⊓ (d y) ⋅ nc ≤ ((d x) ⋅ nc) ∥ ((d y) ⋅ nc)"
by (simp add: meet_le_par)
also have "... = (d x ∥ d y) ⋅ nc"
by (metis local.cl4 nc_nc_par subidem_par)
finally show "(d x) ⋅ nc ⊓ (d y) ⋅ nc ≤ (d x ⊓ d y) ⋅ nc"
by (simp add: d_p_prod_eq_meet)
qed
lemma nsv_hom_par: "(x ∥ y) ⋅ nc = (x ⋅ nc) ∥ (y ⋅ nc)"
by (simp add: local.cl4)
lemma vec_p_prod_meet: "((x ⊓ nc) ⋅ nc) ∥ ((y ⊓ nc) ⋅ nc) = ((x ⊓ nc) ⋅ nc) ⊓ ((y ⊓ nc) ⋅ nc)"
proof -
have "((x ⊓ nc) ⋅ nc) ∥ ((y ⊓ nc) ⋅ nc) = (d (x ⊓ nc) ⋅ nc) ∥ (d (y ⊓ nc) ⋅ nc)"
by (metis cl11_d)
also have "... = (d (x ⊓ nc) ∥ d (y ⊓ nc)) ⋅ nc"
by (simp add: nsv_hom_par)
also have "... = (d (x ⊓ nc) ⊓ d (y ⊓ nc)) ⋅ nc"
by (simp add: d_p_prod_eq_meet)
also have "... = (d (x ⊓ nc) ⋅ nc) ⊓ (d (y ⊓ nc) ⋅ nc)"
by (simp add: nsv_hom_meet)
thus ?thesis
by (simp add: calculation)
qed
lemma nvs_hom_meet: "d (((x ⊓ nc) ⋅ nc) ⊓ ((y ⊓ nc) ⋅ nc)) = d ((x ⊓ nc) ⋅ nc) ⊓ d ((y ⊓ nc) ⋅ nc)"
by (metis d_p_prod_eq_meet local.d_conc6 vec_p_prod_meet)
lemma ncv_hom_meet: "(x ⋅ 1⇩π ⊓ y ⋅ 1⇩π) ∥ nc = (x ⋅ 1⇩π) ∥ nc ⊓ (y ⋅ 1⇩π) ∥ nc"
by (metis d_p_prod_eq_meet local.c2_d local.c3 local.d_conc6 nsv_hom_meet p_subid_par_eq_meet_var)
lemma ncv_hom_par: "(x ∥ y) ∥ nc = x ∥ nc ∥ y ∥ nc"
by (metis local.mult_assoc local.mult_commute nc_nc_par)
lemma nvc_hom_meet: "((x ⊓ nc) ⋅ nc ⊓ (y ⊓ nc) ⋅ nc) ⋅ 1⇩π = ((x ⊓ nc) ⋅ nc) ⋅ 1⇩π ⊓ ((y ⊓ nc) ⋅ nc) ⋅ 1⇩π"
by (metis local.c3 p_subid_par_eq_meet_var vec_p_prod_meet)
subsection ‹Terminal and Nonterminal Elements›
text ‹Now we define the projection functions on terminals and nonterminal parts and verify the properties
of Section 11 in~\<^cite>‹"FurusawaS15a"›.›
definition tau :: "'a ⇒ 'a" ("τ") where
"τ x = x ⋅ 0"
definition nu :: "'a ⇒ 'a" ("ν") where
"ν x = x ⊓ nc"
text ‹Lemma 11.1.›
lemma tau_int: "τ x ≤ x"
by (metis c_0 local.inf_le1 tau_def)
lemma nu_int: "ν x ≤ x"
by (simp add: nu_def)
lemma tau_ret [simp]: "τ (τ x) = τ x"
by (simp add: tau_def)
lemma nu_ret [simp]: "ν (ν x) = ν x"
by (simp add: local.meet_assoc nu_def)
lemma tau_iso: "x ≤ y ⟹ τ x ≤ τ y"
using local.order_prop local.s_prod_distr tau_def by auto
lemma nu_iso: "x ≤ y ⟹ ν x ≤ ν y"
using local.inf_mono nu_def by auto
text ‹Lemma 11.2.›
lemma tau_zero [simp]: "τ 0 = 0"
by (simp add: tau_def)
lemma nu_zero [simp]: "ν 0 = 0"
using nu_def by auto
lemma tau_s [simp]: "τ 1⇩σ = 0"
using tau_def by auto
lemma nu_s [simp]: "ν 1⇩σ = 1⇩σ"
using nu_def by auto
lemma tau_c [simp]: "τ 1⇩π = 1⇩π"
using c_x_prop tau_def by presburger
lemma nu_c [simp]: "ν 1⇩π = 0"
using c_nc_comp2 nu_def by presburger
lemma tau_nc [simp]: "τ nc = 0"
using nc_iff2 tau_def by auto
lemma nu_nc [simp]: "ν nc = nc"
using nu_def by auto
lemma tau_U [simp]: "τ U = 1⇩π"
using c_def tau_def by presburger
lemma nu_U [simp]: "ν U = nc"
using local.U_def local.meet_comm local.inf.absorb_iff1 nu_def by fastforce
text ‹Lemma 11.3.›
lemma tau_add [simp]: "τ (x + y) = τ x + τ y"
by (simp add: tau_def x_zero_add_closed)
lemma nu_add [simp]: "ν (x + y) = ν x + ν y"
by (simp add: local.lat_dist3 local.meet_comm nu_def)
lemma tau_meet [simp]: "τ (x ⊓ y) = τ x ⊓ τ y"
using tau_def x_zero_meet_closed by auto
lemma nu_meet [simp]: "ν (x ⊓ y) = ν x ⊓ ν y"
using nc_meet_closed nu_def by auto
lemma tau_seq: "τ (x ⋅ y) = τ x + ν x ⋅ τ y"
using local.add_comm nu_def tau_def x_y_split zero_assoc3 by presburger
lemma tau_par [simp]: "τ (x ∥ y) = τ x ∥ τ y"
using tau_def x_zero_interr by presburger
lemma nu_par_aux1: "x ∥ τ y = d (τ y) ⋅ x"
by (simp add: local.c2_d local.mult_commute tau_def)
lemma nu_par_aux2 [simp]: "ν (ν x ∥ ν y) = ν x ∥ ν y"
by (simp add: nu_def)
lemma nu_par_aux3 [simp]: "ν (ν x ∥ τ y) = ν x ∥ τ y"
by (metis local.mult_commute nc_ccomp_closed_alt nu_def)
lemma nu_par_aux4 [simp]: "ν (τ x ∥ τ y) = 0"
by (metis nu_def tau_def tau_par zero_nc)
lemma nu_par: "ν (x ∥ y) = d (τ x) ⋅ ν y + d (τ y) ⋅ ν x + ν x ∥ ν y"
proof -
have "ν (x ∥ y) = ν (ν x ∥ ν y) + ν (ν x ∥ τ y) + ν (τ x ∥ ν y) + ν (τ x ∥ τ y)"
by (metis local.distrib_left local.distrib_right nu_add nu_def tau_def x_split_var join.sup.commute join.sup.left_commute)
also have "ν (x ∥ y) = ν x ∥ ν y + ν x ∥ τ y + τ x ∥ ν y"
by (simp add: calculation local.c_prod_comm)
thus ?thesis
using local.join.sup_assoc local.join.sup_commute local.mult_commute nu_par_aux1 by auto
qed
text ‹Lemma 11.5.›
lemma sprod_tau_nu: "x ⋅ y = τ x + ν x ⋅ y"
by (metis local.add_comm nu_def tau_def x_y_split)
lemma pprod_tau_nu: "x ∥ y = ν x ∥ ν y + d (τ x) ⋅ ν y + d (τ y) ⋅ ν x + τ x ∥ τ y"
proof -
have "x ∥ y = ν (x ∥ y) + τ (x ∥ y)"
by (simp add: nu_def tau_def)
also have "... = (d (τ x) ⋅ ν y + d (τ y) ⋅ ν x + ν x ∥ ν y) + τ x ∥ τ y"
by (simp add: nu_par)
thus ?thesis
using add_assoc add_commute calculation by force
qed
text ‹We now verify some additional properties which are not mentioned in the paper.›
lemma tau_idem [simp]: "τ x ⋅ τ x = τ x"
by (simp add: tau_def)
lemma tau_interr: "(x ∥ y) ⋅ τ z = (x ⋅ τ z) ∥ (y ⋅ τ z)"
by (simp add: local.cl4 tau_def)
lemma tau_le_c: "τ x ≤ 1⇩π"
by (simp add: local.x_zero_le_c tau_def)
lemma c_le_tauc: "1⇩π ≤ τ 1⇩π"
using local.eq_refl tau_c by presburger
lemma x_alpha_tau [simp]: "ν x + τ x = x"
using nu_def tau_def x_split_var by presburger
lemma alpha_tau_zero [simp]: "ν (τ x) = 0"
by (simp add: nu_def tau_def)
lemma tau_alpha_zero [simp]: "τ (ν x) = 0"
by (simp add: nu_def tau_def)
lemma sprod_tau_nu_var [simp]: "ν (ν x ⋅ y) = ν (x ⋅ y)"
proof -
have "ν (x ⋅ y) = ν (τ x) + ν (ν x ⋅ y)"
by (metis nu_add sprod_tau_nu)
thus ?thesis
by simp
qed
lemma tau_s_prod [simp]: "τ (x ⋅ y) = x ⋅ τ y"
by (simp add: tau_def zero_assoc3)
lemma alpha_fp: "ν x = x ⟷ x ⋅ 0 = 0"
by (metis local.add_zeror tau_alpha_zero tau_def x_alpha_tau)
lemma alpha_prod_closed [simp]: "ν (ν x ⋅ ν y) = ν x ⋅ ν y"
by (simp add: nu_def)
lemma alpha_par_prod [simp]: "ν (x ∥ ν y) = x ∥ ν y"
by (simp add: nu_def)
lemma p_prod_tau_alpha: "x ∥ y = x ∥ ν y + ν x ∥ y + τ x ∥ τ y"
proof -
have "x ∥ y = (ν x + τ x) ∥ (ν y + τ y)"
using x_alpha_tau by simp
also have "... = ν x ∥ ν y + ν x ∥ τ y + τ x ∥ ν y + τ x ∥ τ y"
by (metis add_commute local.combine_common_factor local.p_prod_distl)
also have "... = (ν x ∥ ν y + ν x ∥ τ y) + (ν x ∥ ν y + τ x ∥ ν y) + τ x ∥ τ y"
by (simp add: add_ac)
thus ?thesis
by (metis calculation local.add_comm local.distrib_left local.distrib_right x_alpha_tau)
qed
lemma p_prod_tau_alpha_var: "x ∥ y = x ∥ ν y + ν x ∥ y + τ (x ∥ y)"
by (metis p_prod_tau_alpha tau_par)
lemma alpha_par: "ν (x ∥ y) = ν x ∥ y + x ∥ ν y"
proof -
have "ν (x ∥ y) = ν (x ∥ ν y) + ν (ν x ∥ y) + ν (τ (x ∥ y))"
by (metis nu_add p_prod_tau_alpha_var)
thus ?thesis
by (simp add: local.mult_commute add_ac)
qed
lemma alpha_tau [simp]: "ν (x ⋅ τ y) = 0"
by (metis alpha_tau_zero tau_s_prod)
lemma nu_par_prop: "ν x = x ⟹ ν (x ∥ y) = x ∥ y"
by (metis alpha_par_prod local.mult_commute)
lemma tau_seq_prop: "τ x = x ⟹ x ⋅ y = x"
by (metis local.cl6 tau_def)
lemma tau_seq_prop2: "τ y = y ⟹ τ (x ⋅ y) = x ⋅ y"
by auto
lemma d_nu: "ν (d x ⋅ y) = d x ⋅ ν y"
proof -
have "ν (d x ⋅ y) = ν ((x ⋅ 1⇩π) ∥ y)"
by (simp add: local.c2_d)
also have "... = d (τ (x ⋅ 1⇩π)) ⋅ ν y + d (τ y) ⋅ ν (x ⋅ 1⇩π) + ν (x ⋅ 1⇩π) ∥ ν y"
by (simp add: nu_par)
thus ?thesis
using alpha_par local.c2_d nu_def by force
qed
text ‹Lemma 11.6 and 11.7.›
lemma nu_ideal1: "⟦ν x = x; y ≤ x⟧ ⟹ ν y = y"
by (metis local.meet_prop local.inf.absorb_iff1 nu_def)
lemma tau_ideal1: "⟦τ x = x; y ≤ x⟧ ⟹ τ y = y"
by (metis local.dual_order.trans tau_def term_p_subid_var)
lemma nu_ideal2: "⟦ν x = x; ν y = y⟧ ⟹ ν (x + y) = x + y"
by (simp add: local.lat_dist3 local.meet_comm)
lemma tau_ideal2: "⟦τ x = x; τ y = y⟧ ⟹ τ (x + y) = x + y"
by simp
lemma tau_ideal3: "τ x = x ⟹ τ (x ⋅ y) = x ⋅ y"
by (simp add: tau_seq_prop)
text ‹We prove the precongruence properties of Lemma 11.9.›
lemma tau_add_precong: "τ x ≤ τ y ⟹ τ (x + z) ≤ τ (y + z)"
proof -
assume "τ x ≤ τ y"
hence "(x + y) ⋅ 0 = y ⋅ 0" using local.less_eq_def local.s_prod_distr tau_def
by auto
hence "(x + z + y) ⋅ 0 = (y + z) ⋅ 0"
by (metis (no_types) add_assoc add_commute local.s_prod_distr)
thus "τ (x + z) ≤ τ (y + z)" using local.order_prop local.s_prod_distr tau_def
by metis
qed
lemma tau_meet_precong: "τ x ≤ τ y ⟹ τ (x ⊓ z) ≤ τ (y ⊓ z)"
proof -
assume "τ x ≤ τ y"
hence "⋀z. (x ⊓ y ⊓ z) ⋅ 0 = (x ⊓ z) ⋅ 0"
by (metis local.le_iff_inf tau_def x_zero_meet_closed)
thus ?thesis
using local.inf_left_commute local.le_iff_inf local.meet_comm tau_def x_zero_meet_closed by fastforce
qed
lemma tau_par_precong: "τ x ≤ τ y ⟹ τ (x ∥ z) ≤ τ (y ∥ z)"
proof -
assume "τ x ≤ τ y"
hence "x ∥ z ⋅ 0 ≤ y ⋅ 0"
by (metis (no_types) local.dual_order.trans local.p_subid_lb1 tau_def tau_par)
thus "τ (x ∥ z) ≤ τ (y ∥ z)"
by (simp add: ‹τ x ≤ τ y› local.mult_isor)
qed
lemma tau_seq_precongl: "τ x ≤ τ y ⟹ τ (z ⋅ x) ≤ τ (z ⋅ y)"
by (simp add: local.s_prod_isol)
lemma nu_add_precong: "ν x ≤ ν y ⟹ ν (x + z) ≤ ν (y + z)"
proof -
assume "ν x ≤ ν y"
hence "ν x = ν x ⊓ ν y"
using local.inf.absorb_iff1 by auto
hence "∀a. ν (x + a) = ν (x + a) ⊓ ν (y + a)"
by (metis (no_types) local.lat_dist2 nu_add)
thus ?thesis
using local.inf.absorb_iff1 by presburger
qed
lemma nu_meet_precong: "ν x ≤ ν y ⟹ ν (x ⊓ z) ≤ ν (y ⊓ z)"
proof -
assume "ν x ≤ ν y"
hence "ν y = ν x + ν y"
using local.less_eq_def by auto
hence "ν (y ⊓ z) = ν (x ⊓ z) + ν (y ⊓ z)"
by (metis (no_types) local.lat_dist4 nu_meet)
thus ?thesis
using local.less_eq_def by presburger
qed
lemma nu_seq_precongr: "ν x ≤ ν y ⟹ ν (x ⋅ z) ≤ ν (y ⋅ z)"
proof -
assume a: "ν x ≤ ν y"
have "ν (x ⋅ z) = ν (ν x ⋅ z)"
by simp
also have "... ≤ ν (ν y ⋅ z)"
by (metis a local.less_eq_def local.s_prod_distr nu_iso)
thus ?thesis
by simp
qed
text‹We prove the congruence properties of Corollary~11.11.›
definition tcg :: "'a ⇒ 'a ⇒ bool" where
"tcg x y = (τ x ≤ τ y ∧ τ y ≤ τ x)"
definition ncg :: "'a ⇒ 'a ⇒ bool" where
"ncg x y = (ν x ≤ ν y ∧ ν y ≤ ν x)"
lemma tcg_refl: "tcg x x"
by (simp add: tcg_def)
lemma tcg_trans: "⟦tcg x y; tcg y z⟧ ⟹ tcg x z"
using tcg_def by force
lemma tcg_sym: "tcg x y ⟹ tcg y x"
by (simp add: tcg_def)
lemma ncg_refl: "ncg x x"
using ncg_def by blast
lemma ncg_trans: "⟦ncg x y; ncg y z⟧ ⟹ ncg x z"
using ncg_def by force
lemma ncg_sym: "ncg x y ⟹ ncg y x"
using ncg_def by auto
lemma tcg_alt: "tcg x y = (τ x = τ y)"
using tcg_def by auto
lemma ncg_alt: "ncg x y = (ν x = ν y)"
by (simp add: order.eq_iff ncg_def)
lemma tcg_add: "τ x = τ y ⟹ τ (x + z) = τ (y + z)"
by simp
lemma tcg_meet: "τ x = τ y ⟹ τ (x ⊓ z) = τ (y ⊓ z)"
by simp
lemma tcg_par: "τ x = τ y ⟹ τ (x ∥ z) = τ (y ∥ z)"
by simp
lemma tcg_seql: "τ x = τ y ⟹ τ (z ⋅ x) = τ (z ⋅ y)"
by simp
lemma ncg_add: "ν x = ν y ⟹ ν (x + z) = ν (y + z)"
by simp
lemma ncg_meet: "ν x = ν y ⟹ ν (x ⊓ z) = ν (y ⊓ z)"
by simp
lemma ncg_seqr: "ν x = ν y ⟹ ν (x ⋅ z) = ν (y ⋅ z)"
by (simp add: order.eq_iff nu_seq_precongr)
end
subsection ‹Powers in C-Algebras›
text ‹We define the power functions from Section~6 in~\<^cite>‹"FurusawaS15a"› after Lemma~12.4.›
context proto_dioid
begin
primrec p_power :: "'a ⇒ nat ⇒ 'a" where
"p_power x 0 = 1⇩σ" |
"p_power x (Suc n) = x ⋅ p_power x n"
primrec power_rd :: "'a ⇒ nat ⇒ 'a" where
"power_rd x 0 = 0" |
"power_rd x (Suc n) = 1⇩σ + x ⋅ power_rd x n"
primrec power_sq :: "'a ⇒ nat ⇒ 'a" where
"power_sq x 0 = 1⇩σ" |
"power_sq x (Suc n) = 1⇩σ + x ⋅ power_sq x n"
text ‹Lemma~12.5›
lemma power_rd_chain: "power_rd x n ≤ power_rd x (n + 1)"
by (induct n, simp, metis Suc_eq_plus1 local.add_comm local.add_iso local.s_prod_isol power_rd.simps(2))
lemma power_sq_chain: "power_sq x n ≤ power_sq x (n + 1)"
by (induct n, clarsimp, metis Suc_eq_plus1 local.add_comm local.add_iso local.s_prod_isol power_sq.simps(2))
lemma pow_chain: "p_power (1⇩σ + x) n ≤ p_power (1⇩σ + x) (n + 1)"
by (induct n, simp, metis Suc_eq_plus1 local.p_power.simps(2) local.s_prod_isol)
lemma pow_prop: "p_power (1⇩σ + x) (n + 1) = 1⇩σ + x ⋅ p_power (1⇩σ + x) n"
proof (induct n)
case 0
show ?case by simp
next
case (Suc n)
have f1: "p_power (1⇩σ + x) (Suc n + 1) = 1⇩σ + x ⋅ p_power (1⇩σ + x) n + x ⋅ p_power (1⇩σ + x) (n + 1)"
proof -
have "p_power (1⇩σ + x) (Suc (n + 1)) = (1⇩σ + x) ⋅ p_power (1⇩σ + x) (n + 1)"
using local.p_power.simps(2) by blast
also have "... = p_power (1⇩σ + x) (n + 1) + x ⋅ p_power (1⇩σ + x) (n + 1)"
by (metis local.s_prod_distr local.s_prod_idl)
also have "... = 1⇩σ + x ⋅ p_power (1⇩σ + x) n + x ⋅ p_power (1⇩σ + x) (n + 1)"
using Suc.hyps by auto
finally show ?thesis
by simp
qed
have "x ⋅ p_power (1⇩σ + x) (Suc n) = x ⋅ p_power (1⇩σ + x) n + x ⋅ p_power (1⇩σ + x) (n + 1)"
using Suc_eq_plus1 local.less_eq_def local.s_prod_isol pow_chain by simp
with f1 show ?case by (simp add: add_ac)
qed
text ‹Next we verify facts from the proofs of Lemma~12.6.›
lemma power_rd_le_sq: "power_rd x n ≤ power_sq x n"
by (induct n, simp, simp add: local.join.le_supI2 local.s_prod_isol)
lemma power_sq_le_rd: "power_sq x n ≤ power_rd x (Suc n)"
by (induct n, simp, simp add: local.join.le_supI2 local.s_prod_isol)
lemma power_sq_power: "power_sq x n = p_power (1⇩σ + x) n"
apply (induct n)
apply (simp)
using Suc_eq_plus1 pow_prop power_sq.simps(2) by simp
end
subsection ‹C-Kleene Algebras›
text ‹The definition of c-Kleene algebra is slightly different from that in Section~6
of~\<^cite>‹"FurusawaS15a"›. It is used to prove properties from Section~6 and Section~12.›
class c_kleene_algebra = c_lattice + star_op +
assumes star_unfold: "1⇩σ + x ⋅ x⇧⋆ ≤ x⇧⋆"
and star_induct: "1⇩σ + x ⋅ y ≤ y ⟹ x⇧⋆ ≤ y"
begin
lemma star_irr: "1⇩σ ≤ x⇧⋆"
using local.star_unfold by auto
lemma star_unfold_part: "x ⋅ x⇧⋆ ≤ x⇧⋆"
using local.star_unfold by auto
lemma star_ext_aux: "x ≤ x ⋅ x⇧⋆"
using local.s_prod_isol star_irr by fastforce
lemma star_ext: "x ≤ x⇧⋆"
using local.order_trans star_ext_aux star_unfold_part by blast
lemma star_co_trans: "x⇧⋆ ≤ x⇧⋆ ⋅ x⇧⋆"
using local.s_prod_isol star_irr by fastforce
lemma star_iso: "x ≤ y ⟹ x⇧⋆ ≤ y⇧⋆"
proof -
assume a1: "x ≤ y"
have f2: "y ⋅ y⇧⋆ + y⇧⋆ = y⇧⋆"
by (meson local.less_eq_def star_unfold_part)
have "x + y = y"
using a1 by (meson local.less_eq_def)
hence "x ⋅ y⇧⋆ + y⇧⋆ = y⇧⋆"
using f2 by (metis (no_types) local.add_assoc' local.s_prod_distr)
thus ?thesis
using local.add_assoc' local.less_eq_def local.star_induct star_irr by presburger
qed
lemma star_unfold_eq [simp]: "1⇩σ + x ⋅ x⇧⋆ = x⇧⋆"
proof (rule order.antisym)
show a: "1⇩σ + x ⋅ x⇧⋆ ≤ x⇧⋆"
using local.star_unfold by blast
have "1⇩σ + x ⋅ (1⇩σ + x ⋅ x⇧⋆) ≤ 1⇩σ + x ⋅ x⇧⋆"
by (meson local.eq_refl local.join.sup_mono local.s_prod_isol local.star_unfold)
thus "x⇧⋆ ≤ 1⇩σ + x ⋅ x⇧⋆"
by (simp add: local.star_induct)
qed
text ‹Lemma 12.2.›
lemma nu_star1:
assumes "⋀x y z. x ⋅ (y ⋅ z) = (x ⋅ y) ⋅ z"
shows "x⇧⋆ ≤ (ν x)⇧⋆ ⋅ (1⇩σ + τ x)"
proof -
have "1⇩σ + x ⋅ ((ν x)⇧⋆ ⋅ (1⇩σ + τ x)) = 1⇩σ + τ x + ν x ⋅ ((ν x)⇧⋆ ⋅ (1⇩σ + τ x))"
by (metis add_assoc local.sprod_tau_nu)
also have "... = (1⇩σ + ν x ⋅ (ν x)⇧⋆) ⋅ (1⇩σ + τ x)"
using assms local.s_prod_distr local.s_prod_idl by presburger
also have "... ≤ (ν x)⇧⋆ ⋅ (1⇩σ + τ x)"
using local.s_prod_isor local.star_unfold by auto
thus ?thesis
by (simp add: calculation local.star_induct)
qed
lemma nu_star2:
assumes "⋀x. x⇧⋆ ⋅ x⇧⋆ ≤ x⇧⋆"
shows "(ν x)⇧⋆ ⋅ (1⇩σ + τ x) ≤ x⇧⋆"
proof -
have "(ν x)⇧⋆ ⋅ (1⇩σ + τ x) ≤ x⇧⋆ ⋅ (1⇩σ + τ x)"
using local.nu_int local.s_prod_isor star_iso by blast
also have "... ≤ x⇧⋆ ⋅ (1⇩σ + x)"
using local.s_prod_isol local.join.sup_mono local.tau_int by blast
also have "... ≤ x⇧⋆ ⋅ x⇧⋆"
by (simp add: local.s_prod_isol star_ext star_irr)
finally show ?thesis
using assms local.order_trans by blast
qed
lemma nu_star:
assumes "⋀x. x⇧⋆ ⋅ x⇧⋆ ≤ x⇧⋆"
and "⋀x y z. x ⋅ (y ⋅ z) = (x ⋅ y) ⋅ z"
shows "(ν x)⇧⋆ ⋅ (1⇩σ + τ x) = x⇧⋆"
by (simp add: assms(1) assms(2) local.dual_order.antisym nu_star1 nu_star2)
text ‹Lemma 12.3.›
lemma tau_star: "(τ x)⇧⋆ = 1⇩σ + τ x"
by (metis local.cl6 local.tau_def star_unfold_eq)
lemma tau_star_var:
assumes "⋀x y z. x ⋅ (y ⋅ z) = (x ⋅ y) ⋅ z"
and "⋀x. x⇧⋆ ⋅ x⇧⋆ ≤ x⇧⋆"
shows "τ (x⇧⋆) = (ν x)⇧⋆ ⋅ τ x"
by (metis (no_types, lifting) assms(1) assms(2) local.add_0_right local.add_comm local.s_prod_distr local.s_prod_idl local.tau_def local.tau_zero nu_star)
lemma nu_star_sub: "(ν x)⇧⋆ ≤ ν (x⇧⋆)"
by (metis add_commute local.less_eq_def local.meet_prop local.nc_nc local.nu_def local.order.refl local.s_le_nc local.star_induct star_iso)
lemma nu_star_nu [simp]: "ν ((ν x)⇧⋆) = (ν x)⇧⋆"
using local.nu_ideal1 local.nu_ret nu_star_sub by blast
lemma nu_star_tau [simp]: "ν ((τ x)⇧⋆) = 1⇩σ"
using tau_star by fastforce
lemma tau_star_tau [simp]: "τ ((τ x)⇧⋆) = τ x"
using local.s_prod_distr tau_star by auto
lemma tau_star_nu [simp]: "τ ((ν x)⇧⋆) = 0"
using local.alpha_fp local.tau_def nu_star_nu by presburger
text ‹Finally we verify Lemma 6.2. Proofs can be found in~\<^cite>‹"FurusawaS15b"›.›
lemma d_star_unfold [simp]:
assumes "⋀x y z. (x ⋅ y) ⋅ d z = x ⋅ (y ⋅ d z)"
shows "d y + d (x ⋅ d (x⇧⋆ ⋅ y)) = d (x⇧⋆ ⋅ y)"
proof -
have "d y + d (x ⋅ d (x⇧⋆ ⋅ y)) = d y + d (x ⋅ (x⇧⋆ ⋅ d y))"
by (metis local.c4 local.d_def local.dc_prop1)
moreover have "... = d (1⇩σ ⋅ d y + (x ⋅ (x⇧⋆ ⋅ d y)))"
by (simp add: local.d_add_ax)
moreover have "... = d (1⇩σ ⋅ d y + (x ⋅ x⇧⋆) ⋅ d y)"
by (simp add: assms)
moreover have "... = d ((1⇩σ + x ⋅ x⇧⋆) ⋅ d y)"
using local.s_prod_distr by presburger
ultimately show ?thesis
by simp
qed
lemma d_star_sim1:
assumes "⋀ x y z. d z + x ⋅ y ≤ y ⟹ x⇧⋆ ⋅ d z ≤ y"
and "⋀ x y z. (x ⋅ d y) ⋅ z = x ⋅ (d y ⋅ z)"
and "⋀ x y z. (d x ⋅ y) ⋅ z = d x ⋅ (y ⋅ z)"
shows "x ⋅ d z ≤ d z ⋅ y ⟹ x⇧⋆ ⋅ d z ≤ d z ⋅ y⇧⋆"
proof -
fix x y z
assume a: "x ⋅ d z ≤ d z ⋅ y"
have b: "x ⋅ (d z ⋅ y⇧⋆) ≤ d z ⋅ (y ⋅ y⇧⋆)"
by (metis a assms(2) assms(3) local.s_prod_isor)
hence "x ⋅ (d z ⋅ y⇧⋆) ≤ d z ⋅ y⇧⋆"
proof -
have f1: "x ⋅ (y⇧⋆ ∥ (z ⋅ 1⇩π)) ≤ z ⋅ 1⇩π ∥ (y ⋅ y⇧⋆)"
using b local.c2_d local.mult_commute by auto
have "∃a. (a + z ⋅ 1⇩π) ∥ (y ⋅ y⇧⋆) ≤ y⇧⋆ ∥ (z ⋅ 1⇩π)"
by (metis (no_types) local.eq_refl local.mult_commute local.mult_isol_var local.join.sup_idem star_unfold_part)
hence "x ⋅ (y⇧⋆ ∥ (z ⋅ 1⇩π)) ≤ y⇧⋆ ∥ (z ⋅ 1⇩π)"
using f1 by (metis (no_types) local.distrib_right' local.dual_order.trans local.join.sup.cobounded2)
thus ?thesis
using local.c2_d local.mult_commute by auto
qed
hence "d z + x ⋅ (d z ⋅ y⇧⋆)≤ d z ⋅ y⇧⋆"
using local.s_prod_isol star_irr by fastforce
thus "x⇧⋆ ⋅ d z ≤ d z ⋅ y⇧⋆"
using assms(1) by force
qed
lemma d_star_induct:
assumes "⋀ x y z. d z + x ⋅ y ≤ y ⟹ x⇧⋆ ⋅ d z ≤ y"
and "⋀ x y z. (x ⋅ d y) ⋅ z = x ⋅ (d y ⋅ z)"
and "⋀ x y z. (d x ⋅ y) ⋅ z = d x ⋅ (y ⋅ z)"
shows "d (x ⋅ y) ≤ d y ⟹ d (x⇧⋆ ⋅ y) ≤ d y"
proof -
fix x y
assume "d (x ⋅ y) ≤ d y"
hence "x ⋅ d y ≤ d y ⋅ x"
by (simp add: demod1)
hence "x⇧⋆ ⋅ d y ≤ d y ⋅ x⇧⋆"
using assms(1) assms(2) assms(3) d_star_sim1 by blast
thus "d (x⇧⋆ ⋅ y) ≤ d y"
by (simp add: demod2)
qed
end
subsection ‹C-Omega Algebras›
text ‹These structures do not feature in~\<^cite>‹"FurusawaS15a"›, but in fact,
many lemmas from Section 13 can be proved in this setting. The proto-quantales and c-quantales
using in~\<^cite>‹"FurusawaS15a"› provide a more expressive setting in which least and greatest fixpoints
need not be postulated; they exists due to properties of sequential composition and addition over
complete lattices.›
class c_omega_algebra = c_kleene_algebra + omega_op +
assumes om_unfold: "x⇧ω ≤ x ⋅ x⇧ω"
and om_coinduct: "y ≤ x ⋅ y ⟹ y ≤ x⇧ω"
begin
text ‹Lemma 13.4.›
lemma om_unfold_eq [simp]: "x ⋅ x⇧ω = x⇧ω"
apply (rule order.antisym)
using local.om_coinduct local.om_unfold local.s_prod_isol by auto
lemma om_iso: "x ≤ y ⟹ x⇧ω ≤ y⇧ω"
by (metis local.om_coinduct local.s_prod_isor om_unfold_eq)
text ‹Lemma 13.5.›
lemma zero_om [simp]: "0⇧ω = 0"
by (metis local.s_prod_annil om_unfold_eq)
lemma s_id_om [simp]: "1⇩σ⇧ω = U"
by (simp add: local.U_def order.eq_iff local.om_coinduct)
lemma p_id_om [simp]: "1⇩π⇧ω = 1⇩π"
by (metis local.c_x_prop om_unfold_eq)
lemma nc_om [simp]: "nc⇧ω = U"
using local.U_def order.eq_iff local.s_le_nc om_iso s_id_om by blast
lemma U_om [simp]: "U⇧ω = U"
by (simp add: local.U_def order.eq_iff local.om_coinduct)
text ‹Lemma 13.6.›
lemma tau_om1: "τ x ≤ τ (x⇧ω)"
using local.om_coinduct local.s_prod_isor local.tau_def local.tau_int by fastforce
lemma tau_om2 [simp]: "τ x⇧ω = τ x"
by (metis local.cl6 local.tau_def om_unfold_eq)
lemma tau_om3: "(τ x)⇧ω ≤ τ (x⇧ω)"
by (simp add: tau_om1)
text ‹Lemma 13.7.›
lemma om_nu_tau: "(ν x)⇧ω + (ν x)⇧⋆ ⋅ τ x ≤ x⇧ω"
proof -
have "(ν x)⇧ω + (ν x)⇧⋆ ⋅ τ x = (ν x)⇧ω + (1⇩σ + ν x ⋅ (ν x)⇧⋆) ⋅ τ x"
by auto
also have "... = (ν x)⇧ω + τ x + ν x ⋅ (ν x)⇧⋆ ⋅ τ x"
using add_assoc local.s_prod_distr local.s_prod_idl by presburger
also have "... = τ x + ν x ⋅ (ν x)⇧ω + ν x ⋅ (ν x)⇧⋆ ⋅ τ x"
by (simp add: add_ac)
also have "... ≤ τ x + ν x ⋅ ((ν x)⇧ω + (ν x)⇧⋆ ⋅ τ x)"
by (metis add_assoc local.cl5 local.lat_dist1 local.inf.absorb_iff1 local.s_prod_subdistl local.tau_def)
also have "... = x ⋅ ((ν x)⇧ω + (ν x)⇧⋆ ⋅ τ x)"
by (metis local.sprod_tau_nu)
finally show ?thesis
using local.om_coinduct by blast
qed
end
subsection ‹C-Nabla Algebras›
text ‹Nabla-algebras provide yet another way of formalising non-terminating behaviour in Section 13.›
class c_nabla_algebra = c_omega_algebra +
fixes nabla :: "'a ⇒ 'a" ("∇")
assumes nabla_unfold: "∇ x ≤ d (x ⋅ ∇ x)"
and nabla_coinduct: "d y ≤ d (x ⋅ y) ⟹ d y ≤ ∇ x"
begin
lemma nabla_unfold_eq [simp]: "∇ x = d (x ⋅ ∇ x)"
proof (rule order.antisym)
show "∇ x ≤ d (x ⋅ ∇ x)"
using local.nabla_unfold by blast
have "d (x ⋅ ∇ x) ≤ d (x ⋅ d (x ⋅ ∇ x))"
by (metis local.d_def local.mult_commute local.mult_isol local.nabla_unfold local.s_prod_isol local.s_prod_isor)
also have "... = d (x ⋅ (x ⋅ ∇ x))"
using local.d_loc_ax by blast
finally show "d (x ⋅ ∇ x) ≤ ∇ x"
by (simp add: local.nabla_coinduct)
qed
lemma nabla_le_s: "∇ x ≤ 1⇩σ"
by (metis local.d_sub_id_ax nabla_unfold_eq)
lemma nabla_nu [simp]: "ν (∇ x) = ∇ x"
using local.nu_ideal1 local.nu_s nabla_le_s by blast
text ‹Proposition 13.9.›
lemma nabla_omega_U:
assumes "⋀x y z. x ⋅ (d y ⋅ z) = (x ⋅ d y ) ⋅ z"
shows "(ν x)⇧ω = ∇ (ν x) ⋅ U"
proof (rule order.antisym)
have "d ((ν x)⇧ω) ≤ ∇ (ν x)"
using local.nabla_coinduct local.om_unfold_eq local.order_refl by presburger
hence "(ν x)⇧ω ≤ ∇ (ν x) ⋅ (ν x)⇧ω"
using local.dlp_ax local.dual_order.trans local.s_prod_isor by blast
thus "(ν x)⇧ω ≤ ∇ (ν x) ⋅ U"
using local.U_def local.dual_order.trans local.s_prod_isol by blast
have "ν x ⋅ (∇ (ν x) ⋅ U) = (ν x ⋅ d (∇ (ν x))) ⋅ U"
by (metis assms local.d_s_subid nabla_le_s)
also have "... = (ν (ν x ⋅ ν (∇ (ν x)))) ⋅ U"
by (metis local.d_s_subid nabla_le_s nabla_nu local.alpha_prod_closed)
also have "... = d (ν (ν x ⋅ ν (∇ (ν x)))) ⋅ U"
using local.ax5_d local.nu_def by presburger
also have "... = d (ν x ⋅ ∇ (ν x)) ⋅ U"
by (metis local.alpha_prod_closed nabla_nu)
finally show "∇ (ν x) ⋅ U ≤ (ν x)⇧ω"
using local.nabla_unfold local.om_coinduct local.s_prod_isor by presburger
qed
text ‹Corollary 13.10.›
lemma nabla_omega_U_cor:
assumes "⋀x y z. x ⋅ (d y ⋅ z) = (x ⋅ d y ) ⋅ z"
shows "∇ (ν x) ⋅ U + (ν x)⇧⋆ ⋅ τ x ≤ x⇧ω"
by (metis assms nabla_omega_U local.om_nu_tau)
text ‹Lemma 13.11.›
lemma nu_om_nu:
assumes "⋀x y z. x ⋅ (d y ⋅ z) = (x ⋅ d y ) ⋅ z"
shows "ν ((ν x)⇧ω) = ∇ (ν x) ⋅ nc"
proof -
have "ν ((ν x)⇧ω) = ν (∇ (ν x) ⋅ U)"
using assms nabla_omega_U by presburger
also have "... = ν (d (∇ (ν x)) ⋅ U)"
by (metis local.d_s_subid nabla_le_s)
also have "... = (∇ (ν x)) ⋅ ν U"
by (metis local.d_nu local.d_s_subid nabla_le_s)
finally show ?thesis
using local.nu_U by presburger
qed
lemma tau_om_nu:
assumes "⋀x y z. x ⋅ (d y ⋅ z) = (x ⋅ d y ) ⋅ z"
shows "τ ((ν x)⇧ω) = ∇ (ν x) ⋅ 1⇩π"
proof -
have "τ ((ν x)⇧ω) = τ (∇ (ν x) ⋅ U)"
by (metis assms nabla_omega_U)
also have "... = ∇ (ν x) ⋅ τ U"
using local.tau_s_prod by blast
finally show ?thesis
using local.tau_U by blast
qed
text ‹Proposition 13.12.›
lemma wf_eq_defl: "(∀y. d y ≤ d (x ⋅ y) ⟶ d y = 0) ⟷ (∀y. y ≤ x ⋅ y ⟶ y = 0)"
apply standard
apply (metis local.d_add_ax local.d_rest_ax local.less_eq_def local.s_prod_annil)
by (metis local.c2_d local.c4 local.d_def local.mult_commute local.mult_onel local.p_rpd_annir local.s_prod_isor)
lemma defl_eq_om_trivial: "x⇧ω = 0 ⟷ (∀y. y ≤ x ⋅ y ⟶ y = 0)"
using local.join.bot_unique local.om_coinduct by auto
lemma wf_eq_om_trivial: "x⇧ω = 0 ⟷ (∀y. d y ≤ d (x ⋅ y) ⟶ d y = 0)"
by (simp add: defl_eq_om_trivial wf_eq_defl)
end
subsection ‹Proto-Quantales›
text ‹Finally we define the class of proto-quantales and prove some of the
remaining facts from the article. Full c-quantales, as defined there, are not needed
for these proofs.›
class proto_quantale = complete_lattice + proto_monoid +
assumes Sup_mult_distr: "Sup X ⋅ y = Sup {x ⋅ y | x. x ∈ X}"
and isol: "x ≤ y ⟹ z ⋅ x ≤ z ⋅ y"
begin