src/ZF/nat.ML
author clasohm
Thu Sep 16 12:20:38 1993 +0200 (1993-09-16)
changeset 0 a5a9c433f639
child 6 8ce8c4d13d4d
permissions -rw-r--r--
Initial revision
clasohm@0
     1
(*  Title: 	ZF/nat.ML
clasohm@0
     2
    ID:         $Id$
clasohm@0
     3
    Author: 	Lawrence C Paulson, Cambridge University Computer Laboratory
clasohm@0
     4
    Copyright   1992  University of Cambridge
clasohm@0
     5
clasohm@0
     6
For nat.thy.  Natural numbers in Zermelo-Fraenkel Set Theory 
clasohm@0
     7
*)
clasohm@0
     8
clasohm@0
     9
open Nat;
clasohm@0
    10
clasohm@0
    11
goal Nat.thy "bnd_mono(Inf, %X. {0} Un {succ(i). i:X})";
clasohm@0
    12
by (rtac bnd_monoI 1);
clasohm@0
    13
by (REPEAT (ares_tac [subset_refl, RepFun_mono, Un_mono] 2)); 
clasohm@0
    14
by (cut_facts_tac [infinity] 1);
clasohm@0
    15
by (fast_tac ZF_cs 1);
clasohm@0
    16
val nat_bnd_mono = result();
clasohm@0
    17
clasohm@0
    18
(* nat = {0} Un {succ(x). x:nat} *)
clasohm@0
    19
val nat_unfold = nat_bnd_mono RS (nat_def RS def_lfp_Tarski);
clasohm@0
    20
clasohm@0
    21
(** Type checking of 0 and successor **)
clasohm@0
    22
clasohm@0
    23
goal Nat.thy "0 : nat";
clasohm@0
    24
by (rtac (nat_unfold RS ssubst) 1);
clasohm@0
    25
by (rtac (singletonI RS UnI1) 1);
clasohm@0
    26
val nat_0I = result();
clasohm@0
    27
clasohm@0
    28
val prems = goal Nat.thy "n : nat ==> succ(n) : nat";
clasohm@0
    29
by (rtac (nat_unfold RS ssubst) 1);
clasohm@0
    30
by (rtac (RepFunI RS UnI2) 1);
clasohm@0
    31
by (resolve_tac prems 1);
clasohm@0
    32
val nat_succI = result();
clasohm@0
    33
clasohm@0
    34
goalw Nat.thy [one_def] "1 : nat";
clasohm@0
    35
by (rtac (nat_0I RS nat_succI) 1);
clasohm@0
    36
val nat_1I = result();
clasohm@0
    37
clasohm@0
    38
goal Nat.thy "bool <= nat";
clasohm@0
    39
by (REPEAT (ares_tac [subsetI,nat_0I,nat_1I] 1 ORELSE etac boolE 1));
clasohm@0
    40
val bool_subset_nat = result();
clasohm@0
    41
clasohm@0
    42
val bool_into_nat = bool_subset_nat RS subsetD;
clasohm@0
    43
clasohm@0
    44
clasohm@0
    45
(** Injectivity properties and induction **)
clasohm@0
    46
clasohm@0
    47
(*Mathematical induction*)
clasohm@0
    48
val major::prems = goal Nat.thy
clasohm@0
    49
    "[| n: nat;  P(0);  !!x. [| x: nat;  P(x) |] ==> P(succ(x)) |] ==> P(n)";
clasohm@0
    50
by (rtac ([nat_def, nat_bnd_mono, major] MRS def_induct) 1);
clasohm@0
    51
by (fast_tac (ZF_cs addIs prems) 1);
clasohm@0
    52
val nat_induct = result();
clasohm@0
    53
clasohm@0
    54
(*Perform induction on n, then prove the n:nat subgoal using prems. *)
clasohm@0
    55
fun nat_ind_tac a prems i = 
clasohm@0
    56
    EVERY [res_inst_tac [("n",a)] nat_induct i,
clasohm@0
    57
	   rename_last_tac a ["1"] (i+2),
clasohm@0
    58
	   ares_tac prems i];
clasohm@0
    59
clasohm@0
    60
val major::prems = goal Nat.thy
clasohm@0
    61
    "[| n: nat;  n=0 ==> P;  !!x. [| x: nat; n=succ(x) |] ==> P |] ==> P";
clasohm@0
    62
