Shared publicly  - 
 
The smallest natural number that cannot be described in sixteen words without use of self reference.
18
2
Ulrik Buchholtz's profile photoChao Chen's profile photoRefurio Anachro's profile photoPhilip Thrift's profile photo
48 comments
 
I will not be drawn into your trap of circular logic.
 
This sound's like a mathematician's version of the "your mama" joke.
 
versus "The smallest natural number that cannot be described in fifteen words without use of self-reference." ?
 
That is a very famous paradox. I learned it in my logic class but I have no idea how to solve it.
 
The largest natural number that can be described in sixteen words without the use of self reference. Plus one. ?
 
@Chao Chen (and others): The "without self reference" tosses an extra (albeit largely irrelevant, depending on what one takes "without use of self reference" to mean) wrinkle on this, but as for how one might resolve the classical paradox:

One could, for example, abandon the idea that for every string of words, one has either "YES, this (uniquely) describes the number n" or "NO, this does not (uniquely) describe a number". In a suitable logical framework, this frees one from the obligation to suppose there is a smallest natural number not described within [however many] words.

This corresponds to what we readily acknowledge if we view the same problem in the context of, say, computer programs: one could tersely write a program to enumerate all the programs of length less than [whatever], and see what outputs they produce. And if one could furthermore tell which programs did not produce outputs as well, then the enumerating program could conclude by producing an output distinct from all those it enumerated (even, if you like, specifically the smallest natural number not output by any of them); for suitably non-tiny [whatever] (non-tiny enough to exceed the size of the terse enumerator), this yields a potential paradox, averted only by the resolution that there is not, in fact, a program which always outputs, when given another program as input, precisely one of "YES, this program outputs the number n" (whenever appropriate) or "NO, this program does not output a number".
 
Berry's Paradox. I think I agree that "without self reference" doesn't add anything.
 
+Chao Chen wrote: "This is a very famous paradox I learned it in my logic class but I have no idea how to solve it."

I think you're talking about Berry's paradox, which is about

The smallest natural number that cannot be described in eleven words.

This leads to a paradox, of course, because we're describing this number in eleven words. There are various ways out of this paradox. One is to complain about the vagueness of this sentence. Another is to simply forbid self-reference: this sentence refers to all possible eleven-word sentences, including itself, and it's known that self-reference causes problems.

My variant:

The smallest natural number that cannot be described in sixteen words without use of self reference.

is supposed to not be paradox. I'm describing a number in sixteen words, but in a way that uses self-reference. So, it's no paradox that this sentence describes a number that can't be described in sixteen words without self-reference.

