My Math Forum Paradox on natural numbers

 Applied Math Applied Math Forum

 December 1st, 2012, 04:56 PM #1 Newbie   Joined: Nov 2012 Posts: 25 Thanks: 0 Paradox on natural numbers Hi... Can anyone please help me with this problem statement. Let N be the set of all natural numbers that can be described with a sentence of one hundred characters or less. Clearly there are at most 100^127 such numbers where all 127 printable ASCII characters have been permitted. Let n be the first number not in the set N. This sentence which describes the number n has less than one hundred characters. Then n belong to set N. Can anyone help me in solving this Paradox?
 December 2nd, 2012, 01:19 AM #2 Senior Member   Joined: May 2008 From: York, UK Posts: 1,300 Thanks: 0 Re: Paradox on natural numbers Firstly, as far as I can see there are 95 printable ASCII characters, not 127! But it doesn't really matter how many there are, so we'll call this number C. It follows that the total number of different strings of no more than 100 characters is $S:=\sum_{k=0}^{100} C^k.$ Note that the empty string "" is different from a single space " " which is again different from two spaces " ", and so on. If we assign a different integer in a set N to each possible string then we can represent S different integers, but note that we will have to explicitly give the relationship between strings and integers, so one might argue that this doesn't fulfil the conditions of the original problem. The string "Let n be the first number not in the set N" then already represents one of the numbers in N. On the other hand, we might demand that the number being described by the string is obvious from context, which makes this harder to resolve. We would then have to conclude that "the first number not in the set N" was both in N and not in N. This is really just a variant of Russell's paradox, and the set you describe would not be well defined in ZFC set theory.
 December 21st, 2012, 03:18 PM #3 Newbie   Joined: Dec 2012 From: France Posts: 6 Thanks: 0 Re: Paradox on natural numbers The property "be described with a sentence of one hundred characters or less" is not a mathematically well-defined property. It is possible to develop some formal mathematical constructions inspired by this idea. But there cannot be a unique way to do it, as it will necessarily depend on a choice of formalism (theory) in which "descriptions" can be expressed and interpreted. And no theory can ever correctly describe and interpret the full meaning of all its own formulas in a single formula; only a second theory can take an external view on a first theory to interpret its whole meaning. The formal application of such self-reference paradoxes then serve as a proof of the non-equivalence between both theories. In particular it takes the form of Tarski's Truth Undefinability theorem, and Gödel's Incompleteness theorem. I describe these things in details in my web site settheory.net.
December 21st, 2012, 06:51 PM   #4
Senior Member

Joined: Aug 2012

Posts: 2,355
Thanks: 737

Quote:
 Originally Posted by unm Hi... Can anyone please help me with this problem statement. Let N be the set of all natural numbers that can be described with a sentence of one hundred characters or less. Clearly there are at most 100^127 such numbers where all 127 printable ASCII characters have been permitted. Let n be the first number not in the set N. This sentence which describes the number n has less than one hundred characters. Then n belong to set N. Can anyone help me in solving this Paradox?
I think the trick is that you have to clarify that the set of all natural numbers that can be described in 100 characters or less is relative to a fixed language and notation.

So if I say, "The smallest number not expressible in four characters or fewer, in standard decimal notation," I am unambiguously referring to the number 10000.

And yet 10^4 is a four-character description of this very same number, isn't it? But there's no paradox, because 10^n is not a valid expression in standard decimal notation.

The expression, "The smallest N that can not be expressed in 100 characters in notation X," is perfectly unambiguous. You could in principle simply enumerate all the well-formed expressions in notation X and circle the first one of length 101 ... and then map it to the particular natural number it designates, in notation X.

