How to construct a counterexample?

Question

The question: "Let $\mathcal{L}$ be a language, let $\psi$ be a formula and let $\phi$ be a subformula of $\psi$ occurring at position p. Let $\bar\phi$ be another formula and let $\bar\psi$ be the string obtained from $\psi$ by replacing $\phi$ at position p with $\bar\phi$. Show that for $\Sigma \subseteq Fml(\mathcal{L}) $ with $\Sigma \vdash \phi \leftrightarrow \bar\phi$ it is in general not true that $\Sigma \vdash \psi\leftrightarrow \bar\psi$."

I've been thinking about this for a very long time and I really don't know where to start. What does it mean for "$\Sigma \vdash \phi \leftrightarrow \bar\phi$"? Please give me some examples and help me make sense of the notation.

Answer 1

See Stephen Cole Kleene, Mathematical logic (1967 - Dover ed 2002), page 122 [I've changed a little bit the notation] :

Replacement theorem. Let $\varphi_A$ be a formula containing a formula $A$ as a specified (consecutive) part [i.e. sub-formula], and let $\varphi_B$ come from $\varphi_A$ by replacing that part by a formula $B$. Let $x_1, \ldots, x_n$ be the free variables of $A$ or $B$ which belong to quantifiers of $\varphi_A$ having the specified part within their scopes (i.e. $x_1, \ldots, x_n$, are the variables having free occurrences in $A$ or $B$ which become bound occurrences in $\varphi_A$ or $\varphi_B$).

Let $\Gamma$ be a list of (zero or more) formulas not containing any of $x_1, \ldots, x_n$ free. Then:

If $\Gamma \vdash A \leftrightarrow B$, then $\Gamma \vdash \varphi_A \leftrightarrow \varphi_B$.

In order to simplify a little bit, we consider only $x$ free in $A,B$ which becomes bound in $\varphi_A, \varphi_B$ : the proviso is that $x$ is not free in $\Gamma$.

Thus, to manufacture the required counterexample, we have to violate the proviso, i.e. to conside a situation with $x$ free in $\Gamma$ .

---

Let $\Sigma := \{ x=1 \}$ , let $\phi : x=1$ and let $\psi := \forall x \phi$ ; $\phi$ is the needed sub-formula of $\psi$.

Finally, consider : $\overline \phi := x=1 \rightarrow x = 1$; thus $\overline \psi := \forall x (x=1 \rightarrow x = 1)$.

It is an easy task of propositional logic to prove that :

$x = 1 \vdash (x= 1 \rightarrow x = 1) \leftrightarrow x=1$

i.e. that $\Sigma \vdash \phi \leftrightarrow \overline \phi$.

But we have that $\Sigma \nvdash \psi \leftrightarrow \overline \psi$, i.e. :

$x = 1 \nvdash \forall x (x= 1 \rightarrow x = 1) \leftrightarrow \forall x (x=1)$.

The bi-conditional is not provable because, in the interpretation with domain $\mathbb N$ (but it is enough to consider as domain the subset $\{ 0,1 \}$ of $\mathbb N$), $\forall x (x=1)$ is false, while $\forall x (x= 1 \rightarrow x = 1)$ is always true.