Theory More_Disjoint_Set_Forests

(* Title:      More on Disjoint-Set Forests
   Author:     Walter Guttmann
   Maintainer: Walter Guttmann <walter.guttmann at canterbury.ac.nz>
*)

theory More_Disjoint_Set_Forests

imports Disjoint_Set_Forests

begin

section ‹More on Array Access and Disjoint-Set Forests›

text ‹
This section contains further results about directed acyclic graphs and relational array operations.
›

context stone_relation_algebra
begin

lemma update_square:
  assumes "point y"
    shows "x[yx[[x[[y]]]]]  x * x  x"
proof -
  have "x[yx[[x[[y]]]]] = (y  yT * x * x)  (-y  x)"
    by (simp add: conv_dist_comp)
  also have "...  (y  yT) * x * x  x"
    by (smt assms inf.eq_refl inf.sup_monoid.add_commute inf_le1 sup_mono vector_inf_comp)
  also have "...  x * x  x"
    by (smt (z3) assms comp_associative conv_dist_comp coreflexive_comp_top_inf inf.cobounded2 sup_left_isotone symmetric_top_closed)
  finally show ?thesis
    .
qed

lemma update_ub:
  "x[yz]  x  zT"
  by (meson dual_order.trans inf.cobounded2 le_supI sup.cobounded1 sup_ge2)

lemma update_square_ub:
  "x[y(x * x)T]  x  x * x"
  by (metis conv_involutive update_ub)

lemma update_same_sub:
  assumes "u  x = u  z"
      and "y  u"
      and "regular y"
    shows "x[yzT] = x"
  by (smt (z3) assms conv_involutive inf.sup_monoid.add_commute inf.sup_relative_same_increasing maddux_3_11_pp)

lemma update_point_get:
  "point y  x[yz[[y]]] = x[yzT]"
  by (metis conv_involutive get_put inf_commute update_inf_same)

lemma update_bot:
  "x[botz] = x"
  by simp

lemma update_top:
  "x[topz] = zT"
  by simp

lemma update_same:
  assumes "regular u"
    shows "(x[yz])[uz] = x[y  uz]"
proof -
  have "(x[yz])[uz] = (u  zT)  (-u  y  zT)  (-u  -y  x)"
    using inf.sup_monoid.add_assoc inf_sup_distrib1 sup_assoc by force
  also have "... = (u  zT)  (y  zT)  (-(u  y)  x)"
    by (metis assms inf_sup_distrib2 maddux_3_21_pp p_dist_sup)
  also have "... = x[y  uz]"
    using comp_inf.mult_right_dist_sup sup_commute by auto
  finally show ?thesis
    .
qed

lemma update_same_3:
  assumes "regular u"
      and "regular v"
    shows "((x[yz])[uz])[vz] = x[y  u  vz]"
  by (metis assms update_same)

lemma update_split:
  assumes "regular w"
    shows "x[yz] = (x[y - wz])[y  wz]"
  by (smt (z3) assms comp_inf.semiring.distrib_left inf.left_commute inf.sup_monoid.add_commute inf_import_p maddux_3_11_pp maddux_3_12 p_dist_inf sup_assoc)

lemma update_injective_swap:
  assumes "injective x"
      and "point y"
      and "injective z"
      and "vector z"
    shows "injective ((x[yx[[z]]])[zx[[y]]])"
proof -
  have 1: "(z  yT * x) * (z  yT * x)T  1"
    using assms(3) injective_inf_closed by auto
  have "(z  yT * x) * (-z  y  zT * x)T  (z  yT * x) * (yT  xT * z)"
    by (metis conv_dist_comp conv_involutive conv_order inf.boundedE inf.boundedI inf.cobounded1 inf.cobounded2 mult_right_isotone)
  also have "... = (z  zT * x) * (yT  xT * y)"
    by (smt (z3) assms(2,4) covector_inf_comp_3 inf.left_commute inf.sup_monoid.add_commute comp_associative conv_dist_comp conv_involutive)
  also have "... = (z  zT) * x * xT * (y  yT)"
    by (smt (z3) assms(2,4) comp_associative inf.sup_monoid.add_commute vector_covector vector_inf_comp)
  also have "...  x * xT"
    by (metis assms(2-4) comp_associative comp_right_one coreflexive_comp_top_inf inf.coboundedI2 mult_right_isotone vector_covector)
  also have "...  1"
    by (simp add: assms(1))
  finally have 2: "(z  yT * x) * (-z  y  zT * x)T  1"
    .
  have "(z  yT * x) * (-z  -y  x)T  yT * x * (-yT  xT)"
    by (smt comp_isotone conv_complement conv_dist_inf inf.cobounded2 inf.sup_monoid.add_assoc)
  also have "... = yT * x * xT  -yT"
    by (simp add: inf.commute assms(2) covector_comp_inf vector_conv_compl)
  also have "...  yT  -yT"
    by (metis assms(1) comp_associative comp_inf.mult_left_isotone comp_isotone comp_right_one mult_sub_right_one)
  finally have 3: "(z  yT * x) * (-z  -y  x)T  1"
    using pseudo_complement by fastforce
  have 4: "(-z  y  zT * x) * (z  yT * x)T  1"
    using 2 conv_dist_comp conv_order by force
  have 5: "(-z  y  zT * x) * (-z  y  zT * x)T  1"
    by (simp add: assms(2) inf_assoc inf_left_commute injective_inf_closed)
  have "(-z  y  zT * x) * (-z  -y  x)T  zT * x * (-zT  xT)"
    using comp_inf.mult_left_isotone comp_isotone conv_complement conv_dist_inf inf.cobounded1 inf.cobounded2 by auto
  also have "... = zT * x * xT  -zT"
    by (metis assms(4) covector_comp_inf inf.sup_monoid.add_commute vector_conv_compl)
  also have "...  zT  -zT"
    by (metis assms(1) comp_associative comp_inf.mult_left_isotone comp_isotone comp_right_one mult_sub_right_one)
  finally have 6: "(-z  y  zT * x) * (-z  -y  x)T  1"
    using pseudo_complement by fastforce
  have 7: "(-z  -y  x) * (z  yT * x)T  1"
    using 3 conv_dist_comp coreflexive_symmetric by fastforce
  have 8: "(-z  -y  x) * (-z  y  zT * x)T  1"
    using 6 conv_dist_comp coreflexive_symmetric by fastforce
  have 9: "(-z  -y  x) * (-z  -y  x)T  1"
    using assms(1) inf.sup_monoid.add_commute injective_inf_closed by auto
  have "(x[yx[[z]]])[zx[[y]]] = (z  yT * x)  (-z  y  zT * x)  (-z  -y  x)"
    by (simp add: comp_inf.comp_left_dist_sup conv_dist_comp inf_assoc sup_monoid.add_assoc)
  hence "((x[yx[[z]]])[zx[[y]]]) * ((x[yx[[z]]])[zx[[y]]])T = ((z  yT * x)  (-z  y  zT * x)  (-z  -y  x)) * ((z  yT * x)T  (-z  y  zT * x)T  (-z  -y  x)T)"
    by (simp add: conv_dist_sup)
  also have "... = (z  yT * x) * ((z  yT * x)T  (-z  y  zT * x)T  (-z  -y  x)T) 
                   (-z  y  zT * x) * ((z  yT * x)T  (-z  y  zT * x)T  (-z  -y  x)T) 
                   (-z  -y  x) * ((z  yT * x)T  (-z  y  zT * x)T  (-z  -y  x)T)"
    using mult_right_dist_sup by auto
  also have "... = (z  yT * x) * (z  yT * x)T  (z  yT * x) * (-z  y  zT * x)T  (z  yT * x) * (-z  -y  x)T 
                   (-z  y  zT * x) * (z  yT * x)T  (-z  y  zT * x) * (-z  y  zT * x)T  (-z  y  zT * x) * (-z  -y  x)T 
                   (-z  -y  x) * (z  yT * x)T  (-z  -y  x) * (-z  y  zT * x)T  (-z  -y  x) * (-z  -y  x)T"
    using mult_left_dist_sup sup.left_commute sup_commute by auto
  also have "...  1"
    using 1 2 3 4 5 6 7 8 9 by simp_all
  finally show ?thesis
    .
qed

lemma update_injective_swap_2:
  assumes "injective x"
    shows "injective ((x[yx[[bot]]])[botx[[y]]])"
  by (simp add: assms inf.sup_monoid.add_commute injective_inf_closed)

lemma update_univalent_swap:
  assumes "univalent x"
      and "injective y"
      and "vector y"
      and "injective z"
      and "vector z"
    shows "univalent ((x[yx[[z]]])[zx[[y]]])"
  by (simp add: assms read_injective update_univalent)

lemma update_mapping_swap:
  assumes "mapping x"
      and "point y"
      and "point z"
    shows "mapping ((x[yx[[z]]])[zx[[y]]])"
  by (simp add: assms bijective_regular read_injective read_surjective update_total update_univalent)

text ‹lemma mapping_inf_point_arc› has been moved to theory Relation_Algebras› in entry Stone_Relation_Algebras›

end

context stone_kleene_relation_algebra
begin

lemma omit_redundant_points_2:
  assumes "point p"
  shows "p  x = (p  1)  (p  x  -pT) * (x  -pT)"
proof -
  let ?p = "p  1"
  let ?np = "-p  1"
  have 1: "p  x  1 = p  1"
    by (metis inf.le_iff_sup inf.left_commute inf.sup_monoid.add_commute star.circ_reflexive)
  have 2: "p  1  -pT = bot"
    by (smt (z3) inf_bot_right inf_commute inf_left_commute one_inf_conv p_inf)
  have "p  x  -1 = p  x  -pT"
    by (metis assms antisymmetric_inf_diversity inf.cobounded1 inf.sup_relative_same_increasing vector_covector)
  also have "... = (p  1  -pT)  ((p  x) * (-p  x)  -pT)"
    by (simp add: assms omit_redundant_points comp_inf.semiring.distrib_right)
  also have "... = (p  x) * (-p  x)  -pT"
    using 2 by simp
  also have "... = ?p * x * (-p  x)  -pT"
    by (metis assms vector_export_comp_unit)
  also have "... = ?p * x * (?np * x)  -pT"
    by (metis assms vector_complement_closed vector_export_comp_unit)
  also have "... = ?p * x * (?np * x) * ?np"
    by (metis assms conv_complement covector_comp_inf inf.sup_monoid.add_commute mult_1_right one_inf_conv vector_conv_compl)
  also have "... = ?p * x * ?np * (x * ?np)"
    using star_slide mult_assoc by auto
  also have "... = (?p * x  -pT) * (x * ?np)"
    by (metis assms conv_complement covector_comp_inf inf.sup_monoid.add_commute mult_1_right one_inf_conv vector_conv_compl)
  also have "... = (?p * x  -pT) * (x  -pT)"
    by (metis assms conv_complement covector_comp_inf inf.sup_monoid.add_commute mult_1_right one_inf_conv vector_conv_compl)
  also have "... = (p  x  -pT) * (x  -pT)"
    by (metis assms vector_export_comp_unit)
  finally show ?thesis
    using 1 by (metis maddux_3_11_pp regular_one_closed)
qed

lemma omit_redundant_points_3:
  assumes "point p"
  shows "p  x = (p  1)  (p  (x  -pT)+)"
  by (simp add: assms inf_assoc vector_inf_comp omit_redundant_points_2)

lemma even_odd_root:
  assumes "acyclic (x - 1)"
      and "regular x"
      and "univalent x"
    shows "(x * x)T  xT * (x * x)T = (1  x) * ((x * x)T  xT * (x * x)T)"
proof -
  have 1: "univalent (x * x)"
    by (simp add: assms(3) univalent_mult_closed)
  have "x  1  top * (x  1)"
    by (simp add: top_left_mult_increasing)
  hence "x  -(top * (x  1))  x - 1"
    using assms(2) p_shunting_swap pp_dist_comp by auto
  hence "x * (x  -(top * (x  1)))  (x - 1) * (x - 1)"
    using mult_right_isotone reachable_without_loops by auto
  also have "...  -1"
    by (simp add: assms(1) star_plus)
  finally have "(x  -(top * (x  1)))T  -x"
    using schroeder_4_p by force
  hence "xT  x  (top * (x  1))T"
    by (smt (z3) assms(2) conv_complement conv_dist_inf p_shunting_swap regular_closed_inf regular_closed_top regular_mult_closed regular_one_closed)
  also have "... = (1  x) * top"
    by (metis conv_dist_comp conv_dist_inf inf_commute one_inf_conv symmetric_one_closed symmetric_top_closed)
  finally have 2: "(xT  x) * top  (1  x) * top"
    by (metis inf.orderE inf.orderI inf_commute inf_vector_comp)
  have "1  xT+  (xT  1 * x) * xT"
    by (metis conv_involutive conv_star_commute dedekind_2 inf_commute)
  also have "...  (xT  x) * top"
    by (simp add: mult_right_isotone)
  also have "...  (1  x) * top"
    using 2 by simp
  finally have 3: "1  xT+  (1  x) * top"
    .
  have "xT  (xT * xT)+ = 1 * xT  (xT * xT) * xT * xT"
    using star_plus mult_assoc by auto
  also have "... = (1  (xT * xT) * xT) * xT"
    using assms(3) injective_comp_right_dist_inf by force
  also have "...  (1  xT * xT) * xT"
    by (meson comp_inf.mult_right_isotone comp_isotone inf.eq_refl star.circ_square)
  also have "...  (1  x) * top * xT"
    using 3 by (simp add: mult_left_isotone star_plus)
  also have "...  (1  x) * top"
    by (simp add: comp_associative mult_right_isotone)
  finally have 4: "xT  (xT * xT)+  (1  x) * top"
    .
  have "xT  (xT * xT) = (xT  1)  (xT  (xT * xT)+)"
    by (metis inf_sup_distrib1 star_left_unfold_equal)
  also have "...  (1  x) * top"
    using 4 by (metis inf.sup_monoid.add_commute le_supI one_inf_conv top_right_mult_increasing)
  finally have 4: "xT  (xT * xT)  (1  x) * top"
    .
  have "xT  (x * x)  -1  xT  x  -1"
    by (simp add: inf.coboundedI2 inf.sup_monoid.add_commute star.circ_square)
  also have "... = (x - 1)  (x - 1)T"
    using conv_complement conv_dist_inf inf_assoc inf_left_commute reachable_without_loops symmetric_one_closed by auto
  also have "... = bot"
    using assms(1) acyclic_star_below_complement_1 by auto
  finally have 5: "xT  (x * x)  -1 = bot"
    by (simp add: le_bot)
  have "xT  (x * x) = (xT  (x * x)  1)  (xT  (x * x)  -1)"
    by (metis maddux_3_11_pp regular_one_closed)
  also have "... = xT  (x * x)  1"
    using 5 by simp
  also have "... = xT  1"
    by (metis calculation comp_inf.semiring.distrib_left inf.sup_monoid.add_commute star.circ_transitive_equal star_involutive star_left_unfold_equal sup_inf_absorb)
  finally have "(xT  (x * x))  (xT  (xT * xT))  (1  x) * top"
    using 4 inf.sup_monoid.add_commute one_inf_conv top_right_mult_increasing by auto
  hence "xT  ((x * x)  (x * x)T)  (1  x) * top"
    by (simp add: comp_inf.semiring.distrib_left conv_dist_comp)
  hence 6: "xT  (x * x)T * (x * x)  (1  x) * top"
    using 1 by (simp add: cancel_separate_eq sup_commute)
  have "(x * x)T  xT * (x * x)T  (xT  (x * x)T * (x * x)) * (x * x)T"
    by (metis conv_involutive conv_star_commute dedekind_2 inf_commute)
  also have "...  (1  x) * top * (x * x)T"
    using 6 by (simp add: mult_left_isotone)
  also have "... = (1  x) * top"
    by (simp add: comp_associative star.circ_left_top)
  finally have "(x * x)T  xT * (x * x)T = (x * x)T  xT * (x * x)T  (1  x) * top"
    using inf.order_iff by auto
  also have "... = (1  x) * ((x * x)T  xT * (x * x)T)"
    by (metis coreflexive_comp_top_inf inf.cobounded1 inf.sup_monoid.add_commute)
  finally show ?thesis
    .
qed

lemma update_square_plus:
  "point y  x[yx[[x[[y]]]]]  x+"
  by (meson update_square comp_isotone dual_order.trans le_supI order_refl star.circ_increasing star.circ_mult_increasing)

lemma update_square_ub_plus:
  "x[y(x * x)T]  x+"
  by (simp add: comp_isotone inf.coboundedI2 star.circ_increasing star.circ_mult_increasing)

lemma acyclic_square:
  assumes "acyclic (x - 1)"
    shows "x * x  1 = x  1"
proof (rule order.antisym)
  have "1  x * x = 1  ((x - 1) * x  (x  1) * x)"
    by (metis maddux_3_11_pp regular_one_closed semiring.distrib_right)
  also have "...  1  ((x - 1) * x  x)"
    by (metis inf.cobounded2 mult_1_left mult_left_isotone inf.sup_right_isotone semiring.add_left_mono)
  also have "... = 1  ((x - 1) * (x - 1)  (x - 1) * (x  1)  x)"
    by (metis maddux_3_11_pp mult_left_dist_sup regular_one_closed)
  also have "...  (1  (x - 1) * (x - 1))  (x - 1) * (x  1)  x"
    by (metis inf_le2 inf_sup_distrib1 semiring.add_left_mono sup_monoid.add_assoc)
  also have "...  (1  (x - 1)+)  (x - 1) * (x  1)  x"
    by (metis comp_isotone inf.eq_refl inf.sup_right_isotone star.circ_increasing sup_monoid.add_commute sup_right_isotone)
  also have "... = (x - 1) * (x  1)  x"
    by (metis assms inf.le_iff_sup inf.sup_monoid.add_commute inf_import_p inf_p regular_one_closed sup_inf_absorb sup_monoid.add_commute)
  also have "... = x"
    by (metis comp_isotone inf.cobounded1 inf_le2 mult_1_right sup.absorb2)
  finally show "x * x  1  x  1"
    by (simp add: inf.sup_monoid.add_commute)
  show "x  1  x * x  1"
    by (metis coreflexive_idempotent inf_le1 inf_le2 le_infI mult_isotone)
qed

lemma diagonal_update_square_aux:
  assumes "acyclic (x - 1)"
      and "point y"
    shows "1  y  yT * x * x = 1  y  x"
proof -
  have 1: "1  y  x  yT * x * x"
    by (metis comp_isotone coreflexive_idempotent inf.boundedE inf.cobounded1 inf.cobounded2 one_inf_conv)
  have "1  y  yT * x * x = 1  (y  yT) * x * x"
    by (simp add: assms(2) inf.sup_monoid.add_assoc vector_inf_comp)
  also have "... = 1  (y  1) * x * x"
    by (metis assms(2) inf.cobounded1 inf.sup_monoid.add_commute inf.sup_same_context one_inf_conv vector_covector)
  also have "...  1  x * x"
    by (metis comp_left_subdist_inf inf.sup_right_isotone le_infE mult_left_isotone mult_left_one)
  also have "...  x"
    using assms(1) acyclic_square inf.sup_monoid.add_commute by auto
  finally show ?thesis
    using 1 by (metis inf.absorb2 inf.left_commute inf.sup_monoid.add_commute)
qed

lemma diagonal_update_square:
  assumes "acyclic (x - 1)"
      and "point y"
    shows "(x[yx[[x[[y]]]]])  1 = x  1"
proof -
  let ?xy = "x[[y]]"
  let ?xxy = "x[[?xy]]"
  let ?xyxxy = "x[y?xxy]"
  have "?xyxxy  1 = ((y  yT * x * x)  (-y  x))  1"
    by (simp add: conv_dist_comp)
  also have "... = (y  yT * x * x  1)  (-y  x  1)"
    by (simp add: inf_sup_distrib2)
  also have "... = (y  x  1)  (-y  x  1)"
    using assms by (smt (verit, ccfv_threshold) diagonal_update_square_aux find_set_precondition_def inf_assoc inf_commute)
  also have "... = x  1"
    by (metis assms(2) bijective_regular comp_inf.mult_right_dist_sup inf.sup_monoid.add_commute maddux_3_11_pp)
  finally show ?thesis
    .
qed

lemma fc_update_square:
  assumes "mapping x"
      and "point y"
    shows "fc (x[yx[[x[[y]]]]]) = fc x"
