tricky question about substituting a logical variable

Question

sadly, i don't know how to solve this question, so i cannot give my input on what i did, only my thoughts.

let $φ$ be a formula with a free variable $x$. for another variable, let's say $y$: $φ(y)=sub(φ,x,y)$ is $φ$ where each occurrence of $x$ is replaced with $y$.

1)prove that if $y$ is not in $φ$, then $\forall y φ(y) \equiv \forall x φ$

2)give an example where $y$ does occur in $φ$ and the equivalence does not happen

3)give an example where $y$ does occur in $φ$, but the equivalence does occur.

i honestly don't quite understand this question, so i would really appreciate your help with it.

the way i think about it, is that if we can how in 1)that if $y$ is not in $φ$, then we might be able to use it in 3 using material implication ($(p \lor q) :: (~p ⊃ q)$).regarding 2) i can't find a way to contradict if $y$ is there.

another way i thought of using is to translate the equivalence so we can use de morgan, but i don't know how to continue with that. what i mean is by using the following relation $(p ≡ q) :: ((p ∙ q) \lor (~p ∙ ~q))$, or if we wanted to use material implication or transposition, we could use the following relation: $(p ≡ q) ::((p ⊃ q) ∙ (q ⊃ p))$ (and then transposition after solving 1) to show that 3 still holds).

Answer 1

It's basically a matter of the meaning of the quantifier. There is a related kind of substitution $φ[y/x]$ that denotes "$φ$ with every free occurrence of $x$ substituted by $y$". Take a look at this section to see the difference between $φ[y/x]$ and $sub(φ,x,y)$, and to understand why the latter substitution may not yield an equivalent formula if $y$ occurs in $φ$.

The bottom-line is that in "$\forall x (φ)$" the "$\forall x$" only captures the free occurrences of $x$ in $φ$, and if you want to rename the quantified variable $x$ to $y$ then you should only rename the occurrences of $x$ that are captured by the quantifier. If you rename other occurrences of $x$, you may change the meaning of the formula because those other occurrences may be bound by a quantifier in $φ$.

The above should address (1) and (2). For (1) in particular, the definition of the interpretation of "$\forall x (φ)$" in a model $M$ is precisely that $φ[a/x]$ is true for every element $a$ in $M$, where $φ[a/x]$ is "$φ$ with every free occurrence of $x$ in $φ$ interpreted as $a$". In logic textbooks you may see instead a recursive definition of satisfaction by interpretation ("$I \vDash P$" means "Under the interpretation $I$, the formula $P$ is satisfied/true.") such as:

If $P = \neg Q$ then $I \vDash P$ iff $I \nvDash Q$.

If $P = Q \land R$ then $I \vDash P$ iff ( $I \vDash Q$ and $I \vDash R$ ).

[Similarly for the other boolean connectives.]

If $P = \forall x (Q)$ then $I \vDash P$ iff ( $I[x:=a] \vDash Q$ for every element $a$ in $M$ ).

[Similarly for the existential quantifier.]

In this kind of definition, an interpretation $I$ specifies the interpretation (or binding) of every free variable, and "$I[x:=a]$" denotes the interpretation that is the same as $I$ except that $x$ is interpreted as $a$ (the original binding is discarded). This also means that later bindings take precedence. For example $I[x:=a][x:=b]$ would bind $x$ to $b$ rather than $a$.

This corresponds to the intuitive definition given earlier, where an inner nested quantifier takes precedence over an outer one if they quantify over the same variable. But this definition is formal, and so you can rigorously prove (1).

For (3), you just need to find some formula $φ$ that has an occurrence of $y$ but whose meaning does not change when you substitute $x$ for $y$. It is actually quite simple, so I'll leave it to you.

---

Further details as requested:

For (3), one way that the meaning of a formula does not change when you perform a substitution is if literally nothing was changed.

For (2), consider "$\exists y ( y \ne x )$". Its meaning would change if you substitute "$x$" with "$y$".

For (1), prove that under every interpretation $I$ with domain $M$, "$\forall x (φ)$" and "$\forall y (sub(φ,x,y))$" are both true or both false. To do so we can first prove that the recursive definition implies the following lemma:

If $y$ does not occur in $P$, then $I[x:=a] \vDash P$ iff $I[y:=a] \vDash sub(P,x,y)$.