br (major RS (nat_unfold RS equalityD1 RS subsetD) RS UnE) 1;
clasohm@0
    63
by (DEPTH_SOLVE (eresolve_tac [singletonE,RepFunE] 1
clasohm@0
    64
          ORELSE ares_tac prems 1));
clasohm@0
    65
val natE = result();
clasohm@0
    66
clasohm@0
    67
val prems = goal Nat.thy "n: nat ==> Ord(n)";
clasohm@0
    68
by (nat_ind_tac "n" prems 1);
clasohm@0
    69
by (REPEAT (ares_tac [Ord_0, Ord_succ] 1));
clasohm@0
    70
val naturals_are_ordinals = result();
clasohm@0
    71
clasohm@0
    72
goal Nat.thy "!!n. n: nat ==> n=0 | 0:n";
clasohm@0
    73
by (etac nat_induct 1);
clasohm@0
    74
by (fast_tac ZF_cs 1);
clasohm@0
    75
by (fast_tac (ZF_cs addIs [naturals_are_ordinals RS Ord_0_mem_succ]) 1);
clasohm@0
    76
val natE0 = result();
clasohm@0
    77
clasohm@0
    78
goal Nat.thy "Ord(nat)";
clasohm@0
    79
by (rtac OrdI 1);
clasohm@0
    80
by (etac (naturals_are_ordinals RS Ord_is_Transset) 2);
clasohm@0
    81
by (rewtac Transset_def);
clasohm@0
    82
by (rtac ballI 1);
clasohm@0
    83
by (etac nat_induct 1);
clasohm@0
    84
by (REPEAT (ares_tac [empty_subsetI,succ_subsetI] 1));
clasohm@0
    85
val Ord_nat = result();
clasohm@0
    86
clasohm@0
    87
(** Variations on mathematical induction **)
clasohm@0
    88
clasohm@0
    89
(*complete induction*)
clasohm@0
    90
val complete_induct = Ord_nat RSN (2, Ord_induct);
clasohm@0
    91
clasohm@0
    92
val prems = goal Nat.thy
clasohm@0
    93
    "[| m: nat;  n: nat;  \
clasohm@0
    94
\       !!x. [| x: nat;  m<=x;  P(x) |] ==> P(succ(x)) \
clasohm@0
    95
\    |] ==> m <= n --> P(m) --> P(n)";
clasohm@0
    96
by (nat_ind_tac "n" prems 1);
clasohm@0
    97
by (ALLGOALS
clasohm@0
    98
    (ASM_SIMP_TAC
clasohm@0
    99
     (ZF_ss addrews (prems@distrib_rews@[subset_empty_iff, subset_succ_iff, 
clasohm@0
   100
					 Ord_nat RS Ord_in_Ord]))));
clasohm@0
   101
val nat_induct_from_lemma = result();
clasohm@0
   102
clasohm@0
   103
(*Induction starting from m rather than 0*)
clasohm@0
   104
val prems = goal Nat.thy
clasohm@0
   105
    "[| m <= n;  m: nat;  n: nat;  \
clasohm@0
   106
\       P(m);  \
clasohm@0
   107
\       !!x. [| x: nat;  m<=x;  P(x) |] ==> P(succ(x)) \
clasohm@0
   108
\    |] ==> P(n)";
clasohm@0
   109
by (rtac (nat_induct_from_lemma RS mp RS mp) 1);
clasohm@0
   110
by (REPEAT (ares_tac prems 1));
clasohm@0
   111
val nat_induct_from = result();
clasohm@0
   112
clasohm@0
   113
(*Induction suitable for subtraction and less-than*)
clasohm@0
   114
val prems = goal Nat.thy
clasohm@0
   115
    "[| m: nat;  n: nat;  \
clasohm@0
   116
\       !!x. [| x: nat |] ==> P(x,0);  \
clasohm@0
   117
\       !!y. [| y: nat |] ==> P(0,succ(y));  \
clasohm@0
   118
\       !!x y. [| x: nat;  y: nat;  P(x,y) |] ==> P(succ(x),succ(y))  \
clasohm@0
   119
\    |] ==> P(m,n)";
clasohm@0
   120
by (res_inst_tac [("x","m")] bspec 1);
clasohm@0
   121
by (resolve_tac prems 2);
clasohm@0
   122
by (nat_ind_tac "n" prems 1);
clasohm@0
   123
