Here is the question:
Define the set WFF as follows--
a) Every element in set $A = \{s_1, s_2, ...\}$ is in WFF. $A$ is countably infinite.
b) If $a$ is in WFF, so is $(\neg a)$. If $n$ and $m$ are in WFF, so is $(n \lor m)$.
c) No other elements are in WFF.
Show that WFF is countable.
Attempt at a solution: I was thinking it might be possible to show by induction that $S_i$, the set of all expressions with $i$ symbols, is countable, and then show that the union of all such countable $S_i$'s is also countable (which I know how to do). However, I'm unsure of how to proceed for the first part -- would it even be necessary to show that the set of all expressions with $i$ symbols is countable, as per the parentheses in the rules, it isn't possible to have an expression with, say, $i = 3$ symbols, or am I confused?
Another thing I am having trouble with is that there doesn't seem to be any restriction from the criteria against infinitely long strings/logical sequences (that would make WFF, to my knowledge, not countable). I believe this is the right approach, but I am unable to justify that to myself.
This style of definition can be confusing if you see it for the first time in a source that does not bother to explain very carefully how it should be understood.
What part (c) means is that $WFF$ is defined to be the smallest possible set that satisfies the conditions in parts (a) and (b).
Before this is actually a definition we need to prove that there is such a unique smallest possible set:
Let's call a set that satisfies (a) and (b) good. Consider now the set $$ W = \{ x \mid x\text{ is a member of every good set}\} $$ It is now easy enough to prove that $W$ is good, and that $W$ is a subset of every good set. This latter property means that $W$ is smaller than every other good set, so it is actually the set $\mathit{WFF}$ being definied!
Since the set of all finite strings over $A\cup\{{\neg},{\vee},{(},{)}\}$ is good (this is easy to verify), we can conclude that it is a subset of $\mathit{WFF}$, and therefore $\mathit{WFF}$ contains only finite stings.
If you know some axiomatic set theory, you will notice that I've swept a problem under the rug, namely showing that $W$ exists as a set at all -- above I've defined it using unrestricted comprehension. But as long as there exists at least one good set (and I've just argued that the set of finite strings is such a good set), then we can see that $W$ is a subclass of this set, and is therefore a set itself.