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

  • $\begingroup$ 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. $\endgroup$ – Giorgio Mossa Feb 19 '14 at 9:31
  • $\begingroup$ @GiorgioMossa It's a function symbol which is the element of symbols set. $\endgroup$ – novice Feb 19 '14 at 11:03
  • 1
    $\begingroup$ 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. $\endgroup$ – 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$.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.