3

The set of real numbers contains element which can be represented (there exists a way to write them down on paper). These numbers include:

  • Integer numbers, such as $-8$, $20$, $32412651$
  • Rational numbers, such as $\frac{7}{41}$, $-\frac{14}{3}$
  • Algebraic numbers
  • Any other number that can be created by a chain of functions whose definition is also finite (ex.: $\sin(\cos(\sqrt{445}))$, $\pi$, $e$)

Another way of thinking about these is that it's possible to write a computer program occupying a finite amount of space that can generate them to any precision (or return it's nth digit).

The set of reals also contains numbers which are impossible to represents (whose digits follow absolutely no logic). We never use such numbers because there is no way of writing them down.

My questions are:

  • What are these numbers called?
  • What is a more formal definition of them?
Asaf Karagila
  • 393,674

1 Answers1

3

The numbers you are describe in your list are called computable numbers meaning they can be computed to arbitrary precision. Equivalently, a number $x$ is computable if it is decidable, given rational $a$ and $b$, if $x\in (a,b)$.

The other numbers are said to be noncomputable. It is worth noting, however, that some noncomputable numbers can still be written down - for instance: $$\sum_{n=0}^{\infty}2^{-BB(n)}$$ where $BB$ is the busy beaver function (which isn't computable).

Milo Brandt
  • 60,888
  • 2
    Pretty sure they are looking for the definable numbers, which include the computable but also others that can be written down but not computed: https://en.wikipedia.org/wiki/Definable_real_number – Alan Sep 05 '15 at 04:49
  • 1
    @Alan What do they mean with "standard model" of set theory? As they list $0^{#}$ as a definable number, $L$ is not what they're having in mind (and it probably should read that $0^{#}$ is definable if it exists anyways). – Stefan Mesken Sep 05 '15 at 07:53
  • 1
    @Alan: That page should be deleted from Wikipedia. Or at least rewritten from scratch. – Asaf Karagila Sep 05 '15 at 09:16