11
$\begingroup$

It occurred to me that there must be a lot of numbers without any form of finite representation on paper. Is there a name for these numbers?

For example...

Integers and rationals have a very simple representation e.g. 3/4

Irrational numbers obviously can also have a finite representation: 1.41421356... can be written as "the solution to the equation x^2 = 2"

Transcendental numbers can also have a finite representation: e can be written as "the limit of (1 + 1/n)^n as n approaches infinity"

In other words, with a finite amount of effort one can give the reader enough information to calculate the value of the specified number exactly (to any degree of accuracy the reader chooses)

However, there must be a lot of numbers where this simply is not possible.

Consider the number 1.2736358762987349862379358... where this is just a string of (genuinely) random digits. There is no way to provide a finite definition that will specify this number to an arbitrary degree of accuracy. Similarly, there is no equation to which this number is a solution (I think, although I don't know how one would prove this).

Does this mean there are "gaps" in the real numbers. The number above is definitely somewhere between 1.2 and 1.3 but there is no way I can specify the value of this number (without writing an infinite number of digits). The number exists on the number line but I will never be able to do anything with it.

Is there a name for these numbers? Can anyone point me to some interesting resources on this topic?

I'm only asking as an interested hobbyist so apologies if this question isn't very scientific.

$\endgroup$
1
  • $\begingroup$ This is a very deep problem. $\endgroup$
    – Christian Blatter
    Jun 26, 2013 at 20:13

6 Answers 6

Reset to default
16
$\begingroup$

That depends on what you mean by "representation." One way to cash this out is to talk about the definable numbers. These are more general than the computable numbers, but they are still countable because there are still only countably many possible descriptions of a number in a language over a finite alphabet.

$\endgroup$
3
  • $\begingroup$ Thanks Qiachu, exactly what I was looking for. Very interesting reading. Although I am struggling to get my head round what it means to be definable but not computable - probably too complicated for this layman's understanding. $\endgroup$
    – njr101
    Jun 27, 2013 at 8:11
  • 4
    $\begingroup$ @njr: roughly speaking, definable numbers are allowed to be the answers to questions which can't be solved by algorithms as long as they can be posed by set theory. For example, fix an enumeration of all Turing machines, and consider the binary decimal $0.d_1 d_2 d_3 ...$ whose $n^{th}$ digit is $0$ if the $n^{th}$ Turing machine halts and $1$ otherwise (related to but easier to define than Chaitin's constant (en.wikipedia.org/wiki/Chaitin's_constant)). This number is uncomputable because a Turing machine computing it can solve the halting problem, but it is still definable in the... $\endgroup$
    – Qiaochu Yuan
    Jun 27, 2013 at 8:17
  • 2
    $\begingroup$ ...sense that set theory can specify this number (set theory can talk about Turing machines and can talk about the function which describes whether they halt or not even though this function is not computable). $\endgroup$
    – Qiaochu Yuan
    Jun 27, 2013 at 8:18
8
$\begingroup$

I believe what you are describing are numbers which are not computable. I think that http://en.wikipedia.org/wiki/Computable_number explains it well enough. Actually, almost all numbers are not computable.

$\endgroup$
6
$\begingroup$

In addition to Daniel R.'s link, you might find the notion of Kolmogorov complexity (a.k.a "descriptive complexity") useful. As a very short summary, descriptive complexity measures how easy it is to write an exact description of a number; the numbers you're talking about don't have a description with a finite length, or any description "denser" than a simple list of the number's digits. By contrast, the transcendental number $e$ has no algebraic description, but it can be described very compactly by any one of its several unique properties (e.g., "the base of the natural logarithm").

$\endgroup$
3
$\begingroup$

The number of finite names/words over a finite alphabet is countable, so you cannot name every irrational. Certainly, if you would use infinite words or infinite alphabet...

$\endgroup$
1
$\begingroup$

The OP is describing Brouwer's choice sequences almost exactly. The whole of intuitionistic analysis is based on them. 'This fluidity was achieved by admitting as "points", not only fully defined discrete numbers such as [root] 2, pi, e, and the like - which have, so to speak, already achieved "being" - but also "numbers" which are in a perpetual state of becoming in that the entries in their decimal (or dyadic) expansions are the result of free acts of choice by a subject operating throughout an indefinitely extended time.' The Continuous and the Infinitesimal, John L Bell.

$\endgroup$
0
$\begingroup$

You pick up an interesting subject. In my opinion you should do research into Math Logic (definability, etc.).

Assume you formally proved that some number is not definable (by means of symbols on a piece paper as you said). Then you come up with a paradox because your formal proof (a lot of finite number of symbols from a formal language) is already a some kind of "representation" of the number on paper.

It implies that even if such kind of number exists,formal proof of its existence is impossible.

That reminds me Continuum Hypothesis.

$\endgroup$
2
  • 2
    $\begingroup$ There is a difference between proving the existence of a specific number and proving the existence of a set of numbers. The fact that undefinable numbers exist follows from showing that definable numbers are countable and real numbers are uncountable. So they can collectively be shown to exist, even if we can't single out a particular one to prove the existence of in isolation. $\endgroup$
    – anon
    Jun 27, 2013 at 0:56
  • $\begingroup$ Of course there is. I am not arguing that proving their existence as a set is the same thing as proving the existence of a single number. $\endgroup$
    – fade2black
    Jun 27, 2013 at 1:38

You must log in to answer this question.

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