12
$\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$
  • $\begingroup$ This is a very deep problem. $\endgroup$ – Christian Blatter Jun 26 '13 at 20:13
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$
  • $\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 '13 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 '13 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 '13 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
    $\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 '13 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 '13 at 1:38
-2
$\begingroup$

I think what you need is this Completeness Theorem:

Each contracting sequence of intervals has a common point; that is, the intersection of all the intervals of the family is not empty.

The basic idea is if the real number $c$ in the proof (below) is the number that you want a finite representation for (your randomly defined number for example), the construction given in the proof represents a finite way of defining the contracting sequence of intervals such that $c$ is in the intersection of all of them.

Here's the proof given in First Concepts of Topology, by Chinn and Steenrod.

Definition. an infinite sequence of closed intervals of real numbers $I_0, I_1, ..., I_n$ is called a contracting sequence if each interval contains the next and hence all intervals that follow: $$I_0 \supset I_1 \supset I_1 \supset ... \supset I_n \supset ...$$ A contracting sequence is called a regularly contracting sequence if $I_0 = [m, m+ 1]$ is the interval from an integer $m$ to the next integer $m + 1,$ and, for each $n >= 1$ $I_n$ is one of the intervals obtained by partitioning $I_{n-1}$ into ten equal parts. Thus $I_1$ is a tenth part of $I_0,$ $I_2$ a tenth part of $I_1$ and so on. The length of $I_n$ is $10^{-n}.$

Consider first the case of a regularly contracting sequence. For each $n = 0, 1, 2, ...$ let $a_n$ denote the left-hand endpoint of $I_n.$ Then $a_0 = m$ is an integer. Since $I_n$ has length $10^{-n}$, $I_n = [a_n, a_{n+10^{-n}}].$ The points that divide $I_{n-1}$ into ten equal parts are

$$a_{n-1}, a_{n-1} + \frac{1}{10^n}, a_{n-1} + \frac{2}{10^n}, ..., a_{n-1}+\frac{10}{10^n}.$$

Since $I_n$ is one of these ten subintervals, its left endpoint must be $$a_n = a_{n-1} + \frac{k_n}{10^n},$$ where $k_n$ is one of the digits $0, 1, 2, ..., 9.$ In this way the sequence of intervals determines an integer $m$ and an infinite sequence of digits $k_1, k_2, ..., k_n, ....$ Let $c$ denote the real number $$c = m + \frac{k_1}{10} + \frac{k_2}{10^2} + ... + \frac{k_n}{10^n} + ....$$ (that is, the decimal expansion of $c$ is $m.k_1k_2,...$).

Since $$a_n = m + \frac{k_1}{10} + \frac{k_2}{10^2} + ... + \frac{k_n}{10^n},$$ it is clear that $a_n <= c$. Now the decimal expansions of $a_n + \frac{1}{10^n}$ and of $c$ agree out to the n'th digits, but the n'th digit of $c$ is $k_n$ while that of $a_n + \frac{1}{10^n}$ is $k_n + 1$. It follows that $$a_n <= c <= a_n + \frac{1}{10^n}.$$

These inequalities assert that $c \in I_n$ and since they hold for every integer $n,$ it follows that $c$ lies in each interval of the sequence, hence in the intersection of all of them. This proves the theorem in case the sequence contracts regularly.

The case where the sequence does not contract regularly is similar, and the same book gives a proof. I am not going to enter it here right now, but would be happy to put the second part in also.

$\endgroup$
  • 1
    $\begingroup$ This construction defines $c$ in terms of a sequence of intervals, which is defined, in turn, using $c$. As a result, there isn't really any definition of $c$ here at all. $\endgroup$ – Andreas Blass Jun 26 '13 at 22:20
  • $\begingroup$ Nevertheless the construction is valid for all n, and gives a finite representation. It is also a completeness theorem for the real numbers; in full it addresses the part of the question related to possible "gaps" in the real numbers. $\endgroup$ – Circulwyrd Jun 27 '13 at 0:11
  • 3
    $\begingroup$ How does this give a finite representation if there is an infinite number of intervals required to specify a generic real number? $\endgroup$ – anon Jun 27 '13 at 0:59
  • $\begingroup$ @GregHill The only thing finite here seems to be the text you wrote, describing how to convert $c$ into an infinitely long "construction" that characterizes the $c$ you began with. The construction itself involves infinitely many intervals, whereas "valid for all n" seems to refer to a notion of validity that has n as a parameter. $\endgroup$ – Andreas Blass Jun 27 '13 at 1:57
  • $\begingroup$ @AndreasBlass Not convert, but show identical. I may not have explained it in a way that is accepted, and I can't reproduce the whole part of the text I quoted from verbatim, but insofar as I understood the question and observed that it is the same as answered in the source text, I remain in the dark as to why my answer is wrong. I think I'll start a negative number support group now ... $\endgroup$ – Circulwyrd Jun 27 '13 at 2:05

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.