Suppose we have a language $\mathfrak{L}=\{\bf{C},\bf{P},\bf{F},\#\}$ consisting of constant, predicate, function symbols and an arity symbol for functions, $\#$, with alphabet $\Sigma(\mathfrak{L})$. We also include in this language all the logical symbols: conjunction, negation etc. as well as punctuation symbols: parentheses, commas ets.
Let the class of terms of $\mathfrak{L}$, denoted $Terms_{\mathfrak{L}}$, be defined as the least subset $X$ of $\Sigma(\mathfrak{L})^*$ such that
1) $X$ contains the variables and constant symbols of the language $Var(\mathfrak{L})\cup \bf{C} \subset X$.
2) $f\frown ( \frown t_1\frown…\frown t_n\frown) \in X$ whenever $t_1, …, t_n \in X$.
Note: $^*$ is the kleene star, and $\frown$ denotes concatenation. I'm no expert, but I believe this is a standard way of defining a formal language.
Suppose we are in the universe of sets, so every element of the language (i.e. a sequence of symbols concatenated) is a set (here is one way to do this: Codification of a formal language in set theory.) I want to make a characteristic function for the class $Terms_{\mathfrak{L}}$, i.e. a function that returns 1 for every element of $\Sigma(\mathfrak{L})^*$that satisfies conditions 1) and 2) above, and returns 0 for all others. In other words, I want to construct the set of terms of this language.
Clearly, by condition 1) all constants and variable symbols are terms, so the difficulty here is in identifying all the terms of the form $f\frown ( \frown t_1\frown…\frown t_n\frown)$ for arbitrary $n \in N$
Naturally, the characteristic function on $Terms_{\mathfrak{L}}$ must be recursive. I have very little experience with recursion, so I'm not sure how to proceed. If I fix $n$ and take the string $f\frown ( \frown t_1\frown…\frown t_n\frown)$, then I know it is a term because it has parentheses and commas separating the terms $t_i$, and the first element of the string is a symbol from the set $\bf{f}$. But how can my characteristic function tell that a string looks like this for any arbitrary string?
Best Answer
The full, formal, exact definitions are very much not the point, it's a good exercise to do once in your life, partially. Other than that, to quote one of my professors when I was a freshman "convince yourself that it's true".
The idea is that terms, or formulas, or whatnot, which are defined recursively, have a sequence of previously-defined terms.
A string in a language is a term if and only if it is an atomic term, or there is a (finite) sequence such that every member of the sequence is either atomic or is obtained from terms appearing before it in the sequence, and the last thing in the sequence is the term itself.
So, $f(x+y)$ is given by $(x,y,x+y,f(x+y))$, for example. Note that these sequences need not be unique!
And we can write the whole thing into the language of set theory, it's just relatively long and ugly. Although it's getting slightly better once you've written some basic formulas such as "$f$ is a finite sequence" etc.