Interesting function

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Posts: 139
Joined: Tue Nov 07, 2006 6:36 pm UTC
Location: Fremont, CA

Interesting function

Postby oblivimous » Mon May 21, 2007 7:16 pm UTC

f(n) defined as the smallest number such that all proveable statements with a length of n characters can be proved in f(n) characters or less, and f(n) = 0 if there are no proveable statements with length n.

So if f(30) = 500 that means "Every 30-character-statement has a 500(or less)-character-proof or it cannot be proved at all"

I'm pretty sure this function exists for all whole number values of n. Although if we replace 'proveable' with 'true' then incompleteness may become an issue.

I think incompleteness also gives us this: there is no computable function g(n) such that we can know that g(n) > f(n) for all n

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Postby skeptical scientist » Mon May 21, 2007 9:13 pm UTC

In fact, there is no computable function g such that g(n)>f(n) for all n, even if we didn't know it (if there were, the set of provable statements would be computable, and that would give you a complete extension of PA).
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 8 guests