Formula

Last updated Nov 1, 2022

The Set of $\mathcal{L}$-formulas is the smallest set $\mathcal{W}$ that satisfies the following properties

1. If $\phi$ is an atomic $\mathcal{L}$-formula, then $\phi \in \mathcal{W}$.
2. If $\phi \in \mathcal{W}$, then $\neg \phi \in \mathcal{W}$.
3. If $\phi, \psi \in \mathcal{W}$, then $(\phi \wedge \psi) \in \mathcal{W}$ and $(\phi \vee \psi) \in \mathcal{W}$.
4. If $\phi \in \mathcal{W}$ and $v$ is a Variable Symbol, then $\exists v \phi \in \mathcal{W}$ and $\forall v \phi \in \mathcal{W}$.

1. Similar to The Term Set is the Union of Term Sets of all Complexities, we have that The Formula Set is the Union of Formula Sets of all Complexities. The proof is almost identical.
2. Formulas are finite strings (because Terms are also finite). This means they only include finitely many Variable Symbols
3. We also use the abbreviation $\phi \rightarrow \psi$ for $\neg \phi \vee \psi$ and $\phi \leftrightarrow \psi$ for $(\phi \rightarrow \psi) \wedge (\psi \rightarrow \phi)$.