(*<*)
theory Closures
imports
  More_Lattices
begin

(*>*)
section‹ Closure operators\label{sec:closures} ›

text‹

  semantic spaces are modelled as lattices arising from the fixed
  of various closure operators. We attempt to reduce our proof
  by defining a locale for Kuratowski's closure axioms,
  we do not requre strictness (i.e., it need not be the case that
  closure maps ‹⊥› to
 ‹⊥›). 🚫 then
 DaveyPriestley:2002"› term these ∗‹topped
  structures›; see also
🚫then
results.

›

locale closure =
  ordering "(\<le>)" "(<)" ―‹ We use a partial order as a preorder does not ensure that the closure is idempotent ›
  for less_eq :: "'a \<Rightarrow> 'a \<Rightarrow> bool" (infix \<open>\<^bold>\<le>\<close> 50)
     and less :: "'a \<Rightarrow> 'a \<Rightarrow> bool" (infix \<open>\<^bold><\<close> 50)
+ fixes cl :: "'a \<Rightarrow> 'a"
  assumes cl: "x \<^bold>\<le> cl y \<longleftrightarrow> cl x \<^bold>\<le> cl y" \<comment>\<open> All-in-one non-strict Kuratowski axiom \<close>
begin

definition closed :: "'a set" where \<comment>\<open> These pre fixed points form a complete lattice ala Tarski/Knaster \<close>
  "closed = {x. cl x \<^bold>\<le> x}"

lemma closed_clI:
  assumes "cl x \<^bold>\<le> x"
  shows "x \<in> closed"
unfolding closed_def using assms by simp

lemma expansive:
  shows "x \<^bold>\<le> cl x"
by (simp add: cl refl)

lemma idempotent[simp]:
  shows "cl (cl x) = cl x"
    and "cl \<circ> cl = cl"
using cl antisym by (auto iff: expansive)

lemma monotone_cl:
  shows "monotone (\<^bold>\<le>) (\<^bold>\<le>) cl"
by (rule monotoneI) (meson cl expansive trans)

lemmas strengthen_cl[strg] = st_monotone[OF monotone_cl]
lemmas mono_cl[trans] = monotoneD[OF monotone_cl]

lemma least:
  assumes "x \<^bold>\<le> y"
  assumes "y \<in> closed"
  shows "cl x \<^bold>\<le> y"
using assms cl closed_def trans by (blast intro: expansive)

lemma least_conv:
  assumes "y \<in> closed"
  shows "cl x \<^bold>\<le> y \<longleftrightarrow> x \<^bold>\<le> y"
using assms expansive least trans by blast

lemma closed[iff]:
  shows "cl x \<in> closed"
unfolding closed_def by (simp add: refl)

lemma le_closedE:
  assumes "x \<^bold>\<le> cl y"
  assumes "y \<in> closed"
  shows "x \<^bold>\<le> y"
using assms closed_def trans by blast

lemma closed_conv: \<comment>\<open> Typically used to manifest the closure using \<open>subst\<close> \<close>
  assumes "X \<in> closed"
  shows "X = cl X"
using assms unfolding closed_def by (blast intro: antisym expansive)

end

lemma (in ordering) closure_axioms_alt_def: \<comment>\<open> Equivalence with the Kuratowski closure axioms \<close>
  shows "closure_axioms (\<^bold>\<le>) cl \<longleftrightarrow> (\<forall>x. x \<^bold>\<le> cl x) \<and> monotone (\<^bold>\<le>) (\<^bold>\<le>) cl \<and> (\<forall>x. cl (cl x) = cl x)"
unfolding closure_axioms_def monotone_def by (metis antisym trans refl)

lemma (in ordering) closureI:
  assumes "\<And>x. x \<^bold>\<le> cl x"
  assumes "monotone (\<^bold>\<le>) (\<^bold>\<le>) cl"
  assumes "\<And>x. cl (cl x) = cl x"
  shows "closure (\<^bold>\<le>) (\<^bold><) cl"
by (blast intro: assms closure.intro[OF ordering_axioms, unfolded closure_axioms_alt_def])

lemma closure_inf_closure:
  fixes cl\<^sub>1 :: "'a::semilattice_inf \<Rightarrow> 'a"
  assumes "closure_axioms (\<le>) cl\<^sub>1"
  assumes "closure_axioms (\<le>) cl\<^sub>2"
  shows "closure_axioms (\<le>) (\<lambda>X. cl\<^sub>1 X \<sqinter> cl\<^sub>2 X)"
using assms unfolding closure_axioms_def by (meson order.trans inf_mono le_inf_iff order_refl)


subsection\<open> Complete lattices and algebraic closures\label{sec:closures-lattices} \<close>

locale closure_complete_lattice =
  complete_lattice "\<^bold>\<Sqinter>" "\<^bold>\<Squnion>" "(\<^bold>\<sqinter>)" "(\<^bold>\<le>)" "(\<^bold><)" "(\<^bold>\<squnion>)" "\<^bold>\<bottom>" "\<^bold>\<top>"
+ closure "(\<^bold>\<le>)" "(\<^bold><)" cl
    for less_eqa :: "'a \<Rightarrow> 'a \<Rightarrow> bool" (infix \<open>\<^bold>\<le>\<close> 50)
    and lessa (infix \<open>\<^bold><\<close> 50)
    and infa (infixl \<open>\<^bold>\<sqinter>\<close> 70)
    and supa (infixl \<open>\<^bold>\<squnion>\<close> 65)
    and bota (\<open>\<^bold>\<bottom>\<close>)
    and topa (\<open>\<^bold>\<top>\<close>)
    and Inf (\<open>\<^bold>\<Sqinter>\<close>)
    and Sup (\<open>\<^bold>\<Squnion>\<close>)
    and cl :: "'a \<Rightarrow> 'a"
begin

