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?
Best 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.