Theory Multirelations

(*
Title: Binary Multirelations
Author: Hitoshi Furusawa, Georg Struth
Maintainer: <g.struth at sheffield.ac.uk>
*)

section ‹Multirelations›

theory Multirelations
imports C_Algebras
begin

subsection ‹Basic Definitions›

text ‹We define a type synonym for multirelations.›

type_synonym 'a mrel = "('a * ('a set)) set"

no_notation  s_prod (infixl "⋅" 80)
no_notation s_id ("1⇩σ")
no_notation c_prod (infixl "∥" 80)
no_notation c_id ("1⇩π")

text ‹Now we start with formalising the multirelational model. First
  we define  sequential composition and paraellel composition of multirelations, their units and 
the universal multirelation as in Section 2 of the article.›

definition s_prod :: "'a mrel ⇒ 'a mrel ⇒ 'a mrel" (infixl "⋅" 70) where
  "R ⋅ S = {(a,A). (∃B. (a,B) ∈ R ∧ (∃f. (∀b ∈ B. (b,f b) ∈ S) ∧ A = ⋃{f b |b. b ∈ B}))}"

definition s_id :: "'a mrel" ("1⇩σ") where
  "1⇩σ ≡ ⋃a. {(a,{a})}"

definition p_prod :: "'a mrel ⇒ 'a mrel ⇒ 'a mrel"  (infixl "∥" 70) where
  "R ∥ S = {(a,A). (∃B C. A = B ∪ C ∧ (a,B) ∈ R ∧ (a,C) ∈ S)}"
 
definition p_id :: "'a mrel" ("1⇩π") where
  "1⇩π ≡ ⋃a. {(a,{})}"

definition U :: "'a mrel" where 
  "U ≡ {(a,A) |a A. a ∈ UNIV ∧ A ⊆ UNIV}"

abbreviation "NC ≡ U - 1⇩π"

text ‹We write NC where $\overline{1_\pi}$ is written in~\<^cite>‹"FurusawaS15a"›.›

text ‹Next we prove some basic set-theoretic properties.›

lemma s_prod_im: "R ⋅ S = {(a,A). (∃B. (a,B) ∈ R ∧ (∃f. (∀b ∈ B. (b,f b) ∈ S) ∧ A = ⋃((λx. f x) ` B)))}"
  by (auto simp: s_prod_def)

lemma s_prod_iff: "(a,A) ∈ (R ⋅ S) ⟷ (∃B. (a,B) ∈ R ∧ (∃f. (∀b ∈ B. (b,f b) ∈ S) ∧ A = ⋃((λx. f x) ` B)))"
  by (unfold s_prod_im, auto)

lemma s_id_iff: "(a,A) ∈ 1⇩σ ⟷ A = {a}"
  by (simp add: s_id_def)

lemma p_prod_iff: "(a,A) ∈ R ∥ S ⟷ (∃B C. A = B ∪ C ∧ (a,B) ∈ R ∧ (a,C) ∈ S)"
  by (clarsimp simp add: p_prod_def)

named_theorems mr_simp
declare s_prod_im [mr_simp] p_prod_def [mr_simp] s_id_def [mr_simp] p_id_def [mr_simp] U_def [mr_simp]

subsection‹Multirelations and Proto-Dioids›

text ‹We can now show that multirelations form proto-trioids. 
This is Proposition 5.1, and it subsumes Proposition 4.1,›

interpretation mrel_proto_trioid: proto_trioid "1⇩σ" "(⋅)" "1⇩π" "(∥)" "(∪)" "(⊆)" "(⊂)" "{}"
proof 
  show "⋀x. 1⇩σ ⋅ x = x"
    by (auto simp: mr_simp)
  show "⋀x. x ⋅ 1⇩σ = x"
    by (auto simp add: mr_simp) (metis UN_singleton)
  show "⋀x. 1⇩π ∥ x = x"
    by (simp add: mr_simp)
  show "⋀x y z. x ∥ y ∥ z = x ∥ (y ∥ z)"
    apply (rule antisym)
    apply (clarsimp simp: mr_simp Un_assoc, metis) 
    by (clarsimp simp: mr_simp, metis (no_types) Un_assoc)
  show "⋀x y. x ∥ y = y ∥ x"
    by  (auto simp: mr_simp)
  show "⋀x y. (x ⊆ y) = (x ∪ y = y)"
    by blast
  show "⋀x y. (x ⊂ y) = (x ⊆ y ∧ x ≠ y)"
    by (simp add: psubset_eq)
  show "⋀x y z. x ∪ y ∪ z = x ∪ (y ∪ z)"
    by (simp add: Un_assoc)
  show "⋀x y. x ∪ y = y ∪ x"
    by blast
  show "⋀x. x ∪ x = x"
    by auto
  show "⋀x. {} ∪ x = x"
    by blast
  show "⋀x y z. (x ∪ y) ⋅ z = x ⋅ z ∪ y ⋅ z"
    by (auto simp: mr_simp)
  show "⋀x y z. x ⋅ y ∪ x ⋅ z ⊆ x ⋅ (y ∪ z)"
    by (auto simp: mr_simp)
  show "⋀x. {} ⋅ x = {}"
    by (auto simp: mr_simp)
  show "⋀x y z. x ∥ (y ∪ z) = x ∥ y ∪ x ∥ z"
    by (auto simp: mr_simp)
  show "⋀x. x ∥ {} = {}"
    by (simp add: mr_simp)
qed

subsection ‹Simple Properties›

text‹This covers all the identities in the display before Lemma 2.1  except the two following ones.›

lemma s_prod_assoc1: "(R ⋅ S ) ⋅ T ⊆ R ⋅ (S ⋅ T)"
  by (clarsimp simp: mr_simp, metis)

lemma seq_conc_subdistr: "(R ∥ S) ⋅ T ⊆ (R ⋅ T) ∥ (S ⋅ T)"
  by (clarsimp simp: mr_simp UnI1 UnI2, blast)

text ‹Next we provide some counterexamples. These do not feature in~\<^cite>‹"FurusawaS15a"›.›

lemma  "R ⋅ {} = {}"
  nitpick 
  oops

lemma "R ⋅ (S ∪ T) = R ⋅ S ∪ R ⋅ T"
  apply (auto simp: s_prod_im)
  nitpick
  oops

lemma "R ⋅ (S ⋅ T) ⊆ (R ⋅ S) ⋅ T"
  apply (auto simp: s_prod_im)
  nitpick
  oops

lemma "(R ∥ R) ⋅ T = (R ⋅ T) ∥ (R ⋅ T)"
  quickcheck 
  oops

text ‹Next we prove the distributivity and associativity laws for sequential subidentities 
mentioned before Lemma 2.1›   

lemma subid_aux2: 
assumes "R ⊆ 1⇩σ"and "(a,A) ∈ R"
shows "A = {a}"
  using assms by (auto simp: mr_simp)

lemma s_prod_test_aux1: 
assumes "S ⊆ 1⇩σ"
and  "(a,A) ∈ R ⋅ S"
shows "((a,A) ∈ R ∧ (∀a ∈ A. (a,{a}) ∈ S))" 
  using assms apply (clarsimp simp: s_prod_im)
  by (metis assms(2) mrel_proto_trioid.s_prod_idr mrel_proto_trioid.s_prod_isol singletonD subid_aux2 subset_eq)

lemma s_prod_test_aux2: 
assumes "(a,A) ∈ R"
and "∀a ∈ A. (a,{a}) ∈ S"
shows "(a,A) ∈ R ⋅ S"
  using assms by (auto simp: mr_simp, fastforce)

lemma s_prod_test: 
assumes "P ⊆ 1⇩σ"
shows "(a,A) ∈ R ⋅ P ⟷ (a,A) ∈ R ∧ (∀a ∈ A. (a,{a}) ∈ P)"
  by (meson assms s_prod_test_aux1 s_prod_test_aux2) 

lemma test_s_prod_aux1: 
assumes "P ⊆  1⇩σ" 
and "(a,A) ∈ P ⋅ R"
shows "(a,{a}) ∈ P ∧ (a,A) ∈ R" 
  by (metis assms mrel_proto_trioid.s_prod_idl s_id_iff s_prod_iff subid_aux2)
  
lemma test_s_prod_aux2: 
assumes "(a,A) ∈ R" 
and "(a,{a}) ∈ P"
shows "(a,A) ∈ P ⋅ R"
  using assms s_prod_iff by fastforce

lemma test_s_prod: 
assumes "P ⊆ 1⇩σ"
shows "(a,A) ∈ P ⋅ R ⟷ (a,{a}) ∈ P ∧ (a,A) ∈ R"
  by (meson assms test_s_prod_aux1 test_s_prod_aux2)

lemma test_assoc1: 
assumes "P ⊆ 1⇩σ"
shows "(R ⋅ P) ⋅ S = R ⋅ (P ⋅ S)"
proof (rule antisym)
  show  "(R ⋅ P) ⋅ S ⊆ R ⋅ (P ⋅ S)"
    by (metis s_prod_assoc1)
next
  show "R ⋅ (P ⋅ S) ⊆ (R ⋅ P) ⋅ S" using assms
  proof clarify
    fix a A
    assume "(a,A) ∈ R ⋅ (P ⋅ S)"
    hence "∃B.(a,B) ∈ R ∧ (∃f. (∀b ∈ B. (b,f b) ∈ P ⋅ S) ∧ A = ⋃((λx. f x) ` B))" 
      by (clarsimp simp: mr_simp)
    hence "∃B.(a,B) ∈ R ∧ (∃f. (∀b ∈ B. (b,{b}) ∈ P ∧ (b,f b) ∈ S) ∧ A = ⋃((λx. f x) ` B))" 
      by (metis assms test_s_prod)
    hence "∃B.(a,B) ∈ R ∧ (∀b ∈ B. (b,{b}) ∈ P) ∧ (∃f. (∀b ∈ B. (b,f b) ∈ S) ∧ A = ⋃((λx. f x) ` B))"  
      by auto
    hence "∃B. (a,B) ∈ R ⋅ P ∧ (∃f. (∀b ∈ B. (b,f b) ∈ S) ∧ A = ⋃((λx. f x) ` B))"
      by (metis assms s_prod_test)
    thus "(a,A) ∈ (R ⋅ P) ⋅ S"
      by (clarsimp simp: mr_simp)
  qed
qed

lemma test_assoc2: 
assumes "P ⊆ 1⇩σ"
shows "(P ⋅ R) ⋅ S = P ⋅ (R ⋅ S)"
proof (rule antisym)
  show "(P ⋅ R) ⋅ S ⊆  P ⋅ (R ⋅ S)"
    by (metis s_prod_assoc1)
  show "P ⋅ (R ⋅ S) ⊆ (P ⋅ R) ⋅ S" using assms
  proof clarify
    fix a A
    assume "(a,A) ∈ P ⋅ (R ⋅ S)"
    hence "(a,{a}) ∈ P ∧ (a,A) ∈ R ⋅ S"
      by (metis assms test_s_prod)
    hence "(a,{a}) ∈ P ∧ (∃B. (a,B) ∈ R ∧ (∃f. (∀b ∈ B. (b,f b) ∈ S) ∧ A = ⋃((λx. f x) ` B)))" 
      by (clarsimp simp: mr_simp)
    hence "∃B.(a,{a}) ∈ P ∧ (a,B) ∈ R ∧ (∃f. (∀b ∈ B. (b,f b) ∈ S) ∧ A = ⋃((λx. f x) ` B))" 
      by (clarsimp simp: mr_simp)
    hence "∃B. (a,B) ∈ P ⋅ R ∧ (∃f. (∀b ∈ B. (b,f b) ∈ S) ∧ A = ⋃((λx. f x) ` B))"
      by (metis assms test_s_prod)
    thus "(a,A) ∈ (P ⋅ R) ⋅ S"
      by (clarsimp simp: mr_simp)
  qed
qed

lemma test_assoc3: 
assumes "P ⊆ 1⇩σ"
shows "(R ⋅ S) ⋅ P = R ⋅ (S ⋅ P)"
proof (rule antisym)
  show "(R ⋅ S) ⋅ P ⊆ R ⋅ (S ⋅ P)"
    by (metis s_prod_assoc1)
  show "R ⋅ (S ⋅ P) ⊆ (R ⋅ S) ⋅ P" using assms
    proof clarify
    fix a A
    assume hyp1: "(a, A) ∈ R ⋅ (S ⋅ P)"
    hence "∃B. (a,B) ∈ R ∧ (∃f. (∀b∈B. (b,f b) ∈ S ⋅ P) ∧ A = ⋃((λx. f x) ` B))"
      by (simp add: s_prod_test s_prod_im)
    hence "∃B. (a,B) ∈ R ∧ (∃f. (∀b∈B. (b,f b) ∈ S ∧ (∀a∈f b. (a,{a}) ∈ P)) ∧ A = ⋃((λx. f x) ` B))"
      by (simp add: s_prod_test assms)
    hence "∃B. (a,B) ∈ R ∧ (∃f. (∀b∈B. (b,f b) ∈ S) ∧ (∀a∈⋃((λx. f x) ` B). (a,{a}) ∈ P) ∧ A = ⋃((λx. f x) ` B))"
      by auto
    hence "∃B. (a,B) ∈ R ∧ (∃f. (∀b∈B. (b,f b) ∈ S) ∧ (∀a∈A. (a,{a}) ∈ P) ∧ A = ⋃((λx. f x) ` B))"
      by auto blast
    hence "(a,A) ∈ R ⋅ S ∧ (∀a∈A. (a,{a}) ∈ P)"
      by (auto simp: mr_simp)
    thus "(a,A) ∈ (R ⋅ S) ⋅ P"
      by (simp add: s_prod_test assms)
  qed
qed

lemma s_distl_test: 
assumes "R ⊆ 1⇩σ"
shows "R ⋅ (S ∪ T) = R ⋅ S ∪ R ⋅ T" 
  apply (clarsimp simp: mr_simp) using assms subid_aux2 by fastforce 

text ‹Next we verify Lemma 2.1.›

lemma subid_par_idem: 
assumes "R ⊆ 1⇩σ"
shows "R ∥ R = R"
  by (rule set_eqI, clarsimp simp: mr_simp, metis Un_absorb assms subid_aux2) 

lemma term_par_idem: 
assumes "R ⊆ 1⇩π" 
shows "R ∥ R = R"
  using assms by (auto simp: mr_simp)

lemma U_par_idem: "U ∥ U = U"
  by (auto simp: mr_simp)

lemma nc_par_idem: "NC ∥ NC = NC"
  by (auto simp: mr_simp)

text ‹Next we prove the properties of Lemma 2.2 and 3.2. First we prepare to show that multirelations form c-lattices.›

text ‹We define the domain operation on multirelations and verify the explicit definition from Section 3.›

definition d :: "'a mrel ⇒ 'a mrel" where
  "d R ≡ {(a,{a}) |a. ∃B. (a,B) ∈ R}"

named_theorems mrd_simp
declare mr_simp [mrd_simp] d_def [mrd_simp]

lemma d_def_expl: "d R = (R ⋅ 1⇩π) ∥ 1⇩σ"
  apply (simp add: mrd_simp) using set_eqI by force

interpretation mrel_pbdl_monoid: pbdl_monoid "1⇩σ" "(⋅)" "1⇩π" "(∥)" "(∪)" "(⊆)" "(⊂)" "{}" "U" "(∩)"
  by (unfold_locales, auto simp: mrd_simp)

text ‹Here come the properties of Lemma 2.2.›

lemma c1: "(R ⋅ 1⇩π) ∥ R = R"
  apply (rule set_eqI) 
  apply (clarsimp simp: mr_simp)
  by (metis (no_types, lifting) SUP_bot SUP_bot_conv(2) sup_bot.left_neutral) 

lemma t_aux: "T ∥ T ⊆ T ⟹ (∀a B C. (a,B) ∈ T ∧ (a,C) ∈ T ⟹ (a,B ∪ C) ∈ T)"
  by (clarsimp simp: mr_simp)

lemma cl4:
assumes "T ∥ T ⊆ T"
shows "(R ⋅ T) ∥ (S ⋅ T) ⊆ (R ∥ S) ⋅ T" 
proof clarify
fix a A   
  assume  "(a,A) ∈ (R ⋅ T) ∥ (S ⋅ T)"
  hence "∃B C. A = B ∪ C ∧ (∃D. (a,D) ∈ R ∧ (∃f. (∀d ∈ D. (d,f d) ∈ T) ∧ B = ⋃ ((λx. f x) ` D))) ∧ (∃E. (a,E) ∈ S ∧ (∃g. (∀e ∈ E. (e,g e) ∈ T) ∧ C = ⋃ ((λx. g x)` E)))"
    by (simp add: mr_simp)
  hence "∃D E. (a,D ∪ E) ∈ R ∥ S ∧ (∃f g. (∀d ∈ D. (d,f d) ∈ T) ∧ (∀e ∈ E. (e,g e) ∈ T) ∧ A = (⋃ ((λx. f x) ` D)) ∪ (⋃ ((λx. g x)` E)))"
    by (auto simp: mr_simp)
  hence "∃D E. (a,D ∪ E) ∈ R ∥ S ∧ (∃f g. (∀d ∈ D-E. (d,f d) ∈ T) ∧ (∀e ∈ E-D. (e,g e) ∈ T) ∧ (∀x ∈ D ∩ E. (x,f x) ∈ T ∧ (x,g x) ∈ T) ∧ A = (⋃ ((λx. f x) ` (D-E))) ∪ (⋃ ((λx. g x) ` (E-D)) ∪ (⋃ ((λy. f y ∪ g y) ` (D ∩ E)))))"
    by auto blast
  hence "∃D E. (a,D ∪ E) ∈ R ∥ S ∧ (∃f g. (∀d ∈ D-E. (d,f d) ∈ T) ∧ (∀e ∈ E-D. (e,g e) ∈ T) ∧ (∀x ∈ D ∩ E. (x,f x ∪ g x) ∈ T) ∧ A = (⋃ ((λx. f x) ` (D-E))) ∪ (⋃ ((λx. g x) ` (E-D)) ∪ (⋃ ((λy. f y ∪ g y) ` (D ∩ E)))))"
    apply clarify
    apply (rule_tac x = D in exI)
    apply (rule_tac x = E in exI)
    apply clarify
    apply (rule_tac x = f in exI)
    apply (rule_tac x = g in exI)
    using assms by (auto simp: p_prod_def p_prod_iff, blast)
  hence "∃D E. (a,D ∪ E) ∈ R ∥ S ∧ (∃h. (∀d ∈ D-E. (d,h d) ∈ T) ∧ (∀e ∈ E-D. (e, h e) ∈ T) ∧ (∀x ∈ D ∩ E. (x, h x) ∈ T) ∧ A = (⋃ ((λx. h x) ` (D-E))) ∪ (⋃ ((λx. h x) ` (E-D)) ∪ (⋃ ((λy. h y) ` (D ∩ E)))))"
    apply clarify
    apply (rule_tac x = D in exI)
    apply (rule_tac x = E in exI)
    apply clarify
    apply (rule_tac x = "λx. if x ∈ (D - E) then f x else (if x ∈ D ∩ E then (f x ∪ g x) else g x)" in exI)
    by auto
  hence " (∃B. (a,B) ∈ R ∥ S ∧ (∃h. (∀b∈B. (b,h b) ∈ T) ∧ A = ⋃((λx. h x) ` B)))"
    by auto blast
  thus "(a,A) ∈ (R ∥ S) ⋅ T"
    by (simp add: mr_simp)
qed

lemma cl3: "R ⋅ (S ∥ T) ⊆ (R ⋅ S) ∥ (R ⋅ T)"
proof clarify
fix a A
assume "(a,A) ∈ R ⋅ (S ∥ T)"
  hence "∃B. (a,B) ∈ R ∧ (∃f. (∀b ∈ B. ∃C D. f b = C ∪ D ∧ (b,C) ∈ S ∧ (b,D) ∈ T) ∧ A = ⋃((λx. f x) ` B))"
    by (clarsimp simp: mr_simp)
  hence "∃B. (a,B) ∈ R ∧ (∃f g h. (∀b ∈ B. f b = g b ∪ h b ∧ (b,g b) ∈ S ∧ (b,h b) ∈ T) ∧ A = ⋃((λx. f x) ` B))"
    by (clarsimp simp: bchoice, metis)
  hence "∃B. (a,B) ∈ R ∧ (∃g h. (∀b ∈ B. (b,g b) ∈ S ∧ (b,h b) ∈ T) ∧ A = (⋃ ((λx. g x) ` B)) ∪ (⋃ ((λx. h x) ` B)))"
    by  blast
  hence "∃C D. (∃B. (a,B) ∈ R ∧ (∃g. (∀b ∈ B. (b,g b) ∈ S) ∧  C = ⋃ ((λx. g x) ` B))) ∧ (∃B. (a,B) ∈ R ∧ (∃h. (∀b ∈ B. (b,h b) ∈ T) ∧  D = ⋃ ((λx. h x)` B))) ∧ A = C ∪ D"
    by blast
  thus "(a,A) ∈ (R ⋅ S) ∥ (R ⋅ T)"
    by (auto simp: mr_simp)
qed

lemma cl5: "(R ⋅ S) ⋅ (T ⋅ {}) = R ⋅ (S ⋅ (T ⋅ {}))"
  proof (rule antisym)
  show "(R ⋅ S) ⋅ (T ⋅ {}) ⊆ R ⋅ (S ⋅ (T ⋅ {}))"
    by (metis s_prod_assoc1)
  show " R ⋅ (S ⋅ (T ⋅ {})) ⊆ (R ⋅ S) ⋅ (T ⋅ {})"
  proof clarify
  fix a A
  assume "(a,A) ∈  R ⋅ (S ⋅ (T ⋅ {}))"
    hence "∃B. (a,B) ∈ R ∧ (∃f. (∀b ∈ B. (∃ C. (b,C) ∈ S ∧ (∃g. (∀x ∈ C. (x,g x) ∈ T ⋅ {}) ∧ f b = ⋃((λx. g x) ` C)))) ∧ A = ⋃((λx. f x) ` B))"
      by (clarsimp simp: mr_simp)
    hence "∃B. (a,B) ∈ R ∧ (∃f. (∀b ∈ B. (∃ C. (b,C) ∈ S ∧ (∀x ∈ C. (x,{}) ∈ T ⋅ {}) ∧ f b = {})) ∧ A = ⋃((λx. f x) ` B))"
      by (clarsimp simp: mr_simp) fastforce
    hence "∃B. (a,B) ∈ R ∧ (∀b ∈ B. (∃ C. (b,C) ∈ S ∧ (∀x ∈ C. (x,{}) ∈ T ⋅ {}))) ∧ A = {}"
      by (metis (erased, opaque_lifting) SUP_bot_conv(2))
    hence "∃B. (a,B) ∈ R ∧ (∃f. (∀b ∈ B. (b,f b) ∈ S ∧ (∀x ∈ f b. (x,{}) ∈ T ⋅ {}))) ∧ A = {}" 
      by metis
    hence "∃B. (a,B) ∈ R ∧ (∃f. (∀b ∈ B. (b,f b) ∈ S) ∧ (∀x ∈ ⋃((λx. f x) ` B). (x,{}) ∈ T ⋅ {})) ∧ A = {}"
      by (metis UN_E) 
    hence "∃C B. (a,B) ∈ R ∧ (∃f. (∀b ∈ B. (b, f b) ∈ S) ∧ C =  ⋃((λx. f x) ` B) ∧ (∀x ∈ C. (x,{}) ∈ T ⋅ {})) ∧ A = {}"
      by metis
    hence "∃C. (a,C) ∈ R ⋅ S ∧ (∀x ∈ C. (x,{}) ∈ T ⋅ {}) ∧ A = {}"
      by (auto simp: mr_simp)
    thus "(a,A) ∈ (R ⋅ S) ⋅ (T ⋅ {})"
      by (clarsimp simp: mr_simp) blast
  qed
qed

text ‹We continue verifying other c-lattice axioms›

lemma cl8_var: "d R ⋅ S = (R ⋅ 1⇩π) ∥ S"
  apply (rule set_eqI)
  apply (clarsimp simp: mrd_simp)
  apply standard
  apply (metis SUP_bot sup.commute sup_bot.right_neutral)
  by auto

lemma cl9_var: "d (R ∩ 1⇩σ) = R ∩ 1⇩σ"
  by (auto simp: mrd_simp)

lemma cl10_var: "d (R - 1⇩π) = 1⇩σ ∩ ((R - 1⇩π) ⋅ NC)"
  apply (rule set_eqI)
  apply (clarsimp simp: d_def p_id_def s_id_def U_def s_prod_im)
  by (metis UN_constant insert_not_empty)

subsection ‹Multirelations and C-Lattices›

text ‹Next we show that multirelations form c-lattices (Proposition 7.3) and prove further facts in this setting.›

interpretation mrel_c_lattice: c_lattice "1⇩σ" "(⋅)" "1⇩π" "(∥)" "(∪)" "(⊆)" "(⊂)" "{}" "U" "(∩)" "NC"
proof
  fix x y z :: "('b × 'b set) set"
  show "x ⋅ 1⇩π ∪ x ⋅ NC = x ⋅ U"
    apply (rule set_eqI) 
    apply (clarsimp simp:  mr_simp)
    using UN_constant all_not_in_conv by metis
  show "1⇩π ∩ (x ∪ NC) = x ⋅ {}"
    by (auto simp: mr_simp)
  show "x ⋅ (y ∥ z) ⊆ x ⋅ y ∥ (x ⋅ z)"
    by (rule cl3)
  show "z ∥ z ⊆ z ⟹ x ∥ y ⋅ z = x ⋅ z ∥ (y ⋅ z)"
    by (metis cl4 seq_conc_subdistr subset_antisym)
  show "x ⋅ (y ⋅ (z ⋅ {})) = x ⋅ y ⋅ (z ⋅ {})"
    by (metis cl5)
  show "x ⋅ {} ⋅ z = x ⋅ {}"
    by (clarsimp simp: mr_simp)
  show "1⇩σ ∥ 1⇩σ = 1⇩σ"
    by (auto simp: mr_simp)
  show "x ⋅ 1⇩π ∥ 1⇩σ ⋅ y = x ⋅ 1⇩π ∥ y"
    by (metis cl8_var d_def_expl)
  show "x ∩ 1⇩σ ⋅ 1⇩π ∥ 1⇩σ = x ∩ 1⇩σ"
    by (auto simp: mr_simp)
  show "x ∩ NC ⋅ 1⇩π ∥ 1⇩σ = 1⇩σ ∩ (x ∩ NC ⋅ NC)"
    by (metis Int_Diff cl10_var d_def_expl)
  show "x ∩ NC ⋅ 1⇩π ∥ NC = x ∩ NC ⋅ NC"
    apply (rule set_eqI)
    apply (clarsimp simp: d_def U_def p_id_def p_prod_def s_prod_im)
    apply standard
    apply (metis (no_types, lifting) UN_extend_simps(2) Un_empty)
  proof -
    fix a :: 'b and b :: "'b set"
    assume a1: "∃B. (a, B) ∈ x ∧ B ≠ {} ∧ (∃f. (∀b∈B. f b ≠ {}) ∧ b = (⋃x∈B. f x))"
    { fix bb :: "'b set ⇒ 'b set ⇒ 'b set ⇒ ('b ⇒ 'b set) ⇒ 'b"
      obtain BB :: "'b set" and BBa :: "'b ⇒ 'b set" where
        ff1: "(a, BB) ∈ x ∧ {} ≠ BB ∧ (∀b. b ∉ BB ∨ {} ≠ BBa b) ∧ ⋃(BBa ` BB) = b"
        by (metis (full_types) a1)
      hence "∀B. (⋃b∈BB. (B::'b set)) = B"
        by force
      hence "∃B Ba. B ∪ Ba = b ∧ (∃Bb. (a, Bb) ∈ x ∧ {} ≠ Bb ∧ (∃f. (bb B Ba Bb f ∉ Bb ∨ {} = f (bb B Ba Bb f)) ∧ ⋃(f ` Bb) = B)) ∧ {} ≠ Ba"
        by (metis ff1 SUP_bot_conv(2) sup_bot.left_neutral) }
    thus "∃B Ba. b = B ∪ Ba ∧ (∃Ba. (a, Ba) ∈ x ∧ Ba ≠ {} ∧ (∃f. (∀b∈Ba. f b = {}) ∧ B = (⋃b∈Ba. f b))) ∧ Ba ≠ {}"
      by metis
  qed
qed

text ‹The following facts from Lemma 2.2 remain to be shown.›

lemma p_id_assoc1: "(1⇩π ⋅ R) ⋅ S = 1⇩π ⋅ (R ⋅ S)"
  by (clarsimp simp: mr_simp)

lemma p_id_assoc2: "(R ⋅ 1⇩π) ⋅ T = R ⋅ (1⇩π ⋅ T)"
  by (auto simp add: mr_simp cong del: SUP_cong_simp, blast+)

lemma seq_conc_subdistrl: 
assumes "P ⊆ 1⇩σ"
shows "P ⋅ (S ∥ T) = (P ⋅ S) ∥ (P ⋅ T)"
  by (metis assms mrel_c_lattice.d_inter_r mrel_c_lattice.d_s_subid)

lemma test_s_prod_is_meet [simp]: 
assumes "R ⊆ 1⇩σ" 
and "S ⊆ 1⇩σ"
shows "R ⋅ S = R ∩ S"
  using assms by (auto simp: mr_simp, force+)

lemma test_p_prod_is_meet: 
assumes "R ⊆ 1⇩σ"
and "S ⊆ 1⇩σ"
shows "R ∥ S = R ∩ S"
  apply standard
  using assms
  apply (auto simp: mr_simp, force+)
  done

lemma test_multipliciativer:
assumes "R ⊆ 1⇩σ"
and "S ⊆ 1⇩σ"
shows "(R ∩ S) ⋅ T = (R ⋅ T) ∩ (S ⋅ T)"
  using assms by (clarsimp simp: set_eqI mr_simp subid_aux2, force)

text ‹Next we verify the remaining fact from Lemma 2.2; in fact it follows from the corresponding theorem of c-lattices.›

lemma c6: "R ⋅ 1⇩π ⊆ 1⇩π"
 by (clarsimp simp: mr_simp)

text ‹Next we verify Lemma 3.1.›

lemma p_id_st: "R ⋅ 1⇩π = {(a,{}) |a.  ∃B. (a,B) ∈ R}"
  by (auto simp: mr_simp)
 
lemma p_id_zero: "R ∩ 1⇩π = R ⋅ {}"
  by (auto simp: mr_simp)

lemma p_id_zero_st: "R ∩ 1⇩π = {(a,{}) |a. (a,{}) ∈ R}"
  by (auto simp: mr_simp)

lemma s_id_st: "R ∩ 1⇩σ = {(a,{a}) |a. (a,{a}) ∈ R}"
  by (auto simp: mr_simp)

lemma U_seq_st: "(a,A) ∈ R ⋅ U ⟷ (A = {} ∧ (a,{}) ∈ R) ∨ (∃B. B ≠ {} ∧ (a,B) ∈ R)"
  by (clarsimp simp: s_prod_im U_def, metis SUP_constant SUP_empty) 

lemma U_par_st: "(a,A) ∈ R ∥ U ⟷ (∃B. B ⊆ A ∧ (a,B) ∈ R)"
  by (auto simp: mr_simp)

text ‹Next we verify the relationships after Lemma 3.1.›

lemma s_subid_iff1: "R ⊆ 1⇩σ ⟷ R ∩ 1⇩σ = R"
  by blast

lemma s_subid_iff2: "R ⊆ 1⇩σ ⟷ d R = R"
  by (auto simp: mrd_simp)

lemma p_subid_iff: "R ⊆ 1⇩π ⟷ R ⋅ 1⇩π = R"
  by (simp add: mrel_c_lattice.term_p_subid)

lemma vec_iff1: 
assumes "∀a. (∃A. (a,A) ∈ R) ⟶ (∀A. (a,A) ∈ R)"
shows "(R ⋅ 1⇩π) ∥ U = R"
  using assms by (auto simp: mr_simp)

lemma vec_iff2: 
assumes "(R ⋅ 1⇩π) ∥ U = R"
shows "(∀a. (∃A. (a,A) ∈ R) ⟶ (∀A. (a,A) ∈ R))"
  using assms apply (clarsimp simp: mr_simp)
  proof -
    fix a :: 'a and A :: "'a set" and Aa :: "'a set"
    assume a1: "(a, A) ∈ R"
    obtain AA :: "('a × 'a set) set ⇒ 'a set ⇒ 'a ⇒ 'a set" where
    "∀x0 x1 x2. (∃v3⊆x1. (x2, v3) ∈ x0) = (AA x0 x1 x2 ⊆ x1 ∧ (x2, AA x0 x1 x2) ∈ x0)"
      by moura
    hence f2: "AA (R ⋅ 1⇩π) A a ⊆ A ∧ (a, AA (R ⋅ 1⇩π) A a) ∈ R ⋅ 1⇩π"
      by (metis a1 U_par_st assms)
    hence "∃aa. (a, AA (R ⋅ 1⇩π) A a) = (aa, {}) ∧ (∃A. (aa, A) ∈ R)"
      by (simp add: p_id_st)
    hence "AA (R ⋅ 1⇩π) A a ⊆ Aa"
      by blast
   thus "(a, Aa) ∈ R"
      using f2 by (metis (no_types) U_par_st assms)
qed

lemma vec_iff: "(∀a. (∃A. (a,A) ∈ R) ⟶ (∀A. (a,A) ∈ R)) ⟷ (R ⋅ 1⇩π) ∥ U = R"
  by (metis vec_iff1 vec_iff2)

lemma ucl_iff: "(∀a A B. (a,A) ∈ R ∧ A ⊆ B ⟶ (a,B) ∈ R) ⟷ R ∥ U = R" 
  by (clarsimp simp: mr_simp, blast)

lemma nt_iff: "R ⊆ NC ⟷ R ∩ NC = R"
  by blast

text‹Next we provide a counterexample for the final paragraph of Section 3.›

lemma "1⇩σ ∩ R ⋅ U = R"
  nitpick
  oops

text‹Next we present a counterexample for vectors mentioned before Lemma 9.3.›

lemma "d (d R ⋅ U) ⋅ (d S ⋅ U) ⋅ U = (d R ⋅ U) ⋅ (d S ⋅ U)"
  nitpick
  oops

text‹Next we prove Tarski' rule (Lemma 9.3).›

lemma tarski_aux: 
assumes "R - 1⇩π ≠ {}"
and "(a,A) ∈  NC"
shows "(a,A) ∈ NC ⋅ ((R - 1⇩π) ⋅ NC)"
proof -
  have "(∃B. B ≠ {} ∧ (∀x ∈ B. (x,{x}) ∈ d (R - 1⇩π)))" 
    using assms(1) by (auto simp: mrd_simp)
  hence "(∃B. B ≠ {} ∧ (∀x ∈ B. (x,{x}) ∈ d (R - 1⇩π))) ∧ A ≠ {}" 
    using assms(2) by (clarsimp simp: mr_simp)
  hence "(∃B. B ≠ {} ∧ (∃f. (∀x ∈ B. (x,{x}) ∈ d (R - 1⇩π) ∧ f x ≠ {}) ∧ A = ⋃ ((λx. (f x)) ` B)))"
    by (metis UN_constant)
  hence "(a,A) ∈ NC ⋅ (d (R - 1⇩π) ⋅ NC)"
    by (clarsimp simp: mrd_simp) metis
  thus ?thesis
   by (clarsimp simp: mrd_simp, metis UN_constant)
qed

lemma tarski: 
assumes "R - 1⇩π ≠ {}"
shows "NC ⋅ ((R - 1⇩π) ⋅ NC) = NC"
  by standard (simp add: U_def p_id_def s_prod_im, force, metis assms tarski_aux subrelI)

text ‹Next we verify the assumptions of Proposition 9.8.›

lemma d_assoc1: "d R ⋅ (S ⋅ T) = (d R ⋅ S) ⋅ T"
  by (metis d_def_expl mrel_c_lattice.d_def mrel_c_lattice.d_sub_id_ax test_assoc2)

lemma d_meet_distr_var: "(d R ∩ d S) ⋅ T = (d R ⋅ T) ∩ (d S ⋅ T)"
  by (auto simp: mrd_simp)

text ‹Lemma 10.5.›

lemma "((R ∩ 1⇩σ) ⋅ (S ∩ 1⇩σ)) ⋅ 1⇩π = ((R ∩ 1⇩σ) ⋅ 1⇩π) ⋅ ((S ∩ 1⇩σ) ⋅ 1⇩π)" 
  nitpick
  oops

lemma "d ((R ⋅ 1⇩π) ⋅ (S ⋅ 1⇩π)) = d (R ⋅ 1⇩π) ⋅ d (S ⋅ 1⇩π)"
  nitpick
  oops

lemma "((R ∩ 1⇩σ) ⋅ (S ∩ 1⇩σ)) ⋅ U = ((R ∩ 1⇩σ) ⋅ U) ⋅ ((S ∩ 1⇩σ) ⋅ U)" 
  nitpick
  oops

lemma "d (((R ⋅ 1⇩π) ∥ U) ⋅ ((S ⋅ 1⇩π) ∥ U)) = d ((R ⋅ 1⇩π) ∥ U) ⋅ d ((S ⋅ 1⇩π) ∥ U)"
  nitpick
  oops

lemma "((R ⋅ 1⇩π) ⋅ (S ⋅ 1⇩π)) ∥ U = ((R ⋅ 1⇩π) ∥ U) ⋅ ((S ⋅ 1⇩π) ∥ U)"
  nitpick
  oops

lemma "(((R - 1⇩π) ∩ 1⇩σ) ⋅ ((S - 1⇩π) ∩ 1⇩σ)) ⋅ 1⇩π = (((R - 1⇩π) ∩ 1⇩σ) ⋅ 1⇩π) ⋅ (((S - 1⇩π) ∩ 1⇩σ) ⋅ 1⇩π)" 
  nitpick
  oops

lemma "d (((R - 1⇩π) ⋅ 1⇩π) ⋅ ((S - 1⇩π) ⋅ 1⇩π)) = d ((R - 1⇩π) ⋅ 1⇩π) ⋅ d ((S - 1⇩π) ⋅ 1⇩π)"
  nitpick
  oops

lemma "(((R - 1⇩π) ∩ 1⇩σ) ⋅ ((S - 1⇩π) ∩ 1⇩σ)) ⋅ NC = (((R - 1⇩π) ∩ 1⇩σ) ⋅ NC) ⋅ (((S - 1⇩π) ∩ 1⇩σ) ⋅ NC)" 
  apply (auto simp: U_def p_id_def s_id_def s_prod_im)
  defer
  nitpick
  oops

lemma "d ((((R - 1⇩π) ⋅ 1⇩π) ∥ NC) ⋅ (((S - 1⇩π) ⋅ 1⇩π) ∥ NC)) = d (((R - 1⇩π) ⋅ 1⇩π) ∥ NC) ⋅ d (((S - 1⇩π) ⋅ 1⇩π) ∥ NC)"
  apply (simp add: U_def p_id_def s_prod_im p_prod_def d_def)
  nitpick
  oops

lemma "(((R - 1⇩π) ⋅ 1⇩π) ⋅ ((S - 1⇩π) ⋅ 1⇩π)) ∥ NC = (((R - 1⇩π) ⋅ 1⇩π) ∥ NC) ⋅ (((S - 1⇩π) ⋅ 1⇩π) ∥ NC)"
  nitpick
  oops

lemma "((((R - 1⇩π) ⋅ 1⇩π) ∥ NC) ⋅ (((S - 1⇩π) ⋅ 1⇩π) ∥ NC)) ⋅ 1⇩π  = ((((R - 1⇩π) ⋅ 1⇩π) ∥ NC) ⋅ 1⇩π) ⋅ ((((S - 1⇩π) ⋅ 1⇩π) ∥ NC) ⋅ 1⇩π)"
  nitpick
  oops

subsection ‹Terminal and Nonterminal Elements›

text ‹Lemma 11.4›

lemma "(R ⋅ S) ⋅ {} = (R ⋅ {}) ⋅ (S ⋅ {})"
  nitpick
  oops

lemma "(R ⋅ S) - 1⇩π = (R - 1⇩π) ⋅ (S - 1⇩π)"
  apply (auto simp: s_prod_im p_id_def)
  nitpick
  oops

lemma "(R ∥ S) - 1⇩π = (R - 1⇩π) ∥ (S - 1⇩π)"
  nitpick
  oops

text ‹Lemma 11.8.›

lemma "((R ⋅ 1⇩π) ⋅ (S - 1⇩π)) - 1⇩π = (R ⋅ 1⇩π) ⋅ (S - 1⇩π)"
  nitpick 
  oops

lemma "((S - 1⇩π) ⋅ (R ⋅ 1⇩π)) - 1⇩π = (S - 1⇩π) ⋅ (R ⋅ 1⇩π)"
  nitpick 
  oops

lemma "((R ⋅ 1⇩π) ∥ (S - 1⇩π)) ⋅ 1⇩π = (R ⋅ 1⇩π) ∥ (S - 1⇩π)"
  nitpick
  oops

text ‹Lemma 11.10.›

lemma "R ⋅ {} ⊆ S ⋅ {} ⟹ (R ⋅ T) ⋅ {} ⊆ (S ⋅ T) ⋅ {}"
  nitpick
  oops

lemma "R - 1⇩π ⊆ S - 1⇩π ⟹ (R ∥ T) - 1⇩π ⊆ (S ∥ T) - 1⇩π"
  nitpick
  oops

lemma "R - 1⇩π ⊆ S - 1⇩π ⟹ (T ⋅ R) - 1⇩π ⊆ (T ⋅ S) - 1⇩π"
  apply (auto simp: p_id_def s_prod_im)
  nitpick
  oops

text ‹Corollary 11.12›

lemma "R ⋅ {} = S ⋅ {} ⟹ (R ⋅ T) ⋅ {} = (S ⋅ T) ⋅ {}"
  nitpick
  oops

lemma "R - 1⇩π = S - 1⇩π ⟹ (R ∥ T) - 1⇩π = (S ∥ T) - 1⇩π"
  nitpick
  oops

lemma "R - 1⇩π = S - 1⇩π ⟹ (T ⋅ R) - 1⇩π = (T ⋅ S) - 1⇩π"
  apply (auto simp: p_id_def s_prod_im)
  nitpick
  oops

subsection ‹Multirelations, Proto-Quantales and Iteration›

interpretation mrel_proto_quantale: proto_quantale "1⇩σ" "(⋅)" Inter Union "(∩)" "(⊆)" "(⊂)" "(∪)" "{}" "U"
  by (unfold_locales, auto simp: mr_simp)

text ‹We reprove Corollary 13.2. because Isabelle does not pick it up from the quantale level.›

lemma iso_prop: "mono (λX. S ∪ R ⋅ X)"
  by (rule monoI, (clarsimp simp: mr_simp), blast)

lemma gfp_lfp_prop: "gfp (λX. R ⋅ X) ∪ lfp (λX. S ∪ R ⋅ X) ⊆ gfp (λX. S ∪ R ⋅ X)"
  by (simp add: lfp_le_gfp gfp_mono iso_prop)

subsection ‹Further Counterexamples›

text ‹Lemma 14,1. and 14.2› 

lemma  "R ∥ R ⊆ R" 
   nitpick
   oops 

lemma "R ⊆ R ∥ S"
   nitpick
   oops

lemma "R ∥ S ∩ R ∥ T ⊆ R ∥ (S ∩ T)"
  nitpick
  oops

lemma "R ⋅ (S ∥ T) = (R ⋅ S) ∥ (R ⋅ T)"
  nitpick
  oops

lemma "R ⋅ (S ⋅ T) ⊆ (R ⋅ S) ⋅ T"
  apply (auto simp: s_prod_im)
  nitpick
  oops

lemma "⟦R ∥ R = R; S ∥ S = S; T ∥ T = T⟧ ⟹ R ⋅ (S ∥ T) = (R ⋅ S) ∥ (R ⋅ T)"
  nitpick
  oops

lemma "⟦R ≠ {}; S ≠ {}; ∀a. (a,{}) ∉ R ∪ S⟧ ⟹ R ⋅ S ⊆ R ∥ S"
  quickcheck
  oops

lemma "⟦R ≠ {}; S ≠ {}; ∀a. (a,{}) ∉ R ∪ S⟧ ⟹ R ∥ S ⊆ R ⋅ S"
  quickcheck
  oops

lemma "⟦R ≠ {}; S ≠ {}; T ≠ {}; ∀a. (a,{}) ∉ R ∪ S ∪ T⟧ ⟹ (R ∥ S) ⋅ T ⊆ R ∥ (S ⋅ T)"
  quickcheck
  oops

lemma "⟦R ≠ {}; S ≠ {}; T ≠ {}; ∀a. (a,{}) ∉ R ∪ S ∪ T⟧ ⟹ R ∥ (S ⋅ T) ⊆ (R ∥ S) ⋅ T" 
  quickcheck
  oops

lemma "⟦R ≠ {}; S ≠ {}; T ≠ {}; ∀a. (a,{}) ∉ R ∪ S ∪ T⟧ ⟹ R ⋅ (S ∥ T) ⊆ (R ⋅ S) ∥ T"
  quickcheck
  oops

lemma "⟦R ≠ {}; S ≠ {}; T ≠ {}; ∀a. (a,{}) ∉ R ∪ S ∪ T⟧ ⟹ (R ⋅ S) ∥ T ⊆ R ⋅ (S ∥ T)"
  quickcheck
  oops

lemma "⟦R ≠ {}; S ≠ {}; ∀a. (a,{}) ∉ R ∪ S⟧ ⟹ (R ∥ S) ⋅ (R ∥ S) ⊆ (R ⋅ R) ∥ (S ⋅ S)"
  quickcheck
  oops

lemma "⟦R ≠ {}; S ≠ {}; ∀a. (a,{}) ∉ R ∪ S⟧ ⟹ (R ⋅ R) ∥ (S ⋅ S) ⊆ (R ∥ S) ⋅ (R ∥ S)"
  quickcheck
  oops

subsection ‹Relationship with Up-Closed Multirelations›

text ‹We now define Parikh's sequential composition.›

definition s_prod_pa :: "'a mrel ⇒ 'a mrel ⇒ 'a mrel" (infixl "⊗" 70) where
  "R ⊗ S = {(a,A). (∃B. (a,B) ∈ R ∧ (∀b ∈ B. (b,A) ∈ S))}"

text ‹We show that Parikh's definition doesn't preserve up-closure.›

lemma up_closed_prop: "((R ∥ U) ⋅ (S ∥ U)) ∥ U = (R ∥ U) ⋅ (S ∥ U)"
  apply (auto simp: p_prod_def s_prod_pa_def U_def)
  nitpick
  oops

text ‹Lemma 15.1.›

lemma onelem: "(R ⋅ S) ∥ U ⊆ R ⊗ (S ∥ U)"
  by (auto simp: s_prod_im p_prod_def U_def s_prod_pa_def)

lemma twolem: "R ⊗ (S ∥ U)  ⊆ (R ⋅ S) ∥ U"
proof clarify
  fix a A
  assume "(a,A) ∈ R ⊗ (S ∥ U)"
  hence "∃B. (a,B) ∈ R ∧ (∀b ∈ B. (b,A) ∈ S ∥ U)"
    by (auto simp: s_prod_pa_def)
  hence "∃B. (a,B) ∈ R ∧ (∀b ∈ B. ∃C. C ⊆ A ∧ (b,C) ∈ S)"
    by (metis U_par_st)
  hence "∃B. (a,B) ∈ R ∧ (∃f. (∀b ∈ B. f b ⊆ A ∧ (b,f b) ∈ S))"
    by metis
  hence "∃C. C ⊆ A ∧ (∃B. (a,B) ∈ R ∧ (∃f. (∀b ∈ B. (b,f b) ∈ S) ∧ C = ⋃ ((λx. f x) ` B)))"
    by clarsimp blast
  hence "∃C. C ⊆ A ∧ (a,C) ∈ R ⋅ S"     
    by (clarsimp simp: mr_simp)
  thus "(a,A) ∈ (R ⋅ S) ∥ U"
    by (simp add: U_par_st)
qed

lemma pe_pa_sim: "(R ⋅ S) ∥ U = R ⊗ (S ∥ U)"
  by (metis antisym onelem twolem)

lemma pe_pa_sim_var: "((R ∥ U) ⋅ (S ∥ U)) ∥ U = (R ∥ U) ⊗ (S ∥ U)"
  by (simp add: mrel_proto_trioid.mult_assoc pe_pa_sim)

lemma pa_assoc1: "((R ∥ U) ⊗ (S ∥ U)) ⊗ (T ∥ U) ⊆ (R ∥ U) ⊗ ((S ∥ U) ⊗ (T ∥ U))"
  by (clarsimp simp: p_prod_def s_prod_pa_def U_def, metis)

text ‹The converse direction of associativity remains to be proved.›

text ‹Corollary 15.3.›

lemma up_closed_par_is_meet: "(R ∥ U) ∥ (S ∥ U) = (R ∥ U) ∩ (S ∥ U)"
  by (auto simp: mr_simp)

end