# Cardinality of the set of all well formed formula in propositional logic?

Here's the simple grammar for propositional logic I'm using:

• For all $n \in \mathbb{N}$, $P_n$ is a WFF (Well formed formula).
• If $\phi$ and $\psi$ are WFF's then $(\phi \rightarrow \psi)$ is a WFF.
• If $\phi$ is a WFF then $\neg \phi$ is a WFF.
• Nothing else is a WFF.

My question is this: What is the cardinality of the set$\{\phi: \phi \text{ is a WFF} \}$? My intuition is that it is $\aleph_0$, but I'm having a hard time seeing why.

-
Well, write it as a countable union of countable sets... – Zhen Lin Dec 11 '13 at 3:15
I agree with @Zhen. Let $\Phi_0 = \{P_n : n \in \mathbb{N}\}$ and define $\Phi_{i+1} = \Phi_{i} \cup \{\phi \rightarrow \psi : \phi,\psi \in \Phi_i\} \cup \{\neg \phi : \phi \in \Phi_i\}.$ Check that the union of $\Phi_i$ really equals the set of all WFF, and then use basic principles of cardinal arithmetic to deduce that $|\bigcup_{i \in \mathbb{N}} \Phi_i| = \aleph_0$. – goblin Dec 11 '13 at 3:27

HINT: Consider your alphabet $\{P_n\mid n\in\Bbb N\}\cup\{\rightarrow,\lnot\}$. That is a countable set. Every WFF is a finite string over this alphabet. What is the cardinality of all finite strings over a countable alphabet?