# Proof of associativity for concatenation operation

I recently took a mathematical proof class and am beginning to teach myself abstract algebra. I'm fairly new to proofing however, and am not very confident in how I do it. Also, I'm new to this site so I apologize for any technical mistakes here (I ended up copying and pasting from Word…how do you do mathematical symbols and all on this site…I’m very low tech)

The book I am using is "A Book of Abstract Algebra" by Charles Pinter. This question is on pg 24 of Chapter 2(Operations) under exercise set D, question 1 for anyone who has the book and would like to reference it.

The question asks us to prove that the operation of concatenation is associative on $A^*$, the set of all sequences of symbols in the alphabet $A$. The operation, $*$ is defined as

$$a * b := a_1 a_2…a_n b_1 b_2…b_m.$$

Theorem: The operation of concatenation denoted by $*$ and defined above is associative on $A^*$, the set of all sequences of symbols in the alphabet $A$.

My Proof: Suppose $x, y, z \in A$. Then $x*y=x_1 x_2…x_n y_1 y_2…y_m$.

Now call $x*y$, $a$.

Then $a*z=x_1 x_2…x_n y_1 y_2…y_m z_1 z_2…z_q$.

Since $a= x*y$, $a*z=(x*y)*z=x_1 x_2…x_n y_1 y_2…y_m z_1 z_2…z_q$.

Now $y*z=y_1 y_2…y_m z_1 z_2…z_q$.

Now call $y*z$, $b$.

Then $x*b=x_1 x_2…x_n y_1 y_2…y_m z_1 z_2…z_q$.

Since $b=y*z$, $x*b=x*(y*z)=x_1 x_2…x_n y_1 y_2…y_m z_1 z_2…z_q.=(xx_1 x_2…x_n y_1 y_2…y_m z_1 z_2…z_q=(x*y)*z$

Thus $\forall x \forall y \forall z \in A^*$, $(x*y)*z=x*(y*z)$, and hence by the definition of associativity, concatenation is associative on $A^*$.

So my questions are:

1) Is this proof correct (I mean this in a very basic sense, not is it written well, but is it correct; will it do?) If not, what do I need to do to fix it?

2) If it is correct, is there anything you'd do in terms of how it is written to make it better?

• Welcome to mathSE. Usually you want to limit your question here to one particular issue (1 and 2 are okay; 3 does not belong here). Also, many people will not bother reading thorugh your wall of text so you should use bold (**bold text**) and italics (*italic text*) to highlight the important parts. – 6005 Aug 8 '15 at 5:35
• As for 3, that sort of question belongs on meta. The answer is that this site uses "MathJax", which is very similar to LaTeX. Put math between dollar signs: $2 + 5 = 7$. A tutorial for how to use MathJax is here. – 6005 Aug 8 '15 at 5:36

You proof is fine. My only nitpick would be more with the definition in the question rather than your solution, because in mathematics if you want rigour you cannot use ellipses (dots). But it would take too long to explain here how to define everything without ellipses, so I'll pass. If you want to know, the basic idea is to recursively define concatenation of $x$ and $y$, with the base case being if $y$ is the empty string and the general case being to append the first symbol of $y$ to $x$ (which should be a primitive operation), and after that to concatenate the result with the tail of $y$ (getting the tail should be another primitive operation). But that is best dealt with in a separate question.
• @LiamCooney: Yea sure at a very basic level you can continue using ellipses. But the inherent lack of rigour is precisely what is involved in your next question. You should decide (by yourself or based on your book) whether writing $a_1 a_2 \cdots a_n$ allows $n = 0$, in which case it would be the empty string. If so, your current proof works fine for empty strings too. Note however that you must be careful that you do not assume there is an $a_1$ when given $a_1 a_2 \cdots a_n$! So very good question (it totally makes sense to ask about such fine detail). – user21820 Aug 10 '15 at 8:03