

last edited 9 years ago by test1 
1 2  
Editor: test1
Time: 2013/04/09 18:25:17 GMT+0 

Note: 
added:
From test1 Tue Apr 9 18:25:17 +0000 2013
From: test1
Date: Tue, 09 Apr 2013 18:25:17 +0000
Subject:
MessageID: <20130409182517+0000@axiomwiki.newsynthesis.org>
FriCAS is no longer doing syntactic transformations on comparison operator. Therefore
using them for partial orders is fine.
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:
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 builtin 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 builtin 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://axiomwiki.newsynthesis.org/SandBoxInequation
The following is an attempt to implement PartiallyOrderedSet
as a
category in a manner consistent with OrderedSet
and SetAggregate
.