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:40 am (UTC)104792 isnt a prime number.
..thats as far as I got. : ) But a nifty thing to think about.
no subject
Date: 2010-05-04 06:52 am (UTC)no subject
Date: 2010-05-04 06:53 am (UTC)no subject
Date: 2010-05-04 07:01 am (UTC)no subject
Date: 2010-05-04 06:44 am (UTC)2. Drop out of Mr. Truman's class
3. No such thing.
no subject
Date: 2010-05-04 06:52 am (UTC)no subject
Date: 2010-05-04 07:09 am (UTC)As for dropping out not resolving the conundrum...it resolves the conundrum of whether I need to resolve the conundrum. If I'm not in the class, I no longer have that need.
Reprogram the scenario and save the ship!
no subject
Date: 2010-05-04 07:11 am (UTC)no subject
Date: 2010-05-04 07:14 am (UTC)no subject
Date: 2010-05-04 10:56 am (UTC)no subject
Date: 2010-05-04 05:37 pm (UTC)no subject
Date: 2010-05-04 06:53 am (UTC)the
least
number
not
describable
in
under
ten
words.
no subject
Date: 2010-05-04 07:05 am (UTC)...that was a long sentence, but I think I figured it out, I just had to read what you said again. Ironically, it wasnt this comment that made me think of that.
I guess then the puzzle is really "what is the least number not OTHERWISE describable in under 10 words."
Though that did bring up that question to me--by who's words and notation? I bet most numbers could be described SOMEHOW in smaller numbers of words than what is circulating in common usage, which means that the answer is only good for a certain subset of notation and mathematics.
The simple thing, for example, would just to put big numbers into base 1000 or something (Im totally guessing here, I realize this wont work for many numbers), which inherently shortens the number considerably. While one does have to tack on a "in base ____", I still think with enough computer power, one could find just the right base with just the right number to make it all work out. ...or at least for a bunch of otherwise longer numbers. That said, thats just one very common way of changing notation and artificially shortening numbers. I am sure than any number of other possibilities are there that I dont even know about.
no subject
Date: 2010-05-04 07:08 am (UTC)Ding ding ding! That's the contradiction. And the problem is, you can't just say "Well, what's the next smallest number?" because that number now becomes the least number not describable in under ten words, which is again only nine words.
And yes, there are often ways to find a shorter way to describe a number, but by "minimal description" I mean the theoretical absolute shortest way a number could possibly be (uniquely) described.
no subject
Date: 2010-05-04 06:57 am (UTC)no subject
Date: 2010-05-04 07:00 am (UTC)no subject
Date: 2010-05-04 07:17 am (UTC)"The number of words in this sentence is nine" is indisputably a logically true statement. However, its exact logical opposite statement, "The number of words in this sentence is NOT nine", is also indisputably a logically true statement. Since we've just proven a contradiction, all statements are true. Logic has revealed this to us. :)
no subject
Date: 2010-05-04 07:41 am (UTC)no subject
Date: 2010-05-04 07:42 am (UTC)no subject
Date: 2010-05-04 05:32 pm (UTC)no subject
Date: 2010-05-04 05:37 pm (UTC)no subject
Date: 2010-05-04 03:21 pm (UTC)First: it should be the least number not describable in under ten words in English, which is 11 words. Now, both that number and the number above it (and every other number) falls back into the set, and the set resumes existence. Then you change it back to the least number indescribable in under ten English words, which is nine words, it falls back out of the set, the next number above does too, and the whole thing unzips again. Wait, hang on! You're still not specific enough- it's the least whole number indescribable in under ten English words! Set blips back into existence. Replace whole number with integer, and it vanishes. Oops, that ought to be positive integer. It reappears.
No, Barnabas, what you have here is a grammatically unstable set, which neither exists nor does not exist. Rather, it flickers in and out of existence context depending, like a fluorescent Schrödinger's cat with a bad ballast.
no subject
Date: 2010-05-04 05:35 pm (UTC)no subject
Date: 2010-05-04 05:09 pm (UTC)no subject
Date: 2010-05-05 05:14 am (UTC)I read your post, went back to cleaning, and then the paradox hit me like a brick to the head.
I fell to the floor giggling at how simple and clever it is!
Answers:
1) Yes.
2) Yes, it involves a handgun.
3) Match and point.
Now to sic some philosophers with baseball bats on your case.