1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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$ ? $\endgroup$ – deeppinkwater Dec 8 '18 at 15:16
  • $\begingroup$ @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. $\endgroup$ – CopyPasteIt Dec 8 '18 at 15:32
  • $\begingroup$ 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...). $\endgroup$ – deeppinkwater Dec 8 '18 at 15:41
  • $\begingroup$ 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... $\endgroup$ – deeppinkwater Dec 8 '18 at 15:41
  • $\begingroup$ @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$. $\endgroup$ – CopyPasteIt Dec 9 '18 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.