There is an old joke about the smallest non-interesting number being interesting in itself (I have heard it attributed to Richard Hamming). This is then used to justify the argument that every number must be interesting. I have always found this induction unsatisfactory.

Here is an attempt at a more precise argument. Consider a set of rules, represented as sentences of some logic. The interesting numbers are then the smallest numbers that are models of some set of sentences. In first-order logic each natural number can be distinguished from every other one, so the sentences true for any natural number will differ from those true for any other, and every number will be interesting.

Now suppose our rules are given in terms of a bounded model of computation, so that only finite sets of properties can be associated with each number, and so that every property can be checked with a bounded amount of some resource (for instance, time or space).

Is every number still interesting with resource-bounded properties?

Edit: to clarify, resource bounds is my focus here. With unbounded resources this devolves into a question about definability and large ordinals, as discussed by Aaron and Kaveh. The idea is that each interesting number should be definable by a sentence that can be checked given a bounded amount of resources. (It might also make sense to allow some finite set of sentences as separate building blocks instead of making them into single sentences via conjunction.)

  • 2
    $\begingroup$ IMHO, this is not a soft-question. You are essentially talking about what is called definable elements in logic/model theory. Every element in $N$ is definable, using a single sentence $x=\bar{n}$, where $\bar{n}$ is the term resulting applying $s$ (successor function) $n$-times to $0$. $\endgroup$ – Kaveh Oct 28 '10 at 17:57
  • 2
    $\begingroup$ I think the old joke gets formalized into a statement that essentially gives the opposite conclusion: namely, most numbers are Kolmogorov-random. (But "interesting" numbers "should" be highly compressible.) $\endgroup$ – Joshua Grochow Oct 28 '10 at 22:37
  • 12
    $\begingroup$ Theorem: All positive integers are boring. Proof by contradiction: Let $n$ be the smallest interesting positive integer. So what? $\endgroup$ – Jeffε Oct 29 '10 at 4:01
  • 1
    $\begingroup$ How about defining the interesting numbers as those which has short description, i.e. small Kolmogorov complexity? Then most numbers will be uninteresting (random). $\endgroup$ – Kaveh Oct 29 '10 at 22:01

This might be cheating, because I am reinterpreting your notion of "number" as "countable ordinal." However, there is an extensive theory about exactly what you are asking about in your question -- which ordinals can be defined, with which definition-strengths. I looked at Wikipedia, and the large countable ordinal page has a lot of information. In particular, the "smallest number that is interesting because the system can't even prove it's a number" corresponds to the unrecursable ordinals, if we require nothing other than computability as the resource bound.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.