Formulas are Finite

Last updated Nov 1, 2022

Let $\mathcal{L}$ be a Language and let $\mathcal{W}$ be the Set of $\mathcal{L}$-Formulas. Each $\phi \in \mathcal{W}$ is a Finite String.

This is a slick proof courtesy of Nick Hanson.

Consider the Set of finite Formulas, $\mathcal{W}’$. This Set exists by Axiom Schema of Specification (since we constructed a superset in The Formula Set is the Union of Formula Sets of all Complexities). Observe that $\mathcal{W}’$ is closed under the defining properties of the Formula Set $\mathcal{W}$ (since Terms are Finite). Since $\mathcal{W}$ is the smallest such set, $\mathcal{W} \subset \mathcal{W}’$. Thus each $\phi \in \mathcal{W}$ is finite.

1. See remark (2) in Formula.
2. Related to Terms are Finite