[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.

[mtdewcmu]

Interesting. I'm not all that up on philosophy, and I had to look up constructivism and the law of the excluded middle. Computers can only deal directly with discrete math, so that eliminates quite a bit of mathematics. Moreover, despite being regarded as Turing machines, you could in reality count all the states that a computer could be in, by counting the bits of memory, and you will find that it's a finite number. So computers are, in fact, only finite state machines. It's often overlooked that what makes a Turing machine a Turing machine is the infinitely-long tape. So computers occupy a fairly small sliver of the infinite universe of math.

Philosophically, my worldview is like that of science: the way to know something is by making observations and formulating and testing hypotheses. What we can observe is limited, and hypotheses are only models that are tested by successive approximations. I'm not sure I understand what you mean that that statement isn't required to have an ultimate truth. Presumably a statement like that has an answer, but the fact that something is knowable in principle doesn't mean that there's any way to get the answer. For instance, the Hubble telescope can see far away galaxies that we can never get an up close look at. The question of whether there's life somewhere else in the universe must have an answer, but we can't know what's in those galaxies; even with a better telescope, we'd be seeing what they looked like a billion years ago. Many things will never be known.

[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).

[mtdewcmu]

I'm referring to irrational numbers with no pattern. Square roots can be described and the digits can be enumerated by an algorithm. The diagonalization argument shows that there can't be a description for all irrational numbers.

[phaemon]

Just to be clear: you think that there are many irrational numbers that exist independently of which number system you use, but that there are infinitely many that do depend on the number system you use? Is that right?

[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.

[mtdewcmu]

"Many irrational numbers are easy to identify unambiguously."

Absolutely. Cantor proved that an infinite number of others can't be identified at all, because they outnumber all possible descriptions. Some numbers can only be described by an infinitely long list of digits, one that can't be produced by a Turing machine and contains an infinite amount of irreducible information. The Kolmogorov complexity is infinite.

Newton's equations describe a mathematical model of the universe that agrees well with measurements taken under familiar conditions. Einstein's equations describe a different mathematical model, one that has good agreement with experiment over a much wider range of conditions than Newton's. But general relativity has well-known problems. Its equations give nonsense solutions under some circumstances, e.g. singularities. Physical theories are models that predict the outcomes of experiments. They're reductionist out of necessity. It's unknown and probably unknowable as to whether a perfect model is possible, but there are likely things that can't be reduced.

[lutusp]

> Cantor proved that an infinite number of others can't be identified at all, because they outnumber all possible descriptions.

I'm tempted to say that that definition places those examples in a unique set, thus at least unambiguously identifying the set to which they belong.

[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".