# Predicate Forms

• Sep 20th 2011, 03:17 PM
demode
Predicate Forms
http://img5.imageshack.us/img5/4056/thequestion.jpg

Here's my attempt so far in proving the equivalence:

The question says "x does not occur freely in A" (which means it is either the variable immediately following a quantifier or it is in the scope of some quantifier involving x). Let I be an interpetation with domain on D, and v be an I-assignment. Suppose $I \models_v \exists x (A \vee B)$. We wish to show that $I \models_v (A \vee \exists x B)$. I don't know if this is correct but I'm considering two cases depending on wether $A^I(d)$ holds for all $d \in D$:

Case 1: $A^I(d)$ holds for all $d \in D$. So $I \models_{v \frac{d}{x}} A$ so $I \models_{v \frac{d}{x}} (A \vee \exists x B)$. Is this correct?

Case 2: There is some $d \in D$ such that $A^I(d)$ does not hold... And we assumed that there is a d such that $I \models_{v\frac{d}{x}} (A \vee B)$. But how can I complete this part?

I greatly appreciate any help on how to prove this question...
• Sep 21st 2011, 03:11 AM
emakarov
Re: Predicate Forms
The exact details depend on the definition of $I\models A$, but here are some remarks.

What is $A^l(d)$? The formula A does not depend on x, so there is no sense in providing d to it.

The proof of equivalence should not require considering whether $A^I(d)$ holds for all d. One should use the fact that if x is not free in A, then $I\models_{v\frac{d}{x}}A$ iff $I\models_{v}A$. So, if $I \models_v \exists x (A \vee B)$, then there is a $d\in D$ such that $I\models_{v\frac{d}{x}}A\lor B$. If $I\models_{v\frac{d}{x}}A$, then $I\models_{v}A$ and so $I \models_v A\lor\exists x\, B$. If $I\models_{v\frac{d}{x}}B$, then $I\models_{v}\exists x\,B$ and so $I \models_v A\lor\exists x\, B$.