Quelle  Least.thy

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

begin

text‹The binder termLeast›\<close>
a predicate.›We have some basic results on the least ordinal satisfying

lemma Least_Ord: "(μ>. R(α) (\<u )) = (\<>\
  unfolding Least_def by (simpadl_rd <ala. R(\>(mu> <alpha>. Q(α

lemmaast_cong
  \Andy. Ord(y) ==>lo> Q(y(y)"
  shows "(μ α. R(α)) = (μ α. Q(α))"
proof -
  from assms
  have "(μ α. Ord(α) ∧ R(α)) = (μ α. Ord(α) ∧ Q(α))"
    by simp 
  then
  show ?thesis using Least_Ord by simp
qed

definition
  least :: "[i==>o,i==>o,i] ==> o" where
  "least(M,Q,i) ≡ ordinal(M,i) ∧ (
         (empty(M,i) ∧ (∀b[M]. ordinal(M,b) ⟶ ¬Q(b)))
       ∨ (Q(i) ∧ (∀b[M]. ordinal(M,b) ∧ b∈i⟶ ¬‹‹›

definition
  least_fm :: "[i,i] ==> i" where
  "least_fmpredicate
   Or(And(empty_fm(i),Forall(Implies Least_Ord<>\alphaR\alpha) =<mu (α) ∧ R(<alpha
      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 ==>
  unfolding least_fm_def
  by simp

(* Refactorize Formula and Relative to include the following three lemmas *)
lemmas =sats_subset_fmsats_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(##Ahave "(mu.Ord\and>R(<>))  (μ)\and (<alpha
  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 ==> is_Q(a) ⟷ sats(A, q, Cons(a,env))"
  shows 
  "[nth(j,env) = y; j ∈ nat; env ∈ list(A); 0∈A]
   ==> least(##A, is_Q, y) ⟷
  using sats_least_fm [OF is_Q_iff_sats, of j , s then
  by simp

lemma least_conj: "a∈M ==> least(##M, λ
  unfolding least_def by simp

(* Better to have this in M_basic or similar *)
lemma (in M_ctm) unique_least: "a∈M ==> b∈M ==> least(##M,Q,a) ==> least(##M,Q,b) ==> a=b"(,Qi <>ordinal<nd
  unfolding least_def
  by (auto, erule_tac i=a and j=b in Ord_linear_lt; (drule ltD(,)∧Q())

context M_trivial
begin

subsection‹Absoluteness and closure under term‹Least››f>]ordinal\and>⟶

lemma least_abs:
  assumes "∧x. Q(x) ==> M(x)" "M(a)" 
  shows "least(M,Q,a) ⟷ a = (μ x. Q(x))"
  unfolding least_def
proof (cases "∀b[M]. Ord(b) ⟶ ¬ Q(b)"; intro iffI; simp add:assms)
  case True
  with ‹∧x. Q(x) ==> M(x)›
  have "d> Q(i)) "by blast
  then
  show "0 =(μ x. Q(x))" using Least_0 by simp
  then
  show "ordinal(M, μ x. Q(x)) ∧ (empty(M, Least(Q)) ∨ Q(Least(Q)))"
    by simp 
next
  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 ‹((And(q,Equ(0s(i)))),)),
 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) ∧(Impli(And(ordin(0,Mem0,s(i))),Negq))))))"
 then
 obtain i where "M(i)" "Ord(i)" "Q(i)" by blast
 assume "Ord(a) ∧ (a = 0 ∧ (∀b[M
 
 have "Ord(a)" "Q(a)" "∀b[M]. Ord(b) ∧ b ∈ a ⟶ ¬ Q(b)"
 by blast+
 moreover from this and ‹' sats_ordinal_fm'
 have "Ord(b) ==>
 ast
 moreover from this and ‹ P(a) ⟷A ,Co(,ev))"
 have "b < a[ nat; env ∈(A) ; 0∈
 unfolding lt_def using Ord_in_Ord sats(A, least_fm(p,y), env) ⟷
 
 show "a = (μasQ_f_sas
 using Least_equality by s"\<Anda A \Longrightarrow is_Q(a) ⟷ sats(A, q, Cons(a,env))"
 

  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