How do I prove that the function symbol $\circ$ is not a term by induction in the calculus?
I've tried to prove it by the definition of term in first-order language.
From the definition of term in first-order language, we can represent the rules as follows:
(T1) $\frac{\quad}{x}$;
(T2) $\frac{\quad}{c}$ if $c\in S$;
(T3) $\frac{t_1,\cdots,t_n}{ft_1\cdots t_n}$ if $f\in S$ and n-ary.
$\frac{\circ}{x}$ and $\frac{\circ}{c}$ are both false by induction hypothesis, but how do I show in (T3)?
An expression is a term if and only if it is the final expression in a tree (or sequence) of other expressions, each of which has also been shown be a term by virtue of a finite tree of applications of rules $T_1$, $T_2$, or $T_3$. (This is a recursive definition). Showing that something is not a term therefore means showing that such a tree cannot exist.
The easiest way to do this is by contradiction. Assume that such a tree exists. Sinc it must be finite, there must be a last such application. If $T_3$ is the final rule, then $$\circ=ft_{1}\ldots t_{n}$$ for some function symbol $f$ with arity $n$.
All you have to do now is show that these cannot be equal, as strings.
Note that this argument is essentially an induction argument. Which is to be expected - induction arguments are generally he best way to prove things about recursively defined structures.