Rig
Posted Wed May 28 07:09:43 -0700 2008
In
http://golem.ph.utexas.edu/category/2008/05/theorems_into_coffee_iii.html
John Baez writes:
Axiom implements something called 'rng' (a ring without identity), but so far as I know the concept of 'rig' is not implemented in any computer algebra system.A rig is a ‘ring without negatives’ — just like a ring but possibly lacking additive inverses. The classic example is the natural numbers, ?. This is, in fact, the free rig on one generator.
Rigs are neglected in ordinary algebra texts, a deficiency that someday must be fixed. Why? First, a lot of stuff that’s true about rings is still true about rigs. Second, and much more importantly, any approach to algebra that doesn’t make room for the natural numbers is clearly defective: the natural numbers are a fundamental algebraic structure that must be reckoned with!
Hi Bill,
I am not sure if a rig is really a _generalization_ of a ring. Just leaving out the additive group, turning it into a semigroup is teh inverse process which Grothendieck did to get from rig to ring, and he had good reason to do so. Since thsi Grothendieck construction works for abelian semigroups always, its almost for free to get a ring out of a rig.
I think the better way to look at this structure is using Natural Number Objects (NNO) in a categoical setting. If in a category you have a natural number object, then you can iterate and get multiplication out of addition. This way you will (since addition is an abelian semigroup here) naturally get a 'rig', but with much more mathematical power behind it.
A good source for natural numer objects and iteration is the book by Lawvere, Rosenbrugh, Sets for Mathematics, and of course Robert Goldblatt, Topi, or the original articles (Freyd, Yetter, and others)
Are you intersted in rig ? if so why?
Ciao
BF.
My main motivation for looking at this is a possible re-design of the Axiom library. Many times when I think about the mathematical taxonomy implemented there, I worry that it is too ad hoc. In a computer algebra system it seems to make sense to start with somewhat more mathematical structure than might be typical in pure mathematics.
In Axiom for example we get positive integers as a subdomain of the Integers. And Integers come from God (well, actually Lisp ... :-).
I agree with your comment about the desirability of putting all this in a categorical setting. I rather liked Baez's description of the NNO as the "free rig on one generator", but I do not know how useful this is in a computer algebra system. Although we certainly do want to do this at a higher level, it seems inconvenient to try to build everything in such a pure manner.
In Axiom we already have:
(1) -> )sh AbelianSemiGroup
AbelianSemiGroup is a category constructor
Abbreviation for AbelianSemiGroup is ABELSG
-------------------- Operations ----------------------------
?*? : (PositiveInteger,%) -> %
?+? : (%,%) -> %
?=? : (%,%) -> Boolean
?~=? : (%,%) -> Boolean
-------
AbelianSemiGroup(): Category == SetCategory with
--operations
"+": (%,%) -> %
++ x+y computes the sum of x and y.
"*": (PositiveInteger,%) -> %
++ n*x computes the left-multiplication of x by the positive integer n.
++ This is equivalent to adding x to itself n times.
add
import RepeatedDoubling(%)
if not (% has Ring) then
n:PositiveInteger * x:% == double(n,x)
-------
Perhaps PositiveInteger is (or should be) Axiom's NNO? Is this "repeated doubling" that kind of thing to which you are referring? Of course in the Axiom programming language (SPAD) we do already have iteration (and much more!).
I also think your reference to Topi is right on. Maybe what we need is some formal mathematical structure (such as topos theory) that we can relate quite directly and formally to Axiom at the level of SPAD. Then when we talk (formally) about introducing seemingly simpler structures into the Axiom library (such as rig and ring), we can do so in reference to something like topi. Then perhaps, it would not seem so embarrassing to see PositiveInteger in AbelianSemiGroup...
Regards,
Bill Page.