# 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. Aug 8, 2015 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. Aug 8, 2015 at 5:36

## 1 Answer

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.

• Thank you. I know what your're getting at, and I can certainly appreciate the rigor. The book I'm using defined ab using the ellipses, however, so I wasn't going to concern myself with it. I am noticing though that the book in the question (which is very long and includes much extraneous information so I disregarded it) says if a=a1a2...an and b=b1b2...bn, then ab=a1a2...anb1b2...bn. Should I have said something about that in my proof or does that illegitimize it in some way? I realized the problem when I was proving that there is an identity element (the empty sequence) Aug 10, 2015 at 2:52
• Thanks. The book I'm using defined ab using the ellipses, however, so I wasn't going to concern myself with it. I'm noticing though that the question (which is very long and includes much extraneous information so I didn't include it) in my book says if a=a1a2...and and b=b1b2...bn, then ab=a1a2...anb1b2...bn. Should I have said something about that in my proof or does that illegitimize it in some way? I realized the problem when I was proving that there is an identity element and the empty sequencex=x1x2...xn which doesn't look like ex=x. Does that make any sense? Aug 10, 2015 at 3:00
• @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). Aug 10, 2015 at 8:03
• @LiamCooney: You're welcome! And yes I forgot to check that your proof verifies that the concatenation's symbols are from the given alphabet, which the answerer of your other question pointed out. This is not necessary to prove associativity, but when we say "operation" we mean that the result is a member of the original collection. So strictly speaking one should check it. Also, on Math SE, if someone posts a response that answers your question completely, you can mark it as accepted to indicate so. Of course you can wait for another answer if none of them fully addresses your question. Aug 11, 2015 at 2:08
• @LiamCooney: The marvelous button is simply the tick below the up and down arrows. On your questions you will see one blank tick for every answer. You click it to accept an answer. You can always click again to unaccept, but perhaps there is a time limit, I'm not sure. Also, you can try clicking on the up and down arrows, but it will say you do not have enough reputation yet. For comments when you hover over them an up arrow appears, which you can click to upvote. Comments can't be downvoted, but with more reputation you will have the ability to flag useless comments. Aug 11, 2015 at 6:02