# Concatenation operation on the set of finite sequences in $\{0, 1\}$

Let $$A^{\ast} = \bigcup_{I \subset \mathbb{N}} \mathcal{F}(I, \{0, 1\}) = \bigcup_{I \subset \mathbb{N}} (\prod_{i \in I} \{0, 1\})$$ be the set of finite sequences in $$\{0, 1\}$$.

First, if $$I = \emptyset$$, then we have $$\prod_{i \in \emptyset} \{0, 1\} = \{u_{\emptyset}\} \in A^{\ast}$$, where $$u_{\emptyset} : \emptyset \rightarrow \{0, 1\}$$ is the empty mapping, right ?

Second, let $$\star$$ be the concatenation operation on $$A^{\ast}$$ defined in the following way : $$\forall (n, m) \in \mathbb{N}^{\ast} \times \mathbb{N}^{\ast}, \ \forall u = (u_{1}, ..., u_{n}) \in A^{\ast}, \ \forall v = (v_{1}, ..., v_{m}) \in A^{\ast}, u \star v = (u_{1}, ..., u_{n}, v_{1}, ..., v_{m}) \ \text{,}$$ I have seen somewhere that the neutral element for this operation is called the "empty sequence" (denoted here $$()$$) such that : $$\forall u \in A^{\ast}, u \star () = () \star u = u$$. The problem is that I don't find a clear definition of what this empty sequence is.

Precisely, my questions are the following : Are the empty sequence and the empty mapping defined above in first point in fact the same element (i.e., $$() = u_{\emptyset}$$) ? If it is not the case, what is exactly the empty sequence ?

Thank you for your help.

## 1 Answer

The OP's definition/setup is murky. Although there is no doubt about the intention, it is helpful to frame this with more precision. This is just one way to 'get formal'.

Definition: If $$n \in \mathbb N$$, then any function $$u$$ of the form

$$\tag 1 u: \{k \in \mathbb N \; | \; 1 \le k \land k \le n\} \to \{0,1\}$$

is said to be a finite sequence in {0,1} of length $$n$$.

If $$u$$ is a finite sequence in {0,1} of length $$n$$ and $$v$$ is a finite sequence in {0,1} of length $$m$$ we define a finite sequence in {0,1} of length $$n +m$$, $$u*v$$, as follows:

$$\quad\quad\quad\quad [u*v](k) = u(k) \text{ for } k \le n$$
$$\quad\quad\quad\quad [u*v](k) = v(k-n) \text{ for } n + 1 \lt k \le n+m$$

Informally, we write $$u = (u_{1}, ..., u_{n})$$.

The definition allows for a finite sequence of length $$0$$, but there can only be one form of such a sequence, the empty graph $$\emptyset$$. In the same way that using logic shows that $$0! = 1$$, you can show that $$\emptyset$$ serves as an identity.

Now if that sounds 'spooky', you can change the definition so that length $$0$$ is not allowed. Then, if you want, you can algebraically 'throw in' an identity with our associative binary operation of concatenation.

With our informal notation, using $$()$$ for $$\emptyset$$ works great!

• In my case, the problem is that I need to allow sequences of length $0$ (so I'm agree, there's only one, the one I denoted "$u_{\emptyset}$"), but I also need that when I do concatenation of any sequence $u \ast u_{\emptyset}$, I obtain $u$. So the algebraic identity for $\ast$ can actually be $u_{\emptyset}$ right ? Moreover (maybe I go to far sometimes, sorry), could we actually throw in another algebraic identity that is different from $u_{\emptyset}$ (if it is one) or it is the only identity for $\ast$ ? – deeppinkwater Dec 8 '18 at 15:16
• @deeppinkwater You can throw in more than one algebraic identity and still have an associative operation - but why would you? When you put in just one identity, it make sense to say it has length $0$ - the length of a concatenation is the sum of the lengths. – CopyPasteIt Dec 8 '18 at 15:32
• I don't want to throw another one. First, I need the existence of a sequence of length $0$ (without talking about concatenation), and then, I need an identity for concatenation and I want this identity to be the sequence of length $0$ I exhibited at first step (also, the problem in my case is that I don't really have an operation since I have a length $N$ that I cannot exceed, so concatenation is not really define for any sequence, but anyway...). – deeppinkwater Dec 8 '18 at 15:41
• I'm asking you if I could put another identity because the one we talk about ($\emptyset$) seems obvious to me and I don't realy see which one you could take instead of... – deeppinkwater Dec 8 '18 at 15:41
• @deeppinkwater Any identity under multiplication (concatenation) does the same thing - nothing! So they all just look like the $\emptyset$ Graph = Null Sequence. You can name it anything or use any notation you want. So use $\text{ [\0]}$ for the $\emptyset$ Graph, and then $\text{ [\0]} * u = u * \text{ [\0]}$ for all $u$. – CopyPasteIt Dec 9 '18 at 1:58