(If "self reference" is not how you want to describe the problem with Berry's paradox, you can change those words to something else, like "impredicativity" or whatever.)
 
Okay, Jim, so don't think about this either:

The smallest number that +Jim Sutton will never think about.
 
Ah, yeah, OK.

I like your last one; it sort of combines the Berry Paradox with Whitely's "Lucas cannot consistently assert this sentence".
 
+John Baez, so you are saying;

Don't believe what I say, except this.

I still smell a paradox.
 
I don't think I'm saying that...
 
If not that, then something very close. There is only one self denial, yet it seems to have infinite expressions. Yours is a denial of a denial, but they seem to be vertical, like a denial in 2d. Still undecidable.
 
I think there is probably a real-world language (German perhaps) with enough flexibility to represent all positive integers. E.g. one could imagine being able to say, "The number of generations you have to go back to get to my greatgreatgreatgreatgreatgreatgrandmother," for an arbitrary number of "great"s. Even in English, there might be a prefix that can be iterated, but I haven't managed to think of one. Maybe you'd be OK with extensions of "minus the log of the ratio of the length of a hemidemisemihemidemisemihemidemisemihemidemisemiquaver to that of a quaver".
 
Of course, if such things became a concern, we'd just switch to counting letters, or some such thing. (The identification of word boundaries, and thus of word counts, is largely orthographic anyway)
 
Language has a way of softening a paradox by weighing its parts and playing with the angle between the components of a denial.
 
You often hear the (often mocked) assertion that Eskimos have lots of words for snow, but my attitude toward such claims underwent a big shift when I discovered that the Inuit language Kalaallisut has a word for

"once again they tried to build a giant radio station, but it was apparently only on the drawing board.”

Namely:

nalunaarasuartaatilioqateeraliorfinnialikkersaatiginialikkersaatilillaranatagoorunarsuarooq.

The whole concept of "word" seems a bit silly in languages of this type - it's a concept imported from linguists who are used to very different languages - but if we go along with them and call this a word, then I wouldn't be surprised if Kalaallisut speakers can name arbitrarily high integers in a single word.

But anyway, I can easily make my example more pedantic to avoid objections of this sort - e.g. by specifying English (some version of English that has finitely many words) or counting letters instead of words. Then we can get into what I consider the more interesting aspect of the problem, namely putting bounds on the number:

http://johncarlosbaez.wordpress.com/2012/04/24/enormous-integers/#comment-15074
 
Interesting. Turkish is like Kalaallisut too. "Çekoslovakyalılaştıramadıklarımızdanmısınız?" means "Are you one of those whom we could not turn into a Czechoslovakian (i.e. a Czech)?" and it was the longest word in Turkish language until the country split into two in 1993.
 
I know that word, but it is more like a joke than a good serious word. Long words are not tolerated because of the mental economy. Same in music. Measures are mostly short, like 4/4. In physics, generic laws are short and made of short parts.
 
Oooh semantics..

. +John Baez How are you using the term 'self reference' in this context? Your phrase - it's not a proper sentence - is not self-referential at all. It's a definite description that refers to a number. To be self-referential a phrase has to refer to itself. e.g. - this sentence is true. By this definition then - your sentence is still without self-reference and still paradoxical. So perhaps you mean something else.

The definite description predicates a property (of a number) - of being the least member of a set of numbers describable by a possible set of sets of words of which we can further predicate the property of having sixteen members and don't refer to themselves.

So then, perhaps by self-reference you mean that the definite description is a member of this set of sets of words as described in the definite description. So is your definite description self-referential in this sense? If it is - then it is possessed of two properties (as described by the sentence - it needs to be 16 words long and not be self-referential (i.e. not be in the set of sets of words it describes)).

Your sentence happens to have this property of being 16 words long. Does it refer to itself? (in this new sense we are exploring) If it does refer to itself, then it is not in the set of sets of words it describes - so it isn't self-referential. Contradiction. If it doesn't refer to itself, then it IS in the set it describes. Contradiction again.

If this is right - then under the two most plausible definitions of self-referential I can think of - this sentence is still paradoxical.
 
+Daniel Haggard - as I said in my longish comment replying to +Chao Chen, my phrase is deliberately not self-referential, to avoid the self-reference, or impredicativity if you prefer, built into Berry's paradox. That's because I want my phrase to not lead to a paradox! If after reading that longish comment you think I'm mixed up, please let me know.
 
I think your formulation is wrong. Assuming your map from descriptions to integers is injective, the smallest number that can't be described is only exponentially large, by a trivial counting argument. To make it super-super-large, as you seem to be intending, don't you have to go for the smallest number such that neither it nor any larger number can be described in sixteen words? Or, more simply, the largest number that can be described in sixteen words?
 
Why do you think I was trying to make this number super-super-large? I wasn't. The puzzle over on my blog is to put either a lower or upper bound on it, and it sounds like you solved that.
 
I thought it because the link had "enormous integers" in it and you've been talking about things like very large cardinals. In that context, I didn't think "mere" exponential largeness would cut the mustard.
 
I see. No, I was just aiming for something structurally analogous to the Fefferman-Schütte ordinal, which I described right after the puzzle... here:

http://johncarlosbaez.wordpress.com/2012/04/24/enormous-integers/#comment-15075

For ordinals and natural numbers we know there's least one with any property, if there's any at all. But I like the idea of "the largest natural number that can be described in eleven words", though it leads to worries about self-referentiality. We can avoid this by discussing "the largest natural number that can be described in ten words", but then we can still
 
Actually, that was one of the things that fooled me. The Fefferman-Schütte ordinal is huge, so it was natural to think that a finite analogue would also be huge. But maybe your notion of "structurually analogous" (which I now don't understand at all) is more flexible than that.
 
The Fefferman-Schütte ordinal is actually pathetically small as countable ordinals go. :-)

By "structurally analogous", I mean that in both cases we're defining something to be the smallest thing whose only description of some sort is self-referential. And this thing is an element of a well-ordered set, so we say "smallest" to make sure this thing is unique, if it exists.
 
I'd like to point out, again, the possibility of using the language of programs to help shed light on these concepts, by identifying them with well understood phenomena in that domain. In particular, "The largest number which has a description of length N" amounts to a version of the infamous busy beaver function.
 
+Sridhar Ramesh - right, I agree that's a good way to go if we get an idea that's sensible and interesting enough to be worth making 100% precise!
 
Hmm ... I slightly take that back. What I want to say is more accurately described as follows. With the ordinals, it seems that they all have a certain complexity up to a certain point, then you take a massive great limit and you get a new ordinal that is more complicated than all the ones that have gone before. But the integers aren't like that. If I take the integer given by a tower of 2s of height ten billion, it has a lovely concise description (which I've just given), but there are lots of integers less than it that are far more difficult to describe.

