src/ZF/Nat.ML
author paulson
Fri, 16 Feb 1996 18:00:47 +0100
changeset 1512 ce37c64244c0
parent 1461 6bcb44e4d6e5
child 1610 60ab5844fe81
permissions -rw-r--r--
Elimination of fully-functorial style. Type tactic changed to a type abbrevation (from a datatype). Constructor tactic and function apply deleted.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
1461
6bcb44e4d6e5 expanded tabs
clasohm
parents: 829
diff changeset
     1
(*  Title:      ZF/nat.ML
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     2
    ID:         $Id$
1461
6bcb44e4d6e5 expanded tabs
clasohm
parents: 829
diff changeset
     3
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     4
    Copyright   1992  University of Cambridge
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     5
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     6
For nat.thy.  Natural numbers in Zermelo-Fraenkel Set Theory 
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     7
*)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     8
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     9
open Nat;
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    10
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    11
goal Nat.thy "bnd_mono(Inf, %X. {0} Un {succ(i). i:X})";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    12
by (rtac bnd_monoI 1);
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    13
by (REPEAT (ares_tac [subset_refl, RepFun_mono, Un_mono] 2)); 
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    14
by (cut_facts_tac [infinity] 1);
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    15
by (fast_tac ZF_cs 1);
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
    16
qed "nat_bnd_mono";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    17
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    18
(* nat = {0} Un {succ(x). x:nat} *)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    19
val nat_unfold = nat_bnd_mono RS (nat_def RS def_lfp_Tarski);
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    20
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    21
(** Type checking of 0 and successor **)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    22
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    23
goal Nat.thy "0 : nat";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    24
by (rtac (nat_unfold RS ssubst) 1);
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    25
by (rtac (singletonI RS UnI1) 1);
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
    26
qed "nat_0I";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    27
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    28
val prems = goal Nat.thy "n : nat ==> succ(n) : nat";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    29
by (rtac (nat_unfold RS ssubst) 1);
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    30
by (rtac (RepFunI RS UnI2) 1);
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    31
by (resolve_tac prems 1);
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
    32
qed "nat_succI";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    33
15
6c6d2f6e3185 ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents: 6
diff changeset
    34
goal Nat.thy "1 : nat";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    35
by (rtac (nat_0I RS nat_succI) 1);
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
    36
qed "nat_1I";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    37
829
ba28811c3496 natE0: deleted, since unused
lcp
parents: 760
diff changeset
    38
goal Nat.thy "2 : nat";
ba28811c3496 natE0: deleted, since unused
lcp
parents: 760
diff changeset
    39
by (rtac (nat_1I RS nat_succI) 1);
ba28811c3496 natE0: deleted, since unused
lcp
parents: 760
diff changeset
    40
qed "nat_2I";
ba28811c3496 natE0: deleted, since unused
lcp
parents: 760
diff changeset
    41
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    42
goal Nat.thy "bool <= nat";
120
09287f26bfb8 changed all co- and co_ to co
lcp
parents: 30
diff changeset
    43
by (REPEAT (ares_tac [subsetI,nat_0I,nat_1I] 1
1461
6bcb44e4d6e5 expanded tabs
clasohm
parents: 829
diff changeset
    44
            ORELSE eresolve_tac [boolE,ssubst] 1));
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
    45
qed "bool_subset_nat";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    46
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    47
val bool_into_nat = bool_subset_nat RS subsetD;
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    48
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    49
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    50
(** Injectivity properties and induction **)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    51
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    52
(*Mathematical induction*)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    53
val major::prems = goal Nat.thy
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    54
    "[| n: nat;  P(0);  !!x. [| x: nat;  P(x) |] ==> P(succ(x)) |] ==> P(n)";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    55
by (rtac ([nat_def, nat_bnd_mono, major] MRS def_induct) 1);
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    56
by (fast_tac (ZF_cs addIs prems) 1);
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
    57
qed "nat_induct";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    58
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    59
(*Perform induction on n, then prove the n:nat subgoal using prems. *)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    60
fun nat_ind_tac a prems i = 
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    61
    EVERY [res_inst_tac [("n",a)] nat_induct i,
1461
6bcb44e4d6e5 expanded tabs
clasohm
parents: 829
diff changeset
    62
           rename_last_tac a ["1"] (i+2),
6bcb44e4d6e5 expanded tabs
clasohm
parents: 829
diff changeset
    63
           ares_tac prems i];
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    64
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    65
val major::prems = goal Nat.thy
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    66
    "[| n: nat;  n=0 ==> P;  !!x. [| x: nat; n=succ(x) |] ==> P |] ==> P";
