src/ZF/Constructible/Relative.thy
changeset 69593 3dda49e08b9d
parent 67443 3abf6a722518
child 71417 89d05db6dd1f
equal deleted inserted replaced
69592:a80d8ec6c998 69593:3dda49e08b9d
   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)"
  1548 apply (elim disjE exE)
  1548 apply (elim disjE exE)
  1549  apply (simp_all add: relation2_def)
  1549  apply (simp_all add: relation2_def)
  1550 done
  1550 done
  1551 
  1551 
  1552 
  1552 
  1553 subsubsection\<open>The Modified Operators @{term hd'} and @{term tl'}\<close>
  1553 subsubsection\<open>The Modified Operators \<^term>\<open>hd'\<close> and \<^term>\<open>tl'\<close>\<close>
  1554 
  1554 
  1555 lemma (in M_trivial) is_hd_Nil: "is_hd(M,[],Z) \<longleftrightarrow> empty(M,Z)"
  1555 lemma (in M_trivial) is_hd_Nil: "is_hd(M,[],Z) \<longleftrightarrow> empty(M,Z)"
  1556 by (simp add: is_hd_def)
  1556 by (simp add: is_hd_def)
  1557 
  1557 
  1558 lemma (in M_trivial) is_hd_Cons:
  1558 lemma (in M_trivial) is_hd_Cons: