src/ZF/Nat.ML
changeset 4091 771b1f6422a8
parent 2929 4eefc6c22d41
child 4243 d7b8dd960514
equal deleted inserted replaced
4090:9f1eaab75e8c 4091:771b1f6422a8
    54 
    54 
    55 (*Mathematical induction*)
    55 (*Mathematical induction*)
    56 val major::prems = goal Nat.thy
    56 val major::prems = goal Nat.thy
    57     "[| n: nat;  P(0);  !!x. [| x: nat;  P(x) |] ==> P(succ(x)) |] ==> P(n)";
    57     "[| n: nat;  P(0);  !!x. [| x: nat;  P(x) |] ==> P(succ(x)) |] ==> P(n)";
    58 by (rtac ([nat_def, nat_bnd_mono, major] MRS def_induct) 1);
    58 by (rtac ([nat_def, nat_bnd_mono, major] MRS def_induct) 1);
    59 by (fast_tac (!claset addIs prems) 1);
    59 by (fast_tac (claset() addIs prems) 1);
    60 qed "nat_induct";
    60 qed "nat_induct";
    61 
    61 
    62 (*Perform induction on n, then prove the n:nat subgoal using prems. *)
    62 (*Perform induction on n, then prove the n:nat subgoal using prems. *)
    63 fun nat_ind_tac a prems i = 
    63 fun nat_ind_tac a prems i = 
    64     EVERY [res_inst_tac [("n",a)] nat_induct i,
    64     EVERY [res_inst_tac [("n",a)] nat_induct i,
    91 by (etac nat_induct 1);
    91 by (etac nat_induct 1);
    92 by (REPEAT (ares_tac [empty_subsetI,succ_subsetI] 1));
    92 by (REPEAT (ares_tac [empty_subsetI,succ_subsetI] 1));
    93 qed "Ord_nat";
    93 qed "Ord_nat";
    94 
    94 
    95 goalw Nat.thy [Limit_def] "Limit(nat)";
    95 goalw Nat.thy [Limit_def] "Limit(nat)";
    96 by (safe_tac (!claset addSIs [ltI, nat_succI, Ord_nat]));
    96 by (safe_tac (claset() addSIs [ltI, nat_succI, Ord_nat]));
    97 by (etac ltD 1);
    97 by (etac ltD 1);
    98 qed "Limit_nat";
    98 qed "Limit_nat";
    99 
    99 
   100 Addsimps [Ord_nat, Limit_nat];
   100 Addsimps [Ord_nat, Limit_nat];
   101 AddSIs   [Ord_nat, Limit_nat];
   101 AddSIs   [Ord_nat, Limit_nat];
   102 
   102 
   103 goal Nat.thy "!!i. Limit(i) ==> nat le i";
   103 goal Nat.thy "!!i. Limit(i) ==> nat le i";
   104 by (rtac subset_imp_le 1);
   104 by (rtac subset_imp_le 1);
   105 by (rtac subsetI 1);
   105 by (rtac subsetI 1);
   106 by (etac nat_induct 1);
   106 by (etac nat_induct 1);
   107 by (blast_tac (!claset addIs [Limit_has_succ RS ltD, ltI, Limit_is_Ord]) 2);
   107 by (blast_tac (claset() addIs [Limit_has_succ RS ltD, ltI, Limit_is_Ord]) 2);
   108 by (REPEAT (ares_tac [Limit_has_0 RS ltD,
   108 by (REPEAT (ares_tac [Limit_has_0 RS ltD,
   109                       Ord_nat, Limit_is_Ord] 1));
   109                       Ord_nat, Limit_is_Ord] 1));
   110 qed "nat_le_Limit";
   110 qed "nat_le_Limit";
   111 
   111 
   112 (* succ(i): nat ==> i: nat *)
   112 (* succ(i): nat ==> i: nat *)
   132 \       !!x. [| x: nat;  m le x;  P(x) |] ==> P(succ(x)) \
   132 \       !!x. [| x: nat;  m le x;  P(x) |] ==> P(succ(x)) \
   133 \    |] ==> m le n --> P(m) --> P(n)";
   133 \    |] ==> m le n --> P(m) --> P(n)";
   134 by (nat_ind_tac "n" prems 1);
   134 by (nat_ind_tac "n" prems 1);
   135 by (ALLGOALS
   135 by (ALLGOALS
   136     (asm_simp_tac
   136     (asm_simp_tac
   137      (!simpset addsimps (prems@distrib_simps@[le0_iff, le_succ_iff]))));
   137      (simpset() addsimps (prems@distrib_simps@[le0_iff, le_succ_iff]))));
   138 qed "nat_induct_from_lemma";
   138 qed "nat_induct_from_lemma";
   139 
   139 
   140 (*Induction starting from m rather than 0*)
   140 (*Induction starting from m rather than 0*)
   141 val prems = goal Nat.thy
   141 val prems = goal Nat.thy
   142     "[| m le n;  m: nat;  n: nat;  \
   142     "[| m le n;  m: nat;  n: nat;  \
   184 qed "succ_lt_induct";
   184 qed "succ_lt_induct";
   185 
   185 
   186 (** nat_case **)
   186 (** nat_case **)
   187 
   187 
   188 goalw Nat.thy [nat_case_def] "nat_case(a,b,0) = a";
   188 goalw Nat.thy [nat_case_def] "nat_case(a,b,0) = a";
   189 by (blast_tac (!claset addIs [the_equality]) 1);
   189 by (blast_tac (claset() addIs [the_equality]) 1);
   190 qed "nat_case_0";
   190 qed "nat_case_0";
   191 
   191 
   192 goalw Nat.thy [nat_case_def] "nat_case(a,b,succ(m)) = b(m)";
   192 goalw Nat.thy [nat_case_def] "nat_case(a,b,succ(m)) = b(m)";
   193 by (blast_tac (!claset addIs [the_equality]) 1);
   193 by (blast_tac (claset() addIs [the_equality]) 1);
   194 qed "nat_case_succ";
   194 qed "nat_case_succ";
   195 
   195 
   196 Addsimps [nat_case_0, nat_case_succ];
   196 Addsimps [nat_case_0, nat_case_succ];
   197 
   197 
   198 val major::prems = goal Nat.thy
   198 val major::prems = goal Nat.thy
   199     "[| n: nat;  a: C(0);  !!m. m: nat ==> b(m): C(succ(m))  \
   199     "[| n: nat;  a: C(0);  !!m. m: nat ==> b(m): C(succ(m))  \
   200 \    |] ==> nat_case(a,b,n) : C(n)";
   200 \    |] ==> nat_case(a,b,n) : C(n)";
   201 by (rtac (major RS nat_induct) 1);
   201 by (rtac (major RS nat_induct) 1);
   202 by (ALLGOALS (asm_simp_tac (!simpset addsimps prems)));
   202 by (ALLGOALS (asm_simp_tac (simpset() addsimps prems)));
   203 qed "nat_case_type";
   203 qed "nat_case_type";
   204 
   204 
   205 
   205 
   206 (** nat_rec -- used to define eclose and transrec, then obsolete;
   206 (** nat_rec -- used to define eclose and transrec, then obsolete;
   207     rec, from arith.ML, has fewer typing conditions **)
   207     rec, from arith.ML, has fewer typing conditions **)
   214 qed "nat_rec_0";
   214 qed "nat_rec_0";
   215 
   215 
   216 val [prem] = goal Nat.thy 
   216 val [prem] = goal Nat.thy 
   217     "m: nat ==> nat_rec(succ(m),a,b) = b(m, nat_rec(m,a,b))";
   217     "m: nat ==> nat_rec(succ(m),a,b) = b(m, nat_rec(m,a,b))";
   218 by (rtac nat_rec_trans 1);
   218 by (rtac nat_rec_trans 1);
   219 by (simp_tac (!simpset addsimps [prem, Memrel_iff, vimage_singleton_iff]) 1);
   219 by (simp_tac (simpset() addsimps [prem, Memrel_iff, vimage_singleton_iff]) 1);
   220 qed "nat_rec_succ";
   220 qed "nat_rec_succ";
   221 
   221 
   222 (** The union of two natural numbers is a natural number -- their maximum **)
   222 (** The union of two natural numbers is a natural number -- their maximum **)
   223 
   223 
   224 goal Nat.thy "!!i j. [| i: nat; j: nat |] ==> i Un j: nat";
   224 goal Nat.thy "!!i j. [| i: nat; j: nat |] ==> i Un j: nat";