On Tue, Aug 5, 2008 at 4:20 PM, Gabriel Dos Reis wrote:

The category SetAggregate? exports a partial ordering operation for set inclusion under the name "<". I consider this harmful. The principal reason is that since set inclusion is a partial ordering, its spelling should not be tied to "<", or any other usual relational comparison because the interpreter (and the compiler in older versions of Axiom) do syntactic replacements of x >= y by not (x < y) -- and my other misguided syntactic transformations, -- which is true only if we had a total ordering.

Thoughts?

On Tue, Aug 5, 2008 at 5:54 PM From: Bill Page replied:

It is conventional to use a symbol such as <= for partial ordering, and I think it would be usefully represented as an export of a category PartiallyOrderedSet that satisfies the axioms:

• a <= a (reflexivity);
• if a <= b and b <= a then a = b (antisymmetry);
• if a <= b and b <= c then a <= c (transitivity).

for all a, b, and c in P, where P has PartiallyOrderedSet. Then SetAggregate should be a subcategory of PartiallyOrderedSet which in turn is a subcategory of SetCategory (which provides the equivalence relations = and ~= from BasicType). Similarly if some domain has the category OrderedSet and exports the symbols '<', '<=', > and >= then it makes sense that a default implementation of x >= y can be given by not (x < y).

It seems to me that this sort of mathematical knowledge (semantics) is correctly captured by the appropriate design of the Axiom library. In general I think it should not be built-in to either the compiler or the interpreter. But if (and I am not sure that this antecedent really applies) there is some important optimization that could be done if such knowledge if more directly available to either the compiler or the interpreter, then I think it might be appropriate if some built-in knowledge of the associated categories was assumed which would enable such transformations.

Certainly the relationship between partial orders and total ordering is well understood and essential to mathematics.

http://en.wikipedia.org/wiki/Totally_ordered_set

A more common notation might be "s <= t returns true if all elements of set aggregate s are also elements of set aggregate t", i.e. a partial ordering given by set inclusion.

http://en.wikipedia.org/wiki/Partial_order

Similarly, the documentation says subset? is defined as: "subset?(u,v) tests if u is a subset of v. Note: equivalent to reduce(and,{member?(x,v) for x in u},true,false)". So subset? relation is something that can and should be defined at a higher level in the category hierarchy, e.g. in HomogeneousAggregate which already defines member?.

Apparently the documentation in 'SetAggregate':

    ++ s < t returns true if all elements of set aggregate s are also
    ++ elements of set aggregate t.

is wrong? I guess that is the case since I see that the definition of < in FiniteSetAggregate is:

   s < t           == #s < #t and s = intersect(s,t)

So the intention of SetAggregate is that < denotes a "proper" (strict) subset relation.

http://en.wikipedia.org/wiki/Subset

But then < is just a (strict) "partial ordering operation" that obeys a different but related set of axioms. Of course they are interchangeable because we also have = and ~=.

On Tue, Aug 5, 2008 at 8:52 PM, Gabriel Dos Reis wrote:

I forgot to say in my original email that for full disclosure I ran into the problem I reported precisely because I removed the syntactic transformations and hit lot of regressions. So, it does not look to me that just removing the syntactic transformations is that simple. It does expose a fundamental problem that needs to be addressed:

-- How many are aware that somewhere in AXIOM input files there is an expression such as:

     s >= t

where s and t are both Multiset, which relies on the fact that the interpreter is doing misguided syntactic transformations? (I would not have guessed without actually trying it).

On Tue, Aug 5, 2008 at 9:14 PM Bill Page wrote:

I have seen this kind of thing before because I was interested in the subject of the proper treatment of inequalities and inequations. See the following:

http://axiom-wiki.newsynthesis.org/SandBoxInequation

---

The following is an attempt to implement PartiallyOrderedSet as a category in a manner consistent with OrderedSet and SetAggregate.

FriCAS is no longer doing syntactic transformations on comparison operator. Therefore using them for partial orders is fine.