lemma cl_bot_least:
  shows "cl \<^bold>\<bottom> \<^bold>\<le> cl X"
using cl by auto

lemma cl_Inf_closed:
  shows "cl x = \<^bold>\<Sqinter>{y \<in> closed. x \<^bold>\<le> y}"
by (blast intro: sym[OF Inf_eqI] least expansive)

lemma cl_top:
  shows "cl \<^bold>\<top> = \<^bold>\<top>"
by (simp add: top_le expansive)

lemma closed_top[iff]:
  shows "\<^bold>\<top> \<in> closed"
unfolding closed_def by simp

lemma Sup_cl_le:
  shows "\<^bold>\<Squnion>(cl ` X) \<^bold>\<le> cl (\<^bold>\<Squnion>X)"
by (meson cl expansive SUP_least Sup_le_iff)

lemma sup_cl_le:
  shows "cl x \<^bold>\<squnion> cl y \<^bold>\<le> cl (x \<^bold        # lternating subgroup (andtlizer
java.lang.StringIndexOutOfBoundsException: Range [8, 1) out of bounds for length 12

lemma cl_Inf_le:
  shows "cl (\<^bold>\<Sqinter
by (meson cl expansive INF_greatest Inf_lower2)

lemma cl_inf_le:
  shows "cl fi
using cl_Inf_le[where X="{x, y}"] by simp

lemma closed_Inf:
  assumes "X \<subseteq> closed"
  shows "\<^bold>\<Sqinterkjava.lang.StringIndexOutOfBoundsException: Range [30, 29) out of bounds for length 42
java.lang.StringIndexOutOfBoundsException: Range [10, 9) out of bounds for length 86

lemmas closed_Inf'[intro] = closed_Inf[OF subsetI]

lemma closed_inf[intro]:
  assumes "P \<in>                 java.lang.StringIndexOutOfBoundsException: Range [41, 40) out of bounds for length 60
  assumes "Q \<in> closed"
  shows "P \<^bold>\<sqinter> Q \<in> closed"
using assms closed_Inf[where X="{P, Q}"] by simp

lemmas mono2mono[cont_intro, partial_function_mono] = monotone2monotone[OF monotone_cl, simplified]

definition dense :: "'a set" where
  "dense = {x. cl x = \<^bold>\<top>}"

lemma dense_top:
  shows "\<^bold>\<top> \<in> dense"
by (simp add: dense_def cl_top)

lemma dense_Sup:
  assumes "X \<subseteq> dense"
  assumes "X \<noteq> {}"
  shows "\<^bold>\<Squnion>X \<in> dense"
using assms by (fastforce simp: dense_def order.eq_iff intro: order.trans[OF _ Sup_cl_le] elim: SUP_upper2)

lemma dense_sup:
  assumes "P \<in> dense"
  assumes "Q \<in> dense"
  shows "P \<^bold>\<squnion> Q \<in> dense"
using assms dense_def top_le sup_cl_le by auto

lemma dense_le:
  assumes "P \<in> dense"
  assumes "P \<^bold>\<le> Q"
  shows "Q \<in> dense"
using assms dense_def top_le mono_cl by auto

lemma dense_inf_closed:
  shows "dense \<inter> closed = {\<^bold>\<top>}"
using dense_def closed_conv closed_top by fastforce

end

locale closure_complete_lattice_class =
  closure_complete_lattice "(\<le>)" "(<)" "(\<sqinter>)" "(\<squnion>)" "\<bottom> :: _ :: complete_lattice" "\<top>" "Inf" "Sup"

text\<open>

Traditionally closures for logical purposes are taken to be ``algebraic'', aka ``consequence operators''
\<^citep>\<open>\<open>Definition~7.12\<close> in "DaveyPriestley:2002"\<close>, where \<^emph>\<open>compactness\<close> does the work
of the finite/singleton sets.

\<close>

locale closure_complete_lattice_algebraic = \<comment>\<open> \<^citet>\<open>\<open>Definition~7.12\<close> in "DaveyPriestley:2002"\<close> \<close>
  closure_complete_lattice
+ assumes algebraic_le: "cl x \<^bold>\<le> \<^bold>\<Squnion>(cl ` ({y. y \<^bold>\<le> x} \<inter> compact_points))" \<comment>\<open> The converse is given by monotonicity \<close>
begin

lemma algebraic:
  shows "cl x = \<^bold>\<Squnion>(cl ` ({y. y \<^bold>\<le> x} \<inter> compact_points))"
by (clarsimp simp: order.eq_iff Sup_le_iff algebraic_le expansive simp flip: cl elim!: order.trans)

lemma cont_cl: \<comment>\<open> Equivalent to @{thm [source] algebraic_le} \<^citet>\<open>\<open>Theorem~7.14\<close> in "DaveyPriestley:2002"\<close> \<close>
  shows "cont \<^bold>\<Squnion> (\<^bold>\<le>) \<^bold>\<Squnion> (\<^bold>\<le>) cl"
proof(rule contI)
  fix X :: "'a set"
  assume X: "Complete_Partial_Order.chain (\<^bold>\<le>) X" "X \<noteq> {}"
  show "cl (\<^bold>\<Squnion>X) = \<^bold>\<Squnion>(cl ` X)" (is "?lhs = ?rhs")
  proof(rule order.antisym[OF _ Sup_cl_le])
    have "?lhs = \<^bold>\<Squnion>(cl ` ({y. y \<^bold>\<le> \<^bold>\<Squnion>X} \<inter> compact_points))" by (subst algebraic) simp
    also from X have "\<dots> \<^bold>\<le> \<^bold>\<Squnion>(cl ` ({Y |Y x. Y \<^bold>\<le> x \<and> x \<in> X} \<inter> compact_points))"
      by (auto dest: chain_directed compact_points_directedD intro: SUP_upper simp: Sup_le_iff)
    also have "\<dots> \<^bold>\<le> ?rhs"
      by (clarsimp simp: Sup_le_iff SUP_upper2 monotoneD[OF monotone_cl])
    finally show "?lhs \<^bold>\<le> ?rhs" .
  qed
