4
$\begingroup$

A fellow student just claimed that there are numbers in $\mathbb{R}$ which cannot be expressed as a limit. I don't think that is true, but first some definitions / examples:

Definition: A set $S$ is countable if there exists an injective function $f:S \rightarrow \mathbb{N}$.

Examples:

  • $\{1,2,3,4\}, \mathbb{N},\mathbb{Z}, \mathbb{Q}$ are all countable.
  • $\mathbb{R}$ is not countable.

Now we can define a formal Grammar $(V, \Sigma, P, S)$ with:

  • The terminal symbols $\Sigma = \{0, 1,2,3,4,5,6,7,8,9,.,+,-,\cdot,:,(,), \lim, n, \mathrm{pow}, !, \sum, \prod\}$
  • The vocabulary: $V = \Sigma \cup \{S, Z, N, \mathrm{var}\}$
  • The production rules $P \subseteq (V^* \setminus \Sigma^*) \times V^*$ (they follow)
  • The start symbols $S$

The set of production rules is

  • $S \rightarrow Z\mid\lim_{\mathrm{var}\rightarrow \infty} S \mid S+S\mid S-S\mid S \cdot S\mid S:S\mid (S)\mid S^S\mid S!\mid \sum_{\mathrm{var}=N}^\infty S\mid \prod_{\mathrm{var}=N}^\infty S$
  • $Z \rightarrow ZZ\mid N.N\mid -N.N$
  • $N \rightarrow NN\mid 0\mid 1\mid 2\mid 3\mid 4\mid 5\mid 6\mid 7\mid 8\mid 9$
  • $\mathrm{var}\rightarrow n_N$

You can build some invalid expressions with this grammar (like $\frac{0}{0}$), but I think you can express every number which can be written as a finite forumula / a limit of a finite formula limit with it (can you?).

Sanity check

  • $\mathbb{Q} \in \mathcal{L}(V, \Sigma, P, S)$
  • $e^x = \lim_{n_1 \rightarrow \infty} (1+\frac{x}{n_1})^{n_1}$ (where $x$ is any number) $\in \mathcal{L}(V, \Sigma, P, S)$
  • $\pi = \sum_{n_1 = 0}^\infty \frac{(-1)^{n_1}}{2\cdot n_1 + 1}\in \mathcal{L}(V, \Sigma, P, S)$

Question

Now my problem is that this grammar suggests that you can enumerate each limit with it by using breadth first search. This means the language which is created by this grammar is countable. This either means

  • (1) that I forgot some important numbers which cannot be expressed that way or
  • (2) that there are numbers in $\mathbb{R}$ which cannot be expressed with a finite "formula" and my grammar cannot be extended so that it would work.

Now I want to know if (1) or (2) is the case.

  • If (1) is the case: What are characteristics of those numbers? What is their name? Obviously they cannot be in $\mathbb{Q}$ and there have to be at least countable infinite many of this kind as you can add numbers of $\mathbb{Q}$ to them, so if (1) is the case those numbers have to have some interesting properties
  • If (2) is the case: Which group did I forget? Which numbers cannot be expressed this way?
$\endgroup$
16
  • 3
    $\begingroup$ It is very clear what this question is about, and one should forgive the OP when it is not formulated in proper logolese. It is a central question of analysis. $\endgroup$ Feb 12, 2015 at 16:52
  • 2
    $\begingroup$ How would you express the real root of $\cos(x)=x$, for example? $\endgroup$ Feb 12, 2015 at 17:01
  • 1
    $\begingroup$ How would you express the square root of 2 using this grammar? How would you express the logarithm in base 10 of 3 using this grammar? There are more than a few other functions defined in Mathematics that aren't that easy to express in that way here. $\endgroup$
    – JB King
    Feb 12, 2015 at 17:08
  • 1
    $\begingroup$ @JBKing $\sqrt{2} = 2^{0.5}$. This is covered by the grammar. $\ln (1+x) = \sum_{k=1}^\infty (-1)^{k+1} \frac{x^k}{k}$, also covered by the grammar (once you have one logarithm, you get all other bases trivially). $\endgroup$ Feb 12, 2015 at 17:10
  • 1
    $\begingroup$ @RobertIsrael The language admits $\lim_{h\to0}\frac{f(x+h)-f(x)}{h}$ and probably Faa di Bruno's formula can save our lives even in the case that iterated derivatives don't have closed form, but the function is a composition of functions which iterated derivatives do have closed forms. Haven't checked but one would need to see if the restrictions on the indexes in Faa di Bruno can be modeled in the language. If they can, then all zeros of elementary functions should be "limit numbers". $\endgroup$
    – Tom
    Feb 12, 2015 at 18:35

3 Answers 3

5
$\begingroup$

Unknowable numbers, IIRC.

My recollection from computation theory is fuzzy, but this is a starting point:

http://c2.com/cgi/wiki?UnknowableNumbers

Also: the number of finite formulas is countable, whereas R is not.

$\endgroup$
2
  • $\begingroup$ Do you have a better source for "Unkowable numbers"? (a book / paper / article?) $\endgroup$ Feb 16, 2015 at 16:45
  • $\begingroup$ "The Unknowable" Hardcover – Aug 5 1999 by Gregory J. Chaitin. Also: cs.auckland.ac.nz/~chaitin/rov.html $\endgroup$
    – Jeffrey
    Feb 16, 2015 at 16:58
2
$\begingroup$

Chaitin's constant is not computable.

$\endgroup$
1
  • $\begingroup$ I am not too sure about it, but it seems to be another problem. $\endgroup$ Feb 12, 2015 at 17:13
1
$\begingroup$

This really needs a model theory tag IMO.

Dredging up the little model theory I remember, I believe that the fact you can't expand your grammar to do what you want it to, follows from the Lowenheim-Skolem theorem. This theorem tells you that any countable first order theory which has an infinite model has an infinite model of any size $\kappa$ where $\kappa$ is an infinite cardinal. This in particular means that if you translate your grammar into a theory you end up having a model of that theory of countable size. This then means that the theory can't define all reals since they are uncountable.

$\endgroup$

You must log in to answer this question.

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