Doubt on recursive definition of a term in a first order language, $\mathscr L$

294 Views Asked by At

In his definition of a first order language $\mathscr L$ in "A Friendly Introduction to Mathematical Logic by Leary", the author says a term in $\mathscr L$ is a non-empty, $\underline {\text{finite}}$ string $t $ of symbols from $\mathscr L$ such that :

$1.) \;$ $t$ is a variable, or

$2.) \;$ $t$ is a constant symbol, or

$3.) \;$ $t$ is $f(t_1, t_2, ..., t_n)$ where $f$ is an $n$-ary function symbol of $\mathscr L$ and each $t_i$ is a term of $\mathscr L$.

Now this recursive definition is a little unsettling to me. Suppose, $ t$ is $f(c_1, c_2, l )$ where $c_1$ and $c_2$ are suitable constants of $\mathscr L$ and $l = f(c_1, c_2, l ) $. This conforms to the definition and hence $t$ is a term. But $t$ surely cannot be a finite string can it?

Obviously the author's definition was foolproof (for this is a book on logic). So I must have my thought process jumbled up. Can someone tell me where? Where am I going wrong?

1

There are 1 best solutions below

3
On BEST ANSWER

Git Gud & Brian have said everything I'm going to say, so read only if you still have some doubts.

The expression $f(c_1,c_2,l)$ is a term iff $f$ is a 3-ary function symbol (let's suppose it is) and $c_1$, $c_2$, and $l$ are terms of the language. Since $l$ is a defined symbol, for $t$ to be a term it is necessary that the definiens (namely $f(c_1,c_2,l)$) be a term. You can see the problem: the definition of $l$ is circular (and not recursive), so it fails to define $l$ as a term, so $t$, the 'finite string' fails to be a term.