From list to free group

Given natural numbers \mathbb{N}, we could construct integers \mathbb{Z} by considering the equivalence relation on \mathbb{N} \times \mathbb{N} as follows,

  • (a, b)\sim(c, d) if a + d + r= b + c + r for some r

Obviously, it’s a equivalence relation from properties of commutativity. Thus we have equivalence class {[} ( a , b ){]} where a, b \in \mathbb{N}. Then, {[}(0, 0){]} = {[}(1, 1){]} = {[}(n , n){]}, and -{[}(a, b){]}={[}(b, a){]}. This construction from a commutative monoid to abelian group is called Grothendieck group.

Consider \mathbf{List(A)} = \mu{}F_{L}, where F_{L}(X) = 1 + A \times X for some set A. Let \alpha = \langle i , \mathbf{cons} \rangle with i : 1 \rightarrow X, \mathbf{cons}: A \times X \rightarrow X. Let \epsilon = i(*) and x, y, z, \dots \in A, and xs, ys, zs, \dots \in \mathbf{List(A)}. We also write x as \mathbf{cons}(x, \epsilon). We could find that \alpha is a initial F-algebra.

Define “plus” with respect to \mathbb{N} on \mathbf{List(A)} \times \mathbf{List(A)} as follows,

  • \mathbf{concat}(\epsilon , ys) = ys
  • \mathbf{concat}(\mathbf{cons}(x, xs) , ys) = \mathbf{cons}(x, \mathbf{concat}(xs, ys)){]}

where xs, ys \in \mathbf{List(A)} and x \in A. We will abuse the notation + instead of \mathbf{concat} and use :: as \mathbf{cons}. Acturally, (\mathbf{List(A)}, + , \epsilon) is a monoid. Though, it’s not commutative, and we can’t apply the construction of Grothendieck group.

We could define an inverse element to extend the \mathbf{List(A)}. Let xs \in \mathbf{List(A)}, we define xs^{r} as its reverse list which could be defined in functional programming like Haskell as foldl (flip (:)) []\mathbf{last}(xs) as the last element of xs, \mathbf{head}(xs) as the initial element of xs, \mathbf{init}(xs) as the list without the initial element of xs, \mathbf{final} as the list without the last element.

Finally, define elements on \mathbf{List(A)} with one more field, that is, ( s , x) where s = +, - and x \in \mathbf{List(A)}. We could extend the “plus” as

  • xs + ys = \mathbf{last}(xs) + \mathbf{init}(ys) if \mathbf{last}(xs) = -\mathbf{head}(ys),
  • xs + ys = xs + ys otherwise. the later “plus” ignores the sign field.

However, we could show that every element xs in \mathbf{List'(A)} has an inverse element - xs^{r} and this new type is a free group generated by elements of \mathbf{A}. Thus, \mathbb{N} is \mathbf{List(\top)}, and \mathbb{Z} is \mathbf{List'(\top)} where \top is a unit type has only one element. Note that for xs \in \mathbf{List(\top)}, there is no difference with xs^{r}.

Is there any differences between \mathbf{List'(\top)} and \mathbb{Z} constructed by Grothendieck group ?


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s