Theory Containers.Set_Linorder
theory Set_Linorder
imports
Containers_Auxiliary
Lexicographic_Order
Extend_Partial_Order
"HOL-Library.Cardinality"
begin
section ‹An executable linear order on sets›
subsection ‹Definition of the linear order›
subsubsection ‹Extending finite and cofinite sets›
text ‹
Partition sets into finite and cofinite sets and distribute the rest arbitrarily such that
complement switches between the two.
›
consts infinite_complement_partition :: "'a set set"
specification (infinite_complement_partition)
finite_complement_partition: "finite (A :: 'a set) ⟹ A ∈ infinite_complement_partition"
complement_partition: "¬ finite (UNIV :: 'a set)
⟹ (A :: 'a set) ∈ infinite_complement_partition ⟷ - A ∉ infinite_complement_partition"
proof(cases "finite (UNIV :: 'a set)")
case False
define Field_r where "Field_r = {𝒫 :: 'a set set. (∀C ∈ 𝒫. - C ∉ 𝒫) ∧ (∀A. finite A ⟶ A ∈ 𝒫)}"
define r where "r = {(𝒫1, 𝒫2). 𝒫1 ⊆ 𝒫2 ∧ 𝒫1 ∈ Field_r ∧ 𝒫2 ∈ Field_r}"
have in_Field_r [simp]: "⋀𝒫. 𝒫 ∈ Field_r ⟷ (∀C ∈ 𝒫. - C ∉ 𝒫) ∧ (∀A. finite A ⟶ A ∈ 𝒫)"
unfolding Field_r_def by simp
have in_r [simp]: "⋀𝒫1 𝒫2. (𝒫1, 𝒫2) ∈ r ⟷ 𝒫1 ⊆ 𝒫2 ∧ 𝒫1 ∈ Field_r ∧ 𝒫2 ∈ Field_r"
unfolding r_def by simp
have Field_r [simp]: "Field r = Field_r" by(auto simp add: Field_def Field_r_def)
have "Partial_order r"
by(auto simp add: Field_def r_def partial_order_on_def preorder_on_def intro!: refl_onI transI antisymI)
moreover have "∃ℬ ∈ Field r. ∀𝒜 ∈ ℭ. (𝒜, ℬ) ∈ r" if ℭ: "ℭ ∈ Chains r" for ℭ
proof -
let ?ℬ = "⋃ℭ ∪ {A. finite A}"
have *: "?ℬ ∈ Field r" using False ℭ
by clarsimp(safe, drule (2) ChainsD, auto 4 4 dest: Chains_Field)
hence "⋀𝒜. 𝒜 ∈ ℭ ⟹ (𝒜, ?ℬ) ∈ r"
using ℭ by(auto simp del: in_Field_r dest: Chains_Field)
with * show "∃ℬ ∈ Field r. ∀𝒜 ∈ ℭ. (𝒜, ℬ) ∈ r" by blast
qed
ultimately have "∃𝒫 ∈ Field r. ∀𝒜 ∈ Field r. (𝒫, 𝒜) ∈ r ⟶ 𝒜 = 𝒫"
by(rule Zorns_po_lemma)
then obtain 𝒫 where 𝒫: "𝒫 ∈ Field r"
and max: "⋀𝒜. ⟦ 𝒜 ∈ Field r; (𝒫, 𝒜) ∈ r ⟧ ⟹ 𝒜 = 𝒫" by blast
have "∀A. finite A ⟶ A ∈ 𝒫" using 𝒫 by simp
moreover {
fix C
have "C ∈ 𝒫 ∨ - C ∈ 𝒫"
proof(rule ccontr)
assume "¬ ?thesis"
hence C: "C ∉ 𝒫" "- C ∉ 𝒫" by simp_all
let ?𝒜 = "insert C 𝒫"
have *: "?𝒜 ∈ Field r" using C 𝒫 by auto
hence "(𝒫, ?𝒜) ∈ r" using 𝒫 by auto
with * have "?𝒜 = 𝒫" by(rule max)
thus False using C by auto
qed
hence "C ∈ 𝒫 ⟷ - C ∉ 𝒫" using 𝒫 by auto }
ultimately have "∃𝒫 :: 'a set set. (∀A. finite A ⟶ A ∈ 𝒫) ∧ (∀C. C ∈ 𝒫 ⟷ - C ∉ 𝒫)"
by blast
thus ?thesis by metis
qed auto
lemma not_in_complement_partition:
"¬ finite (UNIV :: 'a set)
⟹ (A :: 'a set) ∉ infinite_complement_partition ⟷ - A ∈ infinite_complement_partition"
by(metis complement_partition)
lemma not_in_complement_partition_False:
"⟦ (A :: 'a set) ∈ infinite_complement_partition; ¬ finite (UNIV :: 'a set) ⟧
⟹ - A ∈ infinite_complement_partition = False"
by(simp add: not_in_complement_partition)
lemma infinite_complement_partition_finite [simp]:
"finite (UNIV :: 'a set) ⟹ infinite_complement_partition = (UNIV :: 'a set set)"
by(auto intro: finite_subset finite_complement_partition)
lemma Compl_eq_empty_iff: "- A = {} ⟷ A = UNIV"
by auto
subsubsection ‹A lexicographic-style order on finite subsets›
context ord begin
definition set_less_aux :: "'a set ⇒ 'a set ⇒ bool" (infix "⊏''" 50)
where "A ⊏' B ⟷ finite A ∧ finite B ∧ (∃y ∈ B - A. ∀z ∈ (A - B) ∪ (B - A). y ≤ z ∧ (z ≤ y ⟶ y = z))"
definition set_less_eq_aux :: "'a set ⇒ 'a set ⇒ bool" (infix "⊑''" 50)
where "A ⊑' B ⟷ A ∈ infinite_complement_partition ∧ A = B ∨ A ⊏' B"
lemma set_less_aux_irrefl [iff]: "¬ A ⊏' A"
by(auto simp add: set_less_aux_def)
lemma set_less_eq_aux_refl [iff]: "A ⊑' A ⟷ A ∈ infinite_complement_partition"
by(simp add: set_less_eq_aux_def)
lemma set_less_aux_empty [simp]: "¬ A ⊏' {}"
by(auto simp add: set_less_aux_def intro: finite_subset finite_complement_partition)
lemma set_less_eq_aux_empty [simp]: "A ⊑' {} ⟷ A = {}"
by(auto simp add: set_less_eq_aux_def finite_complement_partition)
lemma set_less_aux_antisym: "⟦ A ⊏' B; B ⊏' A ⟧ ⟹ False"
by(auto simp add: set_less_aux_def split: if_split_asm)
lemma set_less_aux_conv_set_less_eq_aux:
"A ⊏' B ⟷ A ⊑' B ∧ ¬ B ⊑' A"
by(auto simp add: set_less_eq_aux_def dest: set_less_aux_antisym)
lemma set_less_eq_aux_antisym: "⟦ A ⊑' B; B ⊑' A ⟧ ⟹ A = B"
by(auto simp add: set_less_eq_aux_def dest: set_less_aux_antisym)
lemma set_less_aux_finiteD: "A ⊏' B ⟹ finite A ∧ B ∈ infinite_complement_partition"
by(auto simp add: set_less_aux_def finite_complement_partition)
lemma set_less_eq_aux_infinite_complement_partitionD:
"A ⊑' B ⟹ A ∈ infinite_complement_partition ∧ B ∈ infinite_complement_partition"
by(auto simp add: set_less_eq_aux_def dest: set_less_aux_finiteD intro: finite_complement_partition)
lemma Compl_set_less_aux_Compl:
"finite (UNIV :: 'a set) ⟹ - A ⊏' - B ⟷ B ⊏' A"
by(auto simp add: set_less_aux_def finite_subset[OF subset_UNIV])
lemma Compl_set_less_eq_aux_Compl:
"finite (UNIV :: 'a set) ⟹ - A ⊑' - B ⟷ B ⊑' A"
by(auto simp add: set_less_eq_aux_def Compl_set_less_aux_Compl)
lemma set_less_aux_insert_same:
"x ∈ A ⟷ x ∈ B ⟹ insert x A ⊏' insert x B ⟷ A ⊏' B"
by(auto simp add: set_less_aux_def)
lemma set_less_eq_aux_insert_same:
"⟦ A ∈ infinite_complement_partition; insert x B ∈ infinite_complement_partition;
x ∈ A ⟷ x ∈ B ⟧
⟹ insert x A ⊑' insert x B ⟷ A ⊑' B"
by(auto simp add: set_less_eq_aux_def set_less_aux_insert_same)
end
context order begin
lemma set_less_aux_singleton_iff: "A ⊏' {x} ⟷ finite A ∧ (∀a∈A. x < a)"
by(auto simp add: set_less_aux_def less_le Bex_def)
end
context linorder begin
lemma wlog_le [case_names sym le]:
assumes "⋀a b. P a b ⟹ P b a"
and "⋀a b. a ≤ b ⟹ P a b"
shows "P b a"
by (metis assms linear)
lemma empty_set_less_aux [simp]: "{} ⊏' A ⟷ A ≠ {} ∧ finite A"
by(auto 4 3 simp add: set_less_aux_def intro!: Min_eqI intro: bexI[where x="Min A"] order_trans[where y="Min A"] Min_in)
lemma empty_set_less_eq_aux [simp]: "{} ⊑' A ⟷ finite A"
by(auto simp add: set_less_eq_aux_def finite_complement_partition)
lemma set_less_aux_trans:
assumes AB: "A ⊏' B" and BC: "B ⊏' C"
shows "A ⊏' C"
proof -
from AB BC have A: "finite A" and B: "finite B" and C: "finite C"
by(auto simp add: set_less_aux_def)
from AB A B obtain ab where ab: "ab ∈ B - A"
and minAB: "⋀x. ⟦ x ∈ A; x ∉ B ⟧ ⟹ ab ≤ x ∧ (x ≤ ab ⟶ ab = x)"
and minBA: "⋀x. ⟦ x ∈ B; x ∉ A ⟧ ⟹ ab ≤ x ∧ (x ≤ ab ⟶ ab = x)"
unfolding set_less_aux_def by auto
from BC B C obtain bc where bc: "bc ∈ C - B"
and minBC: "⋀x. ⟦ x ∈ B; x ∉ C ⟧ ⟹ bc ≤ x ∧ (x ≤ bc ⟶ bc = x)"
and minCB: "⋀x. ⟦ x ∈ C; x ∉ B ⟧ ⟹ bc ≤ x ∧ (x ≤ bc ⟶ bc = x)"
unfolding set_less_aux_def by auto
show ?thesis
proof(cases "ab ≤ bc")
case True
hence "ab ∈ C - A" "ab ∉ A - C"
using ab bc by(auto dest: minBC antisym)
moreover {
fix x
assume x: "x ∈ (C - A) ∪ (A - C)"
hence "ab ≤ x"
by(cases "x ∈ B")(auto dest: minAB minBA minBC minCB intro: order_trans[OF True])
moreover hence "ab ≠ x ⟶ ¬ x ≤ ab" using ab bc x
by(cases "x ∈ B")(auto dest: antisym)
moreover note calculation }
ultimately show ?thesis using A C unfolding set_less_aux_def by auto
next
case False
with linear[of ab bc] have "bc ≤ ab" by simp
with ab bc have "bc ∈ C - A" "bc ∉ A - C" by(auto dest: minAB antisym)
moreover {
fix x
assume x: "x ∈ (C - A) ∪ (A - C)"
hence "bc ≤ x"
by(cases "x ∈ B")(auto dest: minAB minBA minBC minCB intro: order_trans[OF ‹bc ≤ ab›])
moreover hence "bc ≠ x ⟶ ¬ x ≤ bc" using ab bc x
by(cases "x ∈ B")(auto dest: antisym)
moreover note calculation }
ultimately show ?thesis using A C unfolding set_less_aux_def by auto
qed
qed
lemma set_less_eq_aux_trans [trans]:
"⟦ A ⊑' B; B ⊑' C ⟧ ⟹ A ⊑' C"
by(auto simp add: set_less_eq_aux_def dest: set_less_aux_trans)
lemma set_less_trans_set_less_eq [trans]:
"⟦ A ⊏' B; B ⊑' C ⟧ ⟹ A ⊏' C"
by(auto simp add: set_less_eq_aux_def dest: set_less_aux_trans)
lemma set_less_eq_aux_porder: "partial_order_on infinite_complement_partition {(A, B). A ⊑' B}"
by(auto simp add: preorder_on_def partial_order_on_def intro!: refl_onI transI antisymI dest: set_less_eq_aux_infinite_complement_partitionD intro: set_less_eq_aux_antisym set_less_eq_aux_trans del: equalityI)
lemma psubset_finite_imp_set_less_aux:
assumes AsB: "A ⊂ B" and B: "finite B"
shows "A ⊏' B"
proof -
from AsB B have A: "finite A" by(auto intro: finite_subset)
moreover from AsB B have "Min (B - A) ∈ B - A" by - (rule Min_in, auto)
ultimately show ?thesis using B AsB
by(auto simp add: set_less_aux_def intro!: rev_bexI[where x="Min (B - A)"] Min_eqI dest: Min_ge_iff[THEN iffD1, rotated 2])
qed
lemma subset_finite_imp_set_less_eq_aux:
"⟦ A ⊆ B; finite B ⟧ ⟹ A ⊑' B"
by(cases "A = B")(auto simp add: set_less_eq_aux_def finite_complement_partition intro: psubset_finite_imp_set_less_aux)
lemma empty_set_less_aux_finite_iff:
"finite A ⟹ {} ⊏' A ⟷ A ≠ {}"
by(auto intro: psubset_finite_imp_set_less_aux)
lemma set_less_aux_finite_total:
assumes A: "finite A" and B: "finite B"
shows "A ⊏' B ∨ A = B ∨ B ⊏' A"
proof(cases "A ⊆ B ∨ B ⊆ A")
case True thus ?thesis
using A B psubset_finite_imp_set_less_aux[of A B] psubset_finite_imp_set_less_aux[of B A]
by auto
next
case False
hence A': "¬ A ⊆ B" and B': "¬ B ⊆ A" and AnB: "A ≠ B" by auto
thus ?thesis using A B
proof(induct "Min (B - A)" "Min (A - B)" arbitrary: A B rule: wlog_le)
case (sym m n)
from sym.hyps[OF refl refl] sym.prems show ?case by blast
next
case (le A B)
note A = ‹finite A› and B = ‹finite B›
and A' = ‹¬ A ⊆ B› and B' = ‹¬ B ⊆ A›
{ fix z
assume z: "z ∈ (A - B) ∪ (B - A)"
hence "Min (B - A) ≤ z ∧ (z ≤ Min (B - A) ⟶ Min (B - A) = z)"
proof
assume "z ∈ B - A"
hence "Min (B - A) ≤ z" by(simp add: B)
thus ?thesis by auto
next
assume "z ∈ A - B"
hence "Min (A - B) ≤ z" by(simp add: A)
with le.hyps show ?thesis by(auto)
qed }
moreover have "Min (B - A) ∈ B - A" by(rule Min_in)(simp_all add: B B')
ultimately have "A ⊏' B" using A B by(auto simp add: set_less_aux_def)
thus ?case ..
qed
qed
lemma set_less_eq_aux_finite_total:
"⟦ finite A; finite B ⟧ ⟹ A ⊑' B ∨ A = B ∨ B ⊑' A"
by(drule (1) set_less_aux_finite_total)(auto simp add: set_less_eq_aux_def)
lemma set_less_eq_aux_finite_total2:
"⟦ finite A; finite B ⟧ ⟹ A ⊑' B ∨ B ⊑' A"
by(drule (1) set_less_eq_aux_finite_total)(auto simp add: finite_complement_partition)
lemma set_less_aux_rec:
assumes A: "finite A" and B: "finite B"
and A': "A ≠ {}" and B': "B ≠ {}"
shows "A ⊏' B ⟷ Min B < Min A ∨ Min A = Min B ∧ A - {Min A} ⊏' B - {Min A}"
proof(cases "Min A = Min B")
case True
from A A' B B' have "insert (Min A) A = A" "insert (Min B) B = B"
by(auto simp add: ex_in_conv[symmetric] exI)
with True show ?thesis
by(subst (2) set_less_aux_insert_same[symmetric, where x="Min A"]) simp_all
next
case False
have "A ⊏' B ⟷ Min B < Min A"
proof
assume AB: "A ⊏' B"
with B A obtain ab where ab: "ab ∈ B - A"
and AB: "⋀x. ⟦ x ∈ A; x ∉ B ⟧ ⟹ ab ≤ x"
by(auto simp add: set_less_aux_def)
{ fix a assume "a ∈ A"
hence "Min B ≤ a" using A A' B B' ab
by(cases "a ∈ B")(auto intro: order_trans[where y=ab] dest: AB) }
hence "Min B ≤ Min A" using A A' by simp
with False show "Min B < Min A" using False by auto
next
assume "Min B < Min A"
hence "∀z∈A - B ∪ (B - A). Min B ≤ z ∧ (z ≤ Min B ⟶ Min B = z)"
using A B A' B' by(auto 4 4 intro: Min_in Min_eqI dest: bspec bspec[where x="Min B"])
moreover have "Min B ∉ A" using ‹Min B < Min A› by (metis A Min_le not_less)
ultimately show "A ⊏' B" using A B A' B' by(simp add: set_less_aux_def bexI[where x="Min B"])
qed
thus ?thesis using False by simp
qed
lemma set_less_eq_aux_rec:
assumes "finite A" "finite B" "A ≠ {}" "B ≠ {}"
shows "A ⊑' B ⟷ Min B < Min A ∨ Min A = Min B ∧ A - {Min A} ⊑' B - {Min A}"
proof(cases "A = B")
case True thus ?thesis using assms by(simp add: finite_complement_partition)
next
case False
moreover
hence "Min A = Min B ⟹ A - {Min A} ≠ B - {Min B}"
by (metis (lifting) assms Min_in insert_Diff)
ultimately show ?thesis using set_less_aux_rec[OF assms]
by(simp add: set_less_eq_aux_def cong: conj_cong)
qed
lemma set_less_aux_Min_antimono:
"⟦ Min A < Min B; finite A; finite B; A ≠ {} ⟧ ⟹ B ⊏' A"
using set_less_aux_rec[of B A]
by(cases "B = {}")(simp_all add: empty_set_less_aux_finite_iff)
lemma sorted_Cons_Min: "sorted (x # xs) ⟹ Min (insert x (set xs)) = x"
by(auto simp add: intro: Min_eqI)
lemma set_less_aux_code:
"⟦ sorted xs; distinct xs; sorted ys; distinct ys ⟧
⟹ set xs ⊏' set ys ⟷ ord.lexordp (>) xs ys"
apply(induct xs ys rule: list_induct2')
apply(simp_all add: empty_set_less_aux_finite_iff sorted_Cons_Min set_less_aux_rec neq_Nil_conv)
apply(auto cong: conj_cong)
done
lemma set_less_eq_aux_code:
assumes "sorted xs" "distinct xs" "sorted ys" "distinct ys"
shows "set xs ⊑' set ys ⟷ ord.lexordp_eq (>) xs ys"
proof -
have dual: "class.linorder (≥) (>)"
by(rule linorder.dual_linorder) unfold_locales
from assms show ?thesis
by(auto simp add: set_less_eq_aux_def finite_complement_partition linorder.lexordp_eq_conv_lexord[OF dual] set_less_aux_code intro: sorted_distinct_set_unique)
qed
end
subsubsection ‹Extending @{term set_less_eq_aux} to have @{term "{}"} as least element›
context ord begin
definition set_less_eq_aux' :: "'a set ⇒ 'a set ⇒ bool" (infix "⊑''''" 50)
where "A ⊑'' B ⟷ A ⊑' B ∨ A = {} ∧ B ∈ infinite_complement_partition"
lemma set_less_eq_aux'_refl:
"A ⊑'' A ⟷ A ∈ infinite_complement_partition"
by(auto simp add: set_less_eq_aux'_def)
lemma set_less_eq_aux'_antisym: "⟦ A ⊑'' B; B ⊑'' A ⟧ ⟹ A = B"
by(auto simp add: set_less_eq_aux'_def intro: set_less_eq_aux_antisym del: equalityI)
lemma set_less_eq_aux'_infinite_complement_partitionD:
"A ⊑'' B ⟹ A ∈ infinite_complement_partition ∧ B ∈ infinite_complement_partition"
by(auto simp add: set_less_eq_aux'_def intro: finite_complement_partition dest: set_less_eq_aux_infinite_complement_partitionD)
lemma empty_set_less_eq_def [simp]: "{} ⊑'' B ⟷ B ∈ infinite_complement_partition"
by(auto simp add: set_less_eq_aux'_def dest: set_less_eq_aux_infinite_complement_partitionD)
end
context linorder begin
lemma set_less_eq_aux'_trans: "⟦ A ⊑'' B; B ⊑'' C ⟧ ⟹ A ⊑'' C"
by(auto simp add: set_less_eq_aux'_def del: equalityI intro: set_less_eq_aux_trans dest: set_less_eq_aux_infinite_complement_partitionD)
lemma set_less_eq_aux'_porder: "partial_order_on infinite_complement_partition {(A, B). A ⊑'' B}"
by(auto simp add: partial_order_on_def preorder_on_def intro!: refl_onI transI antisymI dest: set_less_eq_aux'_antisym set_less_eq_aux'_infinite_complement_partitionD simp add: set_less_eq_aux'_refl intro: set_less_eq_aux'_trans)
end
subsubsection ‹Extend @{term set_less_eq_aux'} to a total order on @{term infinite_complement_partition}›
context ord begin
definition set_less_eq_aux'' :: "'a set ⇒ 'a set ⇒ bool" (infix "⊑''''''" 50)
where "set_less_eq_aux'' =
(SOME sleq.
(linear_order_on UNIV {(a, b). a ≤ b} ⟶ linear_order_on infinite_complement_partition {(A, B). sleq A B}) ∧ order_consistent {(A, B). A ⊑'' B} {(A, B). sleq A B})"
lemma set_less_eq_aux''_spec:
shows "linear_order {(a, b). a ≤ b} ⟹ linear_order_on infinite_complement_partition {(A, B). A ⊑''' B}"
(is "PROP ?thesis1")
and "order_consistent {(A, B). A ⊑'' B} {(A, B). A ⊑''' B}" (is ?thesis2)
proof -
let ?P = "λsleq. (linear_order {(a, b). a ≤ b} ⟶ linear_order_on infinite_complement_partition {(A, B). sleq A B}) ∧
order_consistent {(A, B). A ⊑'' B} {(A, B). sleq A B}"
have "Ex ?P"
proof(cases "linear_order {(a, b). a ≤ b}")
case False
have "antisym {(a, b). a ⊑'' b}"
by (rule antisymI) (simp add: set_less_eq_aux'_antisym)
then show ?thesis using False
by (auto intro: antisym_order_consistent_self)
next
case True
hence "partial_order_on infinite_complement_partition {(A, B). A ⊑'' B}"
by(rule linorder.set_less_eq_aux'_porder[OF linear_order_imp_linorder])
then obtain s where "linear_order_on infinite_complement_partition s"
and "order_consistent {(A, B). A ⊑'' B} s" by(rule porder_extend_to_linorder)
thus ?thesis by(auto intro: exI[where x="λA B. (A, B) ∈ s"])
qed
hence "?P (Eps ?P)" by(rule someI_ex)
thus "PROP ?thesis1" ?thesis2 by(simp_all add: set_less_eq_aux''_def)
qed
end
context linorder begin
lemma set_less_eq_aux''_linear_order:
"linear_order_on infinite_complement_partition {(A, B). A ⊑''' B}"
by(rule set_less_eq_aux''_spec)(rule linear_order)
lemma set_less_eq_aux''_refl [iff]: "A ⊑''' A ⟷ A ∈ infinite_complement_partition"
using set_less_eq_aux''_linear_order
by(auto simp add: linear_order_on_def partial_order_on_def preorder_on_def dest: refl_onD refl_onD1)
lemma set_less_eq_aux'_into_set_less_eq_aux'':
assumes "A ⊑'' B"
shows "A ⊑''' B"
proof(rule ccontr)
assume nleq: "¬ ?thesis"
moreover from assms have A: "A ∈ infinite_complement_partition"
and B: "B ∈ infinite_complement_partition"
by(auto dest: set_less_eq_aux'_infinite_complement_partitionD)
with set_less_eq_aux''_linear_order have "A ⊑''' B ∨ A = B ∨ B ⊑''' A"
by(auto simp add: linear_order_on_def dest: total_onD)
ultimately have "B ⊑''' A" using B by auto
with assms have "A = B" using set_less_eq_aux''_spec(2)
by(simp add: order_consistent_def)
with A nleq show False by simp
qed
lemma finite_set_less_eq_aux''_finite:
assumes "finite A" and "finite B"
shows "A ⊑''' B ⟷ A ⊑'' B"
proof
assume "A ⊑''' B"
from assms have "A ⊑' B ∨ B ⊑' A" by(rule set_less_eq_aux_finite_total2)
hence "A ⊑'' B ∨ B ⊑'' A" by(auto simp add: set_less_eq_aux'_def)
thus "A ⊑'' B"
proof
assume "B ⊑'' A"
hence "B ⊑''' A" by(rule set_less_eq_aux'_into_set_less_eq_aux'')
with ‹A ⊑''' B› set_less_eq_aux''_linear_order have "A = B"
by(auto simp add: linear_order_on_def partial_order_on_def dest: antisymD)
thus ?thesis using assms by(simp add: finite_complement_partition set_less_eq_aux'_def)
qed
qed(rule set_less_eq_aux'_into_set_less_eq_aux'')
lemma set_less_eq_aux''_finite:
"finite (UNIV :: 'a set) ⟹ set_less_eq_aux'' = set_less_eq_aux"
by(auto simp add: fun_eq_iff finite_set_less_eq_aux''_finite set_less_eq_aux'_def finite_subset[OF subset_UNIV])
lemma set_less_eq_aux''_antisym:
"⟦ A ⊑''' B; B ⊑''' A;
A ∈ infinite_complement_partition; B ∈ infinite_complement_partition ⟧
⟹ A = B"
using set_less_eq_aux''_linear_order
by(auto simp add: linear_order_on_def partial_order_on_def dest: antisymD del: equalityI)
lemma set_less_eq_aux''_trans: "⟦ A ⊑''' B; B ⊑''' C ⟧ ⟹ A ⊑''' C"
using set_less_eq_aux''_linear_order
by(auto simp add: linear_order_on_def partial_order_on_def preorder_on_def dest: transD)
lemma set_less_eq_aux''_total:
"⟦ A ∈ infinite_complement_partition; B ∈ infinite_complement_partition ⟧
⟹ A ⊑''' B ∨ B ⊑''' A"
using set_less_eq_aux''_linear_order
by(auto simp add: linear_order_on_def dest: total_onD)
end
subsubsection ‹Extend @{term set_less_eq_aux''} to cofinite sets›
context ord begin
definition set_less_eq :: "'a set ⇒ 'a set ⇒ bool" (infix "⊑" 50)
where
"A ⊑ B ⟷
(if A ∈ infinite_complement_partition then A ⊑''' B ∨ B ∉ infinite_complement_partition
else B ∉ infinite_complement_partition ∧ - B ⊑''' - A)"
definition set_less :: "'a set ⇒ 'a set ⇒ bool" (infix "⊏" 50)
where "A ⊏ B ⟷ A ⊑ B ∧ ¬ B ⊑ A"
lemma set_less_eq_def2:
"A ⊑ B ⟷
(if finite (UNIV :: 'a set) then A ⊑''' B
else if A ∈ infinite_complement_partition then A ⊑''' B ∨ B ∉ infinite_complement_partition
else B ∉ infinite_complement_partition ∧ - B ⊑''' - A)"
by(simp add: set_less_eq_def)
end
context linorder begin
lemma set_less_eq_refl [iff]: "A ⊑ A"
by(auto simp add: set_less_eq_def2 not_in_complement_partition)
lemma set_less_eq_antisym: "⟦ A ⊑ B; B ⊑ A ⟧ ⟹ A = B"
by(auto simp add: set_less_eq_def2 set_less_eq_aux''_finite not_in_complement_partition not_in_complement_partition_False del: equalityI split: if_split_asm dest: set_less_eq_aux_antisym set_less_eq_aux''_antisym)
lemma set_less_eq_trans: "⟦ A ⊑ B; B ⊑ C ⟧ ⟹ A ⊑ C"
by(auto simp add: set_less_eq_def split: if_split_asm intro: set_less_eq_aux''_trans)
lemma set_less_eq_total: "A ⊑ B ∨ B ⊑ A"
by(auto simp add: set_less_eq_def2 set_less_eq_aux''_finite not_in_complement_partition not_in_complement_partition_False intro: set_less_eq_aux_finite_total2 finite_subset[OF subset_UNIV] del: disjCI dest: set_less_eq_aux''_total)
lemma set_less_eq_linorder: "class.linorder (⊑) (⊏)"
by(unfold_locales)(auto simp add: set_less_def set_less_eq_antisym set_less_eq_total intro: set_less_eq_trans)
lemma set_less_eq_conv_set_less: "set_less_eq A B ⟷ A = B ∨ set_less A B"
by(auto simp add: set_less_def del: equalityI dest: set_less_eq_antisym)
lemma Compl_set_less_eq_Compl: "- A ⊑ - B ⟷ B ⊑ A"
by(auto simp add: set_less_eq_def2 not_in_complement_partition_False not_in_complement_partition set_less_eq_aux''_finite Compl_set_less_eq_aux_Compl)
lemma Compl_set_less_Compl: "- A ⊏ - B ⟷ B ⊏ A"
by(simp add: set_less_def Compl_set_less_eq_Compl)
lemma set_less_eq_finite_iff: "⟦ finite A; finite B ⟧ ⟹ A ⊑ B ⟷ A ⊑' B"
by(auto simp add: set_less_eq_def finite_complement_partition set_less_eq_aux'_def finite_set_less_eq_aux''_finite)
lemma set_less_finite_iff: "⟦ finite A; finite B ⟧ ⟹ A ⊏ B ⟷ A ⊏' B"
by(simp add: set_less_def set_less_aux_conv_set_less_eq_aux set_less_eq_finite_iff)
lemma infinite_set_less_eq_Complement:
"⟦ finite A; finite B; ¬ finite (UNIV :: 'a set) ⟧ ⟹ A ⊑ - B"
by(simp add: set_less_eq_def finite_complement_partition not_in_complement_partition)
lemma infinite_set_less_Complement:
"⟦ finite A; finite B; ¬ finite (UNIV :: 'a set) ⟧ ⟹ A ⊏ - B"
by(auto simp add: set_less_def dest: set_less_eq_antisym intro: infinite_set_less_eq_Complement)
lemma infinite_Complement_set_less_eq:
"⟦ finite A; finite B; ¬ finite (UNIV :: 'a set) ⟧ ⟹ ¬ - A ⊑ B"
using infinite_set_less_eq_Complement[of A B] Compl_set_less_eq_Compl[of A "- B"]
by(auto dest: set_less_eq_antisym)
lemma infinite_Complement_set_less:
"⟦ finite A; finite B; ¬ finite (UNIV :: 'a set) ⟧ ⟹ ¬ - A ⊏ B"
using infinite_Complement_set_less_eq[of A B]
by(simp add: set_less_def)
lemma empty_set_less_eq [iff]: "{} ⊑ A"
by(auto simp add: set_less_eq_def finite_complement_partition intro: set_less_eq_aux'_into_set_less_eq_aux'')
lemma set_less_eq_empty [iff]: "A ⊑ {} ⟷ A = {}"
by (metis empty_set_less_eq set_less_eq_antisym)
lemma empty_set_less_iff [iff]: "{} ⊏ A ⟷ A ≠ {}"
by(simp add: set_less_def)
lemma not_set_less_empty [simp]: "¬ A ⊏ {}"
by(simp add: set_less_def)
lemma set_less_eq_UNIV [iff]: "A ⊑ UNIV"
using Compl_set_less_eq_Compl[of "- A" "{}"] by simp
lemma UNIV_set_less_eq [iff]: "UNIV ⊑ A ⟷ A = UNIV"
using Compl_set_less_eq_Compl[of "{}" "- A"]
by(simp add: Compl_eq_empty_iff)
lemma set_less_UNIV_iff [iff]: "A ⊏ UNIV ⟷ A ≠ UNIV"
by(simp add: set_less_def)
lemma not_UNIV_set_less [simp]: "¬ UNIV ⊏ A"
by(simp add: set_less_def)
end
subsection ‹Implementation based on sorted lists›
type_synonym 'a proper_interval = "'a option ⇒ 'a option ⇒ bool"
class proper_intrvl = ord +
fixes proper_interval :: "'a proper_interval"
class proper_interval = proper_intrvl +
assumes proper_interval_simps:
"proper_interval None None = True"
"proper_interval None (Some y) = (∃z. z < y)"
"proper_interval (Some x) None = (∃z. x < z)"
"proper_interval (Some x) (Some y) = (∃z. x < z ∧ z < y)"
context proper_intrvl begin
function set_less_eq_aux_Compl :: "'a option ⇒ 'a list ⇒ 'a list ⇒ bool"
where
"set_less_eq_aux_Compl ao [] ys ⟷ True"
| "set_less_eq_aux_Compl ao xs [] ⟷ True"
| "set_less_eq_aux_Compl ao (x # xs) (y # ys) ⟷
(if x < y then proper_interval ao (Some x) ∨ set_less_eq_aux_Compl (Some x) xs (y # ys)
else if y < x then proper_interval ao (Some y) ∨ set_less_eq_aux_Compl (Some y) (x # xs) ys
else proper_interval ao (Some y))"
by(pat_completeness) simp_all
termination by(lexicographic_order)
fun Compl_set_less_eq_aux :: "'a option ⇒ 'a list ⇒ 'a list ⇒ bool"
where
"Compl_set_less_eq_aux ao [] [] ⟷ ¬ proper_interval ao None"
| "Compl_set_less_eq_aux ao [] (y # ys) ⟷ ¬ proper_interval ao (Some y) ∧ Compl_set_less_eq_aux (Some y) [] ys"
| "Compl_set_less_eq_aux ao (x # xs) [] ⟷ ¬ proper_interval ao (Some x) ∧ Compl_set_less_eq_aux (Some x) xs []"
| "Compl_set_less_eq_aux ao (x # xs) (y # ys) ⟷
(if x < y then ¬ proper_interval ao (Some x) ∧ Compl_set_less_eq_aux (Some x) xs (y # ys)
else if y < x then ¬ proper_interval ao (Some y) ∧ Compl_set_less_eq_aux (Some y) (x # xs) ys
else ¬ proper_interval ao (Some y))"
fun set_less_aux_Compl :: "'a option ⇒ 'a list ⇒ 'a list ⇒ bool" where
"set_less_aux_Compl ao [] [] ⟷ proper_interval ao None"
| "set_less_aux_Compl ao [] (y # ys) ⟷ proper_interval ao (Some y) ∨ set_less_aux_Compl (Some y) [] ys"
| "set_less_aux_Compl ao (x # xs) [] ⟷ proper_interval ao (Some x) ∨ set_less_aux_Compl (Some x) xs []"
| "set_less_aux_Compl ao (x # xs) (y # ys) ⟷
(if x < y then proper_interval ao (Some x) ∨ set_less_aux_Compl (Some x) xs (y # ys)
else if y < x then proper_interval ao (Some y) ∨ set_less_aux_Compl (Some y) (x # xs) ys
else proper_interval ao (Some y))"
function Compl_set_less_aux :: "'a option ⇒ 'a list ⇒ 'a list ⇒ bool" where
"Compl_set_less_aux ao [] ys ⟷ False"
| "Compl_set_less_aux ao xs [] ⟷ False"
| "Compl_set_less_aux ao (x # xs) (y # ys) ⟷
(if x < y then ¬ proper_interval ao (Some x) ∧ Compl_set_less_aux (Some x) xs (y # ys)
else if y < x then ¬ proper_interval ao (Some y) ∧ Compl_set_less_aux (Some y) (x # xs) ys
else ¬ proper_interval ao (Some y))"
by pat_completeness simp_all
termination by lexicographic_order
end
lemmas [code] =
proper_intrvl.set_less_eq_aux_Compl.simps
proper_intrvl.set_less_aux_Compl.simps
proper_intrvl.Compl_set_less_eq_aux.simps
proper_intrvl.Compl_set_less_aux.simps
class linorder_proper_interval = linorder + proper_interval
begin
theorem assumes fin: "finite (UNIV :: 'a set)"
and xs: "sorted xs" "distinct xs"
and ys: "sorted ys" "distinct ys"
shows set_less_eq_aux_Compl2_conv_set_less_eq_aux_Compl:
"set xs ⊑' - set ys ⟷ set_less_eq_aux_Compl None xs ys" (is ?Compl2)
and Compl1_set_less_eq_aux_conv_Compl_set_less_eq_aux:
"- set xs ⊑' set ys ⟷ Compl_set_less_eq_aux None xs ys" (is ?Compl1)
proof -
note fin' [simp] = finite_subset[OF subset_UNIV fin]
define above where "above = case_option UNIV (Collect ∘ less)"
have above_simps [simp]: "above None = UNIV" "⋀x. above (Some x) = {y. x < y}"
and above_upclosed: "⋀x y ao. ⟦ x ∈ above ao; x < y ⟧ ⟹ y ∈ above ao"
and proper_interval_Some2: "⋀x ao. proper_interval ao (Some x) ⟷ (∃z∈above ao. z < x)"
and proper_interval_None2: "⋀ao. proper_interval ao None ⟷ above ao ≠ {}"
by(simp_all add: proper_interval_simps above_def split: option.splits)
{ fix ao x A B
assume ex: "proper_interval ao (Some x)"
and A: "∀a ∈ A. x ≤ a"
and B: "∀b ∈ B. x ≤ b"
from ex obtain z where z_ao: "z ∈ above ao" and z: "z < x"
by(auto simp add: proper_interval_Some2)
with A have A_eq: "A ∩ above ao = A"
by(auto simp add: above_upclosed)
from z_ao z B have B_eq: "B ∩ above ao = B"
by(auto simp add: above_upclosed)
define w where "w = Min (above ao)"
with z_ao have "w ≤ z" "∀z ∈ above ao. w ≤ z" "w ∈ above ao"
by(auto simp add: Min_le_iff intro: Min_in)
hence "A ∩ above ao ⊏' (- B) ∩ above ao" (is "?lhs ⊏' ?rhs")
using A B z by(auto simp add: set_less_aux_def intro!: bexI[where x="w"])
hence "A ⊑' ?rhs" unfolding A_eq by(simp add: set_less_eq_aux_def)
moreover
from z_ao z A B have "z ∈ - A ∩ above ao" "z ∉ B" by auto
hence neq: "- A ∩ above ao ≠ B ∩ above ao" by auto
have "¬ - A ∩ above ao ⊏' B ∩ above ao" (is "¬ ?lhs' ⊏' ?rhs'")
using A B z z_ao by(force simp add: set_less_aux_def not_less dest: bspec[where x=z])
with neq have "¬ ?lhs' ⊑' B" unfolding B_eq by(auto simp add: set_less_eq_aux_def)
moreover note calculation }
note proper_interval_set_less_eqI = this(1)
and proper_interval_not_set_less_eq_auxI = this(2)
{ fix ao
assume "set xs ∪ set ys ⊆ above ao"
with xs ys
have "set_less_eq_aux_Compl ao xs ys ⟷ set xs ⊑' (- set ys) ∩ above ao"
proof(induction ao xs ys rule: set_less_eq_aux_Compl.induct)
case 1 thus ?case by simp
next
case 2 thus ?case by(auto intro: subset_finite_imp_set_less_eq_aux)
next
case (3 ao x xs y ys)
note ao = ‹set (x # xs) ∪ set (y # ys) ⊆ above ao›
hence x_ao: "x ∈ above ao" and y_ao: "y ∈ above ao" by simp_all
note yys = ‹sorted (y # ys)› ‹distinct (y # ys)›
hence ys: "sorted ys" "distinct ys" and y_Min: "∀y' ∈ set ys. y < y'"
by(auto simp add: less_le)
note xxs = ‹sorted (x # xs)› ‹distinct (x # xs)›
hence xs: "sorted xs" "distinct xs" and x_Min: "∀x' ∈ set xs. x < x'"
by(auto simp add: less_le)
let ?lhs = "set (x # xs)" and ?rhs = "- set (y # ys) ∩ above ao"
show ?case
proof(cases "x < y")
case True
show ?thesis
proof(cases "proper_interval ao (Some x)")
case True
hence "?lhs ⊑' ?rhs" using x_Min y_Min ‹x < y›
by(auto intro!: proper_interval_set_less_eqI)
with True show ?thesis using ‹x < y› by simp
next
case False
have "set xs ∪ set (y # ys) ⊆ above (Some x)" using True x_Min y_Min by auto
with True xs yys
have IH: "set_less_eq_aux_Compl (Some x) xs (y # ys) =
(set xs ⊑' - set (y # ys) ∩ above (Some x))"
by(rule "3.IH")
from True y_Min x_ao have "x ∈ - set (y # ys) ∩ above ao" by auto
hence "?rhs ≠ {}" by blast
moreover have "Min ?lhs = x" using x_Min x_ao by(auto intro!: Min_eqI)
moreover have "Min ?rhs = x" using ‹x < y› y_Min x_ao False
by(auto intro!: Min_eqI simp add: proper_interval_Some2)
moreover have "set xs = set xs - {x}"
using ao x_Min by auto
moreover have "- set (y # ys) ∩ above (Some x) = - set (y # ys) ∩ above ao - {x}"
using False x_ao by(auto simp add: proper_interval_Some2 intro: above_upclosed)
ultimately show ?thesis using True False IH
by(simp del: set_simps)(subst (2) set_less_eq_aux_rec, simp_all add: x_ao)
qed
next
case False
show ?thesis
proof(cases "y < x")
case True
show ?thesis
proof(cases "proper_interval ao (Some y)")
case True
hence "?lhs ⊑' ?rhs" using x_Min y_Min ‹¬ x < y›
by(auto intro!: proper_interval_set_less_eqI)
with True show ?thesis using ‹¬ x < y› by simp
next
case False
have "set (x # xs) ∪ set ys ⊆ above (Some y)"
using ‹y < x› x_Min y_Min by auto
with ‹¬ x < y› ‹y < x› xxs ys
have IH: "set_less_eq_aux_Compl (Some y) (x # xs) ys =
(set (x # xs) ⊑' - set ys ∩ above (Some y))"
by(rule "3.IH")
moreover have "- set ys ∩ above (Some y) = ?rhs"
using y_ao False by(auto intro: above_upclosed simp add: proper_interval_Some2)
ultimately show ?thesis using ‹¬ x < y› True False by simp
qed
next
case False with ‹¬ x < y› have "x = y" by auto
{ assume "proper_interval ao (Some y)"
hence "?lhs ⊑' ?rhs" using x_Min y_Min ‹x = y›
by(auto intro!: proper_interval_set_less_eqI) }
moreover
{ assume "?lhs ⊑' ?rhs"
moreover have "?lhs ≠ ?rhs"
proof
assume eq: "?lhs = ?rhs"
have "x ∈ ?lhs" using x_ao by simp
also note eq also note ‹x = y›
finally show False by simp
qed
ultimately obtain z where "z ∈ above ao" "z < y" using ‹x = y› y_ao
by(fastforce simp add: set_less_eq_aux_def set_less_aux_def not_le dest!: bspec[where x=y])
hence "proper_interval ao (Some y)" by(auto simp add: proper_interval_Some2) }
ultimately show ?thesis using ‹x = y› ‹¬ x < y› ‹¬ y < x› by auto
qed
qed
qed }
from this[of None] show ?Compl2 by simp
{ fix ao
assume "set xs ∪ set ys ⊆ above ao"
with xs ys
have "Compl_set_less_eq_aux ao xs ys ⟷ (- set xs) ∩ above ao ⊑' set ys"
proof(induction ao xs ys rule: Compl_set_less_eq_aux.induct)
case 1 thus ?case by(simp add: proper_interval_None2)
next
case (2 ao y ys)
from ‹sorted (y # ys)› ‹distinct (y # ys)›
have ys: "sorted ys" "distinct ys" and y_Min: "∀y' ∈ set ys. y < y'"
by(auto simp add: less_le)
show ?case
proof(cases "proper_interval ao (Some y)")
case True
hence "¬ - set [] ∩ above ao ⊑' set (y # ys)" using y_Min
by -(erule proper_interval_not_set_less_eq_auxI, auto)
thus ?thesis using True by simp
next
case False
note ao = ‹set [] ∪ set (y # ys) ⊆ above ao›
hence y_ao: "y ∈ above ao" by simp
from ao y_Min have "set [] ∪ set ys ⊆ above (Some y)" by auto
with ‹sorted []› ‹distinct []› ys
have "Compl_set_less_eq_aux (Some y) [] ys ⟷ - set [] ∩ above (Some y) ⊑' set ys"
by(rule "2.IH")
moreover have "above ao ≠ {}" using y_ao by auto
moreover have "Min (above ao) = y"
and "Min (set (y # ys)) = y"
using y_ao False ao by(auto intro!: Min_eqI simp add: proper_interval_Some2 not_less)
moreover have "above ao - {y} = above (Some y)" using False y_ao
by(auto simp add: proper_interval_Some2 intro: above_upclosed)
moreover have "set ys - {y} = set ys"
using y_Min y_ao by(auto)
ultimately show ?thesis using False y_ao
by(simp)(subst (2) set_less_eq_aux_rec, simp_all)
qed
next
case (3 ao x xs)
from ‹sorted (x # xs)› ‹distinct (x # xs)›
have xs: "sorted xs" "distinct xs" and x_Min: "∀x'∈set xs. x < x'"
by(auto simp add: less_le)
show ?case
proof(cases "proper_interval ao (Some x)")
case True
then obtain z where "z ∈ above ao" "z < x" by(auto simp add: proper_interval_Some2)
hence "z ∈ - set (x # xs) ∩ above ao" using x_Min by auto
thus ?thesis using True by auto
next
case False
note ao = ‹set (x # xs) ∪ set [] ⊆ above ao›
hence x_ao: "x ∈ above ao" by simp
from ao have "set xs ∪ set [] ⊆ above (Some x)" using x_Min by auto
with xs ‹sorted []› ‹distinct []›
have "Compl_set_less_eq_aux (Some x) xs [] ⟷
- set xs ∩ above (Some x) ⊑' set []"
by(rule "3.IH")
moreover have "- set (x # xs) ∩ above ao = - set xs ∩ above (Some x)"
using False x_ao by(auto simp add: proper_interval_Some2 intro: above_upclosed)
ultimately show ?thesis using False by simp
qed
next
case (4 ao x xs y ys)
note ao = ‹set (x # xs) ∪ set (y # ys) ⊆ above ao›
hence x_ao: "x ∈ above ao" and y_ao: "y ∈ above ao" by simp_all
note xxs = ‹sorted (x # xs)› ‹distinct (x # xs)›
hence xs: "sorted xs" "distinct xs" and x_Min: "∀x'∈set xs. x < x'"
by(auto simp add: less_le)
note yys = ‹sorted (y # ys)› ‹distinct (y # ys)›
hence ys: "sorted ys" "distinct ys" and y_Min: "∀y'∈set ys. y < y'"
by(auto simp add: less_le)
let ?lhs = "- set (x # xs) ∩ above ao" and ?rhs = "set (y # ys)"
show ?case
proof(cases "x < y")
case True
show ?thesis
proof(cases "proper_interval ao (Some x)")
case True
hence "¬ ?lhs ⊑' ?rhs" using x_Min y_Min ‹x < y›
by -(erule proper_interval_not_set_less_eq_auxI, auto)
thus ?thesis using True ‹x < y› by simp
next
case False
have "set xs ∪ set (y # ys) ⊆ above (Some x)"
using ao x_Min y_Min True by auto
with True xs yys
have "Compl_set_less_eq_aux (Some x) xs (y # ys) ⟷
- set xs ∩ above (Some x) ⊑' set (y # ys)"
by(rule "4.IH")
moreover have "- set xs ∩ above (Some x) = ?lhs"
using x_ao False by(auto intro: above_upclosed simp add: proper_interval_Some2)
ultimately show ?thesis using False True by simp
qed
next
case False
show ?thesis
proof(cases "y < x")
case True
show ?thesis
proof(cases "proper_interval ao (Some y)")
case True
hence "¬ ?lhs ⊑' ?rhs" using x_Min y_Min ‹y < x›
by -(erule proper_interval_not_set_less_eq_auxI, auto)
thus ?thesis using True ‹y < x› ‹¬ x < y› by simp
next
case False
from ao True x_Min y_Min
have "set (x # xs) ∪ set ys ⊆ above (Some y)" by auto
with ‹¬ x < y› True xxs ys
have "Compl_set_less_eq_aux (Some y) (x # xs) ys ⟷
- set (x # xs) ∩ above (Some y) ⊑' set ys"
by(rule "4.IH")
moreover have "y ∈ ?lhs" using True x_Min y_ao by auto
hence "?lhs ≠ {}" by auto
moreover have "Min ?lhs = y" using True False x_Min y_ao
by(auto intro!: Min_eqI simp add: not_le not_less proper_interval_Some2)
moreover have "Min ?rhs = y" using y_Min y_ao by(auto intro!: Min_eqI)
moreover have "- set (x # xs) ∩ above (Some y) = ?lhs - {y}"
using y_ao False by(auto intro: above_upclosed simp add: proper_interval_Some2)
moreover have "set ys = set ys - {y}"
using y_ao y_Min by(auto intro: above_upclosed)
ultimately show ?thesis using True False ‹¬ x < y› y_ao
by(simp)(subst (2) set_less_eq_aux_rec, simp_all)
qed
next
case False
with ‹¬ x < y› have "x = y" by auto
{ assume "proper_interval ao (Some y)"
hence "¬ ?lhs ⊑' ?rhs" using x_Min y_Min ‹x = y›
by -(erule proper_interval_not_set_less_eq_auxI, auto) }
moreover
{ assume "¬ ?lhs ⊑' ?rhs"
also have "?rhs = set (y # ys) ∩ above ao"
using ao by auto
finally obtain z where "z ∈ above ao" "z < y"
using ‹x = y› x_ao x_Min[unfolded Ball_def]
by(fastforce simp add: set_less_eq_aux_def set_less_aux_def simp add: less_le not_le dest!: bspec[where x=y])
hence "proper_interval ao (Some y)"
by(auto simp add: proper_interval_Some2) }
ultimately show ?thesis using ‹x = y› by auto
qed
qed
qed }
from this[of None] show ?Compl1 by simp
qed
lemma set_less_aux_Compl_iff:
"set_less_aux_Compl ao xs ys ⟷ set_less_eq_aux_Compl ao xs ys ∧ ¬ Compl_set_less_eq_aux ao ys xs"
by(induct ao xs ys rule: set_less_aux_Compl.induct)(auto simp add: not_less_iff_gr_or_eq)
lemma Compl_set_less_aux_Compl_iff:
"Compl_set_less_aux ao xs ys ⟷ Compl_set_less_eq_aux ao xs ys ∧ ¬ set_less_eq_aux_Compl ao ys xs"
by(induct ao xs ys rule: Compl_set_less_aux.induct)(auto simp add: not_less_iff_gr_or_eq)
theorem assumes fin: "finite (UNIV :: 'a set)"
and xs: "sorted xs" "distinct xs"
and ys: "sorted ys" "distinct ys"
shows set_less_aux_Compl2_conv_set_less_aux_Compl:
"set xs ⊏' - set ys ⟷ set_less_aux_Compl None xs ys" (is ?Compl2)
and Compl1_set_less_aux_conv_Compl_set_less_aux:
"- set xs ⊏' set ys ⟷ Compl_set_less_aux None xs ys" (is ?Compl1)
using assms
by(simp_all only: set_less_aux_conv_set_less_eq_aux set_less_aux_Compl_iff Compl_set_less_aux_Compl_iff set_less_eq_aux_Compl2_conv_set_less_eq_aux_Compl Compl1_set_less_eq_aux_conv_Compl_set_less_eq_aux)
end
subsection ‹Implementation of proper intervals for sets›
definition length_last :: "'a list ⇒ nat × 'a"
where "length_last xs = (length xs, last xs)"
lemma length_last_Nil [code]: "length_last [] = (0, undefined)"
by(simp add: length_last_def last_def)
lemma length_last_Cons_code [symmetric, code]:
"fold (λx (n, _) . (n + 1, x)) xs (1, x) = length_last (x # xs)"
by(induct xs rule: rev_induct)(simp_all add: length_last_def)
context proper_intrvl begin
fun exhaustive_above :: "'a ⇒ 'a list ⇒ bool" where
"exhaustive_above x [] ⟷ ¬ proper_interval (Some x) None"
| "exhaustive_above x (y # ys) ⟷ ¬ proper_interval (Some x) (Some y) ∧ exhaustive_above y ys"
fun exhaustive :: "'a list ⇒ bool" where
"exhaustive [] = False"
| "exhaustive (x # xs) ⟷ ¬ proper_interval None (Some x) ∧ exhaustive_above x xs"
fun proper_interval_set_aux :: "'a list ⇒ 'a list ⇒ bool"
where
"proper_interval_set_aux xs [] ⟷ False"
| "proper_interval_set_aux [] (y # ys) ⟷ ys ≠ [] ∨ proper_interval (Some y) None"
| "proper_interval_set_aux (x # xs) (y # ys) ⟷
(if x < y then False
else if y < x then proper_interval (Some y) (Some x) ∨ ys ≠ [] ∨ ¬ exhaustive_above x xs
else proper_interval_set_aux xs ys)"
fun proper_interval_set_Compl_aux :: "'a option ⇒ nat ⇒ 'a list ⇒ 'a list ⇒ bool"
where
"proper_interval_set_Compl_aux ao n [] [] ⟷
CARD('a) > n + 1"
| "proper_interval_set_Compl_aux ao n [] (y # ys) ⟷
(let m = CARD('a) - n; (len_y, y') = length_last (y # ys)
in m ≠ len_y ∧ (m = len_y + 1 ⟶ ¬ proper_interval (Some y') None))"
| "proper_interval_set_Compl_aux ao n (x # xs) [] ⟷
(let m = CARD('a) - n; (len_x, x') = length_last (x # xs)
in m ≠ len_x ∧ (m = len_x + 1 ⟶ ¬ proper_interval (Some x') None))"
| "proper_interval_set_Compl_aux ao n (x # xs) (y # ys) ⟷
(if x < y then
proper_interval ao (Some x) ∨
proper_interval_set_Compl_aux (Some x) (n + 1) xs (y # ys)
else if y < x then
proper_interval ao (Some y) ∨
proper_interval_set_Compl_aux (Some y) (n + 1) (x # xs) ys
else proper_interval ao (Some x) ∧
(let m = card (UNIV :: 'a set) - n in m - length ys ≠ 2 ∨ m - length xs ≠ 2))"
fun proper_interval_Compl_set_aux :: "'a option ⇒ 'a list ⇒ 'a list ⇒ bool"
where
"proper_interval_Compl_set_aux ao (x # xs) (y # ys) ⟷
(if x < y then
¬ proper_interval ao (Some x) ∧
proper_interval_Compl_set_aux (Some x) xs (y # ys)
else if y < x then
¬ proper_interval ao (Some y) ∧
proper_interval_Compl_set_aux (Some y) (x # xs) ys
else ¬ proper_interval ao (Some x) ∧ (ys = [] ⟶ xs ≠ []))"
| "proper_interval_Compl_set_aux ao _ _ ⟷ False"
end
lemmas [code] =
proper_intrvl.exhaustive_above.simps
proper_intrvl.exhaustive.simps
proper_intrvl.proper_interval_set_aux.simps
proper_intrvl.proper_interval_set_Compl_aux.simps
proper_intrvl.proper_interval_Compl_set_aux.simps
context linorder_proper_interval begin
lemma exhaustive_above_iff:
"⟦ sorted xs; distinct xs; ∀x'∈set xs. x < x' ⟧ ⟹ exhaustive_above x xs ⟷ set xs = {z. z > x}"
proof(induction x xs rule: exhaustive_above.induct)
case 1 thus ?case by(simp add: proper_interval_simps)
next
case (2 x y ys)
from ‹sorted (y # ys)› ‹distinct (y # ys)›
have ys: "sorted ys" "distinct ys" and y: "∀y'∈set ys. y < y'"
by(auto simp add: less_le)
hence "exhaustive_above y ys = (set ys = {z. y < z})" by(rule "2.IH")
moreover from ‹∀y'∈set (y # ys). x < y'› have "x < y" by simp
ultimately show ?case using y
by(fastforce simp add: proper_interval_simps)
qed
lemma exhaustive_correct:
assumes "sorted xs" "distinct xs"
shows "exhaustive xs ⟷ set xs = UNIV"
proof(cases xs)
case Nil thus ?thesis by auto
next
case Cons
show ?thesis using assms unfolding Cons exhaustive.simps
apply(subst exhaustive_above_iff)
apply(auto simp add: less_le proper_interval_simps not_less intro: order_antisym)
done
qed
theorem proper_interval_set_aux:
assumes fin: "finite (UNIV :: 'a set)"
and xs: "sorted xs" "distinct xs"
and ys: "sorted ys" "distinct ys"
shows "proper_interval_set_aux xs ys ⟷ (∃A. set xs ⊏' A ∧ A ⊏' set ys)"
proof -
note [simp] = finite_subset[OF subset_UNIV fin]
show ?thesis using xs ys
proof(induction xs ys rule: proper_interval_set_aux.induct)
case 1 thus ?case by simp
next
case (2 y ys)
hence "∀y'∈set ys. y < y'" by(auto simp add: less_le)
thus ?case
by(cases ys)(auto simp add: proper_interval_simps set_less_aux_singleton_iff intro: psubset_finite_imp_set_less_aux)
next
case (3 x xs y ys)
from ‹sorted (x # xs)› ‹distinct (x # xs)›
have xs: "sorted xs" "distinct xs" and x: "∀x'∈set xs. x < x'"
by(auto simp add: less_le)
from ‹sorted (y # ys)› ‹distinct (y # ys)›
have ys: "sorted ys" "distinct ys" and y: "∀y'∈set ys. y < y'"
by(auto simp add: less_le)
have Minxxs: "Min (set (x # xs)) = x" and xnxs: "x ∉ set xs"
using x by(auto intro!: Min_eqI)
have Minyys: "Min (set (y # ys)) = y" and ynys: "y ∉ set ys"
using y by(auto intro!: Min_eqI)
show ?case
proof(cases "x < y")
case True
hence "set (y # ys) ⊏' set (x # xs)" using Minxxs Minyys
by -(rule set_less_aux_Min_antimono, simp_all)
thus ?thesis using True by(auto dest: set_less_aux_trans set_less_aux_antisym)
next
case False
show ?thesis
proof(cases "y < x")
case True
{ assume "proper_interval (Some y) (Some x)"
then obtain z where z: "y < z" "z < x" by(auto simp add: proper_interval_simps)
hence "set (x # xs) ⊏' {z}" using x
by -(rule set_less_aux_Min_antimono, auto)
moreover have "{z} ⊏' set (y # ys)" using z y Minyys
by -(rule set_less_aux_Min_antimono, auto)
ultimately have "∃A. set (x # xs) ⊏' A ∧ A ⊏' set (y # ys)" by blast }
moreover
{ assume "ys ≠ []"
hence "{y} ⊏' set (y # ys)" using y
by -(rule psubset_finite_imp_set_less_aux, auto simp add: neq_Nil_conv)
moreover have "set (x # xs) ⊏' {y}" using False True x
by -(rule set_less_aux_Min_antimono, auto)
ultimately have "∃A. set (x # xs) ⊏' A ∧ A ⊏' set (y # ys)" by blast }
moreover
{ assume "¬ exhaustive_above x xs"
then obtain z where z: "z > x" "z ∉ set xs" using x
by(auto simp add: exhaustive_above_iff[OF xs x])
let ?A = "insert z (set (x # xs))"
have "set (x # xs) ⊏' ?A" using z
by -(rule psubset_finite_imp_set_less_aux, auto)
moreover have "?A ⊏' set (y # ys)" using Minyys False True z x
by -(rule set_less_aux_Min_antimono, auto)
ultimately have "∃A. set (x # xs) ⊏' A ∧ A ⊏' set (y # ys)" by blast }
moreover
{ fix A
assume A: "set (x # xs) ⊏' A" and A': "A ⊏' {y}"
and pi: "¬ proper_interval (Some y) (Some x)"
from A have nempty: "A ≠ {}" by auto
have "y ∉ A"
proof
assume "y ∈ A"
moreover with A' have "A ≠ {y}" by auto
ultimately have "{y} ⊏' A" by -(rule psubset_finite_imp_set_less_aux, auto)
with A' show False by(rule set_less_aux_antisym)
qed
have "y < Min A" unfolding not_le[symmetric]
proof
assume "Min A ≤ y"
moreover have "Min A ≠ y" using ‹y ∉ A› nempty by clarsimp
ultimately have "Min A < Min {y}" by simp
hence "{y} ⊏' A" by(rule set_less_aux_Min_antimono)(simp_all add: nempty)
with A' show False by(rule set_less_aux_antisym)
qed
with pi nempty have "x ≤ Min A" by(auto simp add: proper_interval_simps)
moreover
from A obtain z where z: "z ∈ A" "z ∉ set (x # xs)"
by(auto simp add: set_less_aux_def)
with ‹x ≤ Min A› nempty have "x < z" by auto
with z have "¬ exhaustive_above x xs"
by(auto simp add: exhaustive_above_iff[OF xs x]) }
ultimately show ?thesis using True False by fastforce
next
case False
with ‹¬ x < y› have "x = y" by auto
from ‹¬ x < y› False
have "proper_interval_set_aux xs ys = (∃A. set xs ⊏' A ∧ A ⊏' set ys)"
using xs ys by(rule "3.IH")
also have "… = (∃A. set (x # xs) ⊏' A ∧ A ⊏' set (y # ys))"
(is "?lhs = ?rhs")
proof
assume ?lhs
then obtain A where A: "set xs ⊏' A"
and A': "A ⊏' set ys" by blast
hence nempty: "A ≠ {}" "ys ≠ []" by auto
let ?A = "insert y A"
{ assume "Min A ≤ y"
also from y nempty have "y < Min (set ys)" by auto
finally have "set ys ⊏' A" by(rule set_less_aux_Min_antimono)(simp_all add: nempty)
with A' have False by(rule set_less_aux_antisym) }
hence MinA: "y < Min A" by(metis not_le)
with nempty have "y ∉ A" by auto
moreover
with MinA nempty have MinyA: "Min ?A = y" by -(rule Min_eqI, auto)
ultimately have A1: "set (x # xs) ⊏' ?A" using ‹x = y› A Minxxs xnxs
by(subst set_less_aux_rec) simp_all
moreover
have "?A ⊏' set (y # ys)" using ‹x = y› MinyA ‹y ∉ A› A' Minyys ynys
by(subst set_less_aux_rec) simp_all
ultimately show ?rhs by blast
next
assume "?rhs"
then obtain A where A: "set (x # xs) ⊏' A"
and A': "A ⊏' set (y # ys)" by blast
let ?A = "A - {x}"
from A have nempty: "A ≠ {}" by auto
{ assume "x < Min A"
hence "Min (set (x # xs)) < Min A" unfolding Minxxs .
hence "A ⊏' set (x # xs)"
by(rule set_less_aux_Min_antimono) simp_all
with A have False by(rule set_less_aux_antisym) }
moreover
{ assume "Min A < x"
hence "Min A < Min (set (y # ys))" unfolding ‹x = y› Minyys .
hence "set (y # ys) ⊏' A" by(rule set_less_aux_Min_antimono)(simp_all add: nempty)
with A' have False by(rule set_less_aux_antisym) }
ultimately have MinA: "Min A = x" by(metis less_linear)
hence "x ∈ A" using nempty by(metis Min_in ‹finite A›)
from A nempty Minxxs xnxs have "set xs ⊏' ?A"
by(subst (asm) set_less_aux_rec)(auto simp add: MinA)
moreover from A' ‹x = y› nempty Minyys MinA ynys have "?A ⊏' set ys"
by(subst (asm) set_less_aux_rec) simp_all
ultimately show ?lhs by blast
qed
finally show ?thesis using ‹x = y› by simp
qed
qed
qed
qed
lemma proper_interval_set_Compl_aux:
assumes fin: "finite (UNIV :: 'a set)"
and xs: "sorted xs" "distinct xs"
and ys: "sorted ys" "distinct ys"
shows "proper_interval_set_Compl_aux None 0 xs ys ⟷ (∃A. set xs ⊏' A ∧ A ⊏' - set ys)"
proof -
note [simp] = finite_subset[OF subset_UNIV fin]
define above where "above = case_option UNIV (Collect ∘ less)"
have above_simps [simp]: "above None = UNIV" "⋀x. above (Some x) = {y. x < y}"
and above_upclosed: "⋀x y ao. ⟦ x ∈ above ao; x < y ⟧ ⟹ y ∈ above ao"
and proper_interval_Some2: "⋀x ao. proper_interval ao (Some x) ⟷ (∃z∈above ao. z < x)"
by(simp_all add: proper_interval_simps above_def split: option.splits)
{ fix ao n
assume "set xs ⊆ above ao" "set ys ⊆ above ao"
from xs ‹set xs ⊆ above ao› ys ‹set ys ⊆ above ao›
have "proper_interval_set_Compl_aux ao (card (UNIV - above ao)) xs ys ⟷
(∃A ⊆ above ao. set xs ⊏' A ∧ A ⊏' - set ys ∩ above ao)"
proof(induct ao n≡"card (UNIV - above ao)" xs ys rule: proper_interval_set_Compl_aux.induct)
case (1 ao)
have "card (UNIV - above ao) + 1 < CARD('a) ⟷ (∃A ⊆ above ao. A ≠ {} ∧ A ⊏' above ao)"
(is "?lhs ⟷ ?rhs")
proof
assume ?lhs
hence "card (UNIV - (UNIV - above ao)) > 1" by(simp add: card_Diff_subset)
from card_gt_1D[OF this]
obtain x y where above: "x ∈ above ao" "y ∈ above ao"
and neq: "x ≠ y" by blast
hence "{x} ⊏' {x, y} ∩ above ao"
by(simp_all add: psubsetI psubset_finite_imp_set_less_aux)
also have "… ⊑' above ao"
by(auto intro: subset_finite_imp_set_less_eq_aux)
finally show ?rhs using above by blast
next
assume ?rhs
then obtain A where nempty: "A ∩ above ao ≠ {}"
and subset: "A ⊆ above ao"
and less: "A ⊏' above ao" by blast
from nempty obtain x where x: "x ∈ A" "x ∈ above ao" by blast
show ?lhs
proof(rule ccontr)
assume "¬ ?lhs"
moreover have "CARD('a) ≥ card (UNIV - above ao)" by(rule card_mono) simp_all
moreover from card_Un_disjoint[of "UNIV - above ao" "above ao"]
have "CARD('a) = card (UNIV - above ao) + card (above ao)" by auto
ultimately have "card (above ao) = 1" using x
by(cases "card (above ao)")(auto simp add: not_less_eq less_Suc_eq_le)
with x have "above ao = {x}" unfolding card_eq_1_iff by auto
moreover with x subset have A: "A = {x}" by auto
ultimately show False using less by simp
qed
qed
thus ?case by simp
next
case (2 ao y ys)
note ys = ‹sorted (y # ys)› ‹distinct (y # ys)› ‹set (y # ys) ⊆ above ao›
have len_ys: "length ys = card (set ys)"
using ys by(auto simp add: List.card_set intro: sym)
define m where "m = CARD('a) - card (UNIV - above ao)"
have "CARD('a) = card (above ao) + card (UNIV - above ao)"
using card_Un_disjoint[of "above ao" "UNIV - above ao"] by auto
hence m_eq: "m = card (above ao)" unfolding m_def by simp
have "m ≠ length ys + 1 ∧ (m = length ys + 2 ⟶ ¬ proper_interval (Some (last (y # ys))) None) ⟷
(∃A ⊆ above ao. A ≠ {} ∧ A ⊏' - set (y # ys) ∩ above ao)" (is "?lhs ⟷ ?rhs")
proof
assume ?lhs
hence m: "m ≠ length ys + 1"
and pi: "m = length ys + 2 ⟹ ¬ proper_interval (Some (last (y # ys))) None"
by simp_all
have "length ys + 1 = card (set (y # ys))" using ys len_ys by simp
also have "… ≤ m" unfolding m_eq by(rule card_mono)(simp, rule ys)
finally have "length ys + 2 ≤ m" using m by simp
show ?rhs
proof(cases "m = length ys + 2")
case True
hence "card (UNIV - (UNIV - above ao) - set (y # ys)) = 1"
using ys len_ys
by(subst card_Diff_subset)(auto simp add: m_def card_Diff_subset)
then obtain z where z: "z ∈ above ao" "z ≠ y" "z ∉ set ys"
unfolding card_eq_1_iff by auto
from True have "¬ proper_interval (Some (last (y # ys))) None" by(rule pi)
hence "z ≤ last (y # ys)" by(simp add: proper_interval_simps not_less del: last.simps)
moreover have ly: "last (y # ys) ∈ set (y # ys)" by(rule last_in_set) simp
with z have "z ≠ last (y # ys)" by auto
ultimately have "z < last (y # ys)" by simp
hence "{last (y # ys)} ⊏' {z}"
using z ly ys by(auto 4 3 simp add: set_less_aux_def)
also have "… ⊑' - set (y # ys) ∩ above ao"
using z by(auto intro: subset_finite_imp_set_less_eq_aux)
also have "{last (y # ys)} ≠ {}" using ly ys by blast
moreover have "{last (y # ys)} ⊆ above ao" using ys by auto
ultimately show ?thesis by blast
next
case False
with ‹length ys + 2 ≤ m› ys len_ys
have "card (UNIV - (UNIV - above ao) - set (y # ys)) > 1"
by(subst card_Diff_subset)(auto simp add: card_Diff_subset m_def)
from card_gt_1D[OF this]
obtain x x' where x: "x ∈ above ao" "x ≠ y" "x ∉ set ys"
and x': "x' ∈ above ao" "x' ≠ y" "x' ∉ set ys"
and neq: "x ≠ x'" by auto
hence "{x} ⊏' {x, x'} ∩ above ao"
by(simp_all add: psubsetI psubset_finite_imp_set_less_aux)
also have "… ⊑' - set (y # ys) ∩ above ao" using x x' ys
by(auto intro: subset_finite_imp_set_less_eq_aux)
also have "{x} ∩ above ao ≠ {}" using x by simp
ultimately show ?rhs by blast
qed
next
assume ?rhs
then obtain A where nempty: "A ≠ {}"
and less: "A ⊏' - set (y # ys) ∩ above ao"
and subset: "A ⊆ above ao" by blast
have "card (set (y # ys)) ≤ card (above ao)" using ys(3) by(simp add: card_mono)
hence "length ys + 1 ≤ m" unfolding m_eq using ys by(simp add: len_ys)
have "m ≠ length ys + 1"
proof
assume "m = length ys + 1"
hence "card (above ao) ≤ card (set (y # ys))"
unfolding m_eq using ys len_ys by auto
from card_seteq[OF _ _ this] ys have "set (y # ys) = above ao" by simp
with nempty less show False by(auto simp add: set_less_aux_def)
qed
moreover
{ assume "m = length ys + 2"
hence "card (above ao - set (y # ys)) = 1"
using ys len_ys m_eq by(auto simp add: card_Diff_subset)
then obtain z where z: "above ao - set (y # ys) = {z}"
unfolding card_eq_1_iff ..
hence eq_z: "- set (y # ys) ∩ above ao = {z}" by auto
with less have "A ⊏' {z}" by simp
have "¬ proper_interval (Some (last (y # ys))) None"
proof
assume "proper_interval (Some (last (y # ys))) None"
then obtain z' where z': "last (y # ys) < z'"
by(clarsimp simp add: proper_interval_simps)
have "last (y # ys) ∈ set (y # ys)" by(rule last_in_set) simp
with ys z' have "z' ∈ above ao" "z' ∉ set (y # ys)"
using above_upclosed local.not_less local.sorted_last ys(1) z' by blast+
with eq_z have "z = z'" by fastforce
from z' have "⋀x. x ∈ set (y # ys) ⟹ x < z'" using ys
by(auto dest: sorted_last simp del: sorted_wrt.simps(2))
with eq_z ‹z = z'›
have "⋀x. x ∈ above ao ⟹ x ≤ z'" by(fastforce)
with ‹A ⊏' {z}› nempty ‹z = z'› subset
show False by(auto simp add: set_less_aux_def)
qed }
ultimately show ?lhs by simp
qed
thus ?case by(simp add: length_last_def m_def Let_def)
next
case (3 ao x xs)
note xs = ‹sorted (x # xs)› ‹distinct (x # xs)› ‹set (x # xs) ⊆ above ao›
have len_xs: "length xs = card (set xs)"
using xs by(auto simp add: List.card_set intro: sym)
define m where "m = CARD('a) - card (UNIV - above ao)"
have "CARD('a) = card (above ao) + card (UNIV - above ao)"
using card_Un_disjoint[of "above ao" "UNIV - above ao"] by auto
hence m_eq: "m = card (above ao)" unfolding m_def by simp
have "m ≠ length xs + 1 ∧ (m = length xs + 2 ⟶ ¬ proper_interval (Some (last (x # xs))) None) ⟷
(∃A ⊆ above ao. set (x # xs) ⊏' A ∧ A ⊏' above ao)" (is "?lhs ⟷ ?rhs")
proof
assume ?lhs
hence m: "m ≠ length xs + 1"
and pi: "m = length xs + 2 ⟹ ¬ proper_interval (Some (last (x # xs))) None"
by simp_all
have "length xs + 1 = card (set (x # xs))" using xs len_xs by simp
also have "… ≤ m" unfolding m_eq by(rule card_mono)(simp, rule xs)
finally have "length xs + 2 ≤ m" using m by simp
show ?rhs
proof(cases "m = length xs + 2")
case True
hence "card (UNIV - (UNIV - above ao) - set (x # xs)) = 1"
using xs len_xs
by(subst card_Diff_subset)(auto simp add: m_def card_Diff_subset)
then obtain z where z: "z ∈ above ao" "z ≠ x" "z ∉ set xs"
unfolding card_eq_1_iff by auto
define A where "A = insert z {y. y ∈ set (x # xs) ∧ y < z}"
from True have "¬ proper_interval (Some (last (x # xs))) None" by(rule pi)
hence "z ≤ last (x # xs)" by(simp add: proper_interval_simps not_less del: last.simps)
moreover have lx: "last (x # xs) ∈ set (x # xs)" by(rule last_in_set) simp
with z have "z ≠ last (x # xs)" by auto
ultimately have "z < last (x # xs)" by simp
hence "set (x # xs) ⊏' A"
using z xs by(auto simp add: A_def set_less_aux_def intro: rev_bexI[where x=z])
moreover have "last (x # xs) ∉ A" using xs ‹z < last (x # xs)›
by(auto simp add: A_def simp del: last.simps)
hence "A ⊂ insert (last (x # xs)) A" by blast
hence less': "A ⊏' insert (last (x # xs)) A"
by(rule psubset_finite_imp_set_less_aux) simp
have "… ⊆ above ao" using xs lx z
by(auto simp del: last.simps simp add: A_def)
hence "insert (last (x # xs)) A ⊑' above ao"
by(auto intro: subset_finite_imp_set_less_eq_aux)
with less' have "A ⊏' above ao"
by(rule set_less_trans_set_less_eq)
moreover have "A ⊆ above ao" using xs z by(auto simp add: A_def)
ultimately show ?thesis by blast
next
case False
with ‹length xs + 2 ≤ m› xs len_xs
have "card (UNIV - (UNIV - above ao) - set (x # xs)) > 1"
by(subst card_Diff_subset)(auto simp add: card_Diff_subset m_def)
from card_gt_1D[OF this]
obtain y y' where y: "y ∈ above ao" "y ≠ x" "y ∉ set xs"
and y': "y' ∈ above ao" "y' ≠ x" "y' ∉ set xs"
and neq: "y ≠ y'" by auto
define A where "A = insert y (set (x # xs) ∩ above ao)"
hence "set (x # xs) ⊂ A" using y xs by auto
hence "set (x # xs) ⊏' …"
by(fastforce intro: psubset_finite_imp_set_less_aux)
moreover have *: "… ⊂ above ao"
using y y' neq by(auto simp add: A_def)
moreover from * have "A ⊏' above ao"
by(auto intro: psubset_finite_imp_set_less_aux)
ultimately show ?thesis by blast
qed
next
assume ?rhs
then obtain A where lessA: "set (x # xs) ⊏' A"
and Aless: "A ⊏' above ao" and subset: "A ⊆ above ao" by blast
have "card (set (x # xs)) ≤ card (above ao)" using xs(3) by(simp add: card_mono)
hence "length xs + 1 ≤ m" unfolding m_eq using xs by(simp add: len_xs)
have "m ≠ length xs + 1"
proof
assume "m = length xs + 1"
hence "card (above ao) ≤ card (set (x # xs))"
unfolding m_eq using xs len_xs by auto
from card_seteq[OF _ _ this] xs have "set (x # xs) = above ao" by simp
with lessA Aless show False by(auto dest: set_less_aux_antisym)
qed
moreover
{ assume "m = length xs + 2"
hence "card (above ao - set (x # xs)) = 1"
using xs len_xs m_eq by(auto simp add: card_Diff_subset)
then obtain z where z: "above ao - set (x # xs) = {z}"
unfolding card_eq_1_iff ..
have "¬ proper_interval (Some (last (x # xs))) None"
proof
assume "proper_interval (Some (last (x # xs))) None"
then obtain z' where z': "last (x # xs) < z'"
by(clarsimp simp add: proper_interval_simps)
have "last (x # xs) ∈ set (x # xs)" by(rule last_in_set) simp
with xs z' have "z' ∈ above ao" "z' ∉ set (x # xs)"
by(auto simp del: last.simps sorted_wrt.simps(2) intro: above_upclosed dest: sorted_last)
with z have "z = z'" by fastforce
from z' have y_less: "⋀y. y ∈ set (x # xs) ⟹ y < z'" using xs
by(auto simp del: sorted_wrt.simps(2) dest: sorted_last)
with z ‹z = z'› have "⋀y. y ∈ above ao ⟹ y ≤ z'" by(fastforce)
from lessA subset obtain y where y: "y ∈ A" "y ∈ above ao" "y ∉ set (x # xs)"
and min: "⋀y'. ⟦ y' ∈ set (x # xs); y' ∈ above ao; y' ∉ A ⟧ ⟹ y ≤ y'"
by(auto simp add: set_less_aux_def)
with z ‹z = z'› have "y = z'" by auto
have "set (x # xs) ⊆ A"
proof
fix y'
assume y': "y' ∈ set (x # xs)"
show "y' ∈ A"
proof(rule ccontr)
assume "y' ∉ A"
from y' xs have "y' ∈ above ao" by auto
with y' have "y ≤ y'" using ‹y' ∉ A› by(rule min)
moreover from y' have "y' < z'" by(rule y_less)
ultimately show False using ‹y = z'› by simp
qed
qed
moreover from z xs have "above ao = insert z (set (x # xs))" by auto
ultimately have "A = above ao" using y ‹y = z'› ‹z = z'› subset by auto
with Aless show False by simp
qed }
ultimately show ?lhs by simp
qed
thus ?case by(simp add: length_last_def m_def Let_def del: last.simps)
next
case (4 ao x xs y ys)
note xxs = ‹sorted (x # xs)› ‹distinct (x # xs)›
and yys = ‹sorted (y # ys)› ‹distinct (y # ys)›
and xxs_above = ‹set (x # xs) ⊆ above ao›
and yys_above = ‹set (y # ys) ⊆ above ao›
from xxs have xs: "sorted xs" "distinct xs" and x_Min: "∀x'∈set xs. x < x'"
by(auto simp add: less_le)
from yys have ys: "sorted ys" "distinct ys" and y_Min: "∀y'∈set ys. y < y'"
by(auto simp add: less_le)
have len_xs: "length xs = card (set xs)"
using xs by(auto simp add: List.card_set intro: sym)
have len_ys: "length ys = card (set ys)"
using ys by(auto simp add: List.card_set intro: sym)
show ?case
proof(cases "x < y")
case True
have "proper_interval ao (Some x) ∨
proper_interval_set_Compl_aux (Some x) (card (UNIV - above ao) + 1) xs (y # ys) ⟷
(∃A ⊆ above ao. set (x # xs) ⊏' A ∧ A ⊏' - set (y # ys) ∩ above ao)"
(is "?lhs ⟷ ?rhs")
proof(cases "proper_interval ao (Some x)")
case True
then obtain z where z: "z ∈ above ao" "z < x"
by(clarsimp simp add: proper_interval_Some2)
moreover with xxs have "∀x'∈set xs. z < x'" by(auto)
ultimately have "set (x # xs) ⊏' {z}"
by(auto simp add: set_less_aux_def intro!: bexI[where x=z])
moreover {
from z yys ‹x < y› have "z < y" "∀y'∈set ys. z < y'"
by(auto)
hence subset: "{z} ⊆ - set (y # ys) ∩ above ao"
using ys ‹x < y› z by auto
moreover have "x ∈ …" using yys xxs ‹x < y› xxs_above by(auto)
ultimately have "{z} ⊂ …" using ‹z < x› by fastforce
hence "{z} ⊏' …"
by(fastforce intro: psubset_finite_imp_set_less_aux) }
moreover have "{z} ⊆ above ao" using z by simp
ultimately have ?rhs by blast
thus ?thesis using True by simp
next
case False
hence above_eq: "above ao = insert x (above (Some x))" using xxs_above
by(auto simp add: proper_interval_Some2 intro: above_upclosed)
moreover have "card (above (Some x)) < CARD('a)"
by(rule psubset_card_mono)(auto)
ultimately have card_eq: "card (UNIV - above ao) + 1 = card (UNIV - above (Some x))"
by(simp add: card_Diff_subset)
from xxs_above x_Min have xs_above: "set xs ⊆ above (Some x)" by(auto)
from ‹x < y› y_Min have "set (y # ys) ⊆ above (Some x)" by(auto)
with ‹x < y› card_eq xs xs_above yys
have "proper_interval_set_Compl_aux (Some x) (card (UNIV - above ao) + 1) xs (y # ys) ⟷
(∃A ⊆ above (Some x). set xs ⊏' A ∧ A ⊏' - set (y # ys) ∩ above (Some x))"
by(subst card_eq)(rule 4)
also have "… ⟷ ?rhs" (is "?lhs' ⟷ _")
proof
assume ?lhs'
then obtain A where less_A: "set xs ⊏' A"
and A_less: "A ⊏' - set (y # ys) ∩ above (Some x)"
and subset: "A ⊆ above (Some x)" by blast
let ?A = "insert x A"
have Min_A': "Min ?A = x" using xxs_above False subset
by(auto intro!: Min_eqI simp add: proper_interval_Some2)
moreover have "Min (set (x # xs)) = x"
using x_Min by(auto intro!: Min_eqI)
moreover have Amx: "A - {x} = A"
using False subset
by(auto simp add: proper_interval_Some2 intro: above_upclosed)
moreover have "set xs - {x} = set xs" using x_Min by auto
ultimately have less_A': "set (x # xs) ⊏' ?A"
using less_A xxs_above x_Min by(subst set_less_aux_rec) simp_all
have "x ∈ - insert y (set ys) ∩ above ao"
using ‹x < y› xxs_above y_Min by auto
hence "- insert y (set ys) ∩ above ao ≠ {}" by auto
moreover have "Min (- insert y (set ys) ∩ above ao) = x"
using yys y_Min xxs_above ‹x < y› False
by(auto intro!: Min_eqI simp add: proper_interval_Some2)
moreover have "- set (y # ys) ∩ above ao - {x} = - set (y # ys) ∩ above (Some x)"
using yys_above False xxs_above
by(auto simp add: proper_interval_Some2 intro: above_upclosed)
ultimately have A'_less: "?A ⊏' - set (y # ys) ∩ above ao"
using Min_A' A_less Amx xxs_above by(subst set_less_aux_rec) simp_all
moreover have "?A ⊆ above ao" using subset xxs_above by(auto intro: above_upclosed)
ultimately show ?rhs using less_A' by blast
next
assume ?rhs
then obtain A where less_A: "set (x # xs) ⊏' A"
and A_less: "A ⊏' - set (y # ys) ∩ above ao"
and subset: "A ⊆ above ao" by blast
let ?A = "A - {x}"
from less_A subset xxs_above have "set (x # xs) ∩ above ao ⊏' A ∩ above ao"
by(simp add: Int_absorb2)
with False xxs_above subset have "x ∈ A"
by(auto simp add: set_less_aux_def proper_interval_Some2)
hence "… ≠ {}" by auto
moreover from ‹x ∈ A› False subset
have Min_A: "Min A = x"
by(auto intro!: Min_eqI simp add: proper_interval_Some2 not_less)
moreover have "Min (set (x # xs)) = x"
using x_Min by(auto intro!: Min_eqI)
moreover have eq_A: "?A ⊆ above (Some x)"
using xxs_above False subset
by(fastforce simp add: proper_interval_Some2 not_less intro: above_upclosed)
moreover have "set xs - {x} = set xs"
using x_Min by(auto)
ultimately have less_A': "set xs ⊏' ?A"
using xxs_above less_A by(subst (asm) set_less_aux_rec)(simp_all cong: conj_cong)
have "x ∈ - insert y (set ys) ∩ above ao"
using ‹x < y› xxs_above y_Min by auto
hence "- insert y (set ys) ∩ above ao ≠ {}" by auto
moreover have "Min (- set (y # ys) ∩ above ao) = x"
using yys y_Min xxs_above ‹x < y› False
by(auto intro!: Min_eqI simp add: proper_interval_Some2)
moreover have "- set (y # ys) ∩ above (Some x) = - set (y # ys) ∩ above ao - {x}"
by(auto simp add: above_eq)
ultimately have "?A ⊏' - set (y # ys) ∩ above (Some x)"
using A_less ‹A ≠ {}› eq_A Min_A
by(subst (asm) set_less_aux_rec) simp_all
with less_A' eq_A show ?lhs' by blast
qed
finally show ?thesis using False by simp
qed
thus ?thesis using True by simp
next
case False
show ?thesis
proof(cases "y < x")
case True
have "proper_interval ao (Some y) ∨
proper_interval_set_Compl_aux (Some y) (card (UNIV - above ao) + 1) (x # xs) ys ⟷
(∃A ⊆ above ao. set (x # xs) ⊏' A ∧ A ⊏' - set (y # ys) ∩ above ao)"
(is "?lhs ⟷ ?rhs")
proof(cases "proper_interval ao (Some y)")
case True
then obtain z where z: "z ∈ above ao" "z < y"
by(clarsimp simp add: proper_interval_Some2)
from xxs ‹y < x› have "∀x'∈set (x # xs). y < x'" by(auto)
hence less_A: "set (x # xs) ⊏' {y}"
by(auto simp add: set_less_aux_def intro!: bexI[where x=y])
have "{y} ⊏' {z}"
using z y_Min by(auto simp add: set_less_aux_def intro: bexI[where x=z])
also have "… ⊆ - set (y # ys) ∩ above ao" using z y_Min by auto
hence "{z} ⊑' …" by(auto intro: subset_finite_imp_set_less_eq_aux)
finally have "{y} ⊏' …" .
moreover have "{y} ⊆ above ao" using yys_above by auto
ultimately have ?rhs using less_A by blast
thus ?thesis using True by simp
next
case False
hence above_eq: "above ao = insert y (above (Some y))" using yys_above
by(auto simp add: proper_interval_Some2 intro: above_upclosed)
moreover have "card (above (Some y)) < CARD('a)"
by(rule psubset_card_mono)(auto)
ultimately have card_eq: "card (UNIV - above ao) + 1 = card (UNIV - above (Some y))"
by(simp add: card_Diff_subset)
from yys_above y_Min have ys_above: "set ys ⊆ above (Some y)" by(auto)
have eq_ys: "- set ys ∩ above (Some y) = - set (y # ys) ∩ above ao"
by(auto simp add: above_eq)
from ‹y < x› x_Min have "set (x # xs) ⊆ above (Some y)" by(auto)
with ‹¬ x < y› ‹y < x› card_eq xxs ys ys_above
have "proper_interval_set_Compl_aux (Some y) (card (UNIV - above ao) + 1) (x # xs) ys ⟷
(∃A ⊆ above (Some y). set (x # xs) ⊏' A ∧ A ⊏' - set ys ∩ above (Some y))"
by(subst card_eq)(rule 4)
also have "… ⟷ ?rhs" (is "?lhs' ⟷ _")
proof
assume ?lhs'
then obtain A where "set (x # xs) ⊏' A" and subset: "A ⊆ above (Some y)"
and "A ⊏' - set ys ∩ above (Some y)" by blast
moreover from subset have "A - {y} = A" by auto
ultimately have "set (x # xs) ⊏' A - {y}"
and "A - {y} ⊏' - set (y # ys) ∩ above ao"
using eq_ys by simp_all
moreover from subset have "A - {y} ⊆ above ao"
using yys_above by(auto intro: above_upclosed)
ultimately show ?rhs by blast
next
assume ?rhs
then obtain A where "set (x # xs) ⊏' A"
and A_less: "A ⊏' - set (y # ys) ∩ above ao"
and subset: "A ⊆ above ao" by blast
moreover
from A_less False yys_above have "y ∉ A"
by(auto simp add: set_less_aux_def proper_interval_Some2 not_less)
ultimately have "set (x # xs) ⊏' A"
and "A ⊏' - set ys ∩ above (Some y)"
using eq_ys by simp_all
moreover from ‹y ∉ A› subset above_eq have "A ⊆ above (Some y)" by auto
ultimately show ?lhs' by blast
qed
finally show ?thesis using False by simp
qed
with False True show ?thesis by simp
next
case False
with ‹¬ x < y› have "x = y" by simp
have "proper_interval ao (Some x) ∧
(CARD('a) - (card (UNIV - above ao) + length ys) ≠ 2 ∨
CARD('a) - (card (UNIV - above ao) + length xs) ≠ 2) ⟷
(∃A ⊆ above ao. set (x # xs) ⊏' A ∧ A ⊏' - set (y # ys) ∩ above ao)"
(is "?below ∧ ?card ⟷ ?rhs")
proof(cases "?below")
case False
hence "- set (y # ys) ∩ above ao ⊏' set (x # xs)"
using ‹x = y› yys_above xxs_above y_Min
by(auto simp add: not_less set_less_aux_def proper_interval_Some2 intro!: bexI[where x=y])
with False show ?thesis by(auto dest: set_less_aux_trans)
next
case True
then obtain z where z: "z ∈ above ao" "z < x"
by(clarsimp simp add: proper_interval_Some2)
have "?card ⟷ ?rhs"
proof
assume ?rhs
then obtain A where less_A: "set (x # xs) ⊏' A"
and A_less: "A ⊏' - set (y # ys) ∩ above ao"
and subset: "A ⊆ above ao" by blast
{
assume c_ys: "CARD('a) - (card (UNIV - above ao) + length ys) = 2"
and c_xs: "CARD('a) - (card (UNIV - above ao) + length xs) = 2"
from c_ys yys_above len_ys y_Min have "card (UNIV - (UNIV - above ao) - set (y # ys)) = 1"
by(subst card_Diff_subset)(auto simp add: card_Diff_subset)
then obtain z' where eq_y: "- set (y # ys) ∩ above ao = {z'}"
unfolding card_eq_1_iff by auto
moreover from z have "z ∉ set (y # ys)" using ‹x = y› y_Min by auto
ultimately have "z' = z" using z by fastforce
from c_xs xxs_above len_xs x_Min have "card (UNIV - (UNIV - above ao) - set (x # xs)) = 1"
by(subst card_Diff_subset)(auto simp add: card_Diff_subset)
then obtain z'' where eq_x: "- set (x # xs) ∩ above ao = {z''}"
unfolding card_eq_1_iff by auto
moreover from z have "z ∉ set (x # xs)" using x_Min by auto
ultimately have "z'' = z" using z by fastforce
from less_A subset obtain q where "q ∈ A" "q ∈ above ao" "q ∉ set (x # xs)"
by(auto simp add: set_less_aux_def)
hence "q ∈ {z''}" unfolding eq_x[symmetric] by simp
hence "q = z''" by simp
with ‹q ∈ A› ‹z' = z› ‹z'' = z› z
have "- set (y # ys) ∩ above ao ⊆ A"
unfolding eq_y by simp
hence "- set (y # ys) ∩ above ao ⊑' A"
by(auto intro: subset_finite_imp_set_less_eq_aux)
with A_less have False by(auto dest: set_less_trans_set_less_eq) }
thus ?card by auto
next
assume ?card (is "?card_ys ∨ ?card_xs")
thus ?rhs
proof
assume ?card_ys
let ?YS = "UNIV - (UNIV - above ao) - set (y # ys)"
from ‹?card_ys› yys_above len_ys y_Min have "card ?YS ≠ 1"
by(subst card_Diff_subset)(auto simp add: card_Diff_subset)
moreover have "?YS ≠ {}" using True y_Min yys_above ‹x = y›
by(fastforce simp add: proper_interval_Some2)
hence "card ?YS ≠ 0" by simp
ultimately have "card ?YS > 1" by(cases "card ?YS") simp_all
from card_gt_1D[OF this] obtain x' y'
where x': "x' ∈ above ao" "x' ∉ set (y # ys)"
and y': "y' ∈ above ao" "y' ∉ set (y # ys)"
and neq: "x' ≠ y'" by auto
let ?A = "{z}"
have "set (x # xs) ⊏' ?A" using z x_Min
by(auto simp add: set_less_aux_def intro!: rev_bexI)
moreover
{ have "?A ⊆ - set (y # ys) ∩ above ao"
using z ‹x = y› y_Min by(auto)
moreover have "x' ∉ ?A ∨ y' ∉ ?A" using neq by auto
with x' y' have "?A ≠ - set (y # ys) ∩ above ao" by auto
ultimately have "?A ⊂ - set (y # ys) ∩ above ao" by(rule psubsetI)
hence "?A ⊏' …" by(fastforce intro: psubset_finite_imp_set_less_aux) }
ultimately show ?thesis using z by blast
next
assume ?card_xs
let ?XS = "UNIV - (UNIV - above ao) - set (x # xs)"
from ‹?card_xs› xxs_above len_xs x_Min have "card ?XS ≠ 1"
by(subst card_Diff_subset)(auto simp add: card_Diff_subset)
moreover have "?XS ≠ {}" using True x_Min xxs_above
by(fastforce simp add: proper_interval_Some2)
hence "card ?XS ≠ 0" by simp
ultimately have "card ?XS > 1" by(cases "card ?XS") simp_all
from card_gt_1D[OF this] obtain x' y'
where x': "x' ∈ above ao" "x' ∉ set (x # xs)"
and y': "y' ∈ above ao" "y' ∉ set (x # xs)"
and neq: "x' ≠ y'" by auto
define A
where "A = (if x' = Min (above ao) then insert y' (set (x # xs)) else insert x' (set (x # xs)))"
hence "set (x # xs) ⊆ A" by auto
moreover have "set (x # xs) ≠ …"
using neq x' y' by(auto simp add: A_def)
ultimately have "set (x # xs) ⊂ A" ..
hence "set (x # xs) ⊏' …"
by(fastforce intro: psubset_finite_imp_set_less_aux)
moreover {
have nempty: "above ao ≠ {}" using z by auto
have "A ⊏' {Min (above ao)}"
using z x' y' neq ‹x = y› x_Min xxs_above
by(auto 6 4 simp add: set_less_aux_def A_def nempty intro!: rev_bexI Min_eqI)
also have "Min (above ao) ≤ z" using z by(simp)
hence "Min (above ao) < x" using ‹z < x› by(rule le_less_trans)
with ‹x = y› y_Min have "Min (above ao) ∉ set (y # ys)" by auto
hence "{Min (above ao)} ⊆ - set (y # ys) ∩ above ao"
by(auto simp add: nempty)
hence "{Min (above ao)} ⊑' …" by(auto intro: subset_finite_imp_set_less_eq_aux)
finally have "A ⊏' …" . }
moreover have "A ⊆ above ao" using xxs_above yys_above x' y'
by(auto simp add: A_def)
ultimately show ?rhs by blast
qed
qed
thus ?thesis using True by simp
qed
thus ?thesis using ‹x = y› by simp
qed
qed
qed }
from this[of None]
show ?thesis by(simp)
qed
lemma proper_interval_Compl_set_aux:
assumes fin: "finite (UNIV :: 'a set)"
and xs: "sorted xs" "distinct xs"
and ys: "sorted ys" "distinct ys"
shows "proper_interval_Compl_set_aux None xs ys ⟷ (∃A. - set xs ⊏' A ∧ A ⊏' set ys)"
proof -
note [simp] = finite_subset[OF subset_UNIV fin]
define above where "above = case_option UNIV (Collect ∘ less)"
have above_simps [simp]: "above None = UNIV" "⋀x. above (Some x) = {y. x < y}"
and above_upclosed: "⋀x y ao. ⟦ x ∈ above ao; x < y ⟧ ⟹ y ∈ above ao"
and proper_interval_Some2: "⋀x ao. proper_interval ao (Some x) ⟷ (∃z∈above ao. z < x)"
by(simp_all add: proper_interval_simps above_def split: option.splits)
{ fix ao n
assume "set xs ⊆ above ao" "set ys ⊆ above ao"
from xs ‹set xs ⊆ above ao› ys ‹set ys ⊆ above ao›
have "proper_interval_Compl_set_aux ao xs ys ⟷
(∃A. - set xs ∩ above ao ⊏' A ∩ above ao ∧ A ∩ above ao ⊏' set ys ∩ above ao)"
proof(induction ao xs ys rule: proper_interval_Compl_set_aux.induct)
case ("2_1" ao ys)
{ fix A
assume "above ao ⊏' A ∩ above ao"
also have "… ⊆ above ao" by simp
hence "A ∩ above ao ⊑' above ao"
by(auto intro: subset_finite_imp_set_less_eq_aux)
finally have False by simp }
thus ?case by auto
next
case ("2_2" ao xs) thus ?case by simp
next
case (1 ao x xs y ys)
note xxs = ‹sorted (x # xs)› ‹distinct (x # xs)›
hence xs: "sorted xs" "distinct xs" and x_Min: "∀x' ∈ set xs. x < x'"
by(auto simp add: less_le)
note yys = ‹sorted (y # ys)› ‹distinct (y # ys)›
hence ys: "sorted ys" "distinct ys" and y_Min: "∀y'∈set ys. y < y'"
by(auto simp add: less_le)
note xxs_above = ‹set (x # xs) ⊆ above ao›
note yys_above = ‹set (y # ys) ⊆ above ao›
show ?case
proof(cases "x < y")
case True
have "¬ proper_interval ao (Some x) ∧ proper_interval_Compl_set_aux (Some x) xs (y # ys) ⟷
(∃A. - set (x # xs) ∩ above ao ⊏' A ∩ above ao ∧ A ∩ above ao ⊏' set (y # ys) ∩ above ao)"
(is "?lhs ⟷ ?rhs")
proof(cases "proper_interval ao (Some x)")
case True
then obtain z where z: "z < x" "z ∈ above ao"
by(auto simp add: proper_interval_Some2)
hence nempty: "above ao ≠ {}" by auto
with z have "Min (above ao) ≤ z" by auto
hence "Min (above ao) < x" using ‹z < x› by(rule le_less_trans)
hence "set (y # ys) ∩ above ao ⊏' - set (x # xs) ∩ above ao"
using y_Min x_Min z ‹x < y›
by(fastforce simp add: set_less_aux_def nempty intro!: Min_eqI bexI[where x="Min (above ao)"])
thus ?thesis using True by(auto dest: set_less_aux_trans set_less_aux_antisym)
next
case False
hence above_eq: "above ao = insert x (above (Some x))"
using xxs_above by(auto simp add: proper_interval_Some2 intro: above_upclosed)
from x_Min have xs_above: "set xs ⊆ above (Some x)" by auto
from ‹x < y› y_Min have ys_above: "set (y # ys) ⊆ above (Some x)" by auto
have eq_xs: "- set xs ∩ above (Some x) = - set (x # xs) ∩ above ao"
using above_eq by auto
have eq_ys: "set (y # ys) ∩ above (Some x) = set (y # ys) ∩ above ao"
using y_Min ‹x < y› xxs_above by(auto intro: above_upclosed)
from ‹x < y› xs xs_above yys ys_above
have "proper_interval_Compl_set_aux (Some x) xs (y # ys) ⟷
(∃A. - set xs ∩ above (Some x) ⊏' A ∩ above (Some x) ∧
A ∩ above (Some x) ⊏' set (y # ys) ∩ above (Some x))"
by(rule "1.IH")
also have "… ⟷ ?rhs" (is "?lhs ⟷ _")
proof
assume ?lhs
then obtain A where "- set xs ∩ above (Some x) ⊏' A ∩ above (Some x)"
and "A ∩ above (Some x) ⊏' set (y # ys) ∩ above (Some x)" by blast
moreover have "A ∩ above (Some x) = (A - {x}) ∩ above ao"
using above_eq by auto
ultimately have "- set (x # xs) ∩ above ao ⊏' (A - {x}) ∩ above ao"
and "(A - {x}) ∩ above ao ⊏' set (y # ys) ∩ above ao"
using eq_xs eq_ys by simp_all
thus ?rhs by blast
next
assume ?rhs
then obtain A where "- set (x # xs) ∩ above ao ⊏' A ∩ above ao"
and A_less: "A ∩ above ao ⊏' set (y # ys) ∩ above ao" by blast
moreover have "x ∉ A"
proof
assume "x ∈ A"
hence "set (y # ys) ∩ above ao ⊏' A ∩ above ao"
using y_Min ‹x < y› by(auto simp add: above_eq set_less_aux_def intro!: bexI[where x=x])
with A_less show False by(auto dest: set_less_aux_antisym)
qed
hence "A ∩ above ao = A ∩ above (Some x)" using above_eq by auto
ultimately show ?lhs using eq_xs eq_ys by auto
qed
finally show ?thesis using False by simp
qed
thus ?thesis using True by simp
next
case False
show ?thesis
proof(cases "y < x")
case True
show ?thesis (is "?lhs ⟷ ?rhs")
proof(cases "proper_interval ao (Some y)")
case True
then obtain z where z: "z < y" "z ∈ above ao"
by(auto simp add: proper_interval_Some2)
hence nempty: "above ao ≠ {}" by auto
with z have "Min (above ao) ≤ z" by auto
hence "Min (above ao) < y" using ‹z < y› by(rule le_less_trans)
hence "set (y # ys) ∩ above ao ⊏' - set (x # xs) ∩ above ao"
using y_Min x_Min z ‹y < x›
by(fastforce simp add: set_less_aux_def nempty intro!: Min_eqI bexI[where x="Min (above ao)"])
thus ?thesis using True ‹y < x› by(auto dest: set_less_aux_trans set_less_aux_antisym)
next
case False
hence above_eq: "above ao = insert y (above (Some y))"
using yys_above by(auto simp add: proper_interval_Some2 intro: above_upclosed)
from y_Min have ys_above: "set ys ⊆ above (Some y)" by auto
from ‹y < x› x_Min have xs_above: "set (x # xs) ⊆ above (Some y)" by auto
have "y ∈ - set (x # xs) ∩ above ao" using ‹y < x› x_Min yys_above by auto
hence nempty: "- set (x # xs) ∩ above ao ≠ {}" by auto
have Min_x: "Min (- set (x # xs) ∩ above ao) = y"
using above_eq ‹y < x› x_Min by(auto intro!: Min_eqI)
have Min_y: "Min (set (y # ys) ∩ above ao) = y"
using y_Min above_eq by(auto intro!: Min_eqI)
have eq_xs: "- set (x # xs) ∩ above ao - {y} = - set (x # xs) ∩ above (Some y)"
by(auto simp add: above_eq)
have eq_ys: "set ys ∩ above ao - {y} = set ys ∩ above (Some y)"
using y_Min above_eq by auto
from ‹¬ x < y› ‹y < x› xxs xs_above ys ys_above
have "proper_interval_Compl_set_aux (Some y) (x # xs) ys ⟷
(∃A. - set (x # xs) ∩ above (Some y) ⊏' A ∩ above (Some y) ∧
A ∩ above (Some y) ⊏' set ys ∩ above (Some y))"
by(rule "1.IH")
also have "… ⟷ ?rhs" (is "?lhs' ⟷ _")
proof
assume ?lhs'
then obtain A where less_A: "- set (x # xs) ∩ above (Some y) ⊏' A ∩ above (Some y)"
and A_less: "A ∩ above (Some y) ⊏' set ys ∩ above (Some y)" by blast
let ?A = "insert y A"
have Min_A: "Min (?A ∩ above ao) = y"
using above_eq by(auto intro!: Min_eqI)
moreover have A_eq: "A ∩ above ao - {y} = A ∩ above (Some y)"
using above_eq by auto
ultimately have less_A': "- set (x # xs) ∩ above ao ⊏' ?A ∩ above ao"
using nempty yys_above less_A Min_x eq_xs by(subst set_less_aux_rec) simp_all
have A'_less: "?A ∩ above ao ⊏' set (y # ys) ∩ above ao"
using yys_above nempty Min_A A_eq A_less Min_y eq_ys
by(subst set_less_aux_rec) simp_all
with less_A' show ?rhs by blast
next
assume ?rhs
then obtain A where less_A: "- set (x # xs) ∩ above ao ⊏' A ∩ above ao"
and A_less: "A ∩ above ao ⊏' set (y # ys) ∩ above ao" by blast
from less_A have nempty': "A ∩ above ao ≠ {}" by auto
moreover have A_eq: "A ∩ above ao - {y} = A ∩ above (Some y)"
using above_eq by auto
moreover have y_in_xxs: "y ∈ - set (x # xs) ∩ above ao"
using ‹y < x› x_Min yys_above by auto
moreover have "y ∈ A"
proof(rule ccontr)
assume "y ∉ A"
hence "A ∩ above ao ⊏' - set (x # xs) ∩ above ao"
using ‹y < x› x_Min y_in_xxs
by(auto simp add: set_less_aux_def above_eq intro: bexI[where x=y])
with less_A show False by(rule set_less_aux_antisym)
qed
hence Min_A: "Min (A ∩ above ao) = y" using above_eq y_Min by(auto intro!: Min_eqI)
ultimately have less_A': "- set (x # xs) ∩ above (Some y) ⊏' A ∩ above (Some y)"
using nempty less_A Min_x eq_xs
by(subst (asm) set_less_aux_rec)(auto dest: bspec[where x=y])
have A'_less: "A ∩ above (Some y) ⊏' set ys ∩ above (Some y)"
using A_less nempty' yys_above Min_A Min_y A_eq eq_ys
by(subst (asm) set_less_aux_rec) simp_all
with less_A' show ?lhs' by blast
qed
finally show ?thesis using ‹¬ x < y› ‹y < x› False by simp
qed
next
case False
with ‹¬ x < y› have "x = y" by auto
thus ?thesis (is "?lhs ⟷ ?rhs")
proof(cases "proper_interval ao (Some x)")
case True
then obtain z where z: "z < x" "z ∈ above ao"
by(auto simp add: proper_interval_Some2)
hence nempty: "above ao ≠ {}" by auto
with z have "Min (above ao) ≤ z" by auto
hence "Min (above ao) < x" using ‹z < x› by(rule le_less_trans)
hence "set (y # ys) ∩ above ao ⊏' - set (x # xs) ∩ above ao"
using y_Min x_Min z ‹x = y›
by(fastforce simp add: set_less_aux_def nempty intro!: Min_eqI bexI[where x="Min (above ao)"])
thus ?thesis using True ‹x = y› by(auto dest: set_less_aux_trans set_less_aux_antisym)
next
case False
hence above_eq: "above ao = insert x (above (Some x))"
using xxs_above by(auto simp add: proper_interval_Some2 intro: above_upclosed)
have "(ys = [] ⟶ xs ≠ []) ⟷ ?rhs" (is "?lhs' ⟷ _")
proof(intro iffI strip notI)
assume ?lhs'
show ?rhs
proof(cases ys)
case Nil
with ‹?lhs'› obtain x' xs' where xs_eq: "xs = x' # xs'"
by(auto simp add: neq_Nil_conv)
with xs have x'_Min: "∀x'' ∈ set xs'. x' < x''"
by(auto simp add: less_le)
let ?A = "- set (x # xs')"
have "- set (x # xs) ∩ above ao ⊆ ?A ∩ above ao"
using xs_eq by auto
moreover have "x' ∉ - set (x # xs) ∩ above ao" "x' ∈ ?A ∩ above ao"
using xs_eq xxs_above x'_Min x_Min by auto
ultimately have "- set (x # xs) ∩ above ao ⊂ ?A ∩ above ao"
by blast
hence "- set (x # xs) ∩ above ao ⊏' … "
by(fastforce intro: psubset_finite_imp_set_less_aux)
moreover have "… ⊏' set (y # ys) ∩ above ao"
using Nil ‹x = y› by(auto simp add: set_less_aux_def above_eq)
ultimately show ?thesis by blast
next
case (Cons y' ys')
let ?A = "{y}"
have "- set (x # xs) ∩ above ao ⊏' ?A ∩ above ao"
using ‹x = y› x_Min by(auto simp add: set_less_aux_def above_eq)
moreover have "… ⊂ set (y # ys) ∩ above ao"
using yys_above yys Cons by auto
hence "?A ∩ above ao ⊏' …" by(fastforce intro: psubset_finite_imp_set_less_aux)
ultimately show ?thesis by blast
qed
next
assume Nil: "ys = []" "xs = []" and ?rhs
then obtain A where less_A: "- {x} ∩ above ao ⊏' A ∩ above ao"
and A_less: "A ∩ above ao ⊏' {x}" using ‹x = y› above_eq by auto
have "x ∉ A" using A_less by(auto simp add: set_less_aux_def above_eq)
hence "A ∩ above ao ⊆ - {x} ∩ above ao" by auto
hence "A ∩ above ao ⊑' …" by(auto intro: subset_finite_imp_set_less_eq_aux)
with less_A have "… ⊏' …" by(rule set_less_trans_set_less_eq)
thus False by simp
qed
with ‹x = y› False show ?thesis by simp
qed
qed
qed
qed }
from this[of None] show ?thesis by simp
qed
end
subsection ‹Proper intervals for HOL types›
instantiation unit :: proper_interval begin
fun proper_interval_unit :: "unit proper_interval" where
"proper_interval_unit None None = True"
| "proper_interval_unit _ _ = False"
instance by intro_classes auto
end
instantiation bool :: proper_interval begin
fun proper_interval_bool :: "bool proper_interval" where
"proper_interval_bool (Some x) (Some y) ⟷ False"
| "proper_interval_bool (Some x) None ⟷ ¬ x"
| "proper_interval_bool None (Some y) ⟷ y"
| "proper_interval_bool None None = True"
instance by intro_classes auto
end
instantiation nat :: proper_interval begin
fun proper_interval_nat :: "nat proper_interval" where
"proper_interval_nat no None = True"
| "proper_interval_nat None (Some x) ⟷ x > 0"
| "proper_interval_nat (Some x) (Some y) ⟷ y - x > 1"
instance by intro_classes auto
end
instantiation int :: proper_interval begin
fun proper_interval_int :: "int proper_interval" where
"proper_interval_int (Some x) (Some y) ⟷ y - x > 1"
| "proper_interval_int _ _ = True"
instance by intro_classes (auto intro: less_add_one, metis less_add_one minus_less_iff)
end
instantiation integer :: proper_interval begin
context includes integer.lifting begin
lift_definition proper_interval_integer :: "integer proper_interval" is "proper_interval" .
instance by(intro_classes)(transfer, simp only: proper_interval_simps)+
end
end
lemma proper_interval_integer_simps [code]:
includes integer.lifting fixes x y :: integer and xo yo :: "integer option" shows
"proper_interval (Some x) (Some y) = (1 < y - x)"
"proper_interval None yo = True"
"proper_interval xo None = True"
by(transfer, simp)+
instantiation natural :: proper_interval begin
context includes natural.lifting begin
lift_definition proper_interval_natural :: "natural proper_interval" is "proper_interval" .
instance by(intro_classes)(transfer, simp only: proper_interval_simps)+
end
end
lemma proper_interval_natural_simps [code]:
includes natural.lifting fixes x y :: natural and xo :: "natural option" shows
"proper_interval xo None = True"
"proper_interval None (Some y) ⟷ y > 0"
"proper_interval (Some x) (Some y) ⟷ y - x > 1"
by(transfer, simp)+
lemma char_less_iff_nat_of_char: "x < y ⟷ of_char x < (of_char y :: nat)"
by (fact less_char_def)
lemma nat_of_char_inject [simp]: "of_char x = (of_char y :: nat) ⟷ x = y"
by (fact of_char_eq_iff)
lemma char_le_iff_nat_of_char: "x ≤ y ⟷ of_char x ≤ (of_char y :: nat)"
by (fact less_eq_char_def)
instantiation char :: proper_interval
begin
fun proper_interval_char :: "char proper_interval" where
"proper_interval_char None None ⟷ True"
| "proper_interval_char None (Some x) ⟷ x ≠ CHR 0x00"
| "proper_interval_char (Some x) None ⟷ x ≠ CHR 0xFF"
| "proper_interval_char (Some x) (Some y) ⟷ of_char y - of_char x > (1 :: nat)"
instance proof
fix y :: char
{ assume "y ≠ CHR 0x00"
have "CHR 0x00 < y"
proof (rule ccontr)
assume "¬ CHR 0x00 < y"
then have "of_char y = (of_char CHR 0x00 :: nat)"
by (simp add: not_less char_le_iff_nat_of_char)
then have "y = CHR 0x00"
using nat_of_char_inject [of y "CHR 0x00"] by simp
with ‹y ≠ CHR 0x00› show False
by simp
qed }
moreover
{ fix z :: char
assume "z < CHR 0x00"
hence False
by (simp add: char_less_iff_nat_of_char of_char_eq_iff [symmetric]) }
ultimately show "proper_interval None (Some y) = (∃z. z < y)"
by auto
fix x :: char
{ assume "x ≠ CHR 0xFF"
then have "x < CHR 0xFF"
by (auto simp add: neq_iff char_less_iff_nat_of_char)
(insert nat_of_char_less_256 [of x], simp)
hence "∃z. x < z" .. }
moreover
{ fix z :: char
assume "CHR 0xFF < z"
hence "False"
by (simp add: char_less_iff_nat_of_char)
(insert nat_of_char_less_256 [of z], simp) }
ultimately show "proper_interval (Some x) None = (∃z. x < z)" by auto
{ assume gt: "of_char y - of_char x > (1 :: nat)"
let ?z = "char_of (of_char x + (1 :: nat))"
from gt nat_of_char_less_256 [of y]
have 255: "of_char x < (255 :: nat)" by arith
with gt have "x < ?z" "?z < y"
by (simp_all add: char_less_iff_nat_of_char)
hence "∃z. x < z ∧ z < y" by blast }
moreover
{ fix z
assume "x < z" "z < y"
hence "(1 :: nat) < of_char y - of_char x"
by (simp add: char_less_iff_nat_of_char) }
ultimately show "proper_interval (Some x) (Some y) = (∃z>x. z < y)"
by auto
qed simp
end
instantiation Enum.finite_1 :: proper_interval begin
definition proper_interval_finite_1 :: "Enum.finite_1 proper_interval"
where "proper_interval_finite_1 x y ⟷ x = None ∧ y = None"
instance by intro_classes (simp_all add: proper_interval_finite_1_def less_finite_1_def)
end
instantiation Enum.finite_2 :: proper_interval begin
fun proper_interval_finite_2 :: "Enum.finite_2 proper_interval" where
"proper_interval_finite_2 None None ⟷ True"
| "proper_interval_finite_2 None (Some x) ⟷ x = finite_2.a⇩2"
| "proper_interval_finite_2 (Some x) None ⟷ x = finite_2.a⇩1"
| "proper_interval_finite_2 (Some x) (Some y) ⟷ False"
instance by intro_classes (auto simp add: less_finite_2_def)
end
instantiation Enum.finite_3 :: proper_interval begin
fun proper_interval_finite_3 :: "Enum.finite_3 proper_interval" where
"proper_interval_finite_3 None None ⟷ True"
| "proper_interval_finite_3 None (Some x) ⟷ x ≠ finite_3.a⇩1"
| "proper_interval_finite_3 (Some x) None ⟷ x ≠ finite_3.a⇩3"
| "proper_interval_finite_3 (Some x) (Some y) ⟷ x = finite_3.a⇩1 ∧ y = finite_3.a⇩3"
instance
proof
fix x y :: Enum.finite_3
show "proper_interval None (Some y) = (∃z. z < y)"
by(cases y)(auto simp add: less_finite_3_def split: finite_3.split)
show "proper_interval (Some x) None = (∃z. x < z)"
by(cases x)(auto simp add: less_finite_3_def)
show "proper_interval (Some x) (Some y) = (∃z>x. z < y)"
by(auto simp add: less_finite_3_def split: finite_3.split_asm)
qed simp
end
subsection ‹List fusion for the order and proper intervals on @{typ "'a set"}›
definition length_last_fusion :: "('a, 's) generator ⇒ 's ⇒ nat × 'a"
where "length_last_fusion g s = length_last (list.unfoldr g s)"
lemma length_last_fusion_code [code]:
"length_last_fusion g s =
(if list.has_next g s then
let (x, s') = list.next g s
in fold_fusion g (λx (n, _). (n + 1, x)) s' (1, x)
else (0, undefined))"
unfolding length_last_fusion_def
by(subst list.unfoldr.simps)(simp add: length_last_Nil length_last_Cons_code fold_fusion_def split_beta)
declare length_last_fusion_def [symmetric, code_unfold]
context proper_intrvl begin
definition set_less_eq_aux_Compl_fusion :: "('a, 's1) generator ⇒ ('a, 's2) generator ⇒ 'a option ⇒ 's1 ⇒ 's2 ⇒ bool"
where
"set_less_eq_aux_Compl_fusion g1 g2 ao s1 s2 =
set_less_eq_aux_Compl ao (list.unfoldr g1 s1) (list.unfoldr g2 s2)"
definition Compl_set_less_eq_aux_fusion :: "('a, 's1) generator ⇒ ('a, 's2) generator ⇒ 'a option ⇒ 's1 ⇒ 's2 ⇒ bool"
where
"Compl_set_less_eq_aux_fusion g1 g2 ao s1 s2 =
Compl_set_less_eq_aux ao (list.unfoldr g1 s1) (list.unfoldr g2 s2)"
definition set_less_aux_Compl_fusion :: "('a, 's1) generator ⇒ ('a, 's2) generator ⇒ 'a option ⇒ 's1 ⇒ 's2 ⇒ bool"
where
"set_less_aux_Compl_fusion g1 g2 ao s1 s2 =
set_less_aux_Compl ao (list.unfoldr g1 s1) (list.unfoldr g2 s2)"
definition Compl_set_less_aux_fusion :: "('a, 's1) generator ⇒ ('a, 's2) generator ⇒ 'a option ⇒ 's1 ⇒ 's2 ⇒ bool"
where
"Compl_set_less_aux_fusion g1 g2 ao s1 s2 =
Compl_set_less_aux ao (list.unfoldr g1 s1) (list.unfoldr g2 s2)"
definition exhaustive_above_fusion :: "('a, 's) generator ⇒ 'a ⇒ 's ⇒ bool"
where "exhaustive_above_fusion g a s = exhaustive_above a (list.unfoldr g s)"
definition exhaustive_fusion :: "('a, 's) generator ⇒ 's ⇒ bool"
where "exhaustive_fusion g s = exhaustive (list.unfoldr g s)"
definition proper_interval_set_aux_fusion :: "('a, 's1) generator ⇒ ('a, 's2) generator ⇒ 's1 ⇒ 's2 ⇒ bool"
where
"proper_interval_set_aux_fusion g1 g2 s1 s2 =
proper_interval_set_aux (list.unfoldr g1 s1) (list.unfoldr g2 s2)"
definition proper_interval_set_Compl_aux_fusion ::
"('a, 's1) generator ⇒ ('a, 's2) generator ⇒ 'a option ⇒ nat ⇒ 's1 ⇒ 's2 ⇒ bool"
where
"proper_interval_set_Compl_aux_fusion g1 g2 ao n s1 s2 =
proper_interval_set_Compl_aux ao n (list.unfoldr g1 s1) (list.unfoldr g2 s2)"
definition proper_interval_Compl_set_aux_fusion ::
"('a, 's1) generator ⇒ ('a, 's2) generator ⇒ 'a option ⇒ 's1 ⇒ 's2 ⇒ bool"
where
"proper_interval_Compl_set_aux_fusion g1 g2 ao s1 s2 =
proper_interval_Compl_set_aux ao (list.unfoldr g1 s1) (list.unfoldr g2 s2)"
lemma set_less_eq_aux_Compl_fusion_code:
"set_less_eq_aux_Compl_fusion g1 g2 ao s1 s2 ⟷
(list.has_next g1 s1 ⟶ list.has_next g2 s2 ⟶
(let (x, s1') = list.next g1 s1;
(y, s2') = list.next g2 s2
in if x < y then proper_interval ao (Some x) ∨ set_less_eq_aux_Compl_fusion g1 g2 (Some x) s1' s2
else if y < x then proper_interval ao (Some y) ∨ set_less_eq_aux_Compl_fusion g1 g2 (Some y) s1 s2'
else proper_interval ao (Some y)))"
unfolding set_less_eq_aux_Compl_fusion_def
by(subst (1 2 4 5) list.unfoldr.simps)(simp add: split_beta)
lemma Compl_set_less_eq_aux_fusion_code:
"Compl_set_less_eq_aux_fusion g1 g2 ao s1 s2 ⟷
(if list.has_next g1 s1 then
let (x, s1') = list.next g1 s1
in if list.has_next g2 s2 then
let (y, s2') = list.next g2 s2
in if x < y then ¬ proper_interval ao (Some x) ∧ Compl_set_less_eq_aux_fusion g1 g2 (Some x) s1' s2
else if y < x then ¬ proper_interval ao (Some y) ∧ Compl_set_less_eq_aux_fusion g1 g2 (Some y) s1 s2'
else ¬ proper_interval ao (Some y)
else ¬ proper_interval ao (Some x) ∧ Compl_set_less_eq_aux_fusion g1 g2 (Some x) s1' s2
else if list.has_next g2 s2 then
let (y, s2') = list.next g2 s2
in ¬ proper_interval ao (Some y) ∧ Compl_set_less_eq_aux_fusion g1 g2 (Some y) s1 s2'
else ¬ proper_interval ao None)"
unfolding Compl_set_less_eq_aux_fusion_def
by(subst (1 2 4 5 8 9) list.unfoldr.simps)(simp add: split_beta)
lemma set_less_aux_Compl_fusion_code:
"set_less_aux_Compl_fusion g1 g2 ao s1 s2 ⟷
(if list.has_next g1 s1 then
let (x, s1') = list.next g1 s1
in if list.has_next g2 s2 then
let (y, s2') = list.next g2 s2
in if x < y then proper_interval ao (Some x) ∨ set_less_aux_Compl_fusion g1 g2 (Some x) s1' s2
else if y < x then proper_interval ao (Some y) ∨ set_less_aux_Compl_fusion g1 g2 (Some y) s1 s2'
else proper_interval ao (Some y)
else proper_interval ao (Some x) ∨ set_less_aux_Compl_fusion g1 g2 (Some x) s1' s2
else if list.has_next g2 s2 then
let (y, s2') = list.next g2 s2
in proper_interval ao (Some y) ∨ set_less_aux_Compl_fusion g1 g2 (Some y) s1 s2'
else proper_interval ao None)"
unfolding set_less_aux_Compl_fusion_def
by(subst (1 2 4 5 8 9) list.unfoldr.simps)(simp add: split_beta)
lemma Compl_set_less_aux_fusion_code:
"Compl_set_less_aux_fusion g1 g2 ao s1 s2 ⟷
list.has_next g1 s1 ∧ list.has_next g2 s2 ∧
(let (x, s1') = list.next g1 s1;
(y, s2') = list.next g2 s2
in if x < y then ¬ proper_interval ao (Some x) ∧ Compl_set_less_aux_fusion g1 g2 (Some x) s1' s2
else if y < x then ¬ proper_interval ao (Some y) ∧ Compl_set_less_aux_fusion g1 g2 (Some y) s1 s2'
else ¬ proper_interval ao (Some y))"
unfolding Compl_set_less_aux_fusion_def
by(subst (1 2 4 5) list.unfoldr.simps)(simp add: split_beta)
lemma exhaustive_above_fusion_code:
"exhaustive_above_fusion g y s ⟷
(if list.has_next g s then
let (x, s') = list.next g s
in ¬ proper_interval (Some y) (Some x) ∧ exhaustive_above_fusion g x s'
else ¬ proper_interval (Some y) None)"
unfolding exhaustive_above_fusion_def
by(subst list.unfoldr.simps)(simp add: split_beta)
lemma exhaustive_fusion_code:
"exhaustive_fusion g s =
(list.has_next g s ∧
(let (x, s') = list.next g s
in ¬ proper_interval None (Some x) ∧ exhaustive_above_fusion g x s'))"
unfolding exhaustive_fusion_def exhaustive_above_fusion_def
by(subst (1) list.unfoldr.simps)(simp add: split_beta)
lemma proper_interval_set_aux_fusion_code:
"proper_interval_set_aux_fusion g1 g2 s1 s2 ⟷
list.has_next g2 s2 ∧
(let (y, s2') = list.next g2 s2
in if list.has_next g1 s1 then
let (x, s1') = list.next g1 s1
in if x < y then False
else if y < x then proper_interval (Some y) (Some x) ∨ list.has_next g2 s2' ∨ ¬ exhaustive_above_fusion g1 x s1'
else proper_interval_set_aux_fusion g1 g2 s1' s2'
else list.has_next g2 s2' ∨ proper_interval (Some y) None)"
unfolding proper_interval_set_aux_fusion_def exhaustive_above_fusion_def
by(subst (1 2) list.unfoldr.simps)(simp add: split_beta)
lemma proper_interval_set_Compl_aux_fusion_code:
"proper_interval_set_Compl_aux_fusion g1 g2 ao n s1 s2 ⟷
(if list.has_next g1 s1 then
let (x, s1') = list.next g1 s1
in if list.has_next g2 s2 then
let (y, s2') = list.next g2 s2
in if x < y then
proper_interval ao (Some x) ∨
proper_interval_set_Compl_aux_fusion g1 g2 (Some x) (n + 1) s1' s2
else if y < x then
proper_interval ao (Some y) ∨
proper_interval_set_Compl_aux_fusion g1 g2 (Some y) (n + 1) s1 s2'
else
proper_interval ao (Some x) ∧
(let m = CARD('a) - n
in m - length_fusion g2 s2' ≠ 2 ∨ m - length_fusion g1 s1' ≠ 2)
else
let m = CARD('a) - n; (len_x, x') = length_last_fusion g1 s1
in m ≠ len_x ∧ (m = len_x + 1 ⟶ ¬ proper_interval (Some x') None)
else if list.has_next g2 s2 then
let (y, s2') = list.next g2 s2;
m = CARD('a) - n;
(len_y, y') = length_last_fusion g2 s2
in m ≠ len_y ∧ (m = len_y + 1 ⟶ ¬ proper_interval (Some y') None)
else CARD('a) > n + 1)"
unfolding proper_interval_set_Compl_aux_fusion_def length_last_fusion_def length_fusion_def
by(subst (1 2 4 5 9 10) list.unfoldr.simps)(simp add: split_beta)
lemma proper_interval_Compl_set_aux_fusion_code:
"proper_interval_Compl_set_aux_fusion g1 g2 ao s1 s2 ⟷
list.has_next g1 s1 ∧ list.has_next g2 s2 ∧
(let (x, s1') = list.next g1 s1;
(y, s2') = list.next g2 s2
in if x < y then
¬ proper_interval ao (Some x) ∧ proper_interval_Compl_set_aux_fusion g1 g2 (Some x) s1' s2
else if y < x then
¬ proper_interval ao (Some y) ∧ proper_interval_Compl_set_aux_fusion g1 g2 (Some y) s1 s2'
else ¬ proper_interval ao (Some x) ∧ (list.has_next g2 s2' ∨ list.has_next g1 s1'))"
unfolding proper_interval_Compl_set_aux_fusion_def
by(subst (1 2 4 5) list.unfoldr.simps)(auto simp add: split_beta)
end
lemmas [code] =
set_less_eq_aux_Compl_fusion_code proper_intrvl.set_less_eq_aux_Compl_fusion_code
Compl_set_less_eq_aux_fusion_code proper_intrvl.Compl_set_less_eq_aux_fusion_code
set_less_aux_Compl_fusion_code proper_intrvl.set_less_aux_Compl_fusion_code
Compl_set_less_aux_fusion_code proper_intrvl.Compl_set_less_aux_fusion_code
exhaustive_above_fusion_code proper_intrvl.exhaustive_above_fusion_code
exhaustive_fusion_code proper_intrvl.exhaustive_fusion_code
proper_interval_set_aux_fusion_code proper_intrvl.proper_interval_set_aux_fusion_code
proper_interval_set_Compl_aux_fusion_code proper_intrvl.proper_interval_set_Compl_aux_fusion_code
proper_interval_Compl_set_aux_fusion_code proper_intrvl.proper_interval_Compl_set_aux_fusion_code
lemmas [symmetric, code_unfold] =
set_less_eq_aux_Compl_fusion_def proper_intrvl.set_less_eq_aux_Compl_fusion_def
Compl_set_less_eq_aux_fusion_def proper_intrvl.Compl_set_less_eq_aux_fusion_def
set_less_aux_Compl_fusion_def proper_intrvl.set_less_aux_Compl_fusion_def
Compl_set_less_aux_fusion_def proper_intrvl.Compl_set_less_aux_fusion_def
exhaustive_above_fusion_def proper_intrvl.exhaustive_above_fusion_def
exhaustive_fusion_def proper_intrvl.exhaustive_fusion_def
proper_interval_set_aux_fusion_def proper_intrvl.proper_interval_set_aux_fusion_def
proper_interval_set_Compl_aux_fusion_def proper_intrvl.proper_interval_set_Compl_aux_fusion_def
proper_interval_Compl_set_aux_fusion_def proper_intrvl.proper_interval_Compl_set_aux_fusion_def
subsection ‹Drop notation›
context ord begin
no_notation set_less_aux (infix "⊏''" 50)
and set_less_eq_aux (infix "⊑''" 50)
and set_less_eq_aux' (infix "⊑''''" 50)
and set_less_eq_aux'' (infix "⊑''''''" 50)
and set_less_eq (infix "⊑" 50)
and set_less (infix "⊏" 50)
end
end