Bags vs. Sets

From: <vadimtro_at_gmail.com>
Date: 22 Jun 2006 11:50:23 -0700
Message-ID: <1151002223.848102.58220_at_p79g2000cwp.googlegroups.com>


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

The term for such an object in algebraic geometry is an "affine variety". (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

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. Received on Thu Jun 22 2006 - 20:50:23 CEST

Original text of this message