I am reading Course in Mathematical Logic by S.M. Srivastava. The author defines terms and their rank of a first order language $L$ as follows:
The set of all terms of a language $L$ is the smallest set $\mathcal T$ of expressions of $L$ that contains all variables and constant symbols and is closed under the following
operation: whenever $t_1, \ldots,t_n \in \mathcal T$ , $f_j t_1\ldots t_n ∈ T$ , where $f_j$ is any $n$-ary function symbol of $L$. Equivalently, all the terms of a language can be inductively defined as follows: variables and constant symbols are terms of rank $0$; if $t_1,\ldots,t_n$ are terms of
rank $\le k$, and if $f_j$ is an $n$-ary function symbol, then $f_j t_1\ldots t_n$ is a term of rank at most $k+1$. Thus, the rank of a term $t$ is the smallest natural number $k$ such that $t$ is of rank $\le k$.
Here are my questions:
- In the inductive step of defining rank, the author says if $f_j$ is an $n$-ary function symbol, then $f_j t_1\ldots t_n$ is a term of rank at most $k+1$ and does not explicitly assign any number as its rank. Is this valid? For instance, if $c$ is a constant symbol and $f$ is a unary function symbol in some first order language $L$ then rank of the term $c$ is $0$ by definition. How does this definition allow me to determine the rank of the term $fc$ or even $ffc$?
- I do not see how the terms can be equivalently defined by the notion of rank when the definition itself appeals to the term "term" itself. Am I missing something here?
Best Answer
Srivastava is not defining the rank of a term by induction. Instead, he is defining the set of terms of rank $\leq k$ by induction on $k$. Then (implicitly) a term is a term of rank $\leq k$ for some natural number $k$. Finally, he defines the rank of a term $t$ to be the least natural number such that $t$ has rank $\leq k$.
Here is a slightly more precise way of expressing Srivastava's definition:
We define the set $S_k$ of terms of rank at most $k$ by induction on $k$. $S_0$ is the set of all variables and constant symbols. Given $S_k$, we define $$S_{k+1} = S_k\cup \{ft_1\dots t_n\mid f\text{ is an $n$-ary function symbol, and }t_1,\dots,t_n\in S_k\}.$$ The set of all terms is $\mathcal{T} = \bigcup_{k\in \mathbb{N}} S_k$. Given a term $t\in \mathcal{T}$, the rank of $t$ is the least natural number $k$ such that $t\in S_k$.
Note that I've made explicit the fact that $S_{k+1}$ contains $S_k$ (that is, that a term of rank at most $k$ also has rank at most $k+1$). Srivastava leaves this implicit in his definition.
For example, consider the term $fc$ (where $f$ is a $1$-ary function symbol and $c$ is a constant symbol). $c\in S_0$, so $fc\in S_1$. On the other hand, $fc\notin S_0$ (since it is not a variable or a constant symbol). So the rank of $fc$ is $1$. Similarly, the rank of $ffc$ is $2$ (but for this one, you need to think for a second about why $ffc\notin S_1$).