Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is a fact we use very frequently in general mathematics when we write such notations as $1+2+3+4$: since we know that $+$ is commutative and associative, we can just "drop the parentheses" and not worry about order of operations. Of course I believe this, but how does one prove this in full generality? Even stating it is giving me trouble. Here's my attempt:

Assume an operation $\oplus:S\times S\to S$ is provided satisfying $x\oplus y=y\oplus x$ and $x\oplus(y\oplus z)=(x\oplus y)\oplus z$ for all $x,y,z\in S$.

Claim: Given any finite set $\emptyset\subset A\subseteq S$, there exists a unique $z\in S$ such that for any function $f:{\cal P}(A)\to{\cal P}(A)$ which satisfies $\emptyset \subset f(B)\subset B$ for all $B\subseteq A$ with $|B|\ge 2$ and any function $g:{\cal P}(A)\to S$ which satisfies $g(\{x\})=x$ for all $x\in S$ and $g(B)=g(f(B))\oplus g(B-f(B))$ for all $|B|\ge 2$, $g(A)=z$.

The operation $\oplus$ does not necessarily have an identity element, so we do not attempt to define an empty sum. Intuitively, this element $z$ represents the finite sum of the elements in $A$, so if $A=\{1,2,3\}$ and $f(\{1,2,3\})=\{1\}$ and $f(\{2,3\})=\{3\}$, then $$z=g(\{1,2,3\})=g(\{1\})\oplus g(\{2,3\})=g(\{1\})\oplus (g(\{3\})\oplus g(\{2\}))=1\oplus(3\oplus 2).$$ There has got to be a better way to say that, but this is the only way I can think of to capture all the possibilities of parenthesization, and still be amenable to a formal proof. And now that I've stated it, how should I prove it? I suppose I should induct on something, but I've no idea what.

Edit: The goal here is to be able to define an operation $F$ such that $F(\{x_1,\dots,x_n\})=x_1\oplus\cdots\oplus x_n$ and be assured that the operation is well defined and satisfies $F(A\cup B)=F(A)\oplus F(B)$, when $A$ and $B$ are disjoint finite nonempty subsets of $S$.

share|improve this question
    
Not sure about the tags on this one. I want to emphasize the formal proof aspect, but there isn't a tag for that. –  Mario Carneiro May 18 '13 at 7:14
    
First we may show the general associative law via a tricky induction argument (see e.g. page 6 here), and then (after we're allowed to ignore parentheses) we may show the general commutativity law second. (The latter follows from transpositions generating symmetric groups, a proof of which does not require any commutativity laws in place.) Machine-checkable proofs are probably a different story. The (universal-algebra) tag may be relevant. –  anon May 18 '13 at 7:38
1  
A better version of the theorem replaces the phrase "finite set" with the phrase "finite multiset". Note that every finite sequence gives rise to a finite multiset in a natural way. –  user18921 May 18 '13 at 10:41
    
@user18921 You are correct that this theorem is not as general as it could be with respect to the domain. However, in my application we need to sum only over distinct elements, so plain sets work fine; and also multisets are a pain to work with formally (although they might yield a better proof of my version of the proof than using sequences, with that unnecessary structure). –  Mario Carneiro May 18 '13 at 21:20
add comment

4 Answers

up vote 1 down vote accepted

So you want to prove that if $S$ is a set and $+$ is a binary commutative associative law : $S \times S \to S$, then there is a unique function $\sum$ from non empty finite subsets of $S$ to $S$ satisfying :
- if $x \in S, \sum \{x\} = x$
- if $A \cap B = \emptyset, \sum A \cup B = \sum A + \sum B$.

Prove this by induction of the size of the subset : if $|A| = 1$ then we have no choice.
If $|A| \ge 2$, suppose we can define $\sum A$ in several ways : $A = B_1 \cup B_2 = C_1 \cup C_2$, where the pairs are disjoint. Using the induction hypothesis, the sums of the subsets $B_i$ and $C_j$ are well-defined and we need to show that $\sum B_1 + \sum B_2 = \sum C_1 + \sum C_2$.
Let $D_{ij} = B_i \cap C_j$. Suppose for now that none of them is empty. Then $\sum B_1 = \sum D_{11} + \sum D_{12}$ and so on, and the claim boils down to proving $\forall a,b,c,d \in S, (a+b)+(c+d) = (a+c)+(b+d)$.

And this is easy : $(a+b)+(c+d) = a+(b+(c+d)) = a+((c+d)+b) = a+(c+(d+b)) = (a+c)+(d+b) = (a+c)+(b+d)$.

The cases where one or more of the $D_{ij}$ is empty are done in a similar way (and are even easier). Or you could add an element $\star$ to $S$ and extend $+$ by defining $\star + x = x + \star = x$, prove that $+$ still is commutative and associative, and finally define $\sum \emptyset = \star$

share|improve this answer
    
+1 This is way better than my proof. There is some case analysis at the end, but the work in each case is much much simpler than the stuff you have to do in my version. –  Mario Carneiro May 18 '13 at 11:04
add comment

You can state it as follows: Given is a set $S$ with a binary $\oplus$ operation on it which is associative and commutative.

For every finite nonempty set $A\subseteq S$, there exists an element $S_A\in S$ such that: 1) If $A=\{a\}$, then $S_A=a$. 2) If $|A|=n$ then for any bijective function $f:\{1,2,3,4,\cdots ,n\}\to A$, it holds that $S_A = f(1)\otimes S_{\{f(2),f(3),\cdots, f(n)\}}$.

