I thought Gurkenglas’ solution was a lovely discrete math sledgehammer approach. There’s a lot of subtly different problems that Thomas could have meant and I think Gurkenglas’ approach would probably be enough to tackle most of them.
(Attempting to summarize his proof: Some English sentences, like the one this problem is asking you to dig around in, are countably infinite in length. If some English sentences are countably infinite in length, and any two of them have different infinite suffixes, then there’s no way the text of this sentence contains both of them.)
I think your summary is wrong, I’m afraid. The sentence could contain two different infinite suffixes—e.g., by interleaving them. (Well, maybe; it still isn’t clear to me what sort of descriptions Thomas is intending to allow.) The problem isn’t that having multiple infinite suffixes is a problem, it’s that (at least for certain rather non-standard notions of what a “sentence” is) there are uncountably many different sentences and if they all have to be described separately you’re dead.
If you allow one description to cover multiple sentences, though, you can cover all those uncountably many with something countably long. Suppose the words of the language are W1, W2, …, Wn and suppose a “sentence” is any string of finitely or countably many of them. (That’s not true for any actual natural language, of course, but this language does have uncountably many “sentences”.) Then you could say: “A sentence consists of the empty string, or: of one of W1,...,Wn followed either by the empty string or by: one of W1,...,Wn followed either by the empty string or by: …...”.
You could also, though this is a further step away from the sort of description I think Thomas wants to allow, do that in finite space. In fact, I already did, earlier in the paragraph above.
I think you’re right. I’m badly overlooking a subtlety because I’m narrowing “describe” down to “is a suffix of.” But you’re right that “describe” can be extended to include a lot of other relationships between parts of the big sentence and little sentences, and you’re also right that this argument doesn’t necessarily apply if you unconstrain “describe” that way. (I haven’t formalized exactly what you can constrain “describe” to mean—only that there are definitions that obviously make our sledgehammer argument break.)
I think “a sentence can be countably infinite” is implicit from the problem description because the problem implies that our “giant block of descriptions” sentence probably has countably infinite size. (it can’t exactly be uncountably infinite)
One of the problems was that Thomas spoke about a “natural language” that we all know what it looks like. And a natural language does not have infinite-length sentences.
Another is that Thomas’s question didn’t make it clear that each sentence covered had to be called out individually, as opposed to constructing some description that covers exactly the right sentences. Another is that even if we suppose our natural language augmented by allowing infinite sentences, it’s not clear that it should allow non-computable infinite sentences.
I thought Gurkenglas’ solution was a lovely discrete math sledgehammer approach. There’s a lot of subtly different problems that Thomas could have meant and I think Gurkenglas’ approach would probably be enough to tackle most of them.
(Attempting to summarize his proof: Some English sentences, like the one this problem is asking you to dig around in, are countably infinite in length. If some English sentences are countably infinite in length, and any two of them have different infinite suffixes, then there’s no way the text of this sentence contains both of them.)
I think your summary is wrong, I’m afraid. The sentence could contain two different infinite suffixes—e.g., by interleaving them. (Well, maybe; it still isn’t clear to me what sort of descriptions Thomas is intending to allow.) The problem isn’t that having multiple infinite suffixes is a problem, it’s that (at least for certain rather non-standard notions of what a “sentence” is) there are uncountably many different sentences and if they all have to be described separately you’re dead.
If you allow one description to cover multiple sentences, though, you can cover all those uncountably many with something countably long. Suppose the words of the language are W1, W2, …, Wn and suppose a “sentence” is any string of finitely or countably many of them. (That’s not true for any actual natural language, of course, but this language does have uncountably many “sentences”.) Then you could say: “A sentence consists of the empty string, or: of one of W1,...,Wn followed either by the empty string or by: one of W1,...,Wn followed either by the empty string or by: …...”.
You could also, though this is a further step away from the sort of description I think Thomas wants to allow, do that in finite space. In fact, I already did, earlier in the paragraph above.
I think you’re right. I’m badly overlooking a subtlety because I’m narrowing “describe” down to “is a suffix of.” But you’re right that “describe” can be extended to include a lot of other relationships between parts of the big sentence and little sentences, and you’re also right that this argument doesn’t necessarily apply if you unconstrain “describe” that way. (I haven’t formalized exactly what you can constrain “describe” to mean—only that there are definitions that obviously make our sledgehammer argument break.)
I think “a sentence can be countably infinite” is implicit from the problem description because the problem implies that our “giant block of descriptions” sentence probably has countably infinite size. (it can’t exactly be uncountably infinite)
One of the problems was that Thomas spoke about a “natural language” that we all know what it looks like. And a natural language does not have infinite-length sentences.
Another is that Thomas’s question didn’t make it clear that each sentence covered had to be called out individually, as opposed to constructing some description that covers exactly the right sentences. Another is that even if we suppose our natural language augmented by allowing infinite sentences, it’s not clear that it should allow non-computable infinite sentences.
The whole discussion, plus the posted problem, plus the (re)defining the problem itself—is more interesting than the problem alone.
As I see it, these are my assertions:
an infinite sentence is possible whenever the infinity is permitted
with such an infinite sentence you can uniquely describe all the finite sentences
even if the infinite sentence is selfdescribing
with such an infinite sentence you can uniquely describe countably infinite number of infinite sentences, too
there are non-countably many such infinite sentences
some of them can be described by some finite sentence
every finite or infinite sentence can be uniquely described by some infinite sentence and also by non-countably many of them
there may be some finite self describing sentences in English
By selfdescribing I mean the Quine type of a sentence. A self reproducing sentence.
Funny, but the whole set of infinite sentences can be described by just one finite sentence.