Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

> Since the set of all English sentences is countable

Is it? Where can I read a proof? I have a feeling it’s uncountable set but would be happy to see a proof one way or another.



An spoken English sentence is a finite string of phonemes. The set of allowable phonemes is finite. Given a finite set X, the set of all finite strings of elements of X is countable.

(The latter statement holds because for any given n, the set X_n of all strings of length n is finite. So you can count the members of X_0, then count the members of X_1, and so on, and by continuing on in that way you'll eventually count out all members of X. You never run out of numbers to assign to the next set because at each point the set of numbers you've already assigned is finite (it's smaller in size than X_0, ..., X_n combined, for some n).

In fact, even if you allow countably infinitely many phonemes to be used, the X_n sets will still be countable, if not finite, and in that case their union is still countable: to see that, you can take enumerations of each set put them together as columns an a matrix. Even though the matrix is infinite in both dimensions, it has finite diagonals, so you can enumerate its cells by going a diagonal at a time, like this (the numbers reflect the cells' order in the numeration):

    1  3  6  10 15
    2  5  9  14
    4  8  13
    7  12
    11
However if you allow sentences to be countably infinitely long, then even when you only have finitely many phonemes, the set of all sentences will be uncountable, because in that case each countably infinitely long sentence can be mapped to a real number represented as an expansion in some base, and you can apply Cantor's diagonal argument. The "just count out each X_n separately" argument doesn't work in this case because it only applies to the sentences of finite length.)


The set of text files is clearly countable because it's made of binary. Do you think you can make an English sentence that can't be written into a text file?


If humanity lives forever, it will keep on inventing new words and therefore new sentences. So the question of whether or not language is finite is really the same question as whether or not the universe is.


> If humanity lives forever, it will keep on inventing new words and therefore new sentences.

That just increases the fraction of text files that count as "English". Which doesn't affect the argument.

> the question of whether or not language is finite

does not need to be answered. If English has a thousand words and never gains another one, the list of English sentences is countably infinite. If English gains 10% more words every year forever, the list of English sentences is still countably infinite.


Finite is not the same thing as countable. https://mathinsight.org/definition/countably_infinite


eventually that will be something that is not engish in any way we, but formally it will not be english straight away


See The Library of Babel, by Jorge Luis Borges:

https://archive.org/details/TheLibraryOfBabel


You are right because you can recursively add clauses. 'Buffalo buffalo...' or 'This was my dad's dad's dad's...' If you think you have a full set you can always add one more


You seem to misunderstand the concept of countable infinity


Haha oh you're right, was misframing in my head the word countable as meaning finite.

I even provide the definition of countable infinity in my counterargument without realising it, though maybe that too is a misunderstanding.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: