saturn comments on The Lifespan Dilemma - Less Wrong

39 Post author: Eliezer_Yudkowsky 10 September 2009 06:45PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (214)

You are viewing a single comment's thread. Show more comments above.

Comment author: saturn 11 September 2009 08:30:52AM *  25 points [-]

Imagine A is the set of all positive integers and B is the set of all positive even integers. You would say B is smaller than A. Now multiply every number in A by two. Did you just make A become smaller without removing any elements from it?

Comment author: Alicorn 11 September 2009 12:32:04PM 8 points [-]

...Okay, that's weird! Clearly that shouldn't work. Thanks for the counterexample.

Comment author: DanielH 27 July 2013 04:32:36AM *  0 points [-]

It gets even worse than that if you want to keep your intuitions (which are actually partially formalized as the concept natural density). Imagine that T is the set of all Unicode text strings. Most of these strings, like "๐Ÿ‚พโจŸ๊ —โˆงฬŠโฉถ๐Ÿ", are gibberish, while some are valid sentences in various languages (such as "The five boxing wizards jump quickly.", "print 'Hello, world!'", "แผ”ฯƒฯ‡ฮฑฯ„ฮฟฯ‚ แผฯ‡ฮธฯแฝธฯ‚ ฮบฮฑฯ„ฮฑฯฮณฮตแฟ–ฯ„ฮฑฮน แฝ ฮธแฝฑฮฝฮฑฯ„ฮฟฯ‚ฮ‡", or "ื•ืงืจืืชื ื‘ืฉื ืืœื”ื™ื›ื ื•ืื ื™ ืืงืจื ื‘ืฉื ื™ื”ื•ื” ื•ื”ื™ื” ื”ืืœื”ื™ื ืืฉืจ ื™ืขื ื” ื‘ืืฉ ื”ื•ื ื”ืืœื”ื™ื ื•ื™ืขืŸ ื›ืœ ื”ืขื ื•ื™ืืžืจื• ื˜ื•ื‘ ื”ื“ื‘ืจ"). The interesting strings for this problem are things like "42", "22/7", "e", "10โ†‘โ†‘(10โ†‘โ†‘10)", or even "The square root of 17". These are the strings that unambiguously describe some number (under certain conventions). As we haven't put a length limit on the elements of T, we can easily show that every natural number, every rational number, and an infinite number of irrational numbers are each described by elements of T. As some elements of T don't unambiguously describe some number, our intuitions tell us that there are more text files than there are rational numbers.

However, a computer (with arbitrarily high disk space) would represent these strings encoded as sequences of bytes. If we use a BOM in our encoding, or if we use the Modified UTF-8 used in Java's DataInput interface, then every sequence of bytes encoding a string in T corresponds to a different natural number. However, given any common encoding, not every byte sequence corresponds to a string, and therefore not every natural number corresponds to a string. As encoding strings like this is the most natural way to map strings to natural numbers, there must intuitively be more natural numbers than strings.

We have thus shown that there are more strings than rational numbers, and more natural numbers than strings. Thus, any consistent definition of "bigger" that works like this can't be transitive, which would rule out many potential applications of such a concept.

EDIT: Fixed an error arising from my original thoughts differing from the way I wanted to explain them