Moreover, this assignment $A\mapsto S_A$ is the only one with these properties.

The proof of both existence and uniqueness is done by a standrad proof by induction.

share|improve this answer
    
That was my first attempt, in fact. Unfortunately, that way to break up the sum does not consider all possible parentheses: $(1\oplus 2)\oplus(3\oplus 4)$ cannot be directly deduced from that statement. –  Mario Carneiro May 18 '13 at 7:46
    
Also, (and it's a minor point) I'm trying to avoid the axiom of Infinity, so I have made the statement quite finitistic. Your statement involves (implicitly) an existence claim on a function $A\mapsto S_A$ (since it is self-referencing, you have to claim the existence of all of the $S_A$'s at once) with unspecified domain (I think it would need to include all finite subsets of $S$), which I would like to avoid. –  Mario Carneiro May 18 '13 at 7:52
    
@MarioCarneiro if you specifically wish to have all possible parenthesized expressions, then you can consider finite binary trees, decorated by the elements of your finite set $A$ (without repetition). Then you can make the statement precise and prove it by induction again. As for the finitism remark, while I'm no fan of finitism, if you don't accept the principle of induction then you can't prove generalized associativity. –  Ittay Weiss May 18 '13 at 8:37
    
I accept finite induction alright, I just don't want to posit the existence of a function $S_A:\{A\subseteq S\mid A\mbox{ is finite}\}\to S$, which would be necessary in order to make sense of the claim (instead, we only demand pieces of this function, depending on $A$, so that for each $A$ we get a finite function, but altogether we recreate your $S_A$). Also, "standard proof by induction" is a little demeaning here. Obviously it's induction, but the induction step is hairy. –  Mario Carneiro May 18 '13 at 8:46
    
I edited the description to perhaps reflect my goal better. Your idea of just adding single elements repeatedly works to define the function $F(A)=\bigoplus_{x\in A}x$, but it can't be used to prove that $F(A\cup B)=F(A)\oplus F(B)$ for arbitrary disjoint $A,B$. –  Mario Carneiro May 18 '13 at 8:59
add comment

This is the equivalence between commutative semigroups in the usual sense and their monadic description. It follows, for example, from Beck's monadicity theorem. Here is a down-to-earth formulation: If $S$ is a commutative semigroup, then we have a map which associates to every function $\lambda : S \to \mathbb{N}$ with the property that $\lambda(s)>0$ for at least one $s$, an element $\sum_{x \in S} \lambda(x) \cdot x$ of $S$ (abbreviated by $\sum \lambda$), with the following properties:

  • If $E=\{s\}$ for some $s \in S$ and $\lambda(s)=1$, then $$\sum_{x \in E} \lambda(x) \cdot x = s.$$
  • If $\mu$ is a function which associated to every $\lambda$ as above a natural number (with the property that there is some $\lambda$ with $\mu(\lambda)>0$), then $$\sum_{x \in S} \left(\sum_{\lambda} \mu(\lambda) \cdot \lambda(x)\right) \cdot x = \sum_{x \in S} \left(\sum_{\sum \lambda = s} \mu(\lambda) \right) \cdot x$$

The converse is also true. Whenever $S$ is a set equipped with a sum operation as above, then this endows $S$ with the structure of a commutative semigroup. The point is that the set of functions $\lambda$ equipped with the pointwise addition is the free commutative semigroup on the set $S$. See here for the corresponding monadic description of abelian groups.

share|improve this answer
add comment

It turns out that the claim as originally stated cannot be proven by induction directly, since later steps may introduce repeated elements, which are not accounted for in the claim. Instead, we shall prove it for sequences and weaken it at the end.

Claim: Let $[n]=\{0,1,\dots,n-1\}$. Given any finite sequence $A=\langle x_0,x_2,\dots,x_{n-1}\rangle$ with $n\ge1$ and each $x_i\in S$, there exists a unique $z\in S$ (denoted $F(A)$) such that for any function $f:{\cal P}[n]\to{\cal P}[n]$ which satisfies $\emptyset \subset f(B)\subset B$ for all $B\subseteq [n]$ with $|B|\ge 2$ and any function $g:{\cal P}[n]\to S$ which satisfies $g(\{i\})=x_i$ for all $i\in [n]$ and $g(B)=g(f(B))\oplus g(B-f(B))$ for all $|B|\ge 2$, $g[n]=z=F(A)$.

Let's try to prove this by induction on $n$. In the base case, $A=\langle x_0\rangle$ for some $x_0\in S$. Then $g(\{0\})=g(\{x\})=x_0$ is unique, so we are done.

In the induction step, we assume that for all $|B|\le n$, there is a unique $F(B)$ as stated in the claim and we consider $|A|=n+1$. Then we claim that there exists some two-element set that is evaluated by $g$. (This step takes some justification; we were not precise about the "relevant" part of the domain of $g$, so this should say: $\exists k\in{\Bbb N}\ \exists h:[k]\to {\cal P}(n)$ such that $h(0)=[n+1]$ and $|h(k-1)|=2$ and $\forall m<k-1\,\big[h(m+1)=f(h(m))\vee h(m+1)=h(m)-f(h(m))\big]$. This is our way of specifying a "path" through the "binary tree" prescribed by $f$.) Suppose $h(k-1)=\{i,j\}$ is this two-element set. Then $g(\{i,j\})=x_i\oplus x_j$ or $g(\{i,j\})=x_j\oplus x_i$, and we know these are equal.

Now consider $B=\langle y_0,\dots,y_{n-1}\rangle=A-\langle x_i,x_j\rangle+\langle x_i\oplus x_j\rangle$, where we remove $x_i$ and $x_j$ from the sequence and append $x_i\oplus x_j$ to the end. There is an index mapping $\varphi$ which takes each element of $A$ to the corresponding element of $B$, that is, $y_{\varphi(m)}=x_m$, except that $y_{\varphi(i)}=y_{\varphi(j)}=x_i\oplus x_j$. If we define a function $f':{\cal P}[n]\to{\cal P}[n]$ by $f'(\varphi(X))=\varphi(f(X))$, it will satisfy the induction requirements (and a $g$ satisfying the requirements given $B$ and $f'$ always exists), so we can apply the induction hypothesis to $B$, to find that we can rearrange the sequence to $$(\,((y_0\oplus y_1)\oplus y_2)\cdots\oplus y_{n-2})\oplus(x_i\oplus x_j)=((\,((y_0\oplus y_1)\oplus y_2)\cdots\oplus y_{n-2})\oplus x_i)\oplus x_j$$

by associativity. We're nearly done; we just need to put $x_{n+1}$ at the end instead of $x_j$. If $j=n+1$, great, otherwise, swap $x_{n+1}$ with $x_i$ in the left argument (which is of length $n$ and thus can be rearranged by hypothesis) and then swap $x_{n+1}$ with $x_j$ by regular associativity and commutativity. The left argument is now $\langle x_0,x_1,\dots,x_n\rangle$ in some order, so it adds to something unique by hypothesis; thus $F(A)=F(A-\langle x_{n+1}\rangle)\oplus x_{n+1}$ is independent of $f$ and $g$ and thus is unique.

There's my proof; as you can see I got tired of the $f$ and $g$ interpretation halfway through, but hopefully the attentive reader can fill in the details. Unfortunately, that's supposed to be me, so we'll see how the real proof goes.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.