Given two expressions $\phi$ and $\psi$, call $\psi$ an initial segment of $\phi$ if and only if $\phi$ can be obtained by concatenating some (possibly no) symbols to the right-hand end of $\psi$. For example, $\neg$ is an initial segment of $\neg \neg A$.
Now I am a good way through a proof that or any sentence $\phi$ of first-order logic, the only sentence which is an initial segment of $\phi$ is $\phi$ itself. I am proving it by strong induction on the length of sentences, by considering the different possible forms $\phi$ may take, and I have managed all the cases except when $\phi$ is $\forall v \psi$ for some $v$ and $\psi$.
Here's where I've got to on this last part.
Let $\chi$ be an initial segment of $\phi$. Then $\chi$ must be of the form $\forall v' \psi'$ for some $v'$ and some $\psi'$. Now we want to show that $\chi$ must be $\phi$ by showing that $v'$ and $\psi'$ must be $v$ and $\psi$, respectively. But the issue is a bit complicated because $\psi$ and $\psi'$ could be formulas with open variables, and in that case they won't possess the inductive property (which is precisely the property I am trying to prove $\phi$ has). What's more, I don't know what to say about $v$. I haven't proved have an analogous theorem for terms, but my feeling is that we don't need to (when I watched my tutor prove this he didn't make use of any such theorem). How might I navigate this tricky business at the end of my proof?
Thank you for any help!
I’m assuming your syntax requires parentheses (eg, we need $(P \land Q)$ instead of $P \land Q$). If you don’t require parentheses but instead have an order of operations, this isn’t true, as the example $P \land Q$ demonstrates (where $P$ is an initial segment).
The trick here is quite simple. All you have to do is drop the requirement that the proposition be a sentence. If you do this, then you are able to do this final inductive step, since we know that $\psi’$ would be an initial segment of $\psi$ and thus $\psi$ itself.