My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
December 1st, 2012, 04:56 PM   #1
unm
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?
unm is offline  
 
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.
mattpi is offline  
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.
spoirier is offline  
December 21st, 2012, 06:51 PM   #4
Senior Member
 
Joined: Aug 2012

Posts: 2,355
Thanks: 737

Re: Paradox on natural numbers

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.
Maschke is online now  
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.

soroban is offline  
December 22nd, 2012, 05:51 PM   #6
Senior Member
 
Solarmew's Avatar
 
Joined: Feb 2010

Posts: 199
Thanks: 0

Re: Paradox on natural numbers

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
Solarmew is offline  
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...).
spoirier is offline  
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.
spoirier is offline  
December 23rd, 2012, 04:43 AM   #9
Senior Member
 
MarkFL's Avatar
 
Joined: Jul 2010
From: St. Augustine, FL., U.S.A.'s oldest city

Posts: 12,211
Thanks: 521

Math Focus: Calculus/ODEs
Re: Paradox on natural numbers

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.
MarkFL is offline  
December 23rd, 2012, 08:53 AM   #10
Senior Member
 
Joined: Jun 2011

Posts: 298
Thanks: 0

Re: Paradox on natural numbers

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?
Math Dreamer is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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





Copyright © 2019 My Math Forum. All rights reserved.