proof (rule order.antisym)
  let ?xy = "x[[y]]"
  let ?xxy = "x[[?xy]]"
  let ?xyxxy = "x[y?xxy]"
  have 1: "y  yT * x * x  x * x"
    by (smt (z3) assms(2) inf.cobounded2 inf.sup_monoid.add_commute inf.sup_same_context mult_1_left one_inf_conv vector_covector vector_inf_comp)
  have 2: "?xyxxy = (y  yT * x * x)  (-y  x)"
    by (simp add: conv_dist_comp)
  also have "...  x * x  x"
    using 1 inf_le2 sup_mono by blast
  also have "...  x"
    by (simp add: star.circ_increasing star.circ_mult_upper_bound)
  finally show "fc ?xyxxy  fc x"
    by (metis comp_isotone conv_order conv_star_commute star_involutive star_isotone)
  have 3: "y  x  1  fc ?xyxxy"
    using inf.coboundedI1 inf.sup_monoid.add_commute reflexive_mult_closed star.circ_reflexive by auto
  have 4: "y - 1  -yT"
    using assms(2) p_shunting_swap regular_one_closed vector_covector by auto
  have "y  x  yT * x"
    by (simp add: assms(2) vector_restrict_comp_conv)
  also have "...  yT * x * x * xT"
    by (metis assms(1) comp_associative mult_1_right mult_right_isotone total_var)
  finally have "y  x  -1  y  -yT  yT * x * x * xT"
    using 4 by (smt (z3) inf.cobounded1 inf.coboundedI2 inf.sup_monoid.add_assoc inf.sup_monoid.add_commute inf_greatest)
  also have "... = (y  yT * x * x) * xT  -yT"
    by (metis assms(2) inf.sup_monoid.add_assoc inf.sup_monoid.add_commute vector_inf_comp)
  also have "... = (y  yT * x * x) * (xT  -yT)"
    using assms(2) covector_comp_inf vector_conv_compl by auto
  also have "... = (y  yT * x * x) * (-y  x)T"
    by (simp add: conv_complement conv_dist_inf inf_commute)
  also have "...  ?xyxxy * (-y  x)T"
    using 2 by (simp add: comp_left_increasing_sup)
  also have "...  ?xyxxy * ?xyxxyT"
    by (simp add: conv_isotone mult_right_isotone)
  also have "...  fc ?xyxxy"
    using comp_isotone star.circ_increasing by blast
  finally have 5: "y  x  fc ?xyxxy"
    using 3 by (smt (z3) comp_inf.semiring.distrib_left inf.le_iff_sup maddux_3_11_pp regular_one_closed)
  have "x = (y  x)  (-y  x)"
    by (metis assms(2) bijective_regular inf.sup_monoid.add_commute maddux_3_11_pp)
  also have "...  fc ?xyxxy"
    using 5 dual_order.trans fc_increasing sup.cobounded2 sup_least by blast
  finally show "fc x  fc ?xyxxy"
    by (smt (z3) assms fc_equivalence fc_isotone fc_wcc read_injective star.circ_decompose_9 star_decompose_1 update_univalent)
qed

lemma acyclic_plus_loop:
  assumes "acyclic (x - 1)"
  shows "x+  1 = x  1"
proof -
  let ?r = "x  1"
  let ?i = "x - 1"
  have "x+  1 = (?i  ?r)+  1"
    by (metis maddux_3_11_pp regular_one_closed)
  also have "... = ((?i * ?r) * ?i+  (?i * ?r)+)  1"
    using plus_sup by auto
  also have "...  (?i+  (?i * ?r)+)  1"
    by (metis comp_associative dual_order.eq_iff maddux_3_11_pp reachable_without_loops regular_one_closed star.circ_plus_same star.circ_sup_9)
  also have "... = (?i * ?r)+  1"
    by (smt (z3) assms comp_inf.mult_right_dist_sup inf.absorb2 inf.sup_monoid.add_commute inf_le2 maddux_3_11_pp pseudo_complement regular_one_closed)
  also have "...  ?i * ?r  1"
    by (metis comp_associative dual_order.eq_iff maddux_3_11_pp reachable_without_loops regular_one_closed star.circ_sup_9 star_slide)
  also have "... = (?r  ?i+ * ?r)  1"
    using comp_associative star.circ_loop_fixpoint sup_commute by force
  also have "...  x  (?i+ * ?r  1)"
    by (metis comp_inf.mult_right_dist_sup inf.absorb1 inf.cobounded1 inf.cobounded2)
  also have "...  x  (-1 * ?r  1)"
    by (meson assms comp_inf.comp_isotone mult_left_isotone order.refl semiring.add_left_mono)
  also have "... = x"
    by (metis comp_inf.semiring.mult_not_zero comp_right_one inf.cobounded2 inf_sup_absorb mult_right_isotone pseudo_complement sup.idem sup_inf_distrib1)
  finally show ?thesis
    by (meson inf.sup_same_context inf_le1 order_trans star.circ_mult_increasing)
qed

lemma star_irreflexive_part_eq:
  "x - 1 = (x - 1)+ - 1"
  by (metis reachable_without_loops star_plus_without_loops)

lemma star_irreflexive_part:
  "x - 1  (x - 1)+"
  using star_irreflexive_part_eq by auto

lemma square_irreflexive_part:
  "x * x - 1  (x - 1)+"
proof -
  have "x * x = (x  1) * x  (x - 1) * x"
    by (metis maddux_3_11_pp mult_right_dist_sup regular_one_closed)
  also have "...  1 * x  (x - 1) * x"
    using comp_isotone inf.cobounded2 semiring.add_right_mono by blast
  also have "...  1  (x - 1)  (x - 1) * x"
    by (metis inf.cobounded2 maddux_3_11_pp mult_1_left regular_one_closed sup_left_isotone)
  also have "... = (x - 1) * (x  1)  1"
    by (simp add: mult_left_dist_sup sup_assoc sup_commute)
  finally have "x * x - 1  (x - 1) * (x  1)"
    using shunting_var_p by auto
  also have "... = (x - 1) * (x - 1)  (x - 1)"
    by (metis comp_right_one inf.sup_monoid.add_commute maddux_3_21_pp mult_left_dist_sup regular_one_closed sup_commute)
  also have "...  (x - 1)+"
    by (metis mult_left_isotone star.circ_increasing star.circ_mult_increasing star.circ_plus_same sup.bounded_iff)
  finally show ?thesis
    .
qed

lemma square_irreflexive_part_2:
  "x * x - 1  x - 1"
  using comp_inf.mult_left_isotone star.circ_increasing star.circ_mult_upper_bound by blast

lemma acyclic_update_square:
  assumes "acyclic (x - 1)"
  shows "acyclic ((x[y(x * x)T]) - 1)"
proof -
  have "((x[y(x * x)T]) - 1)+  ((x  x * x) - 1)+"
    by (metis comp_inf.mult_right_isotone comp_isotone inf.sup_monoid.add_commute star_isotone update_square_ub)
  also have "... = ((x - 1)  (x * x - 1))+"
    using comp_inf.semiring.distrib_right by auto
  also have "...  ((x - 1)+)+"
    by (smt (verit, del_insts) comp_isotone reachable_without_loops star.circ_mult_increasing star.circ_plus_same star.circ_right_slide star.circ_separate_5 star.circ_square star.circ_transitive_equal star.left_plus_circ sup.bounded_iff sup_ge1 square_irreflexive_part)
  also have "...  -1"
    using assms by (simp add: acyclic_plus)
  finally show ?thesis
    .
qed

lemma disjoint_set_forest_update_square:
  assumes "disjoint_set_forest x"
      and "vector y"
      and "regular y"
    shows "disjoint_set_forest (x[y(x * x)T])"
proof (intro conjI)
  show "univalent (x[y(x * x)T])"
    using assms update_univalent mapping_mult_closed univalent_conv_injective by blast
  show "total (x[y(x * x)T])"
    using assms update_total total_conv_surjective total_mult_closed by blast
  show "acyclic ((x[y(x * x)T]) - 1)"
    using acyclic_update_square assms(1) by blast
qed

lemma disjoint_set_forest_update_square_point:
  assumes "disjoint_set_forest x"
      and "point y"
    shows "disjoint_set_forest (x[y(x * x)T])"
  using assms disjoint_set_forest_update_square bijective_regular by blast

end

section ‹Verifying Further Operations on Disjoint-Set Forests›

text ‹
In this section we verify the init-sets, path-halving and path-splitting operations of disjoint-set forests.
›

class choose_point =
  fixes choose_point :: "'a  'a"

text ‹
Using the choose_point› operation we define a simple for-each-loop abstraction as syntactic sugar translated to a while-loop.
Regular vector h› describes the set of all elements that are yet to be processed.
It is made explicit so that the invariant can refer to it.
›

syntax
  "_Foreach" :: "idt  idt  'assn  'com  'com"  ("(1FOREACH _/ USING _/ INV {_} //DO _ /OD)" [0,0,0,0] 61)
translations "FOREACH x USING h INV { i } DO c OD" =>
  "h := CONST top;
   WHILE h  CONST bot
     INV { CONST regular h  CONST vector h  i }
     VAR { h }
      DO x := CONST choose_point h;
         c;
         h[x] := CONST bot
      OD"

class stone_kleene_relation_algebra_choose_point_finite_regular = stone_kleene_relation_algebra + finite_regular_p_algebra + choose_point +
  assumes choose_point_point: "vector x  x  bot  point (choose_point x)"
  assumes choose_point_decreasing: "choose_point x  --x"
begin

subclass stone_kleene_relation_algebra_tarski_finite_regular
proof unfold_locales
  fix x
  let ?p = "choose_point (x * top)"
  let ?q = "choose_point ((?p  x)T * top)"
  let ?y = "?p  ?qT"
  assume 1: "regular x" "x  bot"
  hence 2: "x * top  bot"
    using le_bot top_right_mult_increasing by auto
  hence 3: "point ?p"
    by (simp add: choose_point_point comp_associative)
  hence 4: "?p  bot"
    using 2 mult_right_zero by force
  have "?p  x  bot"
  proof
    assume "?p  x = bot"
    hence 5: "x  -?p"
      using p_antitone_iff pseudo_complement by auto
    have "?p  --(x * top)"
      by (simp add: choose_point_decreasing)
    also have "...  --(-?p * top)"
      using 5 by (simp add: comp_isotone pp_isotone)
    also have "... = -?p * top"
      using regular_mult_closed by auto
    also have "... = -?p"
      using 3 vector_complement_closed by auto
    finally have "?p = bot"
      using inf_absorb2 by fastforce
    thus False
      using 4 by auto
  qed
  hence "(?p  x)T * top  bot"
    by (metis comp_inf.semiring.mult_zero_left comp_right_one inf.sup_monoid.add_commute inf_top.left_neutral schroeder_1)
  hence "point ?q"
    using choose_point_point vector_top_closed mult_assoc by auto
  hence 6: "arc ?y"
    using 3 by (smt bijective_conv_mapping inf.sup_monoid.add_commute mapping_inf_point_arc)
  have "?q  --((?p  x)T * top)"
    by (simp add: choose_point_decreasing)
  hence "?y  ?p  --((?p  x)T * top)T"
    by (metis conv_complement conv_isotone inf.sup_right_isotone)
  also have "... = ?p  --(top * (?p  x))"
    by (simp add: conv_dist_comp)
  also have "... = ?p  top * (?p  x)"
    using 1 3 bijective_regular pp_dist_comp by auto
  also have "... = ?p  ?pT * x"
    using 3 by (metis comp_inf_vector conv_dist_comp inf.sup_monoid.add_commute inf_top_right symmetric_top_closed)
  also have "... = (?p  ?pT) * x"
    using 3 by (simp add: vector_inf_comp)
  also have "...  1 * x"
    using 3 point_antisymmetric mult_left_isotone by blast
  finally have "?y  x"
    by simp
  thus "top * x * top = top"
    using 6 by (smt (verit, ccfv_SIG) mult_assoc le_iff_sup mult_left_isotone semiring.distrib_left sup.orderE top.extremum)
qed

subsection ‹Init-Sets›

text ‹
A disjoint-set forest is initialised by applying make_set› to each node.
We prove that the resulting disjoint-set forest is the identity relation.
›

theorem init_sets:
  "VARS h p x
  [ True ]
  FOREACH x
    USING h
      INV { p - h = 1 - h }
       DO p := make_set p x
       OD
  [ p = 1  disjoint_set_forest p  h = bot ]"
proof vcg_tc_simp
  fix h p
  let ?x = "choose_point h"
  let ?m = "make_set p ?x"
  assume 1: "regular h  vector h  p - h = 1 - h  h  bot"
  show "vector (-?x  h) 
        ?m  (--?x  -h) = 1  (--?x  -h) 
        card { x . regular x  x  -?x  x  h } < h"
  proof (intro conjI)
    show "vector (-?x  h)"
      using 1 choose_point_point vector_complement_closed vector_inf_closed by blast
    have 2: "point ?x  regular ?x"
      using 1 bijective_regular choose_point_point by blast
    have 3: "-h  -?x"
      using choose_point_decreasing p_antitone_iff by auto
    have 4: "?x  ?m = ?x * ?xT  -?x  ?m = -?x  p"
      using 1 choose_point_point make_set_function make_set_postcondition_def by auto
    have "?m  (--?x  -h) = (?m  ?x)  (?m - h)"
      using 2 comp_inf.comp_left_dist_sup by auto
    also have "... = ?x * ?xT  (?m  -?x  -h)"
      using 3 4 by (smt (z3) inf_absorb2 inf_assoc inf_commute)
    also have "... = ?x * ?xT  (1 - h)"
      using 1 3 4 inf.absorb2 inf.sup_monoid.add_assoc inf_commute by auto
    also have "... = (1  ?x)  (1 - h)"
      using 2 by (metis inf.cobounded2 inf.sup_same_context one_inf_conv vector_covector)
    also have "... = 1  (--?x  -h)"
      using 2 comp_inf.semiring.distrib_left by auto
    finally show "?m  (--?x  -h) = 1  (--?x  -h)"
      .
    have 5: "¬ ?x  -?x"
      using 1 2 by (metis comp_commute_below_diversity conv_order inf.cobounded2 inf_absorb2 pseudo_complement strict_order_var top.extremum)
    have 6: "?x  h"
      using 1 by (metis choose_point_decreasing)
    show "card { x . regular x  x  -?x  x  h } < h"
      apply (rule psubset_card_mono)
      using finite_regular apply simp
      using 2 5 6 by auto
  qed
qed

end

subsection ‹Path Halving›

text ‹
Path halving is a variant of the path compression technique.
Similarly to path compression, we implement path halving independently of find-set, using a second while-loop which iterates over the same path to the root.
We prove that path halving preserves the equivalence-relational semantics of the disjoint-set forest and also preserves the roots of the component trees.
Additionally we prove the exact effect of path halving, which is to replace every other parent pointer with a pointer to the respective grandparent.
›

context stone_kleene_relation_algebra_tarski_finite_regular
begin

definition "path_halving_invariant p x y p0  
  find_set_precondition p x  point y  y  pT * x  y  (p0 * p0)T * x 
  p0[(p0 * p0)T * x - p0T * y(p0 * p0)T] = p 
  disjoint_set_forest p0"
definition "path_halving_postcondition p x y p0  
  disjoint_set_forest p  y = root p x  p  1 = p0  1  fc p = fc p0 
  p0[(p0 * p0)T * x(p0 * p0)T] = p"

lemma path_halving_invariant_aux_1:
  assumes "point x"
      and "point y"
      and "disjoint_set_forest p0"
  shows "p0  wcc (p0[(p0 * p0)T * x - p0T * y(p0 * p0)T])"
proof -
  let ?p2 = "p0 * p0"
  let ?p2t = "?p2T"
  let ?p2ts = "?p2t"
  let ?px = "?p2ts * x"
  let ?py = "-(p0T * y)"
  let ?pxy = "?px  ?py"
  let ?p = "p0[?pxy?p2t]"
  have 1: "regular ?pxy"
    using assms(1,3) bijective_regular find_set_precondition_def mapping_regular pp_dist_comp regular_closed_star regular_conv_closed path_halving_invariant_def by auto
  have 2: "vector x  vector ?px  vector ?py"
    using assms(1,2) find_set_precondition_def vector_complement_closed vector_mult_closed path_halving_invariant_def by auto
  have 3: "?pxy  p0  -?p2  -?pxT"
  proof -
    have 4: "injective x  univalent ?p2  regular p0"
      using assms(1,3) find_set_precondition_def mapping_regular univalent_mult_closed path_halving_invariant_def by auto
    have "?p2 * p0  1  p0+  1"
      using comp_inf.mult_left_isotone comp_isotone comp_right_one mult_sub_right_one star.circ_square star_slide by auto
    also have "...  p0"
      using acyclic_plus_loop assms(3) path_halving_invariant_def by auto
    finally have 5: "?p2 * p0  1  p0"
      .
    hence 6: "?p2ts * (1 - p0)  -p0"
      by (smt (verit, ccfv_SIG) conv_star_commute dual_order.trans inf.sup_monoid.add_assoc order.refl p_antitone_iff pseudo_complement schroeder_4_p schroeder_6_p)
    have "?p2t+ * p0  1 = ?p2ts * p0T * (p0T * p0)  1"
      by (metis conv_dist_comp star_plus mult_assoc)
    also have "...  ?p2ts * p0T  1"
      by (metis assms(3) comp_inf.mult_left_isotone comp_isotone comp_right_one mult_sub_right_one)
    also have "...  p0"
      using 5 by (metis conv_dist_comp conv_star_commute inf_commute one_inf_conv star_slide)
    finally have "?p2t+ * p0  -1  p0"
      by (metis regular_one_closed shunting_var_p sup_commute)
    hence 7: "?p2+ * (1 - p0)  -p0"
      by (smt (z3) conv_dist_comp conv_star_commute half_shunting inf.sup_monoid.add_assoc inf.sup_monoid.add_commute pseudo_complement schroeder_4_p schroeder_6_p star.circ_plus_same)
    have "(1  ?px) * top * (1  ?px  -p0) = ?px  top * (1  ?px  -p0)"
      using 2 by (metis inf_commute vector_inf_one_comp mult_assoc)
    also have "... = ?px  ?pxT * (1 - p0)"
      using 2 by (smt (verit, ccfv_threshold) covector_inf_comp_3 inf.sup_monoid.add_assoc inf.sup_monoid.add_commute inf_top.left_neutral)
    also have "... = ?px  xT * ?p2 * (1 - p0)"
      by (simp add: conv_dist_comp conv_star_commute)
    also have "... = (?px  xT) * ?p2 * (1 - p0)"
      using 2 vector_inf_comp by auto
    also have "... = ?p2ts * (x * xT) * ?p2 * (1 - p0)"
      using 2 vector_covector mult_assoc by auto
    also have "...  ?p2ts * ?p2 * (1 - p0)"
      using 4 by (metis inf.order_lesseq_imp mult_left_isotone star.circ_mult_upper_bound star.circ_reflexive)
    also have "... = (?p2ts  ?p2) * (1 - p0)"
      using 4 by (simp add: cancel_separate_eq)
    also have "... = (?p2ts  ?p2+) * (1 - p0)"
      by (metis star.circ_plus_one star_plus_loops sup_assoc sup_commute)
    also have "...  -p0"
      using 6 7 by (simp add: mult_right_dist_sup)
    finally have "(1  ?px)T * p0 * (1  ?px  -p0)T  bot"
      by (smt (z3) inf.boundedI inf_p top.extremum triple_schroeder_p)
    hence 8: "(1  ?px) * p0 * (1  ?px  -p0) = bot"
      by (simp add: coreflexive_inf_closed coreflexive_symmetric le_bot)
    have "?px  p0  ?pxT = (1  ?px) * p0  ?pxT"
      using 2 inf_commute vector_inf_one_comp by fastforce
    also have "... = (1  ?px) * p0 * (1  ?px)"
      using 2 by (metis comp_inf_vector mult_1_right vector_conv_covector)
    also have "... = (1  ?px) * p0 * (1  ?px  p0)  (1  ?px) * p0 * (1  ?px  -p0)"
      using 4 by (metis maddux_3_11_pp mult_left_dist_sup)
    also have "... = (1  ?px) * p0 * (1  ?px  p0)"
      using 8 by simp
    also have "...  ?p2"
      by (metis comp_isotone coreflexive_comp_top_inf inf.cobounded1 inf.cobounded2)
    finally have "?px  p0  -?p2  -?pxT"
      using 4 p_shunting_swap regular_mult_closed by fastforce
    thus ?thesis
      by (meson comp_inf.mult_left_isotone dual_order.trans inf.cobounded1)
  qed
  have "p0  ?p2 * p0T"
    by (metis assms(3) comp_associative comp_isotone comp_right_one eq_refl total_var)
  hence "?pxy  p0  -?p2  ?p2 * p0T"
    by (metis inf.coboundedI1 inf.sup_monoid.add_commute)
  hence "?pxy  p0  -?p2  ?pxy  ?p2 * p0T  -?pxT"
    using 3 by (meson dual_order.trans inf.boundedI inf.cobounded1)
  also have "... = (?pxy  ?p2) * p0T  -?pxT"
    using 2 vector_inf_comp by auto
  also have "... = (?pxy  ?p2) * (-?px  p0)T"
    using 2 by (simp add: covector_comp_inf inf.sup_monoid.add_commute vector_conv_compl conv_complement conv_dist_inf)
  also have "...  ?p * (-?px  p0)T"
    using comp_left_increasing_sup by auto
  also have "...  ?p * ?pT"
    by (metis comp_inf.mult_right_isotone comp_isotone conv_isotone inf.eq_refl inf.sup_monoid.add_commute le_supI1 p_antitone_inf sup_commute)
  also have "...  wcc ?p"
    using star.circ_sub_dist_2 by auto
  finally have 9: "?pxy  p0  -?p2  wcc ?p"
    .
  have "p0 = (?pxy  p0)  (-?pxy  p0)"
    using 1 by (metis inf.sup_monoid.add_commute maddux_3_11_pp)
  also have "...  (?pxy  p0)  ?p"
    using sup_right_isotone by auto
  also have "... = (?pxy  p0  -?p2)  (?pxy  p0  ?p2)  ?p"
    by (smt (z3) assms(3) maddux_3_11_pp mapping_regular pp_dist_comp path_halving_invariant_def)
  also have "...  (?pxy  p0  -?p2)  (?pxy  ?p2)  ?p"
    by (meson comp_inf.comp_left_subdist_inf inf.boundedE semiring.add_left_mono semiring.add_right_mono)
  also have "... = (?pxy  p0  -?p2)  ?p"
    using sup_assoc by auto
  also have "...  wcc ?p  ?p"
    using 9 sup_left_isotone by blast
  also have "...  wcc ?p"
    by (simp add: star.circ_sub_dist_1)
  finally show ?thesis
    .
