Print

Print


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