I read an answer to this here on MathSE, but the details of the argument are still hazy to me.
One of the users suggested that the set of WFFs is countable because:
S = $A \cup \{\neg,\lor,\land, (, )\}$ is a countable set of symbols ($A$ is a countably infinite set of propositional variables).
$S_f$, the set of finite strings of symbols from $S$, is countable.
As the set of all well-formed formulae is a subset of $S_f$, it is countable.
My question: Why is $S_f$ countable? Could you suggest a bijection between $S_f$ and $\mathbb{N}$? (for if $S_f$ is countable, it must be countably infinite)
Best Answer
Hint: As $S$ is countable, you can get a bijection $f:S\rightarrow P$ where $P$ is the set of all prime numbers. Now, if $a_1\dots a_n$ is a string of simbols in $S$, you can codify it with the number $f(a_1)\times...\times f(a_n)$.