All that makes me wonder what some of the more obscure ordinals that are less than the Fefferman-Schütte ordinal are like. They usually hide in the dot dot dots ...
 
I wouldn't say ordinals are strictly increasing in description complexity... After all, among the ordinals (and interwoven in their structure throughout) are those same natural numbers with all their same oscillations of complexity. omega * (the integer given by a tower of 2s of height ten billion) is easy to describe, but specifying it as a limit of other ordinals will likely involve some of the other ordinals being rather more difficult to uniquely describe. Or, at any rate, specifying it as a limit of other ordinals amounts to not very different a problem than specifying a tower of 2s of height ten billion as a limit of other naturals.
 
+John Baez It's quite common that I'm mixed up if anyone is :)

I don't think you're mixed up. It's just that I think it possibly still leads to a paradox that you might not have noticed. I'll try to say it clearer.

To be self referential - the definite description has to satisfy the property it predicates of sets of words. Let's call it property X.

There is a property (X) of sets of words described by your definite description. Something satisfies property X if it is 16 words long and does not satisfy property X (as per the definition of self-reference).

So does your definite description satisfy this property or not? To say the sentence does satisfy it - to claim that it is self-referential (as you claim) - is to say it satisfies both halves of the conjunct. That is - it is to say that it is 16 words long, and does not satisfy X. But this is a contradiction. Conversely if it does not satisfy property X, then it does...
 
+Timothy Gowers - I also wonder what some of the more obscure integers are like. A while back I asked people to estimate the smallest natural number nobody had written down or thought of yet. I came up with an upper bound by looking up the number of people who have ever lived and guessing a conservative upper bound on how many numbers they could have thought of. I believe +Douglas Summers-Stay found some natural numbers that weren't googlable (until he typed them in). Or maybe they just weren't in Sloane's list of integer sequences.

By the way, if you could list all integer sequences, Sloane's list would not be such a challenging project. :-)
 
+Timothy Gowers - I'm getting quite curious about what they call 'systems of notation' for countable ordinals - which means more or less what it sounds like, but was made into a precise notion by Church and Kleene. I'm curious about them, but I know very little about the formal theory of them. There's a well-known system of notation that can describe all the ordinals up to ε_0. It's called Cantor normal form:

http://en.wikipedia.org/wiki/Ordinal_arithmetic#Cantor_normal_form

(I apologize if you know all this stuff - someone out there won't.) Indeed the Wikipedia article says Cantor normal form describes all ordinals... but, heh-heh, this notation involves ordinals, and when we get to ε_0 the Cantor normal form for ε_0 needs to mention ε_0! But before that point it's unproblematic.

However, I can imagine other systems of notation - not necessarily in the technical sense, which I don't understand - which are 'patchy', in that they can describe some ordinal but not other ordinals less than that. Those would certainly count as 'obscure' ordinals in your sense.

I don't know if the Veblen functions only give a 'patchy' system of notation, or can be used to give a notation that handles all ordinals below the Fefferman-Schütte ordinal.
 
+Sridhar Ramesh I agree that there isn't some monotone "complexity" associated with ordinals. But it does seem to be the case that when people define an ordinal to be the smallest that can't be described in a certain way, all ordinals above that ordinal can't be described in that way either. That's of course largely to do with the types of "certain way" that interest us when we talk about ordinals.

I'd be very interested in a counterexample to this: some natural notion of simplicity of ordinals such that the first complicated ordinal is not the limit of all simple ordinals.
 
Consistently separating words by spaces became a general custom about the tenth century A.D., and lasted until about 1957, when FORTRAN abandoned the practice.
-- (credited to a Sun reference manual)
 
Trick question. All descriptions (in isolation) are a form of self reference.
 
Is that really the same concept? Hmm...
 
The smallest natural number that can be described in standard English using fewer than 200 ASCII symbols.
 
I wrote: "I don't know if the Veblen functions only give a 'patchy' system of notation, or can be used to give a notation that handles all ordinals below the Fefferman-Schütte ordinal."

They can be used to give a notation that describes all ordinals below the Fefferman-Schütte ordinal, and in terms of this notation the usual operations of ordinal arithmetic become computable functions. A good account of this is here:

Jean H. Gallier, What's so special about Kruskal's theorem and the ordinal Gamma_0, Annals of Pure and Applied Logic 53 (1991), 199-260. Chapter 7: A glimpse at Veblen hierarchies.
http://repository.upenn.edu/cgi/viewcontent.cgi?article=1248&context=cis_reports
 
Sorry, I was a bit inaccurate. The precise concept that is key in Kritchman-Raz is "the smallest upper bound M such that one can prove (in, say, Peano arithmetic) that there is a number less than M which cannot be described as the output of any Turing machine of length at most L". One trivially has that M is at most 2^{L+1} (this is the "trivial counting argument" Tim alludes to above). On the other hand, if Peano arithmetic can prove its own consistency, one can show using Chaitin's theorem that any upper bound M implies an upper bound of M-1 (as long as L is large enough that Chaitin's theorem applies), which leads to absurdity upon iteration (the surprise examination paradox).

