# predicate forms implications

• Sep 20th 2011, 04:01 PM
demode
predicate forms implications
http://img18.imageshack.us/img18/8937/13877630.jpg

Attempt:

(a) Let $I$ be an interpetation, and let $v$ be an I-assignment.
Suppose that $I \models_v A$. We want $I \models_v \exists x A$. And we know that $I \models_v \exists x A$ iff there is some $d \in D$ with $I \models_{v \frac{d}{x}}A$. But how do we show that we have such a d?

(b) Suppose $I \models_v \exists x Ax$, I have to show that $I \not{\models_v} Ax$. But I'm confused because assuming $I \models_v \exists x Ax$ means there is some d in the domain with $I \models_{v \frac{d}{x}} Ax$. What could I do? Are there better ways to show that the implication doesn't hold?
• Sep 21st 2011, 11:49 AM
emakarov
Re: predicate forms implications
Again, one should use the property that if x is not free in B, then $I\models_{v\frac{d}{x}}B$ iff $I\models_v B$.

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

For (b), suppose that $I\models_v\exists x\,Ax$, which means that $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 $I\models_v Ax$. You should construct a counterexample.
• Sep 21st 2011, 10:32 PM
demode
Re: predicate forms implications
Quote:

Originally Posted by emakarov
For (b), suppose that $I\models_v\exists x\,Ax$, which means that $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 $I\models_v Ax$. You should construct a counterexample.

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

P.S. Normally, when we give counter-examples for implications involving 2 variables we use an interpetation such that $A^I(m,n)$ holding iff $m, 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...
• Sep 22nd 2011, 01:22 AM
emakarov
Re: predicate forms implications
Let the carrier of I be natural numbers and $A^I(m)$ hold iff m is even. Let also v map a single variable x to 3. Then $I\models_v\exists x\,Ax$, but $I\not\models_v Ax$.