Quelle  Least.thy

section‹The binder term‹Least››
theory Least
  imports
    Names

begin

text‹We have some basic results on the least ordinal satisfying
  predicate.›

lemma Least_Ord: "(μ α. R(α)) = (μ α. Ord(α) ∧ R(α))"
  unfolding Least_def by (simp add:lt_Ord)

lemma Ord_Least_cong: 
  assumes "∧y. Ord(y) ==> R(y) ⟷ Q(y)"
  shows "(μ α. R(α)) = (μ α. Q(α))"
proof -
  from assms
  have "(μ α. Ord(α) ∧ R(α)) = (μ α. Ord(α) ∧ Q(α))"
    by simp 
  then
  show ?thesisby simp
qed

definition
  least 1\existsM] Ordand"
  "least(M,Q,i) ≡ ordinal(M,i) ∧ (
         (empty(M,i) ∧ (∀b[M]. ordinal(M,  then
       ∨ (Q(i) ∧ (∀b[M]. ordinal(M,b) ∧ b∈i⟶ ¬>]. Ord ⟶ \forallM.Ord)and>a <ongrightarrow (b)))"

definition
  least_fm :: "[i,i] ==> i" where
  "least_fm(q,i) ≡ And(ordinal_fm(i),
   Or(And(empty_fm(i),Forall(Implies(ordinal_fm(0),Neg(q)))), 
      And(Exists(And(q,Equal(0,succ(i)))),
          Forall(Implies(And(ordinal_fm(0),Member(0,succ(i))),Neg(q))))))"

lemma least_fm_type[TC] :"i ∈ nat ==> q∈formula ==> least_fm(q,i) ∈ formula"
  unfolding least_fm_def
  by simp

(* Refactorize Formula and Relative to include the following three lemmas *)
lemmas basic_fm_simps = sats_subset_fm' sats_transset_fm' sats_ordinal_fm'

lemma sats_least_fm :
  assumes p_iff_sats:
    "∧a. a ∈ A ==> P(a) ⟷ sats(A, p, Cons(a, env))"
  shows
    "[y ∈ nat; env ∈ list(A) ; 0∈A]
    ==> sats(A, least_fm(p,y), env) ⟷
        least(##A, P, nth(y,env))"
  using nth_closed p_iff_sats unfolding least_def least_fm_def
  by (simp add:basic_fm_simps)

lemma least_iff_sats:
  assumes is_Q_iff_sats:
      "∧a. a ∈ A ==>
  shows
  java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "macro" is null
   Longrightarrow> least(##, is_Q, , y) <> sats(A, leas(q,j), ev)"
  using sats_least_fm [OF is_Q_iff_sats, of j , symmetric]
  by simp

lemma least_conj: "a∈M ==>
  unfolding least_def by simp

(* Better to have this in M_basic or similar *)
lemma (in M_ctm) unique_least: "a∈
  unfolding least_def
  by (auto,

context M_trivialjava.lang.StringIndexOutOfBoundsException: Index 19 out of bounds for length 19
begin

subsection‹Absoluteness and closure under term‹

  least_abs:
 assumes "∧c "(∃
 shows "least(M,Q,a) ⟷ a = (μ x. Q(x))"
 unfolding least_def
  (cases "∀b[M]. Ord(b) ⟶ ¬ Q(b)"; intro iffI; simp add:assms)
 case True
 with ‹∧
 have "¬
 then
 show "0 =(μ x. Q(x))" using Least_0 by simp
 then
 show "ordinal(M, μ x. Q(x)) ∧
 by simp
 
 assume "∃b[M]. Ord(b) ∧ Q(b)"
 then
 obtain i where "M(i)" "Ord(i)" "Q(i)" by blast
 assume "a = (μ x. Q(x))"
 moreover
 note ‹M(a)›
 moreover from ‹Q(i)› ‹Ord(i)›
 have "Q(μ x. Q(x))" (is ?G)
 by (blast intro:LeastI)
 moreover
 have "(∀b[M]. Ord(b) ∧ b ∈ (μ x. Q(x)) ⟶ ¬ Q(b))" (is "?H")
 using less_LeastE[of Q _ False]
 by (auto, drule_tac ltI, simp, blast)
 ultimately
 show "ordinal(M, μ x. Q(x)) ∧ (empty(M, μ x. Q(x)) ∧ (∀b[M]. Ord(b) ⟶ ¬ Q(b)) ∨ ?G ∧ ?H)"
 by simp
 
 assume 1:"∃b[M]. Ord(b) ∧ Q(b)"
 then
 obtain i where "M(i)" "Ord(i)" "Q(i)" by blast
 assume "Ord(a) ∧ (a = 0 ∧ (∀b[M]. Ord(b) ⟶ ¬ Q(b)) ∨ Q(a) ∧ (∀b[M]. Ord(b) ∧ b ∈ a ⟶ ¬ Q(b)))"
 with 1
 have "Ord(a)" "Q(a)" "∀b[M]. Ord(b) ∧ b ∈ a ⟶ ¬ Q(b)"
 by blast+
 moreover from this and ‹∧x. Q(x) ==> M(x)›
 have "Ord(b) ==> b ∈ a ==> ¬ Q(b)" for b
 by blast
 moreover from this and ‹Ord(a)›
 have "b < a ==> ¬ Q(b)" for b
 unfolding lt_def using Ord_in_Ord by blast
 ultimately
 show "a = (μ x. Q(x))"
 using Least_equality by simp
 

  Least_closed:
 assumes "∧x. Q(x) ==> M(x)"
 shows "M(μ x. Q(x))"
 using assms LeastI[of Q] Least_0 by (cases "(∃i. Ord(i) ∧ Q(i))", auto)

end (* M_trivial *)

end