14 |
14 |
15 instance nat :: semigroup |
15 instance nat :: semigroup |
16 "m \<otimes> n \<equiv> m + n" |
16 "m \<otimes> n \<equiv> m + n" |
17 proof |
17 proof |
18 fix m n q :: nat |
18 fix m n q :: nat |
19 from semigroup_nat_def show "m \<otimes> n \<otimes> q = m \<otimes> (n \<otimes> q)" by simp |
19 from mult_nat_def show "m \<otimes> n \<otimes> q = m \<otimes> (n \<otimes> q)" by simp |
20 qed |
20 qed |
21 |
21 |
22 instance int :: semigroup |
22 instance int :: semigroup |
23 "k \<otimes> l \<equiv> k + l" |
23 "k \<otimes> l \<equiv> k + l" |
24 proof |
24 proof |
25 fix k l j :: int |
25 fix k l j :: int |
26 from semigroup_int_def show "k \<otimes> l \<otimes> j = k \<otimes> (l \<otimes> j)" by simp |
26 from mult_int_def show "k \<otimes> l \<otimes> j = k \<otimes> (l \<otimes> j)" by simp |
27 qed |
27 qed |
28 |
28 |
29 instance list :: (type) semigroup |
29 instance list :: (type) semigroup |
30 "xs \<otimes> ys \<equiv> xs @ ys" |
30 "xs \<otimes> ys \<equiv> xs @ ys" |
31 proof |
31 proof |
32 fix xs ys zs :: "'a list" |
32 fix xs ys zs :: "'a list" |
33 show "xs \<otimes> ys \<otimes> zs = xs \<otimes> (ys \<otimes> zs)" |
33 show "xs \<otimes> ys \<otimes> zs = xs \<otimes> (ys \<otimes> zs)" |
34 proof - |
34 proof - |
35 from semigroup_list_def have "\<And>xs ys\<Colon>'a list. xs \<otimes> ys \<equiv> xs @ ys" . |
35 from mult_list_def have "\<And>xs ys\<Colon>'a list. xs \<otimes> ys \<equiv> xs @ ys" . |
36 thus ?thesis by simp |
36 thus ?thesis by simp |
37 qed |
37 qed |
38 qed |
38 qed |
39 |
39 |
40 class monoidl = semigroup + |
40 class monoidl = semigroup + |
41 fixes one :: 'a ("\<^loc>\<one>") |
41 fixes one :: 'a ("\<^loc>\<one>") |
42 assumes neutl: "\<^loc>\<one> \<^loc>\<otimes> x = x" |
42 assumes neutl: "\<^loc>\<one> \<^loc>\<otimes> x = x" |
43 |
43 |
44 instance monoidl_num_def: nat :: monoidl and int :: monoidl |
44 instance nat :: monoidl and int :: monoidl |
45 "\<one> \<equiv> 0" |
45 "\<one> \<equiv> 0" |
46 "\<one> \<equiv> 0" |
46 "\<one> \<equiv> 0" |
47 proof |
47 proof |
48 fix n :: nat |
48 fix n :: nat |
49 from monoidl_num_def show "\<one> \<otimes> n = n" by simp |
49 from mult_nat_def one_nat_def show "\<one> \<otimes> n = n" by simp |
50 next |
50 next |
51 fix k :: int |
51 fix k :: int |
52 from monoidl_num_def show "\<one> \<otimes> k = k" by simp |
52 from mult_int_def one_int_def show "\<one> \<otimes> k = k" by simp |
53 qed |
53 qed |
54 |
54 |
55 instance list :: (type) monoidl |
55 instance list :: (type) monoidl |
56 "\<one> \<equiv> []" |
56 "\<one> \<equiv> []" |
57 proof |
57 proof |
58 fix xs :: "'a list" |
58 fix xs :: "'a list" |
59 show "\<one> \<otimes> xs = xs" |
59 show "\<one> \<otimes> xs = xs" |
60 proof - |
60 proof - |
61 from mult_list_def have "\<And>xs ys\<Colon>'a list. xs \<otimes> ys \<equiv> xs @ ys" . |
61 from mult_list_def have "\<And>xs ys\<Colon>'a list. xs \<otimes> ys \<equiv> xs @ ys" . |
62 moreover from monoidl_list_def have "\<one> \<equiv> []\<Colon>'a list" by simp |
62 moreover from one_list_def have "\<one> \<equiv> []\<Colon>'a list" by simp |
63 ultimately show ?thesis by simp |
63 ultimately show ?thesis by simp |
64 qed |
64 qed |
65 qed |
65 qed |
66 |
66 |
67 class monoid = monoidl + |
67 class monoid = monoidl + |
68 assumes neutr: "x \<^loc>\<otimes> \<^loc>\<one> = x" |
68 assumes neutr: "x \<^loc>\<otimes> \<^loc>\<one> = x" |
69 |
69 |
70 instance monoid_list_def: list :: (type) monoid |
70 instance list :: (type) monoid |
71 proof |
71 proof |
72 fix xs :: "'a list" |
72 fix xs :: "'a list" |
73 show "xs \<otimes> \<one> = xs" |
73 show "xs \<otimes> \<one> = xs" |
74 proof - |
74 proof - |
75 from mult_list_def have "\<And>xs ys\<Colon>'a list. xs \<otimes> ys \<equiv> xs @ ys" . |
75 from mult_list_def have "\<And>xs ys\<Colon>'a list. xs \<otimes> ys \<equiv> xs @ ys" . |
76 moreover from monoid_list_def have "\<one> \<equiv> []\<Colon>'a list" by simp |
76 moreover from one_list_def have "\<one> \<equiv> []\<Colon>'a list" by simp |
77 ultimately show ?thesis by simp |
77 ultimately show ?thesis by simp |
78 qed |
78 qed |
79 qed |
79 qed |
80 |
80 |
81 class monoid_comm = monoid + |
81 class monoid_comm = monoid + |
82 assumes comm: "x \<^loc>\<otimes> y = y \<^loc>\<otimes> x" |
82 assumes comm: "x \<^loc>\<otimes> y = y \<^loc>\<otimes> x" |
83 |
83 |
84 instance monoid_comm_num_def: nat :: monoid_comm and int :: monoid_comm |
84 instance nat :: monoid_comm and int :: monoid_comm |
85 proof |
85 proof |
86 fix n :: nat |
86 fix n :: nat |
87 from monoid_comm_num_def show "n \<otimes> \<one> = n" by simp |
87 from mult_nat_def one_nat_def show "n \<otimes> \<one> = n" by simp |
88 next |
88 next |
89 fix n m :: nat |
89 fix n m :: nat |
90 from monoid_comm_num_def show "n \<otimes> m = m \<otimes> n" by simp |
90 from mult_nat_def show "n \<otimes> m = m \<otimes> n" by simp |
91 next |
91 next |
92 fix k :: int |
92 fix k :: int |
93 from monoid_comm_num_def show "k \<otimes> \<one> = k" by simp |
93 from mult_int_def one_int_def show "k \<otimes> \<one> = k" by simp |
94 next |
94 next |
95 fix k l :: int |
95 fix k l :: int |
96 from monoid_comm_num_def show "k \<otimes> l = l \<otimes> k" by simp |
96 from mult_int_def show "k \<otimes> l = l \<otimes> k" by simp |
97 qed |
97 qed |
98 |
98 |
99 context monoid |
99 context monoid |
100 begin |
100 begin |
101 |
101 |
179 fixes inv :: "'a \<Rightarrow> 'a" ("\<^loc>\<div> _" [81] 80) |
179 fixes inv :: "'a \<Rightarrow> 'a" ("\<^loc>\<div> _" [81] 80) |
180 assumes invl: "\<^loc>\<div> x \<^loc>\<otimes> x = \<^loc>\<one>" |
180 assumes invl: "\<^loc>\<div> x \<^loc>\<otimes> x = \<^loc>\<one>" |
181 |
181 |
182 class group_comm = group + monoid_comm |
182 class group_comm = group + monoid_comm |
183 |
183 |
184 instance group_comm_int_def: int :: group_comm |
184 instance int :: group_comm |
185 "\<div> k \<equiv> - (k\<Colon>int)" |
185 "\<div> k \<equiv> - (k\<Colon>int)" |
186 proof |
186 proof |
187 fix k :: int |
187 fix k :: int |
188 from group_comm_int_def show "\<div> k \<otimes> k = \<one>" by simp |
188 from mult_int_def one_int_def inv_int_def show "\<div> k \<otimes> k = \<one>" by simp |
189 qed |
189 qed |
190 |
190 |
191 lemma (in group) cancel: |
191 lemma (in group) cancel: |
192 "(x \<^loc>\<otimes> y = x \<^loc>\<otimes> z) = (y = z)" |
192 "(x \<^loc>\<otimes> y = x \<^loc>\<otimes> z) = (y = z)" |
193 proof |
193 proof |
294 |
294 |
295 lemma (in group) int_pow_one: |
295 lemma (in group) int_pow_one: |
296 "\<^loc>\<one> \<^loc>\<up> (k\<Colon>int) = \<^loc>\<one>" |
296 "\<^loc>\<one> \<^loc>\<up> (k\<Colon>int) = \<^loc>\<one>" |
297 using pow_def nat_pow_one inv_one by simp |
297 using pow_def nat_pow_one inv_one by simp |
298 |
298 |
299 instance semigroup_prod_def: * :: (semigroup, semigroup) semigroup |
299 instance * :: (semigroup, semigroup) semigroup |
300 mult_prod_def: "x \<otimes> y \<equiv> let (x1, x2) = x; (y1, y2) = y in |
300 mult_prod_def: "x \<otimes> y \<equiv> let (x1, x2) = x; (y1, y2) = y in |
301 (x1 \<otimes> y1, x2 \<otimes> y2)" |
301 (x1 \<otimes> y1, x2 \<otimes> y2)" |
302 by default (simp_all add: split_paired_all semigroup_prod_def assoc) |
302 by default (simp_all add: split_paired_all mult_prod_def assoc) |
303 |
303 |
304 instance monoidl_prod_def: * :: (monoidl, monoidl) monoidl |
304 instance * :: (monoidl, monoidl) monoidl |
305 one_prod_def: "\<one> \<equiv> (\<one>, \<one>)" |
305 one_prod_def: "\<one> \<equiv> (\<one>, \<one>)" |
306 by default (simp_all add: split_paired_all monoidl_prod_def neutl) |
306 by default (simp_all add: split_paired_all mult_prod_def one_prod_def neutl) |
307 |
307 |
308 instance monoid_prod_def: * :: (monoid, monoid) monoid |
308 instance * :: (monoid, monoid) monoid |
309 by default (simp_all add: split_paired_all monoid_prod_def neutr) |
309 by default (simp_all add: split_paired_all mult_prod_def one_prod_def neutr) |
310 |
310 |
311 instance monoid_comm_prod_def: * :: (monoid_comm, monoid_comm) monoid_comm |
311 instance * :: (monoid_comm, monoid_comm) monoid_comm |
312 by default (simp_all add: split_paired_all monoidl_prod_def comm) |
312 by default (simp_all add: split_paired_all mult_prod_def comm) |
313 |
313 |
314 instance group_prod_def: * :: (group, group) group |
314 instance * :: (group, group) group |
315 inv_prod_def: "\<div> x \<equiv> let (x1, x2) = x in (\<div> x1, \<div> x2)" |
315 inv_prod_def: "\<div> x \<equiv> let (x1, x2) = x in (\<div> x1, \<div> x2)" |
316 by default (simp_all add: split_paired_all group_prod_def invl) |
316 by default (simp_all add: split_paired_all mult_prod_def one_prod_def inv_prod_def invl) |
317 |
317 |
318 instance group_comm_prod_def: * :: (group_comm, group_comm) group_comm |
318 instance * :: (group_comm, group_comm) group_comm |
319 by default (simp_all add: split_paired_all group_prod_def comm) |
319 by default (simp_all add: split_paired_all mult_prod_def comm) |
320 |
320 |
321 definition |
321 definition |
322 "X a b c = (a \<otimes> \<one> \<otimes> b, a \<otimes> \<one> \<otimes> b, [a, b] \<otimes> \<one> \<otimes> [a, b, c])" |
322 "X a b c = (a \<otimes> \<one> \<otimes> b, a \<otimes> \<one> \<otimes> b, [a, b] \<otimes> \<one> \<otimes> [a, b, c])" |
323 definition |
323 definition |
324 "Y a b c = (a, \<div> a) \<otimes> \<one> \<otimes> \<div> (b, \<div> c)" |
324 "Y a b c = (a, \<div> a) \<otimes> \<one> \<otimes> \<div> (b, \<div> c)" |