# Section 2.3: Problem 2 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

Let
be an expression consisting of variables, constant symbols, and function symbols. Show that
is a term iff
and for every terminal segment
of
we have
.

*Suggestion*: Prove the stronger result that if for every terminal segment of , then is a concatenation of terms. (This algorithm is due to Jáskowski.)
If
is a term, then
and every terminal segment
of
is a concatenation of one or more terms (Lemma 23B), therefore,
(equals the number of terms in the concatenation).

We now prove the stronger result, as suggested. We also prove the uniqueness of the decomposition of such
into
terms. We prove it by induction on the length of
.

For
consisting of
symbol,
cannot be a function symbol, as otherwise
. Hence,
is either a variable or constant symbol. In both cases
is a term, and
.

Now, suppose that for all lengths less than
the statement is true, and we consider
of length
. Its terminal segment
of length
satisfies the condition that every terminal segment
of
is a terminal segment of
, hence,
. Therefore,
is a (unique) concatenation of
terms. If the first symbol of
is a variable or constant symbol, then
. The first variable or constant symbol of
is a term itself. And no term of length greater than 1 can start with a variable or constant (by definition). Moreover,
is uniquely decomposed into
terms, therefore,
is uniquely decomposed into
terms. If the first symbol of
is an
-place function symbol
, then, since
,
. Then,
together with the first
terms of the unique decomposition of
into
terms forms one new term, and the resulting number of terms is
, as instead of
terms we now have just
term. So, again, the number of terms in the decomposition is
. The composition is also unique, as, by definition, a term starting with
must be
, where
are terms, and due to the unique decomposition of
into terms,
are uniquely determined, and so is the decomposition of the remaining expression into
terms.