91Ó°ÊÓ

Suppose that \(\mathcal{L}\) is \(\\{0, f, g\\}\), where 0 is a constant symbol, \(f\) is a binary function symbol, and \(g\) is a 4-ary function symbol. Use induction on complexity to show that every \(\mathcal{L}\) -term has an odd number of symbols.

If \(s\) and \(t\) are strings, we say that \(s\) is an initial segment of \(t\) if there is a nonempty string \(u\) such that \(t:=s u\), where \(s u\) is the string \(s\) followed by the string \(u\). For example, \(K U M Q\) is an initial segment of \(K U M Q U A T\) and \(+24\) is an initial segment of \(+24 u-v\). Prove, by induction on the complexity of \(s\), that if \(s\) and \(t\) are terms, then \(s\) is not an initial segment of \(t\). [Suggestion: The base case, when \(s\) is either a variable or a constant symbol, should be easy. Then suppose that \(s\) is an initial segment of \(t\) and \(s: \equiv f t_{1} t_{2} \ldots t_{n}\), where you know that each \(t_{i}\) is not an initial segment of any other term. Look for a contradiction.]