So my wife (who was a math major) and I (who took a lot of math classes in college) had a conversation about this this morning. Unfortunately, I don't know enough linguistics to present a totally non-hand-wavy proof that the sentences in the English language are countably infinite, but here's what we came up with: First off, I'm defining a sentence in English as some combination of English words fulfilling some set of syntax rules. Whether the rules prohibit infinitely long sentences or not is a question for linguists, and I am not one. However, if infinite sentences are allowed there are uncountably infinite possible sentences and if they are not it is countable. Let's start with the easy case, that if infinite sentences are allowed, there are unaccountably many sentences. I'll prove this by taking just the infinite sentences. My understanding is that these must contain infinite recursion or use conjunctions (if a linguist corrects me on this, I withdraw this portion of the proof). Specifically, I would like to state that they must contain non-repeating recursion/conjunctions. ie "This is the dog that bit the cat that bit the dog that bit the cat..." does not count. As an example of such a sentence might be to assign a noun to each digit (1 - dog, 2 - cat, 3 - man 4 - woman, etc). Then pick a verb, and construct a sentence using the digits of pi to progressively embed those nouns. "This is the man that bit the dog that bit the woman that bit the dog..." This could of course be varied by using other irrational numbers than pi, different lists of nouns, changing the verbs instead of the nouns, incorporating adjectives, or whatever. Since there are uncountably infinite irrational numbers, there are uncountably infinite of these such sentences. The diagonalization argument could be easily applied by tracing through each of the previous sentences and constructing a new one changing each embedding word. Now that we've proved that there are uncountably infinite sentences of a certain form, adding in the remaining sentences means that the total will still be uncountably infinite. Now, let's disallow infinite sentences, but allow sentences of a finitely large arbitrary length. First off, English sentences can clearly be of finitely large arbitrary length. Mathieu has demonstrated a proof of this with his "X+7" argument. However, all sentences constructed in this fashion are still finite. There is just no upper limit. This is similar to the list of whole numbers, as they are all finite, but there is no upper limit. In fact it is a sufficient proof that there are infinitely many sentences, since if you claim to construct a finite list of all the sentences, I'll simply add a conjuction or recursive clause to your longest sentence and create a new, longer sentence not on your list. Now is it countably infinite? First, note that words are irrelevant, since there are finitely many of them. What matters is whether the number of possible sentence structures, "[article] [noun] [verb] [article] [adjective] [noun]" for example, is countably infinite. I don't know enough linguistics to offer a proof here, but if there are a finite number of possible constructions without using embedding or conjunctions (actually, an infinite list of adjectives would qualify as an option as well...) then those all reduce out as well. So what we're left with is: Number of possible sentences = (# of words (not exactly, since not all words qualify at all parts, but this term is finite, so it doesn't matter)) x (# of possible sentences without embedding, conjunction or adjectives) x (# of possible adjective list lengths) x (# of times recursing) x (# of conjunctions) Or something along those lines. The first two terms are finite, and the last three are infinite. Countably infinite sets and finite sets can all be combined a finite number of times to make countably infinite sets, so the finite terms can be discarded, and the last three are what we're concerned with. All three of those are trivially countably infinite. Therefore if not-repeating infinite sentences are not allowed, there are a countably infinite number of possible sentences in the English language. Sound reasonable? -Daniel