I have an alphabet or set of symbols $\Sigma$ from which I can build sequences of symbols in $\Sigma^+$ (think of sentences of characters). Now I have a function $f_1:\Sigma\rightarrow\Sigma\times\Sigma_1$ that assigns to each input symbol another symbol in alphabet $\Sigma_1$. The idea here is that we keep the original and the new symbol. Another function $f_2:\Sigma\times\Sigma_1\rightarrow\Sigma\times\Sigma_1\times\Sigma_2$ is now applied in much the same sense, and so on with several functions: $f_i:\Sigma\times\Sigma_1\times...\times\Sigma_{i-1}\rightarrow\Sigma\times\Sigma_1\times...\times\Sigma_i$.

But I don't like that formalization with Cartesian products. These functions are calculating properties of the initial symbols based on the properties calculated by the previous functions. For instance, $\Sigma_1=\{letter,number,punctuation\}$ and $\Sigma_2=\{uppercase,lowercase\}$. I'd like to be able to write something like this: $c\in\Sigma$ is a character, and has properties $c.prop1\in\Sigma_1, c.prop2\in\Sigma_2, \dots c.propN\in\Sigma_n$, so that I can still write each of these functions as $f_i:\Sigma\rightarrow\Sigma$, like saying that they are just filling out those properties. Also, please note that some functions can't compute the property for some input symbol (e.g. $f_2$ doesn't make sense with numbers), we could say that it assigns a symbol $*$ meaning anything, and therefore we would have $c.prop2\in\Sigma_2+*$.

Is there a way to formalize this better than with Cartesian products?

  • 1
    $\begingroup$ I do not get why range of $f_1:\Sigma\rightarrow\Sigma\times\Sigma_1$ is $\Sigma\times\Sigma_1$. Why not just $\Sigma_1$? $\endgroup$ Feb 24, 2014 at 9:33
  • $\begingroup$ @Trismegistos you're right, range of $f_i$ can be just $\Sigma_i$. I included all $\Sigma\times\dots\times\Sigma_i$ to show that they all go as the domain for $f_{i+1}$. $\endgroup$ Feb 24, 2014 at 10:38

1 Answer 1


In order to be able to write down something like $c.prop1\in\Sigma_1$ etc, you'll have to define some functions $g_i:\Sigma\to\Sigma_i$. Then, $g_1$ will stand for $prop1$ and generally, $g_i(c)$ will stand for $c.propi$.

As I understand, $\Sigma_i$ and $f_i$ are already defined. If you had those $g_i$ in hand, they should be such that $$f_1=\mathbf{1}\times g_1\\f_2=\mathbf{1}\times g_1\times g_2\\\vdots\\f_n=\mathbf{1}\times g_1\times\cdots\times g_n$$

where $\mathbf{1}:\Sigma\to\Sigma$ is the identity function: $\mathbf{1}(c)=c$. You can see that $f_i$'s implicitly define $g_i$'s, because $f_i$'s are constructed over $g_i$'s in a way that ths construction is invertible. So, if you know the functions $f_i$, then you can retrieve functions $g_i$ by doing the inverse of product, which is projection.

Then you have $$g_1=\pi_2\circ f_1\\ g_2=\pi_3\circ f_2\circ f_1\\ \vdots\\ g_n=\pi_{n+1}\circ f_n\circ\cdots\circ f_1$$

Since you have $g_i$'s defined and $f_i$'s depend on $g_i's$, you can simplify the way you get a property of a character by ignoring $f_i$'s and taking $g_i$'s only.

If you know only $f_i$ and there is no other information on the properties of the characters, then there is no other way to build functions that map a character to its $i$-th property.

  • $\begingroup$ But $f_i$ receives not only the initial symbol in $\Sigma$, but all the symbols from properties $1,\dots,i-1$, so it's not true that $g_i:\Sigma\rightarrow\Sigma_i\cup\{*\}$ when we do $\pi_{i+1}\circ f_i\circ g_{i-1}$. Also, shouldn't it be $\pi_i$ instead of $\pi_{i+1}$? I might had misunderstood you though. $\endgroup$ Feb 23, 2014 at 16:33
  • $\begingroup$ @JuliánUrbano Yes, you're right. The correct solution is $g_i=\pi_{i+1}\circ f_i\circ\cdots\circ f_1$. I'll correct that at my answer. About $\pi_{i+1}$, this is correct, because $\Sigma_i$ start counting from zero, while the projections start counting from 1. But this is just a convention. You could start counting the projections from zero, too, but you'll have to mention it explicitly. $\endgroup$
    – frabala
    Feb 24, 2014 at 17:32
  • $\begingroup$ but then we are still using Cartesian products as in the OP, right? I mean, each of the $f_i$ functions will have a Cartesian product as domain and (possibly) as codomain too. $\endgroup$ Feb 24, 2014 at 18:09
  • $\begingroup$ @JuliánUrbano What I have done in my answer is construct functions $g_i$ that don't have cartesian products neither in the domain nor in the codomain. The construction uses cartesian products, because it depends on $f_i$, but in the end $g_i$ don't have cartesian products. So, instead of using $f_i$ to describe the properties of a character, I suggested $g_i$. $\endgroup$
    – frabala
    Feb 24, 2014 at 18:25
  • $\begingroup$ @JuliánUrbano Since $g_i$ are defined, you can get rid of $f_i$. $\endgroup$
    – frabala
    Feb 24, 2014 at 18:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .