Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Propositional Logic - There Exists dual

  1. Dec 3, 2007 #1
    Propositional Logic - "There Exists" dual

    1. The problem statement, all variables and given/known data
    "State and prove the [itex]\exists[/itex]-dual of 6.1.8"

    Section 6.1.8 shows how to change [itex]\vdash (\forall x)(\forall y)A \equiv (\forall y)(\forall x)A[/itex] via this method:

    (Line 1) [itex](\forall x)(\forall y)A[/itex] (Hypothesis)
    (Line 2) [itex](\forall y)A[/itex] (Line 1 + spec)
    (Line 3) [itex]A[/itex] (Line 2 + spec)
    (Line 4) [itex](\forall x)A[/itex] (Line 3 + gen; Line 1 has no free x)
    (Line 5) [itex](\forall y)(\forall x)A[/itex] (Line 4 + gen; Line 1 has no free y)

    The [itex]\exists[/itex]-dual of this would be to show [itex]\vdash (\exists x)(\exists y)A \equiv (\exists y)(\exists x)A[/itex].

    2. Relevant equations
    A crucial formula here is that [itex](\forall x)A \equiv \neg (\exists x) \neg A[/itex]

    3. The attempt at a solution
    I potentially solved it, but something seems off.

    This is what I did:

    [itex]\vdash (\exists x)(\exists y)A \equiv (\exists y)(\exists x)A[/itex]

    (Line 1) [itex](\exists x)(\exists y)A[/itex]
    (Line 2) [itex]\neg (\forall x)\neg (\exists y)A[/itex] Definition of [itex]\exists[/itex]
    (Line 3) [itex]\neg (\forall x)\neg \neg (\forall y)\neg A[/itex] Definition of [itex]\exists[/itex]
    (Line 4) [itex]\neg (\forall x)(\forall y)\neg A[/itex] Double negative
    (Line 5) [itex]\neg (\forall y)\neg A[/itex] Spec
    (Line 6) [itex]\neg \neg A[/itex] Spec
    (Line 7) [itex]\neg (\forall x)\neg A[/itex] Gen
    (Line 8) [itex]\neg (\forall y)(\forall x)\neg A[/itex] Gen
    (Line 9) [itex]\neg (\forall y)\neg \neg (\forall x)\neg A[/itex] Double negative
    (Line 10) [itex]\neg (\forall y)\neg (\exists x)A[/itex] Definition of [itex]\forall[/itex]
    (Line 11) [itex](\exists y)(\exists x)A[/itex] Definition of [itex]\forall[/itex]

    What worries me is going from Line 5 to 6, what happens to the first [itex]\neg[/itex] symbol? Can I just leave it there, and then insert my [itex](\forall x)[/itex] between the two [itex]\neg[/itex]s in Line 7 like that?
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted