author paulson Tue, 13 Aug 2002 17:42:34 +0200 changeset 13496 6f0c57def6d5 parent 13495 af27202d6d1c child 13497 defb74f6a5bc
In ZF/Constructible, moved many results from Satisfies_absolute, etc., to the new theory Internalize.thy
 src/ZF/Constructible/Internalize.thy file | annotate | diff | comparison | revisions src/ZF/Constructible/L_axioms.thy file | annotate | diff | comparison | revisions src/ZF/Constructible/Rec_Separation.thy file | annotate | diff | comparison | revisions src/ZF/Constructible/Satisfies_absolute.thy file | annotate | diff | comparison | revisions src/ZF/IsaMakefile file | annotate | diff | comparison | revisions
```--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/ZF/Constructible/Internalize.thy	Tue Aug 13 17:42:34 2002 +0200
@@ -0,0 +1,559 @@
+theory Internalize = L_axioms + Datatype_absolute:
+
+subsection{*Internalized Forms of Data Structuring Operators*}
+
+subsubsection{*The Formula @{term is_Inl}, Internalized*}
+
+(*  is_Inl(M,a,z) == \<exists>zero[M]. empty(M,zero) & pair(M,zero,a,z) *)
+constdefs Inl_fm :: "[i,i]=>i"
+    "Inl_fm(a,z) == Exists(And(empty_fm(0), pair_fm(0,succ(a),succ(z))))"
+
+lemma Inl_type [TC]:
+     "[| x \<in> nat; z \<in> nat |] ==> Inl_fm(x,z) \<in> formula"
+
+lemma sats_Inl_fm [simp]:
+   "[| x \<in> nat; z \<in> nat; env \<in> list(A)|]
+    ==> sats(A, Inl_fm(x,z), env) <-> is_Inl(**A, nth(x,env), nth(z,env))"
+
+lemma Inl_iff_sats:
+      "[| nth(i,env) = x; nth(k,env) = z;
+          i \<in> nat; k \<in> nat; env \<in> list(A)|]
+       ==> is_Inl(**A, x, z) <-> sats(A, Inl_fm(i,k), env)"
+by simp
+
+theorem Inl_reflection:
+     "REFLECTS[\<lambda>x. is_Inl(L,f(x),h(x)),
+               \<lambda>i x. is_Inl(**Lset(i),f(x),h(x))]"
+apply (simp only: is_Inl_def setclass_simps)
+apply (intro FOL_reflections function_reflections)
+done
+
+
+subsubsection{*The Formula @{term is_Inr}, Internalized*}
+
+(*  is_Inr(M,a,z) == \<exists>n1[M]. number1(M,n1) & pair(M,n1,a,z) *)
+constdefs Inr_fm :: "[i,i]=>i"
+    "Inr_fm(a,z) == Exists(And(number1_fm(0), pair_fm(0,succ(a),succ(z))))"
+
+lemma Inr_type [TC]:
+     "[| x \<in> nat; z \<in> nat |] ==> Inr_fm(x,z) \<in> formula"
+
+lemma sats_Inr_fm [simp]:
+   "[| x \<in> nat; z \<in> nat; env \<in> list(A)|]
+    ==> sats(A, Inr_fm(x,z), env) <-> is_Inr(**A, nth(x,env), nth(z,env))"
+
+lemma Inr_iff_sats:
+      "[| nth(i,env) = x; nth(k,env) = z;
+          i \<in> nat; k \<in> nat; env \<in> list(A)|]
+       ==> is_Inr(**A, x, z) <-> sats(A, Inr_fm(i,k), env)"
+by simp
+
+theorem Inr_reflection:
+     "REFLECTS[\<lambda>x. is_Inr(L,f(x),h(x)),
+               \<lambda>i x. is_Inr(**Lset(i),f(x),h(x))]"
+apply (simp only: is_Inr_def setclass_simps)
+apply (intro FOL_reflections function_reflections)
+done
+
+
+subsubsection{*The Formula @{term is_Nil}, Internalized*}
+
+(* is_Nil(M,xs) == \<exists>zero[M]. empty(M,zero) & is_Inl(M,zero,xs) *)
+
+constdefs Nil_fm :: "i=>i"
+    "Nil_fm(x) == Exists(And(empty_fm(0), Inl_fm(0,succ(x))))"
+
+lemma Nil_type [TC]: "x \<in> nat ==> Nil_fm(x) \<in> formula"
+
+lemma sats_Nil_fm [simp]:
+   "[| x \<in> nat; env \<in> list(A)|]
+    ==> sats(A, Nil_fm(x), env) <-> is_Nil(**A, nth(x,env))"
+
+lemma Nil_iff_sats:
+      "[| nth(i,env) = x; i \<in> nat; env \<in> list(A)|]
+       ==> is_Nil(**A, x) <-> sats(A, Nil_fm(i), env)"
+by simp
+
+theorem Nil_reflection:
+     "REFLECTS[\<lambda>x. is_Nil(L,f(x)),
+               \<lambda>i x. is_Nil(**Lset(i),f(x))]"
+apply (simp only: is_Nil_def setclass_simps)
+apply (intro FOL_reflections function_reflections Inl_reflection)
+done
+
+
+subsubsection{*The Formula @{term is_Cons}, Internalized*}
+
+
+(*  "is_Cons(M,a,l,Z) == \<exists>p[M]. pair(M,a,l,p) & is_Inr(M,p,Z)" *)
+constdefs Cons_fm :: "[i,i,i]=>i"
+    "Cons_fm(a,l,Z) ==
+       Exists(And(pair_fm(succ(a),succ(l),0), Inr_fm(0,succ(Z))))"
+
+lemma Cons_type [TC]:
+     "[| x \<in> nat; y \<in> nat; z \<in> nat |] ==> Cons_fm(x,y,z) \<in> formula"
+
+lemma sats_Cons_fm [simp]:
+   "[| x \<in> nat; y \<in> nat; z \<in> nat; env \<in> list(A)|]
+    ==> sats(A, Cons_fm(x,y,z), env) <->
+       is_Cons(**A, nth(x,env), nth(y,env), nth(z,env))"
+
+lemma Cons_iff_sats:
+      "[| nth(i,env) = x; nth(j,env) = y; nth(k,env) = z;
+          i \<in> nat; j \<in> nat; k \<in> nat; env \<in> list(A)|]
+       ==>is_Cons(**A, x, y, z) <-> sats(A, Cons_fm(i,j,k), env)"
+by simp
+
+theorem Cons_reflection:
+     "REFLECTS[\<lambda>x. is_Cons(L,f(x),g(x),h(x)),
+               \<lambda>i x. is_Cons(**Lset(i),f(x),g(x),h(x))]"
+apply (simp only: is_Cons_def setclass_simps)
+apply (intro FOL_reflections pair_reflection Inr_reflection)
+done
+
+subsubsection{*The Formula @{term is_quasilist}, Internalized*}
+
+(* is_quasilist(M,xs) == is_Nil(M,z) | (\<exists>x[M]. \<exists>l[M]. is_Cons(M,x,l,z))" *)
+
+constdefs quasilist_fm :: "i=>i"
+    "quasilist_fm(x) ==
+       Or(Nil_fm(x), Exists(Exists(Cons_fm(1,0,succ(succ(x))))))"
+
+lemma quasilist_type [TC]: "x \<in> nat ==> quasilist_fm(x) \<in> formula"
+
+lemma sats_quasilist_fm [simp]:
+   "[| x \<in> nat; env \<in> list(A)|]
+    ==> sats(A, quasilist_fm(x), env) <-> is_quasilist(**A, nth(x,env))"
+
+lemma quasilist_iff_sats:
+      "[| nth(i,env) = x; i \<in> nat; env \<in> list(A)|]
+       ==> is_quasilist(**A, x) <-> sats(A, quasilist_fm(i), env)"
+by simp
+
+theorem quasilist_reflection:
+     "REFLECTS[\<lambda>x. is_quasilist(L,f(x)),
+               \<lambda>i x. is_quasilist(**Lset(i),f(x))]"
+apply (simp only: is_quasilist_def setclass_simps)
+apply (intro FOL_reflections Nil_reflection Cons_reflection)
+done
+
+
+subsection{*Absoluteness for the Function @{term nth}*}
+
+
+subsubsection{*The Formula @{term is_hd}, Internalized*}
+
+(*   "is_hd(M,xs,H) ==
+       (is_Nil(M,xs) --> empty(M,H)) &
+       (\<forall>x[M]. \<forall>l[M]. ~ is_Cons(M,x,l,xs) | H=x) &
+       (is_quasilist(M,xs) | empty(M,H))" *)
+constdefs hd_fm :: "[i,i]=>i"
+    "hd_fm(xs,H) ==
+       And(Implies(Nil_fm(xs), empty_fm(H)),
+           And(Forall(Forall(Or(Neg(Cons_fm(1,0,xs#+2)), Equal(H#+2,1)))),
+               Or(quasilist_fm(xs), empty_fm(H))))"
+
+lemma hd_type [TC]:
+     "[| x \<in> nat; y \<in> nat |] ==> hd_fm(x,y) \<in> formula"
+
+lemma sats_hd_fm [simp]:
+   "[| x \<in> nat; y \<in> nat; env \<in> list(A)|]
+    ==> sats(A, hd_fm(x,y), env) <-> is_hd(**A, nth(x,env), nth(y,env))"
+
+lemma hd_iff_sats:
+      "[| nth(i,env) = x; nth(j,env) = y;
+          i \<in> nat; j \<in> nat; env \<in> list(A)|]
+       ==> is_hd(**A, x, y) <-> sats(A, hd_fm(i,j), env)"
+by simp
+
+theorem hd_reflection:
+     "REFLECTS[\<lambda>x. is_hd(L,f(x),g(x)),
+               \<lambda>i x. is_hd(**Lset(i),f(x),g(x))]"
+apply (simp only: is_hd_def setclass_simps)
+apply (intro FOL_reflections Nil_reflection Cons_reflection
+             quasilist_reflection empty_reflection)
+done
+
+
+subsubsection{*The Formula @{term is_tl}, Internalized*}
+
+(*     "is_tl(M,xs,T) ==
+       (is_Nil(M,xs) --> T=xs) &
+       (\<forall>x[M]. \<forall>l[M]. ~ is_Cons(M,x,l,xs) | T=l) &
+       (is_quasilist(M,xs) | empty(M,T))" *)
+constdefs tl_fm :: "[i,i]=>i"
+    "tl_fm(xs,T) ==
+       And(Implies(Nil_fm(xs), Equal(T,xs)),
+           And(Forall(Forall(Or(Neg(Cons_fm(1,0,xs#+2)), Equal(T#+2,0)))),
+               Or(quasilist_fm(xs), empty_fm(T))))"
+
+lemma tl_type [TC]:
+     "[| x \<in> nat; y \<in> nat |] ==> tl_fm(x,y) \<in> formula"
+
+lemma sats_tl_fm [simp]:
+   "[| x \<in> nat; y \<in> nat; env \<in> list(A)|]
+    ==> sats(A, tl_fm(x,y), env) <-> is_tl(**A, nth(x,env), nth(y,env))"
+
+lemma tl_iff_sats:
+      "[| nth(i,env) = x; nth(j,env) = y;
+          i \<in> nat; j \<in> nat; env \<in> list(A)|]
+       ==> is_tl(**A, x, y) <-> sats(A, tl_fm(i,j), env)"
+by simp
+
+theorem tl_reflection:
+     "REFLECTS[\<lambda>x. is_tl(L,f(x),g(x)),
+               \<lambda>i x. is_tl(**Lset(i),f(x),g(x))]"
+apply (simp only: is_tl_def setclass_simps)
+apply (intro FOL_reflections Nil_reflection Cons_reflection
+             quasilist_reflection empty_reflection)
+done
+
+
+subsubsection{*The Operator @{term is_bool_of_o}*}
+
+(*   is_bool_of_o :: "[i=>o, o, i] => o"
+   "is_bool_of_o(M,P,z) == (P & number1(M,z)) | (~P & empty(M,z))" *)
+
+text{*The formula @{term p} has no free variables.*}
+constdefs bool_of_o_fm :: "[i, i]=>i"
+ "bool_of_o_fm(p,z) ==
+    Or(And(p,number1_fm(z)),
+       And(Neg(p),empty_fm(z)))"
+
+lemma is_bool_of_o_type [TC]:
+     "[| p \<in> formula; z \<in> nat |] ==> bool_of_o_fm(p,z) \<in> formula"
+
+lemma sats_bool_of_o_fm:
+  assumes p_iff_sats: "P <-> sats(A, p, env)"
+  shows
+      "[|z \<in> nat; env \<in> list(A)|]
+       ==> sats(A, bool_of_o_fm(p,z), env) <->
+           is_bool_of_o(**A, P, nth(z,env))"
+by (simp add: bool_of_o_fm_def is_bool_of_o_def p_iff_sats [THEN iff_sym])
+
+lemma is_bool_of_o_iff_sats:
+  "[| P <-> sats(A, p, env); nth(k,env) = z; k \<in> nat; env \<in> list(A)|]
+   ==> is_bool_of_o(**A, P, z) <-> sats(A, bool_of_o_fm(p,k), env)"
+
+theorem bool_of_o_reflection:
+     "REFLECTS [P(L), \<lambda>i. P(**Lset(i))] ==>
+      REFLECTS[\<lambda>x. is_bool_of_o(L, P(L,x), f(x)),
+               \<lambda>i x. is_bool_of_o(**Lset(i), P(**Lset(i),x), f(x))]"
+apply (simp (no_asm) only: is_bool_of_o_def setclass_simps)
+apply (intro FOL_reflections function_reflections, assumption+)
+done
+
+
+subsection{*More Internalizations*}
+
+subsubsection{*The Operator @{term is_lambda}*}
+
+text{*The two arguments of @{term p} are always 1, 0. Remember that
+ @{term p} will be enclosed by three quantifiers.*}
+
+(* is_lambda :: "[i=>o, i, [i,i]=>o, i] => o"
+    "is_lambda(M, A, is_b, z) ==
+       \<forall>p[M]. p \<in> z <->
+        (\<exists>u[M]. \<exists>v[M]. u\<in>A & pair(M,u,v,p) & is_b(u,v))" *)
+constdefs lambda_fm :: "[i, i, i]=>i"
+ "lambda_fm(p,A,z) ==
+    Forall(Iff(Member(0,succ(z)),
+            Exists(Exists(And(Member(1,A#+3),
+                           And(pair_fm(1,0,2), p))))))"
+
+text{*We call @{term p} with arguments x, y by equating them with
+  the corresponding quantified variables with de Bruijn indices 1, 0.*}
+
+lemma is_lambda_type [TC]:
+     "[| p \<in> formula; x \<in> nat; y \<in> nat |]
+      ==> lambda_fm(p,x,y) \<in> formula"
+
+lemma sats_lambda_fm:
+  assumes is_b_iff_sats:
+      "!!a0 a1 a2.
+        [|a0\<in>A; a1\<in>A; a2\<in>A|]
+        ==> is_b(a1, a0) <-> sats(A, p, Cons(a0,Cons(a1,Cons(a2,env))))"
+  shows
+      "[|x \<in> nat; y \<in> nat; env \<in> list(A)|]
+       ==> sats(A, lambda_fm(p,x,y), env) <->
+           is_lambda(**A, nth(x,env), is_b, nth(y,env))"
+by (simp add: lambda_fm_def is_lambda_def is_b_iff_sats [THEN iff_sym])
+
+lemma is_lambda_iff_sats:
+  assumes is_b_iff_sats:
+      "!!a0 a1 a2.
+        [|a0\<in>A; a1\<in>A; a2\<in>A|]
+        ==> is_b(a1, a0) <-> sats(A, p, Cons(a0,Cons(a1,Cons(a2,env))))"
+  shows
+  "[|nth(i,env) = x; nth(j,env) = y;
+      i \<in> nat; j \<in> nat; env \<in> list(A)|]
+   ==> is_lambda(**A, x, is_b, y) <-> sats(A, lambda_fm(p,i,j), env)"
+by (simp add: sats_lambda_fm [OF is_b_iff_sats])
+
+theorem is_lambda_reflection:
+  assumes is_b_reflection:
+    "!!f' f g h. REFLECTS[\<lambda>x. is_b(L, f'(x), f(x), g(x)),
+                     \<lambda>i x. is_b(**Lset(i), f'(x), f(x), g(x))]"
+  shows "REFLECTS[\<lambda>x. is_lambda(L, A(x), is_b(L,x), f(x)),
+               \<lambda>i x. is_lambda(**Lset(i), A(x), is_b(**Lset(i),x), f(x))]"
+apply (simp (no_asm_use) only: is_lambda_def setclass_simps)
+apply (intro FOL_reflections is_b_reflection pair_reflection)
+done
+
+subsubsection{*The Operator @{term is_Member}, Internalized*}
+
+(*    "is_Member(M,x,y,Z) ==
+	\<exists>p[M]. \<exists>u[M]. pair(M,x,y,p) & is_Inl(M,p,u) & is_Inl(M,u,Z)" *)
+constdefs Member_fm :: "[i,i,i]=>i"
+    "Member_fm(x,y,Z) ==
+       Exists(Exists(And(pair_fm(x#+2,y#+2,1),
+                      And(Inl_fm(1,0), Inl_fm(0,Z#+2)))))"
+
+lemma is_Member_type [TC]:
+     "[| x \<in> nat; y \<in> nat; z \<in> nat |] ==> Member_fm(x,y,z) \<in> formula"
+
+lemma sats_Member_fm [simp]:
+   "[| x \<in> nat; y \<in> nat; z \<in> nat; env \<in> list(A)|]
+    ==> sats(A, Member_fm(x,y,z), env) <->
+        is_Member(**A, nth(x,env), nth(y,env), nth(z,env))"
+
+lemma Member_iff_sats:
+      "[| nth(i,env) = x; nth(j,env) = y; nth(k,env) = z;
+          i \<in> nat; j \<in> nat; k \<in> nat; env \<in> list(A)|]
+       ==> is_Member(**A, x, y, z) <-> sats(A, Member_fm(i,j,k), env)"
+
+theorem Member_reflection:
+     "REFLECTS[\<lambda>x. is_Member(L,f(x),g(x),h(x)),
+               \<lambda>i x. is_Member(**Lset(i),f(x),g(x),h(x))]"
+apply (simp only: is_Member_def setclass_simps)
+apply (intro FOL_reflections pair_reflection Inl_reflection)
+done
+
+subsubsection{*The Operator @{term is_Equal}, Internalized*}
+
+(*    "is_Equal(M,x,y,Z) ==
+	\<exists>p[M]. \<exists>u[M]. pair(M,x,y,p) & is_Inr(M,p,u) & is_Inl(M,u,Z)" *)
+constdefs Equal_fm :: "[i,i,i]=>i"
+    "Equal_fm(x,y,Z) ==
+       Exists(Exists(And(pair_fm(x#+2,y#+2,1),
+                      And(Inr_fm(1,0), Inl_fm(0,Z#+2)))))"
+
+lemma is_Equal_type [TC]:
+     "[| x \<in> nat; y \<in> nat; z \<in> nat |] ==> Equal_fm(x,y,z) \<in> formula"
+
+lemma sats_Equal_fm [simp]:
+   "[| x \<in> nat; y \<in> nat; z \<in> nat; env \<in> list(A)|]
+    ==> sats(A, Equal_fm(x,y,z), env) <->
+        is_Equal(**A, nth(x,env), nth(y,env), nth(z,env))"
+
+lemma Equal_iff_sats:
+      "[| nth(i,env) = x; nth(j,env) = y; nth(k,env) = z;
+          i \<in> nat; j \<in> nat; k \<in> nat; env \<in> list(A)|]
+       ==> is_Equal(**A, x, y, z) <-> sats(A, Equal_fm(i,j,k), env)"
+
+theorem Equal_reflection:
+     "REFLECTS[\<lambda>x. is_Equal(L,f(x),g(x),h(x)),
+               \<lambda>i x. is_Equal(**Lset(i),f(x),g(x),h(x))]"
+apply (simp only: is_Equal_def setclass_simps)
+apply (intro FOL_reflections pair_reflection Inl_reflection Inr_reflection)
+done
+
+subsubsection{*The Operator @{term is_Nand}, Internalized*}
+
+(*    "is_Nand(M,x,y,Z) ==
+	\<exists>p[M]. \<exists>u[M]. pair(M,x,y,p) & is_Inl(M,p,u) & is_Inr(M,u,Z)" *)
+constdefs Nand_fm :: "[i,i,i]=>i"
+    "Nand_fm(x,y,Z) ==
+       Exists(Exists(And(pair_fm(x#+2,y#+2,1),
+                      And(Inl_fm(1,0), Inr_fm(0,Z#+2)))))"
+
+lemma is_Nand_type [TC]:
+     "[| x \<in> nat; y \<in> nat; z \<in> nat |] ==> Nand_fm(x,y,z) \<in> formula"
+
+lemma sats_Nand_fm [simp]:
+   "[| x \<in> nat; y \<in> nat; z \<in> nat; env \<in> list(A)|]
+    ==> sats(A, Nand_fm(x,y,z), env) <->
+        is_Nand(**A, nth(x,env), nth(y,env), nth(z,env))"
+
+lemma Nand_iff_sats:
+      "[| nth(i,env) = x; nth(j,env) = y; nth(k,env) = z;
+          i \<in> nat; j \<in> nat; k \<in> nat; env \<in> list(A)|]
+       ==> is_Nand(**A, x, y, z) <-> sats(A, Nand_fm(i,j,k), env)"
+
+theorem Nand_reflection:
+     "REFLECTS[\<lambda>x. is_Nand(L,f(x),g(x),h(x)),
+               \<lambda>i x. is_Nand(**Lset(i),f(x),g(x),h(x))]"
+apply (simp only: is_Nand_def setclass_simps)
+apply (intro FOL_reflections pair_reflection Inl_reflection Inr_reflection)
+done
+
+subsubsection{*The Operator @{term is_Forall}, Internalized*}
+
+(* "is_Forall(M,p,Z) == \<exists>u[M]. is_Inr(M,p,u) & is_Inr(M,u,Z)" *)
+constdefs Forall_fm :: "[i,i]=>i"
+    "Forall_fm(x,Z) ==
+       Exists(And(Inr_fm(succ(x),0), Inr_fm(0,succ(Z))))"
+
+lemma is_Forall_type [TC]:
+     "[| x \<in> nat; y \<in> nat |] ==> Forall_fm(x,y) \<in> formula"
+
+lemma sats_Forall_fm [simp]:
+   "[| x \<in> nat; y \<in> nat; env \<in> list(A)|]
+    ==> sats(A, Forall_fm(x,y), env) <->
+        is_Forall(**A, nth(x,env), nth(y,env))"
+
+lemma Forall_iff_sats:
+      "[| nth(i,env) = x; nth(j,env) = y;
+          i \<in> nat; j \<in> nat; env \<in> list(A)|]
+       ==> is_Forall(**A, x, y) <-> sats(A, Forall_fm(i,j), env)"
+
+theorem Forall_reflection:
+     "REFLECTS[\<lambda>x. is_Forall(L,f(x),g(x)),
+               \<lambda>i x. is_Forall(**Lset(i),f(x),g(x))]"
+apply (simp only: is_Forall_def setclass_simps)
+apply (intro FOL_reflections pair_reflection Inr_reflection)
+done
+
+
+subsubsection{*The Operator @{term is_and}, Internalized*}
+
+(* is_and(M,a,b,z) == (number1(M,a)  & z=b) |
+                       (~number1(M,a) & empty(M,z)) *)
+constdefs and_fm :: "[i,i,i]=>i"
+    "and_fm(a,b,z) ==
+       Or(And(number1_fm(a), Equal(z,b)),
+          And(Neg(number1_fm(a)),empty_fm(z)))"
+
+lemma is_and_type [TC]:
+     "[| x \<in> nat; y \<in> nat; z \<in> nat |] ==> and_fm(x,y,z) \<in> formula"
+
+lemma sats_and_fm [simp]:
+   "[| x \<in> nat; y \<in> nat; z \<in> nat; env \<in> list(A)|]
+    ==> sats(A, and_fm(x,y,z), env) <->
+        is_and(**A, nth(x,env), nth(y,env), nth(z,env))"
+
+lemma is_and_iff_sats:
+      "[| nth(i,env) = x; nth(j,env) = y; nth(k,env) = z;
+          i \<in> nat; j \<in> nat; k \<in> nat; env \<in> list(A)|]
+       ==> is_and(**A, x, y, z) <-> sats(A, and_fm(i,j,k), env)"
+by simp
+
+theorem is_and_reflection:
+     "REFLECTS[\<lambda>x. is_and(L,f(x),g(x),h(x)),
+               \<lambda>i x. is_and(**Lset(i),f(x),g(x),h(x))]"
+apply (simp only: is_and_def setclass_simps)
+apply (intro FOL_reflections function_reflections)
+done
+
+
+subsubsection{*The Operator @{term is_or}, Internalized*}
+
+(* is_or(M,a,b,z) == (number1(M,a)  & number1(M,z)) |
+                     (~number1(M,a) & z=b) *)
+
+constdefs or_fm :: "[i,i,i]=>i"
+    "or_fm(a,b,z) ==
+       Or(And(number1_fm(a), number1_fm(z)),
+          And(Neg(number1_fm(a)), Equal(z,b)))"
+
+lemma is_or_type [TC]:
+     "[| x \<in> nat; y \<in> nat; z \<in> nat |] ==> or_fm(x,y,z) \<in> formula"
+
+lemma sats_or_fm [simp]:
+   "[| x \<in> nat; y \<in> nat; z \<in> nat; env \<in> list(A)|]
+    ==> sats(A, or_fm(x,y,z), env) <->
+        is_or(**A, nth(x,env), nth(y,env), nth(z,env))"
+
+lemma is_or_iff_sats:
+      "[| nth(i,env) = x; nth(j,env) = y; nth(k,env) = z;
+          i \<in> nat; j \<in> nat; k \<in> nat; env \<in> list(A)|]
+       ==> is_or(**A, x, y, z) <-> sats(A, or_fm(i,j,k), env)"
+by simp
+
+theorem is_or_reflection:
+     "REFLECTS[\<lambda>x. is_or(L,f(x),g(x),h(x)),
+               \<lambda>i x. is_or(**Lset(i),f(x),g(x),h(x))]"
+apply (simp only: is_or_def setclass_simps)
+apply (intro FOL_reflections function_reflections)
+done
+
+
+
+subsubsection{*The Operator @{term is_not}, Internalized*}
+
+(* is_not(M,a,z) == (number1(M,a)  & empty(M,z)) |
+                     (~number1(M,a) & number1(M,z)) *)
+constdefs not_fm :: "[i,i]=>i"
+    "not_fm(a,z) ==
+       Or(And(number1_fm(a), empty_fm(z)),
+          And(Neg(number1_fm(a)), number1_fm(z)))"
+
+lemma is_not_type [TC]:
+     "[| x \<in> nat; z \<in> nat |] ==> not_fm(x,z) \<in> formula"
+
+lemma sats_is_not_fm [simp]:
+   "[| x \<in> nat; z \<in> nat; env \<in> list(A)|]
+    ==> sats(A, not_fm(x,z), env) <-> is_not(**A, nth(x,env), nth(z,env))"
+
+lemma is_not_iff_sats:
+      "[| nth(i,env) = x; nth(k,env) = z;
+          i \<in> nat; k \<in> nat; env \<in> list(A)|]
+       ==> is_not(**A, x, z) <-> sats(A, not_fm(i,k), env)"
+by simp
+
+theorem is_not_reflection:
+     "REFLECTS[\<lambda>x. is_not(L,f(x),g(x)),
+               \<lambda>i x. is_not(**Lset(i),f(x),g(x))]"
+apply (simp only: is_not_def setclass_simps)
+apply (intro FOL_reflections function_reflections)
+done
+
+
+lemmas extra_reflections =
+    Inl_reflection Inr_reflection Nil_reflection Cons_reflection
+    quasilist_reflection hd_reflection tl_reflection bool_of_o_reflection
+    is_lambda_reflection Member_reflection Equal_reflection Nand_reflection
+    Forall_reflection is_and_reflection is_or_reflection is_not_reflection
+
+lemmas extra_iff_sats =
+    Inl_iff_sats Inr_iff_sats Nil_iff_sats Cons_iff_sats quasilist_iff_sats
+    hd_iff_sats tl_iff_sats is_bool_of_o_iff_sats is_lambda_iff_sats
+    Member_iff_sats Equal_iff_sats Nand_iff_sats Forall_iff_sats
+    is_and_iff_sats is_or_iff_sats is_not_iff_sats
+
+end```
```--- a/src/ZF/Constructible/L_axioms.thy	Tue Aug 13 12:16:14 2002 +0200
+++ b/src/ZF/Constructible/L_axioms.thy	Tue Aug 13 17:42:34 2002 +0200
@@ -1539,14 +1539,14 @@
typed_function_reflection composition_reflection
injection_reflection surjection_reflection
bijection_reflection restriction_reflection
-        order_isomorphism_reflection
+        order_isomorphism_reflection finite_ordinal_reflection
ordinal_reflection limit_ordinal_reflection omega_reflection

lemmas fun_plus_iff_sats =
typed_function_iff_sats composition_iff_sats
injection_iff_sats surjection_iff_sats
bijection_iff_sats restriction_iff_sats
-        order_isomorphism_iff_sats
+        order_isomorphism_iff_sats finite_ordinal_iff_sats
ordinal_iff_sats limit_ordinal_iff_sats omega_iff_sats

end```
```--- a/src/ZF/Constructible/Rec_Separation.thy	Tue Aug 13 12:16:14 2002 +0200
+++ b/src/ZF/Constructible/Rec_Separation.thy	Tue Aug 13 17:42:34 2002 +0200
@@ -2,13 +2,11 @@
ID:         \$Id\$
Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
-
-FIXME: define nth_fm and prove its "sats" theorem
*)

-theory Rec_Separation = Separation + Datatype_absolute:
+theory Rec_Separation = Separation + Internalize:

text{*This theory proves all instances needed for locales @{text
"M_trancl"}, @{text "M_wfrank"} and @{text "M_datatypes"}*}
@@ -305,13 +303,7 @@
"[| nth(i,env) = x; nth(j,env) = y; nth(k,env) = z;
i \<in> nat; j \<in> nat; k \<in> nat; env \<in> list(A)|]
==> M_is_recfun(**A, MH, x, y, z) <-> sats(A, is_recfun_fm(p,i,j,k), env)"
-apply (rule iff_sym)
-apply (rule iff_trans)
-apply (rule sats_is_recfun_fm [of A MH])
-apply (rule MH_iff_sats, simp_all)
-done
-(*FIXME: surely proof can be improved?*)
-
+by (simp add: sats_is_recfun_fm [OF MH_iff_sats])

text{*The additional variable in the premise, namely @{term f'}, is essential.
It lets @{term MH} depend upon @{term x}, which seems often necessary.
@@ -754,28 +746,27 @@
done

-
lemma iterates_MH_iff_sats:
-  "[| (!!a b c d. [| a \<in> A; b \<in> A; c \<in> A; d \<in> A|]
+  assumes is_F_iff_sats:
+      "!!a b c d. [| a \<in> A; b \<in> A; c \<in> A; d \<in> A|]
==> is_F(a,b) <->
-                  sats(A, p, Cons(b, Cons(a, Cons(c, Cons(d,env))))));
-      nth(i',env) = v; nth(i,env) = x; nth(j,env) = y; nth(k,env) = z;
+                  sats(A, p, Cons(b, Cons(a, Cons(c, Cons(d,env)))))"
+  shows
+  "[| nth(i',env) = v; nth(i,env) = x; nth(j,env) = y; nth(k,env) = z;
i' \<in> nat; i \<in> nat; j \<in> nat; k < length(env); env \<in> list(A)|]
==> iterates_MH(**A, is_F, v, x, y, z) <->
sats(A, iterates_MH_fm(p,i',i,j,k), env)"
-apply (rule iff_sym)
-apply (rule iff_trans)
-apply (rule sats_iterates_MH_fm [of A is_F], blast, simp_all)
-done
-(*FIXME: surely proof can be improved?*)
+by (simp add: sats_iterates_MH_fm [OF is_F_iff_sats])

-
+text{*The second argument of @{term p} gives it direct access to @{term x},
+  which is essential for handling free variable references.  Without this
+  argument, we cannot prove reflection for @{term list_N}.*}
theorem iterates_MH_reflection:
assumes p_reflection:
-    "!!f g h. REFLECTS[\<lambda>x. p(L, f(x), g(x)),
-                     \<lambda>i x. p(**Lset(i), f(x), g(x))]"
- shows "REFLECTS[\<lambda>x. iterates_MH(L, p(L), e(x), f(x), g(x), h(x)),
-               \<lambda>i x. iterates_MH(**Lset(i), p(**Lset(i)), e(x), f(x), g(x), h(x))]"
+    "!!f g h. REFLECTS[\<lambda>x. p(L, h(x), f(x), g(x)),
+                     \<lambda>i x. p(**Lset(i), h(x), f(x), g(x))]"
+ shows "REFLECTS[\<lambda>x. iterates_MH(L, p(L,x), e(x), f(x), g(x), h(x)),
+               \<lambda>i x. iterates_MH(**Lset(i), p(**Lset(i),x), e(x), f(x), g(x), h(x))]"
apply (simp (no_asm_use) only: iterates_MH_def)
txt{*Must be careful: simplifying with @{text setclass_simps} above would
change @{text "\<exists>gm[**Lset(i)]"} into @{text "\<exists>gm \<in> Lset(i)"}, when
@@ -1035,229 +1026,6 @@
for @{term "list(A)"}.  It was a cut-and-paste job! *}

-subsection{*Internalized Forms of Data Structuring Operators*}
-
-subsubsection{*The Formula @{term is_Inl}, Internalized*}
-
-(*  is_Inl(M,a,z) == \<exists>zero[M]. empty(M,zero) & pair(M,zero,a,z) *)
-constdefs Inl_fm :: "[i,i]=>i"
-    "Inl_fm(a,z) == Exists(And(empty_fm(0), pair_fm(0,succ(a),succ(z))))"
-
-lemma Inl_type [TC]:
-     "[| x \<in> nat; z \<in> nat |] ==> Inl_fm(x,z) \<in> formula"
-
-lemma sats_Inl_fm [simp]:
-   "[| x \<in> nat; z \<in> nat; env \<in> list(A)|]
-    ==> sats(A, Inl_fm(x,z), env) <-> is_Inl(**A, nth(x,env), nth(z,env))"
-
-lemma Inl_iff_sats:
-      "[| nth(i,env) = x; nth(k,env) = z;
-          i \<in> nat; k \<in> nat; env \<in> list(A)|]
-       ==> is_Inl(**A, x, z) <-> sats(A, Inl_fm(i,k), env)"
-by simp
-
-theorem Inl_reflection:
-     "REFLECTS[\<lambda>x. is_Inl(L,f(x),h(x)),
-               \<lambda>i x. is_Inl(**Lset(i),f(x),h(x))]"
-apply (simp only: is_Inl_def setclass_simps)
-apply (intro FOL_reflections function_reflections)
-done
-
-
-subsubsection{*The Formula @{term is_Inr}, Internalized*}
-
-(*  is_Inr(M,a,z) == \<exists>n1[M]. number1(M,n1) & pair(M,n1,a,z) *)
-constdefs Inr_fm :: "[i,i]=>i"
-    "Inr_fm(a,z) == Exists(And(number1_fm(0), pair_fm(0,succ(a),succ(z))))"
-
-lemma Inr_type [TC]:
-     "[| x \<in> nat; z \<in> nat |] ==> Inr_fm(x,z) \<in> formula"
-
-lemma sats_Inr_fm [simp]:
-   "[| x \<in> nat; z \<in> nat; env \<in> list(A)|]
-    ==> sats(A, Inr_fm(x,z), env) <-> is_Inr(**A, nth(x,env), nth(z,env))"
-
-lemma Inr_iff_sats:
-      "[| nth(i,env) = x; nth(k,env) = z;
-          i \<in> nat; k \<in> nat; env \<in> list(A)|]
-       ==> is_Inr(**A, x, z) <-> sats(A, Inr_fm(i,k), env)"
-by simp
-
-theorem Inr_reflection:
-     "REFLECTS[\<lambda>x. is_Inr(L,f(x),h(x)),
-               \<lambda>i x. is_Inr(**Lset(i),f(x),h(x))]"
-apply (simp only: is_Inr_def setclass_simps)
-apply (intro FOL_reflections function_reflections)
-done
-
-
-subsubsection{*The Formula @{term is_Nil}, Internalized*}
-
-(* is_Nil(M,xs) == \<exists>zero[M]. empty(M,zero) & is_Inl(M,zero,xs) *)
-
-constdefs Nil_fm :: "i=>i"
-    "Nil_fm(x) == Exists(And(empty_fm(0), Inl_fm(0,succ(x))))"
-
-lemma Nil_type [TC]: "x \<in> nat ==> Nil_fm(x) \<in> formula"
-
-lemma sats_Nil_fm [simp]:
-   "[| x \<in> nat; env \<in> list(A)|]
-    ==> sats(A, Nil_fm(x), env) <-> is_Nil(**A, nth(x,env))"
-
-lemma Nil_iff_sats:
-      "[| nth(i,env) = x; i \<in> nat; env \<in> list(A)|]
-       ==> is_Nil(**A, x) <-> sats(A, Nil_fm(i), env)"
-by simp
-
-theorem Nil_reflection:
-     "REFLECTS[\<lambda>x. is_Nil(L,f(x)),
-               \<lambda>i x. is_Nil(**Lset(i),f(x))]"
-apply (simp only: is_Nil_def setclass_simps)
-apply (intro FOL_reflections function_reflections Inl_reflection)
-done
-
-
-subsubsection{*The Formula @{term is_Cons}, Internalized*}
-
-
-(*  "is_Cons(M,a,l,Z) == \<exists>p[M]. pair(M,a,l,p) & is_Inr(M,p,Z)" *)
-constdefs Cons_fm :: "[i,i,i]=>i"
-    "Cons_fm(a,l,Z) ==
-       Exists(And(pair_fm(succ(a),succ(l),0), Inr_fm(0,succ(Z))))"
-
-lemma Cons_type [TC]:
-     "[| x \<in> nat; y \<in> nat; z \<in> nat |] ==> Cons_fm(x,y,z) \<in> formula"
-
-lemma sats_Cons_fm [simp]:
-   "[| x \<in> nat; y \<in> nat; z \<in> nat; env \<in> list(A)|]
-    ==> sats(A, Cons_fm(x,y,z), env) <->
-       is_Cons(**A, nth(x,env), nth(y,env), nth(z,env))"
-
-lemma Cons_iff_sats:
-      "[| nth(i,env) = x; nth(j,env) = y; nth(k,env) = z;
-          i \<in> nat; j \<in> nat; k \<in> nat; env \<in> list(A)|]
-       ==>is_Cons(**A, x, y, z) <-> sats(A, Cons_fm(i,j,k), env)"
-by simp
-
-theorem Cons_reflection:
-     "REFLECTS[\<lambda>x. is_Cons(L,f(x),g(x),h(x)),
-               \<lambda>i x. is_Cons(**Lset(i),f(x),g(x),h(x))]"
-apply (simp only: is_Cons_def setclass_simps)
-apply (intro FOL_reflections pair_reflection Inr_reflection)
-done
-
-subsubsection{*The Formula @{term is_quasilist}, Internalized*}
-
-(* is_quasilist(M,xs) == is_Nil(M,z) | (\<exists>x[M]. \<exists>l[M]. is_Cons(M,x,l,z))" *)
-
-constdefs quasilist_fm :: "i=>i"
-    "quasilist_fm(x) ==
-       Or(Nil_fm(x), Exists(Exists(Cons_fm(1,0,succ(succ(x))))))"
-
-lemma quasilist_type [TC]: "x \<in> nat ==> quasilist_fm(x) \<in> formula"
-
-lemma sats_quasilist_fm [simp]:
-   "[| x \<in> nat; env \<in> list(A)|]
-    ==> sats(A, quasilist_fm(x), env) <-> is_quasilist(**A, nth(x,env))"
-
-lemma quasilist_iff_sats:
-      "[| nth(i,env) = x; i \<in> nat; env \<in> list(A)|]
-       ==> is_quasilist(**A, x) <-> sats(A, quasilist_fm(i), env)"
-by simp
-
-theorem quasilist_reflection:
-     "REFLECTS[\<lambda>x. is_quasilist(L,f(x)),
-               \<lambda>i x. is_quasilist(**Lset(i),f(x))]"
-apply (simp only: is_quasilist_def setclass_simps)
-apply (intro FOL_reflections Nil_reflection Cons_reflection)
-done
-
-
-subsection{*Absoluteness for the Function @{term nth}*}
-
-
-subsubsection{*The Formula @{term is_hd}, Internalized*}
-
-(*   "is_hd(M,xs,H) ==
-       (is_Nil(M,xs) --> empty(M,H)) &
-       (\<forall>x[M]. \<forall>l[M]. ~ is_Cons(M,x,l,xs) | H=x) &
-       (is_quasilist(M,xs) | empty(M,H))" *)
-constdefs hd_fm :: "[i,i]=>i"
-    "hd_fm(xs,H) ==
-       And(Implies(Nil_fm(xs), empty_fm(H)),
-           And(Forall(Forall(Or(Neg(Cons_fm(1,0,xs#+2)), Equal(H#+2,1)))),
-               Or(quasilist_fm(xs), empty_fm(H))))"
-
-lemma hd_type [TC]:
-     "[| x \<in> nat; y \<in> nat |] ==> hd_fm(x,y) \<in> formula"
-
-lemma sats_hd_fm [simp]:
-   "[| x \<in> nat; y \<in> nat; env \<in> list(A)|]
-    ==> sats(A, hd_fm(x,y), env) <-> is_hd(**A, nth(x,env), nth(y,env))"
-
-lemma hd_iff_sats:
-      "[| nth(i,env) = x; nth(j,env) = y;
-          i \<in> nat; j \<in> nat; env \<in> list(A)|]
-       ==> is_hd(**A, x, y) <-> sats(A, hd_fm(i,j), env)"
-by simp
-
-theorem hd_reflection:
-     "REFLECTS[\<lambda>x. is_hd(L,f(x),g(x)),
-               \<lambda>i x. is_hd(**Lset(i),f(x),g(x))]"
-apply (simp only: is_hd_def setclass_simps)
-apply (intro FOL_reflections Nil_reflection Cons_reflection
-             quasilist_reflection empty_reflection)
-done
-
-
-subsubsection{*The Formula @{term is_tl}, Internalized*}
-
-(*     "is_tl(M,xs,T) ==
-       (is_Nil(M,xs) --> T=xs) &
-       (\<forall>x[M]. \<forall>l[M]. ~ is_Cons(M,x,l,xs) | T=l) &
-       (is_quasilist(M,xs) | empty(M,T))" *)
-constdefs tl_fm :: "[i,i]=>i"
-    "tl_fm(xs,T) ==
-       And(Implies(Nil_fm(xs), Equal(T,xs)),
-           And(Forall(Forall(Or(Neg(Cons_fm(1,0,xs#+2)), Equal(T#+2,0)))),
-               Or(quasilist_fm(xs), empty_fm(T))))"
-
-lemma tl_type [TC]:
-     "[| x \<in> nat; y \<in> nat |] ==> tl_fm(x,y) \<in> formula"
-
-lemma sats_tl_fm [simp]:
-   "[| x \<in> nat; y \<in> nat; env \<in> list(A)|]
-    ==> sats(A, tl_fm(x,y), env) <-> is_tl(**A, nth(x,env), nth(y,env))"
-
-lemma tl_iff_sats:
-      "[| nth(i,env) = x; nth(j,env) = y;
-          i \<in> nat; j \<in> nat; env \<in> list(A)|]
-       ==> is_tl(**A, x, y) <-> sats(A, tl_fm(i,j), env)"
-by simp
-
-theorem tl_reflection:
-     "REFLECTS[\<lambda>x. is_tl(L,f(x),g(x)),
-               \<lambda>i x. is_tl(**Lset(i),f(x),g(x))]"
-apply (simp only: is_tl_def setclass_simps)
-apply (intro FOL_reflections Nil_reflection Cons_reflection
-             quasilist_reflection empty_reflection)
-done
-
-
subsubsection{*The Formula @{term is_nth}, Internalized*}

(* "is_nth(M,n,l,Z) ==
@@ -1299,14 +1067,6 @@
iterates_MH_reflection hd_reflection tl_reflection)
done

-theorem bool_of_o_reflection:
-     "REFLECTS [P(L), \<lambda>i. P(**Lset(i))] ==>
-      REFLECTS[\<lambda>x. is_bool_of_o(L, P(L,x), f(x)),
-               \<lambda>i x. is_bool_of_o(**Lset(i), P(**Lset(i),x), f(x))]"
-apply (simp (no_asm) only: is_bool_of_o_def setclass_simps)
-apply (intro FOL_reflections function_reflections, assumption+)
-done
-

subsubsection{*An Instance of Replacement for @{term nth}*}
```
```--- a/src/ZF/Constructible/Satisfies_absolute.thy	Tue Aug 13 12:16:14 2002 +0200
+++ b/src/ZF/Constructible/Satisfies_absolute.thy	Tue Aug 13 17:42:34 2002 +0200
@@ -4,218 +4,126 @@
*)

+header {*Absoluteness for the Satisfies Relation on Formulas*}
+
theory Satisfies_absolute = Datatype_absolute + Rec_Separation:

-subsection{*More Internalizations*}
+
+subsubsection{*The Formula @{term is_list_N}, Internalized*}

-lemma and_reflection:
-     "REFLECTS[\<lambda>x. is_and(L,f(x),g(x),h(x)),
-               \<lambda>i x. is_and(**Lset(i),f(x),g(x),h(x))]"
-apply (simp only: is_and_def setclass_simps)
-apply (intro FOL_reflections function_reflections)
-done
+(* "is_list_N(M,A,n,Z) ==
+      \<exists>zero[M]. \<exists>sn[M]. \<exists>msn[M].
+       empty(M,zero) &
+       successor(M,n,sn) & membership(M,sn,msn) &
+       is_wfrec(M, iterates_MH(M, is_list_functor(M,A),zero), msn, n, Z)" *)
+
+constdefs list_N_fm :: "[i,i,i]=>i"
+  "list_N_fm(A,n,Z) ==
+     Exists(Exists(Exists(
+       And(empty_fm(2),
+         And(succ_fm(n#+3,1),
+          And(Memrel_fm(1,0),
+              is_wfrec_fm(iterates_MH_fm(list_functor_fm(A#+9#+3,1,0),
+                                         7,2,1,0),
+                           0, n#+3, Z#+3)))))))"

-lemma not_reflection:
-     "REFLECTS[\<lambda>x. is_not(L,f(x),g(x)),
-               \<lambda>i x. is_not(**Lset(i),f(x),g(x))]"
-apply (simp only: is_not_def setclass_simps)
-apply (intro FOL_reflections function_reflections)
+lemma list_N_fm_type [TC]:
+ "[| x \<in> nat; y \<in> nat; z \<in> nat |] ==> list_N_fm(x,y,z) \<in> formula"
+
+lemma sats_list_N_fm [simp]:
+   "[| x \<in> nat; y < length(env); z < length(env); env \<in> list(A)|]
+    ==> sats(A, list_N_fm(x,y,z), env) <->
+        is_list_N(**A, nth(x,env), nth(y,env), nth(z,env))"
+apply (frule_tac x=z in lt_length_in_nat, assumption)
+apply (frule_tac x=y in lt_length_in_nat, assumption)
+apply (simp add: list_N_fm_def is_list_N_def sats_is_wfrec_fm
+                 sats_iterates_MH_fm)
done

-subsubsection{*The Operator @{term is_lambda}*}
-
-text{*The two arguments of @{term p} are always 1, 0. Remember that
- @{term p} will be enclosed by three quantifiers.*}
-
-(* is_lambda :: "[i=>o, i, [i,i]=>o, i] => o"
-    "is_lambda(M, A, is_b, z) ==
-       \<forall>p[M]. p \<in> z <->
-        (\<exists>u[M]. \<exists>v[M]. u\<in>A & pair(M,u,v,p) & is_b(u,v))" *)
-constdefs lambda_fm :: "[i, i, i]=>i"
- "lambda_fm(p,A,z) ==
-    Forall(Iff(Member(0,succ(z)),
-            Exists(Exists(And(Member(1,A#+3),
-                           And(pair_fm(1,0,2), p))))))"
-
-text{*We call @{term p} with arguments x, y by equating them with
-  the corresponding quantified variables with de Bruijn indices 1, 0.*}
-
-lemma is_lambda_type [TC]:
-     "[| p \<in> formula; x \<in> nat; y \<in> nat |]
-      ==> lambda_fm(p,x,y) \<in> formula"
+lemma list_N_iff_sats:
+      "[| nth(i,env) = x; nth(j,env) = y; nth(k,env) = z;
+          i \<in> nat; j < length(env); k < length(env); env \<in> list(A)|]
+       ==> is_list_N(**A, x, y, z) <-> sats(A, list_N_fm(i,j,k), env)"

-lemma sats_lambda_fm:
-  assumes is_b_iff_sats:
-      "!!a0 a1 a2.
-        [|a0\<in>A; a1\<in>A; a2\<in>A|]
-        ==> is_b(a1, a0) <-> sats(A, p, Cons(a0,Cons(a1,Cons(a2,env))))"
-  shows
-      "[|x \<in> nat; y \<in> nat; env \<in> list(A)|]
-       ==> sats(A, lambda_fm(p,x,y), env) <->
-           is_lambda(**A, nth(x,env), is_b, nth(y,env))"
-by (simp add: lambda_fm_def sats_is_recfun_fm is_lambda_def is_b_iff_sats [THEN iff_sym])
-
-
-lemma is_lambda_iff_sats:
-  assumes is_b_iff_sats:
-      "!!a0 a1 a2.
-        [|a0\<in>A; a1\<in>A; a2\<in>A|]
-        ==> is_b(a1, a0) <-> sats(A, p, Cons(a0,Cons(a1,Cons(a2,env))))"
-  shows
-  "[|nth(i,env) = x; nth(j,env) = y;
-      i \<in> nat; j \<in> nat; env \<in> list(A)|]
-   ==> is_lambda(**A, x, is_b, y) <-> sats(A, lambda_fm(p,i,j), env)"
-by (simp add: sats_lambda_fm [OF is_b_iff_sats])
-
-theorem is_lambda_reflection:
-  assumes is_b_reflection:
-    "!!f' f g h. REFLECTS[\<lambda>x. is_b(L, f'(x), f(x), g(x)),
-                     \<lambda>i x. is_b(**Lset(i), f'(x), f(x), g(x))]"
-  shows "REFLECTS[\<lambda>x. is_lambda(L, A(x), is_b(L,x), f(x)),
-               \<lambda>i x. is_lambda(**Lset(i), A(x), is_b(**Lset(i),x), f(x))]"
-apply (simp (no_asm_use) only: is_lambda_def setclass_simps)
-apply (intro FOL_reflections is_b_reflection pair_reflection)
+theorem list_N_reflection:
+     "REFLECTS[\<lambda>x. is_list_N(L, f(x), g(x), h(x)),
+               \<lambda>i x. is_list_N(**Lset(i), f(x), g(x), h(x))]"
+apply (simp only: is_list_N_def setclass_simps)
+apply (intro FOL_reflections function_reflections is_wfrec_reflection
+             iterates_MH_reflection list_functor_reflection)
done

-subsubsection{*The Operator @{term is_Member}, Internalized*}
+
+subsubsection{*The Predicate ``Is A List''*}

-(*    "is_Member(M,x,y,Z) ==
-	\<exists>p[M]. \<exists>u[M]. pair(M,x,y,p) & is_Inl(M,p,u) & is_Inl(M,u,Z)" *)
-constdefs Member_fm :: "[i,i,i]=>i"
-    "Member_fm(x,y,Z) ==
-       Exists(Exists(And(pair_fm(x#+2,y#+2,1),
-                      And(Inl_fm(1,0), Inl_fm(0,Z#+2)))))"
+(* mem_list(M,A,l) ==
+      \<exists>n[M]. \<exists>listn[M].
+       finite_ordinal(M,n) & is_list_N(M,A,n,listn) & l \<in> listn *)
+constdefs mem_list_fm :: "[i,i]=>i"
+    "mem_list_fm(x,y) ==
+       Exists(Exists(
+         And(finite_ordinal_fm(1),
+           And(list_N_fm(x#+2,1,0), Member(y#+2,0)))))"

-lemma is_Member_type [TC]:
-     "[| x \<in> nat; y \<in> nat; z \<in> nat |] ==> Member_fm(x,y,z) \<in> formula"
+lemma mem_list_type [TC]:
+     "[| x \<in> nat; y \<in> nat |] ==> mem_list_fm(x,y) \<in> formula"

-lemma sats_Member_fm [simp]:
-   "[| x \<in> nat; y \<in> nat; z \<in> nat; env \<in> list(A)|]
-    ==> sats(A, Member_fm(x,y,z), env) <->
-        is_Member(**A, nth(x,env), nth(y,env), nth(z,env))"
+lemma sats_mem_list_fm [simp]:
+   "[| x \<in> nat; y \<in> nat; env \<in> list(A)|]
+    ==> sats(A, mem_list_fm(x,y), env) <-> mem_list(**A, nth(x,env), nth(y,env))"

-lemma Member_iff_sats:
-      "[| nth(i,env) = x; nth(j,env) = y; nth(k,env) = z;
-          i \<in> nat; j \<in> nat; k \<in> nat; env \<in> list(A)|]
-       ==> is_Member(**A, x, y, z) <-> sats(A, Member_fm(i,j,k), env)"
+lemma mem_list_iff_sats:
+      "[| nth(i,env) = x; nth(j,env) = y;
+          i \<in> nat; j \<in> nat; env \<in> list(A)|]
+       ==> mem_list(**A, x, y) <-> sats(A, mem_list_fm(i,j), env)"
+by simp

-theorem Member_reflection:
-     "REFLECTS[\<lambda>x. is_Member(L,f(x),g(x),h(x)),
-               \<lambda>i x. is_Member(**Lset(i),f(x),g(x),h(x))]"
-apply (simp only: is_Member_def setclass_simps)
-apply (intro FOL_reflections pair_reflection Inl_reflection)
+theorem mem_list_reflection:
+     "REFLECTS[\<lambda>x. mem_list(L,f(x),g(x)),
+               \<lambda>i x. mem_list(**Lset(i),f(x),g(x))]"
+apply (simp only: mem_list_def setclass_simps)
+apply (intro FOL_reflections finite_ordinal_reflection list_N_reflection)
done

-subsubsection{*The Operator @{term is_Equal}, Internalized*}

-(*    "is_Equal(M,x,y,Z) ==
-	\<exists>p[M]. \<exists>u[M]. pair(M,x,y,p) & is_Inr(M,p,u) & is_Inl(M,u,Z)" *)
-constdefs Equal_fm :: "[i,i,i]=>i"
-    "Equal_fm(x,y,Z) ==
-       Exists(Exists(And(pair_fm(x#+2,y#+2,1),
-                      And(Inr_fm(1,0), Inl_fm(0,Z#+2)))))"
-
-lemma is_Equal_type [TC]:
-     "[| x \<in> nat; y \<in> nat; z \<in> nat |] ==> Equal_fm(x,y,z) \<in> formula"
-
-lemma sats_Equal_fm [simp]:
-   "[| x \<in> nat; y \<in> nat; z \<in> nat; env \<in> list(A)|]
-    ==> sats(A, Equal_fm(x,y,z), env) <->
-        is_Equal(**A, nth(x,env), nth(y,env), nth(z,env))"
+subsubsection{*The Predicate ``Is @{term "list(A)"}''*}

-lemma Equal_iff_sats:
-      "[| nth(i,env) = x; nth(j,env) = y; nth(k,env) = z;
-          i \<in> nat; j \<in> nat; k \<in> nat; env \<in> list(A)|]
-       ==> is_Equal(**A, x, y, z) <-> sats(A, Equal_fm(i,j,k), env)"
-
-theorem Equal_reflection:
-     "REFLECTS[\<lambda>x. is_Equal(L,f(x),g(x),h(x)),
-               \<lambda>i x. is_Equal(**Lset(i),f(x),g(x),h(x))]"
-apply (simp only: is_Equal_def setclass_simps)
-apply (intro FOL_reflections pair_reflection Inl_reflection Inr_reflection)
-done
+(* is_list(M,A,Z) == \<forall>l[M]. l \<in> Z <-> mem_list(M,A,l) *)
+constdefs is_list_fm :: "[i,i]=>i"
+    "is_list_fm(A,Z) ==
+       Forall(Iff(Member(0,succ(Z)), mem_list_fm(succ(A),0)))"

-subsubsection{*The Operator @{term is_Nand}, Internalized*}
-
-(*    "is_Nand(M,x,y,Z) ==
-	\<exists>p[M]. \<exists>u[M]. pair(M,x,y,p) & is_Inl(M,p,u) & is_Inr(M,u,Z)" *)
-constdefs Nand_fm :: "[i,i,i]=>i"
-    "Nand_fm(x,y,Z) ==
-       Exists(Exists(And(pair_fm(x#+2,y#+2,1),
-                      And(Inl_fm(1,0), Inr_fm(0,Z#+2)))))"
-
-lemma is_Nand_type [TC]:
-     "[| x \<in> nat; y \<in> nat; z \<in> nat |] ==> Nand_fm(x,y,z) \<in> formula"
+lemma is_list_type [TC]:
+     "[| x \<in> nat; y \<in> nat |] ==> is_list_fm(x,y) \<in> formula"

-lemma sats_Nand_fm [simp]:
-   "[| x \<in> nat; y \<in> nat; z \<in> nat; env \<in> list(A)|]
-    ==> sats(A, Nand_fm(x,y,z), env) <->
-        is_Nand(**A, nth(x,env), nth(y,env), nth(z,env))"
-
-lemma Nand_iff_sats:
-      "[| nth(i,env) = x; nth(j,env) = y; nth(k,env) = z;
-          i \<in> nat; j \<in> nat; k \<in> nat; env \<in> list(A)|]
-       ==> is_Nand(**A, x, y, z) <-> sats(A, Nand_fm(i,j,k), env)"
-
-theorem Nand_reflection:
-     "REFLECTS[\<lambda>x. is_Nand(L,f(x),g(x),h(x)),
-               \<lambda>i x. is_Nand(**Lset(i),f(x),g(x),h(x))]"
-apply (simp only: is_Nand_def setclass_simps)
-apply (intro FOL_reflections pair_reflection Inl_reflection Inr_reflection)
-done
-
-subsubsection{*The Operator @{term is_Forall}, Internalized*}
+lemma sats_is_list_fm [simp]:
+   "[| x \<in> nat; y \<in> nat; env \<in> list(A)|]
+    ==> sats(A, is_list_fm(x,y), env) <-> is_list(**A, nth(x,env), nth(y,env))"

-(* "is_Forall(M,p,Z) == \<exists>u[M]. is_Inr(M,p,u) & is_Inr(M,u,Z)" *)
-constdefs Forall_fm :: "[i,i]=>i"
-    "Forall_fm(x,Z) ==
-       Exists(And(Inr_fm(succ(x),0), Inr_fm(0,succ(Z))))"
-
-lemma is_Forall_type [TC]:
-     "[| x \<in> nat; y \<in> nat |] ==> Forall_fm(x,y) \<in> formula"
+lemma is_list_iff_sats:
+      "[| nth(i,env) = x; nth(j,env) = y;
+          i \<in> nat; j \<in> nat; env \<in> list(A)|]
+       ==> is_list(**A, x, y) <-> sats(A, is_list_fm(i,j), env)"
+by simp

-lemma sats_Forall_fm [simp]:
-   "[| x \<in> nat; y \<in> nat; env \<in> list(A)|]
-    ==> sats(A, Forall_fm(x,y), env) <->
-        is_Forall(**A, nth(x,env), nth(y,env))"
-
-lemma Forall_iff_sats:
-      "[| nth(i,env) = x; nth(j,env) = y;
-          i \<in> nat; j \<in> nat; env \<in> list(A)|]
-       ==> is_Forall(**A, x, y) <-> sats(A, Forall_fm(i,j), env)"
-
-theorem Forall_reflection:
-     "REFLECTS[\<lambda>x. is_Forall(L,f(x),g(x)),
-               \<lambda>i x. is_Forall(**Lset(i),f(x),g(x))]"
-apply (simp only: is_Forall_def setclass_simps)
-apply (intro FOL_reflections pair_reflection Inr_reflection)
+theorem is_list_reflection:
+     "REFLECTS[\<lambda>x. is_list(L,f(x),g(x)),
+               \<lambda>i x. is_list(**Lset(i),f(x),g(x))]"
+apply (simp only: is_list_def setclass_simps)
+apply (intro FOL_reflections mem_list_reflection)
done

subsubsection{*The Formula @{term is_formula_N}, Internalized*}

-(* "is_nth(M,n,l,Z) ==
-      \<exists>X[M]. \<exists>sn[M]. \<exists>msn[M].
-       2       1       0
-       successor(M,n,sn) & membership(M,sn,msn) &
-       is_wfrec(M, iterates_MH(M, is_tl(M), l), msn, n, X) &
-       is_hd(M,X,Z)" *)
-
(* "is_formula_N(M,n,Z) ==
\<exists>zero[M]. \<exists>sn[M]. \<exists>msn[M].
2       1       0
@@ -281,8 +189,7 @@

lemma mem_formula_iff_sats:
-      "[| nth(i,env) = x; nth(j,env) = y;
-          i \<in> nat; env \<in> list(A)|]
+      "[| nth(i,env) = x; i \<in> nat; env \<in> list(A)|]
==> mem_formula(**A, x) <-> sats(A, mem_formula_fm(i), env)"
by simp

@@ -295,6 +202,34 @@

+subsubsection{*The Predicate ``Is @{term "formula"}''*}
+
+(* is_formula(M,Z) == \<forall>p[M]. p \<in> Z <-> mem_formula(M,p) *)
+constdefs is_formula_fm :: "i=>i"
+    "is_formula_fm(Z) == Forall(Iff(Member(0,succ(Z)), mem_formula_fm(0)))"
+
+lemma is_formula_type [TC]:
+     "x \<in> nat ==> is_formula_fm(x) \<in> formula"
+
+lemma sats_is_formula_fm [simp]:
+   "[| x \<in> nat; env \<in> list(A)|]
+    ==> sats(A, is_formula_fm(x), env) <-> is_formula(**A, nth(x,env))"
+
+lemma is_formula_iff_sats:
+      "[| nth(i,env) = x; i \<in> nat; env \<in> list(A)|]
+       ==> is_formula(**A, x) <-> sats(A, is_formula_fm(i), env)"
+by simp
+
+theorem is_formula_reflection:
+     "REFLECTS[\<lambda>x. is_formula(L,f(x)),
+               \<lambda>i x. is_formula(**Lset(i),f(x))]"
+apply (simp only: is_formula_def setclass_simps)
+apply (intro FOL_reflections mem_formula_reflection)
+done
+
+
subsubsection{*The Formula @{term is_depth}, Internalized*}

(*    "is_depth(M,p,n) ==
@@ -580,7 +515,7 @@
--{*Merely a useful abbreviation for the sequel.*}
"is_depth_apply(M,h,p,z) ==
\<exists>dp[M]. \<exists>sdp[M]. \<exists>hsdp[M].
-	dp \<in> nat & is_depth(M,p,dp) & successor(M,dp,sdp) &
+	finite_ordinal(M,dp) & is_depth(M,p,dp) & successor(M,dp,sdp) &
fun_apply(M,h,sdp,hsdp) & fun_apply(M,hsdp,p,z)"

lemma (in M_datatypes) is_depth_apply_abs [simp]:
@@ -588,12 +523,6 @@
==> is_depth_apply(M,h,p,z) <-> z = h ` succ(depth(p)) ` p"
by (simp add: is_depth_apply_def formula_into_M depth_type eq_commute)

-lemma depth_apply_reflection:
-     "REFLECTS[\<lambda>x. is_depth_apply(L,f(x),g(x),h(x)),
-               \<lambda>i x. is_depth_apply(**Lset(i),f(x),g(x),h(x))]"
-apply (simp only: is_depth_apply_def setclass_simps)
-apply (intro FOL_reflections function_reflections depth_reflection)
-done

text{*There is at present some redundancy between the relativizations in
@@ -608,9 +537,12 @@

satisfies_is_a :: "[i=>o,i,i,i,i]=>o"
"satisfies_is_a(M,A) ==
-    \<lambda>x y. is_lambda(M, list(A),
-        \<lambda>env z. is_bool_of_o(M, \<exists>nx[M]. \<exists>ny[M].
-                  is_nth(M,x,env,nx) & is_nth(M,y,env,ny) & nx \<in> ny, z))"
+    \<lambda>x y zz. \<forall>lA[M]. is_list(M,A,lA) -->
+             is_lambda(M, lA,
+		\<lambda>env z. is_bool_of_o(M,
+                      \<exists>nx[M]. \<exists>ny[M].
+ 		       is_nth(M,x,env,nx) & is_nth(M,y,env,ny) & nx \<in> ny, z),
+                zz)"

satisfies_b :: "[i,i,i]=>i"
"satisfies_b(A) ==
@@ -620,20 +552,23 @@
--{*We simplify the formula to have just @{term nx} rather than
introducing @{term ny} with  @{term "nx=ny"} *}
"satisfies_is_b(M,A) ==
-    \<lambda>x y. is_lambda(M, list(A),
-         \<lambda>env z.
-         is_bool_of_o(M, \<exists>nx[M]. is_nth(M,x,env,nx) & is_nth(M,y,env,nx), z))"
+    \<lambda>x y zz. \<forall>lA[M]. is_list(M,A,lA) -->
+             is_lambda(M, lA,
+                \<lambda>env z. is_bool_of_o(M,
+                      \<exists>nx[M]. is_nth(M,x,env,nx) & is_nth(M,y,env,nx), z),
+                zz)"

satisfies_c :: "[i,i,i,i,i]=>i"
"satisfies_c(A,p,q,rp,rq) == \<lambda>env \<in> list(A). not(rp ` env and rq ` env)"

satisfies_is_c :: "[i=>o,i,i,i,i,i]=>o"
"satisfies_is_c(M,A,h) ==
-    \<lambda>p q. is_lambda(M, list(A),
-        \<lambda>env z. \<exists>hp[M]. \<exists>hq[M].
+    \<lambda>p q zz. \<forall>lA[M]. is_list(M,A,lA) -->
+             is_lambda(M, lA, \<lambda>env z. \<exists>hp[M]. \<exists>hq[M].
(\<exists>rp[M]. is_depth_apply(M,h,p,rp) & fun_apply(M,rp,env,hp)) &
(\<exists>rq[M]. is_depth_apply(M,h,q,rq) & fun_apply(M,rq,env,hq)) &
-                 (\<exists>pq[M]. is_and(M,hp,hq,pq) & is_not(M,pq,z)))"
+                 (\<exists>pq[M]. is_and(M,hp,hq,pq) & is_not(M,pq,z)),
+                zz)"

satisfies_d :: "[i,i,i]=>i"
"satisfies_d(A)
@@ -641,21 +576,27 @@

satisfies_is_d :: "[i=>o,i,i,i,i]=>o"
"satisfies_is_d(M,A,h) ==
-    \<lambda>p. is_lambda(M, list(A),
-        \<lambda>env z. \<exists>rp[M]. is_depth_apply(M,h,p,rp) &
-           is_bool_of_o(M,
-                \<forall>x[M]. \<forall>xenv[M]. \<forall>hp[M].
-                       x\<in>A --> is_Cons(M,x,env,xenv) -->
-                       fun_apply(M,rp,xenv,hp) --> number1(M,hp),
-                  z))"
+    \<lambda>p zz. \<forall>lA[M]. is_list(M,A,lA) -->
+             is_lambda(M, lA,
+                \<lambda>env z. \<exists>rp[M]. is_depth_apply(M,h,p,rp) &
+                    is_bool_of_o(M,
+                           \<forall>x[M]. \<forall>xenv[M]. \<forall>hp[M].
+                              x\<in>A --> is_Cons(M,x,env,xenv) -->
+                              fun_apply(M,rp,xenv,hp) --> number1(M,hp),
+                  z),
+               zz)"

satisfies_MH :: "[i=>o,i,i,i,i]=>o"
+    --{*The variable @{term u} is unused, but gives @{term satisfies_MH}
+        the correct arity.*}
"satisfies_MH ==
-    \<lambda>M A u f. is_lambda
-	 (M, formula,
-          is_formula_case (M, satisfies_is_a(M,A),
-                           satisfies_is_b(M,A),
-                           satisfies_is_c(M,A,f), satisfies_is_d(M,A,f)))"
+    \<lambda>M A u f zz.
+         \<forall>fml[M]. is_formula(M,fml) -->
+             is_lambda (M, fml,
+               is_formula_case (M, satisfies_is_a(M,A),
+                                satisfies_is_b(M,A),
+                                satisfies_is_c(M,A,f), satisfies_is_d(M,A,f)),
+               zz)"

text{*Further constraints on the class @{term M} in order to prove
@@ -1003,39 +944,305 @@

+subsubsection{*The Operator @{term is_depth_apply}, Internalized*}
+
+(* is_depth_apply(M,h,p,z) ==
+    \<exists>dp[M]. \<exists>sdp[M]. \<exists>hsdp[M].
+      2        1         0
+	finite_ordinal(M,dp) & is_depth(M,p,dp) & successor(M,dp,sdp) &
+	fun_apply(M,h,sdp,hsdp) & fun_apply(M,hsdp,p,z) *)
+constdefs depth_apply_fm :: "[i,i,i]=>i"
+    "depth_apply_fm(h,p,z) ==
+       Exists(Exists(Exists(
+        And(finite_ordinal_fm(2),
+         And(depth_fm(p#+3,2),
+          And(succ_fm(2,1),
+           And(fun_apply_fm(h#+3,1,0), fun_apply_fm(0,p#+3,z#+3))))))))"
+
+lemma depth_apply_type [TC]:
+     "[| x \<in> nat; y \<in> nat; z \<in> nat |] ==> depth_apply_fm(x,y,z) \<in> formula"
+
+lemma sats_depth_apply_fm [simp]:
+   "[| x \<in> nat; y \<in> nat; z \<in> nat; env \<in> list(A)|]
+    ==> sats(A, depth_apply_fm(x,y,z), env) <->
+        is_depth_apply(**A, nth(x,env), nth(y,env), nth(z,env))"
+
+lemma depth_apply_iff_sats:
+    "[| nth(i,env) = x; nth(j,env) = y; nth(k,env) = z;
+        i \<in> nat; j \<in> nat; k \<in> nat; env \<in> list(A)|]
+     ==> is_depth_apply(**A, x, y, z) <-> sats(A, depth_apply_fm(i,j,k), env)"
+by simp
+
+lemma depth_apply_reflection:
+     "REFLECTS[\<lambda>x. is_depth_apply(L,f(x),g(x),h(x)),
+               \<lambda>i x. is_depth_apply(**Lset(i),f(x),g(x),h(x))]"
+apply (simp only: is_depth_apply_def setclass_simps)
+apply (intro FOL_reflections function_reflections depth_reflection
+             finite_ordinal_reflection)
+done
+
+
+subsubsection{*The Operator @{term satisfies_is_a}, Internalized*}
+
+(* satisfies_is_a(M,A) ==
+    \<lambda>x y zz. \<forall>lA[M]. is_list(M,A,lA) -->
+             is_lambda(M, lA,
+		\<lambda>env z. is_bool_of_o(M,
+                      \<exists>nx[M]. \<exists>ny[M].
+ 		       is_nth(M,x,env,nx) & is_nth(M,y,env,ny) & nx \<in> ny, z),
+                zz)  *)
+
+constdefs satisfies_is_a_fm :: "[i,i,i,i]=>i"
+ "satisfies_is_a_fm(A,x,y,z) ==
+   Forall(
+     Implies(is_list_fm(succ(A),0),
+       lambda_fm(
+         bool_of_o_fm(Exists(
+                       Exists(And(nth_fm(x#+6,3,1),
+                               And(nth_fm(y#+6,3,0),
+                                   Member(1,0))))), 0),
+         0, succ(z))))"
+
+lemma satisfies_is_a_type [TC]:
+     "[| A \<in> nat; x \<in> nat; y \<in> nat; z \<in> nat |]
+      ==> satisfies_is_a_fm(A,x,y,z) \<in> formula"
+
+lemma sats_satisfies_is_a_fm [simp]:
+   "[| u \<in> nat; x < length(env); y < length(env); z \<in> nat; env \<in> list(A)|]
+    ==> sats(A, satisfies_is_a_fm(u,x,y,z), env) <->
+        satisfies_is_a(**A, nth(u,env), nth(x,env), nth(y,env), nth(z,env))"
+apply (frule_tac x=x in lt_length_in_nat, assumption)
+apply (frule_tac x=y in lt_length_in_nat, assumption)
+apply (simp add: satisfies_is_a_fm_def satisfies_is_a_def sats_lambda_fm
+                 sats_bool_of_o_fm)
+done
+
+lemma satisfies_is_a_iff_sats:
+  "[| nth(u,env) = nu; nth(x,env) = nx; nth(y,env) = ny; nth(z,env) = nz;
+      u \<in> nat; x < length(env); y < length(env); z \<in> nat; env \<in> list(A)|]
+   ==> satisfies_is_a(**A,nu,nx,ny,nz) <->
+       sats(A, satisfies_is_a_fm(u,x,y,z), env)"
+by simp
+
theorem satisfies_is_a_reflection:
"REFLECTS[\<lambda>x. satisfies_is_a(L,f(x),g(x),h(x),g'(x)),
\<lambda>i x. satisfies_is_a(**Lset(i),f(x),g(x),h(x),g'(x))]"
apply (unfold satisfies_is_a_def)
apply (intro FOL_reflections is_lambda_reflection bool_of_o_reflection
-             nth_reflection)
+             nth_reflection is_list_reflection)
done

+subsubsection{*The Operator @{term satisfies_is_b}, Internalized*}
+
+(* satisfies_is_b(M,A) ==
+    \<lambda>x y zz. \<forall>lA[M]. is_list(M,A,lA) -->
+             is_lambda(M, lA,
+                \<lambda>env z. is_bool_of_o(M,
+                      \<exists>nx[M]. is_nth(M,x,env,nx) & is_nth(M,y,env,nx), z),
+                zz) *)
+
+constdefs satisfies_is_b_fm :: "[i,i,i,i]=>i"
+ "satisfies_is_b_fm(A,x,y,z) ==
+   Forall(
+     Implies(is_list_fm(succ(A),0),
+       lambda_fm(
+         bool_of_o_fm(Exists(And(nth_fm(x#+5,2,0), nth_fm(y#+5,2,0))), 0),
+         0, succ(z))))"
+
+lemma satisfies_is_b_type [TC]:
+     "[| A \<in> nat; x \<in> nat; y \<in> nat; z \<in> nat |]
+      ==> satisfies_is_b_fm(A,x,y,z) \<in> formula"
+
+lemma sats_satisfies_is_b_fm [simp]:
+   "[| u \<in> nat; x < length(env); y < length(env); z \<in> nat; env \<in> list(A)|]
+    ==> sats(A, satisfies_is_b_fm(u,x,y,z), env) <->
+        satisfies_is_b(**A, nth(u,env), nth(x,env), nth(y,env), nth(z,env))"
+apply (frule_tac x=x in lt_length_in_nat, assumption)
+apply (frule_tac x=y in lt_length_in_nat, assumption)
+apply (simp add: satisfies_is_b_fm_def satisfies_is_b_def sats_lambda_fm
+                 sats_bool_of_o_fm)
+done
+
+lemma satisfies_is_b_iff_sats:
+  "[| nth(u,env) = nu; nth(x,env) = nx; nth(y,env) = ny; nth(z,env) = nz;
+      u \<in> nat; x < length(env); y < length(env); z \<in> nat; env \<in> list(A)|]
+   ==> satisfies_is_b(**A,nu,nx,ny,nz) <->
+       sats(A, satisfies_is_b_fm(u,x,y,z), env)"
+by simp
+
theorem satisfies_is_b_reflection:
"REFLECTS[\<lambda>x. satisfies_is_b(L,f(x),g(x),h(x),g'(x)),
\<lambda>i x. satisfies_is_b(**Lset(i),f(x),g(x),h(x),g'(x))]"
apply (unfold satisfies_is_b_def)
apply (intro FOL_reflections is_lambda_reflection bool_of_o_reflection
-             nth_reflection)
+             nth_reflection is_list_reflection)
done

+
+subsubsection{*The Operator @{term satisfies_is_c}, Internalized*}
+
+(* satisfies_is_c(M,A,h) ==
+    \<lambda>p q zz. \<forall>lA[M]. is_list(M,A,lA) -->
+             is_lambda(M, lA, \<lambda>env z. \<exists>hp[M]. \<exists>hq[M].
+		 (\<exists>rp[M]. is_depth_apply(M,h,p,rp) & fun_apply(M,rp,env,hp)) &
+		 (\<exists>rq[M]. is_depth_apply(M,h,q,rq) & fun_apply(M,rq,env,hq)) &
+                 (\<exists>pq[M]. is_and(M,hp,hq,pq) & is_not(M,pq,z)),
+                zz) *)
+
+constdefs satisfies_is_c_fm :: "[i,i,i,i,i]=>i"
+ "satisfies_is_c_fm(A,h,p,q,zz) ==
+   Forall(
+     Implies(is_list_fm(succ(A),0),
+       lambda_fm(
+         Exists(Exists(
+          And(Exists(And(depth_apply_fm(h#+7,p#+7,0), fun_apply_fm(0,4,2))),
+          And(Exists(And(depth_apply_fm(h#+7,q#+7,0), fun_apply_fm(0,4,1))),
+              Exists(And(and_fm(2,1,0), not_fm(0,3))))))),
+         0, succ(zz))))"
+
+lemma satisfies_is_c_type [TC]:
+     "[| A \<in> nat; h \<in> nat; x \<in> nat; y \<in> nat; z \<in> nat |]
+      ==> satisfies_is_c_fm(A,h,x,y,z) \<in> formula"
+
+lemma sats_satisfies_is_c_fm [simp]:
+   "[| u \<in> nat; v \<in> nat; x \<in> nat; y \<in> nat; z \<in> nat; env \<in> list(A)|]
+    ==> sats(A, satisfies_is_c_fm(u,v,x,y,z), env) <->
+        satisfies_is_c(**A, nth(u,env), nth(v,env), nth(x,env),
+                            nth(y,env), nth(z,env))"
+by (simp add: satisfies_is_c_fm_def satisfies_is_c_def sats_lambda_fm)
+
+lemma satisfies_is_c_iff_sats:
+  "[| nth(u,env) = nu; nth(v,env) = nv; nth(x,env) = nx; nth(y,env) = ny;
+      nth(z,env) = nz;
+      u \<in> nat; v \<in> nat; x \<in> nat; y \<in> nat; z \<in> nat; env \<in> list(A)|]
+   ==> satisfies_is_c(**A,nu,nv,nx,ny,nz) <->
+       sats(A, satisfies_is_c_fm(u,v,x,y,z), env)"
+by simp
+
theorem satisfies_is_c_reflection:
"REFLECTS[\<lambda>x. satisfies_is_c(L,f(x),g(x),h(x),g'(x),h'(x)),
\<lambda>i x. satisfies_is_c(**Lset(i),f(x),g(x),h(x),g'(x),h'(x))]"
-apply (unfold satisfies_is_c_def )
+apply (unfold satisfies_is_c_def)
apply (intro FOL_reflections function_reflections is_lambda_reflection
-             bool_of_o_reflection not_reflection and_reflection
-             nth_reflection depth_apply_reflection)
+             extra_reflections nth_reflection depth_apply_reflection
+             is_list_reflection)
done

+subsubsection{*The Operator @{term satisfies_is_d}, Internalized*}
+
+(* satisfies_is_d(M,A,h) ==
+    \<lambda>p zz. \<forall>lA[M]. is_list(M,A,lA) -->
+             is_lambda(M, lA,
+                \<lambda>env z. \<exists>rp[M]. is_depth_apply(M,h,p,rp) &
+                    is_bool_of_o(M,
+                           \<forall>x[M]. \<forall>xenv[M]. \<forall>hp[M].
+                              x\<in>A --> is_Cons(M,x,env,xenv) -->
+                              fun_apply(M,rp,xenv,hp) --> number1(M,hp),
+                  z),
+               zz) *)
+
+constdefs satisfies_is_d_fm :: "[i,i,i,i]=>i"
+ "satisfies_is_d_fm(A,h,p,zz) ==
+   Forall(
+     Implies(is_list_fm(succ(A),0),
+       lambda_fm(
+         Exists(
+           And(depth_apply_fm(h#+5,p#+5,0),
+               bool_of_o_fm(
+                Forall(Forall(Forall(
+                 Implies(Member(2,A#+8),
+                  Implies(Cons_fm(2,5,1),
+                   Implies(fun_apply_fm(3,1,0), number1_fm(0))))))), 1))),
+         0, succ(zz))))"
+
+lemma satisfies_is_d_type [TC]:
+     "[| A \<in> nat; h \<in> nat; x \<in> nat; z \<in> nat |]
+      ==> satisfies_is_d_fm(A,h,x,z) \<in> formula"
+
+lemma sats_satisfies_is_d_fm [simp]:
+   "[| u \<in> nat; x \<in> nat; y \<in> nat; z \<in> nat; env \<in> list(A)|]
+    ==> sats(A, satisfies_is_d_fm(u,x,y,z), env) <->
+        satisfies_is_d(**A, nth(u,env), nth(x,env), nth(y,env), nth(z,env))"
+by (simp add: satisfies_is_d_fm_def satisfies_is_d_def sats_lambda_fm
+              sats_bool_of_o_fm)
+
+lemma satisfies_is_d_iff_sats:
+  "[| nth(u,env) = nu; nth(x,env) = nx; nth(y,env) = ny; nth(z,env) = nz;
+      u \<in> nat; x \<in> nat; y \<in> nat; z \<in> nat; env \<in> list(A)|]
+   ==> satisfies_is_d(**A,nu,nx,ny,nz) <->
+       sats(A, satisfies_is_d_fm(u,x,y,z), env)"
+by simp
+
theorem satisfies_is_d_reflection:
"REFLECTS[\<lambda>x. satisfies_is_d(L,f(x),g(x),h(x),g'(x)),
\<lambda>i x. satisfies_is_d(**Lset(i),f(x),g(x),h(x),g'(x))]"
apply (unfold satisfies_is_d_def )
apply (intro FOL_reflections function_reflections is_lambda_reflection
-             bool_of_o_reflection not_reflection and_reflection
-             nth_reflection depth_apply_reflection Cons_reflection)
+             extra_reflections nth_reflection depth_apply_reflection
+             is_list_reflection)
+done
+
+
+subsubsection{*The Operator @{term satisfies_MH}, Internalized*}
+
+(* satisfies_MH ==
+    \<lambda>M A u f zz.
+         \<forall>fml[M]. is_formula(M,fml) -->
+             is_lambda (M, fml,
+               is_formula_case (M, satisfies_is_a(M,A),
+                                satisfies_is_b(M,A),
+                                satisfies_is_c(M,A,f), satisfies_is_d(M,A,f)),
+               zz) *)
+
+constdefs satisfies_MH_fm :: "[i,i,i,i]=>i"
+ "satisfies_MH_fm(A,u,f,zz) ==
+   Forall(
+     Implies(is_formula_fm(0),
+       lambda_fm(
+         formula_case_fm(satisfies_is_a_fm(A#+7,2,1,0),
+                         satisfies_is_b_fm(A#+7,2,1,0),
+                         satisfies_is_c_fm(A#+7,f#+7,2,1,0),
+                         satisfies_is_d_fm(A#+6,f#+6,1,0),
+                         1, 0),
+         0, succ(zz))))"
+
+lemma satisfies_MH_type [TC]:
+     "[| A \<in> nat; u \<in> nat; x \<in> nat; z \<in> nat |]
+      ==> satisfies_MH_fm(A,u,x,z) \<in> formula"
+
+lemma sats_satisfies_MH_fm [simp]:
+   "[| u \<in> nat; x \<in> nat; y \<in> nat; z \<in> nat; env \<in> list(A)|]
+    ==> sats(A, satisfies_MH_fm(u,x,y,z), env) <->
+        satisfies_MH(**A, nth(u,env), nth(x,env), nth(y,env), nth(z,env))"
+by (simp add: satisfies_MH_fm_def satisfies_MH_def sats_lambda_fm
+              sats_formula_case_fm)
+
+lemma satisfies_MH_iff_sats:
+  "[| nth(u,env) = nu; nth(x,env) = nx; nth(y,env) = ny; nth(z,env) = nz;
+      u \<in> nat; x \<in> nat; y \<in> nat; z \<in> nat; env \<in> list(A)|]
+   ==> satisfies_MH(**A,nu,nx,ny,nz) <->
+       sats(A, satisfies_MH_fm(u,x,y,z), env)"
+by simp
+
+lemmas satisfies_reflections =
+       is_lambda_reflection is_formula_reflection
+       is_formula_case_reflection
+       satisfies_is_a_reflection satisfies_is_b_reflection
+       satisfies_is_c_reflection satisfies_is_d_reflection
+
+theorem satisfies_MH_reflection:
+     "REFLECTS[\<lambda>x. satisfies_MH(L,f(x),g(x),h(x),g'(x)),
+               \<lambda>i x. satisfies_MH(**Lset(i),f(x),g(x),h(x),g'(x))]"
+apply (unfold satisfies_MH_def)
+apply (intro FOL_reflections satisfies_reflections)
done

@@ -1044,17 +1251,32 @@
is_wfrec (L, satisfies_MH(L,A), mesa, u, y)),
\<lambda>i x. \<exists>u \<in> Lset(i). u \<in> B \<and> (\<exists>y \<in> Lset(i). pair(**Lset(i), u, y, x) \<and>
is_wfrec (**Lset(i), satisfies_MH(**Lset(i),A), mesa, u, y))]"
-apply (unfold satisfies_MH_def)
-apply (intro FOL_reflections function_reflections is_wfrec_reflection
-             is_lambda_reflection)
-apply (simp only: is_formula_case_def)
-apply (intro FOL_reflections finite_ordinal_reflection mem_formula_reflection
-          Member_reflection Equal_reflection Nand_reflection Forall_reflection
-          satisfies_is_a_reflection satisfies_is_b_reflection
-          satisfies_is_c_reflection satisfies_is_d_reflection)
+by (intro FOL_reflections function_reflections satisfies_MH_reflection
+          is_wfrec_reflection)
+
+lemma formula_rec_replacement:
+      --{*For the @{term transrec}*}
+   "[|n \<in> nat; L(A)|] ==> transrec_replacement(L, satisfies_MH(L,A), n)"
+apply (subgoal_tac "L(Memrel(eclose({n})))")
+ prefer 2 apply (simp add: nat_into_M)
+apply (rule transrec_replacementI)
+apply (rule strong_replacementI)
+apply (rule rallI)
+apply (rename_tac B)
+apply (rule separation_CollectI)
+apply (rule_tac A="{B,A,n,z,Memrel(eclose({n}))}" in subset_LsetE, blast )
+apply (rule ReflectsE [OF formula_rec_replacement_Reflects], assumption)
+apply (drule subset_Lset_ltD, assumption)
+apply (erule reflection_imp_L_separation)
+  apply (simp_all add: lt_Ord2 Memrel_closed)
+apply (elim conjE)
+apply (rule DPow_LsetI)
+apply (rename_tac v)
+apply (rule bex_iff_sats conj_iff_sats)+
+apply (rule_tac env = "[u,v,A,n,B,Memrel(eclose({n}))]" in mem_iff_sats)
+apply (rule sep_rules | simp)+
+apply (rule sep_rules satisfies_MH_iff_sats is_wfrec_iff_sats | simp)+
done

end
-
-
-```
```--- a/src/ZF/IsaMakefile	Tue Aug 13 12:16:14 2002 +0200
+++ b/src/ZF/IsaMakefile	Tue Aug 13 17:42:34 2002 +0200
@@ -79,7 +79,8 @@

\$(LOG)/ZF-Constructible.gz: \$(OUT)/ZF  Constructible/ROOT.ML \
Constructible/Datatype_absolute.thy\
-  Constructible/Formula.thy     Constructible/Relative.thy \
+  Constructible/Formula.thy Constructible/Internalize.thy \
+  Constructible/Relative.thy \
Constructible/L_axioms.thy    Constructible/Wellorderings.thy \
Constructible/MetaExists.thy  Constructible/Normal.thy \
Constructible/Rec_Separation.thy Constructible/Separation.thy \```