author | paulson |
Fri, 20 Nov 1998 10:37:12 +0100 | |
changeset 5941 | 1db9fad40a4f |
parent 4152 | 451104c223e2 |
child 6176 | 707b6f9859d2 |
permissions | -rw-r--r-- |
1461 | 1 |
(* Title: ZF/AC/rel_is_fun.ML |
992 | 2 |
ID: $Id$ |
1461 | 3 |
Author: Krzysztof Grabczewski |
992 | 4 |
|
5 |
Lemmas needed to state when a finite relation is a function. |
|
6 |
||
7 |
The criteria are cardinalities of the relation and its domain. |
|
8 |
Used in WO6WO1.ML |
|
9 |
*) |
|
10 |
||
1070 | 11 |
(*Using AC we could trivially prove, for all u, domain(u) lepoll u*) |
992 | 12 |
goalw Cardinal.thy [lepoll_def] |
13 |
"!!m. [| m:nat; u lepoll m |] ==> domain(u) lepoll m"; |
|
1208
bc3093616ba4
Ran expandshort and corrected spelling of Grabczewski
paulson
parents:
1070
diff
changeset
|
14 |
by (etac exE 1); |
992 | 15 |
by (res_inst_tac [("x", |
1461 | 16 |
"lam x:domain(u). LEAST i. EX y. <x,y> : u & f`<x,y> = i")] exI 1); |
992 | 17 |
by (res_inst_tac [("d","%y. fst(converse(f)`y)")] lam_injective 1); |
4091 | 18 |
by (fast_tac (claset() addIs [LeastI2, nat_into_Ord RS Ord_in_Ord, |
1461 | 19 |
inj_is_fun RS apply_type]) 1); |
1208
bc3093616ba4
Ran expandshort and corrected spelling of Grabczewski
paulson
parents:
1070
diff
changeset
|
20 |
by (etac domainE 1); |
992 | 21 |
by (forward_tac [inj_is_fun RS apply_type] 1 THEN (atac 1)); |
1208
bc3093616ba4
Ran expandshort and corrected spelling of Grabczewski
paulson
parents:
1070
diff
changeset
|
22 |
by (rtac LeastI2 1); |
4091 | 23 |
by (REPEAT (fast_tac (claset() addSEs [nat_into_Ord RS Ord_in_Ord] |
24 |
addss (simpset() addsimps [left_inverse])) 1)); |
|
3731 | 25 |
qed "lepoll_m_imp_domain_lepoll_m"; |
992 | 26 |
|
1070 | 27 |
goalw Cardinal.thy [function_def] |
992 | 28 |
"!!r. [| succ(m) lepoll domain(r); r lepoll succ(m); m:nat |] ==> \ |
1461 | 29 |
\ function(r)"; |
4152 | 30 |
by Safe_tac; |
992 | 31 |
by (resolve_tac [excluded_middle RS disjE] 1 THEN (atac 2)); |
4091 | 32 |
by (fast_tac (claset() addSEs [lepoll_trans RS succ_lepoll_natE, |
1461 | 33 |
Diff_sing_lepoll RSN (2, lepoll_m_imp_domain_lepoll_m)] |
2469 | 34 |
addEs [not_sym RSN (2, domain_Diff_eq) RS subst]) 1); |
3731 | 35 |
qed "rel_domain_ex1"; |
992 | 36 |
|
37 |
goal Cardinal.thy |
|
38 |
"!!r. [| succ(m) lepoll domain(r); r lepoll succ(m); m:nat; \ |
|
1461 | 39 |
\ r<=A*B; A=domain(r) |] ==> r: A->B"; |
992 | 40 |
by (hyp_subst_tac 1); |
4091 | 41 |
by (asm_simp_tac (simpset() addsimps [Pi_iff, rel_domain_ex1]) 1); |
3731 | 42 |
qed "rel_is_fun"; |