qed

lemma path_halving_invariant_aux:
  assumes "path_halving_invariant p x y p0"
  shows "p[[y]] = p0[[y]]"
    and "p[[p[[y]]]] = p0[[p0[[y]]]]"
    and "p[[p[[p[[y]]]]]] = p0[[p0[[p0[[y]]]]]]"
    and "p  1 = p0  1"
    and "fc p = fc p0"
proof -
  let ?p2 = "p0 * p0"
  let ?p2t = "?p2T"
  let ?p2ts = "?p2t"
  let ?px = "?p2ts * x"
  let ?py = "-(p0T * y)"
  let ?pxy = "?px  ?py"
  let ?p = "p0[?pxy?p2t]"
  have "?p[[y]] = p0[[y]]"
    apply (rule put_get_different_vector)
    using assms find_set_precondition_def vector_complement_closed vector_inf_closed vector_mult_closed path_halving_invariant_def apply force
    by (meson inf.cobounded2 order_lesseq_imp p_antitone_iff path_compression_1b)
  thus 1: "p[[y]] = p0[[y]]"
    using assms path_halving_invariant_def by auto
  have "?p[[p0[[y]]]] = p0[[p0[[y]]]]"
    apply (rule put_get_different_vector)
    using assms find_set_precondition_def vector_complement_closed vector_inf_closed vector_mult_closed path_halving_invariant_def apply force
    by (metis comp_isotone inf.boundedE inf.coboundedI2 inf.eq_refl p_antitone_iff selection_closed_id star.circ_increasing)
  thus 2: "p[[p[[y]]]] = p0[[p0[[y]]]]"
    using 1 assms path_halving_invariant_def by auto
  have "?p[[p0[[p0[[y]]]]]] = p0[[p0[[p0[[y]]]]]]"
    apply (rule put_get_different_vector)
    using assms find_set_precondition_def vector_complement_closed vector_inf_closed vector_mult_closed path_halving_invariant_def apply force
    by (metis comp_associative comp_isotone conv_dist_comp conv_involutive conv_order inf.coboundedI2 inf.le_iff_sup mult_left_isotone p_antitone_iff p_antitone_inf star.circ_increasing star.circ_transitive_equal)
  thus "p[[p[[p[[y]]]]]] = p0[[p0[[p0[[y]]]]]]"
    using 2 assms path_halving_invariant_def by auto
  have 3: "regular ?pxy"
    using assms bijective_regular find_set_precondition_def mapping_regular pp_dist_comp regular_closed_star regular_conv_closed path_halving_invariant_def by auto
  have "p  1 = ?p  1"
    using assms path_halving_invariant_def by auto
  also have "... = (?pxy  ?p2  1)  (-?pxy  p0  1)"
    using comp_inf.semiring.distrib_right conv_involutive by auto
  also have "... = (?pxy  p0  1)  (-?pxy  p0  1)"
    using assms acyclic_square path_halving_invariant_def inf.sup_monoid.add_assoc by auto
  also have "... = (?pxy  -?pxy)  p0  1"
    using inf_sup_distrib2 by auto
  also have "... = p0  1"
    using 3 by (metis inf.sup_monoid.add_commute inf_sup_distrib1 maddux_3_11_pp)
  finally show "p  1 = p0  1"
    .
  have "p  p0+"
    by (metis assms path_halving_invariant_def update_square_ub_plus)
  hence 4: "fc p  fc p0"
    using conv_plus_commute fc_isotone star.left_plus_circ by fastforce
  have "wcc p0  wcc ?p"
    by (meson assms wcc_below_wcc path_halving_invariant_aux_1 path_halving_invariant_def find_set_precondition_def)
  hence "fc p0  fc ?p"
    using assms find_set_precondition_def path_halving_invariant_def fc_wcc by auto
  thus "fc p = fc p0"
    using 4 assms path_halving_invariant_def by auto
qed

lemma path_halving_1:
  "find_set_precondition p0 x  path_halving_invariant p0 x x p0"
proof -
  assume 1: "find_set_precondition p0 x"
  show "path_halving_invariant p0 x x p0"
  proof (unfold path_halving_invariant_def, intro conjI)
    show "find_set_precondition p0 x"
      using 1 by simp
    show "vector x" "injective x" "surjective x"
      using 1 find_set_precondition_def by auto
    show "x  p0T * x"
      by (simp add: path_compression_1b)
    show "x  (p0 * p0)T * x"
      by (simp add: path_compression_1b)
    have "(p0 * p0)T * x  p0T * x"
      by (simp add: conv_dist_comp mult_left_isotone star.circ_square)
    thus "p0[(p0 * p0)T * x - p0T * x(p0 * p0)T] = p0"
      by (smt (z3) inf.le_iff_sup inf_commute maddux_3_11_pp p_antitone_inf pseudo_complement)
    show "univalent p0" "total p0" "acyclic (p0 - 1)"
      using 1 find_set_precondition_def by auto
  qed
qed

lemma path_halving_2:
  "path_halving_invariant p x y p0  y  p[[y]]  path_halving_invariant (p[yp[[p[[y]]]]]) x ((p[yp[[p[[y]]]]])[[y]]) p0  ((p[yp[[p[[y]]]]])T * ((p[yp[[p[[y]]]]])[[y]])) < (pT * y)"
proof -
  let ?py = "p[[y]]"
  let ?ppy = "p[[?py]]"
  let ?pyppy = "p[y?ppy]"
  let ?p2 = "p0 * p0"
  let ?p2t = "?p2T"
  let ?p2ts = "?p2t"
  let ?px = "?p2ts * x"
  let ?py2 = "-(p0T * y)"
  let ?pxy = "?px  ?py2"
  let ?p = "p0[?pxy?p2t]"
  let ?pty = "p0T * y"
  let ?pt2y = "p0T * p0T * y"
  let ?pt2sy = "p0T * p0T * p0T * y"
  assume 1: "path_halving_invariant p x y p0  y  ?py"
  have 2: "point ?pty  point ?pt2y"
    using 1 by (smt (verit) comp_associative read_injective read_surjective path_halving_invariant_def)
  show "path_halving_invariant ?pyppy x (?pyppy[[y]]) p0  (?pyppyT * (?pyppy[[y]])) < (pT * y)"
  proof
    show "path_halving_invariant ?pyppy x (?pyppy[[y]]) p0"
    proof (unfold path_halving_invariant_def, intro conjI)
      show 3: "find_set_precondition ?pyppy x"
      proof (unfold find_set_precondition_def, intro conjI)
        show "univalent ?pyppy"
          using 1 find_set_precondition_def read_injective update_univalent path_halving_invariant_def by auto
        show "total ?pyppy"
          using 1 bijective_regular find_set_precondition_def read_surjective update_total path_halving_invariant_def by force
        show "acyclic (?pyppy - 1)"
          apply (rule update_acyclic_3)
          using 1 find_set_precondition_def path_halving_invariant_def apply blast
          using 1 2 comp_associative path_halving_invariant_aux(2) apply force
          using 1 path_halving_invariant_def apply blast
          by (metis inf.order_lesseq_imp mult_isotone star.circ_increasing star.circ_square mult_assoc)
        show "vector x" "injective x" "surjective x"
          using 1 find_set_precondition_def path_halving_invariant_def by auto
      qed
      show "vector (?pyppy[[y]])"
        using 1 comp_associative path_halving_invariant_def by auto
      show "injective (?pyppy[[y]])"
        using 1 3 read_injective path_halving_invariant_def find_set_precondition_def by auto
      show "surjective (?pyppy[[y]])"
        using 1 3 read_surjective path_halving_invariant_def find_set_precondition_def by auto
      show "?pyppy[[y]]  ?pyppyT * x"
      proof -
        have "y = (y  pT) * x"
          using 1 le_iff_inf vector_inf_comp path_halving_invariant_def by auto
        also have "... = ((y  1)  (y  (pT  -yT)+)) * x"
          using 1 omit_redundant_points_3 path_halving_invariant_def by auto
        also have "...  (1  (y  (pT  -yT)+)) * x"
          using 1 sup_inf_distrib2 vector_inf_comp path_halving_invariant_def by auto
        also have "...  (1  (pT  -yT)+) * x"
          by (simp add: inf.coboundedI2 mult_left_isotone)
        also have "... = (p  -y)T * x"
          by (simp add: conv_complement conv_dist_inf star_left_unfold_equal)
        also have "...  ?pyppyT * x"
          by (simp add: conv_isotone inf.sup_monoid.add_commute mult_left_isotone star_isotone)
        finally show ?thesis
          by (metis mult_isotone star.circ_increasing star.circ_transitive_equal mult_assoc)
      qed
      show "?pyppy[[y]]  ?px"
      proof -
        have "?pyppy[[y]] = p[[?py]]"
          using 1 put_get vector_mult_closed path_halving_invariant_def by force
        also have "... = p0[[p0[[y]]]]"
          using 1 path_halving_invariant_aux(2) by blast
        also have "... = ?p2t * y"
          by (simp add: conv_dist_comp mult_assoc)
        also have "...  ?p2t * ?px"
          using 1 path_halving_invariant_def comp_associative mult_right_isotone by force
        also have "...  ?px"
          by (metis comp_associative mult_left_isotone star.left_plus_below_circ)
        finally show ?thesis
          .
      qed
      show "p0[?px - p0T * (?pyppy[[y]])?p2t] = ?pyppy"
      proof -
        have "?px  ?pty = ?px  p0T * ?px  ?pty"
          using 1 inf.absorb2 inf.sup_monoid.add_assoc mult_right_isotone path_halving_invariant_def by force
        also have "... = (?p2ts  p0T * ?p2ts) * x  ?pty"
          using 3 comp_associative find_set_precondition_def injective_comp_right_dist_inf by auto
        also have "... = (1  p0) * (?p2ts  p0T * ?p2ts) * x  ?pty"
          using 1 even_odd_root mapping_regular path_halving_invariant_def by auto
        also have "...  (1  p0) * top  ?pty"
          by (metis comp_associative comp_inf.mult_left_isotone comp_inf.star.circ_sub_dist_2 comp_left_subdist_inf dual_order.trans mult_right_isotone)
        also have 4: "... = (1  p0T) * ?pty"
          using coreflexive_comp_top_inf one_inf_conv by auto
        also have "...  ?pt2y"
          by (simp add: mult_assoc mult_left_isotone)
        finally have 5: "?px  ?pty  ?pt2y"
          .
        have 6: "p[?px  -?pt2sy  ?pty?p2t] = p"
        proof (cases "?pty  ?px  -?pt2sy")
          case True
          hence "?pty  ?pt2y"
            using 5 conv_dist_comp inf.absorb2 by auto
          hence 7: "?pty = ?pt2y"
            using 2 epm_3 by fastforce
          have "p[?px  -?pt2sy  ?pty?p2t] = p[?pty?p2t]"
            using True inf.absorb2 by auto
          also have "... = p[?pty?p2[[?pty]]]"
            using 2 update_point_get by auto
          also have "... = p[?ptyp0T * p0T * p0T * y]"
            using comp_associative conv_dist_comp by auto
          also have "... = p[?pty?pt2y]"
            using 7 mult_assoc by simp
          also have "... = p[?ptyp[[?pty]]]"
            using 1 path_halving_invariant_aux(1,2) mult_assoc by force
          also have "... = p"
            using 2 get_put by auto
          finally show ?thesis
            .
        next
          case False
          have "mapping ?p2"
            using 1 mapping_mult_closed path_halving_invariant_def by blast
          hence 8: "regular (?px  -?pt2sy)"
            using 1 bijective_regular find_set_precondition_def mapping_regular pp_dist_comp regular_closed_star regular_conv_closed path_halving_invariant_def by auto
          have "vector (?px  -?pt2sy)"
            using 1 find_set_precondition_def vector_complement_closed vector_inf_closed vector_mult_closed path_halving_invariant_def by force
          hence "?pty  -(?px  -?pt2sy)"
            using 2 8 point_in_vector_or_complement False by blast
          hence "?px  -?pt2sy  ?pty = bot"
            by (simp add: p_antitone_iff pseudo_complement)
          thus ?thesis
            by simp
        qed
        have 9: "p[?px  -?pt2sy  y?p2t] = ?pyppy"
        proof (cases "y  -?pt2sy")
          case True
          hence "p[?px  -?pt2sy  y?p2t] = p[y?p2t]"
            using 1 inf.absorb2 path_halving_invariant_def by auto
          also have "... = ?pyppy"
            using 1 by (metis comp_associative conv_dist_comp path_halving_invariant_aux(2) path_halving_invariant_def update_point_get)
          finally show ?thesis
            .
        next
          case False
          have "vector (-?pt2sy)"
            using 1 vector_complement_closed vector_mult_closed path_halving_invariant_def by blast
          hence 10: "y  ?pt2sy"
            using 1 by (smt (verit, del_insts) False bijective_regular point_in_vector_or_complement regular_closed_star regular_mult_closed total_conv_surjective univalent_conv_injective path_halving_invariant_def)
          hence "?px  -?pt2sy  y = bot"
            by (simp add: inf.coboundedI2 p_antitone pseudo_complement)
          hence 11: "p[?px  -?pt2sy  y?p2t] = p"
            by simp
          have "y  p0T+ * y"
            using 10 by (metis mult_left_isotone order_lesseq_imp star.circ_plus_same star.left_plus_below_circ)
          hence 12: "y = root p0 y"
            using 1 loop_root_2 path_halving_invariant_def by blast
          have "?pyppy = p[yp0[[p0[[y]]]]]"
            using 1 path_halving_invariant_aux(2) by force
          also have "... = p[yp0[[y]]]"
            using 1 12 by (metis root_successor_loop path_halving_invariant_def)
          also have "... = p[y?py]"
            using 1 path_halving_invariant_aux(1) by force
          also have "... = p"
            using 1 get_put path_halving_invariant_def by blast
          finally show ?thesis
            using 11 by simp
        qed
        have 13: "-?pt2sy = -(p0T * y)  (-?pt2sy  ?pty)  (-?pt2sy  y)"
        proof (rule order.antisym)
          have 14: "regular (p0T * y)  regular ?pt2sy"
            using 1 by (metis order.antisym conv_complement conv_dist_comp conv_involutive conv_star_commute forest_components_increasing mapping_regular pp_dist_star regular_mult_closed top.extremum path_halving_invariant_def)
          have "p0T = p0T * p0T * p0T  p0T  1"
            using star.circ_back_loop_fixpoint star.circ_plus_same star_left_unfold_equal sup_commute by auto
          hence "p0T * y  ?pt2sy  ?pty  y"
            by (metis inf.eq_refl mult_1_left mult_right_dist_sup)
          also have "... = ?pt2sy  (-?pt2sy  ?pty)  y"
            using 14 by (metis maddux_3_21_pp)
          also have "... = ?pt2sy  (-?pt2sy  ?pty)  (-?pt2sy  y)"
            using 14 by (smt (z3) maddux_3_21_pp sup.left_commute sup_assoc)
          hence "p0T * y  -?pt2sy  (-?pt2sy  ?pty)  (-?pt2sy  y)"
            using calculation half_shunting sup_assoc sup_commute by auto
          thus "-?pt2sy  -(p0T * y)  (-?pt2sy  ?pty)  (-?pt2sy  y)"
            using 14 by (smt (z3) inf.sup_monoid.add_commute shunting_var_p sup.left_commute sup_commute)
          have "-(p0T * y)  -?pt2sy"
            by (meson mult_left_isotone order.trans p_antitone star.right_plus_below_circ)
          thus "-(p0T * y)  (-?pt2sy  ?pty)  (-?pt2sy  y)  -?pt2sy"
            by simp
        qed
        have "regular ?px" "regular ?pty" "regular y"
          using 1 bijective_regular find_set_precondition_def mapping_regular pp_dist_comp regular_closed_star regular_conv_closed path_halving_invariant_def by auto
        hence 15: "regular (?px  -?pt2sy  ?pty)" "regular (?px  -?pt2sy  y)"
          by auto
        have "p0[?px - p0T * (?pyppy[[y]])?p2t] = p0[?px - p0T * (p[[?py]])?p2t]"
          using 1 put_get vector_mult_closed path_halving_invariant_def by auto
        also have "... = p0[?px - ?pt2sy?p2t]"
          using 1 comp_associative path_halving_invariant_aux(2) by force
        also have "... = p0[?pxy  (?px  -?pt2sy  ?pty)  (?px  -?pt2sy  y)?p2t]"
          using 13 by (metis comp_inf.semiring.distrib_left inf.sup_monoid.add_assoc)
        also have "... = (?p[?px  -?pt2sy  ?pty?p2t])[?px  -?pt2sy  y?p2t]"
          using 15 by (smt (z3) update_same_3 comp_inf.semiring.mult_not_zero inf.sup_monoid.add_assoc inf.sup_monoid.add_commute)
        also have "... = (p[?px  -?pt2sy  ?pty?p2t])[?px  -?pt2sy  y?p2t]"
          using 1 path_halving_invariant_def by auto
        also have "... = p[?px  -?pt2sy  y?p2t]"
          using 6 by simp
        also have "... = ?pyppy"
          using 9 by auto
        finally show ?thesis
          .
      qed
      show "univalent p0" "total p0" "acyclic (p0 - 1)"
        using 1 path_halving_invariant_def by auto
    qed
    let ?s = "{ z . regular z  z  pT * y }"
    let ?t = "{ z . regular z  z  ?pyppyT * (?pyppy[[y]]) }"
    have "?pyppyT * (?pyppy[[y]]) = ?pyppyT * (p[[?py]])"
      using 1 put_get vector_mult_closed path_halving_invariant_def by force
    also have "...  p+T * (p[[?py]])"
      using 1 path_halving_invariant_def update_square_plus conv_order mult_left_isotone star_isotone by force
    also have "... = pT * pT * pT * y"
      by (simp add: conv_plus_commute star.left_plus_circ mult_assoc)
    also have "...  pT+ * y"
      by (metis mult_left_isotone star.left_plus_below_circ star_plus)
    finally have 16: "?pyppyT * (?pyppy[[y]])  pT+ * y"
      .
    hence "?pyppyT * (?pyppy[[y]])  pT * y"
      using mult_left_isotone order_lesseq_imp star.left_plus_below_circ by blast
    hence 17: "?t  ?s"
      using order_trans by auto
    have 18: "y  ?s"
      using 1 bijective_regular path_compression_1b path_halving_invariant_def by force
    have 19: "¬ y  ?t"
    proof
      assume "y  ?t"
      hence "y  ?pyppyT * (?pyppy[[y]])"
        by simp
      hence "y  pT+ * y"
        using 16 dual_order.trans by blast
      hence "y = root p y"
        using 1 find_set_precondition_def loop_root_2 path_halving_invariant_def by blast
      hence "y = ?py"
        using 1 by (metis find_set_precondition_def root_successor_loop path_halving_invariant_def)
      thus False
        using 1 by simp
    qed
    show "card ?t < card ?s"
      apply (rule psubset_card_mono)
      subgoal using finite_regular by simp
      subgoal using 17 18 19 by auto
      done
  qed
qed

lemma path_halving_3:
  "path_halving_invariant p x y p0  y = p[[y]]  path_halving_postcondition p x y p0"
proof -
  assume 1: "path_halving_invariant p x y p0  y = p[[y]]"
  show "path_halving_postcondition p x y p0"
  proof (unfold path_halving_postcondition_def, intro conjI)
    show "univalent p" "total p" "acyclic (p - 1)"
      using 1 find_set_precondition_def path_halving_invariant_def by blast+
    have "find_set_invariant p x y"
      using 1 find_set_invariant_def path_halving_invariant_def by blast
    thus "y = root p x"
      using 1 find_set_3 find_set_postcondition_def by blast
    show "p  1 = p0  1"
      using 1 path_halving_invariant_aux(4) by blast
    show "fc p = fc p0"
      using 1 path_halving_invariant_aux(5) by blast
    have 2: "y = p0[[y]]"
      using 1 path_halving_invariant_aux(1) by auto
    hence "p0T * y = y"
      using order.antisym path_compression_1b star_left_induct_mult_equal by auto
    hence 3: "p0[(p0 * p0)T * x - y(p0 * p0)T] = p"
      using 1 path_halving_invariant_def by auto
    have "(p0 * p0)T * y = y"
      using 2 mult_assoc conv_dist_comp by auto
    hence "y  p0 * p0 = y  p0"
      using 1 2 by (smt path_halving_invariant_def update_postcondition)
    hence 4: "y  p = y  p0 * p0"
      using 1 2 by (smt path_halving_invariant_def update_postcondition)
    have "p0[(p0 * p0)T * x(p0 * p0)T] = (p0[(p0 * p0)T * x - y(p0 * p0)T])[(p0 * p0)T * x  y(p0 * p0)T]"
      using 1 bijective_regular path_halving_invariant_def update_split by blast
    also have "... = p[(p0 * p0)T * x  y(p0 * p0)T]"
      using 3 by simp
    also have "... = p"
      apply (rule update_same_sub)
      using 4 apply simp
      apply simp
      using 1 bijective_regular inf.absorb2 path_halving_invariant_def by auto
    finally show "p0[(p0 * p0)T * x(p0 * p0)T] = p"
      .
  qed
qed

theorem find_path_halving:
  "VARS p y
  [ find_set_precondition p x  p0 = p ]
  y := x;
  WHILE y  p[[y]]
    INV { path_halving_invariant p x y p0 }
    VAR { (pT * y) }
     DO p[y] := p[[p[[y]]]];
        y := p[[y]]
     OD
  [ path_halving_postcondition p x y p0 ]"
  apply vcg_tc_simp
    apply (fact path_halving_1)
   apply (fact path_halving_2)
  by (fact path_halving_3)

subsection ‹Path Splitting›

text ‹
Path splitting is another variant of the path compression technique.
We implement it again independently of find-set, using a second while-loop which iterates over the same path to the root.
We prove that path splitting preserves the equivalence-relational semantics of the disjoint-set forest and also preserves the roots of the component trees.
Additionally we prove the exact effect of path splitting, which is to replace every parent pointer with a pointer to the respective grandparent.
›

definition "path_splitting_invariant p x y p0  
  find_set_precondition p x  point y  y  p0T * x 
  p0[p0T * x - p0T * y(p0 * p0)T] = p 
  disjoint_set_forest p0"
definition "path_splitting_postcondition p x y p0  
  disjoint_set_forest p  y = root p x  p  1 = p0  1  fc p = fc p0 
  p0[p0T * x(p0 * p0)T] = p"

lemma path_splitting_invariant_aux_1:
  assumes "point x"
      and "point y"
      and "disjoint_set_forest p0"
    shows "(p0[p0T * x - p0T * y(p0 * p0)T])  1 = p0  1"
      and "fc (p0[p0T * x - p0T * y(p0 * p0)T]) = fc p0"
      and "p0T * x  p0 * root p0 x"
proof -
  let ?p2 = "p0 * p0"
  let ?p2t = "?p2T"
  let ?px = "p0T * x"
  let ?py = "-(p0T * y)"
  let ?pxy = "?px  ?py"
  let ?q1 = "?pxy  p0"
  let ?q2 = "-?pxy  p0"
  let ?q3 = "?pxy  ?p2"
  let ?q4 = "-?pxy  ?p2"
  let ?p = "p0[?pxy?p2t]"
  let ?r0 = "root p0 x"
  let ?rp = "root ?p x"
  have 1: "regular ?px  regular (p0T * y)  regular ?pxy"
    using assms bijective_regular find_set_precondition_def mapping_regular pp_dist_comp regular_closed_star regular_conv_closed path_halving_invariant_def regular_closed_inf by auto
  have 2: "vector x  vector ?px  vector ?py  vector ?pxy"
    using assms(1,2) find_set_precondition_def vector_complement_closed vector_mult_closed path_halving_invariant_def vector_inf_closed by auto
  have 3: "?r0  p0 * ?r0"
    by (metis assms(3) dedekind_1 inf.le_iff_sup root_successor_loop top_greatest)
  hence "?pxy  p0 * ?r0  ?pxy  ?p2 * ?r0"
    by (metis comp_associative inf.eq_refl inf.sup_right_isotone mult_isotone)
  hence 4: "?q1 * ?r0  ?q3 * ?r0"
    using 2 by (simp add: vector_inf_comp)
  have 5: "?q1 * ?q2  ?q3"
    using 2 by (smt (z3) comp_isotone inf.cobounded1 inf.cobounded2 inf_greatest vector_export_comp)
  have "?q1 * ?q2 * ?r0 = ?q1 * ?r0  ?q1 * ?q2 * ?q2 * ?r0"
    by (metis comp_associative semiring.distrib_left star.circ_loop_fixpoint sup_commute)
  also have "...  ?q1 * ?r0  ?q3 * ?q2 * ?r0"
    using 5 by (meson mult_left_isotone sup_right_isotone)
  also have "...  ?q3 * ?r0  ?q3 * ?q2 * ?r0"
    using 4 sup_left_isotone by blast
  also have "... = ?q3 * ?q2 * ?r0"
    by (smt (verit, del_insts) comp_associative semiring.distrib_left star.circ_loop_fixpoint star.circ_transitive_equal star_involutive sup_commute)
  finally have 6: "?q1 * ?q2 * ?r0  ?q3 * ?q2 * ?r0"
    .
  have "?q1 * (-?pxy  p0+) * ?pxy  (?px  p0) * (-?pxy  p0+) * ?pxy"
    by (meson comp_inf.comp_left_subdist_inf inf.boundedE mult_left_isotone)
  also have "...  (?px  p0) * (-?pxy  p0+) * ?py"
    by (simp add: mult_right_isotone)
  also have "...  ?pxT * (-?pxy  p0+) * ?py"
  proof -
    have "?px  p0  ?pxT * p0"
      using 2 by (simp add: vector_restrict_comp_conv)
    also have "...  ?pxT"
      by (metis comp_associative conv_dist_comp conv_involutive conv_star_commute mult_right_isotone star.circ_increasing star.circ_transitive_equal)
    finally show ?thesis
      using mult_left_isotone by auto
  qed
  also have "... = top * (?px  -?pxy  p0+) * ?py"
    using 2 by (smt (z3) comp_inf.star_plus conv_dist_inf covector_inf_comp_3 inf_top.right_neutral vector_complement_closed vector_inf_closed)
  also have "...  top * (-?py  p0+) * ?py"
    by (metis comp_inf.comp_isotone comp_isotone inf.cobounded2 inf.eq_refl inf_import_p)
  also have "... = top * (-?py  p0+  ?pyT) * top"
    using 2 by (simp add: comp_associative covector_inf_comp_3)
  also have "... = bot"
  proof -
    have "p0T * y - yT * p0 = p0T * y * yT * -p0"
      using 2 by (metis assms(2) bijective_conv_mapping comp_mapping_complement vector_covector vector_export_comp vector_mult_closed)
    also have "...  p0T * -p0"
      by (meson assms(2) mult_left_isotone order_refl shunt_bijective)
    also have "...  -p0"
      by (simp add: conv_complement conv_star_commute pp_increasing schroeder_6_p star.circ_transitive_equal)
    also have "...  -p0+"
      by (simp add: p_antitone star.left_plus_below_circ)
    finally have "-?py  p0+  ?pyT = bot"
      by (metis comp_inf.p_pp_comp conv_complement conv_dist_comp conv_involutive conv_star_commute p_shunting_swap pp_isotone pseudo_complement_pp regular_closed_p)
    thus ?thesis
      by simp
  qed
  finally have 7: "?q1 * (-?pxy  p0+) * ?pxy = bot"
    using le_bot by blast
  have "?q2+  -?pxy"
    using 2 by (smt (z3) comp_isotone complement_conv_sub inf.order_trans inf.sup_right_divisibility inf_commute symmetric_top_closed top_greatest)
  hence "?q2+  -?pxy  p0+"
    by (simp add: comp_isotone star_isotone)
  hence 8: "?q1 * ?q2+ * ?pxy = bot"
    using 7 mult_left_isotone mult_right_isotone le_bot by auto
  have "?q1 * ?q2+ * ?q3 = ?q1 * ?q2+  ?q1 * ?q2+ * ?q3+"
    by (smt (z3) comp_associative star.circ_back_loop_fixpoint star.circ_plus_same sup_commute)
  also have "...  ?q1 * ?q2+  ?q1 * ?q2+ * ?pxy"
    using 2 by (smt (z3) inf.cobounded1 mult_right_isotone sup_right_isotone vector_inf_comp)
  finally have 9: "?q1 * ?q2+ * ?q3  ?q1 * ?q2+"
    using 8 by simp
  have 10: "?q1 * ?q4 * ?pxy = bot"
  proof -
    have "?p2  p0+"
      by (simp add: mult_right_isotone star.circ_increasing)
    thus ?thesis
      using 7 by (metis mult_left_isotone mult_right_isotone le_bot comp_inf.comp_isotone eq_refl)
  qed
  have 11: "?q1 * ?q2 * ?pxy = bot"
  proof -
    have "p0  p0+"
      by (simp add: star.circ_mult_increasing)
    thus ?thesis
      using 7 by (metis mult_left_isotone mult_right_isotone le_bot comp_inf.comp_isotone eq_refl)
  qed
  have 12: "?q2  p0 * ?q3 * ?q2"
    by (smt (verit, del_insts) conv_dist_comp conv_order conv_star_commute inf.coboundedI1 inf.orderE inf.sup_monoid.add_commute path_compression_1b)
  have "?q3 * p0 * ?q3 * ?q2 = ?q1 * p0 * p0 * ?q3 * ?q2"
    using 2 vector_inf_comp by auto
  also have "... = ?q1 * (?q3  ?q4) * ?q3 * ?q2"
    using 1 by (smt (z3) comp_associative comp_inf.mult_right_dist_sup comp_inf.star_slide inf_top.right_neutral regular_complement_top)
  also have "... = ?q1 * ?q3 * ?q3 * ?q2  ?q1 * ?q4 * ?q3 * ?q2"
    using mult_left_dist_sup mult_right_dist_sup by auto
  also have "...  ?q1 * ?q3 * ?q2  ?q1 * ?q4 * ?q3 * ?q2"
    by (smt (z3) mult_left_isotone mult_left_sub_dist_sup_right sup_left_isotone sup_right_divisibility mult_assoc star.left_plus_below_circ)
  also have "... = ?q1 * ?q3 * ?q2  ?q1 * ?q4 * ?q2  ?q1 * ?q4 * ?q3+ * ?q2"
    by (smt (z3) semiring.combine_common_factor star.circ_back_loop_fixpoint star_plus sup_monoid.add_commute mult_assoc)
  also have "...  ?q1 * ?q3 * ?q2  ?q1 * ?q4 * ?q2  ?q1 * ?q4 * ?pxy * ?q3 * ?q2"
    by (smt (verit, ccfv_threshold) comp_isotone inf.sup_right_divisibility inf_commute order.refl semiring.add_left_mono mult_assoc)
  also have "... = ?q1 * ?q3 * ?q2  ?q1 * ?q4 * ?q2"
    using 10 by simp
  also have "... = ?q1 * ?q3 * ?q2  ?q1 * ?q2 * p0 * ?q2"
    using 2 by (smt vector_complement_closed vector_inf_comp mult_assoc)
  also have "... = ?q1 * ?q3 * ?q2  ?q1 * ?q2 * (?q2  ?q1) * ?q2"
    using 1 by (smt (z3) comp_associative comp_inf.mult_right_dist_sup comp_inf.star_slide inf_top.right_neutral regular_complement_top)
  also have "... = ?q1 * ?q3 * ?q2  ?q1 * ?q2 * ?q2 * ?q2  ?q1 * ?q2 * ?q1 * ?q2"
    using mult_left_dist_sup mult_right_dist_sup sup_commute sup_left_commute by auto
  also have "...  ?q1 * ?q3 * ?q2  ?q1 * ?q2 * ?q2 * ?q2  ?q1 * ?q2 * ?pxy * ?q2"
    by (smt (verit, ccfv_threshold) comp_isotone inf.sup_right_divisibility inf_commute order.refl semiring.add_left_mono mult_assoc)
  also have "... = ?q1 * ?q3 * ?q2  ?q1 * ?q2 * ?q2 * ?q2"
    using 11 by simp
  also have "...  ?q1 * ?q3 * ?q2  ?q1 * ?q2"
    by (smt comp_associative comp_isotone mult_right_isotone star.circ_increasing star.circ_transitive_equal star.left_plus_below_circ sup_right_isotone)
  also have "... = ?q1 * ?q3 * ?q2"
    by (smt (verit, best) comp_associative semiring.distrib_left star.circ_loop_fixpoint star.circ_transitive_equal star_involutive)
  finally have 13: "?q3 * p0 * ?q3 * ?q2  p0 * ?q3 * ?q2"
    by (meson inf.cobounded2 mult_left_isotone order_lesseq_imp)
  hence "?q3 * p0 * ?q3 * ?q2  ?q2  p0 * ?q3 * ?q2"
    using 12 by simp
  hence "?q3 * ?q2  p0 * ?q3 * ?q2"
    by (simp add: star_left_induct mult_assoc)
  hence "?q1 * ?q3 * ?q2  ?q1 * p0 * ?q3 * ?q2"
    by (simp add: comp_associative mult_right_isotone)
  hence "?q1 * ?q3 * ?q2  ?q3+ * ?q2"
    using 2 by (simp add: vector_inf_comp)
  hence 14: "?q1 * ?q3 * ?q2  ?q3 * ?q2"
    using mult_left_isotone order_lesseq_imp star.left_plus_below_circ by blast
  have "p0 * ?r0  p0 * ?q3 * ?q2 * ?r0"
    by (metis comp_associative mult_1_right mult_left_isotone mult_right_isotone reflexive_mult_closed star.circ_reflexive)
  hence 15: "?r0  p0 * ?q3 * ?q2 * ?r0"
    using 3 dual_order.trans by blast
  have "?q3 * p0 * ?q3 * ?q2 * ?r0  p0 * ?q3 * ?q2 * ?r0"
    using 13 mult_left_isotone by blast
  hence "?q3 * p0 * ?q3 * ?q2 * ?r0  ?r0  p0 * ?q3 * ?q2 * ?r0"
    using 15 by simp
  hence "?q3 * ?r0  p0 * ?q3 * ?q2 * ?r0"
    by (simp add: star_left_induct mult_assoc)
  hence "?q1 * ?q3 * ?r0  ?q1 * p0 * ?q3 * ?q2 * ?r0"
    by (simp add: comp_associative mult_right_isotone)
  hence "?q1 * ?q3 * ?r0  ?q3+ * ?q2 * ?r0"
    using 2 by (simp add: vector_inf_comp)
  hence 16: "?q1 * ?q3 * ?r0  ?q3 * ?q2 * ?r0"
    using mult_left_isotone order_lesseq_imp star.left_plus_below_circ by blast
  have "?q1 * ?q3 * ?q2 * ?r0 = ?q1 * ?q3 * ?r0  ?q1 * ?q3 * ?q2+ * ?r0"
    by (smt (z3) comp_associative mult_right_dist_sup star.circ_back_loop_fixpoint star.circ_plus_same sup_commute)
  also have "...  ?q3 * ?q2 * ?r0  ?q1 * ?q3 * ?q2+ * ?r0"
    using 16 sup_left_isotone by blast
  also have "...  ?q3 * ?q2 * ?r0  ?q3 * ?q2 * ?q2 * ?r0"
    using 14 by (smt (z3) inf.eq_refl semiring.distrib_right star.circ_transitive_equal sup.absorb2 sup_monoid.add_commute mult_assoc)
  also have "... = ?q3 * ?q2 * ?r0"
    by (simp add: comp_associative star.circ_transitive_equal)
  finally have 17: "?q1 * ?q3 * ?q2 * ?r0  ?q3 * ?q2 * ?r0"
    .
  have "?r0  ?q2 * ?r0"
    using star.circ_loop_fixpoint sup_right_divisibility by auto
  also have "...  ?q3 * ?q2 * ?r0"
    using comp_associative star.circ_loop_fixpoint sup_right_divisibility by force
  also have "...  ?q2 * ?q3 * ?q2 * ?r0"
    using comp_associative star.circ_loop_fixpoint sup_right_divisibility by force
  finally have 18: "?r0  ?q2 * ?q3 * ?q2 * ?r0"
    .
  have "p0 * ?q2 * ?q3 * ?q2 * ?r0 = (?q2  ?q1) * ?q2 * ?q3 * ?q2 * ?r0"
    using 1 by (smt (z3) comp_inf.mult_right_dist_sup comp_inf.star_plus inf_top.right_neutral regular_complement_top)
  also have "... = ?q2 * ?q2 * ?q3 * ?q2 * ?r0  ?q1 * ?q2 * ?q3 * ?q2 * ?r0"
    using mult_right_dist_sup by auto
  also have "...  ?q2 * ?q3 * ?q2 * ?r0  ?q1 * ?q2 * ?q3 * ?q2 * ?r0"
    by (smt (z3) comp_left_increasing_sup star.circ_loop_fixpoint sup_left_isotone mult_assoc)
  also have "... = ?q2 * ?q3 * ?q2 * ?r0  ?q1 * ?q3 * ?q2 * ?r0  ?q1 * ?q2+ * ?q3 * ?q2 * ?r0"
    by (smt (z3) mult_left_dist_sup semiring.combine_common_factor star.circ_loop_fixpoint sup_monoid.add_commute mult_assoc)
  also have "...  ?q2 * ?q3 * ?q2 * ?r0  ?q1 * ?q3 * ?q2 * ?r0  ?q1 * ?q2+ * ?q2 * ?r0"
    using 9 mult_left_isotone sup_right_isotone by auto
  also have "...  ?q2 * ?q3 * ?q2 * ?r0  ?q1 * ?q3 * ?q2 * ?r0  ?q1 * ?q2 * ?r0"
    by (smt (z3) comp_associative comp_isotone inf.eq_refl semiring.add_right_mono star.circ_transitive_equal star.left_plus_below_circ sup_commute)
  also have "...  ?q2 * ?q3 * ?q2 * ?r0  ?q1 * ?q3 * ?q2 * ?r0  ?q3 * ?q2 * ?r0"
    using 6 sup_right_isotone by blast
  also have "... = ?q2 * ?q3 * ?q2 * ?r0  ?q3 * ?q2 * ?r0"
    using 17 by (smt (z3) le_iff_sup semiring.combine_common_factor semiring.distrib_right star.circ_loop_fixpoint sup_monoid.add_commute)
  also have "...  ?q2 * ?q3 * ?q2 * ?r0  ?q3 * ?q2 * ?r0"
    by (meson mult_left_isotone star.circ_increasing sup_right_isotone)
  also have "... = ?q2 * ?q3 * ?q2 * ?r0"
    by (smt (z3) comp_associative star.circ_loop_fixpoint star.circ_transitive_equal star_involutive)
  finally have "p0 * ?q2 * ?q3 * ?q2 * ?r0  ?r0  ?q2 * ?q3 * ?q2 * ?r0"
    using 18 sup.boundedI by blast
  hence "p0 * ?r0  ?q2 * ?q3 * ?q2 * ?r0"
    by (simp add: comp_associative star_left_induct)
  also have "...  ?p * ?q3 * ?q2 * ?r0"
    by (metis mult_left_isotone star.circ_sub_dist sup_commute)
  also have "...  ?p * ?p * ?q2 * ?r0"
    by (simp add: mult_left_isotone mult_right_isotone star_isotone)
  also have "...  ?p * ?p * ?p * ?r0"
    by (metis mult_isotone order.refl star.circ_sub_dist sup_commute)
  finally have 19: "p0 * ?r0  ?p * ?r0"
    by (simp add: star.circ_transitive_equal)
  have 20: "?p  p0"
    by (metis star.left_plus_circ star_isotone update_square_ub_plus)
  hence 21: "p0 * ?r0 = ?p * ?r0"
    using 19 order.antisym mult_left_isotone by auto
  have "?p  1 = (?q3  1)  (?q2  1)"
    using comp_inf.semiring.distrib_right conv_involutive by auto
  also have "... = (?q1  1)  (?q2  1)"
    using assms(3) acyclic_square path_splitting_invariant_def inf.sup_monoid.add_assoc by auto
  also have "... = (?pxy  -?pxy)  p0  1"
    using inf_sup_distrib2 by auto
  also have "... = p0  1"
    using 1 by (metis inf.sup_monoid.add_commute inf_sup_distrib1 maddux_3_11_pp)
  finally show 22: "?p  1 = p0  1"
    .
  have "?pT * x  p0T * x"
    using 20 by (metis conv_isotone conv_star_commute mult_left_isotone)
  hence 23: "?rp  ?r0"
    using 22 comp_inf.mult_left_isotone by auto
  have 24: "disjoint_set_forest ?p"
    using 1 2 assms(3) disjoint_set_forest_update_square by blast
  hence 25: "point ?rp"
    using root_point assms(1) by auto
  have "?r0 * ?rpT = ?r0 * xT * ?p * (?p  1)"
    by (smt (z3) comp_associative conv_dist_comp conv_dist_inf conv_involutive conv_star_commute inf.sup_monoid.add_commute one_inf_conv root_var star_one star_sup_one wcc_one)
  also have "...  (p0  1) * p0T * 1 * ?p * (?p  1)"
    by (smt (z3) assms(1) comp_associative mult_left_isotone mult_right_isotone root_var)
  also have "...  (p0  1) * p0T * p0 * (p0  1)"
    using 20 22 comp_isotone by force
  also have "... = (p0  1) * p0 * (p0  1)  (p0  1) * p0T * (p0  1)"
    by (simp add: assms(3) cancel_separate_eq sup_monoid.add_commute mult_assoc mult_left_dist_sup semiring.distrib_right)
  also have "... = (p0  1) * (p0  1)  (p0  1) * p0T * (p0  1)"
    using univalent_root_successors assms(3) by simp
  also have "... = (p0  1) * (p0  1)  (p0  1) * ((p0  1) * p0)T"
    by (smt (z3) comp_associative conv_dist_comp conv_dist_inf conv_star_commute inf.sup_monoid.add_commute one_inf_conv star_one star_sup_one wcc_one)
  also have "... = (p0  1) * (p0  1)"
    by (metis univalent_root_successors assms(3) conv_dist_inf inf.sup_monoid.add_commute one_inf_conv sup_idem symmetric_one_closed)
  also have "...  1"
    by (simp add: coreflexive_mult_closed)
  finally have "?r0 * ?rpT  1"
    .
  hence "?r0  1 * ?rp"
    using 25 shunt_bijective by blast
  hence 26: "?r0 = ?rp"
    using 23 order.antisym by simp
  have "?px * ?r0T = ?px * xT * p0 * (p0  1)"
    by (smt (z3) comp_associative conv_dist_comp conv_dist_inf conv_involutive conv_star_commute inf.sup_monoid.add_commute one_inf_conv root_var star_one star_sup_one wcc_one)
  also have "...  p0T * 1 * p0 * (p0  1)"
    by (smt (z3) assms(1) comp_associative mult_left_isotone mult_right_isotone root_var)
  also have "... = p0 * (p0  1)  p0T * (p0  1)"
    by (simp add: assms(3) cancel_separate_eq sup_monoid.add_commute mult_right_dist_sup)
  also have "... = p0 * (p0  1)  ((p0  1) * p0)T"
    by (smt (z3) conv_dist_comp conv_dist_inf conv_star_commute inf.sup_monoid.add_commute one_inf_conv star_one star_sup_one wcc_one)
  also have "... = p0 * (p0  1)  (p0  1)"
    by (metis univalent_root_successors assms(3) conv_dist_inf inf.sup_monoid.add_commute one_inf_conv symmetric_one_closed)
  also have "... = p0 * (p0  1)"
    by (metis conv_involutive path_compression_1b sup.absorb2 sup_commute)
  also have "...  p0"
    by (simp add: inf.coboundedI1 star.circ_increasing star.circ_mult_upper_bound)
  finally have 27: "?px * ?r0T  p0"
    .
  thus 28: "?px  p0 * ?r0"
    by (simp add: assms(1,3) root_point shunt_bijective)
  have 29: "point ?r0"
    using root_point assms(1,3) by auto
  hence 30: "mapping (?r0T)"
    using bijective_conv_mapping by blast
  have "?r0 * (?px  p0) = ?r0 * top * (?px  p0)"
    using 29 by force
  also have "... = ?r0 * ?pxT * p0"
    using 29 by (metis assms(1) covector_inf_comp_3 vector_covector vector_mult_closed)
  also have "... = ?r0 * xT * p0 * p0"
    using comp_associative conv_dist_comp conv_star_commute by auto
  also have "...  ?r0 * xT * p0"
    by (simp add: comp_associative mult_right_isotone star.circ_plus_same star.left_plus_below_circ)
  also have "... = ?r0 * ?pxT"
    by (simp add: comp_associative conv_dist_comp conv_star_commute)
  also have "... = (?px * ?r0T)T"
    by (simp add: conv_dist_comp)
  also have "...  p0T"
    using 27 conv_isotone conv_star_commute by fastforce
  finally have "?r0 * (?px  p0)  p0T"
    .
  hence "?px  p0  ?r0T * p0T"
    using 30 shunt_mapping by auto
  hence "?px  p0  p0 * ?r0  ?r0T * p0T"
    using 28 inf.coboundedI2 inf.sup_monoid.add_commute by fastforce
  also have "... = p0 * ?r0 * ?r0T * p0T"
    using 29 by (smt (z3) vector_covector vector_inf_comp vector_mult_closed)
  also have "... = ?p * ?r0 * ?r0T * ?pT"
    using 21 by (smt comp_associative conv_dist_comp conv_star_commute)
  also have "... = ?p * ?rp * ?rpT * ?pT"
    using 26 by auto
  also have "...  ?p * 1 * ?pT"
    using 25 by (smt (z3) comp_associative mult_left_isotone mult_right_isotone)
  finally have 31: "?px  p0  fc ?p"
    by auto
  have "-?px  p0  ?p"
    by (simp add: inf.sup_monoid.add_commute le_supI1 sup_commute)
  also have "...  fc ?p"
    using fc_increasing by auto
  finally have "p0  fc ?p"
    using 1 31 by (smt (z3) inf.sup_monoid.add_commute maddux_3_11_pp semiring.add_left_mono sup.orderE sup_commute)
  also have "...  wcc ?p"
    using star.circ_sub_dist_3 by auto
  finally have 32: "wcc p0  wcc ?p"
    using wcc_below_wcc by blast
  have "?p  wcc p0"
    by (simp add: inf.coboundedI1 inf.sup_monoid.add_commute star.circ_mult_upper_bound star.circ_sub_dist_1)
  hence "wcc ?p  wcc p0"
    using wcc_below_wcc by blast
  hence "wcc ?p = wcc p0"
    using 32 order.antisym by blast
  thus "fc ?p = fc p0"
    using 24 assms(3) fc_wcc by auto