We can prove this by structural induction on the definition of satisfaction. Namely, you show that if this is true for all shorter formulae than $P$ then this is also true for $P$. The induction step is easy for all the boolean connectives. For example if $P = Q \land R$ then:

  $I[x:=a] \vDash P$

  iff $I[x:=a] \vDash Q \land R$

  iff ( $I[x:=a] \vDash Q$ and $I[x:=a] \vDash R$ )

  iff ( $I[y:=a] \vDash sub(Q,x,y)$ and $I[y:=a] \vDash sub(R,x,y)$ )   [by the lemma on $Q,R$]

  iff $I[y:=a] \vDash sub(Q,x,y) \land sub(R,x,y)$

  iff $I[y:=a] \vDash sub( Q \land R ,x,y)$   [by definition of substitution]

  iff $I[y:=a] \vDash sub(P,x,y)$.

Please handle the cases for the other boolean connectives yourself.

What is left is the quantifier case. If $P = \forall z (Q)$ then we already know that $z$ is different from $y$.

If $z$ is different from $x$ then:

  $I[x:=a] \vDash P$

  iff $I[x:=a][z:=b] \vDash Q$ for every element $b$ in $M$

  iff $I[z:=b][x:=a] \vDash Q$ for every element $b$ in $M$

  iff $I[z:=b][y:=a] \vDash sub(Q,x,y)$ for every element $b$ in $M$   [by the lemma on $Q$]

  iff $I[y:=a][z:=b] \vDash sub(Q,x,y)$ for every element $b$ in $M$

  iff $I[y:=a] \vDash \forall z (sub(Q,x,y))$

  iff $I[y:=a] \vDash sub(P,x,y)$.

If $z$ is the same as $x$ then:

  $I[x:=a] \vDash P$

  iff $I[x:=a][x:=b] \vDash Q$ for every element $b$ in $M$

  iff $I[x:=b] \vDash Q$ for every element $b$ in $M$

  iff $I[y:=b] \vDash sub(Q,x,y)$ for every element $b$ in $M$   [by the lemma on $Q$]

  iff $I[y:=a] \vDash sub(Q,x,y)$ for every element $a$ in $M$

  iff $I[y:=a][y:=a] \vDash sub(Q,x,y)$ for every element $a$ in $M$

  iff $I[y:=a] \vDash \forall y (sub(Q,x,y))$

  iff $I[y:=a] \vDash sub(P,x,y)$.

Using this lemma it is trivial to prove (1); under every interpretation $I$ with domain $M$ and $y$ not occurring in $φ$ we have:

  $I \vDash \forall x (φ)$

  iff $I[x:=a] \vDash φ$ for every element $a$ in $M$

  iff $I[y:=a] \vDash sub(φ,x,y)$ for every element $a$ in $M$   [by the lemma]

  iff $I \vDash \forall y (sub(φ,x,y))$.

Answer 2

Hint

Let $φ$ be a formula with a free variable $x$. Let's say : $φ(y)=sub(φ,x,y)$ is $φ$ where each occurrence of $x$ is replaced with $y$.

Prove that if $y$ is not in $φ$, then $∀yφ(y)≡∀xφ$.

The result is obvious: if $\varphi$ holds for "all", it holds for every object of the domain, irrespective of the bound variable we use in the universal quantifier.

A syntactical proof will use the axiom $\forall x \varphi \to \varphi[t/x]$ (where I've used $\varphi[t/x]$ to mean the substitution of each free occurrence of $x$ with $t$) as well as the Generalization Th :

if $\Gamma \vdash \varphi$ and $x$ is not free in $\Gamma$, then $\Gamma \vdash ∀x φ$.

A semantical proof exploit the fact that the universally quantified formula $\forall x \varphi$ will be satisfied in a model by a variable assignment $s$ iff it is satisfied by every variable assignment $s'$ that differ from $s$ only in the object assigned to $x$.

---

For 2), consider as $φ$ the formula :

$(x=y)$.

Thus, $φ[y/x]$ will be $(y=y)$ and $∀yφ(y)$ is$∀y(y=y)$, which is valid (always true).

But $∀xφ$ is $∀x(x=y)$, that is not always true.