Show (a) $\forall x A \models A$ (b) $A \models ^x \forall x A $ (c) $A \models \forall x A$ does not hold in general.

Question

This question is from Mathematical Logic by Kleene page 107, Exercise 20.5. https://cdn.preterhuman.net/texts/math/Kleene%20%20Mathemathical%20logic%20scaned%20by%20YRB.pdf

The meaning of $\models ^x$ is on page 106. I'm still not entirely sure what is meant by it. $A$ is any formula containg any number of variables and connectives.

Show that for any variable $x$ and any formula $A$: (a) $\forall x A \models A$. (b) $A \models ^x \forall x A $. (c) "$A \models \forall x A$" does not hold in general.

It seems to me (a) and (b) do in fact hold in general and only (c) does not. Maybe question is not worded properly.

Extra: I also have trouble with understanding what to do for Exercise 19.1 on page 101, if anyone can take the trouble to read the relevant section, section 19, to explain to me what Ex 19.1 is about that would be greatly appreciated.

Answer 1

Your interpretation of the Exercise is not correct... We have fullstops and not commas:

Show that for any variable $x$ and any formula $A$: (a) $∀xA⊨A$. (b) $A⊨^x∀xA$.(c) "$A ⊨ ∀xA$" does not hold in general.

Thus, you are right: (a) and (b) hold: you have to prove them, while (c) does not: give a counter-example.

---

Note 1: in a nutshell, $A⊨^x∀xA$ is simply $∀xA⊨∀xA$.

Note 2: for (c), see the definition of $\vDash$ (page 101): for a counterexample to: "$A \vDash ∀xA$", consider $x=0$ as $A$.

This definition of logical consequence can be rewritten (in "more modern" terms) as follows (see: Enderton, page 88):

Let $\Gamma$ be a set of formulas, $\varphi$ a formula. Then $\Gamma$ logically implies $\varphi$, written $\Gamma \vDash \varphi$, iff for every interpretation $\mathcal M$ with domain $M$ and every variable assignment function $s$ such that $\mathcal M$ satisfies every member of $\Gamma$ with $s$, $\mathcal M$ also satisfies $\varphi$ with $s$ (in symbols: $\mathcal M,s \vDash \varphi$).

Now, we have to consider the variable assignment function $s$ such that $s(x)=0$. Clearly: $\mathcal M,s \vDash (x=0)$ but $\mathcal M,s \nvDash \forall x \ (x=0)$.

---

---

For Ex.19.1, consider page 98: we have a formula $A(y) \to \exists x A(x)$ and we want to susbt in place of $A$ the formula $\forall z Q(w,z,w)$ which, having $w$ free, we call $A(w)$.

For the LHS, we have $A(y)$ with $y$ free; thus we have to subst it with $A(w)$, with $y$ in place of $w$, i.e. $\forall z \ Q(y,z,y)$.

For the RHS, we have $A(x)$, i.e. $\forall z \ Q(x,z,x)$, in the scope of the quantifier $\exists x$.

The result is:

$\forall z \ Q(y,z,y) \to \exists x \ \forall z \ Q(x,z,x)$.

The subs is "free" because no unwanted "capturing" of free variables has occurred.

Now consider the subst of $\exists z \ P(z,w,y)$ and $Q$ as $P(w)$ and $Q$ into: $P(z) \to Q$.

For the subst of $Q$ in place of $Q$, no issue.

For the subst of $\exists z \ P(z,w,y)$, consider again the rewritten formula as: $A(z) \to Q$ and consider $\exists z \ P(z,w,y)$ as $A(w)$ (with $w$ free).

Thus, $A(z)$ will be $\exists z \ P(z,z,y)$ and we have that the previous free occurrence of $w$ has been replaced by an occurrence of $z$ that is bound by the leading quantifier.

Thus, the result: $\exists z \ P(z,z,y) \to Q$ is an example of subst that is no free.