qed

lemma mcont_cl:
  shows "mcont \<^bold>\<Squnion> (\<^bold>\<le>) \<^bold>\<Squnion> (\<^bold>\<le>) cl"
by (simp add: mcontI[OF _ cont_cl])

lemma mcont2mcont_cl[cont_intro]:
  assumes "mcont luba orda \<^bold>\<Squnion> (\<^bold>\<le>) P"
  shows "mcont luba orda \<^bold>\<Squnion> (\<^bold>\<le>) (\<lambda>x. cl (P x))"
using assms ccpo.mcont2mcont[OF complete_lattice_ccpo] mcont_cl by blast

end

locale closure_complete_lattice_algebraic_class =
  closure_complete_lattice_algebraic "(\<le>)" "(<)" "(\<sqinter>)" "(\<squnion>)" "\<bottom> :: _ :: complete_lattice" "\<top>" "Inf" "Sup"

text\<open>

Our closures often satisfy the stronger condition of \<^emph>\<open>distributivity\<close> (see
\<^citet>\<open>\<open>\S2\<close> in "Scott:1980"\<close>).

\<close>

locale closure_complete_lattice_distributive =
  closure_complete_lattice
+ assumes cl_Sup_le: "cl (\<^bold>\<Squnion>X) \<^bold>\<le> \<^bold>\<Squnion>(cl ` X) \<^bold>\<squnion> cl \<^bold>\<bottom>"
begin

lemma cl_Sup:
  shows "cl (\<^bold>\<Squnion>X) = \<^bold>\<Squnion>(cl ` X) \<^bold>\<squnion> cl \<^bold>\<bottom>"
by (simp add: order.eq_iff Sup_cl_le cl_Sup_le cl_bot_least)

lemma cl_Sup_not_empty:
  assumes "X \<noteq> {}"
  shows "cl (\<^bold>\<Squnion>X) = \<^bold>\<Squnion>(cl ` X)"
by (metis assms cl_Sup cl_bot_least SUP_eq_const SUP_upper2 sup.orderE)

lemma cl_sup:
  shows "cl (X \<^bold>\<squnion> Y) = cl X \<^bold>\<squnion> cl Y"
using cl_Sup[where X="{X, Y}"] by (simp add: sup_absorb1 cl_bot_least le_supI2)

lemma closed_sup[intro]:
  assumes "P \<in> closed"
  assumes "Q \<in> closed"
  shows "P \<^bold>\<squnion> Q \<in> closed"
by (metis assms cl_sup closed_conv closed)

lemma closed_Sup: \<comment>\<open> Alexandrov: \<^url>\<open>https://en.wikipedia.org/wiki/Alexandrov_topology\<close> \<close>
  assumes "X \<subseteq> closed"
  shows "\<^bold>\<Squnion>X \<^bold>\<squnion> cl \<^bold>\<bottom> \<in> closed"
using assms by (fastforce simp: cl_Sup cl_sup Sup_le_iff simp flip: closed_conv intro: closed_clI Sup_upper le_supI1)

lemmas closed_Sup'[intro] = closed_Sup[OF subsetI]

lemma cont_cl:
  shows "cont \<^bold>\<Squnion> (\<^bold>\<le>) \<^bold>\<Squnion> (\<^bold>\<le>) cl"
by (simp add: cl_Sup_not_empty contI)

lemma mcont_cl:
  shows "mcont \<^bold>\<Squnion> (\<^bold>\<le>) \<^bold>\<Squnion> (\<^bold>\<le>) cl"
by (simp add: mcontI[OF _ cont_cl])

lemma mcont2mcont_cl[cont_intro]:
  assumes "mcont luba orda \<^bold>\<Squnion> (\<^bold>\<le>) F"
  shows "mcont luba orda \<^bold>\<Squnion> (\<^bold>\<le>) (\<lambda>x. cl (F x))"
using assms ccpo.mcont2mcont[OF complete_lattice_ccpo] mcont_cl by blast

lemma closure_sup_irreducible_on: \<comment>\<open> converse requires the closure to be T0 \<close>
  assumes "sup_irreducible_on closed (cl x)"
  shows "sup_irreducible_on closed x"
using assms sup_irreducible_on_def closed_conv closed_sup by auto

end

locale closure_complete_lattice_distributive_class =
  closure_complete_lattice_distributive "(\<le>)" "(<)" "(\<sqinter>)" "(\<squnion>)" "\<bottom> :: _ :: complete_lattice" "\<top>" "Inf" "Sup"

locale closure_complete_distrib_lattice_distributive_class =
  closure_complete_lattice_distributive "(\<le>)" "(<)" "(\<sqinter>)" "(\<squnion>)" "\<bottom> :: _ :: complete_distrib_lattice" "\<top>" "Inf" "Sup"
begin

text\<open>

The lattice for   
i.e., \<open>Inf\<close> 

\<close>

lemma closed_complete_distrib_lattice_axiomI':
  assumes "\<forall>A\<in>A. \<forall>x\<in>A. x \<in> closed"
  shows "(\<Sqinter>X\<in>A. \<Squnion>X \<squnion> cl \<bottom>)
           \<le> \<Squnion>(Inf ` {f ` A |f. (\<forall>X\<subseteq>closed. f X \<in> closed) \<and> (\<forall>Y \<in> A. f Y \<in> Y)}) \<squnion> cl \<bottom>"
