# HG changeset patch # User paulson # Date 1029253354 -7200 # Node ID 6f0c57def6d5e8ed2e4665c263addfe0cfefe179 # Parent af27202d6d1c4b0a791a59128a2300e67f1d524d In ZF/Constructible, moved many results from Satisfies_absolute, etc., to the new theory Internalize.thy diff -r af27202d6d1c -r 6f0c57def6d5 src/ZF/Constructible/Internalize.thy --- /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) == \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 \ nat; z \ nat |] ==> Inl_fm(x,z) \ formula" +by (simp add: Inl_fm_def) + +lemma sats_Inl_fm [simp]: + "[| x \ nat; z \ nat; env \ 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 \ nat; k \ nat; env \ list(A)|] + ==> is_Inl(**A, x, z) <-> sats(A, Inl_fm(i,k), env)" +by simp + +theorem Inl_reflection: + "REFLECTS[\x. is_Inl(L,f(x),h(x)), + \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) == \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 \ nat; z \ nat |] ==> Inr_fm(x,z) \ formula" +by (simp add: Inr_fm_def) + +lemma sats_Inr_fm [simp]: + "[| x \ nat; z \ nat; env \ 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 \ nat; k \ nat; env \ list(A)|] + ==> is_Inr(**A, x, z) <-> sats(A, Inr_fm(i,k), env)" +by simp + +theorem Inr_reflection: + "REFLECTS[\x. is_Inr(L,f(x),h(x)), + \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) == \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 \ nat ==> Nil_fm(x) \ formula" +by (simp add: Nil_fm_def) + +lemma sats_Nil_fm [simp]: + "[| x \ nat; env \ 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 \ nat; env \ list(A)|] + ==> is_Nil(**A, x) <-> sats(A, Nil_fm(i), env)" +by simp + +theorem Nil_reflection: + "REFLECTS[\x. is_Nil(L,f(x)), + \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) == \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 \ nat; y \ nat; z \ nat |] ==> Cons_fm(x,y,z) \ formula" +by (simp add: Cons_fm_def) + +lemma sats_Cons_fm [simp]: + "[| x \ nat; y \ nat; z \ nat; env \ 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 \ nat; j \ nat; k \ nat; env \ list(A)|] + ==>is_Cons(**A, x, y, z) <-> sats(A, Cons_fm(i,j,k), env)" +by simp + +theorem Cons_reflection: + "REFLECTS[\x. is_Cons(L,f(x),g(x),h(x)), + \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) | (\x[M]. \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 \ nat ==> quasilist_fm(x) \ formula" +by (simp add: quasilist_fm_def) + +lemma sats_quasilist_fm [simp]: + "[| x \ nat; env \ 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 \ nat; env \ list(A)|] + ==> is_quasilist(**A, x) <-> sats(A, quasilist_fm(i), env)" +by simp + +theorem quasilist_reflection: + "REFLECTS[\x. is_quasilist(L,f(x)), + \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)) & + (\x[M]. \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 \ nat; y \ nat |] ==> hd_fm(x,y) \ formula" +by (simp add: hd_fm_def) + +lemma sats_hd_fm [simp]: + "[| x \ nat; y \ nat; env \ 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 \ nat; j \ nat; env \ list(A)|] + ==> is_hd(**A, x, y) <-> sats(A, hd_fm(i,j), env)" +by simp + +theorem hd_reflection: + "REFLECTS[\x. is_hd(L,f(x),g(x)), + \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) & + (\x[M]. \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 \ nat; y \ nat |] ==> tl_fm(x,y) \ formula" +by (simp add: tl_fm_def) + +lemma sats_tl_fm [simp]: + "[| x \ nat; y \ nat; env \ 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 \ nat; j \ nat; env \ list(A)|] + ==> is_tl(**A, x, y) <-> sats(A, tl_fm(i,j), env)" +by simp + +theorem tl_reflection: + "REFLECTS[\x. is_tl(L,f(x),g(x)), + \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 \ formula; z \ nat |] ==> bool_of_o_fm(p,z) \ 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 \ nat; env \ 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 \ nat; env \ 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), \i. P(**Lset(i))] ==> + REFLECTS[\x. is_bool_of_o(L, P(L,x), f(x)), + \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) == + \p[M]. p \ z <-> + (\u[M]. \v[M]. u\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 \ formula; x \ nat; y \ nat |] + ==> lambda_fm(p,x,y) \ formula" +by (simp add: lambda_fm_def) + +lemma sats_lambda_fm: + assumes is_b_iff_sats: + "!!a0 a1 a2. + [|a0\A; a1\A; a2\A|] + ==> is_b(a1, a0) <-> sats(A, p, Cons(a0,Cons(a1,Cons(a2,env))))" + shows + "[|x \ nat; y \ nat; env \ 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\A; a1\A; a2\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 \ nat; j \ nat; env \ 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[\x. is_b(L, f'(x), f(x), g(x)), + \i x. is_b(**Lset(i), f'(x), f(x), g(x))]" + shows "REFLECTS[\x. is_lambda(L, A(x), is_b(L,x), f(x)), + \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) == + \p[M]. \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 \ nat; y \ nat; z \ nat |] ==> Member_fm(x,y,z) \ formula" +by (simp add: Member_fm_def) + +lemma sats_Member_fm [simp]: + "[| x \ nat; y \ nat; z \ nat; env \ 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 \ nat; j \ nat; k \ nat; env \ 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[\x. is_Member(L,f(x),g(x),h(x)), + \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) == + \p[M]. \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 \ nat; y \ nat; z \ nat |] ==> Equal_fm(x,y,z) \ formula" +by (simp add: Equal_fm_def) + +lemma sats_Equal_fm [simp]: + "[| x \ nat; y \ nat; z \ nat; env \ 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 \ nat; j \ nat; k \ nat; env \ 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[\x. is_Equal(L,f(x),g(x),h(x)), + \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) == + \p[M]. \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 \ nat; y \ nat; z \ nat |] ==> Nand_fm(x,y,z) \ formula" +by (simp add: Nand_fm_def) + +lemma sats_Nand_fm [simp]: + "[| x \ nat; y \ nat; z \ nat; env \ 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 \ nat; j \ nat; k \ nat; env \ 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[\x. is_Nand(L,f(x),g(x),h(x)), + \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) == \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 \ nat; y \ nat |] ==> Forall_fm(x,y) \ formula" +by (simp add: Forall_fm_def) + +lemma sats_Forall_fm [simp]: + "[| x \ nat; y \ nat; env \ 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 \ nat; j \ nat; env \ list(A)|] + ==> is_Forall(**A, x, y) <-> sats(A, Forall_fm(i,j), env)" +by (simp add: sats_Forall_fm) + +theorem Forall_reflection: + "REFLECTS[\x. is_Forall(L,f(x),g(x)), + \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 \ nat; y \ nat; z \ nat |] ==> and_fm(x,y,z) \ formula" +by (simp add: and_fm_def) + +lemma sats_and_fm [simp]: + "[| x \ nat; y \ nat; z \ nat; env \ 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 \ nat; j \ nat; k \ nat; env \ list(A)|] + ==> is_and(**A, x, y, z) <-> sats(A, and_fm(i,j,k), env)" +by simp + +theorem is_and_reflection: + "REFLECTS[\x. is_and(L,f(x),g(x),h(x)), + \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 \ nat; y \ nat; z \ nat |] ==> or_fm(x,y,z) \ formula" +by (simp add: or_fm_def) + +lemma sats_or_fm [simp]: + "[| x \ nat; y \ nat; z \ nat; env \ 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 \ nat; j \ nat; k \ nat; env \ list(A)|] + ==> is_or(**A, x, y, z) <-> sats(A, or_fm(i,j,k), env)" +by simp + +theorem is_or_reflection: + "REFLECTS[\x. is_or(L,f(x),g(x),h(x)), + \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 \ nat; z \ nat |] ==> not_fm(x,z) \ formula" +by (simp add: not_fm_def) + +lemma sats_is_not_fm [simp]: + "[| x \ nat; z \ nat; env \ 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 \ nat; k \ nat; env \ list(A)|] + ==> is_not(**A, x, z) <-> sats(A, not_fm(i,k), env)" +by simp + +theorem is_not_reflection: + "REFLECTS[\x. is_not(L,f(x),g(x)), + \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 diff -r af27202d6d1c -r 6f0c57def6d5 src/ZF/Constructible/L_axioms.thy --- 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 diff -r af27202d6d1c -r 6f0c57def6d5 src/ZF/Constructible/Rec_Separation.thy --- 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 \ nat; j \ nat; k \ nat; env \ 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 \ A; b \ A; c \ A; d \ A|] + assumes is_F_iff_sats: + "!!a b c d. [| a \ A; b \ A; c \ A; d \ 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' \ nat; i \ nat; j \ nat; k < length(env); env \ 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[\x. p(L, f(x), g(x)), - \i x. p(**Lset(i), f(x), g(x))]" - shows "REFLECTS[\x. iterates_MH(L, p(L), e(x), f(x), g(x), h(x)), - \i x. iterates_MH(**Lset(i), p(**Lset(i)), e(x), f(x), g(x), h(x))]" + "!!f g h. REFLECTS[\x. p(L, h(x), f(x), g(x)), + \i x. p(**Lset(i), h(x), f(x), g(x))]" + shows "REFLECTS[\x. iterates_MH(L, p(L,x), e(x), f(x), g(x), h(x)), + \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 "\gm[**Lset(i)]"} into @{text "\gm \ 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) == \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 \ nat; z \ nat |] ==> Inl_fm(x,z) \ formula" -by (simp add: Inl_fm_def) - -lemma sats_Inl_fm [simp]: - "[| x \ nat; z \ nat; env \ 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 \ nat; k \ nat; env \ list(A)|] - ==> is_Inl(**A, x, z) <-> sats(A, Inl_fm(i,k), env)" -by simp - -theorem Inl_reflection: - "REFLECTS[\x. is_Inl(L,f(x),h(x)), - \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) == \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 \ nat; z \ nat |] ==> Inr_fm(x,z) \ formula" -by (simp add: Inr_fm_def) - -lemma sats_Inr_fm [simp]: - "[| x \ nat; z \ nat; env \ 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 \ nat; k \ nat; env \ list(A)|] - ==> is_Inr(**A, x, z) <-> sats(A, Inr_fm(i,k), env)" -by simp - -theorem Inr_reflection: - "REFLECTS[\x. is_Inr(L,f(x),h(x)), - \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) == \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 \ nat ==> Nil_fm(x) \ formula" -by (simp add: Nil_fm_def) - -lemma sats_Nil_fm [simp]: - "[| x \ nat; env \ 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 \ nat; env \ list(A)|] - ==> is_Nil(**A, x) <-> sats(A, Nil_fm(i), env)" -by simp - -theorem Nil_reflection: - "REFLECTS[\x. is_Nil(L,f(x)), - \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) == \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 \ nat; y \ nat; z \ nat |] ==> Cons_fm(x,y,z) \ formula" -by (simp add: Cons_fm_def) - -lemma sats_Cons_fm [simp]: - "[| x \ nat; y \ nat; z \ nat; env \ 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 \ nat; j \ nat; k \ nat; env \ list(A)|] - ==>is_Cons(**A, x, y, z) <-> sats(A, Cons_fm(i,j,k), env)" -by simp - -theorem Cons_reflection: - "REFLECTS[\x. is_Cons(L,f(x),g(x),h(x)), - \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) | (\x[M]. \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 \ nat ==> quasilist_fm(x) \ formula" -by (simp add: quasilist_fm_def) - -lemma sats_quasilist_fm [simp]: - "[| x \ nat; env \ 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 \ nat; env \ list(A)|] - ==> is_quasilist(**A, x) <-> sats(A, quasilist_fm(i), env)" -by simp - -theorem quasilist_reflection: - "REFLECTS[\x. is_quasilist(L,f(x)), - \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)) & - (\x[M]. \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 \ nat; y \ nat |] ==> hd_fm(x,y) \ formula" -by (simp add: hd_fm_def) - -lemma sats_hd_fm [simp]: - "[| x \ nat; y \ nat; env \ 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 \ nat; j \ nat; env \ list(A)|] - ==> is_hd(**A, x, y) <-> sats(A, hd_fm(i,j), env)" -by simp - -theorem hd_reflection: - "REFLECTS[\x. is_hd(L,f(x),g(x)), - \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) & - (\x[M]. \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 \ nat; y \ nat |] ==> tl_fm(x,y) \ formula" -by (simp add: tl_fm_def) - -lemma sats_tl_fm [simp]: - "[| x \ nat; y \ nat; env \ 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 \ nat; j \ nat; env \ list(A)|] - ==> is_tl(**A, x, y) <-> sats(A, tl_fm(i,j), env)" -by simp - -theorem tl_reflection: - "REFLECTS[\x. is_tl(L,f(x),g(x)), - \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), \i. P(**Lset(i))] ==> - REFLECTS[\x. is_bool_of_o(L, P(L,x), f(x)), - \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}*} diff -r af27202d6d1c -r 6f0c57def6d5 src/ZF/Constructible/Satisfies_absolute.thy --- 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[\x. is_and(L,f(x),g(x),h(x)), - \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) == + \zero[M]. \sn[M]. \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[\x. is_not(L,f(x),g(x)), - \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 \ nat; y \ nat; z \ nat |] ==> list_N_fm(x,y,z) \ formula" +by (simp add: list_N_fm_def) + +lemma sats_list_N_fm [simp]: + "[| x \ nat; y < length(env); z < length(env); env \ 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) == - \p[M]. p \ z <-> - (\u[M]. \v[M]. u\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 \ formula; x \ nat; y \ nat |] - ==> lambda_fm(p,x,y) \ 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 \ nat; j < length(env); k < length(env); env \ 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\A; a1\A; a2\A|] - ==> is_b(a1, a0) <-> sats(A, p, Cons(a0,Cons(a1,Cons(a2,env))))" - shows - "[|x \ nat; y \ nat; env \ 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\A; a1\A; a2\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 \ nat; j \ nat; env \ 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[\x. is_b(L, f'(x), f(x), g(x)), - \i x. is_b(**Lset(i), f'(x), f(x), g(x))]" - shows "REFLECTS[\x. is_lambda(L, A(x), is_b(L,x), f(x)), - \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[\x. is_list_N(L, f(x), g(x), h(x)), + \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) == - \p[M]. \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) == + \n[M]. \listn[M]. + finite_ordinal(M,n) & is_list_N(M,A,n,listn) & l \ 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 \ nat; y \ nat; z \ nat |] ==> Member_fm(x,y,z) \ formula" -by (simp add: Member_fm_def) +lemma mem_list_type [TC]: + "[| x \ nat; y \ nat |] ==> mem_list_fm(x,y) \ formula" +by (simp add: mem_list_fm_def) -lemma sats_Member_fm [simp]: - "[| x \ nat; y \ nat; z \ nat; env \ 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 \ nat; y \ nat; env \ 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 \ nat; j \ nat; k \ nat; env \ 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 \ nat; j \ nat; env \ list(A)|] + ==> mem_list(**A, x, y) <-> sats(A, mem_list_fm(i,j), env)" +by simp -theorem Member_reflection: - "REFLECTS[\x. is_Member(L,f(x),g(x),h(x)), - \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[\x. mem_list(L,f(x),g(x)), + \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) == - \p[M]. \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 \ nat; y \ nat; z \ nat |] ==> Equal_fm(x,y,z) \ formula" -by (simp add: Equal_fm_def) - -lemma sats_Equal_fm [simp]: - "[| x \ nat; y \ nat; z \ nat; env \ 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 \ nat; j \ nat; k \ nat; env \ 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[\x. is_Equal(L,f(x),g(x),h(x)), - \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) == \l[M]. l \ 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) == - \p[M]. \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 \ nat; y \ nat; z \ nat |] ==> Nand_fm(x,y,z) \ formula" -by (simp add: Nand_fm_def) +lemma is_list_type [TC]: + "[| x \ nat; y \ nat |] ==> is_list_fm(x,y) \ formula" +by (simp add: is_list_fm_def) -lemma sats_Nand_fm [simp]: - "[| x \ nat; y \ nat; z \ nat; env \ 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 \ nat; j \ nat; k \ nat; env \ 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[\x. is_Nand(L,f(x),g(x),h(x)), - \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 \ nat; y \ nat; env \ 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) == \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 \ nat; y \ nat |] ==> Forall_fm(x,y) \ formula" -by (simp add: Forall_fm_def) +lemma is_list_iff_sats: + "[| nth(i,env) = x; nth(j,env) = y; + i \ nat; j \ nat; env \ list(A)|] + ==> is_list(**A, x, y) <-> sats(A, is_list_fm(i,j), env)" +by simp -lemma sats_Forall_fm [simp]: - "[| x \ nat; y \ nat; env \ 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 \ nat; j \ nat; env \ list(A)|] - ==> is_Forall(**A, x, y) <-> sats(A, Forall_fm(i,j), env)" -by (simp add: sats_Forall_fm) - -theorem Forall_reflection: - "REFLECTS[\x. is_Forall(L,f(x),g(x)), - \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[\x. is_list(L,f(x),g(x)), + \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) == - \X[M]. \sn[M]. \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) == \zero[M]. \sn[M]. \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 \ nat; env \ list(A)|] + "[| nth(i,env) = x; i \ nat; env \ 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) == \p[M]. p \ 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 \ nat ==> is_formula_fm(x) \ formula" +by (simp add: is_formula_fm_def) + +lemma sats_is_formula_fm [simp]: + "[| x \ nat; env \ 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 \ nat; env \ list(A)|] + ==> is_formula(**A, x) <-> sats(A, is_formula_fm(i), env)" +by simp + +theorem is_formula_reflection: + "REFLECTS[\x. is_formula(L,f(x)), + \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) == \dp[M]. \sdp[M]. \hsdp[M]. - dp \ 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[\x. is_depth_apply(L,f(x),g(x),h(x)), - \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) == - \x y. is_lambda(M, list(A), - \env z. is_bool_of_o(M, \nx[M]. \ny[M]. - is_nth(M,x,env,nx) & is_nth(M,y,env,ny) & nx \ ny, z))" + \x y zz. \lA[M]. is_list(M,A,lA) --> + is_lambda(M, lA, + \env z. is_bool_of_o(M, + \nx[M]. \ny[M]. + is_nth(M,x,env,nx) & is_nth(M,y,env,ny) & nx \ 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) == - \x y. is_lambda(M, list(A), - \env z. - is_bool_of_o(M, \nx[M]. is_nth(M,x,env,nx) & is_nth(M,y,env,nx), z))" + \x y zz. \lA[M]. is_list(M,A,lA) --> + is_lambda(M, lA, + \env z. is_bool_of_o(M, + \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) == \env \ 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) == - \p q. is_lambda(M, list(A), - \env z. \hp[M]. \hq[M]. + \p q zz. \lA[M]. is_list(M,A,lA) --> + is_lambda(M, lA, \env z. \hp[M]. \hq[M]. (\rp[M]. is_depth_apply(M,h,p,rp) & fun_apply(M,rp,env,hp)) & (\rq[M]. is_depth_apply(M,h,q,rq) & fun_apply(M,rq,env,hq)) & - (\pq[M]. is_and(M,hp,hq,pq) & is_not(M,pq,z)))" + (\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) == - \p. is_lambda(M, list(A), - \env z. \rp[M]. is_depth_apply(M,h,p,rp) & - is_bool_of_o(M, - \x[M]. \xenv[M]. \hp[M]. - x\A --> is_Cons(M,x,env,xenv) --> - fun_apply(M,rp,xenv,hp) --> number1(M,hp), - z))" + \p zz. \lA[M]. is_list(M,A,lA) --> + is_lambda(M, lA, + \env z. \rp[M]. is_depth_apply(M,h,p,rp) & + is_bool_of_o(M, + \x[M]. \xenv[M]. \hp[M]. + x\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 == - \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)))" + \M A u f zz. + \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) == + \dp[M]. \sdp[M]. \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 \ nat; y \ nat; z \ nat |] ==> depth_apply_fm(x,y,z) \ formula" +by (simp add: depth_apply_fm_def) + +lemma sats_depth_apply_fm [simp]: + "[| x \ nat; y \ nat; z \ nat; env \ 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 \ nat; j \ nat; k \ nat; env \ 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[\x. is_depth_apply(L,f(x),g(x),h(x)), + \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) == + \x y zz. \lA[M]. is_list(M,A,lA) --> + is_lambda(M, lA, + \env z. is_bool_of_o(M, + \nx[M]. \ny[M]. + is_nth(M,x,env,nx) & is_nth(M,y,env,ny) & nx \ 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 \ nat; x \ nat; y \ nat; z \ nat |] + ==> satisfies_is_a_fm(A,x,y,z) \ formula" +by (simp add: satisfies_is_a_fm_def) + +lemma sats_satisfies_is_a_fm [simp]: + "[| u \ nat; x < length(env); y < length(env); z \ nat; env \ 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 \ nat; x < length(env); y < length(env); z \ nat; env \ 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[\x. satisfies_is_a(L,f(x),g(x),h(x),g'(x)), \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) == + \x y zz. \lA[M]. is_list(M,A,lA) --> + is_lambda(M, lA, + \env z. is_bool_of_o(M, + \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 \ nat; x \ nat; y \ nat; z \ nat |] + ==> satisfies_is_b_fm(A,x,y,z) \ formula" +by (simp add: satisfies_is_b_fm_def) + +lemma sats_satisfies_is_b_fm [simp]: + "[| u \ nat; x < length(env); y < length(env); z \ nat; env \ 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 \ nat; x < length(env); y < length(env); z \ nat; env \ 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[\x. satisfies_is_b(L,f(x),g(x),h(x),g'(x)), \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) == + \p q zz. \lA[M]. is_list(M,A,lA) --> + is_lambda(M, lA, \env z. \hp[M]. \hq[M]. + (\rp[M]. is_depth_apply(M,h,p,rp) & fun_apply(M,rp,env,hp)) & + (\rq[M]. is_depth_apply(M,h,q,rq) & fun_apply(M,rq,env,hq)) & + (\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 \ nat; h \ nat; x \ nat; y \ nat; z \ nat |] + ==> satisfies_is_c_fm(A,h,x,y,z) \ formula" +by (simp add: satisfies_is_c_fm_def) + +lemma sats_satisfies_is_c_fm [simp]: + "[| u \ nat; v \ nat; x \ nat; y \ nat; z \ nat; env \ 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 \ nat; v \ nat; x \ nat; y \ nat; z \ nat; env \ 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[\x. satisfies_is_c(L,f(x),g(x),h(x),g'(x),h'(x)), \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) == + \p zz. \lA[M]. is_list(M,A,lA) --> + is_lambda(M, lA, + \env z. \rp[M]. is_depth_apply(M,h,p,rp) & + is_bool_of_o(M, + \x[M]. \xenv[M]. \hp[M]. + x\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 \ nat; h \ nat; x \ nat; z \ nat |] + ==> satisfies_is_d_fm(A,h,x,z) \ formula" +by (simp add: satisfies_is_d_fm_def) + +lemma sats_satisfies_is_d_fm [simp]: + "[| u \ nat; x \ nat; y \ nat; z \ nat; env \ 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 \ nat; x \ nat; y \ nat; z \ nat; env \ 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[\x. satisfies_is_d(L,f(x),g(x),h(x),g'(x)), \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 == + \M A u f zz. + \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 \ nat; u \ nat; x \ nat; z \ nat |] + ==> satisfies_MH_fm(A,u,x,z) \ formula" +by (simp add: satisfies_MH_fm_def) + +lemma sats_satisfies_MH_fm [simp]: + "[| u \ nat; x \ nat; y \ nat; z \ nat; env \ 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 \ nat; x \ nat; y \ nat; z \ nat; env \ 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[\x. satisfies_MH(L,f(x),g(x),h(x),g'(x)), + \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)), \i x. \u \ Lset(i). u \ B \ (\y \ Lset(i). pair(**Lset(i), u, y, x) \ 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 \ 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 - - - diff -r af27202d6d1c -r 6f0c57def6d5 src/ZF/IsaMakefile --- 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 \