5
$\begingroup$

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:

  1. 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$?
  2. 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?
$\endgroup$

1 Answer 1

7
$\begingroup$

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$).

$\endgroup$
7
  • $\begingroup$ Is the concept of rank, as defined here, related in some way to many-sorted alphabets? $\endgroup$
    – Jason
    Commented Feb 5, 2022 at 20:13
  • $\begingroup$ @Jason What is a many-sorted alphabet? $\endgroup$ Commented Feb 5, 2022 at 20:14
  • $\begingroup$ I should have said many sorted signatures sorry. It is a way of "sorting" which symbols can be applied to which symbols, by a set of sorts and a function mapping each symbol to a sort. $\endgroup$
    – Jason
    Commented Feb 5, 2022 at 20:18
  • 1
    $\begingroup$ @Jason Well, you must know that given a many-sorted signature, you can construct the set of terms in that signature. And the same definition of rank can be applied to these terms. I'm not sure what else there is to say. $\endgroup$ Commented Feb 5, 2022 at 20:19
  • $\begingroup$ This makes so much sense! I'll add this note to the margin. $\endgroup$
    – ashK
    Commented Feb 6, 2022 at 1:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .