[Math] Confused by inductive proof of associative law

associativityinduction

In Artin's book he proves the associativity of a $n$-element product.

It says as follows:

i) the product of one element is the element itself.

ii) the product $a_1a_2$ is given by the law of composition.

iii) for any natural n, $[a_1a_2…a_n]=[a_1…a_i][a_{i+1}…a_n]$

Proof:

The product is defined by (i) and (ii) for $n≤2$ and satisfies (iii) for $n=2$. Suppose that we have defined the product of $r$ elements when $r≤n-1$ and that it is the unique product satisfying (iii). We then define the product of $n$ elements by the rule$$[a_1…a_n]=[a_1…a_{n-1}][a_n]$$

where the terms on the right side are those already defined. If a product satisfying (iii) exists, then this formula gives the product because it is (iii) when $i =n-1$. So if it exists, the product is unique. We must now check (iii) for $i< n-1$:
So if it exists, the product is unique. We must now check (iii) for $i< n-1$:
\begin{align} [a_1…a_n]&=[a_1…a_{n-1}][a_n] &&\text{(our definition)}\\
&=([a_1…a_i][a_{i+1}…a_{n-1}])[a_n] &&\text{(induction hypothesis)}\\
&=[a_1…a_i]([a_{i+1}…a_{n-1}][a_n]) &&\text{(associative law)} \\
&=[a_1\cdots a_i][a_{i+1}\cdots a_n] &&\text{(induction hypothesis)}
\end{align}
This completes the proof.

I don't understand how this proves the associativity, for example, for $i=n-1$.

Could someone elaborate a bit more on this proof?

Best Answer

The product is defined by (i) and (ii) for $n≤2$ and satisfies (iii) for n=2.

This is the base case.

Suppose we know how to define the product of r elements when $r≤n-1$ and that this is the unique product satisfying (iii).

This is the induction hypothesis; the proof uses strong induction.

You could rephrase this as follows (and this is the form he uses further down in the proof):

For all $r \leq n-1$ and for all $i<r$, we have $[a_1\cdots a_r] =[a_1\cdots a_i][a_{i+1}\cdots a_r]$

We then define the product of n elements by the rule$$[a_1...a_n]=[a_1...a_{n-1}][a_n]$$ Where the terms on the right side are those already defined. If a product satisfying (iii) exists, then this formula gives the product because it is (iii) when $i =n-1$.

If I understood your question correctly, this is the step that you don't understand. This step actually makes sense only in light of a part of the statement of the proposition that you didn't quote in your question (emphasis mine):

Let an associative law of composition be given on a set $S$. There is a unique way to define, for every integer $n$, a product of $n$ elements $a_1,\dots, a_n$ of $S$, denoted temporarily by $[a_1\cdots a_n]$, with the following properties ...

So this part of the proof explicitly defines the product, and the next parts of the proof show that with this definition, the product satisfies property (iii). This means that associativity doesn't need to be proved for $i=n-1$, because for this $i$ it is satisfied by definition.

Related Question