# Thread: countable & uncountable sets

1. ## countable & uncountable sets

Prove that the set of all grammatical sentences of English is denumerable.(Hint: Every grammatical sentence of English is a finite sequence of English words. First show that the set of all grammatical sentences is countable, and then show that it it infinite)???????

2. Originally Posted by mathsohard
Prove that the set of all grammatical sentences of English is denumerable.(Hint: Every grammatical sentence of English is a finite sequence of English words. First show that the set of all grammatical sentences is countable, and then show that it it infinite)???????
How much do you know? There is a common theorem which states that the set of all finite subsets of an infinite set is equipotent to the full set. Thus, $\displaystyle \mathcal{N}=\left\{E\subseteq\mathbb{N}:|S|<\infty \right\}$ has cardinality of $\displaystyle \aleph_0$. Then, if $\displaystyle \mathcal{G}$ is the set of all grammatical sentences we can clearly inject $\displaystyle \mathcal{G}\to\mathcal{N}$. Then, assuming that I understand a grammatical sentence the sentences $\displaystyle \text{hi},\text{hi hi},\text{hi hi hi},\cdots$ form an infinite subset of $\displaystyle \mathcal{G}$. It clearly follows that $\displaystyle |\mathcal{G}|=\aleph_0$.