## Tuesday, January 6, 2009

### There are no legal numbers

This appears to establish that all integers* are illegal, via a less formal version the following argument.

*(and by a fairly obvious extension, all numbers)

• Some integers are illegal (in the sense, for example, that you can't publish them without violating certain laws)
• Publishing encoded versions of illegal integers (say via some publicly available encoding algorithm) is also illegal
• Assume there is some smallest illegal integer, k
• It is presumably legal to publish k-1
• However, if I publish an algorithm to convert k-1 to an illegal integer (such as "add 1"), it would then be illegal to publish k-1, since with the algorithm it's an encoded version of the illegal integer
• Hence, k-1 is an illegal integer
• Therefore, since the algorithm for converting one less than an illegal integer to an illegal integer has already been published, there is no smallest illegal integer
• A similar argument applies to any integer one larger than an illegal number (with the algorithm "subtract 1"), so there is no largest illegal integer.
• therefore, all integers are illegal.

"I'm sorry, I couldn't do my arithmetic homework. It's against the law!"

#### 1 comment:

Alan said...

Well, in order for this to work, the function

f(k) = k+1

Would have to be an illegal function. Also, an expression for the number of functions to apply on a given number could also be illegal.

My intuition is that any combination of numbers, functions, and expressions that led to an illegal number would also be illegal, but I'm not so sure about the functions or expressions by themselves.