I'm attempting a proof as part of a problem sheet, but I'm new to proofs and have not had the opportunity to have any of my proofs looked at. I wonder if any one you who are competent in proofs would have a look and see if I've made any jumps in reasoning and in general whether the proof succeeds or not?
The proof:
Every formula of $\ell$ contains as many terms as predicate symbols.
Proof.
A term of $\ell$ is either a variable, a constant or a function of the form $f(t_1,...,t_n)$, where f is an n-place function symbol and $t_1,...,t_n$ are terms of $\ell$. But since function symbols may be viewed as abbreviations of definite descriptions in the Russellian mode, we may permissibly ignore function symbols in our proof. What's more, we will take for granted that $\{\rightarrow,\neg,\forall\}$ is expressively adequate for $\ell$.
Now, 'every formula of $\ell$ contains as many terms as predicate symbols' is logically equivalent to 'every formula of $\ell$ has an equal or greater number of terms than predicate letters', which we will prove by induction on the complexity of formulae. So, assume for induction on the complexity that, given some arbitrary formula $\phi$, all well-formed formulae shorter (i.e. of complexity less than) $\phi$ have an equal or greater number of terms than predicate symbols. We will show that $\phi$ too has that property by considering the different possible forms $\phi$ may take.
There are two main cases to consider: $\phi$ is either at atomic or it is complex. If $\phi$ is atomic, then there are two forms it may take: either it is an expression of the form $s=t$, where $s$ and $t$ are variables or constants, or it is an expression of the form $Zt_1,...,t_n$, where $Z$ is an n-place predicate symbol and $t_1$ through $t_n$ are variables or constants. If $\phi$ is of the form $t=t$, then $\phi$ has more terms than predicates because it has precisely two terms ($'s'$ and $'t'$) and precisely one predicate ($'='$). If $\phi$ is of the form $Zt_1,...,t_n$, then there are two possibilities: $Z$ takes just one term – we have $Zt$ – or $Z$ takes $n$ terms, where $n$ is any integer greater than 1. In the first case the number of predicate letters is precisely equal to the number of terms (one of each); in the second second case, there is atleast one more term than predicate letter. Either way, then, if $\phi$ is of the form $Zt_1,...,t_n$, then it has equal or greater number of terms than predicate letters. Since $s=t$ and $Zt_1,...,t_n$ exhaust the possibilities when $\phi$ is atomic, we have it that $\phi$ has an equal or greater number of terms than predicate letters if $\phi$ is atomic. We can now consider the case where $\phi$ is complex.
If $\phi$ is complex, then there are three forms it may take: $\phi$ is $\neg\psi$ for some $\psi$, $\phi$ is $(\psi \rightarrow \chi)$ for some $\psi$ and $\chi$, or $\phi$ is $\forall v\psi$ for some $v$ and $\psi$. We may treat the first two cases together. So, suppose $\phi$ is $\neg\psi$ or $\forall v\psi$. Our inductive hypothesis allows us the assumption that $\psi$ is has an equal or greater number of terms than predicate symbols. But since appending $'\neg'$ or $'\forall v'$ to a formula changes neither the number of terms nor the number of predicate letters, it follows that $\phi$ too has an equal or greater number of terms than predicate symbols.
Finally, suppose $\phi$ is $(\psi \rightarrow \chi)$ for some $\psi$ and $\chi$. Since both $\psi$ and $\chi$ are shorter than $\phi$, our they possess our inductive property. Now, say that $\psi$ has $i$ terms and $j$ predicate symbols, while $\chi$ has $i'$ terms and $j'$ predicate symbols. Since $\psi$ and $\chi$ possess the inductive property, we have it that: $$i \ge i' and j \ge j'$$ Now, since $\phi$ has $i + i$ terms and $j + j$ predicate symbols, if we can show that $$i + i' \ge j + j'$$ we will have shown that $/phi$ too has a equal or greater number of terms than predicate symbols. We can establish that with the following reasoning: We can establish that with the following reasoning:
$$i + i' \ge j + i'$$ and $$j + i' \ge j + j'$$ hence: $$i + i'\ge j + j'$$ and so $$i + i' \ge j + j'$$
and so $\phi$ has an equal or greater number of terms than predicate symbols. Since there are no other forms $\phi$ may take, it follows on our inductive hypothesis that $\phi$ too has an equal or greater number of terms than predicate letters.
Thus, whether $\phi$ is atomic or complex, it will have the inductive property when every shorter formula has that property. It follows by induction on the complexity of formulae that Every formula of $\ell$ contains as many terms as predicate symbols, as claimed. $\square$
I am particularly thinking about this line:
"But since appending $'\neg'$ or $'\forall v'$ to a formula changes neither the number of terms nor the number of predicate letters, it follows that $\phi$ too has an equal or greater number of terms than predicate symbols."
Should I be making more of an effort here? Or is what I've said sufficient?
