src/HOL/Arith.thy
author clasohm
Mon Feb 05 21:27:16 1996 +0100 (1996-02-05)
changeset 1475 7f5a4cd08209
parent 1370 7361ac9b024d
child 1796 c42db9ab8728
permissions -rw-r--r--
expanded tabs; renamed subtype to typedef;
incorporated Konrad's changes
clasohm@923
     1
(*  Title:      HOL/Arith.thy
clasohm@923
     2
    ID:         $Id$
clasohm@923
     3
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
clasohm@923
     4
    Copyright   1993  University of Cambridge
clasohm@923
     5
clasohm@923
     6
Arithmetic operators and their definitions
clasohm@923
     7
*)
clasohm@923
     8
clasohm@923
     9
Arith = Nat +
clasohm@923
    10
clasohm@923
    11
instance
clasohm@923
    12
  nat :: {plus, minus, times}
clasohm@923
    13
clasohm@923
    14
consts
clasohm@1370
    15
  pred      :: nat => nat
clasohm@1370
    16
  div, mod  :: [nat, nat] => nat  (infixl 70)
clasohm@923
    17
clasohm@923
    18
defs
clasohm@923
    19
  pred_def  "pred(m) == nat_rec m 0 (%n r.n)"
clasohm@923
    20
  add_def   "m+n == nat_rec m n (%u v. Suc(v))"
clasohm@923
    21
  diff_def  "m-n == nat_rec n m (%u v. pred(v))"
clasohm@923
    22
  mult_def  "m*n == nat_rec m 0 (%u v. n + v)"
clasohm@1475
    23
mod_def "m mod n == wfrec (trancl pred_nat)
clasohm@1475
    24
                          (%f j. if j<n then j else f (j-n)) m"
clasohm@1475
    25
div_def "m div n == wfrec (trancl pred_nat) 
clasohm@1475
    26
                          (%f j. if j<n then 0 else Suc (f (j-n))) m"
clasohm@923
    27
end
clasohm@923
    28
clasohm@923
    29
(*"Difference" is subtraction of natural numbers.
clasohm@923
    30
  There are no negative numbers; we have
clasohm@972
    31
     m - n = 0  iff  m<=n   and     m - n = Suc(k) iff m)n.
clasohm@923
    32
  Also, nat_rec(m, 0, %z w.z) is pred(m).   *)
clasohm@923
    33