[mag487]

The key phrases there are "almost surely" and "most irrational numbers." There are irrational numbers like pi which can be defined algorithmically, but taken together as a set they have zero Lebesgue measure. (In fact, they're countable.)

[nawitus]

I didn't know that. Any link to a proof?

[nwhitehead]

Consider the set P of programs that take no input and generate an infinite stream of digits. Each program in P has a finite length and is written out of a finite set of symbols, so there must only be a finite number of programs of any given length. That makes P countable. Let Q be the set of numbers described by programs in P. Each program from P describes exactly one number, so Q must also be countable. The set of irrational numbers is uncountable, so there must be an uncountable set of "complex" irrational numbers remaining after you take away all the "non complex" ones in Q.

[nawitus]

Your proof seems to only prove that a finite number of programs (described by you) which can produce a finite number of irrational numbers, while there are infinite number of irrational numbers.

But we're surely not talking about a finite number of programs.

I'm not even sure what the Kolmogorov complexity of a "complex irrational number" means. If you need the sequence of digits and you cannot use an algorithm to produce the digits, then the complexity is infinite?

[nwhitehead]

For each fixed length there are a finite number of programs of that length. If we use 8-bit bytes for the alphabet, there are 256^N programs of length N. The set of ALL programs is infinite (we don't limit the length of programs), but it is countable.

The "countable" part means we can put the set into one-to-one correspondence with the natural numbers. The correspondence starts with 0 mapping to the empty program, then 1-256 mapping to programs of a single byte, then 257-65793 mapping to the programs of two bytes, and so on. This mapping will hit each program exactly once, and it will hit every program because every individual program has a finite length.

Different types of infinities are not intuitive so don't feel bad if the concepts are confusing. These issues troubled lots of very smart mathematicians for decades. The existence of irrational numbers was hugely troubling to Pythagoreans. The existence of uncountable infinities discovered by Cantor was shocking [1].

[1]: http://en.wikipedia.org/wiki/Controversy_over_Cantor%27s_the...

[mtdewcmu]

In some sense, the existence of irrational numbers with no pattern in their digits is an illusory artifact of the number system. We can talk about them collectively because decimals are not required to have an end, and we have to postulate them to fill in the gaps in the number line, but such numbers lack any description or means of being separated as individuals.

But then, is any mathematical abstraction real? I guess it's all beside the point.

[nwhitehead]

> But then, is any mathematical abstraction real? I guess it's all beside the point.

I actually think the reality of mathematical abstractions is hugely important because of... computer programs! In a real way, programs are the embodiment of mathematics. I want my programs to work so I need the underlying math to work as well.

That's why I'm a constructivist. I reject the law of the excluded middle because proofs that use it don't translate into real programs; they translate into programs that ask an omnipotent oracle to decide which branch to take. Constructive proofs translate into working programs.

It also ties into philosophy. I am a skeptic, so when someone tells me either A or not A must be true even if we can never know which one, I ask for proof or justification of that fact. The justifications that I get are remarkably similar to logical "proofs" that god exists, and just as fallacious. This isn't to say that there couldn't be an ultimate truth about A or a god, just that it is not logically necessary.

[phaemon]

This is wrong. The square root of two was identified as irrational by the ancient Greeks, when considering the length of the diagonal of the unit square. The proof has nothing to do with decimal fractions (they didn't use decimal fractions at all).

[lutusp]

> In some sense, the existence of irrational numbers with no pattern in their digits is an illusory artifact of the number system.

But irrational numbers remain irrational in any integer number base. Therefore no, they aren't illusory at all, nor are they an artifact of the "number system".

> ... such numbers lack any description or means of being separated as individuals.

Also false. Many irrational numbers are easy to identify unambiguously. For example, the square roots of numbers that are not perfect squares are irrational, but they can be easily identified by squaring them.

While we're on the topic, the terms in the running sum of odd numbers are all perfect squares:

    0 + 1 =  1
    1 + 3 +  4
    4 + 5 =  9
    9 + 7 = 16
   16 + 9 = 25

As is often true in mathematics, this is easier to explain with a picture:

http://arachnoid.com/example/#Math_Example

> But then, is any mathematical abstraction real?

Certainly. Consider general relativity. It's a mathematical abstraction, and it's also real.

[consz]

The set of irrational numbers which can be defined algorithmically are programable, eg. they are defined by a program of finite length.

[hollerith]

>The set of irrational numbers which can be defined algorithmically are programable

You mean "computable".

[mag487]

There's only a countable number of formulas of ZFC. Therefore, there's only a countable number ways of writing out a formula of ZFC that uniquely specifies a real number. Therefore, only countably many real numbers exist that have such definitions. And all countable sets of reals have zero Lebesgue measure.

[nawitus]

Additional question: what's the Kolmogorov complexity of a irrational numberwhich is not described with a ZFC formula? And how is it described?

[mag487]

I haven't really studied algorithmic information theory, but I'd assume that Kolmogorov complexity isn't defined for uncomputable/undefinable numbers. Or maybe it's defined as "infinite," but either way, my guess is that such numbers are simply ignored. (Interestingly, the function which takes a computable number and outputs its Kolmogorov complexity is itself uncomputable!)

[nawitus]

The article at least implies that the Kolmogorov complexity of uncomputable irrational numbers is larger than computable irrational numbers.