1 (* Title: ZF/AC/rel_is_fun.ML |
1 (* Title: ZF/AC/rel_is_fun.ML |
2 ID: $Id$ |
2 ID: $Id$ |
3 Author: Krzysztof Gr`abczewski |
3 Author: Krzysztof Grabczewski |
4 |
4 |
5 Lemmas needed to state when a finite relation is a function. |
5 Lemmas needed to state when a finite relation is a function. |
6 |
6 |
7 The criteria are cardinalities of the relation and its domain. |
7 The criteria are cardinalities of the relation and its domain. |
8 Used in WO6WO1.ML |
8 Used in WO6WO1.ML |
9 *) |
9 *) |
10 |
10 |
11 (*Using AC we could trivially prove, for all u, domain(u) lepoll u*) |
11 (*Using AC we could trivially prove, for all u, domain(u) lepoll u*) |
12 goalw Cardinal.thy [lepoll_def] |
12 goalw Cardinal.thy [lepoll_def] |
13 "!!m. [| m:nat; u lepoll m |] ==> domain(u) lepoll m"; |
13 "!!m. [| m:nat; u lepoll m |] ==> domain(u) lepoll m"; |
14 by (eresolve_tac [exE] 1); |
14 by (etac exE 1); |
15 by (res_inst_tac [("x", |
15 by (res_inst_tac [("x", |
16 "lam x:domain(u). LEAST i. EX y. <x,y> : u & f`<x,y> = i")] exI 1); |
16 "lam x:domain(u). LEAST i. EX y. <x,y> : u & f`<x,y> = i")] exI 1); |
17 by (res_inst_tac [("d","%y. fst(converse(f)`y)")] lam_injective 1); |
17 by (res_inst_tac [("d","%y. fst(converse(f)`y)")] lam_injective 1); |
18 by (fast_tac (ZF_cs addIs [LeastI2, nat_into_Ord RS Ord_in_Ord, |
18 by (fast_tac (ZF_cs addIs [LeastI2, nat_into_Ord RS Ord_in_Ord, |
19 inj_is_fun RS apply_type]) 1); |
19 inj_is_fun RS apply_type]) 1); |
20 by (eresolve_tac [domainE] 1); |
20 by (etac domainE 1); |
21 by (forward_tac [inj_is_fun RS apply_type] 1 THEN (atac 1)); |
21 by (forward_tac [inj_is_fun RS apply_type] 1 THEN (atac 1)); |
22 by (resolve_tac [LeastI2] 1); |
22 by (rtac LeastI2 1); |
23 by (REPEAT (fast_tac (ZF_cs addIs [fst_conv, left_inverse RS ssubst] |
23 by (REPEAT (fast_tac (ZF_cs addIs [fst_conv, left_inverse RS ssubst] |
24 addSEs [nat_into_Ord RS Ord_in_Ord]) 1)); |
24 addSEs [nat_into_Ord RS Ord_in_Ord]) 1)); |
25 val lepoll_m_imp_domain_lepoll_m = result(); |
25 val lepoll_m_imp_domain_lepoll_m = result(); |
26 |
26 |
27 goal ZF.thy "!!r. [| <a,c> : r; c~=b |] ==> domain(r-{<a,b>}) = domain(r)"; |
27 goal ZF.thy "!!r. [| <a,c> : r; c~=b |] ==> domain(r-{<a,b>}) = domain(r)"; |
28 by (resolve_tac [equalityI] 1); |
28 by (rtac equalityI 1); |
29 by (fast_tac (ZF_cs addSIs [domain_mono]) 1); |
29 by (fast_tac (ZF_cs addSIs [domain_mono]) 1); |
30 by (resolve_tac [subsetI] 1); |
30 by (rtac subsetI 1); |
31 by (excluded_middle_tac "x = a" 1); |
31 by (excluded_middle_tac "x = a" 1); |
32 by (REPEAT (fast_tac (ZF_cs addSIs [domainI] addSEs [domainE]) 1)); |
32 by (REPEAT (fast_tac (ZF_cs addSIs [domainI] addSEs [domainE]) 1)); |
33 val domain_Diff_eq_domain = result(); |
33 val domain_Diff_eq_domain = result(); |
34 |
34 |
35 goalw Cardinal.thy [function_def] |
35 goalw Cardinal.thy [function_def] |