Now the paradox goes away. Because the English-language phrase "The smallest N that can not be expressed in 100 characters in notation X," is not a valid expression in notation X. It's a valid expression in English, a different notation. So there's no paradox.

 December 21st, 2012, 07:59 PM #5 Math Team   Joined: Dec 2006 From: Lexington, MA Posts: 3,267 Thanks: 408 Re: Paradox on natural numbers This is one of the classic paradoxes, usually introduced in a Logic course. Most integers require more than nineteen syllables to describe them. [color=beige]. . [/color](After all, most integers have billions of digits.) Among them, there must be a least integer. We don't know its value, but we can describe it. [color=beige]. . [/color]"The least integer not expressible in nineteen syllables or less." We find that we have described that number in eighteen syllables.
December 22nd, 2012, 05:51 PM   #6
Senior Member

Joined: Feb 2010

Posts: 199
Thanks: 0

Quote:
 Originally Posted by soroban This is one of the classic paradoxes, usually introduced in a Logic course. Most integers require more than nineteen syllables to describe them. [color=beige]. . [/color](After all, most integers have billions of digits.) Among them, there must be a least integer. We don't know its value, but we can describe it. [color=beige]. . [/color]"The least integer not expressible in nineteen syllables or less." We find that we have described that number in eighteen syllables.
ha! i like that

 December 23rd, 2012, 04:36 AM #7 Newbie   Joined: Dec 2012 From: France Posts: 6 Thanks: 0 Re: Paradox on natural numbers You like that already ? But it's just an appetizer. You did not see anything yet. There is much more. There is Gödel's incompleteness theorem that some true formulas are provable, based on a formula that says "This formula is not provable in theory T". And a corollary of this theorem, which says that the formula "This formula is provable" is provable. There is Gödel's speed-up theorem, based on a formula that says "This formula is not provable in theory T in fewer than a googolplex symbols", which clearly is a provable formula whose proof requires more than a googolplex symbols. And there is Chaitin's theorem which says that for any consistent theory T, no sufficiently big file can ever be provably incompressible according to T, for lack of refutability in T of the claim of its compressibility into the self-extracting program P which does the following : P =Search for any possible proof in T of a formula of the type "F is not the output of P" for whatever file F;[/*:2lwxyxy5] Once the first such proof is found, output F[/*:2lwxyxy5] This is actually formalizable as a program (a very impractical one indeed as it will never output anything, but...).
 December 23rd, 2012, 04:40 AM #8 Newbie   Joined: Dec 2012 From: France Posts: 6 Thanks: 0 Re: Paradox on natural numbers Of course I meant "that some true formulas are unprovable". I'm surprised that message corrections are impossible in this forum, even immediately after posting.
December 23rd, 2012, 04:43 AM   #9
Senior Member

Joined: Jul 2010
From: St. Augustine, FL., U.S.A.'s oldest city

Posts: 12,211
Thanks: 521

Math Focus: Calculus/ODEs

Quote:
 Originally Posted by spoirier ...I'm surprised that message corrections are impossible in this forum, even immediately after posting.
You will be able to edit your posts once your status changes from Newcomer.

December 23rd, 2012, 08:53 AM   #10
Senior Member

Joined: Jun 2011

Posts: 298
Thanks: 0

Quote:
 Originally Posted by unm Hi... Can anyone please help me with this problem statement. Let N be the set of all natural numbers that can be described with a sentence of one hundred characters or less. Clearly there are at most 100^127 such numbers where all 127 printable ASCII characters have been permitted. Let n be the first number not in the set N. This sentence which describes the number n has less than one hundred characters. Then n belong to set N. Can anyone help me in solving this Paradox?
Let x be any sentence containing a hundred or less characters, and x is in N. Since any character in x cannot be x, it cannot be in itself, so x is a sentence containing more than a hundred characters. From this fact we know that x is not in N. But didn't we say that x is in N earlier, in bold?

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post yo79 Math Events 2 April 7th, 2013 02:11 AM EulerRules Number Theory 9 March 5th, 2013 09:39 AM Eureka Number Theory 4 November 3rd, 2012 03:51 AM rose3 Number Theory 1 January 13th, 2010 08:41 AM jinjouk Number Theory 12 June 3rd, 2008 06:11 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top