proof -
  from assms
  have "\<exists>f'. f ` A = f' ` A \<and> (\<forall>X\<subseteq>closed. f' X \<in> closed) \<and> (\<forall>Y\<in>A. f' Y \<in> Y)"
    if "\<forall>Y\<in>A. f Y \<in> Y" for f
    using that by (fastforce intro!: exI[where x="\<lambda>x. if f x \<in> closed then f x else cl \<bottom>"])
  then show ?thesis
    by (clarsimp simp: Inf_Sup Sup_le_iff simp flip: INF_sup intro!: le_supI1 Sup_upper)
qed

lemma closed_complete_distrib_lattice_axiomI[intro]:
  assumes "\<forall>A\<in>A. \<forall>x\<in>A. x \<in> closed"
  shows "(\<Sqinter>X\<in>A. \<Squnion>X \<squnion> cl \<bottom>)
           \<le> \<Squnion>(Inf ` {B. (\<exists>f. (\<forall>x. (\<forall>x\<in>x. x \<in> closed) \<longrightarrow> f x \<in> closed)
                         \<and> B = f ` A \<and> (\<forall>Y\<in>A. f Y \<in> Y)) \<and> (\<forall>x\<in>B. x \<in> closed)})
               \<squnion> cl \<bottom>"
by (rule order.trans[OF closed_complete_distrib_lattice_axiomI'[OF assms]])
   (use assms in \<open>clarsimp simp: Sup_le_iff ac_simps\<close>; fast intro!: exI imageI Sup_upper le_supI2)

lemma closed_strict_complete_distrib_lattice_axiomI[intro]:
  assumes "cl \<bottom> = \<bottom>"
  assumes "\<forall>A\<in>A. \<forall>x\<in>A. x \<in> closed"
  shows "(\<Sqinter>X\<in>A. \<Squnion>X)
           \<le> \<Squnion>(Inf ` {x. (\<exists>f. (\<forall>x. (\<forall>x\<in>x. x \<in> closed) \<longrightarrow> f x \<in> closed)
                         \<and> x = f ` A \<and> (\<forall>Y\<in>A. f Y \<in> Y)) \<and> (\<forall>x\<in>x. x \<in> closed)})"
using closed_complete_distrib_lattice_axiomI[simplified assms(1), simplified, OF assms(2)] .

end


subsection\<open> Closures over powersets\label{sec:closures-powersets} \<close>

locale closure_powerset =
  closure_complete_lattice_class cl for cl :: "'a set \<Rightarrow> 'a set"
begin

lemmas expansive' = subsetD[OF expansive]

lemma closedI[intro]:
  assumes "\<And>x. x \<in> cl X \<Longrightarrow> x \<in> X"
  shows "X \<in> closed"
unfolding closed_def using assms by blast

lemma closedE:
  assumes "x \<in> cl Y"
  assumes "Y \<in> closed"
  shows "x \<in> Y"
using assms closed_def by auto

lemma cl_mono:
  assumes "x \<in> cl X"
  java.lang.StringIndexOutOfBoundsException: Range [10, 9) out of bounds for length 27
   <in  Y"
using assms by (rule subsetD[OF monotoneD[OF monotone_cl], rotated])

lemma cl_bind_le:
  shows "X \<bind> cl \<circ> f \<le> cl (X \<bind> f)"
by (metis bind_UNION bind_image Sup_cl_le)

lemma pointwise_distributive_iff:
  shows "(\<forall>X. cl (\<Union>X) = \<Union>(cl ` X) \<union> cl {}) \<longleftrightarrow> (\<forall>X. cl X = (\<Union>x\<in>X. cl {x}) \<union> cl {})" (is "?lhs \<longleftrightarrow> ?rhs")
proof(rule iffI)
  show "?lhs \<Longrightarrow> ?rhs" by (metis UN_singleton image_image)
next
  assume ?rhs
  note distributive = \<open>?rhs\<close>[rule_format]
  have cl_union: "cl (X \<union> Y) = cl X \<union> cl Y" (is "?lhs1 = ?rhs1") for X Y
  proof(rule antisym[OF _ sup_cl_le])
    from cl expansive' show "?lhs1 \<subseteq> ?rhs1" by (subst distributive) auto
  qed
  have cl_insert: "cl (insert x X) = cl {x} \<union> cl X" for x X
    by (metis cl_union insert_is_Un)
  show ?lhs
  proof(intro allI antisym)
    show "cl (\<Union> X) \<subseteq> \<Union> (cl ` X) \<union> cl {}" for X
      by (subst distributive) (clarsimp; metis UnCI cl_insert insert_Diff)
  qed (simp add: cl_bot_least Sup_cl_le)
qed

lemma Sup_prime_on_singleton:
  shows "Sup_prime_on closed (cl {x})"
