Partial Algebras

asked 2011-03-25 04:54:01 +0200

Stefan gravatar image


As part of a future package for matroid theory, I would like to implement an algebraic structure called a "partial field".

A partial field is a tuple P = (S, 0, 1, +, *) such that

  1. S - {0} is a group G under * with identity 1
  2. Every element p has an additive inverse q such that p + q = 0
  3. Otherwise, the sum p + q is defined for only some choices of p + q.

Associativity of + is respected "as much as possible". Formally, this means that there exists a ring R such that G is contained in the group of units of R, and addition in the partial field is the restriction of addition in the ring to S.

Example: the regular partial field. This has elements {-1, 0, 1}, with addition and multiplication as in ZZ, but 1 + 1 is not defined.

How can we best implement such structures? That is, where should the category PartialFields go? One choice would be to subclass Rings. However, for various reasons it is desirable to return an "undefined_element" instead of the sum in the ring. This would break associativity tests that seem to be required for rings.

Example: take the partial field {(-1)^s 2^k : s,k in ZZ} U {0}, with usual multiplication and addition in QQ restricted to this set (e.g. 1/2 - 1 = -1/2 is ok, but 4 - 1/4 is undefined).

  • (1 + 1) + (1 -2) = 1
  • ((1 + 1) + 1) - 2 = undefined_element

If we do not subclass Ring, then a whole new can of worms is opened: we're no longer allowed to fill matrices with our elements. I'm not looking forward to re-implementing the Matrix class (though we would probably subclass it anyway as PMatrix, since we need a different determinant and rank algorithm, as well as some new methods).

P.S. How does one define ZZ[1/2] in Sage? P.P.S. How would I coerce from my own, custom ring into QQ?

edit retag flag offensive close merge delete