# 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 $\displaystyle I \models_v \exists x (A \vee B)$. We wish to show that $\displaystyle 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 $\displaystyle A^I(d)$ holds for all $\displaystyle d \in D$:

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

Case 2: There is some $\displaystyle d \in D$ such that $\displaystyle A^I(d)$ does not hold... And we assumed that there is a d such that $\displaystyle 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 $\displaystyle I\models A$, but here are some remarks.

What is $\displaystyle 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 $\displaystyle A^I(d)$ holds for all d. One should use the fact that if x is not free in A, then $\displaystyle I\models_{v\frac{d}{x}}A$ iff $\displaystyle I\models_{v}A$. So, if $\displaystyle I \models_v \exists x (A \vee B)$, then there is a $\displaystyle d\in D$ such that $\displaystyle I\models_{v\frac{d}{x}}A\lor B$. If $\displaystyle I\models_{v\frac{d}{x}}A$, then $\displaystyle I\models_{v}A$ and so $\displaystyle I \models_v A\lor\exists x\, B$. If $\displaystyle I\models_{v\frac{d}{x}}B$, then $\displaystyle I\models_{v}\exists x\,B$ and so $\displaystyle I \models_v A\lor\exists x\, B$.