Proof about logic interpretations and formulas

84 Views Asked by At

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.

1

There are 1 best solutions below

8
On BEST ANSWER

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.