# Proof about logic interpretations and formulas

Is this solution for the exercise correct?

Although, by (VI), $(∀x)A(x )$ is true whenever A( x ) is true, find an interpretation for which $A(x)\to\forall xA(x)$ is not true.

By Lemma (seen in class), $\vDash\phi$ iff $\vDash CL(\phi)$ which is the closure of $\phi$, we have $A(x)$ is closed and by (VI), $A(x)$ is true iff $\forall xA(x)$ is true, in particular if $A(x)$ is true, then $\forall xA(x)$ is true as well under any interpretation.

Therefore it's impossible to find an interpretation for which $A(x)\to\forall xA(x)$ is not true.

(VI) $\vDash_M\phi \iff\vDash_M\forall x_i\phi,$ where by definition $\phi$ is closed.

• "P is true whenever Q is true" is not an if and only if statement.
– user14972
Nov 25, 2017 at 3:32
• Why do "we have $A(x)$ is closed"? It doesn't look closed to me, because it has a free variable $x$. Nov 25, 2017 at 4:13
• @AndreasBlass Closed if it's true under an interpretation M, but I don't know if I can make that assumption. Nov 25, 2017 at 4:17
• It seems you're using "closed" to mean something other than "having no free variables", but I have no idea what that other meaning might be. Nov 25, 2017 at 4:21
• $(x=0) \to \forall x (x=0)$ is not true in $\mathbb N$ because its closure: $\forall x ((x=0) \to \forall x (x=0))$ is not true in $\mathbb N$. Nov 25, 2017 at 14:34

What your statement (IV) says, is that if $\phi$ is closed, then we have $\vDash\phi \iff\vDash\forall x\phi$

Essentially, what your task wants to emphasize is that the condition that $\phi$ needs to be closed is really necessary, so they want you to realize that $\vDash\phi \iff\vDash\forall x\phi$ does not hold if we don't require $\phi$ to be closed. Your task already gives you a hint as of which direction of this $\iff$ does not hold. Additionally it hints at the fact that a formula of the form $\phi=A(x)$ is already enough to find a counterexample.

So now to the counterexample: You know that $\vDash\phi \iff\vDash\forall x\phi$ holds for all closed $\phi$. As you want to find a counterexample, you know this counterexample can't be closed, and indeed your $\phi=A(x)$ is not closed, as $x$ is free.

For the interpretation you can do pretty much do anything you want, let me just give you one example for an interpretation $I$ over the domain $\mathbb{N}$:

$I(x)=5$

$I(A)=\{n:n<7\}$

So basically what this task shows, is that just because a statement is true for some interpretation, it does not necessarily mean the statement is true for all interpretations.

• I don't understand the way you gave the interpretations, it's supposed to write $A(x)=...$, and then $I(A)=F$ or $I(A)=V$ Nov 26, 2017 at 1:17
• An interpretation is just a function. It maps all free variables ($x$ for us) to some element in the domain ($\mathbb{N}$) and all predicates ($A$) to a subset of the domain. $A(x)$ is true iff $I(x) \in I(A)$ or in other words, $I(A)$ specifies all domain elements for which $A$ returns true. So with our interpretation, $A(x)$ is true. However, $\forall x A(x)$ is not true, because not all numbers are smaller than 7. (Note that this is not the free $x$ we interpreted. It has nothing to do with that $x$, it's a different $x$ in the scope of the $\forall$). Nov 26, 2017 at 2:45
• By the way I imagine there are different ways to write down interpretations, and to be honest I'm only familiar with the one I was taught. So feel free to use the notation you learned. Nov 26, 2017 at 2:49
• What does A(x) mean in our interpretation? $A(x)=\{n:n<7\}$? Nov 26, 2017 at 3:10
• Exactly, with our interpretation of $A$, $A(x)$ is true for some $x$, but not all. That means $\forall x A(x)$ is false. But whether $A(x)$ is true only depends on our interpretation of $x$, so we can chose an $x$ for which $x$ is true (i.e. a witness for $\exists x A(x)$). So with our interpretation of $x$ and $A$, we have that $A(x)$ is true, but $\forall x A(x)$ is not. Therefore we don't have $A(x) \to \forall x A(x)$ with our interpretation $I$, which is exactly what the task asked us. Nov 26, 2017 at 3:26