# How do I prove that the function symbol $\circ$ is not a term by induction in the calculus?

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)?

• What do you mean by $\circ$, is a defined term or is part of the alphabeth (which I suppose is $S$)? In the second case from you rules it should follow that $\circ$ is a term since for every $f \in S$ it follows that $f$ is term (T2), since in this rule there's no restriction on the applicability. Hope this helps. – Giorgio Mossa Feb 19 '14 at 9:31
• @GiorgioMossa It's a function symbol which is the element of symbols set. – novice Feb 19 '14 at 11:03
• then from the rule T2, since as you say $\circ \in S$, we have that $\circ$ is term. Otherwise you have to restrict rule T2 so that it can be applied just to term with $0$-ariety. – Giorgio Mossa Feb 19 '14 at 11:17

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