axiom-developer
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Axiom-developer] operations working in general, but not in special


From: William Sit
Subject: Re: [Axiom-developer] operations working in general, but not in special cases -- help needed
Date: Thu, 06 Apr 2006 09:59:11 -0400

Dear Martin:

Martin Rubey wrote:
> William Sit <address@hidden> writes:
> > I assume you want MatroidCat to be the category of all matroids,
> 
> No, at least not originally. I wanted MatroidCat be the "category" (in the
> sense of axiom/aldor) of those domains, which represent matroids. I.e., an
> element of a domain which in turn belongs to MatroidCat would be a matroid.

One should carefully distinguish a domain from a domain constructor, which
constructs domains (plural) using given parameters. Perhaps by "domain" in your
last line above meant "domain constructor" and "element" meant a domain
constructed with a given set of parameters for the domain constructor? Like:

  Matroid(E:Finite, I: Set Set E): MatroidCat == ...

is a domain constructor, whereas Matroid(GF(5), [[0,1],[0,2],[0,3],[0,4]]) is a
domain (whether the given parameters define a matroid or not requires a proof).

(Otherwise, I am not following: An element of a domain which in turn belongs to
MatroidCat should be an element of a matroid, not a matroid.)
 
> > in which case, the dual operation is actually a domain constructor.  That 
> > is,
> > the above signature cannot do what you are aiming for:
> >
> >     MatroidCat():Category == ... with
> >       dual: % -> %
> >
> > because the % refers to a particular implementation of a domain which is a
> > matroid, not the category itself. The argument to dual is an element of a
> > matroid. A plausible signature is:
> >
> >       dual:() -> MatroidCat()
> >
> > which associates a matroid to the current matroid.
> 
> So, in your view, MatroidCat would contain all matroids, and a domain 
> belonging
> to MatroidCat would be a specific matroid?

Not quite: yes, a domain belonging to MatroidCat would be a specific matroid,
but "belong" must be taken with a grain of salt.  MatroidCat is NOT the set
(class, domain, whatever) of all matroids. It is different from the mathematical
concept of a category, which would include all objects of that category
(matroids) as well as morphisms. A category in Axiom simply specifies what
functions should be exported by a domain of that category. A domain "belongs" to
an Axiom category by declaration when it implements the specified functions
using a particular data structure (given by Rep) for its elements, subject to
certain implicit conventions. A domain constructor for objects (= domain) in the
category builds one object per instance of a given set of parameters. So in a
limited sense, a domain constructor is the part of a functor that maps objects
of one category to objects of another.
 
> > If you do NOT want to implement dual as a domain constructor, then you may
> > try implementing Matroid as the DOMAIN of all matroids. However, Axiom does
> > not allow dependent types at the code level (only at the declaration level
> > for constructors).
> >
> >    Matroid(): SetCategory == ...
> >
> >      Rep:= Record(E:SetCategory, I:Set Set E)
> >
> > probably won't work in Axiom, but Aldor may. The advantage is that this will
> > allow domain constructors implemented as functions, and operations on
> > matroids (not matroid elements) are also possible. So for example, one may
> > test whether two matroids are equal or isomorphic.
> 
> That's what I had in mind.

I can only think of one rough parallel: Axiom algebra library has a domain IDEAL
which represents the set of all polynomial ideals in a polynomial ring. But
there, the ideals belong to a fixed mathematical object, the multivariate
polynomial ring. So one can do all sorts of operations on ideals (like
intersection, union etc), AND at the same time use operations in the polynomial
ring on polynomials IN ideals. In your case, while we are not viewing the set of
all matroids as if the matroids are all subsets of one big set, it seems
possible to implement using the domain and functions approach rather than the
category and domain constructor approach (more below). The choice will be
influenced by how differently Axiom treats constructors from functions. Ideally,
there should be no difference!
 
> > Given any (not necessarily planar) graph G = (N, A), where N is the node 
> > set and
> > A the arc set, there is always a corresponding matroid M = (E, I) called a
> > graphic matroid. (Theorem 4.1, p. 271). Hence a graphic matroid always has a
> > dual matroid called the cographic matroid. So there are TWO matroids for 
> > every
> > graph G.
> 
> Well, yes. Usually one says that the graphic matroid corresponds to the graph,
> though.

Not sure what your point is.
We have two definitions here: Given a graph G, we can construct its graphic
matroid M(G).  So, yes, M(G) "corresponds" to G. Then we can define a matroid M
to be graphic if there is a graph G such that M = M(G). If M is graphic, it is
not a priori true that there is a unique G such that M=M(G), and until uniquness
is proved, one cannot speak of THE graph of a graphic matroid. (Does any one
know if this holds: if M(G1) is isomorphic to M(G2) as matroids, then G1 is
isomorphic to G2 as graphs?) One can always speak of THE graphic matroid of a
graph.
 
> > This means two domain constructors:
> >
> >     GraphicMatroid(G: GraphCat):MatroidCat == ...
> >
> >     CographicMatroid(G: GraphCat):MatroidCat == ...
> 
> If I follow this route I should put all matroidal properties of graphs into
> MatroidCat, and only those properties which are not matroidal into GraphCat I
> think I like this idea.

That is right, but GraphCat should be independent of MatroidCat. A graph is a
graph, not a matroid. The graphic matroid M(G) of a graph G is a matroid, and
that construction is part of a functor (hence a domain constructor in Axiom).
 
> > > Example 2, Differential Equations
> > >
> > > It is quite easy to see that the class of holonomic functions is closed
> > > under integration
> > >
> > > However, we all know that the class of rational functions is *not* closed
> > > under integration
> >
> > The integrate operation is more like the minus or divide operation. Since
> > they operate on elements (not domains), you can simply export integrateIfCan
> > in RatCat.
> 
> yes.
> 
> > The two examples you gave present two different problems.
> 
> It very much depends on how you view the problem(s). Of course, taking your
> approach, these are different problems, but I do think that one can see them 
> as
> a single problem, too.

I don't dictate any approach! I simply analyse the questions you asked. In fact,
I also considered the construction of a DOMAIN called AllMatroids of all
matroids, and in that domain, the dual of any ELEMENT (which is a matroid) may
be constructed, but the implementation of any operation on elements of a matroid
will depend on extracting information from the representation, which is not a
matroid, but data representating a matroid.  On the other hand,  the dual GRAPH
of a graph should not be constructed in AllMatroids because a graph is not a
matroid. The dual matroid of M(G) where G is a graph may be constructed,
provided M(G) can be implemented with a signature:

     graphic(G:GraphCat):AllMatroids ==

Here is where things get limited by the language. It does not seem that
graphic() is a domain constructor, since it only constructs an ELEMENT of
AllMatroids. It does not seem to be a function either, since GraphCat is not a
domain. Two possibilities: we define a DOMAIN AllGraphs of all graphs, much like
AllMatroids. We can then have 
  
     graphic(G:AllGraphs):AllMatroids ==

as a function exported from AllGraphs. The other possibility is to do:

    GraphCat(...) == ...
      graphic: () ->AllMatroids

William




reply via email to

[Prev in Thread] Current Thread [Next in Thread]