Why can we make a recursive definition?

Question

Background: ZFC in classical first-order logic.

To make a definition, we first need to proof something does exist. So, this question is actually about proving something exists based on a recursion.

I know that when you want to prove the existence of a certain function with the domain of ordinal numbers, you can use the transfinite recursion theorem. But our things are not always a function of this sort. For example, when we define the truth value function on the set of formulas in predicate logic, we usually define it recursively based on the number of the logical symbols in a formula(or complexity). But for a certain complexity of the formulae, there're many cases to deal with. I can't figure out how to prove such a definition does make sense, aka the function does exist.

Answer 1

The fact that a recursive definition produces a value for every natural number appearing as the index is a consequence of the induction axiom, which is part of Peano Arithmetic (PA). This is not quite enough to get the existence of the function as a single object. The latter follows from the axiom of separation of Zermelo-Fraenkel set theory (ZF). Thus, PA gives you the value at any $n$, and ZF guarantees the existence of the function as a single entity (no "C" is needed).

Answer 2

Thanks for providing a reference to the kind of definition you are having problems. Let me see if I can give a simpler example that may help you.

Let's look at the set of formulas in the $(\lnot, \land)$ fragment of propositional logic over a set $V_1, V_2, \ldots$ of propositional variables. It may be defined as the smallest set of strings of symbols that satisfies the following rules

• Any $V_i$ is a formula;
• If $\alpha$ is a formula then so is $(\lnot \alpha)$;
• If $\alpha$ and $\beta$ are formulas then so is $(\alpha \land \beta)$.

By somewhat tedious induction that shows along the way that for any left bracket in a formula there is a unique right bracket that matches it in the appropriate sense, you can show that for any formula $\alpha$, either $\alpha$ is $V_i$ for some $i$, or there is a unique formula $\beta$ such that $\alpha$ is $(\lnot \beta)$, or there are unique formulas $\beta$ and $\gamma$ such that $\alpha$ is $(\beta \land \gamma)$ (and these three possibilities are mutually exclusive). Let's call this the "structure theorem".

Now let's define a function $D$ that measures the depth of a formula. We want it to satisfy the following definition scheme:

• $D(V_i) = 1$
• $D((\lnot \alpha)) = 1 + D(\alpha)$
• $S((\lnot \alpha \land \lnot \beta)) = 1 + \max(D(\alpha), D(\beta))$

We have to prove that such a $D$ exists. To do this we show that there exists a unique chain of partial functions $D_1 \subseteq D_2 \subseteq D_3 \subseteq \ldots$ such that $D_i$ is defined for all formulas containing at most $i$ symbols and such that each $D_i$ satisfies the definition scheme above for all formulas in its domain. We can then take $D$ to be the union of the $D_i$. To prove the $D_i$ exist, we show by induction on $n$ that for every $n$, given a chain of functions $D_1 \subseteq D_2 \subseteq D_{n-1}$ satisfying our requirements on the $D_i$, there is a unique $D_n$ such that $D_{n-1} \subseteq D_n$ that also satisfies our requirements.

The proof goes like this. Assume given a chain $D_1 \subseteq D_2 \subseteq \ldots D_{n-1}$ satisfying our requirements. Define $D_n$ so that $D_n(\alpha) = D_{n-1}(\alpha)$ for any formula with less than $n$ symbols. If $\alpha$ has $n$ symbols, then by the structure theorem, exactly one of the following applies:

• $\alpha$ is $V_i$ for some $i$, so that $n = 1$, the given chain is empty and we may (and must) take $D_n(\alpha) = 1$;
• $\alpha$ is $(\lnot \beta)$ for some unique $\beta$, which clearly has less than $n$ symbols. We may (and must) take $D_n(\alpha) = 1 + D_{n-1}(\beta)$;
• $\alpha$ is $(\beta \land \gamma)$ for some unique $\beta$ and $\gamma$, which clearly both have less than $n$ symbols. We may (and must) take $D_n(\alpha) = 1 + \max(D_{n-1}(\beta), D_{n-1}(\gamma))$.

Thus we have found the unique extension of our chain of $n-1$ functions to a chain of $n$ functions.

The reference you give is being a little bit casual about the need for brackets in the formal representation of a formula to ensure that parsing is unique (that's what the structure theorem says). This is a standard slight abuse of notation. You also don't need to go through all the details of the course-of-values induction every time. Instead, you just recognise that you can uniquely define a function by giving its value on the atomic formulas (the $V_i$) and its value on a compound formula ($(\lnot \alpha)$ or $(\alpha \land \beta)$) as a function of its values on the immediate subformulas of the formula. This is often referred to as definition by recursion over the structure of the formula.