Concatenation as an Operation

Concatenation as an Operation

Mathematics is like any activity, sport, or skill: it must be honed and practiced. With that in mind, I have been bolstering up my abilities in algebra with a fantastic book A Book of Abstract Algebra, by Charles C. Pinter.1.

As I go through the chapters, I will be posting and discussing selected relevant exercises that have applications. This first post is a short one on operations and concatenation. I discussed operators here, but will revisit the topic.

 

What’s an operation?

First, we define an operation. From Pinter:

 

Definition (operation): An operation on a given set A, often denoted \ast is a rule which assigns a pair of elements (a,b) in A to exactly one element denoted a\ast b in A

 

Pinter stresses several things about this definition that should not just be read and glossed over. First, a\ast b has to be defined for every single pair of elements in the set A. Some obvious examples include multiplication on integers, or addition on real numbers.

Some rules that try to sneak by, but are not operations including division on the real numbers. Why does this fail? Remember that 0 is a real number. I can divide 0 by anything I like, but can I divide anything by 0? No. A real number divided by 0 is not defined.2.

Secondly, the rule sends a pair of elements to exactly one element. Mathematically, this means a rule must be well defined to be an operation. It can’t take the same pair of elements and get two possible answers.

Lastly, a rule must be closed to be an operation. Whatever (a,b) gets mapped to must also be in the set A. Here again, addition of real numbers is closed. Adding two real numbers yields a real number. Division also becomes our counterexample here, but let’s look at division on the space of just integers. Dividing 2 by 3 is certainly defined, but the result is not an integer; it’s a rational number.3.

 

On to Concatenation

Operations are not just defined on numbers, and they don’t necessarily have to just be your standard arithmetic examples (addition, subtraction, multiplication). We can define operations on any space we want, provided we satisfy the definition. Here we will talk about concatenation as an operation on the space of sequences of symbols. If you’re a programmer, you probably assume we’re looking at binary sequences, but we concatenate English words too. (We just call these compound words, like “lifetime” or “backbone”.)

Let’s call A the alphabet. If we are living in binary, then A = \{0,1\}. If we are speaking of English letters, the alphabet is A = \{a,b,c,\ldots,z\}. Now we can call A^{\ast} the set of all sequences of symbols in the alphabet A.4.

Now we will define an operation on A^{*}: concatenation. Many of you already know what this is, so we’ll formally define it here:

If a and b are two sequences in A^{*}, where \mathbf{a} = a_{1}a_{2}\ldots a_{n}, and \mathbf{b} = b_{1}b_{2},\ldots b_{m} (and each a_{i}, b_{i} are drawn from the alphabet), then the concatenation of  and is given by

\mathbf{ab} = a_{1}a_{2}\ldots a_{n}b_{1}b_{2}\ldots b_{m}

That is, just stick b to the end of a. Quick example, if we live in binary, then for \mathbf{a} = 1010 and \mathbf{b} = 001, then

\mathbf{ab} = 1010001

Let’s also note that there is an empty sequence or NULL sequence \lambda that consists of nothing at all. It’s pretty easy to check that concatenation meets the definition of an operation. Pinter asks us to do three simple things here:

1. Prove that the operation defined above is associative.

Associativity is the property of an operation that allows us to group however we like. Addition is associative:

(1+2) + 3 = 1+ (2+3)

In general, to show associativity of an operation, we need to show that for \mathbf{a,b,c} \in A^{*},

(\mathbf{ab})\mathbf{c} = \mathbf{a}(\mathbf{bc})

First, we will define three generic sequences in our A^{*}. Let

\begin{aligned}\mathbf{a} &= a_{1}a_{2}\ldots a_{m}\\\mathbf{b} &=b_{1}b_{2}\ldots b_{n}\\\mathbf{c} &= c_{1}c_{2}\ldots c_{p}\end{aligned}

Notice here that I did not specify an alphabet, and that the length of \mathbf{a,b} and \mathbf{c} are different. We need to keep this as general as possible to prove the statement. Every restriction we place (same length, specific alphabet, etc) weakens the argument.

Now we will show associativity formally:

\begin{aligned}(\mathbf{ab})\mathbf{c}&=(a_{1}a_{2}\ldots a_{m}b_{1}b_{2}\ldots b_{n})c_{1}c_{2}\ldots c_{p}\\&= a_{1}a_{2}\ldots a_{m}b_{1}b_{2}\ldots b_{n}c_{1}c_{2}\ldots c_{p}\end{aligned}

Here we can see that we can put parentheses any way we want to, and it doesn’t affect the end word. That is,

