# Re: Bags vs. Sets

Date: 28 Jun 2006 10:01:31 -0700

Message-ID: <1151514091.239068.316460_at_75g2000cwc.googlegroups.com>

vadimtro_at_gmail.com wrote:

*> Peter Liedermann wrote:
**> > bags can be represented by means of set theory, can't they?
**>
**> Peter Liedermann wrote:
**> > but bags can be represented by means of set theory, can't they?
**>
**> There is an interesting mathematics behind both concepts. Let's shift
**> pespective from set-theoretic into algebraic and focus upon
**> multivariate polynomials. Consider a relation
**>
**> {(x=1,y=1),(x=2,y=1)}
**>
**> This set can be considered as a set of roots of some system of
**> polynomial equations. Can we write those equations explicitly? Sure:
**>
**> (x-1)*(x-2)=0
**> (y-1)=0
**>
*

That does not look right. Take different values for 'y'.

*> The term for such an object in algebraic geometry is an "affine
**> variety".
*

Well, a variety is a set of points, not a set of equations.
'{(x=1,y=1),(x=2,y=1)}'

is a variety allright.

*>(Finite) relations essentially are 0-dimensional affine
**> varieties. (BTW, this is the ultimate
**> answer to ignorants who claim that relations are 2-dimensional:-)
**>
**> Let's give some example of 1-dimensional affine variety:
**>
**> x-y=0
**>
**> This is a familiar x=y predicate. (It is 1-dimensional because we can
**> parameterize the set of roots of the equation x-y=0 with a single
**> parameter).
**>
**> Next, consider a set which is not a variety:
**>
**> (x-1)*(x-2)<=0
**>
**> This is ax interval {x in [1,2]}, and I speculate that the challenge of
**> modelling temporal and spatial domains is anchored to the fact that we
**> have to give up some nice properties of algebraic varieties.
**>
**> Next, there are set theoretic operations upon varieties. Intersection
**> of varieties is just combining their defining equations:
**>
**> (x-1)*(x-2)=0
**> (y-1)=0
**>
**> intersect
**>
**> x-y=0
**>
**> is
**>
**> (x-1)*(x-2)=0
**> (y-1)=0
**> x-y=0
**>
**> which reduces to
**>
**> (x-1)=0
**> (y-1)=0
*

*>
**> Intersection of varieties corresponds in relational language to join.
**> In our example we joined finite relation {(x=1,y=1),(x=2,y=1)} with
**> predicate {x=y} which in RA terms is the selection.
**>
**> Next, a set of equations for a union of varieties A and B is build by
**> coupling each equation from A with that of B. For example, a union of
**>
**> (x-1)*(x-2)=0
**> (y-1)=0
**>
**> and
**>
**> (y-2)=0
**>
**> is
**>
**> (x-1)*(x-2)*(y-2)=0
**> (y-1)*(y-2)=0
*

Let's fix the terminology first before discussing the above.

*>
**> Even though union operands are 0-dimensional varieties, the result is
**> not a 0-dimensional variety, which translates into the corresponding
**> relation being no longer finite. The result is finite when both
**> varieties are defined in the same space (that is the same set of
**> variables). This is a familiar D&D union operator.
**>
**> Since we are talking about roots of equations, it is naturally to ask
**> what about roots of multiplicity greater than one? For instance,
**>
**> x^2 = 0
**>
**> has root 0 of multiplicity 2. This would be a naive attempt to
**> introduce bags.
**>
**> Unfortunately, the equation
**>
**> x^2 = 0
**>
**> defines the same variety as
**>
**> x = 0
**>
**> therefore, varieties are genuine relations.
**>
**> The mathematical object that corresponds to a bag is a polynomial
**> ideal. Ideal is a set of polymomials closed over addition and
**> multiplication.
*

*> The most celebrated mathematical result of 19th century
**> is Hilbert's basis theorem which says that every ideal has a finite
**> basis.
**>
**> By finding the right mathematical counterpart of a bag we can hope
**> being able to give consistent definition of bag operations.
**>
**> Ideals can be added, multiplied and intersected. The union of ideals
**> usually is not an ideal since it may not be closed under addition. From
**> the perspective of algebraic geometry, ideals and varieties are
**> intimately related: the addition of ideals corresponds to the
**> intersection of varieties, and the intersection of ideals corresponds
**> to the union of varieties. Also, the multiplication of ideals
**> corresponds to the union of varieties. Lets go throug the examples.
**>
**> Multiplication of
**>
**> <x^2>
**>
**> by
**>
**> <x^3>
**>
**> produces
**>
**> <x^5>. In bag language this corresponds to union of {0,0} with {0,0,0}
**> producing
**>
**> {0,0,0,0,0}.
**>
**> Intersection of
**>
**> <x^2>
**>
**> with
**>
**> <x^3>
**>
**> produces
**>
**> <x^3>. In bag language this corresponds to set union of {0,0} with
**> {0,0,0} producing
**>
**> {0,0,0}.
**>
**> Addition of
**>
**> <x^2>
**>
**> with
**>
**> <x^3>
**>
**> produces
**>
**> <x^2>. In bag language this corresponds to set intersection of {0,0}
**> with {0,0,0} producing {0,0}.
**>
**> The analoyy shines in case of one variable. It breaks in case of many.
**> Consider the addition of
**>
**> <x^2>
**>
**> with
**>
**> <y^3>
**>
**> which is
**>
**> <x^2,y^3>. In language of bags the corresponding operation is cartesian
**> product of {x=0,x=0} with {y=0,y=0,y=0}. The bag
**> {(x=0,y=0),(x=0,y=0),(x=0,y=0),(x=0,y=0), (x=0,y=0),(x=0,y=0)} is the
**> expected result, but does it really correspond to the ideal <x^2,y^3>?
**> There are many reasons why not.
**>
**> In classic bag theory if we project
**> {(x=0,y=0),(x=0,y=0),(x=0,y=0),(x=0,y=0),(x=0,y=0),(x=0,y=0)} into x we
**> won't get the original relation {x=0,x=0} back (yet another snag that
**> challenges usefulness of classic bag theory). In ideal theory the
**> calculating elimination ideal is analogous to projection operation on
**> bags. Elimination ideal for <x^2,y^3> is <x^2> -- the original ideal.
**>
**> This is as much info as internet posting can hold. A more detailed
**> paper is due.
*

While there are some similarities, not surprizingly, between ideal operations and RA, it's unclear what advantage if any the variety/ideal lingo may have. For example, what field did you have in mind when you talked about polynomials ? Received on Wed Jun 28 2006 - 19:01:31 CEST