Results 1 to 2 of 2

Thread: Predicate Forms

  1. #1
    Member
    Joined
    Dec 2009
    Posts
    225

    Predicate Forms



    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...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    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$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. predicate forms implications
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Sep 22nd 2011, 01:22 AM
  2. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Mar 23rd 2011, 12:05 PM
  3. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Apr 29th 2010, 03:51 PM
  4. Predicate Calculus
    Posted in the Calculus Forum
    Replies: 1
    Last Post: May 21st 2009, 05:19 PM
  5. Help with predicate logic
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Dec 10th 2008, 05:05 PM

Search Tags


/mathhelpforum @mathhelpforum