5 ms·

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 finit

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 13y ago
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?
- consz 13y ago
  The set of irrational numbers which can be defined algorithmically are programable, eg. they are defined by a program of finite length.
  - hollerith 13y ago
    >The set of irrational numbers which can be defined algorithmically are programable You mean "computable".
- nwhitehead 13y ago
  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_theory http://en.wikipedia.org/wiki/Controversy_over_Cantor%27s_the...
  - mtdewcmu 13y ago
    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.
    - phaemon 13y ago
      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 13y ago
        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 13y ago
        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?
        mtdewcmu 13y ago
        Irrational numbers, by definition, include decimal numbers that have infinitely many digits after the decimal point, and there are no rules about what those digits have to be. This is powerful enough to represent any irrational number regardless of the number base. However, if you're talking about number systems, not all number systems have equal ability to represent irrational numbers. Whatever the system, to represent all the irrationals, it would have to be capable of going on forever. I think the part of my point that you're asking about is my statement that they're a side effect of decimal numbers. Irrational numbers like sqrt(2) and e have concise representations as the limits of Taylor series. Only when converted into decimals do they appear to have infinite amounts of information. So if we used Taylor series as the number system instead of decimals, simple irrationals would look simple, and we might be less inclined to treat them the same as numbers that have no finite descriptions at all.

nawitus 13y ago

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?

consz 13y ago
The set of irrational numbers which can be defined algorithmically are programable, eg. they are defined by a program of finite length.
- hollerith 13y ago
  >The set of irrational numbers which can be defined algorithmically are programable You mean "computable".
nwhitehead 13y ago
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_theory http://en.wikipedia.org/wiki/Controversy_over_Cantor%27s_the...
- mtdewcmu 13y ago
  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.
  - phaemon 13y ago
    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 13y ago
      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 13y ago
        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?
        mtdewcmu 13y ago
        Irrational numbers, by definition, include decimal numbers that have infinitely many digits after the decimal point, and there are no rules about what those digits have to be. This is powerful enough to represent any irrational number regardless of the number base. However, if you're talking about number systems, not all number systems have equal ability to represent irrational numbers. Whatever the system, to represent all the irrationals, it would have to be capable of going on forever. I think the part of my point that you're asking about is my statement that they're a side effect of decimal numbers. Irrational numbers like sqrt(2) and e have concise representations as the limits of Taylor series. Only when converted into decimals do they appear to have infinite amounts of information. So if we used Taylor series as the number system instead of decimals, simple irrationals would look simple, and we might be less inclined to treat them the same as numbers that have no finite descriptions at all.