15
6c6d2f6e3185 ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents: 6
diff changeset
    67
by (rtac (major RS (nat_unfold RS equalityD1 RS subsetD) RS UnE) 1);
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    68
by (DEPTH_SOLVE (eresolve_tac [singletonE,RepFunE] 1
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    69
          ORELSE ares_tac prems 1));
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
    70
qed "natE";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    71
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    72
val prems = goal Nat.thy "n: nat ==> Ord(n)";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    73
by (nat_ind_tac "n" prems 1);
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    74
by (REPEAT (ares_tac [Ord_0, Ord_succ] 1));
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
    75
qed "nat_into_Ord";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    76
30
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
    77
(* i: nat ==> 0 le i *)
435
ca5356bd315a Addition of cardinals and order types, various tidying
lcp
parents: 120
diff changeset
    78
val nat_0_le = nat_into_Ord RS Ord_0_le;
ca5356bd315a Addition of cardinals and order types, various tidying
lcp
parents: 120
diff changeset
    79
ca5356bd315a Addition of cardinals and order types, various tidying
lcp
parents: 120
diff changeset
    80
val nat_le_refl = nat_into_Ord RS le_refl;
15
6c6d2f6e3185 ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents: 6
diff changeset
    81
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    82
goal Nat.thy "Ord(nat)";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    83
by (rtac OrdI 1);
435
ca5356bd315a Addition of cardinals and order types, various tidying
lcp
parents: 120
diff changeset
    84
by (etac (nat_into_Ord RS Ord_is_Transset) 2);
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    85
by (rewtac Transset_def);
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    86
by (rtac ballI 1);
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    87
by (etac nat_induct 1);
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    88
by (REPEAT (ares_tac [empty_subsetI,succ_subsetI] 1));
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
    89
qed "Ord_nat";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    90
435
ca5356bd315a Addition of cardinals and order types, various tidying
lcp
parents: 120
diff changeset
    91
goalw Nat.thy [Limit_def] "Limit(nat)";
ca5356bd315a Addition of cardinals and order types, various tidying
lcp
parents: 120
diff changeset
    92
by (safe_tac (ZF_cs addSIs [ltI, nat_0I, nat_1I, nat_succI, Ord_nat]));
ca5356bd315a Addition of cardinals and order types, various tidying
lcp
parents: 120
diff changeset
    93
by (etac ltD 1);
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
    94
qed "Limit_nat";
435
ca5356bd315a Addition of cardinals and order types, various tidying
lcp
parents: 120
diff changeset
    95
484
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents: 435
diff changeset
    96
goal Nat.thy "!!i. Limit(i) ==> nat le i";
1461
6bcb44e4d6e5 expanded tabs
clasohm
parents: 829
diff changeset
    97
by (rtac subset_imp_le 1);
484
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents: 435
diff changeset
    98
by (rtac subsetI 1);
1461
6bcb44e4d6e5 expanded tabs
clasohm
parents: 829
diff changeset
    99
by (etac nat_induct 1);
484
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents: 435
diff changeset
   100
by (fast_tac (ZF_cs addIs [Limit_has_succ RS ltD, ltI, Limit_is_Ord]) 2);
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents: 435
diff changeset
   101
by (REPEAT (ares_tac [Limit_has_0 RS ltD,
1461
6bcb44e4d6e5 expanded tabs
clasohm
parents: 829
diff changeset
   102
                      Ord_nat, Limit_is_Ord] 1));
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
   103
qed "nat_le_Limit";
484
70b789956bd3 Axiom of choice, cardinality results, etc.
lcp
parents: 435
diff changeset
   104
15
6c6d2f6e3185 ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents: 6
diff changeset
   105
(* succ(i): nat ==> i: nat *)
6c6d2f6e3185 ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents: 6
diff changeset
   106
val succ_natD = [succI1, asm_rl, Ord_nat] MRS Ord_trans;
6c6d2f6e3185 ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents: 6
diff changeset
   107
6c6d2f6e3185 ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents: 6
diff changeset
   108
(* [| succ(i): k;  k: nat |] ==> i: k *)
435
ca5356bd315a Addition of cardinals and order types, various tidying
lcp
parents: 120
diff changeset
   109
val succ_in_naturalD = [succI1, asm_rl, nat_into_Ord] MRS Ord_trans;
15
6c6d2f6e3185 ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents: 6
diff changeset
   110
30
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   111
goal Nat.thy "!!m n. [| m<n;  n: nat |] ==> m: nat";
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   112
by (etac ltE 1);
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   113
by (etac (Ord_nat RSN (3,Ord_trans)) 1);
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   114
by (assume_tac 1);
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
   115
qed "lt_nat_in_nat";
30
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   116
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   117
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   118
(** Variations on mathematical induction **)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   119
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   120
(*complete induction*)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   121
val complete_induct = Ord_nat RSN (2, Ord_induct);
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   122
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   123
val prems = goal Nat.thy
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   124
    "[| m: nat;  n: nat;  \
30
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   125
\       !!x. [| x: nat;  m le x;  P(x) |] ==> P(succ(x)) \
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   126
\    |] ==> m le n --> P(m) --> P(n)";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   127
by (nat_ind_tac "n" prems 1);
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   128
by (ALLGOALS
6
8ce8c4d13d4d Installation of new simplifier for ZF. Deleted all congruence rules not
lcp
parents: 0
diff changeset
   129
    (asm_simp_tac
30
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   130
     (ZF_ss addsimps (prems@distrib_rews@[le0_iff, le_succ_iff]))));
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
   131
qed "nat_induct_from_lemma";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   132
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   133
(*Induction starting from m rather than 0*)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   134
val prems = goal Nat.thy
30
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   135
    "[| m le n;  m: nat;  n: nat;  \
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   136
\       P(m);  \
30
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   137
\       !!x. [| x: nat;  m le x;  P(x) |] ==> P(succ(x)) \
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   138
\    |] ==> P(n)";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   139
by (rtac (nat_induct_from_lemma RS mp RS mp) 1);
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   140
by (REPEAT (ares_tac prems 1));
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
   141
qed "nat_induct_from";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   142
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   143
(*Induction suitable for subtraction and less-than*)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   144
val prems = goal Nat.thy
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   145
    "[| m: nat;  n: nat;  \
30
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   146
\       !!x. x: nat ==> P(x,0);  \
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   147
\       !!y. y: nat ==> P(0,succ(y));  \
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   148
\       !!x y. [| x: nat;  y: nat;  P(x,y) |] ==> P(succ(x),succ(y))  \
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   149
\    |] ==> P(m,n)";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   150
by (res_inst_tac [("x","m")] bspec 1);
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   151
by (resolve_tac prems 2);
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   152
by (nat_ind_tac "n" prems 1);
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   153
by (rtac ballI 2);
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   154
by (nat_ind_tac "x" [] 2);
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   155
by (REPEAT (ares_tac (prems@[ballI]) 1 ORELSE etac bspec 1));
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
   156
qed "diff_induct";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   157
15
6c6d2f6e3185 ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents: 6
diff changeset
   158
(** Induction principle analogous to trancl_induct **)
6c6d2f6e3185 ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents: 6
diff changeset
   159
6c6d2f6e3185 ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents: 6
diff changeset
   160
goal Nat.thy
6c6d2f6e3185 ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents: 6
diff changeset
   161
 "!!m. m: nat ==> P(m,succ(m)) --> (ALL x: nat. P(m,x) --> P(m,succ(x))) --> \
30
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   162
\                 (ALL n:nat. m<n --> P(m,n))";
15
6c6d2f6e3185 ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents: 6
diff changeset
   163
by (etac nat_induct 1);
6c6d2f6e3185 ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents: 6
diff changeset
   164
by (ALLGOALS
6c6d2f6e3185 ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents: 6
diff changeset
   165
    (EVERY' [rtac (impI RS impI), rtac (nat_induct RS ballI), assume_tac,
1461
6bcb44e4d6e5 expanded tabs
clasohm
parents: 829
diff changeset
   166
             fast_tac lt_cs, fast_tac lt_cs]));
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
   167
qed "succ_lt_induct_lemma";
15
6c6d2f6e3185 ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents: 6
diff changeset
   168
6c6d2f6e3185 ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents: 6
diff changeset
   169
val prems = goal Nat.thy
1461
6bcb44e4d6e5 expanded tabs
clasohm
parents: 829
diff changeset
   170
    "[| m<n;  n: nat;                                   \
6bcb44e4d6e5 expanded tabs
clasohm
parents: 829
diff changeset
   171
