0
$\begingroup$

Is the set of real numbers a language?

My idea is that the set of real numbers can't be a language because it is uncountable. Every language must be countable.

Is there any other way to solve this problem?

$\endgroup$
  • 4
    $\begingroup$ What is your definition of a language? $\endgroup$ – Yuval Filmus Dec 18 '17 at 16:21
3
$\begingroup$

The definition of a language, from Hopcroft-Ullman Introduction to Automata and Language Theory, is :

A set of strings all of which are chosen from some $\Sigma^*$, where $\Sigma$ is a particular alphabet, is called a language.

And from the same book, the definition of a string is :

A string (or sometimes word) is a finite sequence of symbols chosen from some alphabet.

So strings must be finite. If we represent real numbers by sequences of digits, those sequences would be infinite in length, so that representation won't give us the language of real numbers.

But can we use another representation ? For example, even though we have rationnal numbers with an infinite sequence of digits, we can consider them as a language thanks to fractional representation.

Suppose that the set of real numbers were a language. Let's call that language $L$, and $\Sigma$ its alphabet. $L$ is a subset of $\Sigma^*$, thus $L$ is countable because $\Sigma^*$ is countable. We conclude that the set of real numbers can't be a language because it's an uncountable set.

NOTE : We can explicitly define an injection from $\Sigma^*$ to natural numbers. First, associate for every letter of $\Sigma$ a unique integer, call it $int(a)$. Let $\sigma$ be that bijection, here is its definition :

$$\left \{ \begin{array}{r c l} \sigma(\epsilon) &=& 0 \\ \sigma(\omega) &=& \prod_{i=1}^{|\omega|} \pi(i)^{int(\omega_i)} &;& \omega \neq \epsilon \end{array} \right .$$

Where $\pi(i)$ is the $i^{th}$ prime number and $\omega_i$ the $i^{th}$ letter of $\omega$.

| cite | improve this answer | |
$\endgroup$

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.