src/FOL/ex/Nat.thy
author haftmann
Tue, 10 Jul 2007 17:30:50 +0200
changeset 23709 fd31da8f752a
parent 19819 14de4d05d275
child 25989 3267d0694d93
permissions -rw-r--r--
moved lfp_induct2 here
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
3115
24ed05500380 tuned comments;
wenzelm
parents: 1473
diff changeset
     1
(*  Title:      FOL/ex/Nat.thy
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     2
    ID:         $Id$
1473
e8d4606e6502 expanded tabs
clasohm
parents: 1322
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
17245
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
     7
header {* Theory of the natural numbers: Peano's axioms, primitive recursion *}
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
     8
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
     9
theory Nat
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
    10
imports FOL
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
    11
begin
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
    12
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
    13
typedecl nat
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
    14
arities nat :: "term"
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
    15
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
    16
consts
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
    17
  0 :: nat    ("0")
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
    18
  Suc :: "nat => nat"
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
    19
  rec :: "[nat, 'a, [nat,'a]=>'a] => 'a"
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
    20
  add :: "[nat, nat] => nat"    (infixl "+" 60)
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
    21
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
    22
axioms
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
    23
  induct:      "[| P(0);  !!x. P(x) ==> P(Suc(x)) |]  ==> P(n)"
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
    24
  Suc_inject:  "Suc(m)=Suc(n) ==> m=n"
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
    25
  Suc_neq_0:   "Suc(m)=0      ==> R"
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
    26
  rec_0:       "rec(0,a,f) = a"
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
    27
  rec_Suc:     "rec(Suc(m), a, f) = f(m, rec(m,a,f))"
19819
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    28
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    29
defs
17245
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
    30
  add_def:     "m+n == rec(m, n, %x y. Suc(y))"
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
    31
19819
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    32
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    33
subsection {* Proofs about the natural numbers *}
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    34
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    35
lemma Suc_n_not_n: "Suc(k) ~= k"
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    36
apply (rule_tac n = k in induct)
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    37
apply (rule notI)
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    38
apply (erule Suc_neq_0)
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    39
apply (rule notI)
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    40
apply (erule notE)
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    41
apply (erule Suc_inject)
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    42
done
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    43
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    44
lemma "(k+m)+n = k+(m+n)"
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    45
apply (rule induct)
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    46
back
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    47
back
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    48
back
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    49
back
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    50
back
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    51
back
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    52
oops
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    53
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    54
lemma add_0 [simp]: "0+n = n"
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    55
apply (unfold add_def)
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    56
apply (rule rec_0)
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    57
done
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    58
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    59
lemma add_Suc [simp]: "Suc(m)+n = Suc(m+n)"
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    60
apply (unfold add_def)
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    61
apply (rule rec_Suc)
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    62
done
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    63
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    64
lemma add_assoc: "(k+m)+n = k+(m+n)"
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    65
apply (rule_tac n = k in induct)
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    66
apply simp
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    67
apply simp
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    68
done
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    69
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    70
lemma add_0_right: "m+0 = m"
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    71
apply (rule_tac n = m in induct)
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    72
apply simp
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    73
apply simp
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    74
done
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    75
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    76
lemma add_Suc_right: "m+Suc(n) = Suc(m+n)"
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    77
apply (rule_tac n = m in induct)
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    78
apply simp_all
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    79
done
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    80
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    81
lemma
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    82
  assumes prem: "!!n. f(Suc(n)) = Suc(f(n))"
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    83
  shows "f(i+j) = i+f(j)"
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    84
apply (rule_tac n = i in induct)
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    85
apply simp
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    86
apply (simp add: prem)
14de4d05d275 removed obsolete ML files;
wenzelm
parents: 17245
diff changeset
    87
done
17245
1c519a3cca59 converted to Isar theory format;
wenzelm
parents: 3115
diff changeset
    88
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    89
end