\       P(m,succ(m));                                   \
6bcb44e4d6e5 expanded tabs
clasohm
parents: 829
diff changeset
   172
\       !!x. [| x: nat;  P(m,x) |] ==> P(m,succ(x))     \
15
6c6d2f6e3185 ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents: 6
diff changeset
   173
\    |] ==> P(m,n)";
6c6d2f6e3185 ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents: 6
diff changeset
   174
by (res_inst_tac [("P4","P")] 
30
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   175
     (succ_lt_induct_lemma RS mp RS mp RS bspec RS mp) 1);
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   176
by (REPEAT (ares_tac (prems @ [ballI, impI, lt_nat_in_nat]) 1));
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
   177
qed "succ_lt_induct";
15
6c6d2f6e3185 ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents: 6
diff changeset
   178
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   179
(** nat_case **)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   180
6
8ce8c4d13d4d Installation of new simplifier for ZF. Deleted all congruence rules not
lcp
parents: 0
diff changeset
   181
goalw Nat.thy [nat_case_def] "nat_case(a,b,0) = a";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   182
by (fast_tac (ZF_cs addIs [the_equality]) 1);
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
   183
qed "nat_case_0";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   184
6
8ce8c4d13d4d Installation of new simplifier for ZF. Deleted all congruence rules not
lcp
parents: 0
diff changeset
   185
goalw Nat.thy [nat_case_def] "nat_case(a,b,succ(m)) = b(m)";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   186
by (fast_tac (ZF_cs addIs [the_equality]) 1);
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
   187
qed "nat_case_succ";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   188
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   189
val major::prems = goal Nat.thy
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   190
    "[| n: nat;  a: C(0);  !!m. m: nat ==> b(m): C(succ(m))  \
6
8ce8c4d13d4d Installation of new simplifier for ZF. Deleted all congruence rules not
lcp
parents: 0
diff changeset
   191
\    |] ==> nat_case(a,b,n) : C(n)";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   192
by (rtac (major RS nat_induct) 1);
30
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   193
by (ALLGOALS 
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   194
    (asm_simp_tac (ZF_ss addsimps (prems @ [nat_case_0, nat_case_succ]))));
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
   195
qed "nat_case_type";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   196
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   197
30
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   198
(** nat_rec -- used to define eclose and transrec, then obsolete;
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   199
    rec, from arith.ML, has fewer typing conditions **)
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   200
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   201
val nat_rec_trans = wf_Memrel RS (nat_rec_def RS def_wfrec RS trans);
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   202
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   203
goal Nat.thy "nat_rec(0,a,b) = a";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   204
by (rtac nat_rec_trans 1);
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   205
by (rtac nat_case_0 1);
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
   206
qed "nat_rec_0";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   207
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   208
val [prem] = goal Nat.thy 
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   209
    "m: nat ==> nat_rec(succ(m),a,b) = b(m, nat_rec(m,a,b))";
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   210
by (rtac nat_rec_trans 1);
15
6c6d2f6e3185 ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents: 6
diff changeset
   211
by (simp_tac (ZF_ss addsimps [prem, nat_case_succ, nat_succI, Memrel_iff, 
1461
6bcb44e4d6e5 expanded tabs
clasohm
parents: 829
diff changeset
   212
                              vimage_singleton_iff]) 1);
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
   213
qed "nat_rec_succ";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   214
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   215
(** The union of two natural numbers is a natural number -- their maximum **)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   216
30
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   217
goal Nat.thy "!!i j. [| i: nat; j: nat |] ==> i Un j: nat";
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   218
by (rtac (Un_least_lt RS ltD) 1);
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   219
by (REPEAT (ares_tac [ltI, Ord_nat] 1));
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
   220
qed "Un_nat_type";
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
   221
30
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   222
goal Nat.thy "!!i j. [| i: nat; j: nat |] ==> i Int j: nat";
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   223
by (rtac (Int_greatest_lt RS ltD) 1);
d49df4181f0d Retrying yet again after network problems
lcp
parents: 15
diff changeset
   224
by (REPEAT (ares_tac [ltI, Ord_nat] 1));
760
f0200e91b272 added qed and qed_goal[w]
clasohm
parents: 484
diff changeset
   225
qed "Int_nat_type";