Results 1 to 4 of 4

Math Help - First order logic

  1. #1
    Newbie
    Joined
    Nov 2011
    Posts
    4

    First order logic

    Hi, I have no idea how to begin constructing this proof, and I would appreciate any help!

    I need to prove the following, and to make matters worse, without soundness or completeness

    ⊢ (∀x.ϕ) →(∃x.ϕ)

    I can use the following axioms/theorems http://img233.imageshack.us/img233/5...11115at824.png Thank you.
    Please note that any sort of help to get me started on the proof would be very helpful.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: First order logic

    Is ∃x.ϕ defined as ∀x.ϕ, since the axioms don't mention ∃? Do you have any previously derived theorems about ∃, such as \phi^x_t\to\exists x.\,\phi? Also, are you allowed to use the deduction theorem?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2011
    Posts
    4

    Re: First order logic

    Quote Originally Posted by emakarov View Post
    Is ∃x.ϕ defined as ∀x.ϕ, since the axioms don't mention ∃? Do you have any previously derived theorems about ∃, such as \phi^x_t\to\exists x.\,\phi? Also, are you allowed to use the deduction theorem?
    Thanks,
    Yes I believe that \phi^x_t\to\exists x.\,\phi would be okay. And I'm allowed to use the deduction theorem.

    Thank you.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: First order logic

    The idea is to assume \forall x.\,\phi and \forall x.\,\neg\phi, then instantiate both quantifiers to x and derive \phi\land\neg\phi. Then by deduction theorem \forall x.\,\phi\vdash (\forall x.\,\neg\phi)\to\phi\land\neg\phi, from where one has to derive \forall x.\,\phi\vdash\neg\forall x.\,\neg\phi. It would help to first derive (A\to B\land\neg B)\to\neg A for all formulas A and B.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Complexity of SAT in First-order logic
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 6th 2011, 09:01 AM
  2. First Order Logic help with corrections.
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 22nd 2011, 01:51 PM
  3. First order logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 10th 2011, 07:10 AM
  4. First order Logic
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 16th 2011, 04:41 AM
  5. First order Logic!
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: January 3rd 2011, 10:55 AM

Search Tags


/mathhelpforum @mathhelpforum