[TYPES] What algebra am I thinking of?

[Jacques Carette]

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 <moggi at 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
>>