122 \<forall>y[M]. y \<in> z \<longleftrightarrow> (\<exists>w[M]. w\<in>r & (\<exists>x[M]. x\<in>A & pair(M,x,y,w)))" |
122 \<forall>y[M]. y \<in> z \<longleftrightarrow> (\<exists>w[M]. w\<in>r & (\<exists>x[M]. x\<in>A & pair(M,x,y,w)))" |
123 |
123 |
124 definition |
124 definition |
125 is_range :: "[i=>o,i,i] => o" where |
125 is_range :: "[i=>o,i,i] => o" where |
126 \<comment> \<open>the cleaner |
126 \<comment> \<open>the cleaner |
127 @{term "\<exists>r'[M]. is_converse(M,r,r') & is_domain(M,r',z)"} |
127 \<^term>\<open>\<exists>r'[M]. is_converse(M,r,r') & is_domain(M,r',z)\<close> |
128 unfortunately needs an instance of separation in order to prove |
128 unfortunately needs an instance of separation in order to prove |
129 @{term "M(converse(r))"}.\<close> |
129 \<^term>\<open>M(converse(r))\<close>.\<close> |
130 "is_range(M,r,z) == |
130 "is_range(M,r,z) == |
131 \<forall>y[M]. y \<in> z \<longleftrightarrow> (\<exists>w[M]. w\<in>r & (\<exists>x[M]. pair(M,x,y,w)))" |
131 \<forall>y[M]. y \<in> z \<longleftrightarrow> (\<exists>w[M]. w\<in>r & (\<exists>x[M]. pair(M,x,y,w)))" |
132 |
132 |
133 definition |
133 definition |
134 is_field :: "[i=>o,i,i] => o" where |
134 is_field :: "[i=>o,i,i] => o" where |
553 by (blast intro: transM) |
553 by (blast intro: transM) |
554 |
554 |
555 text\<open>Simplifies proofs of equalities when there's an iff-equality |
555 text\<open>Simplifies proofs of equalities when there's an iff-equality |
556 available for rewriting, universally quantified over M. |
556 available for rewriting, universally quantified over M. |
557 But it's not the only way to prove such equalities: its |
557 But it's not the only way to prove such equalities: its |
558 premises @{term "M(A)"} and @{term "M(B)"} can be too strong.\<close> |
558 premises \<^term>\<open>M(A)\<close> and \<^term>\<open>M(B)\<close> can be too strong.\<close> |
559 lemma (in M_trivial) M_equalityI: |
559 lemma (in M_trivial) M_equalityI: |
560 "[| !!x. M(x) ==> x\<in>A \<longleftrightarrow> x\<in>B; M(A); M(B) |] ==> A=B" |
560 "[| !!x. M(x) ==> x\<in>A \<longleftrightarrow> x\<in>B; M(A); M(B) |] ==> A=B" |
561 by (blast intro!: equalityI dest: transM) |
561 by (blast intro!: equalityI dest: transM) |
562 |
562 |
563 |
563 |
696 apply (drule_tac x=A in rspec, clarify) |
696 apply (drule_tac x=A in rspec, clarify) |
697 apply (drule_tac z=Y in separationD, assumption, clarify) |
697 apply (drule_tac z=Y in separationD, assumption, clarify) |
698 apply (rule_tac x=y in rexI, force, assumption) |
698 apply (rule_tac x=y in rexI, force, assumption) |
699 done |
699 done |
700 |
700 |
701 subsubsection\<open>The Operator @{term is_Replace}\<close> |
701 subsubsection\<open>The Operator \<^term>\<open>is_Replace\<close>\<close> |
702 |
702 |
703 |
703 |
704 lemma is_Replace_cong [cong]: |
704 lemma is_Replace_cong [cong]: |
705 "[| A=A'; |
705 "[| A=A'; |
706 !!x y. [| M(x); M(y) |] ==> P(x,y) \<longleftrightarrow> P'(x,y); |
706 !!x y. [| M(x); M(y) |] ==> P(x,y) \<longleftrightarrow> P'(x,y); |
756 done |
756 done |
757 |
757 |
758 lemma Replace_conj_eq: "{y . x \<in> A, x\<in>A & y=f(x)} = {y . x\<in>A, y=f(x)}" |
758 lemma Replace_conj_eq: "{y . x \<in> A, x\<in>A & y=f(x)} = {y . x\<in>A, y=f(x)}" |
759 by simp |
759 by simp |
760 |
760 |
761 text\<open>Better than \<open>RepFun_closed\<close> when having the formula @{term "x\<in>A"} |
761 text\<open>Better than \<open>RepFun_closed\<close> when having the formula \<^term>\<open>x\<in>A\<close> |
762 makes relativization easier.\<close> |
762 makes relativization easier.\<close> |
763 lemma (in M_trivial) RepFun_closed2: |
763 lemma (in M_trivial) RepFun_closed2: |
764 "[| strong_replacement(M, \<lambda>x y. x\<in>A & y = f(x)); M(A); \<forall>x\<in>A. M(f(x)) |] |
764 "[| strong_replacement(M, \<lambda>x y. x\<in>A & y = f(x)); M(A); \<forall>x\<in>A. M(f(x)) |] |
765 ==> M(RepFun(A, %x. f(x)))" |
765 ==> M(RepFun(A, %x. f(x)))" |
766 apply (simp add: RepFun_def) |
766 apply (simp add: RepFun_def) |
767 apply (frule strong_replacement_closed, assumption) |
767 apply (frule strong_replacement_closed, assumption) |
768 apply (auto dest: transM simp add: Replace_conj_eq univalent_def) |
768 apply (auto dest: transM simp add: Replace_conj_eq univalent_def) |
769 done |
769 done |
770 |
770 |
771 subsubsection \<open>Absoluteness for @{term Lambda}\<close> |
771 subsubsection \<open>Absoluteness for \<^term>\<open>Lambda\<close>\<close> |
772 |
772 |
773 definition |
773 definition |
774 is_lambda :: "[i=>o, i, [i,i]=>o, i] => o" where |
774 is_lambda :: "[i=>o, i, [i,i]=>o, i] => o" where |
775 "is_lambda(M, A, is_b, z) == |
775 "is_lambda(M, A, is_b, z) == |
776 \<forall>p[M]. p \<in> z \<longleftrightarrow> |
776 \<forall>p[M]. p \<in> z \<longleftrightarrow> |
779 lemma (in M_trivial) lam_closed: |
779 lemma (in M_trivial) lam_closed: |
780 "[| strong_replacement(M, \<lambda>x y. y = <x,b(x)>); M(A); \<forall>x\<in>A. M(b(x)) |] |
780 "[| strong_replacement(M, \<lambda>x y. y = <x,b(x)>); M(A); \<forall>x\<in>A. M(b(x)) |] |
781 ==> M(\<lambda>x\<in>A. b(x))" |
781 ==> M(\<lambda>x\<in>A. b(x))" |
782 by (simp add: lam_def, blast intro: RepFun_closed dest: transM) |
782 by (simp add: lam_def, blast intro: RepFun_closed dest: transM) |
783 |
783 |
784 text\<open>Better than \<open>lam_closed\<close>: has the formula @{term "x\<in>A"}\<close> |
784 text\<open>Better than \<open>lam_closed\<close>: has the formula \<^term>\<open>x\<in>A\<close>\<close> |
785 lemma (in M_trivial) lam_closed2: |
785 lemma (in M_trivial) lam_closed2: |
786 "[|strong_replacement(M, \<lambda>x y. x\<in>A & y = \<langle>x, b(x)\<rangle>); |
786 "[|strong_replacement(M, \<lambda>x y. x\<in>A & y = \<langle>x, b(x)\<rangle>); |
787 M(A); \<forall>m[M]. m\<in>A \<longrightarrow> M(b(m))|] ==> M(Lambda(A,b))" |
787 M(A); \<forall>m[M]. m\<in>A \<longrightarrow> M(b(m))|] ==> M(Lambda(A,b))" |
788 apply (simp add: lam_def) |
788 apply (simp add: lam_def) |
789 apply (blast intro: RepFun_closed2 dest: transM) |
789 apply (blast intro: RepFun_closed2 dest: transM) |
1222 done |
1222 done |
1223 |
1223 |
1224 lemma (in M_basic) composition_abs [simp]: |
1224 lemma (in M_basic) composition_abs [simp]: |
1225 "[| M(r); M(s); M(t) |] ==> composition(M,r,s,t) \<longleftrightarrow> t = r O s" |
1225 "[| M(r); M(s); M(t) |] ==> composition(M,r,s,t) \<longleftrightarrow> t = r O s" |
1226 apply safe |
1226 apply safe |
1227 txt\<open>Proving @{term "composition(M, r, s, r O s)"}\<close> |
1227 txt\<open>Proving \<^term>\<open>composition(M, r, s, r O s)\<close>\<close> |
1228 prefer 2 |
1228 prefer 2 |
1229 apply (simp add: composition_def comp_def) |
1229 apply (simp add: composition_def comp_def) |
1230 apply (blast dest: transM) |
1230 apply (blast dest: transM) |
1231 txt\<open>Opposite implication\<close> |
1231 txt\<open>Opposite implication\<close> |
1232 apply (rule M_equalityI) |
1232 apply (rule M_equalityI) |
1331 done |
1331 done |
1332 |
1332 |
1333 |
1333 |
1334 subsubsection\<open>Functions and function space\<close> |
1334 subsubsection\<open>Functions and function space\<close> |
1335 |
1335 |
1336 text\<open>The assumption @{term "M(A->B)"} is unusual, but essential: in |
1336 text\<open>The assumption \<^term>\<open>M(A->B)\<close> is unusual, but essential: in |
1337 all but trivial cases, A->B cannot be expected to belong to @{term M}.\<close> |
1337 all but trivial cases, A->B cannot be expected to belong to \<^term>\<open>M\<close>.\<close> |
1338 lemma (in M_basic) is_funspace_abs [simp]: |
1338 lemma (in M_basic) is_funspace_abs [simp]: |
1339 "[|M(A); M(B); M(F); M(A->B)|] ==> is_funspace(M,A,B,F) \<longleftrightarrow> F = A->B" |
1339 "[|M(A); M(B); M(F); M(A->B)|] ==> is_funspace(M,A,B,F) \<longleftrightarrow> F = A->B" |
1340 apply (simp add: is_funspace_def) |
1340 apply (simp add: is_funspace_def) |
1341 apply (rule iffI) |
1341 apply (rule iffI) |
1342 prefer 2 apply blast |
1342 prefer 2 apply blast |
1356 "[|M(n); M(B); M(n->B) |] ==> M(succ(n) -> B)" |
1356 "[|M(n); M(B); M(n->B) |] ==> M(succ(n) -> B)" |
1357 apply (insert funspace_succ_replacement [of n], simp) |
1357 apply (insert funspace_succ_replacement [of n], simp) |
1358 apply (force simp add: succ_fun_eq2 univalent_def) |
1358 apply (force simp add: succ_fun_eq2 univalent_def) |
1359 done |
1359 done |
1360 |
1360 |
1361 text\<open>@{term M} contains all finite function spaces. Needed to prove the |
1361 text\<open>\<^term>\<open>M\<close> contains all finite function spaces. Needed to prove the |
1362 absoluteness of transitive closure. See the definition of |
1362 absoluteness of transitive closure. See the definition of |
1363 \<open>rtrancl_alt\<close> in in \<open>WF_absolute.thy\<close>.\<close> |
1363 \<open>rtrancl_alt\<close> in in \<open>WF_absolute.thy\<close>.\<close> |
1364 lemma (in M_basic) finite_funspace_closed [intro,simp]: |
1364 lemma (in M_basic) finite_funspace_closed [intro,simp]: |
1365 "[|n\<in>nat; M(B)|] ==> M(n->B)" |
1365 "[|n\<in>nat; M(B)|] ==> M(n->B)" |
1366 apply (induct_tac n, simp) |
1366 apply (induct_tac n, simp) |
1426 |
1426 |
1427 subsection\<open>Relativization and Absoluteness for List Operators\<close> |
1427 subsection\<open>Relativization and Absoluteness for List Operators\<close> |
1428 |
1428 |
1429 definition |
1429 definition |
1430 is_Nil :: "[i=>o, i] => o" where |
1430 is_Nil :: "[i=>o, i] => o" where |
1431 \<comment> \<open>because @{prop "[] \<equiv> Inl(0)"}\<close> |
1431 \<comment> \<open>because \<^prop>\<open>[] \<equiv> Inl(0)\<close>\<close> |
1432 "is_Nil(M,xs) == \<exists>zero[M]. empty(M,zero) & is_Inl(M,zero,xs)" |
1432 "is_Nil(M,xs) == \<exists>zero[M]. empty(M,zero) & is_Inl(M,zero,xs)" |
1433 |
1433 |
1434 definition |
1434 definition |
1435 is_Cons :: "[i=>o,i,i,i] => o" where |
1435 is_Cons :: "[i=>o,i,i,i] => o" where |
1436 \<comment> \<open>because @{prop "Cons(a, l) \<equiv> Inr(\<langle>a,l\<rangle>)"}\<close> |
1436 \<comment> \<open>because \<^prop>\<open>Cons(a, l) \<equiv> Inr(\<langle>a,l\<rangle>)\<close>\<close> |
1437 "is_Cons(M,a,l,Z) == \<exists>p[M]. pair(M,a,l,p) & is_Inr(M,p,Z)" |
1437 "is_Cons(M,a,l,Z) == \<exists>p[M]. pair(M,a,l,p) & is_Inr(M,p,Z)" |
1438 |
1438 |
1439 |
1439 |
1440 lemma (in M_trivial) Nil_in_M [intro,simp]: "M(Nil)" |
1440 lemma (in M_trivial) Nil_in_M [intro,simp]: "M(Nil)" |
1441 by (simp add: Nil_def) |
1441 by (simp add: Nil_def) |
1459 is_quasilist :: "[i=>o,i] => o" where |
1459 is_quasilist :: "[i=>o,i] => o" where |
1460 "is_quasilist(M,z) == is_Nil(M,z) | (\<exists>x[M]. \<exists>l[M]. is_Cons(M,x,l,z))" |
1460 "is_quasilist(M,z) == is_Nil(M,z) | (\<exists>x[M]. \<exists>l[M]. is_Cons(M,x,l,z))" |
1461 |
1461 |
1462 definition |
1462 definition |
1463 list_case' :: "[i, [i,i]=>i, i] => i" where |
1463 list_case' :: "[i, [i,i]=>i, i] => i" where |
1464 \<comment> \<open>A version of @{term list_case} that's always defined.\<close> |
1464 \<comment> \<open>A version of \<^term>\<open>list_case\<close> that's always defined.\<close> |
1465 "list_case'(a,b,xs) == |
1465 "list_case'(a,b,xs) == |
1466 if quasilist(xs) then list_case(a,b,xs) else 0" |
1466 if quasilist(xs) then list_case(a,b,xs) else 0" |
1467 |
1467 |
1468 definition |
1468 definition |
1469 is_list_case :: "[i=>o, i, [i,i,i]=>o, i, i] => o" where |
1469 is_list_case :: "[i=>o, i, [i,i,i]=>o, i, i] => o" where |
1473 (\<forall>x[M]. \<forall>l[M]. is_Cons(M,x,l,xs) \<longrightarrow> is_b(x,l,z)) & |
1473 (\<forall>x[M]. \<forall>l[M]. is_Cons(M,x,l,xs) \<longrightarrow> is_b(x,l,z)) & |
1474 (is_quasilist(M,xs) | empty(M,z))" |
1474 (is_quasilist(M,xs) | empty(M,z))" |
1475 |
1475 |
1476 definition |
1476 definition |
1477 hd' :: "i => i" where |
1477 hd' :: "i => i" where |
1478 \<comment> \<open>A version of @{term hd} that's always defined.\<close> |
1478 \<comment> \<open>A version of \<^term>\<open>hd\<close> that's always defined.\<close> |
1479 "hd'(xs) == if quasilist(xs) then hd(xs) else 0" |
1479 "hd'(xs) == if quasilist(xs) then hd(xs) else 0" |
1480 |
1480 |
1481 definition |
1481 definition |
1482 tl' :: "i => i" where |
1482 tl' :: "i => i" where |
1483 \<comment> \<open>A version of @{term tl} that's always defined.\<close> |
1483 \<comment> \<open>A version of \<^term>\<open>tl\<close> that's always defined.\<close> |
1484 "tl'(xs) == if quasilist(xs) then tl(xs) else 0" |
1484 "tl'(xs) == if quasilist(xs) then tl(xs) else 0" |
1485 |
1485 |
1486 definition |
1486 definition |
1487 is_hd :: "[i=>o,i,i] => o" where |
1487 is_hd :: "[i=>o,i,i] => o" where |
1488 \<comment> \<open>@{term "hd([]) = 0"} no constraints if not a list. |
1488 \<comment> \<open>\<^term>\<open>hd([]) = 0\<close> no constraints if not a list. |
1489 Avoiding implication prevents the simplifier's looping.\<close> |
1489 Avoiding implication prevents the simplifier's looping.\<close> |
1490 "is_hd(M,xs,H) == |
1490 "is_hd(M,xs,H) == |
1491 (is_Nil(M,xs) \<longrightarrow> empty(M,H)) & |
1491 (is_Nil(M,xs) \<longrightarrow> empty(M,H)) & |
1492 (\<forall>x[M]. \<forall>l[M]. ~ is_Cons(M,x,l,xs) | H=x) & |
1492 (\<forall>x[M]. \<forall>l[M]. ~ is_Cons(M,x,l,xs) | H=x) & |
1493 (is_quasilist(M,xs) | empty(M,H))" |
1493 (is_quasilist(M,xs) | empty(M,H))" |
1494 |
1494 |
1495 definition |
1495 definition |
1496 is_tl :: "[i=>o,i,i] => o" where |
1496 is_tl :: "[i=>o,i,i] => o" where |
1497 \<comment> \<open>@{term "tl([]) = []"}; see comments about @{term is_hd}\<close> |
1497 \<comment> \<open>\<^term>\<open>tl([]) = []\<close>; see comments about \<^term>\<open>is_hd\<close>\<close> |
1498 "is_tl(M,xs,T) == |
1498 "is_tl(M,xs,T) == |
1499 (is_Nil(M,xs) \<longrightarrow> T=xs) & |
1499 (is_Nil(M,xs) \<longrightarrow> T=xs) & |
1500 (\<forall>x[M]. \<forall>l[M]. ~ is_Cons(M,x,l,xs) | T=l) & |
1500 (\<forall>x[M]. \<forall>l[M]. ~ is_Cons(M,x,l,xs) | T=l) & |
1501 (is_quasilist(M,xs) | empty(M,T))" |
1501 (is_quasilist(M,xs) | empty(M,T))" |
1502 |
1502 |
1503 subsubsection\<open>@{term quasilist}: For Case-Splitting with @{term list_case'}\<close> |
1503 subsubsection\<open>\<^term>\<open>quasilist\<close>: For Case-Splitting with \<^term>\<open>list_case'\<close>\<close> |
1504 |
1504 |
1505 lemma [iff]: "quasilist(Nil)" |
1505 lemma [iff]: "quasilist(Nil)" |
1506 by (simp add: quasilist_def) |
1506 by (simp add: quasilist_def) |
1507 |
1507 |
1508 lemma [iff]: "quasilist(Cons(x,l))" |
1508 lemma [iff]: "quasilist(Cons(x,l))" |
1509 by (simp add: quasilist_def) |
1509 by (simp add: quasilist_def) |
1510 |
1510 |
1511 lemma list_imp_quasilist: "l \<in> list(A) ==> quasilist(l)" |
1511 lemma list_imp_quasilist: "l \<in> list(A) ==> quasilist(l)" |
1512 by (erule list.cases, simp_all) |
1512 by (erule list.cases, simp_all) |
1513 |
1513 |
1514 subsubsection\<open>@{term list_case'}, the Modified Version of @{term list_case}\<close> |
1514 subsubsection\<open>\<^term>\<open>list_case'\<close>, the Modified Version of \<^term>\<open>list_case\<close>\<close> |
1515 |
1515 |
1516 lemma list_case'_Nil [simp]: "list_case'(a,b,Nil) = a" |
1516 lemma list_case'_Nil [simp]: "list_case'(a,b,Nil) = a" |
1517 by (simp add: list_case'_def quasilist_def) |
1517 by (simp add: list_case'_def quasilist_def) |
1518 |
1518 |
1519 lemma list_case'_Cons [simp]: "list_case'(a,b,Cons(x,l)) = b(x,l)" |
1519 lemma list_case'_Cons [simp]: "list_case'(a,b,Cons(x,l)) = b(x,l)" |