27 (\<forall>j[M]. j\<in>n \<longrightarrow> |
27 (\<forall>j[M]. j\<in>n \<longrightarrow> |
28 (\<exists>fj[M]. \<exists>sj[M]. \<exists>fsj[M]. \<exists>ffp[M]. |
28 (\<exists>fj[M]. \<exists>sj[M]. \<exists>fsj[M]. \<exists>ffp[M]. |
29 fun_apply(M,f,j,fj) \<and> successor(M,j,sj) \<and> |
29 fun_apply(M,f,j,fj) \<and> successor(M,j,sj) \<and> |
30 fun_apply(M,f,sj,fsj) \<and> pair(M,fj,fsj,ffp) \<and> ffp \<in> r)))"*) |
30 fun_apply(M,f,sj,fsj) \<and> pair(M,fj,fsj,ffp) \<and> ffp \<in> r)))"*) |
31 definition |
31 definition |
32 rtran_closure_mem_fm :: "[i,i,i]=>i" where |
32 rtran_closure_mem_fm :: "[i,i,i]\<Rightarrow>i" where |
33 "rtran_closure_mem_fm(A,r,p) \<equiv> |
33 "rtran_closure_mem_fm(A,r,p) \<equiv> |
34 Exists(Exists(Exists( |
34 Exists(Exists(Exists( |
35 And(omega_fm(2), |
35 And(omega_fm(2), |
36 And(Member(1,2), |
36 And(Member(1,2), |
37 And(succ_fm(1,0), |
37 And(succ_fm(1,0), |
85 |
85 |
86 (* "rtran_closure(M,r,s) \<equiv> |
86 (* "rtran_closure(M,r,s) \<equiv> |
87 \<forall>A[M]. is_field(M,r,A) \<longrightarrow> |
87 \<forall>A[M]. is_field(M,r,A) \<longrightarrow> |
88 (\<forall>p[M]. p \<in> s \<longleftrightarrow> rtran_closure_mem(M,A,r,p))" *) |
88 (\<forall>p[M]. p \<in> s \<longleftrightarrow> rtran_closure_mem(M,A,r,p))" *) |
89 definition |
89 definition |
90 rtran_closure_fm :: "[i,i]=>i" where |
90 rtran_closure_fm :: "[i,i]\<Rightarrow>i" where |
91 "rtran_closure_fm(r,s) \<equiv> |
91 "rtran_closure_fm(r,s) \<equiv> |
92 Forall(Implies(field_fm(succ(r),0), |
92 Forall(Implies(field_fm(succ(r),0), |
93 Forall(Iff(Member(0,succ(succ(s))), |
93 Forall(Iff(Member(0,succ(succ(s))), |
94 rtran_closure_mem_fm(1,succ(succ(r)),0)))))" |
94 rtran_closure_mem_fm(1,succ(succ(r)),0)))))" |
95 |
95 |
120 subsubsection\<open>Transitive Closure of a Relation, Internalized\<close> |
120 subsubsection\<open>Transitive Closure of a Relation, Internalized\<close> |
121 |
121 |
122 (* "tran_closure(M,r,t) \<equiv> |
122 (* "tran_closure(M,r,t) \<equiv> |
123 \<exists>s[M]. rtran_closure(M,r,s) \<and> composition(M,r,s,t)" *) |
123 \<exists>s[M]. rtran_closure(M,r,s) \<and> composition(M,r,s,t)" *) |
124 definition |
124 definition |
125 tran_closure_fm :: "[i,i]=>i" where |
125 tran_closure_fm :: "[i,i]\<Rightarrow>i" where |
126 "tran_closure_fm(r,s) \<equiv> |
126 "tran_closure_fm(r,s) \<equiv> |
127 Exists(And(rtran_closure_fm(succ(r),0), composition_fm(succ(r),0,succ(s))))" |
127 Exists(And(rtran_closure_fm(succ(r),0), composition_fm(succ(r),0,succ(s))))" |
128 |
128 |
129 lemma tran_closure_type [TC]: |
129 lemma tran_closure_type [TC]: |
130 "\<lbrakk>x \<in> nat; y \<in> nat\<rbrakk> \<Longrightarrow> tran_closure_fm(x,y) \<in> formula" |
130 "\<lbrakk>x \<in> nat; y \<in> nat\<rbrakk> \<Longrightarrow> tran_closure_fm(x,y) \<in> formula" |
293 subsubsection\<open>The Formula \<^term>\<open>is_nth\<close>, Internalized\<close> |
293 subsubsection\<open>The Formula \<^term>\<open>is_nth\<close>, Internalized\<close> |
294 |
294 |
295 (* "is_nth(M,n,l,Z) \<equiv> |
295 (* "is_nth(M,n,l,Z) \<equiv> |
296 \<exists>X[M]. is_iterates(M, is_tl(M), l, n, X) \<and> is_hd(M,X,Z)" *) |
296 \<exists>X[M]. is_iterates(M, is_tl(M), l, n, X) \<and> is_hd(M,X,Z)" *) |
297 definition |
297 definition |
298 nth_fm :: "[i,i,i]=>i" where |
298 nth_fm :: "[i,i,i]\<Rightarrow>i" where |
299 "nth_fm(n,l,Z) \<equiv> |
299 "nth_fm(n,l,Z) \<equiv> |
300 Exists(And(is_iterates_fm(tl_fm(1,0), succ(l), succ(n), 0), |
300 Exists(And(is_iterates_fm(tl_fm(1,0), succ(l), succ(n), 0), |
301 hd_fm(0,succ(Z))))" |
301 hd_fm(0,succ(Z))))" |
302 |
302 |
303 lemma nth_fm_type [TC]: |
303 lemma nth_fm_type [TC]: |