The Number Description Paradox
May. 3rd, 2010 11:07 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
barnabas_trumanI am nearly done grading the second round of midterms, and overall my students are mostly doing better than usual, which puts me in a good mood. To celebrate, I shall write up an intriguing logical conundrum for you. Yes, for you! Aren't you special!
Consider the set of all natural (whole) numbers: N = {1, 2, 3, 4, ...}. Every number in N can be described by a sequence of words in the English language (or any language, really; for this argument we will use English, and the argument should work in a similar fashion any other language). Furthermore, there are a variety of ways each number can be described.
For example, the number 2 can be described as "two" or "one plus one" or "the first prime" or "the only even prime."
27 can be described as "twenty seven" or "three cubed" or "nine times three" or "the third cube number" or "the ninth multiple of three."
104729 can be described as "one hundred four thousand seven hundred twenty nine" or, more concisely, "the ten thousandth prime."
Note that for each number n there is some shortest way (or, in case of a tie, some shortest ways) to describe n. (In this case "shortest" is taken to mean "with the fewest words," not "with the fewest letters.") For instance, the shortest way to describe 2 is "two," which uses only one word. The shortest way to describe 27 is a tie between "twenty seven" and "three cubed," both of which use two words. The shortest way to describe 104729 is "the ten thousandth prime," which uses four words. We can call these shortest descriptions "minimal."
It can be readily observed that, in most cases, the larger a number is, the more words are required to describe it minimally. There are of course exceptions--for instance, 999999999999999 is pretty big, but can be described in just four words: "one quadrillion minus one."
What if we wanted to study all numbers that require, say, ten words or more to be minimally described? Clearly we'll have to get to a pretty high number before that many words are required, but it seems equally clear that we'll get to one eventually--there must be some numbers that can't be described in under ten words.
To formalize this, we'll need a little help from set theory. Let S be defined as the set of all numbers that cannot be described in under ten words: that is, if a number can be described in under ten words, it is not in S; if a number's minimal description requires ten words or more then that number is in S. For example, none of the numbers we've looked at so far would be in S; they can all be described in far fewer than ten words.
One of the important facts in set theory is that any non-empty set of natural numbers (that is, any non-empty subset of N) must have a least element. This is called the Well-Ordering Principle. For example, the set of all even numbers is a non-empty subset of N, so by the Well-Order Principle it must have a least element (which is 2). The set of all cubes of odd prime numbers is a non-empty subset of N, so it must have a least element (which is 27).
In particular, the Well-Ordering Principle demands that S has a least element. Let us call this least element x. What can we say about x? First, x is a member of S, so by definition, it cannot be described in under ten words. Second, x is the least element of S, so it is the least number not describable in under ten words.
That is: x is the least number not describable in under ten words.
Chew on that one for a while. x is the least number not describable in under ten words.
Discussion Questions
1) Do you see what's wrong here?
2) Can you suggest any way to resolve this conundrum?
3) Isn't set theory just magnificently wicked? Diabolical, really.
Consider the set of all natural (whole) numbers: N = {1, 2, 3, 4, ...}. Every number in N can be described by a sequence of words in the English language (or any language, really; for this argument we will use English, and the argument should work in a similar fashion any other language). Furthermore, there are a variety of ways each number can be described.
For example, the number 2 can be described as "two" or "one plus one" or "the first prime" or "the only even prime."
27 can be described as "twenty seven" or "three cubed" or "nine times three" or "the third cube number" or "the ninth multiple of three."
104729 can be described as "one hundred four thousand seven hundred twenty nine" or, more concisely, "the ten thousandth prime."
Note that for each number n there is some shortest way (or, in case of a tie, some shortest ways) to describe n. (In this case "shortest" is taken to mean "with the fewest words," not "with the fewest letters.") For instance, the shortest way to describe 2 is "two," which uses only one word. The shortest way to describe 27 is a tie between "twenty seven" and "three cubed," both of which use two words. The shortest way to describe 104729 is "the ten thousandth prime," which uses four words. We can call these shortest descriptions "minimal."
It can be readily observed that, in most cases, the larger a number is, the more words are required to describe it minimally. There are of course exceptions--for instance, 999999999999999 is pretty big, but can be described in just four words: "one quadrillion minus one."
What if we wanted to study all numbers that require, say, ten words or more to be minimally described? Clearly we'll have to get to a pretty high number before that many words are required, but it seems equally clear that we'll get to one eventually--there must be some numbers that can't be described in under ten words.
To formalize this, we'll need a little help from set theory. Let S be defined as the set of all numbers that cannot be described in under ten words: that is, if a number can be described in under ten words, it is not in S; if a number's minimal description requires ten words or more then that number is in S. For example, none of the numbers we've looked at so far would be in S; they can all be described in far fewer than ten words.
One of the important facts in set theory is that any non-empty set of natural numbers (that is, any non-empty subset of N) must have a least element. This is called the Well-Ordering Principle. For example, the set of all even numbers is a non-empty subset of N, so by the Well-Order Principle it must have a least element (which is 2). The set of all cubes of odd prime numbers is a non-empty subset of N, so it must have a least element (which is 27).
In particular, the Well-Ordering Principle demands that S has a least element. Let us call this least element x. What can we say about x? First, x is a member of S, so by definition, it cannot be described in under ten words. Second, x is the least element of S, so it is the least number not describable in under ten words.
That is: x is the least number not describable in under ten words.
Chew on that one for a while. x is the least number not describable in under ten words.
Discussion Questions
1) Do you see what's wrong here?
2) Can you suggest any way to resolve this conundrum?
3) Isn't set theory just magnificently wicked? Diabolical, really.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2010-05-04 06:57 am (UTC)no subject
Date: 2010-05-04 07:00 am (UTC)