Re: [TYPES] What algebra am I thinking of?

[Jacques Carette]

[ The Types Forum, http://lists.seas.upenn.edu/mailman/listinfo/types-list ]
Correct.  And that (free commutative monoid) is exactly the Bag 
data-structure, with its union and cartesian product operations. [Where 
Bag here is understood to be finitely supported, even though the set of 
resources can be infinite]

Jacques

On 2018-03-27 8:10 AM, Harrison Brown wrote:
[ The Types Forum, http://lists.seas.upenn.edu/mailman/listinfo/types-list ]

Hi Phil,

I think Meola and Eugenio have it right, and in particular I think you're
describing the free module over N generated by the set of resources. (Free
modules over rings proper behave pretty much like vector spaces; I don't
know much about the theory of free modules over rigs, but the analogy
should hold.) And, analogous to how free abelian groups are free modules
over Z, I believe that this is isomorphic to a free commutative monoid
generated by the set of resources. If you want to forbid the empty
transaction, you have a free commutative semigroup. Of course if the
resources interact in some way you no longer have a free structure, but you
should still have an N-module.

Best,

Harrison

On Tue, Mar 27, 2018 at 7:38 AM, Eugenio Moggi <mo...@disi.unige.it> wrote:

[ The Types Forum, http://lists.seas.upenn.edu/mailman/listinfo/types-list
]

Consider a blockchain managing several different resources. Over time,
new
resources may be added or deleted. Each input to or output from a
transaction is associated with a value, where each value consists of
associating zero or more resources with amounts, where the amounts are
natural numbers (that is, integers greater than or equal to zero).

What kind of algebra do values correspond to? It seems similar to vector
spaces, except:
   (a) adding or deleting resources increases or decreases the number of
dimensions in the vector space
   (b) the scalars in the vector space are natural numbers rather than
reals
What algebra am I thinking of? Cheers, -- P
Dear Phil, regarding the issue (b) you want to replace the FIELD of the
real
numbers with the SEMI-RING of natural numbers (N,+,*,0,1).

As suggested by Meola the structure should be a module over a RIG, see
https://ncatlab.org/nlab/show/module
More precisely
- a rig (F,*,+,1,0) for the scalars
- a commutative monoid (V,+,0) for the vectors
- an action *:FxV->V satisfying certain properties, in particular 0*v=0=f*0

When F is a field, one recovers the usual notion of vector space.

A vector space V can be infinite dimensional. In the case of a module over
a
RIG, the definition of base B should be the usual one, namely a subset of
B is a
base for V iff

- every finite subset of B is linearly independent
- every element of V is the linear combination of a finite subset of B

but the definition of LINEARLY INDEPENDENT has to be revised, to avoid the
use
of "negative".  A finite subset {v_i|i:n} of V is lineraly independent <=>
for every a,b:F^n if Sum_i a_i*v_i = Sum_i b_i*v_i, then a=b.

In the module of over N proposed by Meola, ie the maps from the set of
resourses
to the rig N that have finite support, the base is unique, and there is an
obvious definition of inner product, but I doubt you can do much with it.

However, there are modules over N that have no base.  For instance, the
module Z
over N, {1} is too small to be a base, and {1,-1} is too big.

Best Regards
Eugenio Moggi