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 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 welldefined 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 selfreference paradoxes then serve as a proof of the nonequivalence 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,264 Thanks: 690  Re: Paradox on natural numbers Quote:
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 fourcharacter 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 wellformed 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 Englishlanguage 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  Re: Paradox on natural numbers Quote:
 
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 speedup 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 selfextracting program P which does the following : P =

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: 520 Math Focus: Calculus/ODEs  Re: Paradox on natural numbers Quote:
 
December 23rd, 2012, 08:53 AM  #10  
Senior Member Joined: Jun 2011 Posts: 298 Thanks: 0  Re: Paradox on natural numbers Quote:
 

Tags 
natural, numbers, paradox 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Natural numbers  yo79  Math Events  2  April 7th, 2013 02:11 AM 
Natural numbers  EulerRules  Number Theory  9  March 5th, 2013 09:39 AM 
The paradox between prime numbers and natural numbers.  Eureka  Number Theory  4  November 3rd, 2012 03:51 AM 
natural numbers !  rose3  Number Theory  1  January 13th, 2010 08:41 AM 
natural numbers from sets....not very natural  jinjouk  Number Theory  12  June 3rd, 2008 06:11 AM 