7998
|
1 |
(*
|
|
2 |
Abstract class ring (commutative, with 1)
|
|
3 |
$Id$
|
|
4 |
Author: Clemens Ballarin, started 9 December 1996
|
|
5 |
*)
|
|
6 |
|
|
7 |
Ring = Main +
|
|
8 |
|
|
9 |
(* Syntactic class ring *)
|
|
10 |
|
|
11 |
axclass
|
10447
|
12 |
ringS < plus, minus, times, power, inverse
|
7998
|
13 |
|
|
14 |
consts
|
|
15 |
(* Basic rings *)
|
|
16 |
"<0>" :: 'a::ringS ("<0>")
|
|
17 |
"<1>" :: 'a::ringS ("<1>")
|
|
18 |
"--" :: ['a, 'a] => 'a::ringS (infixl 65)
|
|
19 |
|
|
20 |
(* Divisibility *)
|
|
21 |
assoc :: ['a::times, 'a] => bool (infixl 70)
|
|
22 |
irred :: 'a::ringS => bool
|
|
23 |
prime :: 'a::ringS => bool
|
|
24 |
|
|
25 |
translations
|
|
26 |
"a -- b" == "a + (-b)"
|
|
27 |
|
|
28 |
(* Class ring and ring axioms *)
|
|
29 |
|
|
30 |
axclass
|
|
31 |
ring < ringS
|
|
32 |
|
|
33 |
a_assoc "(a + b) + c = a + (b + c)"
|
|
34 |
l_zero "<0> + a = a"
|
|
35 |
l_neg "(-a) + a = <0>"
|
|
36 |
a_comm "a + b = b + a"
|
|
37 |
|
|
38 |
m_assoc "(a * b) * c = a * (b * c)"
|
|
39 |
l_one "<1> * a = a"
|
|
40 |
|
|
41 |
l_distr "(a + b) * c = a * c + b * c"
|
|
42 |
|
|
43 |
m_comm "a * b = b * a"
|
|
44 |
|
|
45 |
one_not_zero "<1> ~= <0>"
|
|
46 |
(* if <1> = <0>, then the ring has only one element! *)
|
|
47 |
|
10447
|
48 |
inverse_ax "inverse a = (if a dvd <1> then @x. a*x = <1> else <0>)"
|
|
49 |
divide_ax "a / b = a * inverse b"
|
7998
|
50 |
power_ax "a ^ n = nat_rec <1> (%u b. b * a) n"
|
|
51 |
|
|
52 |
defs
|
|
53 |
assoc_def "a assoc b == a dvd b & b dvd a"
|
|
54 |
irred_def "irred a == a ~= <0> & ~ a dvd <1>
|
|
55 |
& (ALL d. d dvd a --> d dvd <1> | a dvd d)"
|
|
56 |
prime_def "prime p == p ~= <0> & ~ p dvd <1>
|
|
57 |
& (ALL a b. p dvd (a*b) --> p dvd a | p dvd b)"
|
|
58 |
|
|
59 |
(* Integral domains *)
|
|
60 |
|
|
61 |
axclass
|
|
62 |
domain < ring
|
|
63 |
|
|
64 |
integral "a * b = <0> ==> a = <0> | b = <0>"
|
|
65 |
|
|
66 |
(* Factorial domains *)
|
|
67 |
|
|
68 |
axclass
|
|
69 |
factorial < domain
|
|
70 |
|
|
71 |
(*
|
|
72 |
Proper definition using divisor chain condition currently not supported.
|
|
73 |
factorial_divisor "wf {(a, b). a dvd b & ~ (b dvd a)}"
|
|
74 |
*)
|
|
75 |
factorial_divisor "True"
|
|
76 |
factorial_prime "irred a ==> prime a"
|
|
77 |
|
|
78 |
(* Euclidean domains *)
|
|
79 |
|
|
80 |
(*
|
|
81 |
axclass
|
|
82 |
euclidean < domain
|
|
83 |
|
|
84 |
euclidean_ax "b ~= <0> ==> Ex (% (q, r, e_size::('a::ringS)=>nat).
|
|
85 |
a = b * q + r & e_size r < e_size b)"
|
|
86 |
|
|
87 |
Nothing has been proved about euclidean domains, yet.
|
|
88 |
Design question:
|
|
89 |
Fix quo, rem and e_size as constants that are axiomatised with
|
|
90 |
euclidean_ax?
|
|
91 |
- advantage: more pragmatic and easier to use
|
|
92 |
- disadvantage: for every type, one definition of quo and rem will
|
|
93 |
be fixed, users may want to use differing ones;
|
|
94 |
also, it seems not possible to prove that fields are euclidean
|
|
95 |
domains, because that would require generic (type-independent)
|
|
96 |
definitions of quo and rem.
|
|
97 |
*)
|
|
98 |
|
|
99 |
(* Fields *)
|
|
100 |
|
|
101 |
axclass
|
|
102 |
field < ring
|
|
103 |
|
|
104 |
field_ax "a ~= <0> ==> a dvd <1>"
|
|
105 |
|
|
106 |
end
|