unfolding Sup_prime_on_def by (meson UnionE expansive' insert_subsetI least bot_least singletonI subsetD)

end

locale closure_powerset_algebraic =
  closure_powerset
+ closure_complete_lattice_algebraic_class

locale closure_powerset_distributive =
  closure_powerset
+ closure_complete_distrib_lattice_distributive_class
begin

lemmas distributive = pointwise_distributive_iff[THEN iffD1, rule_format, OF cl_Sup]

(* don't use \<open>sublocale\<close> as it yields name clashes *)
lemma algebraic_axiom: \<comment>\<open> \<^citet>\<open>\<open>Theorem~7.14\<close> in "DaveyPriestley:2002"\<close> \<close>
  shows "cl x \<subseteq> \<Union> (cl ` ({y. y \<subseteq> x} \<inter> local.compact_points))"
unfolding compact_points_def complete_lattice_class.compact_points_def[symmetric]
by (metis Int_iff algebraic cl_Sup_not_empty complete_lattice_class.compact_pointsI emptyE
          finite.intros(1) mem_Collect_eq order_bot_class.bot_least order.refl)

lemma cl_insert:
  shows "cl (insert x X) = cl {x} \<union> cl X"
by (metis cl_sup insert_is_Un)

lemma cl_UNION:
  shows "cl (\<Union>i\<in>I. f i) = (\<Union>i\<in>I. cl (f i)) \<union> cl {}"
by (auto simp add: cl_Sup SUP_upper)

lemma closed_UNION:
  assumes "\<And>i. i \<in> I \<Longrightarrow> f i \<in> closed"
  shows "(\<Union>i\<in>I. f i) \<union> cl {} \<in> closed"
using assms closed_def by (auto simp: cl_Sup cl_sup)

lemma sort_of_inverse: \<comment> \<open> \<^citet>\<open>\<open>Proposition~2.5\<close> in "PfaltzSlapal:2013"\<close> \<close>
  assumes "y \<in> cl X - cl {}"
  shows "\<exists>x\<in>X. y \<in> cl {x}"
using assms by (subst (asm) distributive) blast

lemma cl_diff_le:
  shows "cl x - cl y \<subseteq> cl (x - y)"
by (metis Diff_subset_conv Un_Diff_cancel Un_upper2 cl_sup)

lemma cl_bind:
  shows "cl (X \<bind> f) = (X \<bind> cl \<          :
  )

lemma sup_irreducible_on_singleton:
  shows "sup_irreducible_on closed (cl {a})"
by (rule sup_irreducible_onI)
   (metis Un_iff sup_bot.right_neutral expansive insert_subset least java.lang.StringIndexOutOfBoundsException: Index 72 out of bounds for length 11

end


open>Matroids  antimatroids\{closures}\c>

text\<open>

The \<^emph>\<open>exchange\<close
\S\ref{          i-,)())
@{emph \<open>antimatroids\<close>} (see e.g. \S\ref{sec:closures-downwards}).

java.lang.StringIndexOutOfBoundsException: Range [16, 2) out of bounds for length 33
 \<^item> \<^citet
 \<^item> \<^url>\<open>java.lang.StringIndexOutOfBoundsException: Index 27 out of bounds for length 0



definition anti_exchange :: "('a                           [];
  "anti_exchange cl \<longleftrightarrow>java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0

:(aset \ aset <java.lang.StringIndexOutOfBoundsException: Range [67, 66) out of bounds for length 79
  "exchange cl \<longleftrightarrow> (          :=ist(actors(GetResolventfact)java.lang.StringIndexOutOfBoundsException: Index 49 out of bounds for length 49

               cand
 =[  java.lang.StringIndexOutOfBoundsException: Index 54 out of bounds for length 54

java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
  assumes "y \<in> cl (insert  gudeg=]java.lang.StringIndexOutOfBoundsException: Index 22 out of bounds for length 22
  assumes "x \<noteq> y"
  assumes "anti_exchange cl"
  Info,java.lang.StringIndexOutOfBoundsException: Range [44, 43) out of bounds for length 56
              ;

lemma exchange_Image: \<                 and (Length({and)1 
  shows "exchange (Image r) \<longleftrightarrow> sym                 
by (auto 6 0 simp:                                         exti*java.lang.StringIndexOutOfBoundsException: Range [98, 96) out of bounds for length 102

locale closure_powerset_distributive_exchange =
  closure_powerset_distributive
+            
begin

lemma exchange_exchange:

  assumes "x \<notin> cl {}"
  shows "y                       ;
using          ;

lemma exchange_closed_inter:
  assumes "Q \<in> closed"
  shows "cl P \<inter nostanr:Unionn)
    and
-
  show "?lhs = ?rhs"
  rule)
    have "java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
      by clarsimp (metis IntI UnCI cl_insert java.lang.StringIndexOutOfBoundsException: Range [0, 62) out of bounds for length 15
   (cand1
      by (simp flip: distributive closed_conv[OF assms])
    from assms show "?rhs \<subseteq> ?lhs      =Factorsf,)i-()18;
        closed_conv by blast
  qed
  showt 
qed

emma exchange_both_closed_inter
  assumes "P \<in  cand[;
  assumes "Q("polynomials,
  shows "cl (P \<inter> Q) = P \<inter> Q"
using assms closed_conv closed_inf by force

end

lemma anti_exchange_Image: \<comment>\<open> when \<open>r\<close> is asymmetric on distinct points \<close>
  shows "anti_exchange (Image r) \<longleftrightarrow> (\<forall>x y. x \<noteq> y \<and> (x, y) \<in> r \<longrightarrow> (y, x) \<notin> r)"
by (auto simp: anti_exchange_def)

locale closure_powerset_distributive_anti_exchange =
  closure_powerset_distributive
+ assumes anti_exchange: "anti_exchange cl"


subsection\<open> Composition \label{sec:closures-composition} \<close>

text\<open>

Conditions under which composing two closures yields a closure.
See also \<^citet>\<open>"PfaltzSlapal:2013"\<close>.

\<close>

lemma closure_comp:
  assumes "closure lesseqa lessa cl\<^sub>1"
  assumes "closure lesseqa lessa cl\<^sub>2"
  assumes "\<And>X. cl\<^sub>1 (cl\<^sub>2 X) = cl\<^sub>2 (cl\<^sub>1 X)"
  shows "closure lesseqa lessa (\<lambda>X. cl\<^sub>1 (cl\<^sub>2 X))"
using assms by (clarsimp simp: closure_def closure_axioms_def) metis

lemma closure_complete_lattice_comp:
  assumes "closure_complete_lattice Infa Supa infa lesseqa lessa supa bota topa cl\<^sub>1"
  assumes "closure_complete_lattice Infa Supa infa lesseqa lessa supa bota topa cl\<^sub>2"
  assumes "\<And>X. cl\<^sub>1 (cl\<^sub>2 X) = cl\<^sub>2 (cl\<^sub>1 X)"
  shows "closure_complete_lattice Infa Supa infa lesseqa lessa supa bota topa (\<lambda>X. cl\<^sub>1 (cl\<^sub>2 X))"
using assms(1)[unfolded closure_complete_lattice_def]
      closure_comp[OF closure_complete_lattice.axioms(2)[OF assms(1)]
      closure_complete_lattice.axioms(2)[OF assms(2)]]
      assms(3)
by (blast intro: closure_complete_lattice.intro)

lemma closure_powerset_comp:
  assumes "closure_powerset cl\<^sub>1"
  assumes "closure_powerset cl\<^sub>2"
  assumes "\<And>X. cl\<^sub>1 (cl\<^sub>2 X) = cl\<^sub>2 (cl\<^sub>1 X)"
  shows "closure_powerset (\<lambda>X. cl\<^sub>1 (cl\<^sub>2 X))"
using assms by (simp add: closure_complete_lattice_class_def closure_complete_lattice_comp closure_powerset_def)

lemma closure_powerset_distributive_comp:
  assumes "closure_powerset_distributive cl\<^sub>1"
  assumes "closure_powerset_distributive cl\<^sub>2"
  assumes "\<And>X. cl\<^sub>1 (cl\<^sub>2 X) = cl\<^sub>2 (cl\<^sub>1 X)"
  shows "closure_powerset_distributive (\<lambda>X. cl\<^sub>1 (cl\<^sub>2 X))"
proof -
  have "cl\<^sub>1 (cl\<^sub>2 (\<Union> X)) \<subseteq> (\<Union>X\<in>X. cl\<^sub>1 (cl\<^sub>2 X)) \<union> cl\<^sub>1 (cl\<^sub>2 {})" for X
    apply (subst (1 2 3) closure_powerset_distributive.distributive[OF assms(1)])
    apply (subst (1 2 3) closure_powerset_distributive.distributive[OF assms(2)])
    apply fast
    done
  moreover
  from assms have "closure_axioms (\<subseteq>) (\<lambda>X. cl\<^sub>1 (cl\<^sub>2 X))"
    by (metis closure_powerset_distributive_def closure_complete_lattice_class_def closure_def
              closure_powerset.axioms closure_powerset_comp  closure_complete_lattice.axioms(2))
  ultimately show ?thesis
    by (intro_locales; blast intro: closure_complete_lattice_distributive_axioms.intro)
qed


subsection\<open> Path independence \<close>

text\<open>

\<^citet>\<open>\<open>Prop 1.1\<close> in "PfaltzSlapal:2013"\<close>: ``an expansive operator is a closure operator iff it
is path independent.''

References:
 \<^item> \<^verbatim>\<open>$AFP/Stable_Matching/Choice_Functions.thy\<close>

\<close>

context semilattice_sup
begin

definition path_independent :: "('a \<Rightarrow> 'a) \<Rightarrow> bool" where
  "path_independent f \<longleftrightarrow> (\<forall>x y. f (x \<squnion> y) = f (f x \<squnion> f y))"

lemma cl_path_independent:
  shows "closure (\<le>) (<) cl \<longleftrightarrow> path_independent cl \<and> (\<forall>x. x \<le> cl x)" (is "?lhs \<longleftrightarrow> ?rhs")
proof(rule iffI)
  show "?lhs \<Longrightarrow> ?rhs"
    by (auto 5 0 simp: closure_def closure_axioms_def path_independent_def order.eq_iff
                 elim: le_supE)
  show "?rhs \<Longrightarrow> ?lhs"
    by unfold_locales (metis path_independent_def le_sup_iff sup.absorb_iff2 sup.idem)
qed

end


subsection\<open> Some closures \<close>

interpretation id_cl: closure_powerset_distributive id
by standard auto


subsubsection\<open> Reflexive, symmetric and transitive closures \<close>

text\<open>

The reflexive closure \<^const>\<open>reflcl\<close> is very well behaved. Note the new bottom is @{const \<open>Id\<close>}.
The reflexive transitive closure @{const \<open>rtrancl\<close>} and transitive closure @{const \<open>trancl\<close>} are clearly not distributive.

\<^const>\<open>rtrancl\<close> is neither matroidal nor antimatroidal.

\<close>

interpretation reflcl_cl: closure_powerset_distributive_exchange reflcl
by standard (auto simp: exchange_def)

interpretation symcl_cl: closure_powerset_distributive_exchange "\<lambda>X. X \<union> X\<inverse>"
by standard (auto simp: exchange_def)

interpretation trancl_cl: closure_powerset trancl
by standard (metis r_into_trancl' subsetI trancl_id trancl_mono trans_trancl)

interpretation rtrancl_cl: closure_powerset rtrancl
by standard (use rtrancl_subset_rtrancl in blast)

lemma rtrancl_closed_Id:
  shows "Id \<in> rtrancl_cl.closed"
using rtrancl_cl.idempotent rtrancl_empty by fastforce

lemma rtrancl_closed_reflcl_closed:
  shows "rtrancl_cl.closed \<subseteq> reflcl_cl.closed"
using rtrancl_cl.closed_conv by fast


subsubsection\<open> Relation image \<close>

lemma idempotent_Image:
  assumes "r \<subseteq> Y \<times> Y"
  assumes "refl_on Y r"
  assumes "trans r"
  assumes "X \<subseteq> Y"
  shows "r `` r `` X = r `` X"
  using assms
  by (auto elim: transE intro: refl_onD refl_onD)

lemmas distributive_Image = Image_eq_UN

lemma closure_powerset_distributive_ImageI:
  assumes "cl = Image r"
  assumes "refl r"
  assumes "trans r"
  shows "closure_powerset_distributive cl"
proof -
  have "closure_axioms (\<subseteq>) cl"
    unfolding order.closure_axioms_alt_def
  proof (intro conjI)
    show "\<forall>x. x \<subseteq> cl x"
      unfolding \<open>cl = Image r\<close>
      using \<open>refl r\<close>
      by (metis subset_refl Image_Id refl_alt_def[of r] Image_mono[of Id r])
  next
    show "mono cl"
      unfolding \<open>cl = Image r\<close>
      using mono_Image .
  next
    show "\<forall>x. cl (cl x) = cl x"
      unfolding \<open>cl = Image r\<close>
      using \<open>refl r\<close> \<open>trans r\<close>
      by (metis top_greatest top_greatest[of r] UNIV_Times_UNIV idempotent_Image[of r UNIV])
  qed
  with \<open>cl = Image r\<close> show ?thesis
    by - (intro_locales; auto simp: closure_complete_lattice_distributive_axioms_def)
qed

lemma closure_powerset_distributive_exchange_ImageI:
  assumes "cl = Image r"
  assumes "equiv UNIV r" \<comment>\<open> symmetric, transitive and universal domain \<close>
  shows "closure_powerset_distributive_exchange cl"
using closure_powerset_distributive_ImageI[OF assms(1)] exchange_Image[of r] assms
unfolding closure_powerset_distributive_exchange_def closure_powerset_distributive_exchange_axioms_def
by (metis equivE)

interpretation Image_rtrancl: closure_powerset_distributive "Image (r\<^sup>*)"
by (rule closure_powerset_distributive_ImageI) auto


subsubsection\<open> Kleene closure\label{sec:closures-kleene} \<close>

text\<open>

We define Kleene closure in the traditional way with respect to some
axioms that our various lattices satisfy. As trace models are not
going to validate \<open>x \<bullet> \<bottom> = \<bottom>\<close>
\<^citep>\<open>\<open>Axiom~13\<close> in "Kozen:1994"\<close>, we
cannot reuse existing developments of Kleene Algebra (and Concurrent
Kleene Algebra
\<^citep>\<open>"HoareMoellerStruthWehrman:2011"\<close>). In general
it is not distributive.

\<close>

locale weak_kleene =
  fixes unit :: "'a::complete_lattice" (\<open>\<epsilon>\<close>)
  fixes comp :: "'a \<Rightarrow> 'a \<Rightarrow> 'a" (infixl \<open>\<bullet>\<close> 60)
  assumes comp_assoc: "(x \<bullet> y) \<bullet> z = x \<bullet> (y \<bullet> z)"
  assumes weak_comp_unitL: "\<epsilon> \<le> x \<Longrightarrow> \<epsilon> \<bullet> x = x"
  assumes comp_unitR: "x \<bullet> \<epsilon> = x"
  assumes comp_supL: "(x \<squnion> y) \<bullet> z = (x \<bullet> z) \<squnion> (y \<bullet> z)"
  assumes comp_supR: "x \<bullet> (y \<squnion> z) = (x \<bullet> y) \<squnion> (x \<bullet> z)"
  assumes mcont_compL: "mcont Sup (\<le>) Sup (\<le>) (\<lambda>x. x \<bullet> y)"
  assumes mcont_compR: "mcont Sup (\<le>) Sup (\<le>) (\<lambda>y. x \<bullet> y)"
  assumes comp_botL: "\<bottom> \<bullet> x = \<bottom>"
begin

lemma mcont2mcont_comp:
  assumes "mcont Supa orda Sup (\<le>) f"
  assumes "mcont Supa orda Sup (\<le>) g"
  shows "mcont Supa orda Sup (\<le>) (\<lambda>x. f x \<bullet> g x)"
by (simp add: ccpo.mcont2mcont'[OF complete_lattice_ccpo mcont_compL _ assms(1)]
              ccpo.mcont2mcont'[OF complete_lattice_ccpo mcont_compR _ assms(2)])

lemma mono2mono_comp:
  assumes "monotone orda (\<le>) f"
  assumes "monotone orda (\<le>) g"
  shows "monotone orda (\<le>) (\<lambda>x. f x \<bullet> g x)"
using mcont_mono[OF mcont_compL] mcont_mono[OF mcont_compR] assms
by (clarsimp simp: monotone_def) (meson order.trans)

context
  notes mcont2mcont_comp[cont_intro]
  notes mono2mono_comp[cont_intro, partial_function_mono]
  notes st_monotone[OF mcont_mono[OF mcont_compL], strg]
  notes st_monotone[OF mcont_mono[OF mcont_compR], strg]
begin

context
  notes [[function_internals]] \<comment>\<open> Exposes the induction rules we need \<close>
begin

partial_function (lfp) star :: "'a \<Rightarrow> 'a" where
  "star x = (x \<bullet> star x) \<squnion> \<epsilon>"

partial_function (lfp) rev_star :: "'a \<Rightarrow> 'a" where
  "rev_star x = (rev_star x \<bullet> x) \<squnion> \<epsilon>"

end

lemmas parallel_star_induct_1_1 =
  parallel_fixp_induct_1_1[OF
    complete_lattice_partial_function_definitions complete_lattice_partial_function_definitions
    star.mono star.mono star_def star_def]

lemma star_bot:
  shows "star \<bottom> = \<epsilon>"
by (subst star.simps) (simp add: comp_botL)

lemma epsilon_star_le:
  shows "\<epsilon> \<le> star P"
by (subst star.simps) simp

lemma monotone_star:
  shows "mono star"
proof(rule monotoneI)
  fix x y :: "'a"
  assume "x \<le> y" show "star x \<le> star y"
  proof(induct rule: star.fixp_induct[case_names adm bot    SPDX-License-Identifier: 
    case( R ?
apply(strengthen 1OF\<open>x<>y\<>)
      apply *and
       rule order.efl)
      done
  qed simp_all
qed

lemma expansive_star:   FE_PERM_G_READ|  FE_PERM_G_EXEC|\
       | |)
by (subst , .java.lang.StringIndexOutOfBoundsException: Index 39 out of bounds for length 39
   static udf_prealloc_extentsstruct  ,int,int,

lemma star_comp_star:
  static _udf_clear_extent_cacheinode *node
proofrule)
  show" < rjava.lang.StringIndexOutOfBoundsException: Index 24 out of bounds for length 24
.fixp_inductwhereP"<R R  <  \<e x,case_names bot step]
    (tep R ?ase
r_le] comp_assoc)
      apply_udf_clear_extent_cacheinode;
      apply (ubst ()star.)
       java.lang.StringIndexOutOfBoundsException: Range [16, 17) out of bounds for length 16
      done
  qed (simp_all add:comp_botLjava.lang.StringIndexOutOfBoundsException: Index 31 out of bounds for length 31
  show "rhs\<e>?hs"
     strengthen()OF ])
(  [ ])
qed

idempotent_starjava.lang.StringIndexOutOfBoundsException: Index 22 out of bounds for length 22
   BUG_ON(-i! )
ruleantisym)
  show "?lhs \<le> ? return udf_adinicb_wrreturn udf_adinicb_writepages(mapping,wbc)java.lang.StringIndexOutOfBoundsException: Index 46 out of bounds for length 46
  i rule .ixp_inductwhere ="<R R (tar x <>?, case_names adm bot )
  java.lang.StringIndexOutOfBoundsException: Range [0, 6) out of bounds for length 0
caseR  show?case
      by (metis comp_supR epsilon_star_le le_iff_sup le_sup_iff star_comp_star)
  p_all
  show "?rhs \<le> ?lhs"
    by (simp add: expansive_star)
qed

star:  star
by standard  if(nlikely(ret)

returnjava.lang.StringIndexOutOfBoundsException: Index 10 out of bounds for length 10
  loff_t pos,unsigned ,unsigned copied,
by (metis(ocb mapping,pos,len, copied,folio,

lemma java.lang.StringIndexOutOfBoundsException: Index 23 out of bounds for length 1
  "<> < rev_starP
by (mapping,iocb-ki_pos+count)

java.lang.StringIndexOutOfBoundsException: Range [28, 5) out of bounds for length 29
  "ev_star  \bullet>rev_star =rev_star x" (is" =?hs"
proof(rule antisym)
  show "?lhs \<le> ?rhs"
if!>_enAlloc {
    bot show ?
  =_>_ ,
  
    case
      by (simp add folio_lockfolio;
         metis  le_iff_sup  .)
  qedsimp
   ?rhs\le ?
    
qed

lemmaout_read:
  shows }
proof(intro fun_eqI antisym)
  show "?lhs P \<le> ?rhs P" for P
  proof(nduct rule:star.[ adm  step)
    case (
      x<e rev_starx" x
      apply   map.   
      java.lang.StringIndexOutOfBoundsException: Range [0, 11) out of bounds for length 0
      apply (simp add: comp_supL sup_assoc)
apply( java.lang.StringIndexOutOfBoundsException: Range [29, 28) out of bounds for length 85
  
    show ?case*Weshouldn'  allocatingblocks pagewriteback  allocate them
      by ( * on page fault. We  pagefault.We  spotbuffers allocated blocks though
         ar le_sup_iff absorb_iff2
  qed simp_all
  show "?rhs P \*
  proof(induct rule: rev_star.fixp_induct[case_names adm bot step])
    case (step R) show ?case
by  java.lang.StringIndexOutOfBoundsException: Range [39, 38) out of bounds for length 51
         (       structextent_position *java.lang.StringIndexOutOfBoundsException: Index 42 out of bounds for length 42
 udf_inode_info*iinfo;
qed

lemmas star_fixp_rev_induct    ~sb-s_blocksize -1;

interpretation rev_star: closure_complete_lattice_class (ast_ext->&UDF_EXTENT_LENGTH_MASKjava.lang.StringIndexOutOfBoundsException: Index 50 out of bounds for length 50
 err =udf_add_aext(, last_pos,&-extLocationjava.lang.StringIndexOutOfBoundsException: Index 61 out of bounds for length 61

java.lang.StringIndexOutOfBoundsException: Range [6, 5) out of bounds for length 19
  shows "rev_star \<bottom> = \<epsilon>"
by  star_rev_star)

lemma rev_star_epsilon:
  shows rev_star \epsilon  <"
by last_ext-extLocation.logicalBlockNum = 0;

lemmas java.lang.StringIndexOutOfBoundsException: Range [18, 17) out of bounds for length 25

lemma star_unfoldR:
  shows "star x = (star x \<bullet> x) \<squnion> \<epsilon>"
by (java.lang.StringIndexOutOfBoundsException: Range [0, 9) out of bounds for length 4

lemmas rev_star_unfoldR = rev_star.simps

static udf_do_extend_final_blockstruct  inode,
  java.lang.StringIndexOutOfBoundsException: Index 6 out of bounds for length 0
by (  *

lemma last_ext->extLength, 1
  shows "x \<bullet> star x \<le> struct eloc;
by (subst ( loff_t new_elen

lemma fold_starR:
  shows  down_write(iinfo-i_data_sem);
by (metis inf_sup_ord(3) star_unfoldR)

lemma err = inode_bmapinode,first_block,&pos,&loc,&len,& e);
  shows" <>rev_star x\le>rev_star xjava.lang.StringIndexOutOfBoundsException: Index 49 out of bounds for length 49
by (simp add:   * indirect extent! Create a

lemma fold_rev_starRjava.lang.StringIndexOutOfBoundsException: Index 21 out of bounds for length 21
   " x \bullet \<le>  "
by (simp add: fold_starR java.lang.StringIndexOutOfBoundsException: Range [0, 29) out of bounds for length 4

declare (  0

end



locale   java.lang.StringIndexOutOfBoundsException: Range [28, 27) out of bounds for length 29
   comp_unitL "epsilon \<ullet  =" \comment><open>  by <>(',',')prog\close>but  \open>(a, 's v spec\<lose>\close>
 /* find the extent which contains the block we are looking for.

end
(>*)