Chaitin's theorem, in turn, relies on a similar concept, namely "The shortest proof of an assertion that a number n has Kolmogorov complexity at least L". For L large enough, such a proof is paradoxical for the same reason the Berry paradox is, giving Chaitin's theorem that one cannot prove that the Kolmogorov complexity of any given number is larger than L, if L is large enough.
 
First of all, it is Feferman-Schütte (after Solomon Feferman).

Next, there are larger ordinal notation systems "from below", notably Schütte's Brackets (or Klammersymbole) which go up to the so-called large Veblen ordinal. These are impredicative in the technical sense, but only barely so, and hence they (and the systems whose strength they measure) are sometimes called metapredicative (but we don't have a technical definition of "metapredicative" yet!).

Ordinal notation systems using collapsing, e.g., for the Howard ordinal, are on the face of it "gappy", since they employ symbols that can be thought of as uncountable ordinals. After the fact, though, we can just think of Ω in the notation system for the Howard ordinal as denoting the Howard ordinal itself (essentially taking the Mostowski collapse of the image of the notations in the ordinals). Then the system is ungappy, but doesn't embed nicely in larger systems using larger cardinals (or their recursive analogs).
 
Thanks, +Ulrik Buchholtz - I'm trying to learn this stuff, going rather slowly because it's just a hobby so far, though it would be fun to think of a new idea someday... I don't even understand the technical definition of 'impredicative' yet! There's not a This Week's Finds in Infinity, is there?
 
I'm going to try to understand Schütte's Klammersymbole. Are they discussed in his book or only in his "Kennzeichnung von Ordinalzahlen durch rekursiv definierte Funktionen"? This stuff is hard enough already without the language barrier!
 
+John Baez , I'm afraid there's no This Week's Finds in Infinity yet; perhaps someone should create it!

Technically (following the analysis of Feferman and Schütte), a predicative ordinal is the ordertype of a relation that can be defined and proved to be wellfounded using only previously secured sets (say, in the ramified hierarchy). Feferman has an article discussing the various possible meanings of "predicative", and why the above definition is reasonable (http://math.stanford.edu/~feferman/papers/predicativity.pdf).

Schütte's Klammersymbole are a way of extending the Veblen functions of finite arity to infinite arity. I think Veblen already discussed the idea in his work, but Schütte worked out a way to make a recursive notation system from it. I don't remember if it's discussed in his book (but I guess it is). A shorter treatment is in Crossley and Kister's Natural Well Orderings (http://dx.doi.org/10.1007/BF02017491), which also treats of many other systems and the history of their discovery. If that's too short, try this article by Schütte's student, Hilbert Levitz: http://dx.doi.org/10.5169/seals-37163
 
Great, thanks! I'll read those.
 
+NotReal Naame - The use of English, is, of course, just a trick for starting a conversation. If we go for a formalization using Turing machines or something like that, as +Sridhar Ramesh and you suggest, it seems maybe my idea will morph into the Kritchman-Raz proof of Goedel's 2nd incompleteness theorem, as +Terence Tao pointed out. A summary of that proof is here, by the way:

http://johncarlosbaez.wordpress.com/2011/10/06/chaitins-theorem-and-the-surprise-examination-paradox/

In my dreams, I'd like to formalize the notion of 'avoiding self-reference' well enough to get that to play a real role in the formalization of what I wrote. Logicians try to do this using the idea of 'predicative arithmetic'. But I don't understand that well enough to proceed, so I just thought I'd throw the idea out for discussion. I got the idea from this sentence:

"Specifically, we expect that any proof within predicative mathematics of the existence of TR(2,4) will have incomprehensibly many symbols; e.g., more than A(5,5) symbols."

at the end of here:

http://www.math.osu.edu/~friedman.8/pdf/EnormousInt112201.pdf
Add a comment...