6 Until now, our numerical examples have used the type of \textbf{natural
8 \isa{nat}. This is a recursive datatype generated by the constructors
9 zero and successor, so it works well with inductive proofs and primitive
10 recursive function definitions. HOL also provides the type
11 \isa{int} of \textbf{integers}, which lack induction but support true
12 subtraction. With subtraction, arithmetic reasoning is easier, which makes
13 the integers preferable to the natural numbers for
14 complicated arithmetic expressions, even if they are non-negative. There are also the types
15 \isa{rat}, \isa{real} and \isa{complex}: the rational, real and complex numbers. Isabelle has no
16 subtyping, so the numeric
17 types are distinct and there are functions to convert between them.
18 Most numeric operations are overloaded: the same symbol can be
19 used at all numeric types. Table~\ref{tab:overloading} in the appendix
20 shows the most important operations, together with the priorities of the
21 infix symbols. Algebraic properties are organized using type classes
22 around algebraic concepts such as rings and fields;
23 a property such as the commutativity of addition is a single theorem
24 (\isa{add_commute}) that applies to all numeric types.
26 \index{linear arithmetic}%
27 Many theorems involving numeric types can be proved automatically by
28 Isabelle's arithmetic decision procedure, the method
29 \methdx{arith}. Linear arithmetic comprises addition, subtraction
30 and multiplication by constant factors; subterms involving other operators
31 are regarded as variables. The procedure can be slow, especially if the
32 subgoal to be proved involves subtraction over type \isa{nat}, which
33 causes case splits. On types \isa{nat} and \isa{int}, \methdx{arith}
34 can deal with quantifiers---this is known as Presburger arithmetic---whereas on type \isa{real} it cannot.
36 The simplifier reduces arithmetic expressions in other
37 ways, such as dividing through by common factors. For problems that lie
38 outside the scope of automation, HOL provides hundreds of
39 theorems about multiplication, division, etc., that can be brought to
40 bear. You can locate them using Proof General's Find
41 button. A few lemmas are given below to show what
44 \subsection{Numeric Literals}
47 \index{numeric literals|(}%
48 The constants \cdx{0} and \cdx{1} are overloaded. They denote zero and one,
49 respectively, for all numeric types. Other values are expressed by numeric
50 literals, which consist of one or more decimal digits optionally preceeded by a minus sign (\isa{-}). Examples are \isa{2}, \isa{-3} and
51 \isa{441223334678}. Literals are available for the types of natural
52 numbers, integers, rationals, reals, etc.; they denote integer values of
55 Literals look like constants, but they abbreviate
56 terms representing the number in a two's complement binary notation.
57 Isabelle performs arithmetic on literals by rewriting rather
58 than using the hardware arithmetic. In most cases arithmetic
59 is fast enough, even for numbers in the millions. The arithmetic operations
60 provided for literals include addition, subtraction, multiplication,
61 integer division and remainder. Fractions of literals (expressed using
62 division) are reduced to lowest terms.
64 \begin{warn}\index{overloading!and arithmetic}
65 The arithmetic operators are
66 overloaded, so you must be careful to ensure that each numeric
67 expression refers to a specific type, if necessary by inserting
68 type constraints. Here is an example of what can go wrong:
71 \isacommand{lemma}\ "2\ *\ m\ =\ m\ +\ m"
74 Carefully observe how Isabelle displays the subgoal:
76 \ 1.\ (2::'a)\ *\ m\ =\ m\ +\ m
78 The type \isa{'a} given for the literal \isa{2} warns us that no numeric
79 type has been specified. The problem is underspecified. Given a type
80 constraint such as \isa{nat}, \isa{int} or \isa{real}, it becomes trivial.
84 \index{function@\isacommand {function} (command)!and numeric literals}
85 Numeric literals are not constructors and therefore
86 must not be used in patterns. For example, this declaration is
89 \isacommand{function}\ h\ \isakeyword{where}\isanewline
90 "h\ 3\ =\ 2"\isanewline
91 \isacharbar "h\ i\ \ =\ i"
94 You should use a conditional expression instead:
96 "h\ i\ =\ (if\ i\ =\ 3\ then\ 2\ else\ i)"
98 \index{numeric literals|)}
102 \subsection{The Type of Natural Numbers, {\tt\slshape nat}}
104 \index{natural numbers|(}\index{*nat (type)|(}%
105 This type requires no introduction: we have been using it from the
106 beginning. Hundreds of theorems about the natural numbers are
107 proved in the theories \isa{Nat} and \isa{Divides}.
108 Basic properties of addition and multiplication are available through the
109 axiomatic type class for semirings (\S\ref{sec:numeric-classes}).
111 \subsubsection{Literals}
112 \index{numeric literals!for type \protect\isa{nat}}%
113 The notational options for the natural numbers are confusing. Recall that an
114 overloaded constant can be defined independently for each type; the definition
115 of \cdx{1} for type \isa{nat} is
117 1\ \isasymequiv\ Suc\ 0
118 \rulename{One_nat_def}
120 This is installed as a simplification rule, so the simplifier will replace
121 every occurrence of \isa{1::nat} by \isa{Suc\ 0}. Literals are obviously
122 better than nested \isa{Suc}s at expressing large values. But many theorems,
123 including the rewrite rules for primitive recursive functions, can only be
124 applied to terms of the form \isa{Suc\ $n$}.
126 The following default simplification rules replace
127 small literals by zero and successor:
129 2\ +\ n\ =\ Suc\ (Suc\ n)
130 \rulename{add_2_eq_Suc}\isanewline
131 n\ +\ 2\ =\ Suc\ (Suc\ n)
132 \rulename{add_2_eq_Suc'}
134 It is less easy to transform \isa{100} into \isa{Suc\ 99} (for example), and
135 the simplifier will normally reverse this transformation. Novices should
136 express natural numbers using \isa{0} and \isa{Suc} only.
138 \subsubsection{Division}
139 \index{division!for type \protect\isa{nat}}%
140 The infix operators \isa{div} and \isa{mod} are overloaded.
141 Isabelle/HOL provides the basic facts about quotient and remainder
142 on the natural numbers:
144 m\ mod\ n\ =\ (if\ m\ <\ n\ then\ m\ else\ (m\ -\ n)\ mod\ n)
145 \rulename{mod_if}\isanewline
146 m\ div\ n\ *\ n\ +\ m\ mod\ n\ =\ m%
147 \rulenamedx{mod_div_equality}
150 Many less obvious facts about quotient and remainder are also provided.
153 a\ *\ b\ div\ c\ =\ a\ *\ (b\ div\ c)\ +\ a\ *\ (b\ mod\ c)\ div\ c%
154 \rulename{div_mult1_eq}\isanewline
155 a\ *\ b\ mod\ c\ =\ a\ *\ (b\ mod\ c)\ mod\ c%
156 \rulename{mod_mult_right_eq}\isanewline
157 a\ div\ (b*c)\ =\ a\ div\ b\ div\ c%
158 \rulename{div_mult2_eq}\isanewline
159 a\ mod\ (b*c)\ =\ b * (a\ div\ b\ mod\ c)\ +\ a\ mod\ b%
160 \rulename{mod_mult2_eq}\isanewline
161 0\ <\ c\ \isasymLongrightarrow \ (c\ *\ a)\ div\ (c\ *\ b)\ =\ a\ div\ b%
162 \rulename{div_mult_mult1}\isanewline
163 (m\ mod\ n)\ *\ k\ =\ (m\ *\ k)\ mod\ (n\ *\ k)
164 \rulenamedx{mod_mult_distrib}\isanewline
165 m\ \isasymle \ n\ \isasymLongrightarrow \ m\ div\ k\ \isasymle \ n\ div\ k%
166 \rulename{div_le_mono}
169 Surprisingly few of these results depend upon the
170 divisors' being nonzero.
171 \index{division!by zero}%
172 That is because division by
176 \rulename{DIVISION_BY_ZERO_DIV}\isanewline
178 \rulename{DIVISION_BY_ZERO_MOD}
180 In \isa{div_mult_mult1} above, one of
181 the two divisors (namely~\isa{c}) must still be nonzero.
183 The \textbf{divides} relation\index{divides relation}
184 has the standard definition, which
185 is overloaded over all numeric types:
187 m\ dvd\ n\ \isasymequiv\ {\isasymexists}k.\ n\ =\ m\ *\ k
191 Section~\ref{sec:proving-euclid} discusses proofs involving this
192 relation. Here are some of the facts proved about it:
194 \isasymlbrakk m\ dvd\ n;\ n\ dvd\ m\isasymrbrakk \ \isasymLongrightarrow \ m\ =\ n%
195 \rulenamedx{dvd_anti_sym}\isanewline
196 \isasymlbrakk k\ dvd\ m;\ k\ dvd\ n\isasymrbrakk \ \isasymLongrightarrow \ k\ dvd\ (m\ +\ n)
200 \subsubsection{Subtraction}
202 There are no negative natural numbers, so \isa{m\ -\ n} equals zero unless
203 \isa{m} exceeds~\isa{n}. The following is one of the few facts
204 about \isa{m\ -\ n} that is not subject to
205 the condition \isa{n\ \isasymle \ m}.
207 (m\ -\ n)\ *\ k\ =\ m\ *\ k\ -\ n\ *\ k%
208 \rulenamedx{diff_mult_distrib}
210 Natural number subtraction has few
211 nice properties; often you should remove it by simplifying with this split
214 P(a-b)\ =\ ((a<b\ \isasymlongrightarrow \ P\
215 0)\ \isasymand \ (\isasymforall d.\ a\ =\ b+d\ \isasymlongrightarrow \ P\
217 \rulename{nat_diff_split}
219 For example, splitting helps to prove the following fact.
221 \isacommand{lemma}\ "(n\ -\ 2)\ *\ (n\ +\ 2)\ =\ n\ *\ n\ -\ (4::nat)"\isanewline
222 \isacommand{apply}\ (simp\ split:\ nat_diff_split,\ clarify)\isanewline
223 \ 1.\ \isasymAnd d.\ \isasymlbrakk n\ <\ 2;\ n\ *\ n\ =\ 4\ +\ d\isasymrbrakk \ \isasymLongrightarrow \ d\ =\ 0
225 The result lies outside the scope of linear arithmetic, but
227 if we explicitly split \isa{n<2} as \isa{n=0} or \isa{n=1}:
229 \isacommand{apply}\ (subgoal_tac\ "n=0\ |\ n=1",\ force,\ arith)\isanewline
232 \index{natural numbers|)}\index{*nat (type)|)}
235 \subsection{The Type of Integers, {\tt\slshape int}}
237 \index{integers|(}\index{*int (type)|(}%
238 Reasoning methods for the integers resemble those for the natural numbers,
240 the constant \isa{Suc} are not available. HOL provides many lemmas for
241 proving inequalities involving integer multiplication and division, similar
242 to those shown above for type~\isa{nat}. The laws of addition, subtraction
243 and multiplication are available through the axiomatic type class for rings
244 (\S\ref{sec:numeric-classes}).
246 The \rmindex{absolute value} function \cdx{abs} is overloaded, and is
247 defined for all types that involve negative numbers, including the integers.
248 The \isa{arith} method can prove facts about \isa{abs} automatically,
249 though as it does so by case analysis, the cost can be exponential.
251 \isacommand{lemma}\ "abs\ (x+y)\ \isasymle \ abs\ x\ +\ abs\ (y\ ::\ int)"\isanewline
252 \isacommand{by}\ arith
255 For division and remainder,\index{division!by negative numbers}
256 the treatment of negative divisors follows
257 mathematical practice: the sign of the remainder follows that
260 0\ <\ b\ \isasymLongrightarrow \ 0\ \isasymle \ a\ mod\ b%
261 \rulename{pos_mod_sign}\isanewline
262 0\ <\ b\ \isasymLongrightarrow \ a\ mod\ b\ <\ b%
263 \rulename{pos_mod_bound}\isanewline
264 b\ <\ 0\ \isasymLongrightarrow \ a\ mod\ b\ \isasymle \ 0
265 \rulename{neg_mod_sign}\isanewline
266 b\ <\ 0\ \isasymLongrightarrow \ b\ <\ a\ mod\ b%
267 \rulename{neg_mod_bound}
269 ML treats negative divisors in the same way, but most computer hardware
270 treats signed operands using the same rules as for multiplication.
271 Many facts about quotients and remainders are provided:
273 (a\ +\ b)\ div\ c\ =\isanewline
274 a\ div\ c\ +\ b\ div\ c\ +\ (a\ mod\ c\ +\ b\ mod\ c)\ div\ c%
275 \rulename{zdiv_zadd1_eq}
277 (a\ +\ b)\ mod\ c\ =\ (a\ mod\ c\ +\ b\ mod\ c)\ mod\ c%
278 \rulename{mod_add_eq}
282 (a\ *\ b)\ div\ c\ =\ a\ *\ (b\ div\ c)\ +\ a\ *\ (b\ mod\ c)\ div\ c%
283 \rulename{zdiv_zmult1_eq}\isanewline
284 (a\ *\ b)\ mod\ c\ =\ a\ *\ (b\ mod\ c)\ mod\ c%
285 \rulename{zmod_zmult1_eq}
289 0\ <\ c\ \isasymLongrightarrow \ a\ div\ (b*c)\ =\ a\ div\ b\ div\ c%
290 \rulename{zdiv_zmult2_eq}\isanewline
291 0\ <\ c\ \isasymLongrightarrow \ a\ mod\ (b*c)\ =\ b*(a\ div\ b\ mod\
293 \rulename{zmod_zmult2_eq}
295 The last two differ from their natural number analogues by requiring
296 \isa{c} to be positive. Since division by zero yields zero, we could allow
297 \isa{c} to be zero. However, \isa{c} cannot be negative: a counterexample
299 $\isa{a} = 7$, $\isa{b} = 2$ and $\isa{c} = -3$, when the left-hand side of
300 \isa{zdiv_zmult2_eq} is $-2$ while the right-hand side is~$-1$.
301 The prefix~\isa{z} in many theorem names recalls the use of $\mathbb{Z}$ to
302 denote the set of integers.%
303 \index{integers|)}\index{*int (type)|)}
305 Induction is less important for integers than it is for the natural numbers, but it can be valuable if the range of integers has a lower or upper bound. There are four rules for integer induction, corresponding to the possible relations of the bound ($\geq$, $>$, $\leq$ and $<$):
307 \isasymlbrakk k\ \isasymle \ i;\ P\ k;\ \isasymAnd i.\ \isasymlbrakk k\ \isasymle \ i;\ P\ i\isasymrbrakk \ \isasymLongrightarrow \ P(i+1)\isasymrbrakk \ \isasymLongrightarrow \ P\ i%
308 \rulename{int_ge_induct}\isanewline
309 \isasymlbrakk k\ <\ i;\ P(k+1);\ \isasymAnd i.\ \isasymlbrakk k\ <\ i;\ P\ i\isasymrbrakk \ \isasymLongrightarrow \ P(i+1)\isasymrbrakk \ \isasymLongrightarrow \ P\ i%
310 \rulename{int_gr_induct}\isanewline
311 \isasymlbrakk i\ \isasymle \ k;\ P\ k;\ \isasymAnd i.\ \isasymlbrakk i\ \isasymle \ k;\ P\ i\isasymrbrakk \ \isasymLongrightarrow \ P(i-1)\isasymrbrakk \ \isasymLongrightarrow \ P\ i%
312 \rulename{int_le_induct}\isanewline
313 \isasymlbrakk i\ <\ k;\ P(k-1);\ \isasymAnd i.\ \isasymlbrakk i\ <\ k;\ P\ i\isasymrbrakk \ \isasymLongrightarrow \ P(i-1)\isasymrbrakk \ \isasymLongrightarrow \ P\ i%
314 \rulename{int_less_induct}
318 \subsection{The Types of Rational, Real and Complex Numbers}
321 \index{rational numbers|(}\index{*rat (type)|(}%
322 \index{real numbers|(}\index{*real (type)|(}%
323 \index{complex numbers|(}\index{*complex (type)|(}%
324 These types provide true division, the overloaded operator \isa{/},
325 which differs from the operator \isa{div} of the
326 natural numbers and integers. The rationals and reals are
327 \textbf{dense}: between every two distinct numbers lies another.
328 This property follows from the division laws, since if $x\not=y$ then $(x+y)/2$ lies between them:
330 a\ <\ b\ \isasymLongrightarrow \ \isasymexists r.\ a\ <\ r\ \isasymand \ r\ <\ b%
334 The real numbers are, moreover, \textbf{complete}: every set of reals that
335 is bounded above has a least upper bound. Completeness distinguishes the
336 reals from the rationals, for which the set $\{x\mid x^2<2\}$ has no least
337 upper bound. (It could only be $\surd2$, which is irrational.) The
338 formalization of completeness, which is complicated,
339 can be found in theory \texttt{RComplete}.
341 Numeric literals\index{numeric literals!for type \protect\isa{real}}
342 for type \isa{real} have the same syntax as those for type
343 \isa{int} and only express integral values. Fractions expressed
344 using the division operator are automatically simplified to lowest terms:
346 \ 1.\ P\ ((3\ /\ 4)\ *\ (8\ /\ 15))\isanewline
347 \isacommand{apply} simp\isanewline
350 Exponentiation can express floating-point values such as
351 \isa{2 * 10\isacharcircum6}, but at present no special simplification
355 Types \isa{rat}, \isa{real} and \isa{complex} are provided by theory HOL-Complex, which is
356 Main extended with a definitional development of the rational, real and complex
357 numbers. Base your theory upon theory \thydx{Complex_Main}, not the
361 Available in the logic HOL-NSA is the
362 theory \isa{Hyperreal}, which define the type \tydx{hypreal} of
363 \rmindex{non-standard reals}. These
364 \textbf{hyperreals} include infinitesimals, which represent infinitely
365 small and infinitely large quantities; they facilitate proofs
366 about limits, differentiation and integration~\cite{fleuriot-jcm}. The
367 development defines an infinitely large number, \isa{omega} and an
368 infinitely small positive number, \isa{epsilon}. The
369 relation $x\approx y$ means ``$x$ is infinitely close to~$y$.''
370 Theory \isa{Hyperreal} also defines transcendental functions such as sine,
371 cosine, exponential and logarithm --- even the versions for type
372 \isa{real}, because they are defined using nonstandard limits.%
373 \index{rational numbers|)}\index{*rat (type)|)}%
374 \index{real numbers|)}\index{*real (type)|)}%
375 \index{complex numbers|)}\index{*complex (type)|)}
378 \subsection{The Numeric Type Classes}\label{sec:numeric-classes}
380 Isabelle/HOL organises its numeric theories using axiomatic type classes.
381 Hundreds of basic properties are proved in the theory \isa{Ring_and_Field}.
382 These lemmas are available (as simprules if they were declared as such)
383 for all numeric types satisfying the necessary axioms. The theory defines
384 dozens of type classes, such as the following:
387 \tcdx{semiring} and \tcdx{ordered_semiring}: a \emph{semiring}
388 provides the associative operators \isa{+} and~\isa{*}, with \isa{0} and~\isa{1}
389 as their respective identities. The operators enjoy the usual distributive law,
390 and addition (\isa{+}) is also commutative.
391 An \emph{ordered semiring} is also linearly
392 ordered, with addition and multiplication respecting the ordering. Type \isa{nat} is an ordered semiring.
394 \tcdx{ring} and \tcdx{ordered_ring}: a \emph{ring} extends a semiring
395 with unary minus (the additive inverse) and subtraction (both
396 denoted~\isa{-}). An \emph{ordered ring} includes the absolute value
397 function, \cdx{abs}. Type \isa{int} is an ordered ring.
399 \tcdx{field} and \tcdx{ordered_field}: a field extends a ring with the
400 multiplicative inverse (called simply \cdx{inverse} and division~(\isa{/})).
401 An ordered field is based on an ordered ring. Type \isa{complex} is a field, while type \isa{real} is an ordered field.
403 \tcdx{division_by_zero} includes all types where \isa{inverse 0 = 0}
404 and \isa{a / 0 = 0}. These include all of Isabelle's standard numeric types.
405 However, the basic properties of fields are derived without assuming
409 Hundreds of basic lemmas are proved, each of which
410 holds for all types in the corresponding type class. In most
411 cases, it is obvious whether a property is valid for a particular type. No
412 abstract properties involving subtraction hold for type \isa{nat};
413 instead, theorems such as
414 \isa{diff_mult_distrib} are proved specifically about subtraction on
415 type~\isa{nat}. All abstract properties involving division require a field.
416 Obviously, all properties involving orderings required an ordered
419 The class \tcdx{ring_no_zero_divisors} of rings without zero divisors satisfies a number of natural cancellation laws, the first of which characterizes this class:
421 (a\ *\ b\ =\ (0::'a))\ =\ (a\ =\ (0::'a)\ \isasymor \ b\ =\ (0::'a))
422 \rulename{mult_eq_0_iff}\isanewline
423 (a\ *\ c\ =\ b\ *\ c)\ =\ (c\ =\ (0::'a)\ \isasymor \ a\ =\ b)
424 \rulename{mult_cancel_right}
427 Setting the flag \pgmenu{Isabelle} $>$ \pgmenu{Settings} $>$
428 \pgmenu{Show Sorts} will display the type classes of all type variables.
431 Here is how the theorem \isa{mult_cancel_left} appears with the flag set.
433 ((c::'a::ring_no_zero_divisors)\ *\ (a::'a::ring_no_zero_divisors) =\isanewline
434 \ c\ *\ (b::'a::ring_no_zero_divisors))\ =\isanewline
435 (c\ =\ (0::'a::ring_no_zero_divisors)\ \isasymor\ a\ =\ b)
439 \subsubsection{Simplifying with the AC-Laws}
440 Suppose that two expressions are equal, differing only in
441 associativity and commutativity of addition. Simplifying with the
442 following equations sorts the terms and groups them to the right, making
443 the two expressions identical.
445 a\ +\ b\ +\ c\ =\ a\ +\ (b\ +\ c)
446 \rulenamedx{add_assoc}\isanewline
448 \rulenamedx{add_commute}\isanewline
449 a\ +\ (b\ +\ c)\ =\ b\ +\ (a\ +\ c)
450 \rulename{add_left_commute}
452 The name \isa{add_ac}\index{*add_ac (theorems)}
453 refers to the list of all three theorems; similarly
454 there is \isa{mult_ac}.\index{*mult_ac (theorems)}
455 They are all proved for semirings and therefore hold for all numeric types.
457 Here is an example of the sorting effect. Start
458 with this goal, which involves type \isa{nat}.
460 \ 1.\ Suc\ (i\ +\ j\ *\ l\ *\ k\ +\ m\ *\ n)\ =\
461 f\ (n\ *\ m\ +\ i\ +\ k\ *\ j\ *\ l)
464 Simplify using \isa{add_ac} and \isa{mult_ac}.
466 \isacommand{apply}\ (simp\ add:\ add_ac\ mult_ac)
469 Here is the resulting subgoal.
471 \ 1.\ Suc\ (i\ +\ (m\ *\ n\ +\ j\ *\ (k\ *\ l)))\
472 =\ f\ (i\ +\ (m\ *\ n\ +\ j\ *\ (k\ *\ l)))%
476 \subsubsection{Division Laws for Fields}
478 Here is a selection of rules about the division operator. The following
479 are installed as default simplification rules in order to express
480 combinations of products and quotients as rational expressions:
482 a\ *\ (b\ /\ c)\ =\ a\ *\ b\ /\ c
483 \rulename{times_divide_eq_right}\isanewline
484 b\ /\ c\ *\ a\ =\ b\ *\ a\ /\ c
485 \rulename{times_divide_eq_left}\isanewline
486 a\ /\ (b\ /\ c)\ =\ a\ *\ c\ /\ b
487 \rulename{divide_divide_eq_right}\isanewline
488 a\ /\ b\ /\ c\ =\ a\ /\ (b\ *\ c)
489 \rulename{divide_divide_eq_left}
492 Signs are extracted from quotients in the hope that complementary terms can
495 -\ (a\ /\ b)\ =\ -\ a\ /\ b
496 \rulename{minus_divide_left}\isanewline
497 -\ (a\ /\ b)\ =\ a\ /\ -\ b
498 \rulename{minus_divide_right}
501 The following distributive law is available, but it is not installed as a
504 (a\ +\ b)\ /\ c\ =\ a\ /\ c\ +\ b\ /\ c%
505 \rulename{add_divide_distrib}
509 \subsubsection{Absolute Value}
511 The \rmindex{absolute value} function \cdx{abs} is available for all
512 ordered rings, including types \isa{int}, \isa{rat} and \isa{real}.
513 It satisfies many properties,
514 such as the following:
516 \isasymbar x\ *\ y\isasymbar \ =\ \isasymbar x\isasymbar \ *\ \isasymbar y\isasymbar
517 \rulename{abs_mult}\isanewline
518 (\isasymbar a\isasymbar \ \isasymle \ b)\ =\ (a\ \isasymle \ b\ \isasymand \ -\ a\ \isasymle \ b)
519 \rulename{abs_le_iff}\isanewline
520 \isasymbar a\ +\ b\isasymbar \ \isasymle \ \isasymbar a\isasymbar \ +\ \isasymbar b\isasymbar
521 \rulename{abs_triangle_ineq}
525 The absolute value bars shown above cannot be typed on a keyboard. They
526 can be entered using the X-symbol package. In \textsc{ascii}, type \isa{abs x} to
527 get \isa{\isasymbar x\isasymbar}.
531 \subsubsection{Raising to a Power}
533 Another type class, \tcdx{ordered\_idom}, specifies rings that also have
534 exponentation to a natural number power, defined using the obvious primitive
535 recursion. Theory \thydx{Power} proves various theorems, such as the
538 a\ \isacharcircum \ (m\ +\ n)\ =\ a\ \isacharcircum \ m\ *\ a\ \isacharcircum \ n%
539 \rulename{power_add}\isanewline
540 a\ \isacharcircum \ (m\ *\ n)\ =\ (a\ \isacharcircum \ m)\ \isacharcircum \ n%
541 \rulename{power_mult}\isanewline
542 \isasymbar a\ \isacharcircum \ n\isasymbar \ =\ \isasymbar a\isasymbar \ \isacharcircum \ n%
544 \end{isabelle}%%%%%%%%%%%%%%%%%%%%%%%%%