--- /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"
+by (simp add: Inl_fm_def)
+
+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))"
+by (simp add: Inl_fm_def is_Inl_def)
+
+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"
+by (simp add: Inr_fm_def)
+
+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))"
+by (simp add: Inr_fm_def is_Inr_def)
+
+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"
+by (simp add: Nil_fm_def)
+
+lemma sats_Nil_fm [simp]:
+ "[| x \<in> nat; env \<in> list(A)|]
+ ==> sats(A, Nil_fm(x), env) <-> is_Nil(**A, nth(x,env))"
+by (simp add: Nil_fm_def is_Nil_def)
+
+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"
+by (simp add: Cons_fm_def)
+
+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))"
+by (simp add: Cons_fm_def is_Cons_def)
+
+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"
+by (simp add: quasilist_fm_def)
+
+lemma sats_quasilist_fm [simp]:
+ "[| x \<in> nat; env \<in> list(A)|]
+ ==> sats(A, quasilist_fm(x), env) <-> is_quasilist(**A, nth(x,env))"
+by (simp add: quasilist_fm_def is_quasilist_def)
+
+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"
+by (simp add: hd_fm_def)
+
+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))"
+by (simp add: hd_fm_def is_hd_def)
+
+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"
+by (simp add: tl_fm_def)
+
+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))"
+by (simp add: tl_fm_def is_tl_def)
+
+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"
+by (simp add: bool_of_o_fm_def)
+
+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)"
+by (simp add: sats_bool_of_o_fm)
+
+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"
+by (simp add: lambda_fm_def)
+
+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"
+by (simp add: Member_fm_def)
+
+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))"
+by (simp add: Member_fm_def is_Member_def)
+
+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)"
+by (simp add: sats_Member_fm)
+
+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"
+by (simp add: Equal_fm_def)
+
+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))"
+by (simp add: Equal_fm_def is_Equal_def)
+
+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)"
+by (simp add: sats_Equal_fm)
+
+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"
+by (simp add: Nand_fm_def)
+
+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))"
+by (simp add: Nand_fm_def is_Nand_def)
+
+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)"
+by (simp add: sats_Nand_fm)
+
+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"
+by (simp add: Forall_fm_def)
+
+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))"
+by (simp add: Forall_fm_def is_Forall_def)
+
+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)"
+by (simp add: sats_Forall_fm)
+
+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"
+by (simp add: and_fm_def)
+
+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))"
+by (simp add: and_fm_def is_and_def)
+
+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"
+by (simp add: or_fm_def)
+
+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))"
+by (simp add: or_fm_def is_or_def)
+
+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"
+by (simp add: not_fm_def)
+
+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))"
+by (simp add: not_fm_def is_not_def)
+
+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/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
Copyright 2002 University of Cambridge
-
-FIXME: define nth_fm and prove its "sats" theorem
*)
header {*Separation for Facts About Recursion*}
-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 @@
apply (simp_all add: setclass_def)
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"
-by (simp add: Inl_fm_def)
-
-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))"
-by (simp add: Inl_fm_def is_Inl_def)
-
-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"
-by (simp add: Inr_fm_def)
-
-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))"
-by (simp add: Inr_fm_def is_Inr_def)
-
-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"
-by (simp add: Nil_fm_def)
-
-lemma sats_Nil_fm [simp]:
- "[| x \<in> nat; env \<in> list(A)|]
- ==> sats(A, Nil_fm(x), env) <-> is_Nil(**A, nth(x,env))"
-by (simp add: Nil_fm_def is_Nil_def)
-
-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"
-by (simp add: Cons_fm_def)
-
-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))"
-by (simp add: Cons_fm_def is_Cons_def)
-
-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"
-by (simp add: quasilist_fm_def)
-
-lemma sats_quasilist_fm [simp]:
- "[| x \<in> nat; env \<in> list(A)|]
- ==> sats(A, quasilist_fm(x), env) <-> is_quasilist(**A, nth(x,env))"
-by (simp add: quasilist_fm_def is_quasilist_def)
-
-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"
-by (simp add: hd_fm_def)
-
-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))"
-by (simp add: hd_fm_def is_hd_def)
-
-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"
-by (simp add: tl_fm_def)
-
-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))"
-by (simp add: tl_fm_def is_tl_def)
-
-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 @@
Copyright 2002 University of Cambridge
*)
+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"
+by (simp add: list_N_fm_def)
+
+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"
-by (simp add: lambda_fm_def)
+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)"
+by (simp add: sats_list_N_fm)
-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"
-by (simp add: Member_fm_def)
+lemma mem_list_type [TC]:
+ "[| x \<in> nat; y \<in> nat |] ==> mem_list_fm(x,y) \<in> formula"
+by (simp add: mem_list_fm_def)
-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))"
-by (simp add: Member_fm_def is_Member_def)
+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))"
+by (simp add: mem_list_fm_def mem_list_def)
-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)"
-by (simp add: sats_Member_fm)
+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"
-by (simp add: Equal_fm_def)
-
-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))"
-by (simp add: Equal_fm_def is_Equal_def)
+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)"
-by (simp add: sats_Equal_fm)
-
-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"
-by (simp add: Nand_fm_def)
+lemma is_list_type [TC]:
+ "[| x \<in> nat; y \<in> nat |] ==> is_list_fm(x,y) \<in> formula"
+by (simp add: is_list_fm_def)
-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))"
-by (simp add: Nand_fm_def is_Nand_def)
-
-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)"
-by (simp add: sats_Nand_fm)
-
-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))"
+by (simp add: is_list_fm_def is_list_def)
-(* "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"
-by (simp add: Forall_fm_def)
+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))"
-by (simp add: Forall_fm_def is_Forall_def)
-
-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)"
-by (simp add: sats_Forall_fm)
-
-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 @@
by (simp add: mem_formula_fm_def mem_formula_def)
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"
+by (simp add: is_formula_fm_def)
+
+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))"
+by (simp add: is_formula_fm_def is_formula_def)
+
+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"
+by (simp add: depth_apply_fm_def)
+
+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))"
+by (simp add: depth_apply_fm_def is_depth_apply_def)
+
+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"
+by (simp add: satisfies_is_a_fm_def)
+
+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"
+by (simp add: satisfies_is_b_fm_def)
+
+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"
+by (simp add: satisfies_is_c_fm_def)
+
+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"
+by (simp add: satisfies_is_d_fm_def)
+
+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"
+by (simp add: satisfies_MH_fm_def)
+
+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 (simp add: nat_into_M)
+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
-
-
-