Terms

Now that we have the basic building blocks of a language, we need to specify the syntax of the language. That is, we need to say how we can use the building blocks to form more complex expressions. Our definitions will be recursive, which will (a) insure that we could construct an infinite number of distinct expressions even if we began with finite building blocks, and (b) enable us to prove things about expressions in a language by using mathematical induction. More on this a little later in the course.

So here is the definition of a term (Leary's Definition 1.3.1, p. 11):

Definition: If $\mathcal{L}$ is a language, a term of $\mathcal{L}$ is a nonempty finite string $t$ of symbols from $\mathcal{L}$ such that either:

1. $t$ is a variable, or
2. $t$ is a constant symbol, or
3. $t$ is $ft_1t_2\ldots t_n$, where $f$ is an $n$-ary function symbol of $\mathcal{L}$ and each of the $t_i$ is a term of $\mathcal{L}$.

This is pretty straightforward. We have two base cases of terms, namely variables and constant symbols. And then we can recursively build more terms by using function symbols: an $n$-ary function symbol whose argument places are filled by $n$ terms (not necessarily distinct) will also be a term.

Notice that in the official language, we don't use parentheses and commas; we construct a term simply by stringing the appropriate number of terms after a function symbol. However, for perspicuousness, we will usually use parentheses and commas in the familiar way. Thus $f(t_1, t_2)$ will be regarded as just a longer version of the canonical form $ft_1t_2$. Similarly, $f_1(t_1, f_2(t_2, t_3))$ will be regarded as a longer version of the canonical $f_1t_1f_2t_2t_3$. The parentheses and commas make things easier to read, but they aren't necessary since the official version is also unambiguous.