qed

lemma path_splitting_invariant_aux:
  assumes "path_splitting_invariant p x y p0"
  shows "p[[y]] = p0[[y]]"
    and "p[[p[[y]]]] = p0[[p0[[y]]]]"
    and "p[[p[[p[[y]]]]]] = p0[[p0[[p0[[y]]]]]]"
    and "p  1 = p0  1"
    and "fc p = fc p0"
proof -
  let ?p2 = "p0 * p0"
  let ?p2t = "?p2T"
  let ?px = "p0T * x"
  let ?py = "-(p0T * y)"
  let ?pxy = "?px  ?py"
  let ?p = "p0[?pxy?p2t]"
  have "?p[[y]] = p0[[y]]"
    apply (rule put_get_different_vector)
    using assms find_set_precondition_def vector_complement_closed vector_inf_closed vector_mult_closed path_splitting_invariant_def apply force
    by (meson inf.cobounded2 order_lesseq_imp p_antitone_iff path_compression_1b)
  thus 1: "p[[y]] = p0[[y]]"
    using assms path_splitting_invariant_def by auto
  have "?p[[p0[[y]]]] = p0[[p0[[y]]]]"
    apply (rule put_get_different_vector)
    using assms find_set_precondition_def vector_complement_closed vector_inf_closed vector_mult_closed path_splitting_invariant_def apply force
    by (metis comp_isotone inf.boundedE inf.coboundedI2 inf.eq_refl p_antitone_iff selection_closed_id star.circ_increasing)
  thus 2: "p[[p[[y]]]] = p0[[p0[[y]]]]"
    using 1 assms path_splitting_invariant_def by auto
  have "?p[[p0[[p0[[y]]]]]] = p0[[p0[[p0[[y]]]]]]"
    apply (rule put_get_different_vector)
    using assms find_set_precondition_def vector_complement_closed vector_inf_closed vector_mult_closed path_splitting_invariant_def apply force
    by (metis comp_associative comp_isotone conv_dist_comp conv_involutive conv_order inf.coboundedI2 inf.le_iff_sup mult_left_isotone p_antitone_iff p_antitone_inf star.circ_increasing star.circ_transitive_equal)
  thus "p[[p[[p[[y]]]]]] = p0[[p0[[p0[[y]]]]]]"
    using 2 assms path_splitting_invariant_def by auto
  show "p  1 = p0  1"
    using assms path_splitting_invariant_aux_1(1) path_splitting_invariant_def find_set_precondition_def by auto
  show "fc p = fc p0"
    using assms path_splitting_invariant_aux_1(2) path_splitting_invariant_def find_set_precondition_def by auto
qed

lemma path_splitting_1:
  "find_set_precondition p0 x  path_splitting_invariant p0 x x p0"
proof -
  assume 1: "find_set_precondition p0 x"
  show "path_splitting_invariant p0 x x p0"
  proof (unfold path_splitting_invariant_def, intro conjI)
    show "find_set_precondition p0 x"
      using 1 by simp
    show "vector x" "injective x" "surjective x"
      using 1 find_set_precondition_def by auto
    show "x  p0T * x"
      by (simp add: path_compression_1b)
    have "(p0 * p0)T * x  p0T * x"
      by (simp add: conv_dist_comp mult_left_isotone star.circ_square)
    thus "p0[p0T * x - p0T * x(p0 * p0)T] = p0"
      by (smt (z3) inf.le_iff_sup inf_commute maddux_3_11_pp p_antitone_inf pseudo_complement)
    show "univalent p0" "total p0" "acyclic (p0 - 1)"
      using 1 find_set_precondition_def by auto
  qed
qed

lemma path_splitting_2:
  "path_splitting_invariant p x y p0  y  p[[y]]  path_splitting_invariant (p[yp[[p[[y]]]]]) x (p[[y]]) p0  ((p[yp[[p[[y]]]]])T * (p[[y]])) < (pT * y)"
proof -
  let ?py = "p[[y]]"
  let ?ppy = "p[[?py]]"
  let ?pyppy = "p[y?ppy]"
  let ?p2 = "p0 * p0"
  let ?p2t = "?p2T"
  let ?p2ts = "?p2t"
  let ?px = "p0T * x"
  let ?py2 = "-(p0T * y)"
  let ?pxy = "?px  ?py2"
  let ?p = "p0[?pxy?p2t]"
  let ?pty = "p0T * y"
  let ?pt2y = "p0T * p0T * y"
  let ?pt2sy = "p0T * p0T * p0T * y"
  let ?ptpy = "p0T+ * y"
  assume 1: "path_splitting_invariant p x y p0  y  ?py"
  have 2: "point ?pty  point ?pt2y"
    using 1 by (smt (verit) comp_associative read_injective read_surjective path_splitting_invariant_def)
  show "path_splitting_invariant ?pyppy x (p[[y]]) p0  (?pyppyT * (p[[y]])) < (pT * y)"
  proof
    show "path_splitting_invariant ?pyppy x (p[[y]]) p0"
    proof (unfold path_splitting_invariant_def, intro conjI)
      show 3: "find_set_precondition ?pyppy x"
      proof (unfold find_set_precondition_def, intro conjI)
        show "univalent ?pyppy"
          using 1 find_set_precondition_def read_injective update_univalent path_splitting_invariant_def by auto
        show "total ?pyppy"
          using 1 bijective_regular find_set_precondition_def read_surjective update_total path_splitting_invariant_def by force
        show "acyclic (?pyppy - 1)"
          apply (rule update_acyclic_3)
          using 1 find_set_precondition_def path_splitting_invariant_def apply blast
          using 1 2 comp_associative path_splitting_invariant_aux(2) apply force
          using 1 path_splitting_invariant_def apply blast
          by (metis inf.order_lesseq_imp mult_isotone star.circ_increasing star.circ_square mult_assoc)
        show "vector x" "injective x" "surjective x"
          using 1 find_set_precondition_def path_splitting_invariant_def by auto
      qed
      show "vector (p[[y]])"
        using 1 comp_associative path_splitting_invariant_def by auto
      show "injective (p[[y]])"
        using 1 3 read_injective path_splitting_invariant_def find_set_precondition_def by auto
      show "surjective (p[[y]])"
        using 1 3 read_surjective path_splitting_invariant_def find_set_precondition_def by auto
      show "p[[y]]  ?px"
      proof -
        have "p[[y]] = p0[[y]]"
          using 1 path_splitting_invariant_aux(1) by blast
        also have "...  p0T * ?px"
          using 1 path_splitting_invariant_def mult_right_isotone by force
        also have "...  ?px"
          by (metis comp_associative mult_left_isotone star.left_plus_below_circ)
        finally show ?thesis
          .
      qed
      show "p0[?px - p0T * (p[[y]])?p2t] = ?pyppy"
      proof -
        have 4: "p[?px  -?ptpy  y?p2t] = ?pyppy"
        proof (cases "y  -?ptpy")
          case True
          hence "p[?px  -?ptpy  y?p2t] = p[y?p2t]"
            using 1 inf.absorb2 path_splitting_invariant_def by auto
          also have "... = ?pyppy"
            using 1 by (metis comp_associative conv_dist_comp path_splitting_invariant_aux(2) path_splitting_invariant_def update_point_get)
          finally show ?thesis
            .
        next
          case False
          have "vector (-?ptpy)"
            using 1 vector_complement_closed vector_mult_closed path_splitting_invariant_def by blast
          hence 5: "y  ?ptpy"
            using 1 by (smt (verit, del_insts) False bijective_regular point_in_vector_or_complement regular_closed_star regular_mult_closed total_conv_surjective univalent_conv_injective path_splitting_invariant_def)
          hence "?px  -?ptpy  y = bot"
            by (simp add: inf.coboundedI2 p_antitone pseudo_complement)
          hence 6: "p[?px  -?ptpy  y?p2t] = p"
            by simp
          have 7: "y = root p0 y"
            using 1 5 loop_root_2 path_splitting_invariant_def by blast
          have "?pyppy = p[yp0[[p0[[y]]]]]"
            using 1 path_splitting_invariant_aux(2) by force
          also have "... = p[yp0[[y]]]"
            using 1 7 by (metis root_successor_loop path_splitting_invariant_def)
          also have "... = p[y?py]"
            using 1 path_splitting_invariant_aux(1) by force
          also have "... = p"
            using 1 get_put path_splitting_invariant_def by blast
          finally show ?thesis
            using 6 by simp
        qed
        have 8: "-?ptpy = ?py2  (-?ptpy  y)"
        proof (rule order.antisym)
          have 9: "regular (p0T * y)  regular ?ptpy"
            using 1 bijective_regular mapping_conv_bijective pp_dist_star regular_mult_closed path_splitting_invariant_def by auto
          have "p0T * y  ?ptpy  y"
            by (simp add: star.circ_loop_fixpoint mult_assoc)
          also have "... = ?ptpy  (-?ptpy  y)"
            using 9 by (metis maddux_3_21_pp)
          hence "p0T * y  -?ptpy  -?ptpy  y"
            using calculation half_shunting sup_commute by auto
          thus "-?ptpy  ?py2  (-?ptpy  y)"
            using 9 by (smt (z3) inf.sup_monoid.add_commute shunting_var_p sup.left_commute sup_commute)
          have "-(p0T * y)  -?ptpy"
            by (simp add: comp_isotone p_antitone star.left_plus_below_circ)
          thus "-(p0T * y)  (-?ptpy  y)  -?ptpy"
            by simp
        qed
        have "regular ?px" "regular y"
          using 1 bijective_regular find_set_precondition_def mapping_regular pp_dist_comp regular_closed_star regular_conv_closed path_splitting_invariant_def by auto
        hence 10: "regular (?px  -?ptpy  y)"
          by auto
        have "p0[?px  -(p0T * (p[[y]]))?p2t] = p0[?px  -?ptpy?p2t]"
          using 1 by (smt comp_associative path_splitting_invariant_aux(1) star_plus)
        also have "... = p0[?pxy  (?px  -?ptpy  y)?p2t]"
          using 8 by (metis comp_inf.semiring.distrib_left inf.sup_monoid.add_assoc)
        also have "... = ?p[?px  -?ptpy  y?p2t]"
          using 10 by (smt (z3) update_same comp_inf.semiring.mult_not_zero inf.sup_monoid.add_assoc inf.sup_monoid.add_commute)
        also have "... = p[?px  -?ptpy  y?p2t]"
          using 1 path_splitting_invariant_def by auto
        also have "... = ?pyppy"
          using 4 by auto
        finally show ?thesis
          .
      qed
      show "univalent p0" "total p0" "acyclic (p0 - 1)"
        using 1 path_splitting_invariant_def by auto
    qed
    let ?s = "{ z . regular z  z  pT * y }"
    let ?t = "{ z . regular z  z  ?pyppyT * (p[[y]]) }"
    have "?pyppyT * (p[[y]])  p+T * (p[[y]])"
      using 1 path_splitting_invariant_def update_square_plus conv_order mult_left_isotone star_isotone by force
    also have "... = pT * pT * y"
      by (simp add: conv_plus_commute star.left_plus_circ mult_assoc)
    also have "... = pT+ * y"
      by (simp add: star_plus)
    finally have 11: "?pyppyT * (p[[y]])  pT+ * y"
      .
    hence "?pyppyT * (p[[y]])  pT * y"
      using mult_left_isotone order_lesseq_imp star.left_plus_below_circ by blast
    hence 12: "?t  ?s"
      using order_trans by auto
    have 13: "y  ?s"
      using 1 bijective_regular path_compression_1b path_splitting_invariant_def by force
    have 14: "¬ y  ?t"
    proof
      assume "y  ?t"
      hence "y  ?pyppyT * (p[[y]])"
        by simp
      hence "y  pT+ * y"
        using 11 dual_order.trans by blast
      hence "y = root p y"
        using 1 find_set_precondition_def loop_root_2 path_splitting_invariant_def by blast
      hence "y = ?py"
        using 1 by (metis find_set_precondition_def root_successor_loop path_splitting_invariant_def)
      thus False
        using 1 by simp
    qed
    show "card ?t < card ?s"
      apply (rule psubset_card_mono)
      subgoal using finite_regular by simp
      subgoal using 12 13 14 by auto
      done
  qed
qed

lemma path_splitting_3:
  "path_splitting_invariant p x y p0  y = p[[y]]  path_splitting_postcondition p x y p0"
proof -
  assume 1: "path_splitting_invariant p x y p0  y = p[[y]]"
  show "path_splitting_postcondition p x y p0"
  proof (unfold path_splitting_postcondition_def, intro conjI)
    show "univalent p" "total p" "acyclic (p - 1)"
      using 1 find_set_precondition_def path_splitting_invariant_def by blast+
    show 2: "p  1 = p0  1"
      using 1 path_splitting_invariant_aux(4) by blast
    show 3: "fc p = fc p0"
      using 1 path_splitting_invariant_aux(5) by blast
    have "y  p0T * x"
      using 1 path_splitting_invariant_def by simp
    hence 4: "y * xT  fc p0"
      using 1 by (metis dual_order.trans fc_wcc find_set_precondition_def shunt_bijective star.circ_decompose_11 star_decompose_1 star_outer_increasing path_splitting_invariant_def)
    have 5: "y = p0[[y]]"
      using 1 path_splitting_invariant_aux(1) by auto
    hence "y = root p0 y"
      using 1 path_splitting_invariant_def loop_root by auto
    also have "... = root p0 x"
      using 1 4 find_set_precondition_def path_splitting_invariant_def same_component_same_root by auto
    also have "... = root p x"
      using 1 2 3 by (metis find_set_precondition_def path_splitting_invariant_def same_root)
    finally show "y = root p x"
      .
    have "p0T * y = y"
      using 5 order.antisym path_compression_1b star_left_induct_mult_equal by auto
    hence 6: "p0[p0T * x - y(p0 * p0)T] = p"
      using 1 path_splitting_invariant_def by auto
    have "(p0 * p0)T * y = y"
      using 5 mult_assoc conv_dist_comp by auto
    hence "y  p0 * p0 = y  p0"
      using 1 5 by (smt path_splitting_invariant_def update_postcondition)
    hence 7: "y  p = y  p0 * p0"
      using 1 5 by (smt path_splitting_invariant_def update_postcondition)
    have "p0[p0T * x(p0 * p0)T] = (p0[p0T * x - y(p0 * p0)T])[p0T * x  y(p0 * p0)T]"
      using 1 bijective_regular path_splitting_invariant_def update_split by blast
    also have "... = p[p0T * x  y(p0 * p0)T]"
      using 6 by simp
    also have "... = p"
      apply (rule update_same_sub)
      using 7 apply simp
      apply simp
      using 1 bijective_regular inf.absorb2 path_splitting_invariant_def by auto
    finally show "p0[p0T * x(p0 * p0)T] = p"
      .
  qed
qed

theorem find_path_splitting:
  "VARS p t y
  [ find_set_precondition p x  p0 = p ]
  y := x;
  WHILE y  p[[y]]
    INV { path_splitting_invariant p x y p0 }
    VAR { (pT * y) }
     DO t := p[[y]];
        p[y] := p[[p[[y]]]];
        y := t
     OD
  [ path_splitting_postcondition p x y p0 ]"
  apply vcg_tc_simp
    apply (fact path_splitting_1)
   apply (fact path_splitting_2)
  by (fact path_splitting_3)

end

section ‹Verifying Union by Rank›

text ‹
In this section we verify the union-by-rank operation of disjoint-set forests.
The rank of a node is an upper bound of the height of the subtree rooted at that node.
The rank array of a disjoint-set forest maps each node to its rank.
This can be represented as a homogeneous relation since the possible rank values are $0, \dots, n-1$ where $n$ is the number of nodes of the disjoint-set forest.
›

subsection ‹Peano structures›

text ‹
Since ranks are natural numbers we start by introducing basic Peano arithmetic.
Numbers are represented as (relational) points.
Constant Z› represents the number $0$.
Constant S› represents the successor function.
The successor of a number $x$ is obtained by the relational composition ST * x›.
The composition S * x› results in the predecessor of $x$.
›

class peano_signature =
  fixes Z :: "'a"
  fixes S :: "'a"

text ‹
The numbers will be used in arrays, which are represented by homogeneous finite relations.
Such relations can only represent finitely many numbers.
This means that we weaken the Peano axioms, which are usually used to obtain (infinitely many) natural numbers.
Axiom Z_point› specifies that $0$ is a number.
Axiom S_univalent› specifies that every number has at most one `successor'.
Together with axiom S_total›, which is added later, this means that every number has exactly one `successor'.
Axiom S_injective› specifies that numbers with the same successor are equal.
Axiom S_star_Z_top› specifies that every number can be obtained from $0$ by finitely many applications of the successor.
We omit the Peano axiom S * Z = bot› which would specify that $0$ is not the successor of any number.
Since only finitely many numbers will be represented, the remaining axioms will model successor modulo $m$ for some $m$ depending on the carrier of the algebra.
That is, the algebra will be able to represent numbers $0, \dots, m-1$ where the successor of $m-1$ is $0$.
›

class skra_peano_1 = stone_kleene_relation_algebra_tarski_consistent + peano_signature +
  assumes Z_point: "point Z"
  assumes S_univalent: "univalent S"
  assumes S_injective: "injective S"
  assumes S_star_Z_top: "ST * Z = top"
begin

lemma conv_Z_Z:
  "ZT * Z = top"
  by (simp add: Z_point point_conv_comp)

lemma Z_below_S_star:
  "Z  S"
proof -
  have "top * ZT  ST"
    using S_star_Z_top Z_point shunt_bijective by blast
  thus ?thesis
    using Z_point conv_order conv_star_commute vector_conv_covector by force
qed

lemma S_connected:
  "ST * S = top"
  by (metis Z_below_S_star S_star_Z_top mult_left_dist_sup sup.orderE sup_commute top.extremum)

lemma S_star_connex:
  "S  ST = top"
  using S_connected S_univalent cancel_separate_eq sup_commute by auto

