predicate forms implications

**http://img18.imageshack.us/img18/8937/13877630.jpg**

**Attempt:**

**(a)** Let $\displaystyle I$ be an interpetation, and let $\displaystyle v$ be an I-assignment.

Suppose that $\displaystyle I \models_v A$. We want $\displaystyle I \models_v \exists x A$. And we know that $\displaystyle I \models_v \exists x A$ iff there is some $\displaystyle d \in D$ with $\displaystyle I \models_{v \frac{d}{x}}A$. But how do we show that we have such a d?

**(b)** Suppose $\displaystyle I \models_v \exists x Ax$, I have to show that $\displaystyle I \not{\models_v} Ax$. But I'm confused because assuming $\displaystyle I \models_v \exists x Ax$ means there is some d in the domain with $\displaystyle I \models_{v \frac{d}{x}} Ax$. What could I do? Are there better ways to show that the implication doesn't hold?

Re: predicate forms implications

Again, one should use the property that if x is not free in B, then $\displaystyle I\models_{v\frac{d}{x}}B$ iff $\displaystyle I\models_v B$.

For (a), suppose that v maps x to d, i.e., $\displaystyle v=v'\frac{d}{x}$ for some smaller v'. Then $\displaystyle I\models_v A$ means $\displaystyle I\models_{v'\frac{d}{x}}A$, so $\displaystyle I\models_{v'}\exists x\,A$ and by the property above, $\displaystyle I\models_v\exists x\,A$.

For (b), suppose that $\displaystyle I\models_v\exists x\,Ax$, which means that $\displaystyle I\models_{v\frac{d}{y}}Ay$ for some d. However, v does not have to map x to this particular d, so there is no reason for $\displaystyle I\models_v Ax$. You should construct a counterexample.

Re: predicate forms implications

Quote:

Originally Posted by

**emakarov** For (b), suppose that $\displaystyle I\models_v\exists x\,Ax$, which means that $\displaystyle I\models_{v\frac{d}{y}}Ay$ for some d. However, v does not have to map x to this particular d, so there is no reason for $\displaystyle I\models_v Ax$. You should construct a counterexample.

To give a counter example, can $\displaystyle I$ be an interpetation holding iff the variable $\displaystyle x$ is even? Then $\displaystyle I \models_v \exists x A$ means that $\displaystyle I \models_{v \frac{d}{x}}Ax$ for some $\displaystyle d$ which is even. On the right hand side of the implication we have $\displaystyle Ax$ without any quantifiers before it. So this $\displaystyle x$ doesn't have to be $\displaystyle d$, it could be an odd number $\displaystyle e$. Is this correct?

P.S. Normally, when we give counter-examples for implications involving 2 variables we use an interpetation such that $\displaystyle A^I(m,n)$ holding iff $\displaystyle m<n$, then it's easy to use natural numbers as the domain to get a counter example. But here since here we have a single variable I'm not sure what kind of counter-example to use...

Re: predicate forms implications

Let the carrier of I be natural numbers and $\displaystyle A^I(m)$ hold iff m is even. Let also v map a single variable x to 3. Then $\displaystyle I\models_v\exists x\,Ax$, but $\displaystyle I\not\models_v Ax$.