# Is a single symbol, not in a set, a language?

I was reading about Turing machines and realized I'm not sure about the difference between the following scenario. Given the alphabet $\Sigma = \{a, b \}$, we have the following assertions:

1. $a \in R$
2. $\{a\} \in R$

I think that assertion $1$ is incorrect because $a$ is just a symbol, not a language. On the other hand $\{a\}$ is the language which contains only the $a$ symbol. Given that information, we can prove that $\{a\} \in R$ by trivially building a TM. Here, $R$ denotes the set of recursive languages.

Is my reasoning wrong? Thanks in advance.

## migrated from cstheory.stackexchange.comSep 14 '12 at 15:21

This question came from our site for theoretical computer scientists and researchers in related fields.

• If you repost this somewhere else, it would be useful to explain what the variable R stands for. – Robin Kothari Sep 14 '12 at 15:07
• Well, hold on. If $R$ is taken to denote the set of regular languages, then $a$ may be interpreted as a regular expression for the language $\{a\}$, in which case it is true that $a \in R$. So you might see $a \in R$ somewhere, without it being wrong... – Patrick87 Sep 14 '12 at 17:22
• @RobinKothari Thanks for your comment, I've made a clarification of what $R$ stands for. Anyway, I do not understand why this questions wasn't suitable for cstheory. – Pampero Sep 14 '12 at 21:47
• @Patrick87: A regular expression and the language it represents are two clearly distinct objects. – frafl May 24 '13 at 16:43
• @frafl Yes, but I'm not talking about that; I'm talking about how the notations aren't necessarily always clear and must be understood in context. Depending on the context, $a$ may mean the symbol, the regular expression, or the language of the regular expression. – Patrick87 May 28 '13 at 16:28

By the standard definitions, a language is always a set of (finite-length) words. This means that "$a$" is not a language, but either a symbol or a word.

If $R$ denotes all the regular languages (or alternatively, all the recursive languages), then indeed $a \notin R$. On the other hand, $\{a\}$ is a language, which is also regular (and recursive).

To complete the standard definitions:

1. an alphabet is a finite set of symbols
2. a word is a finite-length string of symbols
3. a language is a set of words (and can be finite or infinite)

of course, there are many possible extensions to the above definitions, such as infinite-alphabet, infinite-length words, etc.

• Thanks for your answer, that's exactly what I was looking for. – Pampero Sep 14 '12 at 21:43
• Hey, not so fast. Sets can be nested! Even if the alphabet $\Sigma$ is a set containing two regular languages $a$ and $b$, the set $\{a\}$ is a finite-and-therefore-regular language over $\Sigma$. – JeffE Sep 14 '12 at 23:12
• Part of the problem is that $a$ is not a language, but $a$ is a regular expression which represents the language $\{a\}$, so often $a$ will be used as shorthand for $\{a\}$. So in a sense, $a$ is not a language but $L(a)$ is. – jmite May 24 '13 at 16:41
• It is unfortunate that there is no formal notational difference between a symbol in the alphabet, a string of length one, and a regular expression encoding a language whose only element has length one. – JeffE May 25 '13 at 14:13

I guess this is not what you were looking for, but I'd like to answer this from the viewpoint of pure set theory:

1. Let $\Sigma$ be any finite set, we call its elements symbols and $\Sigma$ an alphabet.
2. A word over $\Sigma$ is a tuple of elements from $\Sigma$. Tuples can be defined using set theory in a lot of different ways (some of them can be found in WP:Tuples). Especially for the $1$-tuple, there are at least three definitions. Let $(a)$ be the tuple that contains only the set $a$. Then one can define e.g.
• $(a):=a$,
• $(a):=\{\{a\},\{\{\{\emptyset\},a\}\}\}=\{(1,a)\}$ (tuple as finite function) or
• $(a):=\{a,\{\emptyset,a\}\}=(\emptyset,a)$ (nested ordered pairs).
3. A language over $\Sigma$ is a set of words, i.e. a set of tuples whose elements are in $\Sigma$.

If we assume that tuples (and thus words) are finite, then languages are always countable. Whether a symbol $a \in \Sigma$ is also a language (over $\Sigma$ or any other alphabet) now depends on your definition of tuples:

1. If $(a)=a$ then any finite set $S$ can be seen as a language over $S$, containing all words of length $1$. So if $a\in \Sigma$ is a finite set (remember all "objects" in set theory are sets), then it is a language.
2. If not only $a \in \Sigma$, but $a \subset \Sigma$ (e.g. WP:Peano arithmetic), then $a$ is even a language over $\Sigma$ if we define $(a):=a$ and similar cases are possible for the other definitions of tuples, if $\{(a)\} \in \Sigma$.

Conclusion: if you like to ensure that $a \in \Sigma$ is not a language, make your symbols uncountable, e.g. let $\Sigma=\{[i-1,i]\mid i\in {1,\dots,k}\}$, where $[a,b]$ means the closed real interval.