Terms are Finite

Last updated Nov 1, 2022

Let $\mathcal{L}$ be a Language and let $\mathcal{T}$ be the Set of $\mathcal{L}$-Terms. Each $t \in \mathcal{T}$ is a Finite String.

This is a slick proof courtesy of Nick Hanson.

Consider the Set of finite Terms, $\mathcal{T}’$. This Set exists by Axiom Schema of Specification. Observe that $\mathcal{T}’$ is closed under the properties satisfied by the Term Set $\mathcal{T}$. Since $\mathcal{T}$ is the smallest such set, $\mathcal{T} \subset \mathcal{T}’$. Thus each $t \in \mathcal{T}$ is finite.

1. See remark (2) in Term.