lemma Z_sup_conv_S_top:
  "Z  ST * top = top"
  using S_star_Z_top star.circ_loop_fixpoint sup_commute by auto

lemma top_S_sup_conv_Z:
  "top * S  ZT = top"
  by (metis S_star_Z_top conv_dist_comp conv_involutive conv_star_commute star.circ_back_loop_fixpoint symmetric_top_closed)

lemma S_inf_1_below_Z:
  "S  1  Z"
proof -
  have "(S  1) * ST  S  1"
    by (metis S_injective conv_dist_comp coreflexive_symmetric inf.boundedI inf.cobounded1 inf.cobounded2 injective_codomain)
  hence "(S  1) * ST  S  1"
    using star_right_induct_mult by blast
  hence "(S  1) * ST * Z  (S  1) * Z"
    by (simp add: mult_left_isotone)
  also have "...  Z"
    by (metis comp_left_subdist_inf inf.boundedE mult_1_left)
  finally show ?thesis
    using S_star_Z_top inf.order_trans top_right_mult_increasing mult_assoc by auto
qed

lemma S_inf_1_below_conv_Z:
  "S  1  ZT"
  using S_inf_1_below_Z conv_order coreflexive_symmetric by fastforce

text ‹
The successor operation provides a convenient way to compare two natural numbers.
Namely, $k < m$ if $m$ can be reached from $k$ by finitely many applications of the successor, formally m ≤ ST * k› or k ≤ S * m›.
This does not work for numbers modulo $m$ since comparison depends on the chosen representative.
We therefore work with a modified successor relation S'›, which is a partial function that computes the successor for all numbers except $m-1$.
If $S$ is surjective, the point M› representing the greatest number $m-1$ is the predecessor of $0$ under S›.
If $S$ is not surjective (like for the set of all natural numbers), M = bot›.
›

abbreviation "S'  S - ZT"
abbreviation "M  S * Z"

lemma M_point_iff_S_surjective:
  "point M  surjective S"
proof
  assume 1: "point M"
  hence "1  ZT * ST * S * Z"
    using comp_associative conv_dist_comp surjective_var by auto
  hence "Z  ST * S * Z"
    using 1 Z_point bijective_reverse mult_assoc by auto
  also have "...  ST * top"
    by (simp add: comp_isotone mult_assoc)
  finally have "ST * ST * top  Z  ST * top"
    using mult_isotone mult_assoc by force
  hence "ST * Z  ST * top"
    by (simp add: star_left_induct mult_assoc)
  thus "surjective S"
    by (simp add: S_star_Z_top order.antisym surjective_conv_total)
next
  assume "surjective S"
  thus "point M"
    by (metis S_injective Z_point comp_associative injective_mult_closed)
qed

lemma S'_univalent:
  "univalent S'"
  by (simp add: S_univalent univalent_inf_closed)

lemma S'_injective:
  "injective S'"
  by (simp add: S_injective injective_inf_closed)

lemma S'_Z:
  "S' * Z = bot"
  by (simp add: Z_point covector_vector_comp injective_comp_right_dist_inf)

lemma S'_irreflexive:
  "irreflexive S'"
  using S_inf_1_below_conv_Z order_lesseq_imp p_shunting_swap pp_increasing by blast

end

class skra_peano_2 = skra_peano_1 +
  assumes S_total: "total S"
begin

lemma S_mapping:
  "mapping S"
  by (simp add: S_total S_univalent)

lemma M_bot_iff_S_not_surjective:
  "M  bot  surjective S"
proof
  assume "M  bot"
  hence "top * S * Z = top"
    by (metis S_mapping Z_point bijective_regular comp_associative mapping_regular regular_mult_closed tarski)
  hence "ZT  top * S"
    using M_point_iff_S_surjective S_injective Z_point comp_associative injective_mult_closed by auto
  thus "surjective S"
    using sup.orderE top_S_sup_conv_Z by fastforce
next
  assume "surjective S"
  thus "M  bot"
    using M_point_iff_S_surjective consistent covector_bot_closed by force
qed

lemma M_point_or_bot:
  "point M  M = bot"
  using M_bot_iff_S_not_surjective M_point_iff_S_surjective by blast

text ‹Alternative way to express S'›

lemma S'_var:
  "S' = S - M"
proof -
  have "S' = S * (1 - ZT)"
    by (simp add: Z_point covector_comp_inf vector_conv_compl)
  also have "... = S * (1 - Z)"
    by (metis conv_complement one_inf_conv)
  also have "... = S * 1  S * -Z"
    by (simp add: S_mapping univalent_comp_left_dist_inf)
  also have "... = S - M"
    by (simp add: comp_mapping_complement S_mapping)
  finally show ?thesis
    .
qed

text ‹Special case of just $1$ number›

lemma M_is_Z_iff_1_is_top:
  "M = Z  1 = top"
proof
  assume "M = Z"
  hence "Z = ST * Z"
    by (metis S_mapping Z_point order.antisym bijective_reverse inf.eq_refl shunt_mapping)
  thus "1 = top"
    by (metis S_star_Z_top Z_point inf.eq_refl star_left_induct sup.absorb2 symmetric_top_closed top_le)
next
  assume "1 = top"
  thus "M = Z"
    using S_mapping comp_right_one mult_1_left by auto
qed

lemma S_irreflexive:
  assumes "M  Z"
  shows "irreflexive S"
proof -
  have "(S  1) * ST  S  1"
    by (smt (z3) S_injective S_mapping coreflexive_comp_top_inf dual_order.eq_iff inf.cobounded1 inf.sup_monoid.add_commute inf.sup_same_context mult_left_isotone one_inf_conv top_right_mult_increasing total_var)
  hence "(S  1) * ST  S  1"
    using star_right_induct_mult by blast
  hence "(S  1) * ST * Z  (S  1) * Z"
    by (simp add: mult_left_isotone)
  also have "... = M  Z"
    by (simp add: Z_point injective_comp_right_dist_inf)
  also have "... = bot"
    by (smt (verit, ccfv_threshold) M_point_or_bot assms Z_point bijective_one_closed bijective_regular comp_associative conv_complement coreflexive_comp_top_inf epm_3 inf.sup_monoid.add_commute one_inf_conv regular_mult_closed star.circ_increasing star.circ_zero tarski vector_conv_covector vector_export_comp_unit)
  finally have "S  1  bot"
    using S_star_Z_top comp_associative le_bot top_right_mult_increasing by fastforce
  thus ?thesis
    using le_bot pseudo_complement by blast
qed

text ‹
We show that S'› satisfies most properties of S›.
›

lemma M_regular:
  "regular M"
  using S_mapping Z_point bijective_regular mapping_regular regular_mult_closed by blast

lemma S'_regular:
  "regular S'"
  using S_mapping mapping_regular by auto

lemma S'_star_Z_top:
  "S'T * Z = top"
