Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have to prove the replacement lemma by structural induction. We define the logical complexity of a formula as follows:

Let $\varphi$ be a formula.

If $\varphi \in \left\{t, f\right\} \cup IV$ (where $IV$ is the set of propositional atoms), then $complexity(\varphi) = 0$.

If $\varphi = \neg \varphi_1$, then $complexity(\varphi) = complexity(\varphi_1) + 1$

If $\varphi = \varphi_1 \star \varphi_2$ $(\star \in \left\{\wedge, \rightarrow, \vee, \leftrightarrow \right\})$, then $complexity(\varphi) = complexity(\varphi_1) + complexity(\varphi_2) + 1$.

Now i shall prove the classical replacement lemma (semantic version). I.e

If $\mathcal{I} \models \varphi_1 \leftrightarrow \varphi_2$ for some interpretation $\mathcal{I}$ then $\mathcal{I} \models \psi\left[\varphi_1\right] \leftrightarrow \psi\left[\varphi_2\right]$

There's a hint that I shall prove the theorem by induction on

$g(\psi, \varphi_1) = complexity(\psi) - complexity(\varphi_1)$.

My idea is the following:

Let $n = g(\psi, \varphi_1)$.

Induction Base (n = 0): in this case it holds that (assuming $\psi$ contains at least on occurrence of $\varphi_1$) $\psi = \varphi_1$.

Induction Base (n = 1): Same here with $\psi = \neg \varphi_1$

Induction Base (n = 2): Same here with $\psi = \varphi_1 \star p$ for some prop. atom $p$ and $\star \in \left\{\wedge, \rightarrow, \vee, \leftrightarrow \right\}$

The problem now is the hypothesis. Assume the theorem holds for som $n$. Now show that it holds for $n + 1$...

Is this the right approach? How can I infer from $n$ to $n + 1$. Or am I completely wrong with my approach.

Thank you!

share|cite|improve this question
It seems to me that the natural induction is on max of the complexities. – André Nicolas Mar 31 '12 at 16:26
Excuse me, what do you mean exactly? – morris Mar 31 '12 at 16:38
You are really doing an induction on the formation tree. If you are going to replace the natural tree induction by one on a numerical measure of complexity, that numerical measure must take into account the "most complex" of the formulas involved. – André Nicolas Mar 31 '12 at 16:58
Ok, so obviously $complexity(\psi) \geq complexity(\varphi_1)$. So I assign $n$ to the difference between the complexities. But how can I conclude that if the theorem holds for $n$, it must hold for $n+1$. Actually I don't really understand what the difference of the complexities is good for. But it's the way I shall do the proof. – morris Mar 31 '12 at 17:04
up vote 1 down vote accepted

Your induction hypothesis should be that $n>0$ and the result is true whenever $g(\psi,\phi_1)<n$. Now suppose that $g(\psi,\phi_1)=n$. They $\psi$ is either $\lnot\psi_1$ for some $\psi_1$, or $\psi_1\oplus\psi_2$ for some $\psi_1$ and $\psi_2$ and some $\oplus\in\{\land,\lor,\to,\leftrightarrow\}$.

If $\psi=\lnot\psi_1$, it’s not hard to see that $g(\psi_1,\phi_1)<n$, so if some $\mathcal{I} \models \varphi_1 \leftrightarrow \varphi_2$, then $\mathcal{I} \models \psi_1[\varphi_1] \leftrightarrow \psi_1[\varphi_2]$ by the induction hypothesis, and the desired result now presumably follows from your definition of $\models$.

The argument in case $\psi=\psi_1\oplus\psi_2$ is similar, since you will have $g(\psi_1,\phi_1),g(\psi_2,\phi_1)<n$.

share|cite|improve this answer
Thank you very much, so actually I don't need any more base cases than the trivial one with $\varpsi$ being the subformula itself, right? From other sources in the web I just saw proofs constructing the formula according to the inductive definition step-by-step. Why does one actually need this definition of logical complexity? Or is it just this task which entertains such an "odd" concept? – morris Mar 31 '12 at 19:41
@morris: That’s right: the trivial one is the only necessary base case. I wouldn’t have bothered with a numerical definition of complexity; I’d just have used structural induction directly on the construction of the formula $\psi$. I don’t understand why it’s done numerically in your setting. – Brian M. Scott Mar 31 '12 at 19:48
I didn't too, that was the problem. It's an exercise at my logic course and the operations with complexity and especially that $f(\cdot, \cdot$) kinda confused me. However thanks for your help! – morris Mar 31 '12 at 19:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.