by (rtac ballI 2);
clasohm@0
   124
by (nat_ind_tac "x" [] 2);
clasohm@0
   125
by (REPEAT (ares_tac (prems@[ballI]) 1 ORELSE etac bspec 1));
clasohm@0
   126
val diff_induct = result();
clasohm@0
   127
clasohm@0
   128
(** nat_case **)
clasohm@0
   129
clasohm@0
   130
goalw Nat.thy [nat_case_def] "nat_case(0,a,b) = a";
clasohm@0
   131
by (fast_tac (ZF_cs addIs [the_equality]) 1);
clasohm@0
   132
val nat_case_0 = result();
clasohm@0
   133
clasohm@0
   134
goalw Nat.thy [nat_case_def] "nat_case(succ(m),a,b) = b(m)";
clasohm@0
   135
by (fast_tac (ZF_cs addIs [the_equality]) 1);
clasohm@0
   136
val nat_case_succ = result();
clasohm@0
   137
clasohm@0
   138
val major::prems = goal Nat.thy
clasohm@0
   139
    "[| n: nat;  a: C(0);  !!m. m: nat ==> b(m): C(succ(m))  \
clasohm@0
   140
\    |] ==> nat_case(n,a,b) : C(n)";
clasohm@0
   141
by (rtac (major RS nat_induct) 1);
clasohm@0
   142
by (REPEAT (resolve_tac [nat_case_0 RS ssubst,
clasohm@0
   143
			 nat_case_succ RS ssubst] 1 
clasohm@0
   144
       THEN resolve_tac prems 1));
clasohm@0
   145
by (assume_tac 1);
clasohm@0
   146
val nat_case_type = result();
clasohm@0
   147
clasohm@0
   148
val prems = goalw Nat.thy [nat_case_def]
clasohm@0
   149
    "[| n=n';  a=a';  !!m z. b(m)=b'(m)  \
clasohm@0
   150
\    |] ==> nat_case(n,a,b)=nat_case(n',a',b')";
clasohm@0
   151
by (REPEAT (resolve_tac [the_cong,disj_cong,ex_cong] 1
clasohm@0
   152
     ORELSE EVERY1 (map rtac ((prems RL [ssubst]) @ [iff_refl]))));
clasohm@0
   153
val nat_case_cong = result();
clasohm@0
   154
clasohm@0
   155
clasohm@0
   156
(** nat_rec -- used to define eclose and transrec, then obsolete **)
clasohm@0
   157
clasohm@0
   158
val nat_rec_trans = wf_Memrel RS (nat_rec_def RS def_wfrec RS trans);
clasohm@0
   159
clasohm@0
   160
goal Nat.thy "nat_rec(0,a,b) = a";
clasohm@0
   161
by (rtac nat_rec_trans 1);
clasohm@0
   162
by (rtac nat_case_0 1);
clasohm@0
   163
val nat_rec_0 = result();
clasohm@0
   164
clasohm@0
   165
val [prem] = goal Nat.thy 
clasohm@0
   166
    "m: nat ==> nat_rec(succ(m),a,b) = b(m, nat_rec(m,a,b))";
clasohm@0
   167
val nat_rec_ss = ZF_ss 
clasohm@0
   168
      addcongs (mk_typed_congs Nat.thy [("b", "[i,i]=>i")])
clasohm@0
   169
      addrews [prem, nat_case_succ, nat_succI, Memrel_iff, 
clasohm@0
   170
	       vimage_singleton_iff];
clasohm@0
   171
by (rtac nat_rec_trans 1);
clasohm@0
   172
by (SIMP_TAC nat_rec_ss 1);
clasohm@0
   173
val nat_rec_succ = result();
clasohm@0
   174
clasohm@0
   175
(** The union of two natural numbers is a natural number -- their maximum **)
clasohm@0
   176
clasohm@0
   177
(*  [| ?i : nat; ?j : nat |] ==> ?i Un ?j : nat  *)
clasohm@0
   178
val Un_nat_type = standard (Ord_nat RSN (3,Ord_member_UnI));
clasohm@0
   179
clasohm@0
   180
(*  [| ?i : nat; ?j : nat |] ==> ?i Int ?j : nat  *)
clasohm@0
   181
val Int_nat_type = standard (Ord_nat RSN (3,Ord_member_IntI));
clasohm@0
   182