proof -
  have "ST * Z = (S'  (S  M))T * Z"
    by (metis M_regular maddux_3_11_pp S'_var)
  also have "...  S'T * Z"
  proof (cases "M = bot")
    case True
    thus ?thesis
      by simp
  next
    case False
    hence "point M"
      using M_point_or_bot by auto
    hence "arc (S  M)"
      using S_mapping mapping_inf_point_arc by blast
    hence 1: "arc ((S  M)T)"
      using conv_involutive by auto
    have 2: "S  M  ZT"
      by (metis S'_var Z_point bijective_regular conv_complement inf.cobounded2 p_shunting_swap)
    have "(S'  (S  M))T * Z = (S'T  (S  M)T) * Z"
      by (simp add: S'_var conv_dist_sup)
    also have "... = (S'T * (S  M)T * S'T  S'T) * Z"
      using 1 star_arc_decompose sup_commute by auto
    also have "... = S'T * (S  M)T * S'T * Z  S'T * Z"
      using mult_right_dist_sup by auto
    also have "...  S'T * ZTT * S'T * Z  S'T * Z"
      using 2 by (meson comp_isotone conv_isotone inf.eq_refl semiring.add_mono)
    also have "...  S'T * Z"
      by (metis Z_point comp_associative conv_involutive le_supI mult_right_isotone top.extremum)
    finally show ?thesis
      .
  qed
  finally show ?thesis
    using S_star_Z_top top_le by auto
qed

lemma Z_below_S'_star:
  "Z  S'"
  by (metis S'_star_Z_top Z_point comp_associative comp_right_one conv_order conv_star_commute mult_right_isotone vector_conv_covector)

lemma S'_connected:
  "S'T * S' = top"
  by (metis Z_below_S'_star S'_star_Z_top mult_left_dist_sup sup.orderE sup_commute top.extremum)

lemma S'_star_connex:
  "S'  S'T = top"
  using S'_connected S'_univalent cancel_separate_eq sup_commute by auto

lemma Z_sup_conv_S'_top:
  "Z  S'T * top = top"
  using S'_star_Z_top star.circ_loop_fixpoint sup_commute by auto

lemma top_S'_sup_conv_Z:
  "top * S'  ZT = top"
  by (metis S'_star_Z_top conv_dist_comp conv_involutive conv_star_commute star.circ_back_loop_fixpoint symmetric_top_closed)

lemma S_power_point_or_bot:
  assumes "regular S'"
  shows "point (S'T ^ n * Z)  S'T ^ n * Z = bot"
proof -
  have 1: "regular (S'T ^ n * Z)"
    using assms Z_point bijective_regular regular_conv_closed regular_mult_closed regular_power_closed by auto
  have "injective (S'T ^ n)"
    by (simp add: injective_power_closed S'_univalent)
  hence "injective (S'T ^ n * Z)"
    using Z_point injective_mult_closed by blast
  thus ?thesis
    using 1 Z_point comp_associative tarski by force
qed

end

subsection ‹Initialising Ranks›

text ‹
We show that the rank array satisfies three properties which are established/preserved by the union-find operations.
First, every node has a rank, that is, the rank array is a mapping.
Second, the rank of a node is strictly smaller than the rank of its parent, except if the node is a root.
This implies that the rank of a node is an upper bound on the height of its subtree.
Third, the number of roots in the disjoint-set forest (the number of disjoint sets) is not larger than $m-k$ where $m$ is the total number of nodes and $k$ is the maximum rank of any node.
The third property is useful to show that ranks never overflow (exceed $m-1$).
To compare the number of roots and $m-k$ we use the existence of an injective univalent relation between the set of roots and the set of $m-k$ largest numbers, both represented as vectors.
The three properties are captured in rank_property›.
›

class skra_peano_3 = stone_kleene_relation_algebra_tarski_finite_regular + skra_peano_2
begin

definition "card_less_eq v w  i . injective i  univalent i  regular i  v  i * w"
definition "rank_property p rank  mapping rank  (p - 1) * rank  rank * S'+  card_less_eq (roots p) (-(S'+ * rankT * top))"

end

class skra_peano_4 = stone_kleene_relation_algebra_choose_point_finite_regular + skra_peano_2
begin

subclass skra_peano_3 ..

text ‹
The initialisation loop is augmented by setting the rank of each node to $0$.
The resulting rank array satisfies the desired properties explained above.
›

theorem init_ranks:
  "VARS h p x rank
  [ True ]
  FOREACH x
    USING h
      INV { p - h = 1 - h  rank - h = ZT - h }
       DO p := make_set p x;
          rank[x] := Z
       OD
  [ p = 1  disjoint_set_forest p  rank = ZT  rank_property p rank  h = bot ]"
proof vcg_tc_simp
  fix h p rank
  let ?x = "choose_point h"
  let ?m = "make_set p ?x"
  let ?rank = "rank[?xZ]"
  assume 1: "regular h  vector h  p - h = 1 - h  rank - h = ZT - h  h  bot"
  show "vector (-?x  h) 
        ?m  (--?x  -h) = 1  (--?x  -h) 
        ?rank  (--?x  -h) = ZT  (--?x  -h) 
        card { x . regular x  x  -?x  x  h } < h"
  proof (intro conjI)
    show "vector (-?x  h)"
      using 1 choose_point_point vector_complement_closed vector_inf_closed by blast
    have 2: "point ?x  regular ?x"
      using 1 bijective_regular choose_point_point by blast
    have 3: "-h  -?x"
      using choose_point_decreasing p_antitone_iff by auto
    have 4: "?x  ?m = ?x * ?xT  -?x  ?m = -?x  p"
      using 1 choose_point_point make_set_function make_set_postcondition_def by auto
    have "?m  (--?x  -h) = (?m  ?x)  (?m - h)"
      using 2 comp_inf.comp_left_dist_sup by auto
    also have "... = ?x * ?xT  (?m  -?x  -h)"
      using 3 4 by (smt (z3) inf_absorb2 inf_assoc inf_commute)
    also have "... = ?x * ?xT  (1 - h)"
      using 1 3 4 inf.absorb2 inf.sup_monoid.add_assoc inf_commute by auto
    also have "... = (1  ?x)  (1 - h)"
      using 2 by (metis inf.cobounded2 inf.sup_same_context one_inf_conv vector_covector)
    also have "... = 1  (--?x  -h)"
      using 2 comp_inf.semiring.distrib_left by auto
    finally show "?m  (--?x  -h) = 1  (--?x  -h)"
      .
    have 5: "?x  ?rank = ?x  ZT  -?x  ?rank = -?x  rank"
      by (smt (z3) inf_commute order_refl update_inf_different update_inf_same)
    have "?rank  (--?x  -h) = (?rank  ?x)  (?rank - h)"
      using 2 comp_inf.comp_left_dist_sup by auto
    also have "... = (?x  ZT)  (?rank  -?x  -h)"
      using 3 5 by (smt (z3) inf_absorb2 inf_assoc inf_commute)
    also have "... = (ZT  ?x)  (ZT - h)"
      using 1 3 5 inf.absorb2 inf.sup_monoid.add_assoc inf_commute by auto
    also have "... = ZT  (--?x  -h)"
      using 2 comp_inf.semiring.distrib_left by auto
    finally show "?rank  (--?x  -h) = ZT  (--?x  -h)"
      .
    have 5: "¬ ?x  -?x"
      using 1 2 by (metis comp_commute_below_diversity conv_order inf.cobounded2 inf_absorb2 pseudo_complement strict_order_var top.extremum)
    have 6: "?x  h"
      using 1 by (metis choose_point_decreasing)
    show "card { x . regular x  x  -?x  x  h } < h"
      apply (rule psubset_card_mono)
      using finite_regular apply simp
      using 2 5 6 by auto
  qed
next
  show "rank_property 1 (ZT)"
  proof (unfold rank_property_def, intro conjI)
    show "univalent (ZT)" "total (ZT)"
      using Z_point surjective_conv_total by auto
    show "(1 - 1) * (ZT)  (ZT) * S'+"
      by simp
    have "top  1 * -(S'+ * Z * top)"
      by (simp add: S'_Z comp_associative star_simulation_right_equal)
    thus "card_less_eq (roots 1) (-(S'+ * ZTT * top))"
      by (metis conv_involutive inf.idem mapping_one_closed regular_one_closed card_less_eq_def bijective_one_closed)
  qed
qed

end

subsection ‹Union by Rank›

text ‹
We show that path compression and union-by-rank preserve the rank property.
›

context stone_kleene_relation_algebra_tarski_finite_regular
begin

lemma union_sets_1_swap:
  assumes "union_sets_precondition p0 x y"
    and "path_compression_postcondition p1 x r p0"
    and "path_compression_postcondition p2 y s p1"
  shows "union_sets_postcondition (p2[sr]) x y p0"
proof (unfold union_sets_postcondition_def union_sets_precondition_def, intro conjI)
  let ?p = "p2[sr]"
  have 1: "disjoint_set_forest p1  point r  r = root p1 x  p1  1 = p0  1  fc p1 = fc p0"
    by (smt assms(1,2) union_sets_precondition_def path_compression_postcondition_def root_point)
  have 2: "disjoint_set_forest p2  point s  s = root p2 y  p2  1 = p1  1  fc p2 = fc p1"
    by (smt assms(1,3) union_sets_precondition_def path_compression_postcondition_def root_point)
  hence 3: "fc p2 = fc p0"
    using 1 by simp
  show 4: "univalent ?p"
    using 1 2 update_univalent by blast
  show "total ?p"
    using 1 2 bijective_regular update_total by blast
  show "acyclic (?p - 1)"
  proof (cases "r = s")
    case True
    thus ?thesis
      using 2 update_acyclic_5 by fastforce
  next
    case False
    hence "bot = s  r"
      using 1 2 distinct_points inf_commute by blast
    also have "... = s  p1T * r"
      using 1 by (smt root_transitive_successor_loop)
    also have "... = s  p2T * r"
      using 1 2 by (smt (z3) inf_assoc inf_commute same_root)
    finally have "r  p2 * s = bot"
      using schroeder_1 conv_star_commute inf.sup_monoid.add_commute by fastforce
    thus ?thesis
      using 1 2 update_acyclic_4 by blast
  qed
  show "fc ?p = wcc (p0  x * yT)"
  proof (rule order.antisym)
    have "s = p2[[s]]"
      using 2 by (metis root_successor_loop)
    hence "s * sT  p2T"
      using 2 eq_refl shunt_bijective by blast
    hence "s * sT  p2"
      using 2 conv_order coreflexive_symmetric by fastforce
    hence "s  p2 * s"
      using 2 shunt_bijective by blast
    hence 5: "p2[[s]]  s"
      using 2 shunt_mapping by blast
    have "s  p2  s * (top  sT * p2)"
      using 2 by (metis dedekind_1)
    also have "... = s * sT * p2"
      by (simp add: mult_assoc)
    also have "...  s * sT"
      using 5 by (metis comp_associative conv_dist_comp conv_involutive conv_order mult_right_isotone)
    also have "...  1"
      using 2 by blast
    finally have 6: "s  p2  1"
      by simp
    have "p0  wcc p0"
      by (simp add: star.circ_sub_dist_1)
    also have "... = wcc p2"
      using 3 by (simp add: star_decompose_1)
    also have 7: "...  wcc ?p"
    proof -
      have "wcc p2 = wcc ((-s  p2)  (s  p2))"
        using 2 by (metis bijective_regular inf.sup_monoid.add_commute maddux_3_11_pp)
      also have "...  wcc ((-s  p2)  1)"
        using 6 wcc_isotone sup_right_isotone by simp
      also have "... = wcc (-s  p2)"
        using wcc_with_loops by simp
      also have "...  wcc ?p"
        using wcc_isotone sup_ge2 by blast
      finally show ?thesis
        by simp
    qed
    finally have 8: "p0  wcc ?p"
      by force
    have "s  p2T * y"
      using 2 by (metis inf_le1)
    hence 9: "s * yT  p2T"
      using assms(1) shunt_bijective union_sets_precondition_def by blast
    hence "y * sT  p2"
      using conv_dist_comp conv_order conv_star_commute by force
    also have "...  wcc p2"
      by (simp add: star.circ_sub_dist)
    also have "...  wcc ?p"
      using 7 by simp
    finally have 10: "y * sT  wcc ?p"
      by simp
    have 11: "s * rT  wcc ?p"
      using 1 2 star.circ_sub_dist_1 sup_assoc vector_covector by auto
    have "r  p1T * x"
      using 1 by (metis inf_le1)
    hence 12: "r * xT  p1T"
      using assms(1) shunt_bijective union_sets_precondition_def by blast
    also have "...  wcc p1"
      using star_isotone sup_ge2 by blast
    also have "... = wcc p2"
      using 2 by (simp add: star_decompose_1)
    also have "...  wcc ?p"
      using 7 by simp
    finally have 13: "r * xT  wcc ?p"
      by simp
    have "x  x * rT * r  y  y * sT * s"
      using 1 2 shunt_bijective by blast
    hence "y * xT  y * sT * s * (x * rT * r)T"
      using comp_isotone conv_isotone by blast
    also have "... = y * sT * s * rT * r * xT"
      by (simp add: comp_associative conv_dist_comp)
    also have "...  wcc ?p * (s * rT) * (r * xT)"
      using 10 by (metis mult_left_isotone mult_assoc)
    also have "...  wcc ?p * wcc ?p * (r * xT)"
      using 11 by (metis mult_left_isotone mult_right_isotone)
    also have "...  wcc ?p * wcc ?p * wcc ?p"
      using 13 by (metis mult_right_isotone)
    also have "... = wcc ?p"
      by (simp add: star.circ_transitive_equal)
    finally have "x * yT  wcc ?p"
      by (metis conv_dist_comp conv_involutive conv_order wcc_equivalence)
    hence "p0  x * yT  wcc ?p"
      using 8 by simp
    hence "wcc (p0  x * yT)  wcc ?p"
      using wcc_below_wcc by simp
    thus "wcc (p0  x * yT)  fc ?p"
      using 4 fc_wcc by simp
    have "-s  p2  wcc p2"
      by (simp add: inf.coboundedI2 star.circ_sub_dist_1)
    also have "... = wcc p0"
      using 3 by (simp add: star_decompose_1)
    also have "...  wcc (p0  y * xT)"
      by (simp add: wcc_isotone)
    finally have 14: "-s  p2  wcc (p0  y * xT)"
      by simp
    have "s * yT  wcc p2"
      using 9 inf.order_trans star.circ_sub_dist sup_commute by fastforce
    also have "... = wcc p0"
      using 1 2 by (simp add: star_decompose_1)
    also have "...  wcc (p0  y * xT)"
      by (simp add: wcc_isotone)
    finally have 15: "s * yT  wcc (p0  y * xT)"
      by simp
    have 16: "y * xT  wcc (p0  y * xT)"
      using le_supE star.circ_sub_dist_1 by blast
    have "x * rT  p1"
      using 12 conv_dist_comp conv_order conv_star_commute by fastforce
    also have "...  wcc p1"
      using star.circ_sub_dist sup_commute by fastforce
    also have "... = wcc p0"
      using 1 by (simp add: star_decompose_1)
    also have "...  wcc (p0  y * xT)"
      by (simp add: wcc_isotone)
    finally have 17: "x * rT  wcc (p0  y * xT)"
      by simp
    have "r  r * xT * x  s  s * yT * y"
      using assms(1) shunt_bijective union_sets_precondition_def by blast
    hence "s * rT  s * yT * y * (r * xT * x)T"
      using comp_isotone conv_isotone by blast
    also have "... = s * yT * y * xT * x * rT"
      by (simp add: comp_associative conv_dist_comp)
    also have "...  wcc (p0  y * xT) * (y * xT) * (x * rT)"
      using 15 by (metis mult_left_isotone mult_assoc)
    also have "...  wcc (p0  y * xT) * wcc (p0  y * xT) * (x * rT)"
      using 16 by (metis mult_left_isotone mult_right_isotone)
    also have "...  wcc (p0  y * xT) * wcc (p0  y * xT) * wcc (p0  y * xT)"
      using 17 by (metis mult_right_isotone)
    also have "... = wcc (p0  y * xT)"
      by (simp add: star.circ_transitive_equal)
    finally have "?p  wcc (p0  y * xT)"
      using 1 2 14 vector_covector by auto
    hence "wcc ?p  wcc (p0  y * xT)"
      using wcc_below_wcc by blast
    also have "... = wcc (p0  x * yT)"
      using conv_dist_comp conv_dist_sup sup_assoc sup_commute by auto
    finally show "fc ?p  wcc (p0  x * yT)"
      using 4 fc_wcc by simp
  qed
qed

lemma union_sets_1_skip:
  assumes "union_sets_precondition p0 x y"
    and "path_compression_postcondition p1 x r p0"
    and "path_compression_postcondition p2 y r p1"
  shows "union_sets_postcondition p2 x y p0"
proof (unfold union_sets_postcondition_def union_sets_precondition_def, intro conjI)
  have 1: "point r  r = root p1 x  fc p1 = fc p0  disjoint_set_forest p2  r = root p2 y  fc p2 = fc p1"
    by (smt assms(1-3) union_sets_precondition_def path_compression_postcondition_def root_point)
  thus "univalent p2" "total p2" "acyclic (p2 - 1)"
    by auto
  have "r  p1T * x"
    using 1 by (metis inf_le1)
  hence "r * xT  p1T"
    using assms(1) shunt_bijective union_sets_precondition_def by blast
  hence 2: "x * rT  p1"
    using conv_dist_comp conv_order conv_star_commute by force
  have "r  p2T * y"
    using 1 by (metis inf_le1)
  hence 3: "r * yT  p2T"
    using assms(1) shunt_bijective union_sets_precondition_def by blast
  have "x * yT  x * rT * r * yT"
    using 1 mult_left_isotone shunt_bijective by blast
  also have "...  p1 * p2T"
    using 2 3 by (metis comp_associative comp_isotone)
  also have "...  wcc p0"
    using 1 by (metis star.circ_mult_upper_bound star_decompose_1 star_isotone sup_ge2 star.circ_sub_dist)
  finally show "fc p2 = wcc (p0  x * yT)"
    using 1 by (smt (z3) fc_star star_decompose_1 sup_absorb1 wcc_sup_wcc star.circ_sub_dist_3 sup_commute wcc_equivalence)
qed

end

syntax
  "_Cond1" :: "'bexp  'com  'com"  ("(1IF _/ THEN _/ FI)" [0,0] 61)
translations "IF b THEN c FI" == "IF b THEN c ELSE SKIP FI"

context skra_peano_3
begin

lemma path_compression_preserves_rank_property:
  assumes "path_compression_postcondition p x y p0"
      and "point x"
      and "disjoint_set_forest p0"
      and "rank_property p0 rank"
    shows "rank_property p rank"
proof (unfold rank_property_def, intro conjI)
  let ?px = "p0T * x"
  have 1: "point y"
    by (smt assms(1,2) path_compression_postcondition_def root_point)
  have 2: "vector ?px"
    using assms(1,2) comp_associative path_compression_postcondition_def by auto
  have "root p0 x = root p x"
    by (smt (verit) assms(1,3) path_compression_postcondition_def same_root)
  hence "root p0 x = y"
    using assms(1) path_compression_postcondition_def by auto
  hence "?px  p0 * y"
    by (meson assms(2,3) path_splitting_invariant_aux_1(3))
  hence "?px * yT  p0"
    using 1 shunt_bijective by blast
  hence "?px  yT  p0"
    using 1 2 by (simp add: vector_covector)
  also have "... = (p0 - 1)+  1"
    using reachable_without_loops star_left_unfold_equal sup_commute by fastforce
  finally have 3: "?px  yT  -1  (p0 - 1)+"
    using half_shunting by blast
  have "p0[?pxy] = p"
    using assms(1) path_compression_postcondition_def by auto
  hence "(p - 1) * rank = (?px  yT  -1) * rank  (-?px  p0  -1) * rank"
    using inf_sup_distrib2 mult_right_dist_sup by force
  also have "...  (?px  yT  -1) * rank  (p0 - 1) * rank"
    by (meson comp_inf.mult_semi_associative le_infE mult_left_isotone sup_right_isotone)
  also have "...  (?px  yT  -1) * rank  rank * S'+"
    using assms(4) rank_property_def sup_right_isotone by auto
  also have "...  (p0 - 1)+ * rank  rank * S'+"
    using 3 mult_left_isotone sup_left_isotone by blast
  also have "...  rank * S'+"
  proof -
    have "(p0 - 1) * rank  rank * S'"
      using assms(4) rank_property_def star_simulation_left star.left_plus_circ by fastforce
    hence "(p0 - 1)+ * rank  (p0 - 1) * rank * S'"
      by (simp add: comp_associative mult_right_isotone)
    also have "...  rank * S'+"
      by (smt (z3) assms(4) rank_property_def comp_associative comp_left_subdist_inf inf.boundedE inf.sup_right_divisibility star.circ_transitive_equal)
    finally show ?thesis
      by simp
  qed
  finally show "(p - 1) * rank  rank * S'+"
    .
  show "univalent rank" "total rank"
    using rank_property_def assms(4) by auto
  show "card_less_eq (roots p) (-(S'+ * rankT * top))"
    using assms(1,4) path_compression_postcondition_def rank_property_def by auto
qed

theorem union_sets_by_rank:
  "VARS p r s rank
  [ union_sets_precondition p x y  rank_property p rank  p0 = p ]
  r := find_set p x;
  p := path_compression p x r;
  s := find_set p y;
  p := path_compression p y s;
  IF r  s THEN
    IF rank[[r]]  S'+ * (rank[[s]]) THEN
      p[r] := s
    ELSE
      p[s] := r;
      IF rank[[r]] = rank[[s]] THEN
        rank[r] := S'T * (rank[[r]])
      FI
    FI
  FI
  [ union_sets_postcondition p x y p0  rank_property p rank ]"
proof vcg_tc_simp
  fix rank
  let ?r = "find_set p0 x"
  let ?p1 = "path_compression p0 x ?r"
  let ?s = "find_set ?p1 y"
  let ?p2 = "path_compression ?p1 y ?s"
  let ?p5 = "path_compression ?p1 y ?r"
  let ?rr = "rank[[?r]]"
  let ?rs = "rank[[?s]]"
  let ?rank = "rank[?rS'T * ?rs]"
  let ?p3 = "?p2[?r?s]"
  let ?p4 = "?p2[?s?r]"
  assume 1: "union_sets_precondition p0 x y  rank_property p0 rank"
  hence 2: "path_compression_postcondition ?p1 x ?r p0"
    using find_set_function find_set_postcondition_def find_set_precondition_def path_compression_function path_compression_precondition_def union_sets_precondition_def by auto
  hence 3: "path_compression_postcondition ?p2 y ?s ?p1"
    using 1 find_set_function find_set_postcondition_def find_set_precondition_def path_compression_function path_compression_precondition_def union_sets_precondition_def path_compression_postcondition_def by meson
  have "rank_property ?p1 rank"
    using 1 2 path_compression_preserves_rank_property union_sets_precondition_def by blast
  hence 4: "rank_property ?p2 rank"
    using 1 2 3 by (meson path_compression_preserves_rank_property path_compression_postcondition_def union_sets_precondition_def)
  have 5: "point ?r" "point ?s"
    using 1 2 3 by (smt path_compression_postcondition_def union_sets_precondition_def root_point)+
  hence 6: "point ?rr" "point ?rs"
    using 1 comp_associative read_injective read_surjective rank_property_def by auto
  have "top  S'  S'+T"
    by (metis S'_star_connex conv_dist_comp conv_star_commute eq_refl star.circ_reflexive star_left_unfold_equal star_simulation_right_equal sup.orderE sup_monoid.add_assoc)
  hence 7: "-S'+T  S'"
    by (metis comp_inf.case_split_left comp_inf.star.circ_plus_one comp_inf.star.circ_sup_2 half_shunting)
  show "(?r  ?s  (?rr  S'+ * ?rs  union_sets_postcondition ?p3 x y p0  rank_property ?p3 rank) 
                      (¬ ?rr  S'+ * ?rs  ((?rr = ?rs  union_sets_postcondition ?p4 x y p0  rank_property ?p4 ?rank) 
                                              (?rr  ?rs  union_sets_postcondition ?p4 x y p0  rank_property ?p4 rank)))) 
        (?r = ?s  union_sets_postcondition ?p5 x y p0  rank_property ?p5 rank)"
  proof
    show "?r  ?s  (?rr  S'+ * ?rs  union_sets_postcondition ?p3 x y p0  rank_property ?p3 rank) 
                      (¬ ?rr  S'+ * ?rs  ((?rr = ?rs  union_sets_postcondition ?p4 x y p0  rank_property ?p4 ?rank) 
                                              (?rr  ?rs  union_sets_postcondition ?p4 x y p0  rank_property ?p4 rank)))"
    proof
      assume 8: "?r  ?s"
      show "(?rr  S'+ * ?rs  union_sets_postcondition ?p3 x y p0  rank_property ?p3 rank) 
            (¬ ?rr  S'+ * ?rs  ((?rr = ?rs  union_sets_postcondition ?p4 x y p0  rank_property ?p4 ?rank) 
                                    (?rr  ?rs  union_sets_postcondition ?p4 x y p0  rank_property ?p4 rank)))"
      proof
        show "?rr  S'+ * ?rs  union_sets_postcondition ?p3 x y p0  rank_property ?p3 rank"
        proof
          assume 9: "?rr  S'+ * ?rs"
          show "union_sets_postcondition ?p3 x y p0  rank_property ?p3 rank"
          proof
            show "union_sets_postcondition ?p3 x y p0"
              using 1 2 3 by (simp add: union_sets_1)
            show "rank_property ?p3 rank"
            proof (unfold rank_property_def, intro conjI)
              show "univalent rank" "total rank"
                using 1 rank_property_def by auto
              have "?s  -?r"
                using 5 8 by (meson order.antisym bijective_regular point_in_vector_or_complement point_in_vector_or_complement_2)
              hence "?r  ?sT  1 = bot"
                by (metis (full_types) bot_least inf.left_commute inf.sup_monoid.add_commute one_inf_conv pseudo_complement)
              hence "?p3  1  ?p2"
                by (smt half_shunting inf.cobounded2 pseudo_complement regular_one_closed semiring.add_mono sup_commute)
              hence "roots ?p3  roots ?p2"
                by (simp add: mult_left_isotone)
              thus "card_less_eq (roots ?p3) (-(S'+ * rankT * top))"
                using 4 by (meson rank_property_def card_less_eq_def order_trans)
              have "(?p3 - 1) * rank = (?r  ?sT  -1) * rank  (-?r  ?p2  -1) * rank"
                using comp_inf.semiring.distrib_right mult_right_dist_sup by auto
              also have "...  (?r  ?sT  -1) * rank  (?p2 - 1) * rank"
                using comp_inf.mult_semi_associative mult_left_isotone sup_right_isotone by auto
              also have "...  (?r  ?sT  -1) * rank  rank * S'+"
                using 4 sup_right_isotone rank_property_def by blast
              also have "...  (?r  ?sT) * rank  rank * S'+"
                using inf_le1 mult_left_isotone sup_left_isotone by blast
              also have "... = ?r * ?sT * rank  rank * S'+"
                using 5 by (simp add: vector_covector)
              also have "... = rank * S'+"
              proof -
                have "rankT * ?r  S'+ * rankT * ?s"
                  using 9 comp_associative by auto
                hence "?r  rank * S'+ * rankT * ?s"
                  using 4 shunt_mapping comp_associative rank_property_def by auto
                hence "?r * ?sT  rank * S'+ * rankT"
                  using 5 shunt_bijective by blast
                hence "?r * ?sT * rank  rank * S'+"
                  using 4 shunt_bijective rank_property_def mapping_conv_bijective by auto
                thus ?thesis
                  using sup_absorb2 by blast
              qed
              finally show "(?p3 - 1) * rank  rank * S'+"
                .
            qed
          qed
        qed
        show "¬ ?rr  S'+ * ?rs  ((?rr = ?rs  union_sets_postcondition ?p4 x y p0  rank_property ?p4 ?rank) 
                                     (?rr  ?rs  union_sets_postcondition ?p4 x y p0  rank_property ?p4 rank))"
        proof
          assume "¬ ?rr  S'+ * ?rs"
          hence "?rr  -(S'+ * ?rs)"
            using 6 by (meson point_in_vector_or_complement S'_regular bijective_regular regular_closed_star regular_mult_closed vector_mult_closed)
          also have "... = -S'+ * ?rs"
            using 6 comp_bijective_complement by simp
          finally have "?rs  -S'+T * ?rr"
            using 6 by (metis bijective_reverse conv_complement)
          also have "...  S' * ?rr"
            using 7 by (simp add: mult_left_isotone)
          also have "... = S'+ * ?rr  ?rr"
            using star.circ_loop_fixpoint mult_assoc by auto
          finally have 10: "?rs - ?rr  S'+ * ?rr"
            using half_shunting by blast
          show "((?rr = ?rs  union_sets_postcondition ?p4 x y p0  rank_property ?p4 ?rank) 
                 (?rr  ?rs  union_sets_postcondition ?p4 x y p0  rank_property ?p4 rank))"
          proof
            show "?rr = ?rs  union_sets_postcondition ?p4 x y p0  rank_property ?p4 ?rank"
            proof
              assume 11: "?rr = ?rs"
              show "union_sets_postcondition ?p4 x y p0  rank_property ?p4 ?rank"
              proof
                show "union_sets_postcondition ?p4 x y p0"
                  using 1 2 3 by (simp add: union_sets_1_swap)
                show "rank_property ?p4 ?rank"
                proof (unfold rank_property_def, intro conjI)
                  show "univalent ?rank"
                    using 4 5 6 by (meson S'_univalent read_injective update_univalent rank_property_def)
                  have "card_less_eq (roots ?p2) (-(S'+ * rankT * top))"
                    using 4 rank_property_def by blast
                  from this obtain i where 12: "injective i  univalent i  regular i  roots ?p2  i * -(S'+ * rankT * top)"
                    using card_less_eq_def by blast
                  let ?i = "(i[?si[[i * ?rr]]])[i * ?rri[[?s]]]"
                  have 13: "?i = (i * ?rr  ?sT * i)  (-(i * ?rr)  ?s  ?rrT * iT * i)  (-(i * ?rr)  -?s  i)"
                    by (smt (z3) conv_dist_comp conv_involutive inf.sup_monoid.add_assoc inf_sup_distrib1 sup_assoc)
                  have 14: "injective ?i"
                    apply (rule update_injective_swap)
                    subgoal using 12 by simp
                    subgoal using 5 by simp
                    subgoal using 6 12 injective_mult_closed by simp
                    subgoal using 5 comp_associative by simp
                    done
                  have 15: "univalent ?i"
                    apply (rule update_univalent_swap)
                    subgoal using 12 by simp
                    subgoal using 5 by simp
                    subgoal using 5 by simp
                    subgoal using 6 12 injective_mult_closed by simp
                    subgoal using 5 comp_associative by simp
                    done
                  have 16: "regular ?i"
                    using 5 6 12 by (smt (z3) bijective_regular p_dist_inf p_dist_sup pp_dist_comp regular_closed_inf regular_conv_closed)
                  have 17: "regular (i * ?rr)"
                    using 6 12 bijective_regular regular_mult_closed by blast
                  have 18: "find_set_precondition ?p1 y"
                    using 1 2 find_set_precondition_def path_compression_postcondition_def union_sets_precondition_def by blast
                  hence "?s = root ?p1 y"
                    by (meson find_set_function find_set_postcondition_def)
                  also have "... = root ?p2 y"
                    using 3 18 by (smt (z3) find_set_precondition_def path_compression_postcondition_def same_root)
                  also have "...  roots ?p2"
                    by simp
                  also have "...  i * -(S'+ * rankT * top)"
                    using 12 by simp
                  finally have 19: "?s  i * -(S'+ * rankT * top)"
                    .
                  have "roots ?p4  ?i * -(S'+ * ?rankT * top)"
                  proof -
                    have "?r  -?s"
                      using 5 8 by (meson order.antisym bijective_regular point_in_vector_or_complement point_in_vector_or_complement_2)
                    hence "?s  ?rT  1 = bot"
                      by (metis (full_types) bot_least inf.left_commute inf.sup_monoid.add_commute one_inf_conv pseudo_complement)
                    hence "?p4  1  -?s  ?p2"
                      by (smt (z3) bot_least comp_inf.semiring.distrib_left inf.cobounded2 inf.sup_monoid.add_commute le_supI)
                    hence "roots ?p4  roots (-?s  ?p2)"
                      by (simp add: mult_left_isotone)
                    also have "... = -?s  roots ?p2"
                      using 5 inf_assoc vector_complement_closed vector_inf_comp by auto
                    also have "... = (i * ?rr  -?s  roots ?p2)  (-(i * ?rr)  -?s  roots ?p2)"
                      using 17 by (smt (z3) comp_inf.star_plus inf_sup_distrib2 inf_top.right_neutral regular_complement_top)
                    also have "...  ?i * (-(S'+ * ?rankT * top))"
                    proof (rule sup_least)
                      have "?rankT * top = (?r  (S'T * ?rs)T)T * top  (-?r  rank)T * top"
                        using conv_dist_sup mult_right_dist_sup by auto
                      also have "... = (?rT  S'T * ?rs) * top  (-?rT  rankT) * top"
                        using conv_complement conv_dist_inf conv_involutive by auto
                      also have "... = S'T * ?rs * (?r  top)  (-?rT  rankT) * top"
                        using 5 by (smt (z3) covector_inf_comp_3 inf_commute)
                      also have "... = S'T * ?rs * (?r  top)  rankT * (-?r  top)"
                        using 5 by (smt (z3) conv_complement vector_complement_closed covector_inf_comp_3 inf_commute)
                      also have "... = S'T * ?rs * ?r  rankT * -?r"
                        by simp
                      also have "...  S'T * ?rs * ?r  rankT * top"
                        using mult_right_isotone sup_right_isotone by force
                      also have "...  S'T * ?rs  rankT * top"
                        using 5 6 by (metis inf.eq_refl mult_assoc)
                      finally have "S'+ * ?rankT * top  S'+ * S'T * ?rs  S'+ * rankT * top"
                        by (smt comp_associative mult_left_dist_sup mult_right_isotone)
                      also have "... = S' * (S' * S'T) * ?rs  S'+ * rankT * top"
                        by (smt star_plus mult_assoc)
                      also have "...  S' * ?rs  S'+ * rankT * top"
                        by (metis S'_injective comp_right_one mult_left_isotone mult_right_isotone sup_left_isotone)
                      also have "... = ?rs  S'+ * ?rs  S'+ * rankT * top"
                        using comp_associative star.circ_loop_fixpoint sup_commute by fastforce
                      also have "... = ?rs  S'+ * rankT * top"
                        by (smt (verit, del_insts) comp_associative mult_left_dist_sup sup.orderE sup_assoc sup_commute top.extremum)
                      finally have 20: "S'+ * ?rankT * top  ?rs  S'+ * rankT * top"
                        .
                      have "?s * ?sT = (?s  i * -(S'+ * rankT * top)) * ?sT"
                        using 19 inf.orderE by fastforce
                      also have "... = (?s  i * -(S'+ * rankT * top)) * top  ?sT"
                        using 5 by (smt (z3) covector_comp_inf vector_conv_covector vector_covector vector_top_closed)
                      also have "... = ?s  i * -(S'+ * rankT * top) * top  ?sT"
                        using 5 vector_inf_comp by auto
                      also have "...  1  i * -(S'+ * rankT * top) * top"
                        using 5 by (smt (verit, ccfv_SIG) inf.cobounded1 inf.cobounded2 inf_greatest order_trans vector_covector)
                      also have "... = 1  i * -(S'+ * rankT * top)"
                        using comp_associative vector_complement_closed vector_top_closed by auto
                      also have "...  1  i * -(S'+ * rankT)"
                        by (meson comp_inf.mult_right_isotone mult_right_isotone p_antitone top_right_mult_increasing)
                      also have "...  1  i * S'T * rankT"
                      proof -
                        have "S'T * rankT  S'+ * rankT = (S'T  S'+) * rankT"
                          by (simp add: conv_star_commute mult_right_dist_sup)
                        also have "... = (S'T  S') * rankT"
                          by (smt (z3) comp_associative semiring.distrib_right star.circ_loop_fixpoint sup.left_commute sup_commute sup_idem)
                        also have "... = top * rankT"
                          by (simp add: S'_star_connex sup_commute)
                        also have "... = top"
                          using 4 rank_property_def total_conv_surjective by blast
                        finally have "-(S'+ * rankT)  S'T * rankT"
                          by (metis half_shunting inf.idem top_greatest)
                        thus ?thesis
                          using comp_associative inf.sup_right_isotone mult_right_isotone by auto
                      qed
                      also have "... = 1  rank * S' * iT"
                        by (metis comp_associative conv_dist_comp conv_involutive one_inf_conv)
                      also have "...  rank * S' * iT"
                        by simp
                      finally have "?s  rank * S' * iT * ?s"
                        using 5 shunt_bijective by auto
                      hence "?rs  S' * iT * ?s"
                        using 4 shunt_mapping comp_associative rank_property_def by auto
                      hence "?s * (i * ?rr  -?s  roots ?p2)  ?s * (i * S' * iT * ?s  -?s  roots ?p2)"
                        using 11 comp_associative comp_inf.mult_left_isotone comp_isotone inf.eq_refl by auto
                      also have "... = ?s * ((i * S'+ * iT * ?s  i * iT * ?s)  -?s  roots ?p2)"
                        by (metis comp_associative mult_left_dist_sup star.circ_loop_fixpoint)
                      also have "...  ?s * ((i * S'+ * iT * ?s  1 * ?s)  -?s  roots ?p2)"
                        using 12 by (metis mult_left_isotone sup_right_isotone comp_inf.mult_left_isotone mult_right_isotone)
                      also have "... = ?s * (i * S'+ * iT * ?s  -?s  roots ?p2)"
                        using comp_inf.comp_right_dist_sup by simp
                      also have "...  ?s * (i * S'+ * iT * ?s  roots ?p2)"
                        using comp_inf.mult_left_isotone inf.cobounded1 mult_right_isotone by blast
                      also have "...  ?s * (i * S'+ * iT * ?s  i * -(S'+ * rankT * top))"
                        using 12 comp_inf.mult_right_isotone mult_right_isotone by auto
                      also have "... = ?s * (i * S'+ * iT * ?s  i) * -(S'+ * rankT * top)"
                        using 5 by (simp add: comp_associative vector_inf_comp)
                      also have "... = (?s  (i * S'+ * iT * ?s)T) * i * -(S'+ * rankT * top)"
                        using 5 covector_inf_comp_3 mult_assoc by auto
                      also have "... = (?s  ?sT * i * S'+T * iT) * i * -(S'+ * rankT * top)"
                        using conv_dist_comp conv_involutive mult_assoc by auto
                      also have "... = (?s  ?sT) * i * S'+T * iT * i * -(S'+ * rankT * top)"
                        using 5 vector_inf_comp by auto
                      also have "...  i * S'+T * iT * i * -(S'+ * rankT * top)"
                        using 5 by (metis point_antisymmetric mult_left_isotone mult_left_one)
                      also have "...  i * S'+T * -(S'+ * rankT * top)"
                        using 12 by (smt mult_left_isotone mult_right_isotone mult_assoc comp_right_one)
                      also have "...  i * -(S' * rankT * top)"
                      proof -
                        have "S'+ * S' * rankT * top  S'+ * rankT * top"
                          by (simp add: comp_associative star.circ_transitive_equal)
                        hence "S'+T * -(S'+ * rankT * top)  -(S' * rankT * top)"
                          by (smt (verit, ccfv_SIG) comp_associative conv_complement_sub_leq mult_right_isotone order.trans p_antitone)
                        thus ?thesis
                          by (simp add: comp_associative mult_right_isotone)
                      qed
                      also have "...  i * -(S'+ * ?rankT * top)"
                      proof -
                        have "S'+ * ?rankT * top  ?rs  S'+ * rankT * top"
                          using 20 by simp
                        also have "...  rankT * top  S'+ * rankT * top"
                          using mult_right_isotone sup_left_isotone top.extremum by blast
                        also have "... = S' * rankT * top"
                          using comp_associative star.circ_loop_fixpoint sup_commute by auto
                        finally show ?thesis
                          using mult_right_isotone p_antitone by blast
                      qed
                      finally have "?s * (i * ?rr  -?s  roots ?p2)  i * -(S'+ * ?rankT * top)"
                        .
                      hence "i * ?rr  -?s  roots ?p2  ?sT * i * -(S'+ * ?rankT * top)"
                        using 5 shunt_mapping bijective_conv_mapping mult_assoc by auto
                      hence "i * ?rr  -?s  roots ?p2  i * ?rr  ?sT * i * -(S'+ * ?rankT * top)"
                        by (simp add: inf.sup_monoid.add_assoc)
                      also have "... = (i * ?rr  ?sT * i) * -(S'+ * ?rankT * top)"
                        using 6 vector_inf_comp vector_mult_closed by simp
                      also have "...  ?i * -(S'+ * ?rankT * top)"
                        using 13 comp_left_increasing_sup sup_assoc by auto
                      finally show "i * ?rr  -?s  roots ?p2  ?i * -(S'+ * ?rankT * top)"
                        .
                      have "-(i * ?rr)  roots ?p2  -(i * ?rr)  i * -(S'+ * rankT * top)"
                        using 12 inf.sup_right_isotone by auto
                      also have "...  -(i * ?rr)  i * -(?rs  S'+ * rankT * top)"
                      proof -
                        have 21: "regular (?rs  S'+ * rankT * top)"
                          using 4 6 rank_property_def mapping_regular S'_regular pp_dist_star regular_conv_closed regular_mult_closed bijective_regular regular_closed_sup by auto
                        have "?rs  S'+ * rankT * top  S'+ * rankT * top  ?rr"
                          using 11 by simp
                        hence "(?rs  S'+ * rankT * top) - S'+ * rankT * top  ?rr"
                          using half_shunting sup_commute by auto
                        hence "-(S'+ * rankT * top)  -(?rs  S'+ * rankT * top)  ?rr"
                          using 21 by (metis inf.sup_monoid.add_commute shunting_var_p sup_commute)
                        hence "i * -(S'+ * rankT * top)  i * -(?rs  S'+ * rankT * top)  i * ?rr"
                          by (metis mult_left_dist_sup mult_right_isotone)
                        hence "-(i * ?rr)  i * -(S'+ * rankT * top)  i * -(?rs  S'+ * rankT * top)"
                          using half_shunting inf.sup_monoid.add_commute by fastforce
                        thus ?thesis
                          using inf.le_sup_iff by blast
                      qed
                      also have "...  -(i * ?rr)  i * -(S'+ * ?rankT * top)"
                        using 20 by (meson comp_inf.mult_right_isotone mult_right_isotone p_antitone)
                      finally have "-(i * ?rr)  -?s  roots ?p2  -(i * ?rr)  -?s  i * -(S'+ * ?rankT * top)"
                        by (smt (z3) inf.boundedI inf.cobounded1 inf.coboundedI2 inf.sup_monoid.add_assoc inf.sup_monoid.add_commute)
                      also have "...  ?i * (-(S'+ * ?rankT * top))"
                        using 5 6 13 by (smt (z3) sup_commute vector_complement_closed vector_inf_comp vector_mult_closed comp_left_increasing_sup)
                      finally show "-(i * ?rr)  -?s  roots ?p2  ?i * -(S'+ * ?rankT * top)"
                        .
                    qed
                    finally show ?thesis
                      .
                  qed
                  thus "card_less_eq (roots ?p4) (-(S'+ * ?rankT * top))"
                    using 14 15 16 card_less_eq_def by auto
                  have "?s  i * -(S'+ * rankT * top)"
                    using 19 by simp
                  also have "...  i * -(S'+ * ?rr)"
                    using mult_right_isotone p_antitone top.extremum mult_assoc by auto
                  also have "... = i * -S'+ * ?rr"
                    using 6 comp_bijective_complement mult_assoc by fastforce
                  finally have "?rr  -S'T+ * iT * ?s"
                    using 5 6 by (metis conv_complement conv_dist_comp conv_plus_commute bijective_reverse)
                  also have "...  S' * iT * ?s"
                    using 7 conv_plus_commute mult_left_isotone by auto
                  finally have 22: "?rr  S' * iT * ?s"
                    .
                  have "?r = root ?p1 x"
                    using 2 path_compression_postcondition_def by blast
                  also have "... = root ?p2 x"
                    using 3 18 by (smt (z3) find_set_precondition_def path_compression_postcondition_def same_root)
                  also have "...  roots ?p2"
                    by simp
                  also have "...  i * -(S'+ * rankT * top)"
                    using 12 by simp
                  also have "...  i * -(S'+ * ?rr)"
                    using mult_right_isotone p_antitone top.extremum mult_assoc by auto
                  also have "... = i * -S'+ * ?rr"
                    using 6 comp_bijective_complement mult_assoc by fastforce
                  finally have "?rr  -S'T+ * iT * ?r"
                    using 5 6 by (metis conv_complement conv_dist_comp conv_plus_commute bijective_reverse)
                  also have "...  S' * iT * ?r"
                    using 7 conv_plus_commute mult_left_isotone by auto
                  finally have "?rr  S' * iT * ?r"
                    .
                  hence "?rr  S' * iT * ?r  S' * iT * ?s"
                    using 22 inf.boundedI by blast
                  also have "... = (S'+ * iT * ?r  iT * ?r)  S' * iT * ?s"
                    by (simp add: star.circ_loop_fixpoint mult_assoc)
                  also have "...  S'+ * iT * ?r  (iT * ?r  S' * iT * ?s)"
                    by (metis comp_inf.mult_right_dist_sup eq_refl inf.cobounded1 semiring.add_mono)
                  also have "...  S' * top  (iT * ?r  S' * iT * ?s)"
                    using comp_associative mult_right_isotone sup_left_isotone top.extremum by auto
                  also have "... = S' * top  (iT * ?r  (S'+ * iT * ?s  iT * ?s))"
                    by (simp add: star.circ_loop_fixpoint mult_assoc)
                  also have "...  S' * top  S'+ * iT * ?s  (iT * ?r  iT * ?s)"
                    by (smt (z3) comp_inf.semiring.distrib_left inf.sup_right_divisibility star.circ_loop_fixpoint sup_assoc sup_commute sup_inf_distrib1)
                  also have "...  S' * top  (iT * ?r  iT * ?s)"
                    by (metis comp_associative mult_right_isotone order.refl sup.orderE top.extremum)
                  also have "... = S' * top  iT * (?r  ?s)"
                    using 12 conv_involutive univalent_comp_left_dist_inf by auto
                  also have "... = S' * top"
                    using 5 8 distinct_points by auto
                  finally have "top  ?rrT * S' * top"
                    using 6 by (smt conv_involutive shunt_mapping bijective_conv_mapping mult_assoc)
                  hence "surjective (S'T * ?rs)"
                    using 6 11 by (smt conv_dist_comp conv_involutive point_conv_comp top_le)
                  thus "total ?rank"
                    using 4 5 bijective_regular update_total rank_property_def by blast
                  show "(?p4 - 1) * ?rank  ?rank * S'+"
                  proof -
                    have 23: "univalent ?p2"
                      using 3 path_compression_postcondition_def by blast
                    have 24: "?r  (?p4 - 1) * ?rank  ?sT * rank * S' * S'+"
                    proof -
                      have "?r  (?p4 - 1) * ?rank = (?r  ?p4  -1) * ?rank"
                        using 5 vector_complement_closed vector_inf_comp inf_assoc by auto
                      also have "... = (?r  -?s  ?p4  -1) * ?rank"
                          using 5 8 by (smt (z3) order.antisym bijective_regular point_in_vector_or_complement point_in_vector_or_complement_2 inf_absorb1)
                      also have "... = (?r  -?s  ?p2  -1) * ?rank"
                        by (simp add: inf.left_commute inf.sup_monoid.add_commute inf_sup_distrib1 inf_assoc)
                      also have "...  (?r  ?p2  -1) * ?rank"
                        using inf.sup_left_isotone inf_le1 mult_left_isotone by blast
                      also have "... = bot"
                      proof -
                        have "?r = root ?p1 x"
                          using 2 path_compression_postcondition_def by blast
                        also have "... = root ?p2 x"
                          using 3 18 by (smt (z3) find_set_precondition_def path_compression_postcondition_def same_root)
                        also have "...  roots ?p2"
                          by simp
                        finally have "?r  ?p2  roots ?p2  ?p2"
                          using inf.sup_left_isotone by blast
                        also have "...  (?p2  1) * (?p2  1)T * ?p2"
                          by (smt (z3) comp_associative comp_inf.star_plus dedekind_1 inf_top_right order_lesseq_imp)
                        also have "... = (?p2  1) * (?p2  1) * ?p2"
                          using coreflexive_symmetric by force
                        also have "...  (?p2  1) * ?p2"
                          by (metis coreflexive_comp_top_inf inf.cobounded2 mult_left_isotone)
                        also have "...  ?p2  1"
                          by (smt 23 comp_inf.mult_semi_associative conv_dist_comp conv_dist_inf conv_order equivalence_one_closed inf.absorb1 inf.sup_monoid.add_assoc injective_codomain)
                        also have "...  1"
                          by simp
                        finally have "?r  ?p2  1"
                          .
                        thus ?thesis
                          by (metis pseudo_complement regular_one_closed semiring.mult_not_zero)
                      qed
                      finally show ?thesis
                        using bot_least le_bot by blast
                    qed
                    have 25: "-?r  (?p4 - 1) * ?rank  rank * S'+"
                    proof -
                      have "-?r  (?p4 - 1) * ?rank = (-?r  ?p4  -1) * ?rank"
                        using 5 vector_complement_closed vector_inf_comp inf_assoc by auto
                      also have "... = (-?r  (?s  -?s)  ?p4  -1) * ?rank"
                        using 5 bijective_regular inf_top_right regular_complement_top by auto
                      also have "... = (-?r  ?s  ?p4  -1) * ?rank  (-?r  -?s  ?p4  -1) * ?rank"
                        by (smt (z3) inf_sup_distrib1 inf_sup_distrib2 mult_right_dist_sup)
                      also have "... = (-?r  ?s  ?rT  -1) * ?rank  (-?r  -?s  ?p2  -1) * ?rank"
                        using 5 by (smt (z3) bijective_regular comp_inf.comp_left_dist_sup inf_assoc inf_commute inf_top_right mult_right_dist_sup regular_complement_top)
                      also have "...  (?s  ?rT  -1) * ?rank  (-?s  ?p2  -1) * ?rank"
                        by (smt (z3) comp_inf.semiring.distrib_left inf.cobounded2 inf.sup_monoid.add_assoc mult_left_isotone mult_right_dist_sup)
                      also have "...  (?s  ?rT) * ?rank  (?p2 - 1) * ?rank"
                        by (smt (z3) inf.cobounded1 inf.cobounded2 inf.sup_monoid.add_assoc mult_left_isotone semiring.add_mono)
                      also have "... = ?s * (?r  ?rank)  (?p2 - 1) * ?rank"
                        using 5 by (simp add: covector_inf_comp_3)
                      also have "... = ?s * (?r  (S'T * ?rs)T)  (?p2 - 1) * ?rank"
                        using inf_commute update_inf_same mult_assoc by force
                      also have "... = ?s * (?r  ?sT * rank * S')  (?p2 - 1) * ?rank"
                        using comp_associative conv_dist_comp conv_involutive by auto
                      also have "...  ?s * ?sT * rank * S'  (?p2 - 1) * ?rank"
                        using comp_associative inf.cobounded2 mult_right_isotone semiring.add_right_mono by auto
                      also have "...  1 * rank * S'  (?p2 - 1) * ?rank"
                        using 5 by (meson mult_left_isotone order.refl semiring.add_mono)
                      also have "... = rank * S'  (?p2 - 1) * (?r  (S'T * ?rr)T)  (?p2 - 1) * (-?r  rank)"
                        using 11 comp_associative mult_1_left mult_left_dist_sup sup_assoc by auto
                      also have "...  rank * S'  (?p2 - 1) * (?r  ?rT * rank * S')  (?p2 - 1) * rank"
                        using comp_associative conv_dist_comp conv_involutive inf.cobounded1 inf.sup_monoid.add_commute mult_right_isotone semiring.add_left_mono by auto
                      also have "... = rank * S'  (?p2 - 1) * (?r  ?rT) * rank * S'  (?p2 - 1) * rank"
                        using 5 comp_associative vector_inf_comp by auto
                      also have "...  rank * S'  (?p2 - 1) * rank * S'  (?p2 - 1) * rank"
                        using 5 by (metis point_antisymmetric mult_left_isotone mult_right_isotone sup_left_isotone sup_right_isotone comp_right_one)
                      also have "...  rank * S'  rank * S'+ * S'  (?p2 - 1) * rank"
                        using 4 by (metis rank_property_def mult_left_isotone sup_left_isotone sup_right_isotone)
                      also have "...  rank * S'  rank * S'+ * S'  rank * S'+"
                        using 4 by (metis rank_property_def sup_right_isotone)
                      also have "...  rank * S'+"
                        using comp_associative eq_refl le_sup_iff mult_right_isotone star.circ_mult_increasing star.circ_plus_same star.left_plus_below_circ by auto
                      finally show ?thesis
                        .
                    qed
                    have "(?p4 - 1) * ?rank = (?r  (?p4 - 1) * ?rank)  (-?r  (?p4 - 1) * ?rank)"
                      using 5 by (smt (verit, ccfv_threshold) bijective_regular inf_commute inf_sup_distrib2 inf_top_right regular_complement_top)
                    also have "...  (?r  ?sT * rank * S' * S'+)  (-?r  rank * S'+)"
                      using 24 25 by (meson inf.boundedI inf.cobounded1 semiring.add_mono)
                    also have "... = (?r  ?sT * rank * S') * S'+  (-?r  rank) * S'+"
                      using 5 vector_complement_closed vector_inf_comp by auto
                    also have "... = ?rank * S'+"
                      using conv_dist_comp mult_right_dist_sup by auto
                    finally show ?thesis
                      .
                  qed
                qed
              qed
            qed
            show "?rr  ?rs  union_sets_postcondition ?p4 x y p0  rank_property ?p4 rank"
            proof
              assume "?rr  ?rs"
              hence "?rs  ?rr = bot"
                using 6 by (meson bijective_regular dual_order.eq_iff point_in_vector_or_complement point_in_vector_or_complement_2 pseudo_complement)
              hence 26: "?rs  S'+ * ?rr"
                using 10 le_iff_inf pseudo_complement by auto
              show "union_sets_postcondition ?p4 x y p0  rank_property ?p4 rank"
              proof
                show "union_sets_postcondition ?p4 x y p0"
                  using 1 2 3 by (simp add: union_sets_1_swap)
                show "rank_property ?p4 rank"
                proof (unfold rank_property_def, intro conjI)
                  show "univalent rank" "total rank"
                    using 1 rank_property_def by auto
                  have "?r  -?s"
                    using 5 8 by (meson order.antisym bijective_regular point_in_vector_or_complement point_in_vector_or_complement_2)
                  hence "?s  ?rT  1 = bot"
                    by (metis (full_types) bot_least inf.left_commute inf.sup_monoid.add_commute one_inf_conv pseudo_complement)
                  hence "?p4  1  ?p2"
                    by (smt half_shunting inf.cobounded2 pseudo_complement regular_one_closed semiring.add_mono sup_commute)
                  hence "roots ?p4  roots ?p2"
                    by (simp add: mult_left_isotone)
                  thus "card_less_eq (roots ?p4) (-(S'+ * rankT * top))"
                    using 4 by (meson rank_property_def card_less_eq_def order_trans)
                  have "(?p4 - 1) * rank = (?s  ?rT  -1) * rank  (-?s  ?p2  -1) * rank"
                    using comp_inf.semiring.distrib_right mult_right_dist_sup by auto
                  also have "...  (?s  ?rT  -1) * rank  (?p2 - 1) * rank"
                    using comp_inf.mult_semi_associative mult_left_isotone sup_right_isotone by auto
                  also have "...  (?s  ?rT  -1) * rank  rank * S'+"
                    using 4 sup_right_isotone rank_property_def by blast
                  also have "...  (?s  ?rT) * rank  rank * S'+"
                    using inf_le1 mult_left_isotone sup_left_isotone by blast
                  also have "... = ?s * ?rT * rank  rank * S'+"
                    using 5 by (simp add: vector_covector)
                  also have "... = rank * S'+"
                  proof -
                    have "rankT * ?s  S'+ * rankT * ?r"
                      using 26 comp_associative by auto
                    hence "?s  rank * S'+ * rankT * ?r"
                      using 4 shunt_mapping comp_associative rank_property_def by auto
                    hence "?s * ?rT  rank * S'+ * rankT"
                      using 5 shunt_bijective by blast
                    hence "?s * ?rT * rank  rank * S'+"
                      using 4 shunt_bijective rank_property_def mapping_conv_bijective by auto
                    thus ?thesis
                      using sup_absorb2 by blast
                  qed
                  finally show "(?p4 - 1) * rank  rank * S'+"
                    .
                qed
              qed
            qed
          qed
        qed
      qed
    qed
    show "?r = ?s  union_sets_postcondition ?p5 x y p0  rank_property ?p5 rank"
    proof
      assume 27: "?r = ?s"
      show "union_sets_postcondition ?p5 x y p0  rank_property ?p5 rank"
      proof
        show "union_sets_postcondition ?p5 x y p0"
          using 1 2 3 27 by (simp add: union_sets_1_skip)
        show "rank_property ?p5 rank"
          using 4 27 by simp
      qed
    qed
  qed
qed

end

end