# predicate forms implications

• Sep 20th 2011, 04:01 PM
demode
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?
• 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 $\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.
• Sep 21st 2011, 10:32 PM
demode
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...
• Sep 22nd 2011, 01:22 AM
emakarov
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$.