5 theory Nat_Class |
5 theory Nat_Class |
6 imports FOL |
6 imports FOL |
7 begin |
7 begin |
8 |
8 |
9 text \<open> |
9 text \<open> |
10 This is an abstract version of theory \<open>Nat\<close>. Instead of |
10 This is an abstract version of theory \<open>Nat\<close>. Instead of axiomatizing a |
11 axiomatizing a single type \<open>nat\<close> we define the class of all |
11 single type \<open>nat\<close> we define the class of all these types (up to |
12 these types (up to isomorphism). |
12 isomorphism). |
13 |
13 |
14 Note: The \<open>rec\<close> operator had to be made \emph{monomorphic}, |
14 Note: The \<open>rec\<close> operator had to be made \<^emph>\<open>monomorphic\<close>, because class axioms |
15 because class axioms may not contain more than one type variable. |
15 may not contain more than one type variable. |
16 \<close> |
16 \<close> |
17 |
17 |
18 class nat = |
18 class nat = |
19 fixes Zero :: 'a ("0") |
19 fixes Zero :: 'a (\<open>0\<close>) |
20 and Suc :: "'a \<Rightarrow> 'a" |
20 and Suc :: "'a \<Rightarrow> 'a" |
21 and rec :: "'a \<Rightarrow> 'a \<Rightarrow> ('a \<Rightarrow> 'a \<Rightarrow> 'a) \<Rightarrow> 'a" |
21 and rec :: "'a \<Rightarrow> 'a \<Rightarrow> ('a \<Rightarrow> 'a \<Rightarrow> 'a) \<Rightarrow> 'a" |
22 assumes induct: "P(0) \<Longrightarrow> (\<And>x. P(x) \<Longrightarrow> P(Suc(x))) \<Longrightarrow> P(n)" |
22 assumes induct: "P(0) \<Longrightarrow> (\<And>x. P(x) \<Longrightarrow> P(Suc(x))) \<Longrightarrow> P(n)" |
23 and Suc_inject: "Suc(m) = Suc(n) \<Longrightarrow> m = n" |
23 and Suc_inject: "Suc(m) = Suc(n) \<Longrightarrow> m = n" |
24 and Suc_neq_Zero: "Suc(m) = 0 \<Longrightarrow> R" |
24 and Suc_neq_Zero: "Suc(m) = 0 \<Longrightarrow> R" |
25 and rec_Zero: "rec(0, a, f) = a" |
25 and rec_Zero: "rec(0, a, f) = a" |
26 and rec_Suc: "rec(Suc(m), a, f) = f(m, rec(m, a, f))" |
26 and rec_Suc: "rec(Suc(m), a, f) = f(m, rec(m, a, f))" |
27 begin |
27 begin |
28 |
28 |
29 definition add :: "'a \<Rightarrow> 'a \<Rightarrow> 'a" (infixl "+" 60) |
29 definition add :: "'a \<Rightarrow> 'a \<Rightarrow> 'a" (infixl \<open>+\<close> 60) |
30 where "m + n = rec(m, n, \<lambda>x y. Suc(y))" |
30 where "m + n = rec(m, n, \<lambda>x y. Suc(y))" |
31 |
31 |
32 lemma Suc_n_not_n: "Suc(k) \<noteq> (k::'a)" |
32 lemma Suc_n_not_n: "Suc(k) \<noteq> (k::'a)" |
33 apply (rule_tac n = k in induct) |
33 apply (rule_tac n = k in induct) |
34 apply (rule notI) |
34 apply (rule notI) |