0
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ "P is true whenever Q is true" is not an if and only if statement. $\endgroup$
    – user14972
    Nov 25, 2017 at 3:32
  • $\begingroup$ Why do "we have $A(x)$ is closed"? It doesn't look closed to me, because it has a free variable $x$. $\endgroup$ Nov 25, 2017 at 4:13
  • $\begingroup$ @AndreasBlass Closed if it's true under an interpretation M, but I don't know if I can make that assumption. $\endgroup$ Nov 25, 2017 at 4:17
  • $\begingroup$ 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. $\endgroup$ Nov 25, 2017 at 4:21
  • 1
    $\begingroup$ $(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$. $\endgroup$ Nov 25, 2017 at 14:34

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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 $ $\endgroup$ Nov 26, 2017 at 1:17
  • 1
    $\begingroup$ 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$). $\endgroup$
    – PattuX
    Nov 26, 2017 at 2:45
  • $\begingroup$ 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. $\endgroup$
    – PattuX
    Nov 26, 2017 at 2:49
  • $\begingroup$ What does A(x) mean in our interpretation? $A(x)=\{n:n<7\}$? $\endgroup$ Nov 26, 2017 at 3:10
  • 1
    $\begingroup$ 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. $\endgroup$
    – PattuX
    Nov 26, 2017 at 3:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.