# Theory Set_by_Ordered

theory Set_by_Ordered
imports List_Ins_Del
```(* Author: Tobias Nipkow *)

section {* Implementing Ordered Sets *}

theory Set_by_Ordered
imports List_Ins_Del
begin

locale Set =
fixes empty :: "'s"
fixes insert :: "'a ⇒ 's ⇒ 's"
fixes delete :: "'a ⇒ 's ⇒ 's"
fixes isin :: "'s ⇒ 'a ⇒ bool"
fixes set :: "'s ⇒ 'a set"
fixes invar :: "'s ⇒ bool"
assumes set_empty:    "set empty = {}"
assumes set_isin:     "invar s ⟹ isin s x = (x ∈ set s)"
assumes set_insert:   "invar s ⟹ set(insert x s) = Set.insert x (set s)"
assumes set_delete:   "invar s ⟹ set(delete x s) = set s - {x}"
assumes invar_empty:  "invar empty"
assumes invar_insert: "invar s ⟹ invar(insert x s)"
assumes invar_delete: "invar s ⟹ invar(delete x s)"

locale Set_by_Ordered =
fixes empty :: "'t"
fixes insert :: "'a::linorder ⇒ 't ⇒ 't"
fixes delete :: "'a ⇒ 't ⇒ 't"
fixes isin :: "'t ⇒ 'a ⇒ bool"
fixes inorder :: "'t ⇒ 'a list"
fixes inv :: "'t ⇒ bool"
assumes empty: "inorder empty = []"
assumes isin: "inv t ∧ sorted(inorder t) ⟹
isin t x = (x ∈ elems (inorder t))"
assumes insert: "inv t ∧ sorted(inorder t) ⟹
inorder(insert x t) = ins_list x (inorder t)"
assumes delete: "inv t ∧ sorted(inorder t) ⟹
inorder(delete x t) = del_list x (inorder t)"
assumes inv_empty:  "inv empty"
assumes inv_insert: "inv t ∧ sorted(inorder t) ⟹ inv(insert x t)"
assumes inv_delete: "inv t ∧ sorted(inorder t) ⟹ inv(delete x t)"
begin

sublocale Set
empty insert delete isin "elems o inorder" "λt. inv t ∧ sorted(inorder t)"
proof(standard, goal_cases)
case 1 show ?case by (auto simp: empty)
next
case 2 thus ?case by(simp add: isin)
next
case 3 thus ?case by(simp add: insert set_ins_list)
next
case (4 s x) thus ?case
using delete[OF 4, of x] by (auto simp: distinct_if_sorted elems_del_list_eq)
next
case 5 thus ?case by(simp add: empty inv_empty)
next
case 6 thus ?case by(simp add: insert inv_insert sorted_ins_list)
next
case 7 thus ?case by (auto simp: delete inv_delete sorted_del_list)
qed

end

end
```