\begin{aligned}(\mathbf{ab})\mathbf{c}&=(a_{1}a_{2}\ldots a_{m}b_{1}b_{2}\ldots b_{n})c_{1}c_{2}\ldots c_{p}\\&= a_{1}a_{2}\ldots a_{m}b_{1}b_{2}\ldots b_{n}c_{1}c_{2}\ldots c_{p}\\&=a_{1}a_{2}\ldots a_{m}(b_{1}b_{2}\ldots b_{n}c_{1}c_{2}\ldots c_{p})\\&=\mathbf{a}(\mathbf{bc})\end{aligned}

So we’ve concluded that the grouping in which you perform the operation on several elements doesn’t matter, and thus we have concluded that concatenation is associative.

2. Explain why the operation is not commutative.

commutative operation is an operation where the order of the elements in the operation doesn’t matter. That is, for an operation \ast, a\ast b = b\ast a. Examples of commutative operations are addition and multiplication on real numbers ( 2+5 = 5+2, for example). An example of a noncommutative operation is matrix multiplication. In general, the order in which you multiply matrices matters. As an explicit illustration,

\begin{bmatrix}1&2\\1&1\end{bmatrix}\begin{bmatrix}1& 1\\ 1 & 2\end{bmatrix} =\begin{bmatrix} 3 & 5 \\ 2 & 3\end{bmatrix}\neq \begin{bmatrix}2 & 3\\3 & 4\end{bmatrix}=\begin{bmatrix}1& 1\\ 1 & 2\end{bmatrix}\begin{bmatrix}1&2\\1&1\end{bmatrix}

We can see now why concatenation is not commutative. If you append \mathbf{b} to \mathbf{a}, you will definitely not get the same result as appending \mathbf{a} to \mathbf{b}.  “Townhome” and “hometown” are certainly two different words, but the two pieces: “home” and “town” are the same. Switching the order of concatenation gave a different result. Since I have produced a single counter example, concatenation cannot be commutative in general.5

3. Prove there is an identity element for this operation.

An identity element is an element that lives in A^{*} that, when applied via the operation in question to any other element in the set, in any order, returns that other element. Formally, \mathbf{e} \in A^{*} is an identity element for operation \ast if and only if \mathbf{ea} = \mathbf{ae} = \mathbf{a} for every single element in \mathbf{A^{*}}.

Some examples:

  • the identity element for regular addition on the real numbers is 0. 0 + x = x + 0 = x for any real number x
  • the identity element for multiplication on the real numbers is 1.

For concatenation, we seek an element that, when concatenated with any other element, in any order, returns that element. Proving existence has several strategies. The simplest one (in theory) is to find a candidate element, and show it meets the criteria.6. Here, since concatenation involves essentially “compounding” two things together, the only way we could keep an element “unchanged” is to concatenate nothing to it. The NULL element \lambda (which is certainly a word, just a NULL word. Computer scientists are very familiar with this concept) fits our bill here. Try it out. If you take nothing and concatenate a word to it, you just get that word. Conversely, concatenating nothing to a given word doesn’t change the word. So the NULL element is our identity element.

 

Conclusion

Operations and rules aren’t equivalent. A rule is anything we make up for some purpose, but an operation has to meet specific criteria to be called one. This post was meant to show that operations are not restricted to just the space of numbers that we deal with every day, but that we can look at spaces of objects, matrices, functions, words, sequences…anything we like. In addition, we can define operations, as long as we satisfy the definition. This represents the power of abstract algebra: we can take structure we thought only belongs to a very restrictive space (like numbers, or even matrices), and look at other things, like concatenation, in a different light.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Footnotes

  1. Dover editions are amazing. There are many fantastic books for a far more affordable price than the “mainstream” publishers. (Looking at you, Springer)
  2. This is why it’s not entirely correct to say that division is the inverse operation of multiplication. Division isn’t an operation on the set of real numbers, unless you restrict the space to exclude 0
  3. Division is usually a good place to start if you’re looking for counterexamples in algebra
  4. I didn’t specify a length here. So if we are in binary, 00, 01011, and 1 are in the set of sequences of symbols built from the binary alphabet.
  5. Feel free to try other alphabets as well: binary, Greek, Cyrillic, hexadecimal, etc. Challenge question: can you find an alphabet and sequence space under which concatenation would be commutative? Matrix multiplication is commutative in very special cases. Does this also hold true for concatenation?
  6. This seems simple, but some problems do not yield an obvious possible candidate. Sometimes it takes years to find this when proving existence. A lot relies on intuition and experience, which isn’t exactly what you want to hear. But in this particular case, we can look at stuff we already are familiar with: 0 and 1, and try to find something “similar” in our new space.