src/ZF/AC/rel_is_fun.ML
changeset 1208 bc3093616ba4
parent 1070 d290a2f3b9b0
child 1461 6bcb44e4d6e5
equal deleted inserted replaced
1207:3f460842e919 1208:bc3093616ba4
     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]