# First order logic

• Nov 15th 2011, 04:51 PM
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.
• Nov 16th 2011, 03:42 AM
emakarov
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 $\displaystyle \phi^x_t\to\exists x.\,\phi$? Also, are you allowed to use the deduction theorem?
• Nov 16th 2011, 08:09 AM
Re: First order logic
Quote:

Originally Posted by emakarov
Is ∃x.ϕ defined as ¬∀x.¬ϕ, since the axioms don't mention ∃? Do you have any previously derived theorems about ∃, such as $\displaystyle \phi^x_t\to\exists x.\,\phi$? Also, are you allowed to use the deduction theorem?

Thanks,
Yes I believe that $\displaystyle \phi^x_t\to\exists x.\,\phi$ would be okay. And I'm allowed to use the deduction theorem.

Thank you.
• Nov 16th 2011, 08:41 AM
emakarov
Re: First order logic
The idea is to assume $\displaystyle \forall x.\,\phi$ and $\displaystyle \forall x.\,\neg\phi$, then instantiate both quantifiers to x and derive $\displaystyle \phi\land\neg\phi$. Then by deduction theorem $\displaystyle \forall x.\,\phi\vdash (\forall x.\,\neg\phi)\to\phi\land\neg\phi$, from where one has to derive $\displaystyle \forall x.\,\phi\vdash\neg\forall x.\,\neg\phi$. It would help to first derive $\displaystyle (A\to B\land\neg B)\to\neg A$ for all formulas A and B.